Parallel programming with Polaris

Abstract

As we reach the technological limits of hardware improvement, we must rely on multiple processors to improve programming speed. Parallel programming tools are limited, making effective parallel programming difficult and cumbersome. Compilers that translate conventional sequential programs into parallel form would liberate programmers from the complexities of explicit, machine-oriented parallel programming. Polaris, an experimental translator of conventional Fortran programs that target machines such as the Cray T3D, is the first step toward this goal. The most important techniques implemented in Polaris resulted from a study of the effectiveness of commercial Fortran parallelizers. The authors compiled the Perfect Benchmarks, a collection of conventional Fortran programs representing the typical workload of high-performance computers, for the Alliant FX/80, an eight-processor multiprocessor popular in the late 1980s. For each program, they measured the quality of the parallelization by computing the speedup. With few exceptions, the Alliant Fortran compiler failed to deliver any significant speedup for the majority of the programs. The compiler failed to produce a speedup because it could not parallelize some of the most important loops in the Perfect Benchmarks. The study showed that extending the four most important analysis and transformation techniques traditionally used for vectorization leads to significant increases in speedup. Polaris detected much of the parallelism available in the set of benchmark codes. A careful analysis of the remaining loops that Polaris could parallelize highlights four areas for improvement.