| Abstract |
The SPMD (Single Program - Multiple Data) paradigm supported
by most distributed processing software (a common programming style under
MPI) includes the possibility that different sections of code within the
same program will execute concurrently, as a result of logic depending on
data which is different at each process. This leads to the implicit
formation of subgroups of processes executing common code, but these sets
are not known until runtime since they are data-dependent. We call these
process sets Merging Implicit Process Sets (MIPS).
We describe an analysis of the program CFG (control flow graph) that allows
identification of the points in the program at which the process set changes
either through a group splitting into subgroups or by a merge of subgroups
into a larger group. We show the conditions on the program code which permit
us to prove that these split and merge points can be identified, and derive
an algorithm to do so. We show conditions on communications required to
ensure determinism and freedom from deadlock in an MIPS execution.We
further describe a technique called Overlapping, which intervals
between variable definition and use at sender and receiver are overlapped to
permit a runtime system to dynamically schedule communication while
minimizing waits at either process, or a Shortcutting technique, which can
sometimes be used in conjunction with MIPS to potentially, obtain super
scalar computational speedup.
We present a software library called SOS (Shortcutting, Overlapping and
MIPS), which implements the necessary runtime code
|
