Kismet: parallel speedup estimates for serial programs
Kismet: parallel speedup estimates for serial programs
复制标题
Kismet：串行程序的并行加速估计
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
M. Taylor
中科院分区：
文献类型：
--
作者：
Donghwan Jeon;Saturnino Garcia;Christopher M. Louie;M. Taylor
现在，软件工程师面临着重构串行程序以在多核处理器上并行执行的艰巨任务。目前，对于这项任务可能带来多少好处，或它们与最佳并行化的距离，他们几乎没有提供任何指导。本文介绍了Kismet，该工具为无与伦比的串行程序创建并行加速估算。 Kismet与以前的方法不同，因为它不需要对程序进行任何手动分析或修改。这种差异允许对许多程序进行快速分析，避免对从根本上有限的工程进行浪费的工作。为了完成这项任务，Kismet建立在层次临界路径分析（HCPA）技术的基础上，该技术是最近开发的动态分析，将平行性定位于目标程序中每个潜在嵌套区域。然后，它使用并行执行时间模型来计算近似上限的性能，建模源于硬件参数和内部程序结构的约束。
我们的评估将KISMET应用于在32核AMD多功能系统上运行的八个高平行性NAS并行基准测试，五个低平行性Specint基准和六个在良好的MIT RAW处理器上运行的中等平行基准。结果令人信服。 KISMET能够根据临界路径分析显着提高相对于先前工作的并行加速估计的准确性。
Software engineers now face the difficult task of refactoring serial programs for parallel execution on multicore processors. Currently, they are offered little guidance as to how much benefit may come from this task, or how close they are to the best possible parallelization. This paper presents Kismet, a tool that creates parallel speedup estimates for unparallelized serial programs. Kismet differs from previous approaches in that it does not require any manual analysis or modification of the program. This difference allows quick analysis of many programs, avoiding wasted engineering effort on those that are fundamentally limited. To accomplish this task, Kismet builds upon the hierarchical critical path analysis (HCPA) technique, a recently developed dynamic analysis that localizes parallelism to each of the potentially nested regions in the target program. It then uses a parallel execution time model to compute an approximate upper bound for performance, modeling constraints that stem from both hardware parameters and internal program structure.
Our evaluation applies Kismet to eight high-parallelism NAS Parallel Benchmarks running on a 32-core AMD multicore system, five low-parallelism SpecInt benchmarks, and six medium-parallelism benchmarks running on the finegrained MIT Raw processor. The results are compelling. Kismet is able to significantly improve the accuracy of parallel speedup estimates relative to prior work based on critical path analysis.