Example 2, Faddeev

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

Bart Kienhuis
[PDF]``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.

Faddeev

%parameter N 10 100;

%matlab
disp(u);
%end

for j = 1:1:2*N+2,
  for i = 1:1:2*N+2,
    [A(j,i)] = _ReadMatrix_Zeros_64x64();
  end
end

for l = 1:1:1,
    [x(1)] = _ReadMatrix_X();
end

for k= 1 : 1 : N,
    for j=k+1: 1 :N+1,
        for i=k: 1 :2*N+1,
            if i<=k, 
	        if i>=k, 
		    [phi]=atan(A(j,i),A(i,i));
                    [A(i,i)]=sqrt(A(i,i),A(j,i));
                    [A(j,i)]=init(x(1));
%%		else
%%                    [temp_A(1)]=funcA(A(k,i), phi, A(j,i));
%%                    [A(j,i)]=funcB(A(k,i), phi, A(j,i));
%%                    [A(k,i)]=init(temp_A(1));
                end
            else
                [temp_A(1)]=funcA(A(k,i), phi, A(j,i));
                [A(j,i)]=funcB(A(k,i), phi, A(j,i));
                [A(k,i)]=init(temp_A(1));
            end
        end
    end
end

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

Single Assignment Program

%% SAP Generated for HiPars version 3.0 Compliance 
%parameter N 10 100;

%matlab
disp(u);
%end

for j = 1 : 1 : 2*N+2,
   for i = 1 : 1 : 2*N+2,
      [ out_0 ] = _ReadMatrix_Zeros_64x64(  );
      [ A_1( j, i) ]  = opd( out_0 );

   end
end
for l = 1 : 1 : 1,
   [ out_0 ] = _ReadMatrix_X(  );
   [ x_1( l) ]  = opd( out_0 );

end
for k = 1 : 1 : N,
   for j = k+1 : 1 : N+1,
      for i = k : 1 : 2*N+1,
         if -i+k>= 0, 
            if i-k>= 0, 
               
               
               %% SAP Generated for HiPars version 3.0 Compliance 
               if k-2>= 0, 
                  [ in_0 ] = ipd( A_4( k-1, j, i ) );
               else %% if -k+1 >= 0
                  [ in_0 ] = ipd( A_1( j, i ) );
               end


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


               [ out_0 ] = atan( in_0, in_1 );
               [ phi_1( k, j, i) ]  = opd( out_0 );

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


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


               [ out_0 ] = sqrt( in_0, in_1 );
               [ A_2( k, j, i) ]  = opd( out_0 );

               
               
               %% SAP Generated for HiPars version 3.0 Compliance 
               [ in_0 ] = ipd( x_1( 1 ) );


               [ out_0 ] = init( in_0 );
               [ A_3( k, j, i) ]  = opd( out_0 );

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


            
            
            %% SAP Generated for HiPars version 3.0 Compliance 
            [ in_1 ] = ipd( phi_1( k, j, k ) );


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


            [ out_0 ] = funcA( in_0, in_1, in_2 );
            [ temp_A_1( k, j, i) ]  = opd( out_0 );

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


            
            
            %% SAP Generated for HiPars version 3.0 Compliance 
            [ in_1 ] = ipd( phi_1( k, j, k ) );


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


            [ out_0 ] = funcB( in_0, in_1, in_2 );
            [ A_4( k, j, i) ]  = opd( out_0 );

            
            
            %% SAP Generated for HiPars version 3.0 Compliance 
            [ in_0 ] = ipd( temp_A_1( k, j, i ) );


            [ out_0 ] = init( in_0 );
            [ A_5( k, j, i) ]  = opd( out_0 );

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


      [  ] = _WriteMatrix_Rout( in_0 );
   end
end