Accession Number : ADA293534

Title :   Performance Prediction and Tuning of Parallel Programs.

Descriptive Note : Doctoral thesis,

Corporate Author : ROCHESTER UNIV NY DEPT OF COMPUTER SCIENCE

Personal Author(s) : Crovella, Mark E.

PDF Url : ADA293534

Report Date : AUG 1994

Pagination or Media Count : 127

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)

Descriptors :   *PARALLEL PROCESSING, *COMPUTER PROGRAM VERIFICATION, MATHEMATICAL MODELS, ALGORITHMS, COMPUTATIONS, DATA MANAGEMENT, DISTRIBUTED DATA PROCESSING, COMPUTER COMMUNICATIONS, PREDICTIONS, EFFICIENCY, INPUT OUTPUT PROCESSING, MULTIPROCESSORS, FAST FOURIER TRANSFORMS, ONLINE SYSTEMS, SUBROUTINES, DYNAMIC PROGRAMMING, FIELDS(COMPUTER PROGRAMS), EXECUTIVE ROUTINES, STRUCTURED PROGRAMMING.

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE