In order to remark on how the MatParser tool determines parallelism we present an example to explain the methodology.
Suppose we have the following Nested Loop Program of which we would like to find its parallelism, or equivalently derive its Single Assignment Program.
for i= 1 : 1 : N,
for j= 1 : 1 : M,
[a(i+j)] = funcA(a(i+j));
end
end
The for-loops of this program define a 2-dimensional space, the so-called iteration space. Through the
affine function i+j, specific elements of variable a are accessed. Consider variable a(5). The function 'FuncA' not only will use the variable a(5) but also will create the variable a(5). There is thus a data-dependency between subsequent iterations. The value we read at a certain iteration (i,j) was put there in a previous iteration, (I,J) say. The MatParser tool is capable of finding this relation automatically, even if non-linear functions are involved.
We will try to visualize this dependence relation. In the figure below, we drew the iteration space. In the same figure we also drew the line i+j=5, which indicates all instances at which variable a(5) is accessed, either through writing or through reading.
Suppose, at point (3,2) we read variable a. to find its data-dependencies we must answer the question;
Which iteration instance assigned the value to variable a(5) that is picked up at iteration instance (3,2)?
From the figure, we notice that there are multiple points that might have assigned the particular value. The three candidates are (1,4), (2,3) and (4,1). In order to decide which one was the last instance that actually accessed the point (3,2), we look at the order of the iteration space, the so-called
lexicographical order. The inclusion of this order yields the following figure.
From this picture, we see that iteration point (1,4) assigned the value that is read at iteration (2,3). Iteration (1,4) is the lexicographical maximum with respect to iteration (2,3). The analysis for all iteration points in the iteration space expresses all data-dependencies and determines which index points are liable to execute in parallel. However, it will take too much time to evaluate all dependencies for all points. Instead, we use the notion of
Linear Programming technique for finding the dependencies. This Linear Programming technique can find in a very efficient way the lexicographical maximums for all iterations. The following figure incorporates all found dependencies.
Running MatParser to this example, we arrive at the following Single Assignment Program (SAP) code.
for i=1 : 1 : N,
for j=1 : 1 : M,
if i-2>=0,
if M-j-1>=0,
[ in0 ] = ipd(a_1(i-1,j+1));
else %% if -M+j>=0;
[ in0 ] = ipd(a(i+j));
end
else %% if -i+1>=0;
[ in0 ] = ipd(a(i+j));
end
[ out0 ] = funcA( in0 );
[a_1( i ,j )] = opd(out0);
end end
A visualization of the SAP code is a combination of the previous figures.
Note that the if-statements divide the iteration space into different parts each of that has a part specific, and therefore regular, data-dependency.