Reference distance as a metric for data locality

Author

Pyo, Changwoo ; Lee, Kyung-Woo ; Han, Hye-Kyung ; Lee, Gyungho

Author_Institution

Hongik Univ., Seoul, South Korea

fYear

1997

fDate

28 Apr-2 May 1997

Firstpage

151

Lastpage

156

Abstract

We propose the reference distance as a metric for data locality. Reference distance is the number of referenced memory blocks between two successive references to the same memory block. The effectiveness of program transformations for data locality can be evaluated by using reference distance. Our claim is demonstrated by showing the change in data locality and speedup of matrix multiplication due to loop interchange, loop tiling, and loop unrolling. We also present a result of an experiment using loop distribution and unrolling with respect to two subroutines of Perfect benchmark programs. Reference distance would serve as a useful tool for developing a program transformation scheme for data locality optimization

Keywords

cache storage; data structures; matrix multiplication; optimisation; parallel programming; program control structures; software metrics; software performance evaluation; subroutines; Perfect benchmark programs; cache storage; data locality; loop distribution; loop interchange; loop tiling; loop unrolling; matrix multiplication; metric; optimization; program transformations; reference distance; referenced memory blocks; subroutines; Algorithms; Cache memory; Degradation; Velocity measurement;

fLanguage

English

Publisher

ieee

Conference_Titel

High Performance Computing on the Information Superhighway, 1997. HPC Asia '97

Conference_Location

Seoul

Print_ISBN

0-8186-7901-8

Type

conf

DOI

10.1109/HPC.1997.592139

Filename

592139