Program analysis for cache coherence: Beyond procedural boundaries

L. Choi; Pen Chung Yew

doi:10.1109/ICPP.1996.538565

Program analysis for cache coherence: Beyond procedural boundaries

L. Choi
, Pen Chung Yew

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Scopus citations

Abstract

The presence of procedures and procedure calls introduces side effects, which complicates the analysis of stale reference detection in compiler-directed cache coherence schemes. Previous compiler algorithms use cache invalidation at procedure boundary or inlining to avoid reference marking interprocedurally. We introduce a full interprocedural algorithm, which performs bottom-up and top-down analysis on the procedure call graph. This avoids unnecessary cache misses for subroutine local data and exploits locality across procedure boundaries. The result of execution-driven simulations on Perfect benchmarks demonstrates that, the interprocedural algorithm eliminates up to 36.8% of the cache misses for a compiler-directed scheme compared to an existing invalidation-based algorithm.

Original language	English (US)
Title of host publication	Software
Editors	K. Pingali
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	103-113
Number of pages	11
ISBN (Electronic)	081867623X
DOIs	https://doi.org/10.1109/ICPP.1996.538565
State	Published - 1996
Event	25th International Conference on Parallel Processing, ICPP 1996 - Ithaca, United States Duration: Aug 12 1996 → Aug 16 1996

Publication series

Name	Proceedings of the International Conference on Parallel Processing
Volume	3
ISSN (Print)	0190-3918

Other

Other	25th International Conference on Parallel Processing, ICPP 1996
Country/Territory	United States
City	Ithaca
Period	8/12/96 → 8/16/96

Bibliographical note

Publisher Copyright:
© 1996 IEEE.

Publisher link

10.1109/ICPP.1996.538565

Find It

Find It at U of M Libraries

Cite this

Program analysis for cache coherence: Beyond procedural boundaries. / Choi, L.; Yew, Pen Chung.
Software. ed. / K. Pingali. Institute of Electrical and Electronics Engineers Inc., 1996. p. 103-113 538565 (Proceedings of the International Conference on Parallel Processing; Vol. 3).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Choi, L & Yew, PC 1996, Program analysis for cache coherence: Beyond procedural boundaries. in K Pingali (ed.), Software., 538565, Proceedings of the International Conference on Parallel Processing, vol. 3, Institute of Electrical and Electronics Engineers Inc., pp. 103-113, 25th International Conference on Parallel Processing, ICPP 1996, Ithaca, United States, 8/12/96. https://doi.org/10.1109/ICPP.1996.538565

@inproceedings{67ca733e80934621b3fb6887fec40cf5,

title = "Program analysis for cache coherence: Beyond procedural boundaries",

abstract = "The presence of procedures and procedure calls introduces side effects, which complicates the analysis of stale reference detection in compiler-directed cache coherence schemes. Previous compiler algorithms use cache invalidation at procedure boundary or inlining to avoid reference marking interprocedurally. We introduce a full interprocedural algorithm, which performs bottom-up and top-down analysis on the procedure call graph. This avoids unnecessary cache misses for subroutine local data and exploits locality across procedure boundaries. The result of execution-driven simulations on Perfect benchmarks demonstrates that, the interprocedural algorithm eliminates up to 36.8\% of the cache misses for a compiler-directed scheme compared to an existing invalidation-based algorithm.",

author = "L. Choi and Yew, \{Pen Chung\}",

note = "Publisher Copyright: {\textcopyright} 1996 IEEE.; 25th International Conference on Parallel Processing, ICPP 1996 ; Conference date: 12-08-1996 Through 16-08-1996",

year = "1996",

doi = "10.1109/ICPP.1996.538565",

language = "English (US)",

series = "Proceedings of the International Conference on Parallel Processing",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "103--113",

editor = "K. Pingali",

booktitle = "Software",

}

TY - GEN

T1 - Program analysis for cache coherence

T2 - 25th International Conference on Parallel Processing, ICPP 1996

AU - Choi, L.

AU - Yew, Pen Chung

PY - 1996

Y1 - 1996

N2 - The presence of procedures and procedure calls introduces side effects, which complicates the analysis of stale reference detection in compiler-directed cache coherence schemes. Previous compiler algorithms use cache invalidation at procedure boundary or inlining to avoid reference marking interprocedurally. We introduce a full interprocedural algorithm, which performs bottom-up and top-down analysis on the procedure call graph. This avoids unnecessary cache misses for subroutine local data and exploits locality across procedure boundaries. The result of execution-driven simulations on Perfect benchmarks demonstrates that, the interprocedural algorithm eliminates up to 36.8% of the cache misses for a compiler-directed scheme compared to an existing invalidation-based algorithm.

AB - The presence of procedures and procedure calls introduces side effects, which complicates the analysis of stale reference detection in compiler-directed cache coherence schemes. Previous compiler algorithms use cache invalidation at procedure boundary or inlining to avoid reference marking interprocedurally. We introduce a full interprocedural algorithm, which performs bottom-up and top-down analysis on the procedure call graph. This avoids unnecessary cache misses for subroutine local data and exploits locality across procedure boundaries. The result of execution-driven simulations on Perfect benchmarks demonstrates that, the interprocedural algorithm eliminates up to 36.8% of the cache misses for a compiler-directed scheme compared to an existing invalidation-based algorithm.

UR - https://www.scopus.com/pages/publications/33749929170

UR - https://www.scopus.com/pages/publications/33749929170#tab=citedBy

U2 - 10.1109/ICPP.1996.538565

DO - 10.1109/ICPP.1996.538565

M3 - Conference contribution

AN - SCOPUS:33749929170

T3 - Proceedings of the International Conference on Parallel Processing

SP - 103

EP - 113

BT - Software

A2 - Pingali, K.

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 12 August 1996 through 16 August 1996

ER -

Program analysis for cache coherence: Beyond procedural boundaries

Abstract

Publication series

Other

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this