Skip to main content
SpringerLink
Log in

Improving Cache Effectiveness through Array Data Layout Manipulation in SAC

  • Conference paper
  • First Online:
Implementation of Functional Languages (IFL 2000)

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

Included in the following conference series:

Abstract

SAC is a functional array processing language particularly designed with numerical applications in mind. In this field the runtime performance of programs critically depends on the efficient utilization of the memory hierarchy. Cache conflicts due to limited set associativity are one relevant source of inefficiency. This paper describes the realization of an optimization technique which aims at eliminating cache conflicts by adjusting the data layout of arrays to specific access patterns and cache configurations. Its effect on cache utilization and runtime performance is demonstrated by investigations on the PDE1 benchmark.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. D. F. Bacon, S. L. Graham, and O. J. Sharp. Compiler Transformations for High-Performance Computing. ACM Computing Surveys, vol. 26(4), pp. 345–420, 1994.

    Article  Google Scholar 

  2. B. Bershad, D. Lee, T. Romer, and B. Chen. Avoiding Conflict Misses in Large Direct-Mapped Caches. In Proceedings of the 6th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOSVI), San José, California, USA, 1994.

    Google Scholar 

  3. M. Cierniak and W. Li. Unifying Data and Control Transformations for Distributed Shared-Memory Machines. In Proceedings of the ACM SIGPLAN Conference on Programming Design and Implementation (PLDI’95), La Jolla, California, USA, 1995.

    Google Scholar 

  4. S. Coleman and K. McKinley. Tile Size Selection Using Cache Organization and Data Layout. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI’95), La Jolla, California, USA, pp. 279–290, 1995.

    Google Scholar 

  5. D. Gannon, W. Jalby, and K. Gallivan. Strategies for Cache and Local Memory Management by Global Program Transformation. Journal of Parallel and Distributed Computing, vol. 5(5), pp. 587–616, 1988.

    Article  Google Scholar 

  6. S. Ghosh, M. Martonosi, and S. Malik. Cache Miss Equations: A Compiler Framework for Analyzing and Tuning Memory Behavior. ACM Transactions on Programming Languages and Systems, vol. 21(4), pp. 703–746, 1999.

    Article  Google Scholar 

  7. C. Grelck, D. Kreye, and S.-B. Scholz. On Code Generation for Multi-Generator WITH-Loops in SAC. In P. Koopman and C. Clack, editors, Proceedings of the 11th International Workshop on Implementation of Functional Languages (IFL’99), Lochem, The Netherlands, selected papers, Lecture Notes in Computer Science, vol. 1868, pp. 77–94. Springer-Verlag, 2000.

    Google Scholar 

  8. C. Grelck and S.-B. Scholz. HPF vs. SAC — A Case Study. In A. Bode, T. Ludwig, W. Karl, and R. Wismüller, editors, Proceedings of the 6th International Euro-Par Conference on Parallel Processing (Euro-Par’00), Munich, Germany, Lecture Notes in Computer Science, vol. 1900, pp. 620–624. Springer-Verlag, 2000.

    Google Scholar 

  9. J. L. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Approach, Second Edition. Morgan Kaufmann, 1995.

    Google Scholar 

  10. M. S. Lam, E. E. Rothberg, and M. E. Wolf. The Cache Performance of Blocked Algorithms. In Proceedings of the 4th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-IV), Palo Alto, California, USA, pp. 63–74, 1991.

    Google Scholar 

  11. N. Manjikian and T. S. Abdelrahman. Fusion of Loops for Parallelism and Locality. IEEE Transactions on Parallel and Distributed Systems, vol. 8(2), pp. 193–209, 1997.

    Article  Google Scholar 

  12. K. McKinley, S. Carr, and C.-W. Tseng. Improving Data Locality with Loop Transformations. ACM Transactions on Programming Languages and Systems, vol. 18(4), pp. 424–453, 1996.

    Article  Google Scholar 

  13. K. McKinley and O. Temam. A Quantative Analysis of Loop Nest Locality. In Proceedings f the 8th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-VIII), Boston, Massachusetts, USA, 1996.

    Google Scholar 

  14. T. Mowry, M. Lam, and A. Gupta. Design and Evaluation of a Compiler Algorithm for Prefetching. In Proceedings of the 5th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-V), Boston, Massachusetts, USA, pp. 62–73, 1992.

    Google Scholar 

  15. P. R. Panda, H. Nakamura, N. D. Dutt, and A. Nicolau. A Data Alignment Technique for Improving Cache Performance. In Proceedings of the International Conference on Computer Design VLSI in Computers and Processors, Austin, Texas, USA, pp. 587–592. IEEE Computer Society Press, 1997.

    Google Scholar 

  16. G. Rivera and C.-W. Tseng. Data Transformations for Eliminating Conflict Misses. In Proceedings of the ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI’98), Montréal, Canada,ACM SIGPLAN Notices, vol. 33(5), pp. 38–49. ACM Press, 1998.

    Google Scholar 

  17. G. Rivera and C.-W. Tseng. Eliminating Conflict Misses for High Performance Architectures. In Proceedings of the ACM International Conference on Supercomputing (ICS’98), Melbourne, Australia. ACM Press, 1998.

    Google Scholar 

  18. G. Rivera and C.-W. Tseng. A Comparison of Compiler Tiling Algorithms. In Proceedings of the 8th International Conference on Compiler Construction (CC’99), Amsterdam, The Netherlands, Lecture Notes in Computer Science, vol. 1575, pp. 168–182. Springer-Verlag, 1999.

    Google Scholar 

  19. V. Sarkar and R. Thekkath. A General Framework for Iteration-Reordering Loop Transformations. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI’92), San Francisco, California, USA, pp. 175–187, 1992.

    Google Scholar 

  20. S.-B. Scholz. On Defining Application-Specific High-Level Array Operations by Means of Shape-Invariant Programming Facilities. In S. Picchi and M. Micocci, editors, Proceedings of the International Conference on Array Processing Languages (APL’98), Rome, Italy, pp. 40–45. ACM Press, 1998.

    Google Scholar 

  21. S.-B. Scholz. A Case Study: Effects of WITH-Loop Folding on the NAS Benchmark MGin SAC. In K. Hammond, T. Davie, and C. Clack, editors, Proceedings of the 10th International Workshop on Implementation of Functional Languages (IFL’98), London, UK, selected papers, Lecture Notes in Computer Science, vol. 1595, pp. 216–228. Springer-Verlag, 1999.

    Google Scholar 

  22. O. Temam, C. Fricker, and W. Jalby. Cache Interference Phenomena. In Proceedings of the ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, Nashville, Tennessee, USA, pp. 261–271. ACM Press, 1994.

    Google Scholar 

  23. M. E. Wolf and M. S. Lam. A Data Locality Optimizing Algorithm. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI’91), pp. 30–44, 1991.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Applied Mathematics, University of Kiel, 24098, Kiel, Germany

    Clemens Grelck

Authors
  1. Clemens Grelck
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Lehrstuhl für Informatik II, RWTH Aachen, Ahornstr. 55, 52056, Aachen, Germany

    Markus Mohnen

  2. KUN Nijmegen, Toernooiveld 1, 6525, ED Nijmegen, The Netherlands

    Pieter Koopman

Rights and permissions

Reprints and permissions

Copyright information

© 2001 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Grelck, C. (2001). Improving Cache Effectiveness through Array Data Layout Manipulation in SAC. In: Mohnen, M., Koopman, P. (eds) Implementation of Functional Languages. IFL 2000. Lecture Notes in Computer Science, vol 2011. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45361-X_14

Download citation

  • DOI: https://doi.org/10.1007/3-540-45361-X_14

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-41919-8

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

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation