Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Algorithmic skeleton
Summary
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.
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. Second, that algorithmic skeleton programming reduces the number of errors when compared to traditional lower-level parallel programming models (Threads, MPI).
The following example is based on the Java Skandium 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.
// 1. Define the skeleton program
Skeleton sort = new DaC(
new ShouldSplit(threshold, maxTimes),
new SplitList(),
new Sort(),
new MergeList());
// 2. Input parameters
Future 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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.