Home research People General Info Seminars Resources Intranet
| Software & Systems | Home | People | Publications | Links
STAPL | Software & Systems | Parasol Laboratory
STAPL: Standard Template Adaptive Parallel Library

Faculty Members
Lawrence Rauchwerger
Nancy Amato
Bjarne Stroustrup
 
Postdocs
Timmie Smith
Nathan Thomas
 
Research Staff
Robert Metzger
 
Graduate Students
Antal A. Buss
Adam Fidel
Justin Frye
Harshvardhan
Sam Jacobs
Ioannis Papadopoulos
Vincent Marsy
Mani Zandifar
 
Undergraduates
Tyler Biehle
Ross Dixon
Austin Taghavi
 
Project Alumni
Francisco Arzu
Nicolas Castet
Tarun Kumar Jain
Steven Saunders
Shishir Sharma
Gabriel Tanase
Xiabing Xu
 
 
Related Projects
SmartApps
Performance Analysis
Scheduling
K42 - STAPL
 
Projects using
STAPL
Particle Transport
Protein Folding
Motion Planning
Seismic Ray Tracing
 
Related Work
TBB
Charm++
Titanium
UPC
PSTL
 
supported by NSF
and the DOE

STAPL (the Standard Template Adaptive Parallel Library) is a framework for developing parallel programs in C++. It is designed to work on both shared and distributed memory parallel computers. Its core is a library of ISO Standard C++ components with interfaces similar to the (sequential) ISO C++ standard library. STAPL includes a run-time system, design rules for extending the provided library code, and optimization tools. Its goal is to allow the user to work at a high level of abstraction and hide many details specific to parallel programming, to allow a high degree of productivity, portability, and performance. To accomplish these goals STAPL identifies three types of users:

  • Users: application developers that build applications using STAPL data structures and algorithms;
  • Developers: domain specific developers that use the lower level concepts of STAPL to build new data structures and algorithms to be provided to users;
  • Specialists: developers of the core STAPL library that provide developers and users with the programming framework for developing data structures, algorithms, and applications. STAPL programming style extends both STL and the Intel Thread Building Blocks library (TBB), the last being inspired by the STAPL project. STAPL programming style is more general than TBB since it provides more algorithms and data structures, a novel mechanism to design algorithms (pRanges), and it is able to run on shared and distributed memory machines.

    Parallel applications using STAPL Adaptive Framework Parallel Algorithms Views pContainers pRanges STAPL Runtime System OpenMP site MPI resources

    Distributed Data Structures (pContainers)

    A pContainer is the parallel equivalent of an STL container. Its data is partitioned and distributed across the machine, but the User is offered a shared object view. The pContainer distribution across the machine can be user specified or automatically selected by STAPL.

    Currently, STAPL provides STL equivalent containers: pVector, pList, pArray, pMap, pSet, pMultiSet, pMultiMap, pHashMap, pMatrix and pGraph.

    Views

    Views are the STAPL equivalent of STL iterators in the sense that they provide a generic mechanism to access the data of the pContainers. Views emphasize processing data ranges over accessing single items. Each View may be partitioned into subviews hierarchically and this allow to adjust the degree of parallelism to the application needs and nested parallelsm. Views provide iterators to the data items to access single pContainer elements. The partition of the data and the iteration order of the elements may be independent from the physical data distribution, thus allowing easier specification of the parallel algorithms.



    Parallel Algorithms (pAlgorithms)

    A pAlgorithm is the parallel equivalent of an STL algorithm. A pAlgorithm is written in terms of Views operations. The hierarchical structure of input Views and the algorithm access pattern decide the degree of parallelism available for computation. A pAlgorithm can modify input views for optimized data access and/or easier algorithm specification.

    Because performance of parallel algorithms is sensitive to system architecture (latency, topology, etc.) and to application data (data type, distribution, density, etc.), STAPL is designed to continually adapt to the system and the data at all levels -- from selecting the most appropriate algorithmic implementation to balancing communication granularity with latency by self-tuning the message aggregation factor, etc.(see Framework for Adaptive Algorithm Selection in STAPL)

    pRange

    STAPL pAlgorithms are specified as a pRange. A pRange is a Task Dependence Graph (TDG), where a Task is defined as a set of subviews representing data and a function defined over those subviews. Data dependencies are specified among Tasks to guarantee correctness of execution.

    To allow an easy specification of a TDG, STAPL provides a library of dependence graphs and the capability of composing TDGs to build larger and more complex computations. The Developer can still build new TDGs directly through enumeration or closed form description of the dependencies when the dependence pattern of the computation doesn't match one of the dependence graphs provided.

    Run-time System and ARMI

    STAPL's run-time system (RTS) provides to the Developer and Specialist the following facilities:

  • Communication primitives, based on Adaptive Remote Method Invocation (ARMI);
  • Executor of pRange's tasks that enforces tasks dependencies;
  • User definable scheduler for the tasks of pRanges;
  • Performance Monitor for adaptiveness and for user feedback. ARMI communication library hides all the details about the underlying platform, by being implemented over the lower level communication facilities, such as MPI, OpenMP, Pthreads, etc. The communication interface supports a well defined consistency model to allow the developers to design algorithms in a uniform and portable way.

    Applications Developed with STAPL

    STAPL is being refined and extended through the concurrent development of domain specific libraries for particle transport computations (computational physics), protein folding simulation (computational biology), and ray tracing (computational geometry). All these applications, like many problems in the physical and life sciences, make heavy use of dynamic linked data structures (e.g., graphs). STAPL provides built-in support for such irregular data structures.

    Particle Transport in PDT   Protein Folding Seismic Ray Tracing

    If you have questions about STAPL, please email stapl-support@tamu.edu


    Publications

    Using Load Balancing to Scalably Parallelize Sampling-Based Motion Planning Algorithms, Adam Fidel, Sam Ade Jacobs, Shishir Sharma, Nancy M. Amato, Lawrence Rauchwerger, In Proc. Int. Par. and Dist. Proc. Symp. (IPDPS), Phoenix, Arizona, USA, May 2014.
    Proceedings(pdf, abstract)

    A Scalable Distributed RRT for Motion Planning, Sam Ade Jacobs, Nicholas Stradford, Cesar Rodriguez, Shawna Thomas, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 5088-5095, Karlsruhe, Germany, May 2013.
    Proceedings(ps, pdf, abstract)

    Load Balancing Techniques for Scalable Parallelization of Sampling-Based Motion Planning Algorithms, Adam Fidel, Sam Ade Jacobs, Shishir Sharma, Lawrence Rauchwerger, Nancy M. Amato, Technical Report, TR13-002 , Parasol Laboratory, Department of Computer Science, Texas A&M University, Mar 2013.
    Technical Report(pdf, abstract)

    The STAPL Parallel Graph Library, Harshvardhan, Adam Fidel, Nancy M. Amato, Lawrence Rauchwerger, In Wkshp. on Lang. and Comp. for Par. Comp. (LCPC), Tokyo, Japan, Sep 2012.
    Proceedings(pdf, abstract)

    A Scalable Method for Parallelizing Sampling-Based Motion Planning Algorithms, Sam Ade Jacobs, Kasra Manavi, Juan Burgos, Jory Denny, Shawna Thomas, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 2529-2536, St. Paul, Minnesota, USA, May 2012.
    Proceedings(ps, pdf, abstract)

    From Days to Seconds: Scalable Parallel Algorithms for Motion Planning, Sam Ade Jacobs, Nancy M. Amato, In ACM Student Research Compet, Conf. on High Performance Computing Networking, Storage and Analysis Companion Proceedings, Seattle, Washington, USA, Nov 2011.
    Proceedings(pdf, abstract)

    The STAPL Parallel Container Framework, Gabriel Tanase, Antal Buss, Adam Fidel, Harshvardhan, Ioannis Papadopoulos, Olga Pearce, Timmie Smith, Nathan Thomas, Xiabing Xu, Nedhal Mourad, Jeremy Vu, Mauro Bianco, Nancy M. Amato, Lawrence Rauchwerger, In Proc. ACM SIGPLAN Symp. Prin. Prac. Par. Prog. (PPOPP), Feb 2011.
    Proceedings(pdf, abstract)

    The STAPL pView, Antal Buss, Adam Fidel, Harshvardhan, Timmie Smith, Gabriel Tanase, Nathan Thomas, Xiabing Xu, Mauro Bianco, Nancy M. Amato, Lawrence Rauchwerger, In Wkshp. on Lang. and Comp. for Par. Comp. (LCPC), Oct 2010. Also, Technical Report, TR10-001, Parasol Laboratory, Department of Computer Science, Texas A&M University, Jul 2010.
    Proceedings(pdf, abstract) Technical Report(pdf, abstract)

    STAPL: Standard Template Adaptive Parallel Library, Antal Buss, Harshvardhan, Ioannis Papadopoulos, Olga Tkachyshyn, Timmie Smith, Gabriel Tanase, Nathan Thomas, Xiabing Xu, Mauro Bianco, Nancy M. Amato, Lawrence Rauchwerger, In Haifa Experimental Systems Conference, Haifa, Israel, May 2010.
    Proceedings(pdf, abstract)

    The STAPL pList, Gabriel Tanase, Xiabing Xu, Antal Buss, Harshvardhan, Ioannis Papadopoulos, Olga Tkachyshyn, Timmie Smith, Nathan Thomas, Mauro Bianco, Nancy M. Amato, Lawrence Rauchwerger, In Wkshp. on Lang. and Comp. for Par. Comp. (LCPC), Newark, Delaware, Oct 2009.
    Proceedings(pdf, abstract)

    Two Memory Allocators that Use Hints to Improve Locality, Alin Jula, Lawrence Rauchwerger, In International Symposium on Memory Management, Trinity College Dublin, Dublin, Ireland, Jun 2009.
    Proceedings(pdf, abstract)

    Design for Interoperability in STAPL : pMatrices and Linear Algebra Algorithms, Antal Buss, Timmie Smith, Gabriel Tanase, Nathan Thomas, Mauro Bianco, Nancy M. Amato, Lawrence Rauchwerger, In Wkshp. on Lang. and Comp. for Par. Comp. (LCPC), Jul 2008.
    Proceedings(pdf, abstract)

    Design for Interoperability in STAPL: pMatrices and Linear Algebra Algorithms, Antal Buss, Timmie Smith, Gabriel Tanase, Nathan Thomas, Mauro Bianco, Nancy M. Amato, Lawrence Rauchwerger, Lecture Notes in Computer Science, 5335/2008:304-315, 2008.
    Journal(pdf, abstract)

    Associative Parallel Containers In STAPL, Gabriel Tanase, Chidambareswaran (Chids) Raman, Mauro Bianco, Nancy M. Amato, Lawrence Rauchwerger, Lecture Notes in Computer Science, 5234/2008:156-171, 2008. Also, In Wkshp. on Lang. and Comp. for Par. Comp. (LCPC), Oct 2007.
    Journal(pdf, abstract) Proceedings(pdf, abstract)

    Design and Use of htalib – A Library for Hierarchically Tiled Arrays, Ganesh Bikshandy, Jia Guo, Christoph von Praun, Gabriel Tanase, Basilio Fraguela, Maria Jesus Garzaran, David Padua, Lawrence Rauchwerger, Lecture Notes in Computer Science, 4382/2007:17-32, 2008. Also, In Wkshp. on Lang. and Comp. for Par. Comp. (LCPC), Nov 2006.
    Journal(pdf, abstract) Proceedings(abstract)

    The STAPL pArray, Gabriel Tanase, Mauro Bianco, Nancy M. Amato, Lawrence Rauchwerger, In Proc. of Workshop MEDEA, pp. 81-88, Brasov, Romania, Sep 2007.
    Proceedings(pdf, abstract)

    ARMI: A High Level Communication Library for STAPL, Nathan Thomas, Steven Saunders, Tim Smith, Gabriel Tanase, Lawrence Rauchwerger, Parallel Processing Letters, 16(2):261-280, Jun 2006.
    Journal(ps, pdf, abstract)

    Parallel Protein Folding with STAPL, Shawna Thomas, Gabriel Tanase, Lucia K. Dale, Jose M. Moreira, Lawrence Rauchwerger, Nancy M. Amato, Concurrency and Computation: Practice and Experience, 17(14):1643-1656, Dec 2005.
    Journal(ps, pdf, abstract)

    A Framework for Adaptive Algorithm Selection in STAPL, Nathan Thomas, Gabriel Tanase, Olga Tkachyshyn, Jack Perdue, Nancy M. Amato, Lawrence Rauchwerger, In Proc. ACM SIGPLAN Symp. Prin. Prac. Par. Prog. (PPOPP), pp. 277-288, Chicago, Illinois, Jun 2005.
    Proceedings(ps, pdf, abstract)

    Parallel Protein Folding with STAPL, Shawna Thomas, Nancy M. Amato, In Proc. IEEE Int. Wkshp. on High Performance Computational Biology, Santa Fe, NM, Apr 2004.
    Proceedings(ps, pdf, abstract)

    ARMI: An Adaptive, Platform Independent Communication Library, Steven Saunders, Lawrence Rauchwerger, In Proc. ACM SIGPLAN Symp. Prin. Prac. Par. Prog. (PPOPP), pp. 12, San Diego, CA, Jun 2003.
    Proceedings(ps, pdf, abstract)

    STAPL: An Adaptive, Generic Parallel C++ Library, Ping An, Alin Jula, Silvius Rus, Steven Saunders, Tim Smith, Gabriel Tanase, Nathan Thomas, Nancy Amato, Lawrence Rauchwerger, Lecture Notes in Computer Science, 2624/2003:195-210, 2003. Also, In Wkshp. on Lang. and Comp. for Par. Comp. (LCPC), pp. 193-208, Cumberland Falls, Kentucky, Aug 2001.
    Journal(pdf, abstract) Proceedings(ps, pdf, abstract)

    Object Oriented Abstractions for Communication in Parallel Programs, Steven Saunders, Masters Thesis, Parasol Laboratory, Department of Computer Science, Texas A&M University, College Station, TX, May 2003.
    Masters Thesis(ps, pdf, abstract)

    A parallel communication infrastructure for STAPL, Steven Saunders, Lawrence Rauchwerger, In Wkshp. on Perf. Opt. for High-Level Lang. and Lib. (POHLL), New York, NY, Jun 2002.
    Proceedings(ps, pdf, ppt, abstract)

    Adaptive Parallel Sorting in the STAPL library, Steven Saunders, Nathan Thomas, Nancy Amato, Lawrence Rauchwerger, Technical Report, TR01-005, Department of Computer Science and Engineering, Texas A&M University, Nov 2001.
    Technical Report(abstract)

    STAPL: A Standard Template Adaptive Parallel C++ Library, Ping An, Alin Jula, Silvius Rus, Steven Saunders, Tim Smith, Gabriel Tanase, Nathan Thomas, Nancy Amato, Lawrence Rauchwerger, In Int. Wkshp on Adv. Compiler Technology for High Perf. and Embedded Processors, pp. 10, Bucharest, Romania, Jul 2001.
    Proceedings(ps, pdf, abstract)

    Standard Templates Adaptive Parallel Library (STAPL), Lawrence Rauchwerger, Francisco Arzu, K Ouchi, In Wkshp. on Lang. Comp. and Run-time Sys. for Scal. Comp. (LCR)., pp. 402-410, LNCS 1511. Pittsburgh, PA, May 1998.
    Proceedings(ps, pdf, abstract)


  • Parasol Home | Research | People | General info | Seminars | Resources  

    Parasol Lab, 301 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 77843-3112 
    Contact Webmaster      Phone 979.458.0722     Fax 979.458.0718 

    Department of Computer Science and Engineering | Dwight Look College of Engineering Dwight Look College of Engineering | Texas A&M University
        
    Privacy statement: Computer Science and Engineering Engineering TAMU
    Web Accessibility Policy and Law - Web Accessibility and Usability Standards