Application Development using Compositional Performance Analysis
Creators: name: Rifkin, Adam
Publisher: name: California Institute of Technology
Year: 1999

description: A parallel programming archetype [Cha94, CMMM95] is an abstraction that captures the common features of a class of problems with a similar computational structure and combines them with a parallelization strategy to produce a pattern of dataflow and communication. Such abstractions are useful in application development, both as a conceptual framework and as a basis for tools and techniques. The efficiency of a parallel program can depend a great deal on how its data and tasks are decomposed and distributed. This thesis describes a simple performance evaluation methodology that includes an analytic model for predicting the performance of parallel and distributed computations developed for multicomputer machines and networked personal computers. This analytic model can be supplemented by a simulation infrastructure for application writers to use when developing parallel programs using archetypes. These performance evaluation tools were developed with the following restricted goal in mind: We require accuracy of the analytic model and simulation infrastructure only to the extent that they suggest directions for the programmer to make the appropriate optimizations. This restricted goal sacrifices some accuracy, but makes the tools simpler and easier to use. A programmer can use these tools to design programs with decomposition and distribution specialized to a given machine configuration. By instantiating a few architecture-based parameters, the model can be employed in the performance analysis of data-parallel applications, guiding process generation, communication, and mapping decisions. The model is language-independent and machine-independent; it can be applied to help programmers make decisions about performance-affecting parameters as programs are ported across architectures and languages. Furthermore, the model incorporates both platform-specific and application-specific aspects, and it allows programmers to experiment with tradeoffs better than either strictly simulation-based or purely theoretical models. In addition, the model was designed to be simple. In summary, this thesis outlines a simple method for benchmarking a parallel communication library and for using the results to model the performance of applications developed with that communication library. We use compositional performance analysis - decomposing a parallel program into its modular parts and analyzing their respective performances - to gain perspective on the performance of the whole program. This model is useful for predicting parallel program execution times for different types of program archetypes (e.g., mesh and mesh-spectral), using communication libraries built with different message-passing schemes (e.g., Fortran M and Fortran with MPI) running on different architectures (e.g., IBM SP2 and a network of Pentium personal computers).
description: © 1999 Adam Rifkin, California Institute of Technology. 

Written February 29, 1996. Revised July 7,1999. 

There are so many people to thank for their help in this work Berna Massingill for her help in all aspects of this project; Greg Davis for his help in developing the mesh spectral archetype implementation Anita Mareno John Langford and Lena Petrovic for their help in developing the applications used for our experiments Argonne National Laboratory and Intel Corporation for providing access to suitable computing facilities and Hewlett Packard Microsoft and IBM for their support and resources. This research was supported in part by the NSF under CRPC grant CCR 9120008. Special thanks go to Mani Chandy who has nurtured me in his role as an advisor a leader and a friend. Thanks go to the professors and researchers at Caltech who have inspired me Yaser Abu Mostafa, Jim Arvo, Al Barr, Peter Bossaerts, Colin Camerer, Joel Franklin, Mary Hall, Carl Kesselman, Alain Martin, Chuck Seitz, Peter Schröder, Eric Van de Velde, and Jan L.A. van de Snepscheut. Thanks go to the friends at Caltech who have assisted me and supported me: Diane Goodfellow, Roman Ginis, Robert Harley, Peter Hofstee, Rohit Khare, Joseph Kiniry, Svetlana Kryukova, Rustan Leino, Rajit Manohar, Berna Massingill, Paul Sivilotti, Eve Schooler, John Thornley and Dan Zimmerman. And, thanks go to my parents William and Linda brother Brian and sister Jennifer for always believing in me and to my best friend and wife Michelle, for being the light in my life in sickness and in health.
description: Submitted - CSTR2000.pdf
Submitted - postscript.ps