Robust Algorithmic Building Blocks for Parallel Computing

用于并行计算的强大算法构建块

• 批准号: 9988304
• 负责人: Alexander Schwarzmann
• 金额: $ 13.36万
• 依托单位: University of Connecticut
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-08-01 至 2004-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9988304&HistoricalAwards=false
• 关键词: Robust; Algorithmic; Building; Blocks; Parallel

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.

项目摘要编号：NSF 9988304Robust算法构建块，用于并联计算PI：Alexander A. Shvartsmanthisthis Research研究了算法方法，用于稳健的构建块用于并行计算。研究方向是基于这样的想法：计算问题的并行解决方案可以作为构件的组成，即封装有效且容忍度耐受性的计算原始原始基原始人的组成部分。构建块配备了其组成性的精确规格，并且一般而言，与普通并行编程语言提供的操作相比，以更高的抽象提供服务。这项研究的主要目的是提供可靠的有效的构件，以帮助复杂的平行应用设计师专注于算法设计，同时使他们不需要永远考虑在某些指向特定目标机器中表达的算法的有效绘制的问题。传统上，分布式计算领域的研究集中在耐故障上，而平行计算研究已加快了其主要重点。这项研究综合了这两个焦点，并与构件方法相结合，它与多个处理器一起获得了一种计算方法，这些处理器可以获得可扩展的并行加速，同时提供了正确的性和组成性保证，并在面对失败时实现了优雅的降级。通过将强大并行计算的研究与构建复杂系统的构建方法结合起来，这项工作旨在在有效，有效的并行计算理论中实质上推动最新的技术。为此，该研究计划涉及强大的（即高效且耐受耐受性）算法，该算法定义了实现我们的效率目标的限制，可组合构件的构建块，封装了关键的算法和程序模拟和转换，从而可以在可用的平台上有效地执行在可用平台的高级级别上执行的程序。