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