Donald Bren School of Information and Computer Sciences

In this paper, we present a novel method for parallelizing imperative programs in the presence of dynamic recursive data-structures. At the heart of parallelizing compilers are the dependence-analysis and disambiguation mechanisms. We present a three-pronged approach: (1) we augment an imperative language with easily parallelizable recursive data-structures, (2) we develop tools for disambugation and interference analysis for such structures, and (3) we present three methods for using information from the analysis to parallelize programs. We illustrate these techniques with a concrete example that has been processed by our system.