The evolution of computing technology towards the ultimate physical limits makes communication the dominant cost of computing. It would then be desirable to have a framework for the study of locality, which we define as the property of an algorithm that enables implementations with reduced communication overheads. We discuss the issue of useful characterizations of the locality of an algorithm with reference to both single machines and classes of machines. We then consider the question of portability of locality. We illustrate the proposed approach with its application to the study of temporal locality, the property of an algorithm that enables efficient implementations on machines where memory accesses have a variable latency, depending on the location being accessed. We discuss how, for a fixed operation schedule, temporal locality can be characterized for interesting classes of uniform hierarchical machines by a set of metrics, the width lengths of the schedule. Moreover, a portable memory management of any schedule can be obtained for such classes of machines. The situation becomes more complex when the schedule is a degree of freedom of the implementation. Then, while some computations do admit a single schedule, optimal across many machines, this is not always the case. Thus, in general, only the less stringent notion of portability based on parametrized schedules can be pursued. Correspondingly, a concise characterization of temporal locality becomes harder to achieve and still remains an open problem

An Approach toward an Analytical Characterization of Locality and its Portability

BILARDI, GIANFRANCO;PESERICO STECCHINI NEGRI DE SALVI, ENOCH
2001

Abstract

The evolution of computing technology towards the ultimate physical limits makes communication the dominant cost of computing. It would then be desirable to have a framework for the study of locality, which we define as the property of an algorithm that enables implementations with reduced communication overheads. We discuss the issue of useful characterizations of the locality of an algorithm with reference to both single machines and classes of machines. We then consider the question of portability of locality. We illustrate the proposed approach with its application to the study of temporal locality, the property of an algorithm that enables efficient implementations on machines where memory accesses have a variable latency, depending on the location being accessed. We discuss how, for a fixed operation schedule, temporal locality can be characterized for interesting classes of uniform hierarchical machines by a set of metrics, the width lengths of the schedule. Moreover, a portable memory management of any schedule can be obtained for such classes of machines. The situation becomes more complex when the schedule is a degree of freedom of the implementation. Then, while some computations do admit a single schedule, optimal across many machines, this is not always the case. Thus, in general, only the less stringent notion of portability based on parametrized schedules can be pursued. Correspondingly, a concise characterization of temporal locality becomes harder to achieve and still remains an open problem
2001
Proc. of IWIA 2001
0769513093
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/2463759
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact