A Type-Based Approach to Parallelization
No Thumbnail Available
Date
2003-10-01T00:00:00Z
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Parallel functional programming plays an important role in parallel programming [16]. Type system has signi.cant impact on program analysis [23]. In this paper, we show how to automatically and correctly synthesize parallel programs from sequential functional program based on the concept of a type system. Our type system captures the parallelizability of a program, in a modular fashion, by exploring the ring structures of the programs operators. It handles programs de.ned by self-recursive functions with accumulating parameters, as well as a limited form of non-linear mutual-recursive functions. In contrast to the Damas-Milner type system (the typical type system) that is constructed from the evaluation rules of the underlying language, our type system is constructed from a set of meta-rules that are used to transform sequential programs into a special normal form suitable for parallelization. The idea of this paper has been implemented and used to generate parallel code of a form, called mutumorphism, a general parallel computation model. Transforming into such a form is an important step towards constructing e.cient data parallel programs.