How much parallelism is there in irregular applications?

ABSTRACT

Irregular programs are programs organized around pointer-based data structures such as trees and graphs. Recent investigations by the Galois project have shown that many irregular programs have a generalized form of data-parallelism called amorphous data-parallelism. However, in many programs, amorphous data-parallelism cannot be uncovered using static techniques, and its exploitation requires runtime strategies such as optimistic parallel execution. This raises a natural question: how much amorphous data-parallelism actually exists in irregular programs?

In this paper, we describe the design and implementation of a tool called ParaMeter that produces parallelism profiles for irregular programs. Parallelism profiles are an abstract measure of the amount of amorphous data-parallelism at different points in the execution of an algorithm, independent of implementation-dependent details such as the number of cores, cache sizes, load-balancing, etc. ParaMeter can also generate constrained parallelism profiles for a fixed number of cores. We show parallelism profiles for seven irregular applications, and explain how these profiles provide insight into the behavior of these applications.

REFERENCES

• 1: Arvind, David Culler, and Gino Maa. Assessing the benefits of fine-grain parallelism in dataflow programs. International Journal of High-performance Computing Applications, 2(3), 1988.
• 2: Robert D. Blumofe , Christopher F. Joerg , Bradley C. Kuszmaul , Charles E. Leiserson , Keith H. Randall , Yuli Zhou, Cilk: an efficient multithreaded runtime system, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.207-216, July 19-21, 1995, Santa Barbara, California, United States
• 3: Yuri Boykov , Gareth Funka-Lea, Graph Cuts and Efficient N-D Image Segmentation, International Journal of Computer Vision, v.70 n.2, p.109-131, November 2006 [doi>10.1007/s11263-006-7934-5]
• 4: A. Braunstein , M. Mézard , R. Zecchina, Survey propagation: An algorithm for satisfiability, Random Structures & Algorithms, v.27 n.2, p.201-226, September 2005 [doi>10.1002/rsa.v27:2]
• 5: L. Paul Chew, Guaranteed-quality mesh generation for curved surfaces, Proceedings of the ninth annual symposium on Computational geometry, p.274-280, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161150]
• 6: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 7: Edsger Wybe Dijkstra, A Discipline of Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 8: Matteo Frigo , Charles E. Leiserson , Keith H. Randall, The implementation of the Cilk-5 multithreaded language, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.212-223, June 17-19, 1998, Montreal, Quebec, Canada
• 9: Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988 [doi>10.1145/48014.61051]
• 10: Leonidas J. Guibas, Donald E. Knuth, and Micha Sharir. Randomized incremental construction of delaunay and voronoi diagrams. Algorithmica, 7(1):381--413, December 1992.
• 11: Tim Harris , Keir Fraser, Language support for lightweight transactions, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 12: Tim Harris , Satnam Singh, Feedback directed implicit parallelism, Proceedings of the 12th ACM SIGPLAN international conference on Functional programming, October 01-03, 2007, Freiburg, Germany
• 13: L. J. Hendren , A. Nicolau, Parallelizing Programs with Recursive Data Structures, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.35-47, January 1990 [doi>10.1109/71.80123]
• 14: Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States
• 15: Benoît Hudson , Gary L. Miller , Todd Phillips, Sparse parallel Delaunay mesh refinement, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248435]
• 16: Ken Kennedy , John R. Allen, Optimizing compilers for modern architectures: a dependence-based approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 17: Venkata Krishnan , Josep Torrellas, A Chip-Multiprocessor Architecture with Speculative Multithreading, IEEE Transactions on Computers, v.48 n.9, p.866-880, September 1999 [doi>10.1109/12.795218]
• 18: Milind Kulkarni , Patrick Carribault , Keshav Pingali , Ganesh Ramanarayanan , Bruce Walter , Kavita Bala , L. Paul Chew, Scheduling strategies for optimistic parallel execution of irregular programs, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378575]
• 19: Milind Kulkarni , Keshav Pingali , Ganesh Ramanarayanan , Bruce Walter , Kavita Bala , L. Paul Chew, Optimistic parallelism benefits from data partitioning, ACM SIGARCH Computer Architecture News, v.36 n.1, March 2008
• 20: Milind Kulkarni , Keshav Pingali , Bruce Walter , Ganesh Ramanarayanan , Kavita Bala , L. Paul Chew, Optimistic parallelism requires abstractions, ACM SIGPLAN Notices, v.42 n.6, June 2007
• 21: Wei Liu , James Tuck , Luis Ceze , Wonsun Ahn , Karin Strauss , Jose Renau , Josep Torrellas, POSH: a TLS compiler that exploits program structure, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1122997]
• 22: Jayadev Misra, Distributed discrete-event simulation, ACM Computing Surveys (CSUR), v.18 n.1, p.39-65, March 1986 [doi>10.1145/6462.6485]
• 23: L. Rauchwerger Y. Zhan , J. Torrellas, Hardware for Speculative Run-Time Parallelization in Distributed Shared-Memory Multiprocessors, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.162, January 31-February 04, 1998
• 24: Mooly Sagiv , Thomas Reps , Reinhard Wilhelm, Solving shape-analysis problems in languages with destructive updating, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.1, p.1-50, Jan. 1998 [doi>10.1145/271510.271517]
• 25: Pang-Ning Tan , Michael Steinbach , Vipin Kumar, Introduction to Data Mining, (First Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2005
• 26: Kevin B. Theobald , Guang R. Gao , Laurie J. Hendren, On the limits of program parallelism and its smoothability, Proceedings of the 25th annual international symposium on Microarchitecture, p.10-19, December 01-04, 1992, Portland, Oregon, United States
• 27: Christoph von Praun , Rajesh Bordawekar , Calin Cascaval, Modeling optimistic concurrency using quantitative dependence analysis, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345234]
• 28: Bruce Walter, Kavita Bala, Milind Kulkarni, and Keshav Pingali. Fast agglomerative clustering for rendering. In IEEE Symposium on Interactive Ray Tracing (RT), 2008.
• 29: Hongtao Zhong, Mojtaba Mehrara, Steve Lieberman, and Scott Mahlke. Uncovering hidden loop level parallelism in sequential applications. IEEE 14th International Symposium on High Performance Computer Architecture, pages 290--301, Feb. 2008.

INDEX TERMS

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

General Terms:
Algorithms, Languages, Performance

Keywords:
optimistic parallelism, parallelism profiles, profiling