Impact of memory hierarchy on program partitioning and scheduling

Author

Kaplow, Wesley K. ; Maniatty, William A. ; Szymanski, Boleslaw K.

Author_Institution

Dept. of Comput. Sci., Rensselaer Polytech. Inst., Troy, NY, USA

Volume

2

fYear

1995

fDate

3-6 Jan 1995

Firstpage

93

Abstract

Presents a method for determining the cache performance of the loop nests in a program. The cache-miss data are produced by simulating the loop nest execution on an architecturally parameterized cache simulator. We show that the cache-miss rates are highly non-linear with respect to the ranges of the loops, and correlate well with the performance of the loop nests on actual target machines. The cache-miss ratio is used to guide program optimizations such as loop interchange and iteration-space blocking. It can also be used to provide an estimate for the runtime of a program. Both applications are important in scheduling programs for parallel execution. We present examples of program optimization for several popular processors, such as the IBM 9076 SP1, the SuperSPARC and the Intel i860

Keywords

cache storage; memory architecture; optimisation; parallel programming; processor scheduling; program control structures; scheduling; software performance evaluation; IBM 9076 SP1; Intel i860; SuperSPARC; architecturally parameterized cache simulator; cache performance; cache-miss ratio; iteration-space blocking; loop interchange; loop nest execution simulation; loop range; memory hierarchy; nonlinear cache-miss rates; parallel program scheduling; program optimization; program partitioning; program runtime estimation; Binary search trees; Clocks; Computational modeling; Computer science; Economic indicators; High performance computing; Jacobian matrices; Processor scheduling; Program processors; Runtime;

fLanguage

English

Publisher

ieee

Conference_Titel

System Sciences, 1995. Proceedings of the Twenty-Eighth Hawaii International Conference on

Conference_Location

Wailea, HI

Print_ISBN

0-8186-6930-6

Type

conf

DOI

10.1109/HICSS.1995.375473

Filename

375473