Browse Theses

This dissertation describes a paradigm for designing efficient parallel programs, called design-level performance debugging of parallel programs. The paradigm combines program design, optimization constraints, complexity estimation, design visualization, and optimization metrics to systematically debug the performance of a parallel program design.

In considering these issues, we have developed (1) a parallel program design methodology, (2) a set of optimization constraints, (3) an approach for estimating the complexities of a parallel program design, (4) a Parallel Software Design Notation (PSDN) for design visualization, and (5) a set of optimization metrics.

In this paradigm, optimization constraints and estimated design complexities are used as building blocks for design visualization in PSDN. In addition to providing insights into a parallel program design, PSDN can be manipulated to achieve efficient parallel program designs. The performance debugging process is guided by optimization constraints and optimization metrics. Optimization constraints serve to ensure correctness with respect to design specifications while optimization metrics are used to measure progress.

We show in this research how our parallel program design paradigm is applied to achieve efficient parallel design patterns for pipeline, tree, and ring multicomputers. These design patterns are parallel divide-and-conquer, parallel all-pair computation, and parallel matrix triangularization.

We also develop a parallel design toolkit, VIPER, to experiment and validate our approach to designing efficient parallel programs. VIPER is an important building block in an integrated parallel programming and performance debugging environment.