Patented Automatic Parallelization Technology

Overview: Automatic Parallelization in SequenceL

The SequenceL tools use patented technology to automatically turn SequenceL programs into multi-threaded C++ programs. This is done using a combination of two different language semantics that are the foundation of SequenceL:

  • Normalize-Transpose

  • Consume-Simplify-Produce

SequenceL logo

Normalize-Transpose

Normalize-Transpose is a semantic rule that explains what should occur when a function is passed arguments which are overtyped. An argument is overtyped when it is of greater depth (i.e.- number of dimensions) than what the function was expecting.

Example

The following SequenceL function expects both of its arguments to be scalars:

divides(d(0), n(0)) := true when n mod d = 0 else false;

 

When two scalars are passed to the divides function, divides will either return true or false.

divides(2,4) \\Result: true
divides(3,7) \\Result: false

 

However, if one-dimensional sequences are passed to the divides function, a sequence of Boolean values will be returned.

divides([2,3,5],10) \\Result: [true,false,true]

divides(3,[10,15,20]) \\Result: [false,true,false]

divides([2,3,5],[10,14,20]) \\Result: [true,false,true]

 

Each value in the returned sequence can be calculated at the same time. The SequenceL compiler and runtime will determine how to best split up this work to be executed in the most efficient manner on all of the hardware on a machine, including multiple CPU cores and accelerators.

Definition

The Normalize-Transpose operation is very flexible and can handle any combination of overtyped arguments to a function. Below is an illustration of evaluating an expression using the Normalize-Transpose semantic rule:

illustration of evaluating an expression using the Normalize-Transpose (NT) semantic rule

Normalize-Transpose can be defined mathematically in the following manner:

Let f, xi be identifiers, di be integers and Li be expressions. Given the SequenceL function definition:

and the expression:

If at least one Li is overtyped and all overtyped arguments are of length M, then f(L1, …, Ln) is equal to the list of length M whose kth element is:

 

Where:

In short,

 

SequenceL also has a language feature called “indexed functions”. This is syntactic sugaring for a certain type of Normalize-Transpose operation. The compiler and runtime are also able to efficiently parallelize indexed functions in the same manner as other Normalize-Transpose operations.

Consume Simplify Produce

Consume-Simplify-Produce is a semantic rule that explains how to evaluate expressions in SequenceL. In SequenceL, arguments to a function, and elements in a list are evaluated in an eager manner. SequenceL does not allow for dependencies between these arguments, meaning that they can be evaluated simultaneously. The SequenceL compiler and runtime will determine how to best split up this work to be executed in the most efficient manner on all of the hardware on a machine, including multiple CPU cores and accelerators.

Below is an illustration of evaluating an expression using the Consume-Simplify-Produce semantic rule:

illustration of evaluating an expression using the Consume-Simplify-Produce semantic rule

Additional Reading

Patent US8839212 B2. 16 Sept. 2014.  Cooke, Daniel E., J. Nelson Rushton, and Brad Nemanich. Method, Apparatus and Computer Program Product for Automatically Generating a Computer Program Using Consume, Simplify and Produce Semantics with Normalize, Transpose and Distribute Operations.

Normalize, Transpose, and Distribute: An Automatic Approach for Handling Nonscalars.  Daniel E. Cooke, J. Nelson Rushton, Brad Nemanich, Robert G. Watson, and Per Andersen.
ACM Transactions on Programming Languages and Systems, Vol. 30, No. 2, Article 9, Pub. date: March 2008.

Iterative and Parallel Algorithm Design from High Level Language Traces. Daniel E. Cooke and J. Nelson Rushton. (2005).

Get started now for free!

Download