Performance Prediction and Tuning of Parallel Programs.

Abstract

Parallel programs often behave in unexpected ways due to the complex relationship between the structure of a parallel program the machine on which it is run, the number of processors used, the program's input and the measured running time of the program. As a result, performance tuning of parallel programs is an error-prone, time-consuming process. This dissertation describes a set of tools and methods for assisting the programmer in finding the best-performing implementation for a parallel program and in answering common questions that arise during the performance tuning process. Our approach is based on three contributions: new metrics for the measurement of parallel applications, a new approach to the analysis of parallel program performance, and a new modelling method that allows the programmer to predict the performance of a program in advance of a complete implementation. The metrics, which we call performance predicates, provide measurements that are amenable to analysis and yet completely capture parallel overheads. The analysis method, lost cycles analysis applies algorithmic analysis to parallel overheads, assisted by an on-line tool. The modelling method allows lost cycles analysis to be applied to program fragments, and provides rules for aggregating analytic results into a model for the execution time of a (possibly not-yet-implemented) parallel application. We use implementations of subgraph isomorphism and 2D FFT on the SGI Challenge Series and KSR1 multiprocessors to illustrate our methods and tools and show how our approach can be used to explain surprising performance results and predict the performance of alternative implementations of an application in advance of implementation, while avoiding large numbers of measurements for performance tuning. (AN)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1994
Accession Number
ADA293534

Entities

People

  • Mark E. Crovella

Organizations

  • University of Rochester

Tags

Communities of Interest

  • Energy and Power Technologies
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Application Software
  • Communication Systems
  • Computer Programming
  • Computer Programs
  • Computer Science
  • Computers
  • Data Analysis
  • Databases
  • High Performance Computing
  • Network Science
  • Operating Systems
  • Parallel Computing
  • Parallel Processing
  • Parallel Processors
  • Performance Engineering
  • Software Development
  • Two Dimensional

Fields of Study

  • Computer science
  • Engineering

Readers

  • Parallel and Distributed Computing.
  • Theoretical Analysis.