ParaCite: Auto-parallelization of a sequential program using the Program Dependence Graph
Sesha Kalyur, G. S. Nagaraja · 2016
Parallelization is an attractive and popular means of speeding up a given program. Parallelization can be carried out at different levels. Instruction level parallelization exploits parallelism inherent at the level of instructions of the program. In contrast, Task level parallelization targets higher level structures of the program such as statements, blocks and procedures. Loops in a program are an attractive source of potential parallelism. Numerically intensive programs contain many loops rich in hidden parallelism. On the contrary, general purpose programs have plenty of control structures that hinder parallelization. So most of the past work on parallelization has focused on loop dominant programs at the cost of overlooking programs that have plenty of control dependent structures. In this paper, we look at the problem of program parallelization from a holistic perspective. We propose a solution based on the Program Dependence Graph model, that targets both numerical and general purpose programs to deliver the expected parallelism.