Cache-aware partitioning of multi-dimensional iteration spaces

ABSTRACT

The need for high performance per watt has led to development of multi-core systems such as the Intel Core 2 Duo processor and the Intel quad-core Kentsfield processor. Maximal exploitation of the hardware parallelism supported by such systems necessitates the development of concurrent software. This, in part, entails automatic parallelization of programs and efficient mapping of the parallelized program onto the different cores. The latter affects the load balance between the different cores which in turn has a direct impact on performance. In light of the fact that, parallel loops, such as a parallel DO loop in Fortran, account for a large percentage of the total execution time, we focus on the problem of how to efficiently partition the iteration space of (possibly) nested perfect/non-perfect parallel loops. In this regard, one of the key aspects is how to efficiently capture the cache behavior as the cache subsystem is often the main performance bottleneck in multi-core systems. In this paper, we present a novel profile-guided compiler technique for cache-aware scheduling of iteration spaces of such loops. Specifically, we propose a technique for iteration space scheduling which captures the effect of variation in the number of cache misses across the iteration space. Subsequently, we propose a general approach to capture the variation of both the number of cache misses and computation across the iteration space. We demonstrate the efficacy of our approach on a dedicated 4-way Intel® Xeon® based multiprocessor using several kernels from the industry-standard SPEC CPU2000 and CPU2006 benchmarks achieving speedups upto 62.5%.

REFERENCES

• 1: Kunle Olukotun , Lance Hammond, The Future of Microprocessors, Queue, v.3 n.7, September 2005 [doi>10.1145/1095408.1095418]
• 2: Teraflops Research Chip. http://www.intel.com/research/platform/terascale/teraflops.htm.
• 3: Herb Sutter , James Larus, Software and the Concurrency Revolution, Queue, v.3 n.7, September 2005 [doi>10.1145/1095408.1095421]
• 4: S. F. Lundstrom and G. H. Barnes. A controllable MIMD architectures. In Proceedings of the 1980 International Conference on Parallel Processing, pages 19--27, St. Charles, IL, August 1980.
• 5: SPEC CFP2000. http://www.spec.org/cpu2000/CFP2000.
• 6: Mohammad R. Haghighat , Constantine D. Polychronopoulos, Symbolic analysis for parallelizing compilers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.477-518, July 1996 [doi>10.1145/233561.233568]
• 7: R. Sakellariou. On the Quest for Perfect Load Balance in Loop-Based Parallel Computations. PhD thesis, Department of Computer Science, University of Manchester, October 1996.
• 8: C. Polychronopoulos, D. J. Kuck, and D. A. Padua. Execution of parallel loops on parallel processor systems. In Proceedings of the 1986 International Conference on Parallel Processing, pages 519--527, August 1986.
• 9: E. H. D'Hollander, Partitioning and Labeling of Loops by Unimodular Transformations, IEEE Transactions on Parallel and Distributed Systems, v.3 n.4, p.465-476, July 1992 [doi>10.1109/71.149964]
• 10: Arun Kejariwal , Alexandru Nicolau , Hideki Saito , Xinmin Tian , Milind Girkar , Utpal Banerjee , Constantine D. Polychronopoulos, A general approach for partitioning N-dimensional parallel nested loops with conditionals, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148117]
• 11: Arun Kejariwal , Alexandru Nicolau , Utpal Banerjee , Constantine D. Polychronopoulos, A novel approach for partitioning iteration spaces with variable densities, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065962]
• 12: A. Kejariwal, P. D'Alberto, A. Nicolau, and C. D. Polychronopoulos. A geometric approach for partitioning N-dimensional non-rectangular iteration spaces. In Proceedings of the 17th International Workshop on Languages and Compilers for Parallel Computing, pages 102--116, West Lafayette, IN, 2004.
• 13: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 14: Zvika Guz , Idit Keidar , Avinoam Kolodny , Uri Weiser, Nahalal: Cache Organization for Chip Multiprocessors, IEEE Computer Architecture Letters, v.6 n.1, January 2007 [doi>10.1109/L-CA.2007.6]
• 15: Somnath Ghosh , Margaret Martonosi , Sharad Malik, Cache miss equations: an analytical representation of cache misses, Proceedings of the 11th international conference on Supercomputing, p.317-324, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263657]
• 16: John S. Harper , Darren J. Kerbyson , Graham R. Nudd, Analytical Modeling of Set-Associative Cache Behavior, IEEE Transactions on Computers, v.48 n.10, p.1009-1024, October 1999 [doi>10.1109/12.805152]
• 17: Siddhartha Chatterjee , Erin Parker , Philip J. Hanlon , Alvin R. Lebeck, Exact analysis of the cache behavior of nested loops, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.286-297, June 2001, Snowbird, Utah, United States
• 18: B. B. Fraguela , R. Doallo , J. Touriño , E. L. Zapata, A compiler tool to predict memory hierarchy performance of scientific codes, Parallel Computing, v.30 n.2, p.225-248, February 2004 [doi>10.1016/j.parco.2003.09.004]
• 19: C. Polychronopoulos. Loop coalescing: A compiler transformation for parallel machines. In Proceedings of the 1987 International Conference on Parallel Processing, pages 235--242, August 1987.
• 20: SPEC CINT2006. http://www.spec.org/cpu2006/CINT2006.
• 21: SPEC CFP2006. http://www.spec.org/cpu2006/CFP2006.
• 22: Intel® VTune#8482; Performance Analyzer 8.0.1 for Windows. http://www.intel.com/cd/software/products/asmo-na/eng/vtune/219898.htm.
• 23: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 24: OpenMP Specification, version 2.5. http://www.openmp.org/drupal/mp-documents/spec25.pdf.
• 25: Zhiyuan Li, Array privatization for parallel execution of loops, Proceedings of the 6th international conference on Supercomputing, p.313-322, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143426]
• 26: E. W. Weisstein. Abel's impossibility theorem. from mathworld--a wolfram web resource. http://mathworld.wolfram.com/AbelsImpossibilityTheorem.html.
• 27: David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
• 28: M. J. Wolfe. Iteration space tiling for memory hierarchies, December 1987.
• 29: Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada
• 30: M. E. Wolf , M. S. Lam, A Loop Transformation Theory and an Algorithm to Maximize Parallelism, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.452-471, October 1991 [doi>10.1109/71.97902]
• 31: Michael E. Wolf , Dror E. Maydan , Ding-Kai Chen, Combining loop transformations considering caches and scheduling, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.274-286, December 02-04, 1996, Paris, France
• 32: Thomas Ball , James R. Larus, Branch prediction for free, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.300-313, June 21-25, 1993, Albuquerque, New Mexico, United States
• 33: Andreas Krall, Improving semi-static branch prediction by code replication, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.97-106, June 20-24, 1994, Orlando, Florida, United States
• 34: Intel® Compilers for Linux. http://www.intel.com/cd/software/products/asmo-na/eng/compilers/284264.htm.
• 35: D. Kuck, A. H. Sameh, R. Cytron, A. Veidenbaum, C. D. Polychronopoulos, G. Lee, T. McDaniel, B. R. Leasure, C. Beckman, J. R. B Davies, and C. P. Kruskal. The effects of program restructuring, algorithm change and architecture choice on program performance. In Proceedings of the 1984 International Conference on Parallel Processing, pages 129--138, August 1984.
• 36: Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990
• 37: D. Kulkarni , K. G. Kumar , A. Basu , A. Paulraj, Loop partitioning for distributed memory multiprocessors as unimodular transformations, Proceedings of the 5th international conference on Supercomputing, p.206-215, June 17-21, 1991, Cologne, West Germany [doi>10.1145/109025.109079]
• 38: M. O'Boyle and G. A. Hedayat. Program and data transformations for efficient execution on distributed memory architectures. Technical Report UMCS-93-1-6, Department of Computer Science, University of Manchester, 1992.
• 39: J. Sheu and T. Thai. Partitioning and mapping nested for-loops on multiprocessor systems. In Proceedings of the 1991 ACM International Conference on Supercomputing, Cologne, Germany, June 1991.
• 40: Jang-Ping Sheu , Tzung-Shi Chen, Partitioning and mapping of nested loops for linear array multicomputers, The Journal of Supercomputing, v.9 n.1-2, p.183-202, 1995 [doi>10.1007/BF01245404]
• 41: Ioannis Drositis , Giorgos Goumas , Nectarios Koziris , Panayiotis Tsanakas , George Papakonstantinou, Evaluation of Loop Grouping Methods Based on Orthogonal Projection Spaces, Proceedings of the Proceedings of the 2000 International Conference on Parallel Processing, p.469, August 21-24, 2000
• 42: A. Asthana , H. V. Jagadish , J. A. Chandross , D. Lin , S. C. Knauer, An intelligent memory system, ACM SIGARCH Computer Architecture News, v.16 n.4, p.12-20, Sept. 1988 [doi>10.1145/54331.54332]
• 43: J. P. Moskowitz , C. Jousselin, An algebraic memory model, ACM SIGARCH Computer Architecture News, v.17 n.1, p.55-62, March 1989 [doi>10.1145/859580.859581]
• 44: E. Pegg., T. Rowland, and E. W. Weisstein. Cayley graph. from mathworld--a wolfram web resource. http://mathworld.wolfram.com/CayleyGraph.html.
• 45: Jeanne Ferrante , Vivek Sarkar , W. Thrash, On Estimating and Enhancing Cache Effectiveness, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.328-343, August 07-09, 1991
• 46: O. Temam , C. Fricker , W. Jalby, Cache interference phenomena, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.261-271, May 16-20, 1994, Nashville, Tennessee, United States
• 47: Nerina Bermudo , Xavier Vera , Antonio González , Josep Llosa, Optimizing cache miss equations polyhedra, ACM SIGARCH Computer Architecture News, v.28 n.1, p.43-52, March 2000 [doi>10.1145/346023.346042]
• 48: Glenn Ammons , Thomas Ball , James R. Larus, Exploiting hardware performance counters with flow and context sensitive profiling, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.85-96, June 16-18, 1997, Las Vegas, Nevada, United States
• 49: F. Schneider and T. Gross. Using platform-specific performance counters for dynamic compilation. In Proceedings of the 18th International Workshop on Languages and Compilers for Parallel Computing, Hawthorne, NY, October 2005.
• 50: Florian T. Schneider , Mathias Payer , Thomas R. Gross, Online optimizations driven by hardware performance monitoring, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 51: Vivek Sarkar , Barbara Simons, Parallel Program Graphs and their Classification, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.633-655, August 12-14, 1993

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Algorithms, Performance

Keywords:
iteration space, parallel loops, partitioning