Example 1, QR

Example 1, QR algorithm

To understand how MatParser works and how to interpret the Single Assignment Programs, have a look at the documentation for MatParser.

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

This paper presents MatParser, which is an array analysis compiler that automatically converts an affine nested loop program into a single assignment program. The nested loop programs may contain non-linear operators like div/mod/floor/ceil and stepsizes other than one. The focus of this article is on the software architecture used in MatParser to resolve the data dependencies. Finding that two variables are dependent on each other and at which iteration, is a very computational intensive procedure. MatParser employs a particular linear programming technique to find the data-dependencies, based on parametric integer programming (PIP) as proposed by Paul Feautrier. To appreciate the implementation of MatParser, we will explain in this paper in enough detail the basics of the linear programming technique used.

QR algorithm

%parameter N 8 16;
%parameter K 100 1000;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%                                                                            %%
%%             For Matlab we can initialize the matrices                      %%
%%                          in the way we want.                               %%
%%                                                                            %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

for j = 1:1:N,
  for i = j:1:N,
    [r(j,i)] = _ReadMatrix_Zeros_64x64();
  end
end
 
for k = 1:1:K,
  for j = 1:1:N,
    [x(k,j)] = _ReadMatrix_U_1000x16();
  end
end

for k = 1:1:K,
  for j = 1:1:N,
    [r(j,j), x(k,j), t ] = Vectorize( r(j,j), x(k,j) );
    for i = j+1:1:N,
       [r(j,i), x(k,i), t] = Rotate( r(j,i), x(k,i), t );
    end
  end
end

for j = 1:1:N,
  for i = j:1:N,
    [ Sink(j,i) ] = _WriteMatrix_Rout( r(j,i) );
  end
end

MatParser will generated the following Single Assignment Program for this program:

Single Assignment Program

%% SAP Generated for HiPars version 3.0 Compliance 
%parameter N 8 16;
%parameter K 100 1000;
for j = 1 : 1 : N,
   for i = j : 1 : N,
      [ out_0 ] = _ReadMatrix_Zeros_64x64(  );
      [ r_1( j, i) ]  = opd( out_0 );
   end
end
for k = 1 : 1 : K,
   for j = 1 : 1 : N,
      [ out_0 ] = _ReadMatrix_U_1000x16(  );
      [ x_1( k, j) ]  = opd( out_0 );
   end
end
for k = 1 : 1 : K,
   for j = 1 : 1 : N,
      
      %% SAP Generated for HiPars version 3.0 Compliance 
      if k-2>= 0, 
         [ in_0 ] = ipd( r_2( k-1, j ) );
      else %% if -k+1 >= 0
         [ in_0 ] = ipd( r_1( j, j ) );
      end

      %% SAP Generated for HiPars version 3.0 Compliance 
      if j-2>= 0, 
         [ in_1 ] = ipd( x_3( k, j-1, j ) );
      else %% if -j+1 >= 0
         [ in_1 ] = ipd( x_1( k, j ) );
      end

      [ out_0, out_1, out_2 ] = Vectorize( in_0, in_1 );
      [ r_2( k, j) ]  = opd( out_0 );
      [ x_2( k, j) ]  = opd( out_1 );
      [ t_1( k, j) ]  = opd( out_2 );

      for i = j+1 : 1 : N,

         %% SAP Generated for HiPars version 3.0 Compliance 
         if k-2>= 0, 
            [ in_0 ] = ipd( r_3( k-1, j, i ) );
         else %% if -k+1 >= 0
            [ in_0 ] = ipd( r_1( j, i ) );
         end         
         
         %% SAP Generated for HiPars version 3.0 Compliance 
         if j-2>= 0, 
            [ in_1 ] = ipd( x_3( k, j-1, i ) );
         else %% if -j+1 >= 0
            [ in_1 ] = ipd( x_1( k, i ) );
         end

         %% SAP Generated for HiPars version 3.0 Compliance 
         if -j+i-2>= 0, 
            [ in_2 ] = ipd( t_2( k, j, i-1 ) );
         else %% if j-i+1 >= 0
            [ in_2 ] = ipd( t_1( k, j ) );
         end

         [ out_0, out_1, out_2 ] = Rotate( in_0, in_1, in_2 );
         [ r_3( k, j, i) ]  = opd( out_0 );
         [ x_3( k, j, i) ]  = opd( out_1 );
         [ t_2( k, j, i) ]  = opd( out_2 );

      end
   end
end
for j = 1 : 1 : N,
   for i = j : 1 : N,
      
      %% SAP Generated for HiPars version 3.0 Compliance 
      if j-i>= 0, 
         [ in_0 ] = ipd( r_2( K, j ) );
      else %% if -j+i-1 >= 0
         [ in_0 ] = ipd( r_3( K, j, i ) );
      end

      [ out_0 ] = _WriteMatrix_Rout( in_0 );
      [ Sink_1( j, i) ]  = opd( out_0 );
   end
end