The STAPL pArray

ABSTRACT

The Standard Template Adaptive Parallel Library (STAPL) is a parallel programming framework that extends C++ and STL with support for parallelism. STAPL provides parallel data structures (pContainers) and generic parallel algorithms (pAlgorithms), and a methodology for extending them to provide customized functionality. STAPL pContainers are thread-safe, concurrent objects, i.e., shared objects that provide parallel methods that can be invoked concurrently. They provide views as a generic means to access data that can be passed as input to generic pAlgorithms.

In this work, we present the STAPL pArray, the parallel equivalent of the sequential STL valarray, a fixed-size data structure optimized for storing and accessing data based on one-dimensional indices. We describe the pArray design and show how it can support a variety of underlying data distribution policies currently available in STAPL, such as blocked or blocked cyclic. We provide experimental results showing that pAlgorithms using the pArray scale well to more than 2,000 processors. We also provide results using different data distributions that illustrate that the performance of pAlgorithms and pArray methods is usually sensitive to the underlying data distribution, and moreover, that there is no one data distribution that performs best for all pAlgorithms, processor counts, or machines.

REFERENCES

• 1: E. Allen, D. Chase, V. Luchangco, J.-W. Maessen, S. Ryu, G. L. S. Jr., and S. Tobin-Hochstadt. The fortress language specification version 0.707. Technical report, Sun Labs Programming Language Research Group, http://research.sun.com/projects/plrg/fortress0707.pdf, 2005.
• 2: P. An, A. Jula, S. Rus, S. Saunders, T. Smith, G. Tanase, N. Thomas, N. Amato, and L. Rauchwerger. STAPL: A standard template adaptive parallel C++ library. In Proc. of the International Workshop on Advanced Compiler Technology for High Performance and Embedded Processors (IWACT), Bucharest, Romania, Jul 2001.
• 3: Guy E. Blelloch, Vector models for data-parallel computing, MIT Press, Cambridge, MA, 1990
• 4: Guy E. Blelloch, NESL: A Nested Data-Parallel Language (Version 2.6), Carnegie Mellon University, Pittsburgh, PA, 1993
• 5: D. Callahan, Chamberlain, B. L., and H. Zima. The cascade high productivity language. In The Ninth International Workshop on High-Level Parallel Programming Models and Supportive Environments, volume 26, pages 52--60, April 2004.
• 6: A. Chan and F. Dehne. CGMgraph/CGMlib: Implementing and testing CGM graph algorithms on PC clusters, 2003.
• 7: Philippe Charles , Christian Grothoff , Vijay Saraswat , Christopher Donawa , Allan Kielstra , Kemal Ebcioglu , Christoph von Praun , Vivek Sarkar, X10: an object-oriented approach to non-uniform cluster computing, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 8: Douglas Gregor , Andrew Lumsdaine, Lifting sequential graph algorithms for distributed-memory parallel computation, ACM SIGPLAN Notices, v.40 n.10, October 2005
• 9: Intel. Intel. Reference for Intel Threading Building Blocks, version 1.0, April 2006.
• 10: Elizabeth L. Johnson , Dennis Gannon, Support for parallel generic programming, Indiana University, Indianapolis, IN, 1998
• 11: Elizabeth Johnson , Dennis Gannon, HPC++: experiments with the parallel standard template library, Proceedings of the 11th international conference on Supercomputing, p.124-131, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263614]
• 12: Laxmikant V. Kale , Sanjeev Krishnan, CHARM++: a portable concurrent object oriented system based on C++, ACM SIGPLAN Notices, v.28 n.10, p.91-108, Oct. 1, 1993
• 13: David B. Loveman, High Performance Fortran, IEEE Parallel & Distributed Technology: Systems & Technology, v.1 n.1, p.25-42, February 1993 [doi>10.1109/88.219857]
• 14: David R. Musser , Gilmer J. Derge , Atul Saini, STL tutorial and reference guide, second edition: C++ programming with the standard template library, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 15: J. V. W. Reynders, P. J. Hinker, J. C. Cummings, S. R. Atlas, S. Banerjee, W. F. Humphrey, S. R. Karmesin, K. Keahey, M. Srikant, and M. D. Tholburn. POOMA: A Framework for Scientific Simulations of Paralllel Architectures. In G. V. Wilson and P. Lu, editors, Parallel Programming in C++, chapter 14, pages 547--588. MIT Press, 1996.
• 16: H. Richardson. High performance fortran: history, overview and current developments. Technical Report TMC-261, Thinking Machines Corporation, April 1996.
• 17: Steven Saunders , Lawrence Rauchwerger, ARMI: an adaptive, platform independent communication library, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 18: G. Tanase, C. Raman, M. Bianco, N. M. Amato, and L. Rauchwerger. Associative parallel containers in STAPL. In Workshop on Languages and Compilers for Parallel Computing (LCPC), Urbana-Champaign, to appear 2007.
• 19: N. Thomas, S. Saunders, T. Smith, G. Tanase, and L. Rauchwerger. ARMI: A high level communication library for STAPL. Parallel Processing Letters, 16(2):261--280, Jun 2006.
• 20: Nathan Thomas , Gabriel Tanase , Olga Tkachyshyn , Jack Perdue , Nancy M. Amato , Lawrence Rauchwerger, A framework for adaptive algorithm selection in STAPL, 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.1065981]