Scaling irregular parallel codes with minimal programming effort

ABSTRACT

The long foreseen goal of parallel programming models is to scale parallel code without significant programming effort. Irregular parallel applications are a particularly challenging application domain for parallel programming models, since they require domain specific data distribution and load balancing algorithms. From a performance perspective, shared-memory models still fall short of scaling as well as message-passing models in irregular applications, although they require less coding effort. We present a simple runtime methodology for scaling irregular applications parallelized with the standard OpenMP interface. We claim that our parallelization methodology requires the minimum amount of effort from the programmer and prove experimentally that it is able to scale two highly irregular codes as well as MPI, with an order of magnitude less programming effort. This is probably the first time such a result is obtained from OpenMP, more so, by keeping the OpenMP API intact.

REFERENCES

• 1: Siegfried Benkner , Piyush Mehrotra , John Van Rosendale , Hans Zima, High-level management of communication schedules in HPF-like languages, Proceedings of the 12th international conference on Supercomputing, p.109-116, July 1998, Melbourne, Australia [doi>10.1145/277830.277855]
• 2: HPF+ Project Consortium. HPF+: Optimizing HPF for Advanced Applications. Deliverable 1.2c, Final Evaluation Report. http://www.par.univie.ac.at/project/hpf+, April 1998.
• 3: M. Hall and M. Martonosi. Adaptive Parallelism in Compiler-Parallelized Code. In Proc. of the Second SUIF Compiler Workshop, Stanford, California, August 1997.
• 4: D. S. Henty, Performance of hybrid message-passing and shared-memory parallelism for discrete element modeling, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.10-es, November 04-10, 2000, Dallas, Texas, United States
• 5: Jay Hoeflinger , Prasad Alavilli , Thomas Jackson , Bob Kuhn, Producing scalable performance with OpenMP: experiments with two CFD applications, Parallel Computing, v.27 n.4, p.391-413, March 1, 2001 [doi>10.1016/S0167-8191(00)00071-5]
• 6: Y. Charlie Hu , Alan Cox , Willy Zwaenepoel, Improving fine-grained irregular shared-memory benchmarks by data reordering, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.33-es, November 04-10, 2000, Dallas, Texas, United States
• 7: Sotiris Ioannidis , Sandhya Dwarkadas, Compiler and Run-Time Support for Adaptive Load Balancing in Software Distributed Shared Memory Systems, Selected Papers from the 4th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, p.107-122, May 28-30, 1998
• 8: Ayal Itzkovitz , Assaf Schuster , Lea Shalev, Thread migration and its applications in distributed shared memory systems, Journal of Systems and Software, v.42 n.1, p.71-87, July 1, 1998 [doi>10.1016/S0164-1212(98)00008-9]
• 9: Pete Keleher , Alan L. Cox , Willy Zwaenepoel, Lazy release consistency for software distributed shared memory, Proceedings of the 19th annual international symposium on Computer architecture, p.13-21, May 19-21, 1992, Queensland, Australia
• 10: J. Labarta, E. Ayguadé, J. Oliver, and D. Henty. New OpenMP Directives for Irregular Data Access Loops. In Proc. of the Second European Workshop on OpenMP, Edinburgh, Scotland, September 2000.
• 11: David K. Lowenthal , Gregory R. Andrews, An Adaptive Approach to Data Placement, Proceedings of the 10th International Parallel Processing Symposium, p.349-353, April 15-19, 1996
• 12: John Mellor-Crummey , David Whalley , Ken Kennedy, Improving memory hierarchy performance for irregular applications, Proceedings of the 13th international conference on Supercomputing, p.425-433, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305228]
• 13: Dimitrios S. Nikolopoulos , Eduard Ayguadé , Theodore S. Papatheodorou , Constantine D. Polychronopoulos , Jesús Labarta, The trade-off between implicit and explicit data distribution in shared-memory programming paradigms, Proceedings of the 15th international conference on Supercomputing, p.23-37, June 2001, Sorrento, Italy [doi>10.1145/377792.377801]
• 14: Dimitrios S. Nikolopoulos , Theodore S. Papatheodorou , Constantine D. Polychronopoulos , Jesús Labarta , Eduard Ayguadé, A case for user-level dynamic page migration, Proceedings of the 14th international conference on Supercomputing, p.119-130, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335243]
• 15: Dimitrios S. Nikolopoulos , Theodore S. Papatheodorou , Constantine D. Polychronopoulos , Jesus Labarta , Eduard Ayguade;eacute;, Is data distribution necessary in OpenMP?, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.47-es, November 04-10, 2000, Dallas, Texas, United States
• 16: Leonid Oliker , Rupak Biswas, Parallelization of a dynamic unstructured application using three leading paradigms, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.39-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331571]
• 17: Umit Rencuzogullari , Sandhya Dwardadas, Dynamic adaptation to available resources for parallel computing in an autonomous network of workstations, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.72-81, June 2001, Snowbird, Utah, United States
• 18: D. Baxter , R. Mirchandaney , J. H. Saltz, Run-time parallelization and scheduling of loops, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.303-312, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72967]
• 19: Hongzhang Shan , Jaswinder P. Singh , Leonid Oliker , Rupak Biswas, A comparison of three programming models for adaptive applications on the Origin2000, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.11-es, November 04-10, 2000, Dallas, Texas, United States
• 20: P. White. IFS Documentation: Part VI, Technical and Computational Procedures. Technical Report CY21R4, European Center for Medium-Range Forecasts, February 2000.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Modules and interfaces
      D.2.8 Metrics
          Subjects: Performance measures

General Terms:
Algorithms, Design, Performance