CSR-PSCE,SM: Compiler-Directed System Optimization of a Highly-Parallel Fine-Grained Chip Multiprocessor

在多核处理器上加速单程序仍然是计算机系统设计中的一个突出挑战。不幸的是，除了常规的密集矩阵码之外，现有的并行系统在程序上几乎没有获得什么加速比。而且，世界上大多数程序都属于这一类别，广义地称为非常规代码。当然，除了指令级并行性(ILP)之外，一些非规则代码几乎没有并行性；因此，在多核上不可能实现加速。但是，在其他非常规代码中，并行性是存在的，但不可利用。原因包括高同步成本、非循环并行、非数组数据结构、递归表示的并行以及过于细粒度而无法利用的并行。PIS以前的工作提出了基于PRAM的XMT并行体系结构，该体系结构在非规则代码上表现出良好的加速比：在图中的广度优先搜索上加速23倍，在图中寻找生成树方面加速9倍，使用处理器与同类中最好的串行处理器相比。该项目正在为XMT开发新的编译器技术，以在面对可扩展性的体系结构决策时获得可伸缩的性能。它正在研究更好的编译器技术，以实现XMT等UMA架构的可伸缩性能。这些包括使用全局队列而不是工作窃取的更好的任务调度器；针对XMT的独特的存储器层次结构而定制的改进的预取；以及使用每个XMT处理器的本地可扩展的非高速缓存一致的高速暂存存储器来减少对昂贵的远程存储器的需要。该项目的更广泛的影响是(I)开发必要的编译器技术，以将XMT的研究风险降低到行业愿意将该技术商业化的程度；(Ii)为以前难以并行化的应用程序提供可扩展的加速比；(Iii)展示了在大类串行、常规并行和非常规并行程序中实现强劲性能的技术；(Iv)展示了未来通用桌面架构的有力竞争者；以及(V)普及XMT和提高未来劳动力技能的教育和推广计划。

Accelerating single programs on multicore processors remains an outstanding challenge in computer systems design. Unfortunately, existing parallel systems achieve little speedup on programs other than regular dense-matrix codes. And, most of the world's programs are in this category, broadly termed non-regular code. Of course some non-regular codes have little parallelism beyond instruction level parallelism (ILP); hence no speedup is possible on multicores. However in other non-regular code, parallelism is present but is not exploitable. Reasons include high synchronization costs, non-loop parallelism, non-array data structures, recursively expressed parallelism and parallelism that is too fine-grained to be exploitable. Previous work by the PIs presented the PRAM-based XMT parallel architecture which has demonstrated good speedups on non-regular codes: 23X on breadth-first search in graphs and 9X for finding spanning tree in graphs, using 64 processors vs. the best-in-class serial processor.This project is developing new compiler technologies for XMT to achieve scalable performance in the face of architecture decisions made for scalability. It is studying better compiler techniques to achieve scalable performance for UMA architectures such as XMT. These include better task schedulers using global queues rather than work stealing; improved pre-fetching tailored for XMT's unique memory hierarchy; and using scalable non-cache-coherent Scratch-Pad Memory local to each XMT processor to reduce the need to go to expensive remote memory.The broader impacts of this project are (i) the development of compiler technologies necessary to reduce the research risk of XMT to the point where industry is willing to commercialize the technology; (ii) the delivery of scalable speedups for erstwhile hard-to-parallelize applications; (iii) the demonstration of technologies for robust performance across large classes of serial, regular parallel, and non-regular parallel programs; (iv) demonstrating a serious contender for a future universal desktop architecture; and (v) educational and outreach initiatives to popularize XMT and improve the skills of the future workforce.