In signal processing many applications are large-scale algebraic computations and in need of high data throughput, which usually only can be sustained by exploiting parallelism and pipelining in the computations. It goes without saying that parallel implementation must be functionally equivalent to the sequential implementation. However, the derivation of a parallel description from a sequential program often is a difficult and tedious task, as explained in "How do we derive Parallelism".

The MatParser tool automatically converts a specific class of programs, the Nested Loop Programs (NLP), into Single Assignment Programs (SAP). A Single Assignment Program expresses the full data parallelism of the original nested loop program and moreover the program is expressed in the parameters of the original Nested Loop Program. Solving a Parametric Integer Programming (PIP) problem for every data dependency reveals the parallelism available within a NLP. More information about the tools used to do the PIP solving, have a look at the discussion page CASES pages.

The Nested Loop Programs must have static control and their linear expressions must be affine. Static control means that it is known at forehand for each statement how many times it will be invoked irrespective of the processed data. In other words, the NLPs in the set of NLPs that can be converted are deterministic. Their loops are typically expressed in for-loops constructions rather than while-loops constructions, because the latter often depends on the result of a variable (non-static control). Although the expression are confined to be linear, the MatParser Syntax allows nonlinear functions such as MOD, DIV, FLOOR and CEIL and allows step sizes other than one in for-loops.

Example 1, QR algorithm

Example 2, Faddeev algorithm

Example 3, SVD algorithm

Bart Kienhuis
``MatParser: An array dataflow analysis compiler.'',
Technical Report UCB/ERL M00/9.