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

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

2 Citations (Scopus)

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
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
Publication status	Published - 1996
Externally published	Yes
Event	25th International Conference on Parallel Processing, ICPP 1996 - Ithaca, United States Duration: 1996 Aug 12 → 1996 Aug 16

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	96/8/12 → 96/8/16

Bibliographical note

Funding Information:
We have implemented these algorithms on the Polaris parallelizing compiler [l l], and demonstrated the performance driven by the new compiler algorithms by running execution-driven simulations of five Perfect benchmarks. The results show that by avoiding cache invalidations, the intraprocedural algorithm eliminates up to 26.0% of the cache misses for a compiler-directed scheme compared to an existing invalidation-based algorithm [7]. With the full inter-procedural analysis, up to 10.8% of additional cache misses can be removed. Acknowledgments The research described in this paper was supported in part by the NSF Grant No. MIP 89-20891, MIP 93-07910 and ARPA contract #DABT63-95-C-0097. This work is not necessarily representative of the positions or policies of the Army of the Government. This work was performed while the first author was at the University of Illinois. We thank Hock-Beng Lim at the University of Illinois for his valuable comments.

Publisher Copyright:
© 1996 IEEE.

ASJC Scopus subject areas

Software
General Mathematics
Hardware and Architecture

Access to Document

10.1109/ICPP.1996.538565

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, 96/8/12. https://doi.org/10.1109/ICPP.1996.538565

@inproceedings{63ae6905da1743a094da8561bf5f9464,

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 = "Funding Information: We have implemented these algorithms on the Polaris parallelizing compiler [l l], and demonstrated the performance driven by the new compiler algorithms by running execution-driven simulations of five Perfect benchmarks. The results show that by avoiding cache invalidations, the intraprocedural algorithm eliminates up to 26.0% of the cache misses for a compiler-directed scheme compared to an existing invalidation-based algorithm [7]. With the full inter-procedural analysis, up to 10.8% of additional cache misses can be removed. Acknowledgments The research described in this paper was supported in part by the NSF Grant No. MIP 89-20891, MIP 93-07910 and ARPA contract #DABT63-95-C-0097. This work is not necessarily representative of the positions or policies of the Army of the Government. This work was performed while the first author was at the University of Illinois. We thank Hock-Beng Lim at the University of Illinois for his valuable comments. 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",

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

N1 - Funding Information: We have implemented these algorithms on the Polaris parallelizing compiler [l l], and demonstrated the performance driven by the new compiler algorithms by running execution-driven simulations of five Perfect benchmarks. The results show that by avoiding cache invalidations, the intraprocedural algorithm eliminates up to 26.0% of the cache misses for a compiler-directed scheme compared to an existing invalidation-based algorithm [7]. With the full inter-procedural analysis, up to 10.8% of additional cache misses can be removed. Acknowledgments The research described in this paper was supported in part by the NSF Grant No. MIP 89-20891, MIP 93-07910 and ARPA contract #DABT63-95-C-0097. This work is not necessarily representative of the positions or policies of the Army of the Government. This work was performed while the first author was at the University of Illinois. We thank Hock-Beng Lim at the University of Illinois for his valuable comments. Publisher Copyright: © 1996 IEEE.

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 - http://www.scopus.com/inward/record.url?scp=33749929170&partnerID=8YFLogxK

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

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this