Parallel Algorithm Design: From Theory to Practice

PI：Ramachandran，Vijaya机构：德克萨斯大学奥斯汀分校建议编号：9988160项目摘要并行处理的一个重要目标是开发通用的并行模型和算法。这里的挑战一直是在简单性、准确性和广泛适用性之间找到合适的平衡。该项目将通过使用过去十年提出的三种通用并行计算模型|批量同步并行(BSP)、对数并行(LogP)和队列共享内存(QSM)模型|以及外部内存并行磁盘模型(PDM)，开发适合于实际使用的全面的并行算法集合。将为这些模型的有效算法的设计开发一些统一的主题，这些主题将形成关于这些模型的算法的系统开发的基础。将开发的算法范围从基本原语的核心算法到重要应用的算法。这项研究将揭示与这些众所周知的模型相关的统一主题，并将导致快速、高效的并行算法在广泛的并行机上具有良好的性能，以解决实际中常见的大问题规模。此外，这项研究将通过对渐近最优算法和下界的研究，深入了解并行处理的基本优势和局限性。

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.