Reconstructing sequential behavior from parallel behavior projections (Q1065542)

This paper investigates the problem of merging together the output of so- called data-flow slices. A sequential program may be transformed into slices - separately executable programs, results of which, taken together, are the same as results of the original sequential program. In an earlier paper the author suggested program slicing as another, different to vectorization, method of distribution of sequential computation onto parallel processors. A slice is a program created from the original program by removing certain statements. The removed statements are found in other slices of the same program. In the present paper the author discusses the question of slicing, i.e. sequencing the output of slices executed in parallel, to appear as produced by the original program. All the reasoning is given in terms of so-called Program Regular Expressions (PRE), representing all possible paths through a program. In their terms the author formulates restrictions on slices and, consequently, on the original program as well as on the slicing algorithm, to ensure reconstruction of the program result from its slice outputs. Finally, the author discusses briefly possible costs involved in slicing (more programs to compile, communication between slices, reconstruction of output) and speed-up gained. The latter is illustrated by examples of 3 different compilers which have been sliced and, then, their speed - measured against their sequential versions.