Technical reports


Berna L. Massingill, Timothy G. Mattson, and Beverly A. Sanders; "A Pattern Language for Parallel Application Programming"; UF CISE TR 99-022.

A design pattern is a description of a high-quality solution to a frequently occurring problem in some domain. A pattern language is a collection of design patterns that are carefully organized to embody a design methodology. A designer is led through the pattern language, at each step choosing an appropriate pattern, until the final design is obtained in terms of a web of patterns. This paper describes a pattern language for parallel application programs. The current version of the pattern language can be viewed at http://www.cise.ufl.edu/research/ParallelPatterns. The goal of our pattern language is to lower the barrier to parallel programming by guiding a programmer through the entire process of developing a parallel program. The main target audience is experienced programmers who may lack experience with parallel programming. The programmer brings to the process a good understanding of the actual problem to be solved, then works through the pattern language to obtain a detailed parallel design or possibly working code. In this paper, we describe the pattern language, present an example pattern, and sketch a case study illustrating the design process using the pattern language.


Berna L. Massingill; "A Structured Approach to Parallel Programming" (Ph.D. thesis); Caltech CS-TR-98-04.

Parallel programs are more difficult to develop and reason about than sequential programs. There are two broad classes of parallel programs: (1) programs whose specifications describe ongoing behavior and interaction with an environment, and (2) programs whose specifications describe the relation between initial and final states. This thesis presents a simple, structured approach to developing parallel programs of the latter class that allows much of the work of development and reasoning to be done using the same techniques and tools used for sequential programs. In this approach, programs are initially developed in a primary programming model that combines the standard sequential model with a restricted form of parallel composition that is semantically equivalent to sequential composition. Such programs can be reasoned about using sequential techniques and executed sequentially for testing. They are then transformed for execution on typical parallel architectures via a sequence of semantics-preserving transformations, making use of two secondary programming models, both based on parallel composition with barrier synchronization and one incorporating data partitioning. The transformation process for a particular program is typically guided and assisted by a parallel programming archetype, an abstraction that captures the commonality of a class of programs with similar computational features and provides a class-specific strategy for producing efficient parallel programs. Transformations may be applied manually or via a parallelizing compiler. Correctness of transformations within the primary programming model is proved using standard sequential techniques. Correctness of transformations between the programming models and between the models and practical programming languages is proved using a state-transition-based operational model.

This thesis presents: (1) the primary and secondary programming models, (2) an operational model that provides a common framework for reasoning about programs in all three models, (3) a collection of example program transformations with arguments for their correctness, and (4) two groups of experiments in which our overall approach was used to develop example applications. The specific contribution of this work is to present a unified theory/practice framework for this approach to parallel program development, tying together the underlying theory, the program transformations, and the program-development methodology.


Berna L. Massingill and K. Mani Chandy; "Parallel Program Archetypes"; Caltech CS-TR-96-28.

A parallel program archetype is an abstraction that captures the common features of a class of problems with 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. This paper describes an approach to parallel application development based on archetypes and presents two example archetypes with applications.


Adam Rifkin and Berna Massingill; "Performance Analysis for Mesh and Mesh-Spectral Archetype Applications"; Caltech CS-TR-96-27.

This document 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).


Greg Davis and Berna Massingill; "The Mesh-Spectral Archetype"; Caltech CS-TR-96-26.

A parallel program archetype aids in the development of reliable, efficient parallel applications with common computation/communication structures by providing development methods and code libraries specific to the structure. This document presents an archetype for mesh-spectral computations. It describes the common structure captured by the archetype abstraction, discusses a parallelization strategy for such computations, documents our code library to support this parallelization strategy, and presents a collection of tutorial example application programs.


Berna Massingill; "The Mesh Archetype"; Caltech CS-TR-96-25.

A parallel program archetype aids in the development of reliable, efficient parallel applications with common computation/communication structures by providing development methods and code libraries specific to the structure. This document presents an archetype for mesh computations. It describes the common structure captured by the archetype abstraction, discusses a parallelization strategy for such computations, documents our code library to support this parallelization strategy, and presents a collection of example application programs.


Svetlana Kryukova, Berna L. Massingill, and Beverly Sanders; "An Algorithm for Distributed Location Management in Networks of Mobile Computers"; Caltech CS-TR-96-14.

For abstract, see "Specification and Proof of an Algorithm for Location Management for Mobile Communication Devices" above.


Berna L. Massingill; "Integrating Task and Data Parallelism" (M.S. thesis); Caltech CS-TR-93-01.

Many models of concurrency and concurrent programming have been proposed; most can be categorized as either task-parallel (based on functional decomposition) or data-parallel (based on data decomposition). Task-parallel models are most effective for expressing irregular computations; data-parallel models are most effective for expressing regular computations. Some computations, however, exhibit both regular and irregular aspects. For such computations, a better programming model is one that integrates task and data parallelism. This report describes one model of integrating task and data parallelism, some problem classes for which it is effective, and a prototype implementation.