Presidential Young Investigator Award: Theory of Computing Machinery

本研究计划的目标是了解计算硬件的局限性和能力。为这些体系结构发现新的计算体系结构和算法是另一个目标，使用的方法是数学证明。工作的重点是并行计算机的编程问题。这项研究考察了基于胖树（一种新型通用路由网络）的并行超级计算机是如何合理编程的。长期目标是构建一个“元循环求值器”，类似于Lisp解释器或通用图灵机。给定一个并行计算结构的描述和该结构的输入，评估器应该能够自我模拟。实现这一长期目标的短期计划是研究特定的并行算法，特别是集合论和图论算法。一个高效的数据/处理器结构库正在开发中，它可以用作更复杂算法的构建块。该研究还探讨了如何调试并行程序并使其更容易理解。

The goal of this research program is to understand the limitations and capabilities of computing hardware. Discovery of new computing architectures and algorithms for those architectures is another aim, and mathematical proof is the methodology used. The work focuses on the issue of programming parallel computers. This study examines how parallel supercomputers based on fat-trees, a new class of general-purpose routing networks, might reasonably be programmed. The long-term goal is to build a "metacircular evaluator," which is like a Lisp interpreter or a universal Turing machine. Given a description of a parallel computing structure and inputs to the structure, the evaluator should be able to simulate itself. The short-term plan leading toward this long-term goal is to study specific parallel algorithms, particularly set- and graph-theoretic ones. A library of efficient data/processor structures which can be used as building blocks in more complicated algorithms is being developed. The research also investigates how parallel programs might be debugged and more easily understood.