Dynamic language parallelization
Lorenz Huelsbergen · Minds at UW (University of Wisconsin) · 1993
Dynamic language parallelization is a new method, for the automatic parallelization of imperative programs, that finds parallelism during program execution. Dynamic parallelization uncovers more parallelism--and better selects useful parallelism--than is statically possible at compile time. It requires only inexpensive compile-time analyses, allows separate compilation, and admits interactive programming environments. This thesis describes the design and implementation of the first dynamic parallelization techniques for imperative higher-order languages such as ML, Scheme, and Lisp. Prototype implementations, in an optimizing ML compiler on a shared-memory parallel computer, confirm the thesis that dynamic language parallelization is feasible, inexpensive, and often effective. The dynamic techniques address parallelization in the presence of four language attributes that inhibit static parallelization: imperative higher-order functions, side effects to dynamic structures, expressions with variable amounts of computation, and automatic storage reclamation. $\lambda$-Tagging dynamically propagates information about a function's side effects with the function's physical run-time representation. A $\lambda$-tagging compiler can insert checks to $\lambda$-tags that select parallel evaluation only when $\lambda$-tag side-effect information indicates that parallel evaluation is safe. Dynamic resolution determines at run time when updates to a dynamic data structure may safely occur in parallel. It dynamically detects shared data, and correctly coordinates access to this data at run time. Dynamic resolution can automatically parallelize some non-trivial functions that elude static parallelization (e.g., a destructive list-based sort). Dynamic granularity estimation maintains size approximations on dynamic data structures (e.g., lists) at run time. Dynamically, the program consults these approximations to decide when parallel evaluation of an expression will always speed the program's execution. A compiler can statically identify expressions whose evaluation cost always depends on structure sizes, and can insert checks to data sizes that select parallel evaluation when beneficial. A concurrent garbage collector reclaims a program's spent storage in parallel with the program's computation proper. The thesis describes the design and implementation of the first concurrent copying collector that does not require special hardware or operating systems support. The collector relies on the language or compiler to identify all program accesses to mutable data. Measurements of the collector's implementation indicate that it removes all perceptible garbage-collection pauses from a program's execution.