Parallel Execution of Nested Parallel Expressions

This paper describes an implementation of P L for a massively parallel SIMD machine, the M P MP-1. The system is based on a byte code interpreter which can emulate as many virtual processors on each physical processor as desired (within the limits of memory). The implementation makes it possible to activate more virtual processors once execution has begun and this feature can be used to support nested parallelism. Nested parallelism describes the ability to nest data parallel constructs, a feature of P L , C M L , and N ; however, the outer parallel forms usually have to be sequentialized, with only the innermost forms being executed in parallel. N and a subset of P L have been implemented to fully support nested parallelism by flattening nested structures at compile time. To do this the languages must impose various restrictions on both the data and control structures. There is an overhead associated with the runtime technique described here, but it is very versatile and can execute code in parallel that cannot be “flattened.” Hence this technique can be used to effectively support many of the moredifficultaspects of P L .