Robust Algorithmic Building Blocks for Parallel Computing

项目概要提案号：NSF 9988304并行计算鲁棒算法构建块PI: Alexander A. shvartsman本研究探讨并行计算鲁棒构建块的算法方法。研究方向是基于这样一种思想，即计算问题的并行解决方案可以被表述为构建块的组合，组件封装了定义良好的计算原语的高效和容错并行实现。构建块配备了其组合性的精确规范，并且通常在比普通并行编程语言提供的操作更高的抽象级别上提供服务。本研究的一个主要目标是提供可证明的高效构建块，帮助复杂并行应用程序的设计人员专注于算法设计，同时将他们从需要永远考虑以某种符号表示的算法到特定目标机器的高效映射问题中解放出来。传统上，分布式计算领域的研究主要集中在容错上，而并行计算的研究主要集中在加速上。本研究综合了这两个重点，并结合构建块方法，产生了一种多处理器计算方法，该方法获得了可扩展的并行加速，同时提供了正确性和组合性保证，并在面对故障时实现了优雅的降级。通过将鲁棒并行计算的研究与构建复杂系统的构建块方法相结合，本工作旨在实质性地推进有效和高效并行计算理论的最新进展。为此，本研究项目涉及鲁棒（即高效和容错）算法，定义实现效率目标的下限，封装关键算法的可组合构建块，以及允许在可用并行平台上高效执行在高抽象级别指定的程序的程序模拟和转换。

PROJECT SUMMARYProposal Number: NSF 9988304Robust Algorithmic Building Blocks for Parallel Computing PI: Alexander A. ShvartsmanThis research investigates algorithmic approaches to robust building blocks for parallel computing. The research direction is based on the idea that parallel solutions to computational problems can be formulated as compositions of building blocks, components that encapsulate efficient and fault-tolerant parallel implementations of well-defined computation primitives. Building blocks come equipped with precise specifications of their compositionality, and in general provide services at a higher level of abstraction than the operations made available by common parallel programming languages. A major goal of this research is to provide provably efficient building blocks that help the designers of complex parallel applications to concentrate on algorithm design while freeing them from the need to perpetually consider the problem of efficient and effective mapping of the algorithms expressed in some notation to a specific target machine. Traditionally, research in the distributed computing field has concentrated on fault-tolerance, while parallel computing research has taken speed-up as its main focus. This research synthesizes these two foci, and together with the building block methodology, it yields an approach to computing with multiple processors that obtains scalable parallel speed-up, while providing correctness and compositionality guarantees, and enabling graceful degradation in the face of failures. By combining the research on robust parallel computing with the building blocks approach to constructing complex systems, this work intends to substantially advance the state-of-the-art in the theory of effective and efficient parallel computing. Towards this end this research program deals with robust (i.e., efficient and fault-tolerant) algorithms, lower bounds that define the limits for achieving our efficiency goals, composable building blocks that encapsulate key algorithms, and program simulations and transformations that allow to efficiently execute programs specified at a high level of abstraction on the available parallel platforms.