Skip to main content

Exact analysis of the cache behavior of nested loops

Publication ,  Conference
Chatterjee, S; Parker, E; Hanlon, PJ; Lebeck, AR
Published in: Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)
January 1, 2001

We develop from first principles an exact model of the behavior of loop nests executing in a memory hierarchy, by using a nontraditional classification of misses that has the key property of composability. We use Presburger formulas to express various kinds of misses as well as the state of the cache at the end of the loop nest. We use existing tools to simplify these formulas and to count cache misses. The model is powerful enough to handle imperfect loop nests and various flavors of non-linear array layouts based on bit interleaving of array indices. We also indicate how to handle modest levels of associativity, and how to perform limited symbolic analysis of cache behavior. The complexity of the formulas relates to the static structure of the loop nest rather than to its dynamic trip count, allowing our model to gain efficiency in counting cache misses by exploiting repetitive patterns of cache behavior. Validation against cache simulation confirms the exactness of our formulation. Our method can serv e as the basis for a static performance predictor to guide program and data transformations to improve performance.

Duke Scholars

Published In

Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)

Publication Date

January 1, 2001

Start / End Page

286 / 297
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Chatterjee, S., Parker, E., Hanlon, P. J., & Lebeck, A. R. (2001). Exact analysis of the cache behavior of nested loops. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) (pp. 286–297).
Chatterjee, S., E. Parker, P. J. Hanlon, and A. R. Lebeck. “Exact analysis of the cache behavior of nested loops.” In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 286–97, 2001.
Chatterjee S, Parker E, Hanlon PJ, Lebeck AR. Exact analysis of the cache behavior of nested loops. In: Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 2001. p. 286–97.
Chatterjee, S., et al. “Exact analysis of the cache behavior of nested loops.” Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2001, pp. 286–97.
Chatterjee S, Parker E, Hanlon PJ, Lebeck AR. Exact analysis of the cache behavior of nested loops. Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 2001. p. 286–297.

Published In

Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)

Publication Date

January 1, 2001

Start / End Page

286 / 297