An empirical study of automatic restructuring of nonnumerical programs for parallel processors

Reviewer: Utpal Banerjee

Since nonnumerical programs have more complicated dynamic control and data structures than numerical programs, they are hard to restructure automatically for parallel processing. This paper presents the results of some restructuring experiments on the programs for a set of 15 common nonnumerical problems, using the automatic restructurer, Parafrase, of the University of Illinois. First, simple sequential algorithms are selected, coded in FORTRAN, and restructured by Parafrase. The major obstacles to parallelization (i.e., transformation of a program to run well on a multiprocessor) turn out to be complicated cycles (especially for algorithms containing conditional statements), subscripts of subscripts, etc. The unparallelized loops are classified. The loops in some of these classes are recognized to be automatical- ly parallelizable in theory, while the other classes contain loops that are probably doomed to remain serial forever. Next, for the problems whose sequential programs have shown poor speedups after restructuring, known parallel algorithms are selected, coded sequentially in FORTRAN, and passed through Parafrase. This produces good speedup results in most cases. This is an experimental research paper intended for people working in the parallel processing area; familiarity with the work done by the Illinois group is recommended. It is a useful paper that provides insight into the difficulties of parallelization at a low level. The tables are the best feature; the references are adequate; and the length is just right. The presentation is clear except for the part that deals with the classification of unparallelized loops.