Compiling Recurrent and Irregular Serial Code for High Performance Computers.

This dissertation uses existing models of control and data dependence and flow as a starting point for investigating one new analysis model. We focus on an important problem in automatically parallelizing serial code recurrent and irregular code. Recurrent and irregular code play an important role in many scientific codes, as well as many sorting, geometric, and symbolic applications. No general techniques existed prior to this dissertation for automatically parallelizing such code. The extent of current techniques to deal with recurrent loops in automatic parallelization is to simply search for familiar patterns of common loops in the source code. This dissertation will demonstrate, through a relatively simple semantic interpretation of loop bodies, the added power of a small amount of higher-level reasoning in an automatically parallelizating compiler.