In computing, algorithmic skeletons, or parallelism patterns, are a high-level parallel programming model for parallel and distributed computing.
Algorithmic skeletons take advantage of common programming patterns to hide the complexity of parallel and distributed applications. Starting from a basic set of patterns (skeletons), more complex patterns can be built by combining the basic ones.
Overview The most outstanding feature of algorithmic skeletons, which differentiates them from other high-level parallel programming models, is that orchestration and synchronization of the parallel activities is implicitly defined by the skeleton patterns. Programmers do not have to specify the synchronizations between the application's sequential parts. This yields two implications. First, as the communication/data access patterns are known in advance, cost models can be applied to schedule skeletons programs.K. Hammond and G. Michelson, editors. "Research Directions in Parallel Functional Programming." Springer-Verlag, London, UK, 1999. Second, that algorithmic skeleton programming reduces the number of errors when compared to traditional lower-level parallel programming models (Threads, MPI).
Example program The following example is based on the Java library for parallel programming.
The objective is to implement an Algorithmic Skeleton-based parallel version of the QuickSort algorithm using the Divide and Conquer pattern. Notice that the high-level approach hides Thread management from the programmer.
import java.util.concurrent.*; import cl.niclabs.skandium.*;
// 1. Define the skeleton program Skeleton<Range, Range> sort = new DaC<>( new ShouldSplit(threshold, maxTimes), new SplitList(), new Sort(), new MergeList() );
// 2. Input parameters Future<Range> future = sort.input(new Range(generate(...)));
// 3. Do something else here. // ...
// 4. Block for the results Range result = future.get();
The first thing is to define a new instance of the skeleton with the functional code that fills the pattern (ShouldSplit, SplitList, Sort, MergeList). The functional code is written by the programmer without parallelism concerns. The second step is the input of data which triggers the computation. In this case Range is a class holding an array and two indexes which allow the representation of a subarray. For every data entered into the framework a new Future object is created. More than one Future can be entered into a skeleton simultaneously. The Future allows for asynchronous computation, as other tasks can be performed while the results are computed. We can retrieve the result of the computation, blocking if necessary (i.e. results not yet available).
The functional codes in this example correspond to four types Condition, Split, Execute, and Merge.
import java.util.concurrent.*;
public class ShouldSplit implements Condition<Range> { private int threshold; private int maxTimes; private int times;
public ShouldSplit(int threshold, int maxTimes) { this.threshold = threshold; this.maxTimes = maxTimes; this.times = 0;
@Override public synchronized boolean condition(Range r) { return (r.right - r.left) > threshold && times++ < maxTimes;
The ShouldSplit class implements the Condition interface. The function receives an input, Range r in this case, and returning true or false. In the context of the Divide and Conquer where this function will be used, this will decide whether a sub-array should be subdivided again or not.
The SplitList class implements the split interface, which in this case divides an (sub-)array into smaller sub-arrays. The class uses a helper function partition(...) which implements the well-known QuickSort pivot and swap scheme.
import java.util.concurrent.*;
public class SplitList implements Split<Range, Range> { @Override public Range[] split(Range r) { int i = partition(r.array, r.left, r.right);
Range[] intervals = { new Range(r.array, r.left, i - 1), new Range(r.array, i + 1, r.right)
return intervals;
The Sort class implements and Execute interface, and is in charge of sorting the sub-array specified by Range r. In this case we simply invoke Java's default (Arrays.sort) method for the given sub-array.
import java.util.Arrays; import java.util.concurrent.*;
public class Sort implements Execute<Range, Range> { @Override public Range execute(Range r) { if (r.right <= r.left) { return r;
Arrays.sort(r.array, r.left, r.right + 1); return r;
Finally, once a set of sub-arrays are sorted we merge the sub-array parts into a bigger array with the MergeList class which implements a Merge interface.
import java.util.concurrent.*;
public class MergeList implements Merge<Range, Range> { @Override public Range merge(Range[] r) { return new Range(r.array, r.left, r.right);
Frameworks and libraries
ASSIST ASSISTM. Aldinucci, M. Coppola, M. Danelutto, N. Tonellotto, M. Vanneschi, and C. Zoccolo. "High level grid programming with ASSIST." Computational Methods in Science and Technology, 12(1):21–32, 2006. is a programming environment which provides programmers with a structured coordination language. The coordination language can express parallel programs as an arbitrary graph of software modules. The module graph describes how a set of modules interact with each other using a set of typed data streams. The modules can be sequential or parallel. Sequential modules can be written in C, C++, or Fortran; and parallel modules are programmed with a special ASSIST parallel module (parmod).
AdHoc,M. Aldinucci and M. Torquati. Accelerating apache farms through ad hoc distributed scalable object repository. In Proc. of 10th Intl. Euro-Par 2004 Parallel Processing, volume 3149 of LNCS, pages 596–605. Springer, 2004. a hierarchical and fault-tolerant Distributed Shared Memory (DSM) system is used to interconnect streams of data between processing elements by providing a repository with: get/put/remove/execute operations. Research around AdHoc has focused on transparency, scalability, and fault-tolerance of the data repository.
While not a classical skeleton framework, in the sense that no skeletons are provided, ASSIST's generic parmod can be specialized into classical skeletons such as: farm, map, etc. ASSIST also supports autonomic control of parmods, and can be subject to a performance contract by dynamically adapting the number of resources used.
(Correct Object-Oriented Pattern-based Parallel Programming System), is a pattern oriented development environment,'S. MacDonald, J. Anvik, S. Bromling, J. Schaeffer, D. Szafron, and K. Tan.' "From patterns to frameworks to parallel programs." Parallel Comput., 28(12):1663–1683, 2002. which achieves parallelism using threads in Java.
is concerned with the complete development process of a parallel application. Programmers interact through a programming GUI to choose a pattern and its configuration options. Then, programmers fill the hooks required for the pattern, and new code is generated as a framework in Java for the parallel execution of the application. The generated framework uses three levels, in descending order of abstraction: patterns layer, intermediate code layer, and native code layer. Thus, advanced programmers may intervene the generated code at multiple levels to tune the performance of their applications. The generated code is mostly type safe, using the types provided by the programmer which do not require extension of superclass, but fails to be completely type safe such as in the reduce(..., Object reducer) method in the mesh pattern.
The set of patterns supported in corresponds to method-sequence, distributor, mesh, and wavefront. Complex applications can be built by composing frameworks with their object references. Nevertheless, if no pattern is suitable, the graphical tool addresses extensibility by allowing programmers to modify the pattern designs and introduce new patterns into .
Support for distributed memory architectures in was introduced in later.K. Tan, D. Szafron, J. Schaeffer, J. Anvik, and S. MacDonald. "Using generative design patterns to generate parallel code for a distributed memory environment." In PPoPP '03: Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 203–215, New York, NY, USA, 2003. ACM. To use a distributed memory pattern, programmers must change the pattern's memory option from shared to distributed, and generate the new code. From the usage perspective, the distributed memory version of the code requires the management of remote exceptions.
Calcium & Skandium Calcium is greatly inspired by Lithium and Muskel. As such, it provides algorithmic skeleton programming as a Java library. Both task and data parallel skeletons are fully nestable; and are instantiated via parametric skeleton objects, not inheritance.
Calcium supports the execution of skeleton applications on top of the ProActive environment for distributed cluster like infrastructure. Additionally, Calcium has three distinctive features for algorithmic skeleton programming. First, a performance tuning model which helps programmers identify code responsible for performance bugs.D. Caromel and M. Leyton. "Fine tuning algorithmic skeletons." In 13th International Euro-Par Conference: Parallel Processing, volume 4641 of Lecture Notes in Computer Science, pages 72–81. Springer-Verlag, 2007. Second, a type system for nestable skeletons which is proven to guarantee subject reduction properties and is implemented using Java Generics.D. Caromel, L. Henrio, and M. Leyton. "Type safe algorithmic skeletons." In Proceedings of the 16th Euromicro Conference on Parallel, Distributed and Network-based Processing, pages 45–53, Toulouse, France, Feb. 2008. IEEE CS Press. Third, a transparent algorithmic skeleton file access model, which enables skeletons for data intensive applications.D. Caromel and M. Leyton. "A transparent non-invasive file data model for algorithmic skeletons." In 22nd International Parallel and Distributed Processing Symposium (IPDPS), pages 1–8, Miami, USA, March 2008. IEEE Computer Society.
is a complete re-implementation of Calcium for multi-core computing. Programs written on Skandium may take advantage of shared memory to simplify parallel programming.Mario Leyton, Jose M. Piquer. "Skandium: Multi-core Programming with algorithmic skeletons", IEEE Euro-micro PDP 2010.
Eden EdenRita Loogen and Yolanda Ortega-Mallén and Ricardo Peña-Marí. "Parallel Functional Programming in Eden", Journal of Functional Programming, No. 15(2005),3, pages 431–475 is a parallel programming language for distributed memory environments, which extends Haskell. Processes are defined explicitly to achieve parallel programming, while their communications remain implicit. Processes communicate through unidirectional channels, which connect one writer to exactly one reader. Programmers only need to specify which data a processes depends on. Eden's process model provides direct control over process granularity, data distribution and communication topology.
Eden is not a skeleton language in the sense that skeletons are not provided as language constructs. Instead, skeletons are defined on top of Eden's lower-level process abstraction, supporting both task and data parallelism. So, contrary to most other approaches, Eden lets the skeletons be defined in the same language and at the same level, the skeleton instantiation is written: Eden itself. Because Eden is an extension of a functional language, Eden skeletons are higher order functions. Eden introduces the concept of implementation skeleton, which is an architecture independent scheme that describes a parallel implementation of an algorithmic skeleton.
eSkel