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

在多核处理器上加速单个程序仍然是计算机系统设计中的一个突出挑战。不幸的是，现有的并行系统在除常规密矩阵代码之外的程序上几乎没有加速。而且，世界上大多数程序都属于这一类，广义上称为非正则代码。当然，一些非正则代码除了指令级并行（ILP）之外几乎没有并行性；因此，在多核上不可能加速。然而，在其他非正则代码中，并行性是存在的，但不能被利用。原因包括高同步成本、非循环并行性、非数组数据结构、递归表达的并行性以及过于细粒度而无法利用的并行性。pi先前的工作提出了基于pram的XMT并行架构，该架构在非正则代码上显示了良好的加速：在图中进行宽度优先搜索的速度为23X，在图中查找生成树的速度为9X，使用64个处理器与同类最佳串行处理器相比。该项目正在为XMT开发新的编译器技术，以便在面对为可伸缩性而制定的体系结构决策时实现可伸缩性性能。它正在研究更好的编译器技术，以实现xml等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.