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) in NP-Complete. We conjecture that this problem in the general case is indeed NP-Complete.

We consider the problem of generating sequential code for programs written in a language which contains a Multiple GOTO operator, predicates and statements. This problem arises when compiling a parallel intermediate form (such as the PDG [3,4]) to run on a sequential machine; in a source-to-source FORTRAN translator when vectorization of a loop has failed; and when compiling logic designs written in a parallel design language for simulation on a sequential machine. It is easy to generate sequential code for this sort of parallel program if one allows either duplication of code or the insertion of guard variables at merge points; in fact, it is in general impossible without this addition. However, for a large class of parallel programs (such as those originally arising from sequential programs, even after some optimizations have been applied) it is possible to generate sequential code without duplication or the addition of guard variables. In this paper we present an efficient algorithm which will generate sequential code from a parallel program without duplication or additional guard variables for a large class of parallel programs.