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.