|
This page has been moved. If you are not redirected within 3 seconds, click here to go to the STAPL homepage.
Visit gitlab
to download STAPL and get started with the library.
The
STAPL Graph Library (SGL)
source code and tutorial is also available on gitlab.
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.
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.
The
STAPL Graph Library (SGL)
is a distributed-memory high-performance parallel graph processing framework written in C++ using STAPL.
In addition to a graph data structure, SGL includes a collection of efficient parallel graph algorithms.
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.
If you have questions about STAPL, please email stapl-support@tamu.edu
Publications
Bounded Asynchrony and Nested Parallelism for Scalable Graph Processing, Adam Fidel, Nancy M. Amato, Lawrence Rauchwerger, In Proc. Supercomputing (SC), Doctoral Showcase Poster, Nov 2017. Proceedings(pdf, abstract)
Fast Approximate Distance Queries in Unweighted Graphs using Bounded Asynchrony, Adam Fidel, Francisco Coral, Colton Riedel, Nancy M. Amato, Lawrence Rauchwerger, In Wkshp. on Lang. and Comp.
for Par. Comp. (LCPC), Sep 2016. Proceedings(pdf, abstract)
An Algorithmic Approach to Communication Reduction in Parallel Graph Algorithms (Conference Best Paper Finalist), Harshvardhan, Adam Fidel, Nancy M. Amato, Lawrence Rauchwerger, In Proc. IEEE Int.Conf. on Parallel Architectures and Compilation Techniques (PACT), San Francisco, CA, Oct 2015. Proceedings(pdf, abstract)
Asynchronous Nested Parallelism for Dynamic Applications in Distributed Memory, Ioannis Papadopoulos, Nathan Thomas, Adam Fidel, Dielli Hoxha, Nancy M. Amato, Lawrence Rauchwerger, In Wkshp. on Lang. and Comp.
for Par. Comp. (LCPC), pp. 106-121, Chapel Hill, NC, Sep 2015. Proceedings(pdf, abstract)
Composing Algorithmic Skeletons to Express High-Performance Scientific Applications (Conference Best Paper), Mani Zandifar, Mustafa Abdujabbar, Alireza Majidi, David Keyes, Nancy M. Amato, Lawrence Rauchwerger, In Proc. ACM Int. Conf.
Supercomputing (ICS), pp. 415--424, Newport Beach, CA, USA, Jun 2015. Proceedings(pdf, abstract)
STAPL-RTS: An Application Driven Runtime System, Ioannis Papadopoulos, Nathan Thomas, Adam Fidel, Nancy M. Amato, Lawrence Rauchwerger, In Proc. ACM Int. Conf.
Supercomputing (ICS), pp. 425-434 , Newport Beach, CA, USA, Jun 2015. Proceedings(pdf, ppt, abstract)
A Hybrid Approach To Processing Big Data Graphs on Memory-Restricted Systems, Harshvardhan, Brandon West, Adam Fidel, Nancy M. Amato, Lawrence Rauchwerger, In Proc. Int. Par. and Dist.
Proc. Symp. (IPDPS), pp. 799-808, Hyderabad, India, May 2015. Proceedings(pdf, abstract)
A Hierarchical Approach to Reducing Communication in Parallel Graph Algorithms, Harshvardhan, Nancy M. Amato, Lawrence Rauchwerger, In Proc. ACM SIGPLAN Symp.
Prin. Prac. Par. Prog. (PPOPP), pp. 285-286 (Poster), San Francisco, CA, USA, Jan 2015. Proceedings(pdf, abstract)
Efficient, Reachability-based, Parallel Algorithms for Finding Strongly Connected Components, Daniel Tomkins, Timmie Smith, Nancy M. Amato, Lawrence Rauchwerger, Technical Report, TR15-002, Parasol Laboratory, Department of Computer Science, Texas A&M University, College Station, TX 77843-3112, Jan 2015. Technical Report(pdf, abstract)
The STAPL Skeleton Framework, Mani Zandifar, Nathan Thomas, Nancy M. Amato, Lawrence Rauchwerger, In Wkshp. on Lang. and Comp.
for Par. Comp. (LCPC), pp. 176--190, Hillsboro, OR, USA, Sep 2014. Proceedings(pdf, abstract)
KLA: A New Algorithmic Paradigm for Parallel Graph Computations (Conference Best Paper), Harshvardhan, Adam Fidel, Nancy M. Amato, Lawrence Rauchwerger, In Proc. IEEE Int.Conf. on Parallel Architectures and Compilation Techniques (PACT), pp. 27-38, Edmonton, AB, Canada, Aug 2014. Proceedings(pdf, abstract)
From Petascale to the Pocket: Adaptively Scaling Parallel Programs for Mobile SoCs, Adam Fidel, Nancy M. Amato, Lawrence Rauchwerger, In Proc. IEEE Int.Conf. on Parallel Architectures and Compilation Techniques (PACT), SRC Poster, Aug 2014. Proceedings(pdf)
Processing Big Data Graphs on Memory-Restricted Systems, Harshvardhan, Nancy M. Amato, Lawrence Rauchwerger, In Proc. IEEE Int.Conf. on Parallel Architectures and Compilation Techniques (PACT), pp. 517-518 (SRC Poster), Edmonton, AB, Canada, Aug 2014. Proceedings(pdf, abstract)
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 Framework for Parallelizing Sampling-Based Motion Planning Algorithms, Sam Ade Jacobs, Ph.D. Thesis, Department of Computer Science and Engineering, Texas A&M University, May 2014. Ph.D. Thesis(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)
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. Journal(pdf, abstract)
Associative Parallel Containers In STAPL, Gabriel Tanase, Chidambareswaran (Chids) Raman, Mauro Bianco, Nancy M. Amato, Lawrence Rauchwerger, In Wkshp. on Lang. and Comp.
for Par. Comp. (LCPC), Oct 2007. Proceedings(pdf, 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)
|