Compilation techniques for high-performance applicative computation
D.C. Cann · 1989
The importance of parallel processing in the computational community is increasing. The difficulties of programming parallel processors, however, have thwarted their exploitation. Two approaches are receiving attention as possible solutions: supercompilers for extant languages, and new languages. In the latter area, researchers have produced several applicative languages for parallel processing. In the applicative model, only data dependencies constrain evaluation order, so many operations can execute simultaneously if hardware is available. Unfortunately, preserving applicative semantics has required implementations to copy data when deriving one value from another, and in the presence of large arrays, copy costs can become prohibitively expensive. In addition to copying, applicative programs suffer from the same inefficiencies as their imperative counterparts. This dissertation discusses several compilation techniques for high performance parallel applicative computing, with emphasis on update-in-place. All the algorithms take data flow graphs as input and produce improved data flow graphs as output. We have implemented them for SISAL, an applicative language for parallel numerical computation, with encouraging results. Most programs, including those manipulating two-dimensional arrays, run in-place after optimization. Further they achieve execution times competitive with FORTRAN, C, and Pascal on one processor, and good parallel efficiency when more than one processor contributes to execution. This dissertation shows that applicative programming is a powerful approach to programming parallel computers as long as compilers support at least the optimizations of our SISAL compiler.