Emulations among Processor Arrays: A Theoretical Study

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

The research project combines work on graph embeddings and parallel algorithms to study a variety of emulation problems for processor arrays, i.e., parallel architectures that consist of a communication network having processing elements at each mode. The research focuses on a variey of theoretical problems that relate to the design, programming, and implementation of "real" processor arrays. More specifically, the research problems motivating the research include attempts to: o simplify the programming of a parallel architecture, by allowing the programmer to specify an algorithm for an idealized architecture which is then emulated by an actual architecture; o understand the relative communication power of various interconnection networks, by determining how efficiently arrays based on each of the networks can emulate arrays based on the others, on general computations; o achieve fault tolerance, by having an array that has been crippled by defects emulate a fault-free version of itself. The theoretical results obtained in the course of the proposed research should lend insights into the "real" analogs of the problems studied.