| This work is concerned with providing software support for procedural parallelism in parallel execution; specifically with the parallel programming and execution paradigm in which multiple copies of a single program execute concurrently, but in which each specific copy of the program may execute a different sequence of statements and routines than other copies.; We propose a framework for the support of process sets that subdivide and recombine dynamically at runtime. We call this MIPS, which stands for Merging Implicit Process Sets. We extend the concept of communication at global barriers to support communications between subsets of processes at barriers affecting only the communicating group. This, in combination with MIPS, allows us to guarantee a deterministic and deadlock-free execution. MIPS provide a theoretical basis for compiler analysis that is also required by our second innovation, which is a form of overlapping that requires semantic information. We propose the use of a finite-state machine to optimize the communication in the overlapping intervals between variable definition and use at different processes. This has the effect of a synchronization extended over time and allows program execution to tolerate and sometimes hide synchronization and communication costs. Finally we propose support for a short-cutting technique which uses information available in parallel to guide execution, save work, and in some special cases may lead to supra-linear speedup. |
