Orchestrating Communication in High-Latency Parallel Environments

计算机体系结构和通信技术的技术进步，加上经济因素，导致了各种具有高消息延迟的并行计算环境的发展。例如，基于网状和分层环的多处理器，以及工作站网络。在过去紧耦合的小直径并行机中，许多确保处理器间高效通信(至少以高概率)的算法技术不再保证在新环境中的效率。本项目致力于开发和分析通信调度算法，以确保：(A)在工作站网络中进行高效的并行计算；(B)在“环形”多处理器(包括弦环、快速环和分层环形网络)中高效地执行动态演变的计算；在环形网络上高效地协调可变长度的通信。分析和实验方法将被用来制作和评估实现这些目标的算法。这个项目有相辅相成的目标：(1)从理论上了解在高延迟并行环境中提高和降低处理器间通信效率的因素，以及(2)开发算法技术，将这种理解转化为被证明有效的通信策略。

Technological advances in computer architecture and communication technology, coupled with economic factors, have led to the development of a variety of parallel computing environments with high message latencies. Examples include mesh- and hierarchical-ring-based multiprocessors, and networks of workstations. Many algorithmic techniques that ensured efficient interprocessor communication (at least with high probability) in the tightly coupled, small- diameter parallel machines of the past no longer guarantee efficiency in the new environments. This project is dedicated to developing and analyzing communication-scheduling algorithms that ensure: (A) efficient parallel computation in networks of workstations; (B) efficient execution of dynamically evolving computations in "ring-like" multiprocessors (including chordal rings, express rings and hierarchical ring networks); efficient orchestration of variable-length communications on ring-like networks. Both analytical and experimental methods will be invoked to craft and evaluate algorithms that achieve these goals. This project has complementary goals: (1) to gain theoretical understanding of factors that enhance --- and detract from --- efficiency of interprocessor communication in high-latency parallel environments, and (2) to develop algorithmic techniques that translate such understanding into provably efficient communication strategies.