ITR: Parallel Random-Access Model (PRAM)-On-Chip

PRAM（并行随机访问模型，或“机器”）算法模型的算法知识库的规模使其成为串行算法理论的重要替代方案。本研究主要解决以下几个具体的开放性问题。通过真正设计一台在程序员看来像PRAM的机器，能够制造出突破性的高端并行计算机吗？几十年来，建造一台比串行计算机快得多的通用并行计算机一直是计算机科学领域的一个主要开放问题。该提案将为整体计算框架的研究和开发提供研究支柱，称为显式多线程（Explicit Multi-Threading， XMT），旨在解决这个长期存在的开放问题。该提案还包括教育推广部分。技术活动包括以下内容：架构研究（包括内存系统和互连网络）、改进XMT编译器分析、增强XMT优化、自动提取XMT的并行性、在XMT上对几个api以及一些现代软件架构的性能进行原型设计。教育拓展部分将涉及开发一门关于XMT的计算机组织课程。

PRAM-On-ChipAbstractThe magnitude of the algorithmic knowledge base that has been developed for the PRAM (Parallel Random-Access Model, or ``Machine'') algorithmic model makes it a serious alternative to the serial algorithmic theory. The following concrete open problem is addressed in this research. Can a breakthrough high-end parallel computer be built, through truly designing a machine that can look to a programmer like a PRAM? Eluding a solution for several decades, the problem of building a general-purpose parallel computer that is significantly faster than its serial counterpart has been a major open problem for computer science since the inception of the field. This proposal will provide the research backbone in the research and development of a holistic computation framework, called Explicit Multi-Threading (XMT) that seeks to resolve this long-standing open problem. The proposal also has an educational outreach component. Technical activities include the following: architecture studies including memory systems and interconnection networks, improving XMT compiler analysis, enhancing XMT optimizations, automatic extraction of parallelism for XMT, prototyping performance of several APIs, as well as some modern software architectures, on XMT. The education outreach component will involve the development of a computer organization course on XMT.