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.