Lecture 15: Compiling for parallelism

A. Lim and M. Lam, “Maximizing Parallelism and Minimizing Synchronization with Affine Transforms”, Symposium on Principles of Programming Languages, January 1997.

Forehead

This is different style of a paper on compilers; it’s more theoretical. Computer science, mostly not, but sometimes is related to natural science as this paper solves the problem.

Problems

  • To maximize parallelism and minimize synchronization of sequential codes with nested loops
  • To provide a framework of combining prior loop transformation techniques

Prior work

loop fission, loop fusion, unimodular transformations (interchange, reversal, skewing), loop scaling, loop reindexing, and statement reordering

loop fission

   code example A) 
   for i=0..N
     statement 1;
     statement 2;

loop fission converts the code example A to the example B as follows 

   code example B)
   for i=0..N
     statement 1;
   for i=0..N
     statement 2;

each statement has different dependent patterns, hence increased parallelism doesn’t increase locality, but redues working set

loop fusion

it’s an opposite method of loop fission loop fusion converts the above example code B to A improve locality; multiple statements share variables, and may be in producer-consumer relationships

unimodular transforms

  • loop interchange (or reorder loops)

to improve locality, it can change the level of parallelism; change granularity of parallelism — either fine grained to coarse grained, or coarse grained to fine grained 

   code example C)
   for i=0…N
     for j=0…N
       for k=0…N
         statement1;

loop interchange converts the code example C to the example D (interchange loop j and look k) 

   code example D)
   for i=0…N
     for k=0…N
       for j=0…N
         statement1;
  • loop reversal

it can change dependency patterns 

   code example E)
   for i=0…N ==> for i=N…0
  • loop skewing

to remove loop carried dependency by shifting index somehow related to “wavefront” parallelism
The following example shows loop carried dependency on iterating over i or j
(axes i and j represent iteration space, dots are computation of each iteration, and arrows shows dependency)

iterating over i’ doesn’t have loop carried dependency by skewing i’=i+1

I missed loop scaling, loop reindexing, and statement reordering

These techniques are what compiler people long have tried to optimize.
This paper combined all these transformations; compiled codes are the results of some combinations of these techniques

Uniqueness

  • formal optimization of maximizing parlellism and minimizing synchronization
  • but, they didn’t optimize “locality” in this work
    • techniques that optimize locality are loop blocking; they could be also integrated with this framework

Why is it important to minimize synchronization?

  • it depends on the platform
    • the cost of synchronization in SIMD machine — nothing
    • SIMD machines are naturally synchronous
    • there are other examples that synchronization cost is almost nothing
  • this work, not just minimize synchronization, but also searched over all degrees of parallelism

Forms of parallelism

  • example1 in the paper; parllelism on l1 iterations
  • a program has k degree of parallelism if O(n^k) units of computation
    • degree of parallelism is not just loop iterations, but the authors, at least conceptually, completely unroll loops, then analyze dependency through “Affine Transforms”

What’s Affine Transform?

X’ = AX+b; where A, X and X’ are matrices and b is a vector
  • this paper uses Affine transforms to represent dependency in all aspects without changing program behavior
  • in other words, it transforms program’s iteration space to other iteration space while preserving dependency and program behavior
  • Then, there are constraints that they optimize Affine transform against
    • optimization is done by linear algorithms

limitations of Affine transform

  • possible affine index representations are — a[i1][i2][i3], a[i1-i2][i3+i1]
    • every array index is an affine transformation of iterator vector
  • examples of non-affine index representations
    • a[i1*i2] ; no multiplication among indices
    • no transcendental functions (e.g., square root) on loop indices
    • a[i1 mod i2]; no modular operation
    • a[ b[i] ]; no indirect indexing
  • another difficulty — conditionals that depend on data values
    • affine transforms can’t deal with conditionals
  • this framework also needs, at some point, a constant number of loop bounds 
   code example E)
   for i=0…N
     for j=0…i

the above code (E) is fine; outer loop is bounded with a constant N and inner loop’s bound is deterministic
but, the following code (F) doesn’t work with this framework 

   code example F)
   for i=0…N
     for j=0…a[i]

inner loop’s bound, a[i], is a dynamic value, which prevents “conceptual” loop unrolling used in this work

three compiler approaches in 90’s

  1. unimodular transformations
  2. affine transformations
  3. polyhedra(a.k.a N dimensional objects)
  • all these approaches have not yet been actually commercialized due to limitations described above
  • also, optimizing Affine or N-dimensional transformations is not easy

evaluation

  • they proved mathematically, but didn’t show actual work, or whether it’s valuable or not
    • but, there’s another paper showing such evaluation it would be good to add the reference to the paper

I remember there was some discussion on optimizing to proxy, not a real system performance; but can’t remember what exactly it was

  • optimizing a certain constraint doesn’t necessarily lead to a true optimal point unless many system parameters are considered
  • they didn’t describe what exactly the target users are; also didn’t show a program language they assume (although it looks like a C language with some restrictions)

others

current research trend — automatic tuning

  • use compiler techniques to tune parameters on a particluar system

analogy to MATLAB

  • we can express algorithms in two ways in MATLAB
  1. pure C like sequential representation
  2. matrix - vector representation
  • MATLAB will run more efficiently with matrix - vector representation
  • affine transform based parallel compiler also will work better with matrix vector style program representation

Finally …

  • This theoretical work does extremely well on small programs, but not on real programs
  • since software costs a lot, changing existing sequential codes to parallel is really important, but painful
  • This work is state-of-the-art automatic parallelism, but still it has many limitations
  • compilers are very close to architecture; building hardware to help where software is not good at
  • so understanding what software can do well and can’t do is really important