Measurement and Prediction of Parallel Program Performance

本研究的目标是开发一套用于并行程序的性能分析和调优的工具和技术，以弥合测量和建模以及理论和实践之间的差距。性能测量和建模的方法被称为“丢失周期分析”，其基础是观察到生产性计算和并行开销之间的区别对于性能诊断和性能预测都是有用的。这种方法将所有并行开销分解为相互排斥但又全面的类别(如负载不平衡和通信开销)，每个类别都可以单独测量和建模。这些类别以公共单位表示开销，称为“丢失的周期”，它们一起表示没有用于有用计算的总执行时间的部分。这项研究工作的目标是构建一个丢失周期工具包，将统计数据中的经验建模技术与丢失周期分析的测量和建模技术相结合，以生成应用程序性能的准确模型。该工具包将使用并行系统中开销来源和特征的先验知识来指导和约束建模过程。它将把优化实验设计的技术结合到一个实验生成工具中，该工具将生成一个典型程序执行的“脚本”。在这些执行过程中，它将使用测量工具来记录每个开销类别的损失周期，作为感兴趣的变量(包括但不限于处理器数量和问题大小)的函数。它将使用执行过程中获得的测量结果，从管理费用类别的标准模型数据库中进行选择。此外，它还将使用一种工具，将开销类别模型与实验数据进行拟合，以建立与特定硬件和软件系统相关的常量。通过尽可能地自动化性能建模，这项工作旨在使丢失循环分析适用于并行程序员的日常使用。***

The goal of this research is to develop a set of tools and techniques for performance analysis and tuning of parallel programs that bridges this gap between measurement and modeling, and theory and practice. The approach to performance measurement and modeling is called "lost cycles analysis", and is based on the observation that the distinction between productive computation and parallel overhead is useful both for performance diagnosis and for performance prediction. This approach decomposes all parallel overhead into mutually-exclusive, yet comprehensive categories (such as load imbalance and communication overhead), each of which can be measured and modeled separately. These categories express overheads in common units, called "lost cycles", and together represent the portion of the total execution time not devoted to useful computation. This research effort's goal is to build a lost cycles toolkit, integrating empirical model-building techniques from statistics with the measurement and modeling techniques of lost cycles analysis to generate accurate models of application performance. The toolkit will use a priori knowledge of the sources and characteristics of overhead in parallel systems to guide and constrain the modeling process. It will incorporate techniques for optimum experimental design into an experiment generation tool that will generate a "script" of representative program executions. During these executions it will use a measurement tool to record the lost cycles for each overhead category as a function of the variables of interest (including, but not limited to, the number of processors and the problem size). It will use the measurement results obtained from the executions to select from a database of standard models for overhead categories. In addition, it will use a tool for fitting models of overhead categories to experimental data to establish the constants associated with a particular hardware and software system. By automating perfo rmance modeling as much as possible, this effort intends to make lost cycles analysis practical for everyday use by parallel programmers. ***