Pattern Recognition Enables Automatic Parallelization of Numerical Codes

We describe the design of the PARAMAT system which will be able to automatically parallelize many numerical application codes without any user interaction, for execution on distributed memory message-passing multiprocessors (e.g. iPSC/860, CM-5, nCUBE-2,...). The key idea is a high-level pattern recognition approach which permits local restoration of program concepts of a wide class of scientific codes by identifying typical programming patterns. This is also applicable to dusty deck codes that may be encrypted by former machine-specific code transformations. The presented pattern recognition tool is fast and robust against many common transformations such as loop distribution, loop interchange, loop blocking and loop unrolling. Successful pattern recognition enables sophisticated code transformations including algorithm replacement. It also guides data alignment and distribution and allows more exact prediction of the performance of the parallelized target code than usually possible