The goal of this project is to exploit a novel idea for obtaining speedup on vector and concurrent multiprocessors. Most, if not all, studies in parallelism focus on maximizing parallelism within a program or algorithm. It is well known that many programs/algorithms do not exhibit good characteristics of parallelism (e.g. Monte Carlo and general simulations, numerical computations that proceed iteratively, already existing poorly vectorized code, payroll programs, optimization algorithms, etc.) Clearly, one cannot squeeze any more parallelism from within a program if the program does not yield itself to this, and one cannot take already existing code and vectorize it if the code does not vectorize well (unless much time and money is spent in redesigning and rewriting code). Consider, for example, expensive oil-exploration simulations that run for several hours on a single data set. Simulation programs, being event based in nature, simply do not exhibit good characteristics of parallelism. Suppose that one has a program that does not vectorize well (such as the examples given above). Since it is very often the case that the same program has to be executed several times, each time on different data, why not create a Unified version of the program that executes on all the data, so that a single run of the unified program will achieve what a number of serial runs on different data achieves? The advantage is that on vector concurrent multiprocessors, such unified programs (1) yield speedup even though the original program does not, and (2) increase machine utilization more efficiently by exploiting the vector functional units heavily. A simple tool is made to transform the original program into an N-component vector version. Since the different data sets have different effects on program behavior, issues such as path divergence of programs affect speedup. Encouraging results from pilot studies suggest that path divergence can be dealt with through the use of a smart scheduler. The final tool will consist of a transform algorithm, a scheduler, and a decision support system that informs a user how to use the tool for a given program. The support system will use the program graph and machine characteristics to make its decisions.
