Copyright R.A. van Engelen, FSU Department of Computer Science, 2000

# Compiler Projects

• 1: Supported by National Science Foundation: Improving symbolic analysis of restructuring compilers for high-performance computing
• Team members:

• Johnnie Birch
Prof. van Engelen
• 2: Supported by National Science Foundation: Low-level compiler optimizations in VPO and GUI development
• Team members:

• Boacheng Cai
Apan Quasem
Wankang Zhao
Prof. van Engelen
Prof. Whalley
Prof. Yuan

# High-Level Program Restructuring for High-Performance Computing

• Most of the execution time of a program is spend in its loops
• Loop optimizations have the highest impact on speeding up execution
• Loop parallelization by a compiler attempts to parallelize loops to speed up execution

# Loop Parallelization

• Loop parallization requires analysis of data dependencies
• The loop

• for (i=0; i<n; i++)
a[i]=a[i+1]-a[i];
can be parallelized on P processors as follows (assuming that n is a multiple of P):
for (every processor 0<p<P in parallel)
for (i=0; i<n/P; i++)
{ ii=i+(n/P)*p;
tmp[ii]=a[ii+1]-a[ii];
}
/* synchronize all processors */
for (every processor 0<p<P in parallel)
for (i=0; i<n/P; i++)
{ ii=i+(n/P)*p;
a[ii]=tmp[ii];
}
• The loop

• for (i=0; i<n; i++)
a[i]=a[i]-a[i-1];
cannot be parallelized, because the values of array a calculated in previous iterations are used in the current iteration

# Non-Linear Dependence Analysis

• Loop parallelization requires analysis of data dependencies
• Many methods exist for linear data dependence testing
• Array index expressions in loops are often linear
• Example: a[i+1] and [4*i+3] where i is the loop counter variable
• What about more complicated array index expressions?
• Non-linear expressions, e.g. a[i*i-i]
• Symbolic expressions, e.g. a[r*i]
• Non-linear and symbolic expressions appear in
• Scientific applications
• Graphics and visualization software

# Chains of Recurrences

• Chains of recurrences (CR) notation is extremely useful for dependence analysis
• CR rewrite rules can be used to detect non-linear induction variables
• For example, the loop

• for(i=0; i<n; i++)
{ a[i]=a[j];
j=j+i;
}
can be rewritten into:
for(i=0; i<n; i++)
a[i]=a[(i*i-i)/2+j];
and then be parallellized if j>=0 as follows:
for (every processor 0<p<P in parallel)
for(i=0; i<n; i++)
{ ii=i+(n/P)*p;
tmp[ii]=a[(ii*ii-ii)/2+j];
}
/* synchronize all processors */
for (every processor 0<p<P in parallel)
for(i=0; i<n; i++)
{ ii=i+(n/P)*p;
a[ii]=tmp[ii];
}

# Open Student Projects

• Use CRs in program correctness proofs