Research Initiation Award: Network Emulations for Improved Parallel Computation

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

This research concerns theoretical aspects of parallel algorithms and architectures that relate directly to the performance of ``real'' parallel computers. The parallel architectures of interest in this study are multipurpose arrays of identical processing elements. To fully exploit a parallel system, algorithms must be translated into efficient code that can be mapped to a target architecture. The research builds upon earlier work by formulating enhanced versions of mapping problems for these parallel architectures. The particular focus in this proposal is the study of such mapping problems with an eye toward improving the realism of the models, in order to more accurately predict and optimize computational performance. The mapping problems investigated are based on the modeling of computational structures with graphs. The graph-theoretic approach provides fundamental structural information that drives the research program. The framework of graph-embeddings is used to study the problem of programming network emulations. The merit of particular emulation-solutions are quantified in terms of measures of efficiency, including slowdown factors, processor and memory utilization, load balancing, and implementation overhead.