Parallel Algorithm Design: From Theory to Practice

PI：Ramachandran，Vijaya机构：德克萨斯州奥斯汀大学提案编号：9988160A。并行处理的一个重要目标是开发通用并行模型和算法。这里的挑战是在简单性，准确性和广泛的适用性之间找到正确的平衡。这个项目将开发一个全面的收集并行算法适合实际使用的工作与三个通用的并行计算模型，已提出了在过去的十年|批量同步并行（BSP）、LogP和可扩展共享内存（QSM）模型|以及与外部存储器并行磁盘模型（PDM）。在这些模型上设计有效算法的一些统一的主题将被开发出来，这些将成为在这些模型上系统开发算法的基础。要开发的算法将从基本原语的核心算法到重要应用的算法，研究将揭示与这些著名模型相关的统一主题，并将导致快速和有效的并行算法，在广泛的并行机上具有良好的性能，以解决实际中常见的大问题。此外，这项研究将提供洞察到的基本好处和限制并行处理通过theinvestigation的渐近最优算法和下限。

PI: Ramachandran, VijayaInstitution: U of Texas AustinProposal Number: 9988160A. Project SummaryAn important goal in parallel processing is the development of general-purpose parallel models and algorithms. The challenge here has been to findthe right balance between simplicity, accuracy and broad applicability. Thisproject will develop a comprehensive collection of parallel algorithms suitablefor practical use by working with three general-purpose parallel computationmodels that have been proposed over the last decade | Bulk-SynchronousParallel (BSP), LogP, and Queuing Shared-Memory (QSM) models | aswell as with the external memory Parallel Disk Model (PDM). Some uni-fying themes for the design of efficient algorithms on these models will bedeveloped, and these will form the basis for a systematic development of al-gorithms on these models. The algorithms to be developed will range fromkernel algorithms for basic primitives to algorithms for important applica-tions.The research will expose unifying themes relating these well-known models, and will result in fast and efficient parallel algorithms withgood performance on a wide range of parallel machines for large problem sizestypically seen in practice. Additionally, this research will provide insight intothe fundamental benefits and limitations of parallel processing through theinvestigation of asymptotically optimal algorithms and lower bounds.