Automatic parallelization

The presence of ``dusty-deck'' programs in production codes makes automatic parallelization of such programs attractive. Automatic parallelization may also ease the burden of programmers by allowing them to use programming languages and paradigms with which they are more familiar.


Initial efforts were targeted at vector machines.

  1. Discusses the basics of data dependence analysis and loop transformations [PW86].
  2. Vectorization of ``dusty-deck'' Fortran programs [PKL80].
  3. Differentiates between vectorization and vector optimization. Discusses decision mechanisms [Wol88].
  4. Detailed discussion of vectorization and parallelization techniques for Fortran programs [Pol88].
  5. More on vectorization of Fortran programs [AK87].
  6. Still more of the same stuff [Wol89].
  7. Mathematical foundations of dependence analysis [Ban88].


Scheme and other dialects of LISP present a number of difficulties for automatic parallelizers: lists (pointers, non-contiguous storage, no random access), higher-order functions, continuations, closures, and dynamic storage management. Work on such languages is much more recent [HP88, LH88], and the ``dusty-deck'' problem is not as pronounced.

  1. Describes the PARCEL system: vectorized list representation, Fortran-style program transformations [HP88].
  2. Describes the CURARE system: details of dependence analysis for Scheme [LH88].
  3. Harrison's thesis. Lots of semantics and details of optimizations [Har89].
  4. Control flow analysis of Scheme. Not directly concerned with parallelism [Shi88].
  5. Describes the transformation of a PDE solver written in pure Lisp to a vectorizable Fortran program for execution on the CRAY X-MP [BH90]., July 1994