Many domains in computer science, from data-mining to simulation to computational biology, focus heavily on irregular applications, which deal with complex algorithms that manipulate complex data structures. For example, to analyze large data sets, point correlation - a data mining algorithm - organizes data in a tree-like structure that is then manipulated to extract trends and patterns. As such algorithms become more pervasive, and, more importantly, the data sets they are applied to become much larger, writing high performance irregular applications has become critically important. However, the complexity of irregular algorithms makes writing high-performance applications very difficult: simple expressions of the algorithms do not perform well, and high-performance implementations are difficult to express. An attractive solution is to develop a set of tools that could take a simple expression of an algorithm and automatically transform the program into a higher performing version. This project aims to develop automated, robust and generally-applicable performance-enhancing techniques and transformations for irregular programs.
The chief obstacle to identifying and performing performance-enhancing transformations on irregular programs is the apparent lack of principles that unify irregular applications. However, this research argues that there are, indeed, such principles that can guide the development of transformations. By leveraging high-level structural properties of irregular algorithms, it is possible to automatically transform irregular programs to significantly improve their performance. This project pursues a set of interlocking efforts to build a framework to (i) analyze irregular programs, (ii) identify profitable and legal transformations, (iii) automatically restructure programs according to those transformations, and then (iv) tune the performance of the transformed applications to best fit the target execution platform.
