A Characterization of Temporal Locality and Its Portability across Memory Hierarchies
A Characterization of Temporal Locality and Its Portability across Memory Hierarchies
复制标题
DOI：
10.1007/3-540-48224-5_11
复制
发表时间：
2001-07
期刊：
影响因子：
--
通讯作者：
G. Bilardi;E. Peserico
中科院分区：
文献类型：
--
作者：
G. Bilardi;E. Peserico
本文提出并研究了一个给定算法是否能够以一种有效地在具有不同层次存储系统的机器上移植的方式进行编码的问题，模型为asa(x)-HRAMs（层次ram），其中访问位置的时间为xisa(x)。提出了宽度分解框架，通过一组合适的空间重用参数提供计算的时间局部性的机器独立表征。使用这个框架，可以看到，当调度（即操作执行的顺序）是固定的，就可以实现高效的可移植性。我们提出了(a)分解树内存管理器，它在所有hram上实现了对数因子内的最优时间，以及(b)发生宽度内存管理器，它在重要的均匀hram类上实现了常数因子内的最优时间。我们还表明，当将调度视为实现的自由度时，存在其最优调度随访问函数而变化的计算。特别地，我们展示了一些计算，其中任何调度在两台足够不同的机器中的至少一台上必然比最优调度慢一个多项式因子。从积极的方面来看，我们表明相对较少的调度足以在广泛的hram类别上提供接近最优的解决方案。
This paper formulates and investigates the question of whether a given algorithm can be coded in a way efficiently portable across machines with different hierarchical memory systems, modeled asa(x)-HRAMs (Hierarchical RAMs), where the time to access a locationxisa(x).Thewidth decompositionframework is proposed to provide a machine- independent characterization of temporal locality of a computation by a suitable set ofspace reuseparameters. Using this framework, it is shown that, when theschedule, i.e. the order by which operations are executed, is fixed, efficient portability is achievable. We propose (a) thedecomposition-treememory manager, which achieves time within a logarithmic factor of optimal on all HRAMs, and (b) thereoccurrence-widthmemory manager, which achieves time within a constant factor of optimal for the important class ofuniformHRAMs.We also show that, when the schedule is considered as a degree of freedom of the implementation, there are computations whose optimal schedule does vary with the access function. In particular, we exhibit some computations for which any schedule is bound to be a polynomial factor slower than optimal on at least one of two sufficiently different machines. On the positive side, we show that relatively few schedules are sufficient to provide a near optimal solution on a wide class of HRAMs.