How Good Can Parallel Algorithms Really Be?

并行算法到底有多好？

• 批准号: 9988256
• 负责人: Uzi Vishkin
• 金额: $ 26.78万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-07-15 至 2004-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9988256&HistoricalAwards=false
• 关键词: How; Good; Parallel; Algorithms; Really

Institution: U of MD College ParkProposal Number: CCR-9988256How Good Can Parallel Algorithms Really Be?Uzi Vishkin, PI and Manoj Franklin, co-PIAbstractExperimental study of parallel algorithms and applications is proposed. The investigators plan to conduct this study with respect to the Explicit Multi-Threaded (XMT) platform for instruction-level parallelism (ILP). A general goal of this work is to promote \thinking and programming in parallel". For this the investigators will try to better understand the performance potential of a platform such as XMT relative to existing parallel and serial platforms/models. Work which the investigators have already done provides interesting preliminary examples for mixing experimental research and theoretical analysis. This preliminary work appears to update previous knowledge by suggesting that: (i) Good speedups for much smaller inputs are possible. (ii) Incorporating analytic (non-asymptotic) performance evaluation into experimental performance analysis is possible; this includes applicability to relatively small inputs. Explicit Multi-Threading (XMT) is a fine-grained computation framework introduced in a SPAA'98 paper by Vicki et al. XMT aims at faster single-task completion time by way of ILP. Building on some key ideas of parallel computing, XMT covers the spectrum from algorithms through architecture to implementation; the main implementation related innovation in XMT is through the incorporation of low-overhead hardware and software mechanisms (for more effective fine-grained parallelism).

研究机构：马里兰大学帕克分校提案编号：CCR-9988256并行算法到底有多好？Uzi Vishkin，PI和Manoj富兰克林，co-PI摘要提出了并行算法和应用的实验研究。研究人员计划针对用于并行级并行（ILP）的显式多线程（XMT）平台进行这项研究。这项工作的一个总目标是促进“并行思考和编程”。为此，研究人员将尝试更好地了解XMT等平台相对于现有并行和串行平台/模型的性能潜力。研究人员已经完成的工作为混合实验研究和理论分析提供了有趣的初步例子。 这项初步工作似乎更新了以前的知识，建议：（一）良好的加速小得多的输入是可能的。(ii)将分析（非渐近）性能评估简化为实验性能分析是可能的;这包括适用于相对较小的输入。 显式多线程（XMT）是Vicki等人在SPAA'98论文中介绍的细粒度计算框架。XMT旨在通过ILP加快单任务完成时间。基于并行计算的一些关键思想，XMT涵盖了从算法到架构到实现的范围; XMT中与实现相关的主要创新是通过合并低开销硬件和软件机制（用于更有效的细粒度并行）。