Channels ▼


Parallel Pattern 1: Superscalar Sequences and Task Graphs

Structured Patterns: An Overview

Parallel Pattern 1: Superscalar Sequences and Task Graphs

Parallel Pattern 2: Selection

Parallel Pattern 3: Map

Parallel Pattern 4: Gather

Parallel Pattern 5: Stencil

Parallel Pattern 6: Partition

Parallel Pattern 7: Reduce

Parallel Pattern 8: Scan

Parallel Pattern 9: Pack

Structured patterns as a basis for high-level parallel programming constitute a minimal yet broadly applicable set of components for deterministic parallel programming.

Parallel Pattern 1: Superscalar Sequences and Task Graphs is one that at first glance is serial -- the sequence. However, a sequence of operations in a program, if it can be reordered while respecting data dependencies, can in fact express fairly general forms of task parallelism.

Suppose the following sequence of functions is invoked. Uppercase letters denote variables and lowercase letters denote (pure) functions:

B = f(A)
C = g(B)
E = f(C)
F = h(C)
G = g(E,F)
P = p(B)
Q = q(B)
R = r(G,P,Q)

The data dependencies in this code generate the following graph:

Although the input code is conceptually serial, the data dependencies in the graph potentially allow several operations to execute in parallel, such as p and q and f and h. In fact, the entire subgraph consisting of {g, f, h, g} can also execute in parallel with the subgraph given by {p,q}. If the interface allows the system to clearly identify data dependencies, then a platform can automatically extract any latent parallelism in this pattern.

Note, however, the need for pure, side-effect free functions. In particular, data access needs to be limited to clearly defined inputs and outputs. Certain language features, such as global pointers able to access anything in memory, would create global data dependencies. These need to be avoided in order to make automatic transformation of such sequences into parallel task graphs possible. Also, graphs containing loops are not possible. I will discuss other patterns that can be composed with sequences in later posts to express the concepts of recursion and looping (iteration).

The Superscalar Sequence pattern is related to the idea of "futures". Futures are objects that explicitly represent in-progress asynchronous computations and typically provide the ability to check for completion (with or without blocking). Futures may also provide operations to check completion percentages of computations and to cancel operations in progress. Futures are also occasionally useful for fine-grained control of asynchronous operations, but in general future-like controls can also be built into the data objects of the sequence pattern and only invoked when necessary.

Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags


<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags


<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

