Patented Automatic Parallelization Technology
Overview: Automatic Parallelization in SequenceL
The SequenceL tools use patented technology to automatically turn SequenceL programs into multithreaded C++ programs. This is done using a combination of two different language semantics that are the foundation of SequenceL:

NormalizeTranspose

ConsumeSimplifyProduce
NormalizeTranspose
NormalizeTranspose 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 onedimensional 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 NormalizeTranspose 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 NormalizeTranspose semantic rule:
NormalizeTranspose can be defined mathematically in the following manner:
Let f, x_{i} be identifiers, d_{i} be integers and L_{i} be expressions. Given the SequenceL function definition:
and the expression:
If at least one L_{i} is overtyped and all overtyped arguments are of length M, then f(L_{1}, …, L_{n}) is equal to the list of length M whose k^{th} element is:
Where:
In short,
SequenceL also has a language feature called “indexed functions”. This is syntactic sugaring for a certain type of NormalizeTranspose operation. The compiler and runtime are also able to efficiently parallelize indexed functions in the same manner as other NormalizeTranspose operations.
Consume Simplify Produce
ConsumeSimplifyProduce 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 ConsumeSimplifyProduce 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).