Channels ▼
RSS

Database

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

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<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

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video