How Good Can Parallel Algorithms Really Be?

机构：U of MD College Park Proposal编号：CCR-9988256并行算法到底能有多好？尤兹·维什金，PI和马诺伊·富兰克林，联合PI提出了并行算法和应用的实验研究。研究人员计划针对指令级并行(ILP)的显式多线程(XMT)平台进行这项研究。这项工作的一个总体目标是促进思考和编程并行“。为此，调查人员将试图更好地了解XMT等平台相对于现有并行和串行平台/模型的性能潜力。研究人员已经完成的工作为混合实验研究和理论分析提供了有趣的初步范例。这项初步工作似乎更新了以前的知识，因为它表明：(I)对于小得多的输入，有可能实现良好的加速。(2)将分析性(非渐近)绩效评估纳入实验绩效分析是可能的；这包括对相对较小的投入的适用性。显式多线程(XMT)是Vicki等人在SPAA‘98论文中介绍的一个细粒度计算框架。XMT通过ILP的方式以更快的单任务完成时间为目标。XMT以并行计算的一些关键思想为基础，涵盖了从算法到体系结构到实现的各个方面；XMT中与实现相关的主要创新是通过结合低开销的硬件和软件机制(以实现更有效的细粒度并行)。

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).