A Parallelizing Compiler Based on Partial Evaluation

This thesis demonstrates a compiler that uses partial evaluation to achieve outstandingly e cient parallel object code from very high-level source programs. The source programs are ordinary Scheme numerical programs, written abstractly, with no attempt to structure them for parallel execution. The compiler identi es and extracts parallelism completely automatically; nevertheless, it achieves speedups equivalent to or better than the best observed results achieved by previous supercomputer compilers that require manual restructuring of code. This thesis represents one of the rst attempts to capitalize on partial evaluation's ability to expose low-level parallelism. To demonstrate the e ectiveness of this approach, we targeted the compiler for the Supercomputer Toolkit, a parallel machine with eight VLIW processors. Experimental results on integration of the gravitational n-body problem show that the compiler, generating code for 8 processors, achieves a factor of 6.2 speedup over an almost optimal uniprocessor computation, despite the Toolkit's relatively slow interprocessor communication speed. This compares with an average speedup factor of 4.0 on 8 processors obtained at University ofIllinois using manual code restructuring of a suite of benchmarks for the Cray YMP