Generating sequential code from parallel code

Abstract

We consider the problem of generating sequential code for parallel programs written in a language which contains a FORALL operator, predicates and statements. This problem can arise when compiling for a multiprocessor where each processor is sequential, and in the vectorization of sequential programs. We present a necessary and sufficient condition for determining if extra guard variables or duplicate code must be inserted when generating a correct sequential program from a given, well-structured parallel program. We also have an efficient method for checking whether this condition occurs in the parallel program. This method gives rise to an algorithm for generating sequential code from parallel code which inserts guard variables (or duplicate code) only when determined by our necessary and sufficient condition. Given the choice to insert duplicate code, an exponential blow-up in size may result. We suggest some simple heuristics to limit such blow-up. We also show that in a restricted case, the minimal size sequential code can be efficiently generated. However, we show that a problem closely related to finding the minimal size sequential code (or equivalently, the minimum number of guards to be inserted) is NP-Complete. We conjecture that this problem in the general case is indeed NP-Complete.