Compiler and run-time support for irregular computations

There are many important applications in computational fluid dynamics, circuit simulation and structural analysis that can be more accurately modeled using iterations on unstructured grids. In these problems, regular compiler analysis for Massively Parallel Processors (MPP) with distributed address space fails because the communication can only be determined at run-time. However, in many of these applications the communication pattern repeats for every iteration. Therefore, equivalent optimizations to the regular case can be achieved with a combination of run-time support (RTS) and compiler analysis.Moreover, many real applications have irregular access patterns with certain structure. This structure is needed to improve sequential performance, better exploiting the memory hierarchy. In many cases this structure is reflected in the array subscript expressions in the form of hybrid accesses, that is, affine combinations of array indirection and regular accesses. We will show that when we get advantage of this structure, we can dramatically reduce pre-processing overheads, both in terms of memory and time, and improve communication and single node performance.In order to achieve these goals we need a combination of run-time and compiler support. Unfortunately, existing irregular run-time support cannot get advantage of regularity and therefore, our first requirement was to develop a new run-time support for irregular computations, that we called PILAR (Parallel Irregular Library with Application of Regularity). Our second requirement was to automate the task of exploiting regularity in irregular applications through compiler support. For this task we extended the PARADIGM compiler, developed at the University of Illinois, to handle irregular problems. Experimental results will validate the efficacy of our approach.U of I OnlyETDs are only available to UIUC Users without author permissio