Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Interprocedural array data-flow analysis for cache coherence

  • Conference paper
  • First Online:
Languages and Compilers for Parallel Computing (LCPC 1995)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1033))

Abstract

The presence of procedures and procedure calls introduces side effects, which complicate the analysis of stale reference detection in compiler-directed cache coherence schemes [4, 3, 10]. Previous compiler algorithms use the invalidation of an entire cache at procedure boundary [5, 8] or inlining [8] to avoid reference marking interprocedurally. However, frequent cache invalidations will result in poor performance since locality can not be exploited across the procedure boundary. Also, the inlining is often prohibitive due to both its code expansion and increase in its compilation time and memory requirements. In this paper, we introduce an improved intraprocedural and interprocedural algorithms for detecting references to stale data. The intraprocedural algorithm can mark potential stale references without relying on any cache invalidation or inlining at procedure boundaries, thus avoiding unnecessary cache misses for subroutine local data. The interprocedural algorithm performs bottom-up and top-down analysis on the procedure call graph to further exploit locality across procedure boundaries.

This work is supported in part by the National Science Foundation under Grant No. MIP 89-20891, MIP 93-07910.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. R. Ballance, A. Maccabe, and K. Ottenstein. The Program Dependence Web: a Representation Supporting Control-Data-and Demand-Driven Interpretation of Imperative Languages. Proceedings of the SIGPLAN '90 Conference on Programming Language Design and Implementation, pages 257–271, June 1990.

    Google Scholar 

  2. D. Callahan and K. Kennedy. Analysis of Interprocedural Side Effects in a Parallel Programming Environment. Journal of Parallel and Distributed Computing, 5:517–550, 1988.

    Article  Google Scholar 

  3. Hoichi Cheong. Life Span Strategy — A Compiler-Based Approach to Cache Coherence. Proceedings of the 1992 International Conference on Supercomputing, July 1992.

    Google Scholar 

  4. Hoichi Cheong and Alex Veidenbaum. A Cache Coherence Scheme with Fast Selective Invalidation. Proceedings of The 15th Annual International Symposium on Computer Architecture, page 299, June 1988.

    Google Scholar 

  5. Hoichi Cheong and Alexander V. Veidenbaum. Stale Data Detection and Coherence Enforcement Using Flow Analysis. Proceedings of the 1988 International Conference on Parallel Processing, I, Architecture:138–145, August 1988.

    Google Scholar 

  6. Hoichi Cheong and Alexander V. Veidenbaum. A Version Control Approach To Cache Coherence. Proceedings of 1989 ACM/SIGARCH International Conference on Supercomputing, June 1989.

    Google Scholar 

  7. T. Chiueh. A Generational Approach to Software-Controlled Multiprocessor Cache Coherence. Proceedings 1993 International Conference on Parallel Processing, 1993.

    Google Scholar 

  8. Lynn Choi and Pen-Chung Yew. Eliminating Stale Data References through Array Data-Flow Analysis. CSRD Technical Report No. 1425, April. 1995.

    Google Scholar 

  9. Lynn Choi and Pen-Chung Yew. Interprocedural Array Data-Flow Analysis for Cache Coherence. CSRD Technical Report No. 1427, May. 1995.

    Google Scholar 

  10. Lynn Choi and Pen-Chung Yew. A Compiler-Directed Cache Coherence Scheme with Improved Intertask Locality. Proceedings of the Supercomputing'94, November 1994.

    Google Scholar 

  11. Mary W. Hall. Managing Interprocedural Optimization. Technical report, Rice University, Dept. of Computer Science, April 1991. Ph.D. Thesis.

    Google Scholar 

  12. Paul Havlak. Interprocedural Symbolic Analysis. Technical report, Rice University, Dept. of Computer Science, May 1994. Ph.D. Thesis.

    Google Scholar 

  13. A. Louri and H. Sung. A Compiler Directed Cache Coherence Scheme with Fast and Parallel Explicit Invalidation. Proceedings of the 1992 International Conference on Parallel Processing, I, Architecture:I-2–I-9, August 1992.

    Google Scholar 

  14. S. L. Min and J.-L. Baer. A Timestamp-based Cache Coherence Scheme. 1989 International Conference on Parallel Processing, I:23–32, 1989.

    Google Scholar 

  15. D. A. Padua, R. Eigenmann, J. Hoeflinger, P. Peterson, P. Tu, S. Weatherford, and K. Faign. Polaris: A New-Generation Parallelizing Compiler for MPPs. In CSRD Rept. No. 1306. Univ. of Illinois at Urbana-Champaign., June, 1993.

    Google Scholar 

  16. P. Tu and D. Padua. Gated SSA Based Demand-Driven Symbolic Analysis. CSRD Technical Report No. 1336, Feb. 1994.

    Google Scholar 

  17. A. V. Veidenbaum. A Compiler-Assisted Cache Coherence Solution for Multiprocessors. Proceedings of the 1986 International Conference on Parallel Processing, pages 1029–1035, August 1986.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Center for Supercomputing Research and Development, University of Illinois, 61801-1351, Urbana, IL, USA

    Lynn Choi

  2. Department of Computer Science, University of Minnesota, 55455-0519, Minneapolis, MN, USA

    Pen -Chung Yew

Authors
  1. Lynn Choi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Pen -Chung Yew
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Chua-Huang Huang Ponnuswamy Sadayappan Utpal Banerjee David Gelernter Alex Nicolau David Padua

Rights and permissions

Reprints and permissions

Copyright information

© 1996 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Choi, L., Yew, P.C. (1996). Interprocedural array data-flow analysis for cache coherence. In: Huang, CH., Sadayappan, P., Banerjee, U., Gelernter, D., Nicolau, A., Padua, D. (eds) Languages and Compilers for Parallel Computing. LCPC 1995. Lecture Notes in Computer Science, vol 1033. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0014193

Download citation

  • DOI: https://doi.org/10.1007/BFb0014193

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-60765-6

  • Online ISBN: 978-3-540-49446-1

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation