Algorithmic Support for Parallel Architectures

本研究的主题是利用算法技术来提高并行架构的性能和灵活性。具体的项目涵盖了从传统主题（如任务调度和负载平衡）到不太熟悉的主题（如使用仿真来实现架构灵活性（如可重构性））的范围；从关于各种计算和通信模式的潜力和局限性的基础问题（例如，无缓冲通信的局限性），到更直接适用的算法技术研究，这些算法技术赋予并行架构以硬件上难以提供的昂贵设施（例如，多测量能力）。该计划的动机是三个观察：(1)并行架构中处理器的速度增长速度快于通信子系统的速度；(2)只有当程序员从管理机器的详细物理资源（处理器数量、互连拓扑等）中解放出来时，并行计算的潜力才会实现；(3)技术发展不断创造新的并行计算模式。所有这三种现象都增加了开发增强并行体系结构计算能力的算法的重要性。观察(1)表明，我们现在可以将以前要求硬件实现的速度和伴随成本的软件琐事降级。观察(2)指出对增强并行程序可移植性的算法的需求日益增加。观察(3)表明需要了解并行计算的新兴模式，以便有效地利用它们。

This research is based on the theme of using algorithmic techniques to enhance the performance and flexibility of parallel architectures. Specific projects span a spectrum from traditional topics, such as task scheduling and load balancing, to less familiar ones, such as using emulations to achieve architectural flexibility (e.g., reconfigurability); from foundational questions concerning the potential and the limitations of various modalities of computation and communication (e.g., the limitations of bufferless communication), to more immediately applicable studies of algorithmic techniques that endow a parallel architecture with facilities that would be prohibitively expensive to provide in hardware (e.g., a multigauging capability). The program is motivated by three observations: (1) the speed of processors in parallel architectures increases faster than the speed of the communication subsystem; (2) the potential of parallel computation is realized only when programmers are liberated from having to manage the detailed physical resources (number of processors, interconnection topology, etc.) of their machines; (3) technological developments are continually creating new modalities of parallel computation. All three of these phenomena increase the importance of developing algorithms that enhance the computing power of parallel architectures. Observation (1) suggests that we can now relegate to software chores that previously demanded the speed and concomitant cost of hardware implementation. Observation (2) points out the increasing need for algorithms that enhance the portability of parallel programs. Observation (3) suggests the need to understand emerging modalities of parallel computation, in order to exploit them effectively.