Compiling several classes of irregular applications on multithreaded architectures

Irregular applications pose many compilation difficulties for conventional parallel architectures. Some examples are communication optimization, data partitioning, and work distribution. In this thesis, we address compiling irregular applications for efficient execution on a parallel multithreaded architecture. Multithreaded architectures (MTA's) support multiple threads of control, quick context-switching between them, and dynamic load balancing. This allows MTA's to mask communication latencies and minimize idle time, thus giving them strong potential for achieving high performance on irregular applications.; To effectively use a multithreaded system, it is essential to compile irregular applications; coded in a high-level language, for efficient execution. Our thesis is as follows: Irregular applications, containing both iterative and recursive constructs, can be compiled for efficient execution on multithreaded architectures by employing novel techniques for thread coarsening, work distribution, and application-class specific execution strategies and runtime support. We focus on EARTH-modeled MTA's, which support non-preemptive threads and can be built from off-the-shelf processors.; Some irregular applications exhibit unstructured data accesses and dynamic control flow. Dynamic control flow precludes compile-time detection of iteration spaces. For this class of irregular applications, we have developed optimizations to generate higher granularity threads and perform work distribution on recursive, multithreaded functions.; Other irregular applications exhibit unstructured data accesses and static control flow. Static control flow is amenable to compile-time analysis. We have worked with compute-intensive irregular reductions in non-adaptive and adaptive codes. For this class of irregular applications, we have developed an execution strategy and runtime support to exploit an MTA's ability to mask communication and synchronization latencies. The key aspect of our execution strategy is that the frequency and volume of communication is independent of the contents of the indirection arrays.; Our techniques have been implemented and evaluated in the context of the EARTH-C compiler and several EARTH-modeled systems. The EARTH-C language and compiler have been designed in previous work at McGill University and the University of Delaware. The novel techniques we have developed for thread coarsening, work distribution, and application-class specific execution strategies and runtime support, have resulted in significant performance improvements for irregular applications executing on an MTA.