Compiling Irregular Applications on a Multi-threaded Architecture

人们认为，多线程架构的总体成功有两大挑战：(1)使用现成的组件构建多线程系统；(2)为常见的命令式语言(如C和Fortran)提供有效的编程语言和编译器支持。在特拉华大学，高的研究小组已经成功地用现成的组件制造了一台多线程机器。剩下的挑战是演示命令式语言在此类体系结构中的成功使用。该项目建议调查积极的过程间分析和转换，结合准确的别名分析，是否可以应用于以命令式语言编码的非正规应用程序，以便在多线程系统上进行编译和高效执行。正在开发新的分析、转换和代码生成技术，以检查在多线程系统中使用命令式语言的优点(和缺点)。生成代码的主要挑战是将顺序代码划分为串，以便可以在不需要任何远程存储器引用的情况下执行每个串的代码。在串划分之前，将使用过程间代码移动和循环转换来减少处理器外引用的频率并实现更好的串划分。为这些转换开发新的分析，考虑到多线程体系结构的混叠和成本函数的可能性，是本项目的主要重点之一。此外，由于在这些系统中，在上下文切换期间不重新分配寄存器，因此也在开发新的链间寄存器分配技术。

It is believed that there are two major challenges in the overall success of multi-threaded architectures: (1) Building multi-threaded systems with off-the-shelf components and, (2) Providing effective programming language and compiler support for common imperative languages (like C and Fortran). At the University of Delaware Gao's research group has successfully built a multi-threaded machine from off-the-shelf components. The remaining challenge is to demonstrate successful use of imperative languages for such architectures. This project proposes to investigate whether aggressive interprocedural analysis and transformations, combined with accurate alias analysis, can be applied to irregular applications coded in imperative languages for compilation and efficient execution on multi-threaded systems. Novel analysis, transformation and code generation techniques are being developed to examine the strengths (and weaknesses) of using imperative languages for multi-threaded systems. The major challenge in generating code is partitioning the sequential code into strands, such that the code for each strand can be executed without requiring any remote memory references. Before strand partitioning, interprocedural code motion and loop transformations will be used to reduce the frequency of off-processor references and enable better strand partitioning. Developing new analyses for these transformations, which take into account the possibility of aliasing and the cost functions for multi-threaded architectures is one of the main focus of this project. Also, since registers are not reallocated during a context switch in these systems, new inter-strand register allocation techniques are also being developed.