Presidential Young Investigator Award: Theory of Computing Machinery

点击翻译按钮获取中文摘要

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.