Volume 7, Issue 1 -
Spring/Summer 1999

Volume 6, Issue 3
Fall 1998

Volume 6, Issue 2
Spring/Summer 1998

Volume 6, Issue 1
Winter 1998

Volume 5, Issue 4
Fall 1997

Volume 5, Issue 3
Summer 1997

Volume 5, Issue 2
Spring 1997

Volume 5, Issue 1
Winter 1997

Volume 4, Issue 4
Fall 1996

Volume 4, Issue 3
Summer 1996

Volume 4, Issue 2
Spring 1996

Volume 4, Issue 1
Winter 1996

Volume 3, Issue 4
Fall 1995

Volume 3, Issue 3
Summer 1995

Volume 3, Issue 2
Spring 1995

Volume 3, Issue 1
January 1995

Volume 2, Issue 4
October 1994

Volume 2, Issue 3
July 1994

Volume 2, Issue 2
April 1994

Volume 2, Issue 1
January 1994

Volume 1, Issue 4
October 1993

Volume 1, Issue 3
July 1993

Volume 1, Issue 2
April 1993

Volume 1, Issue 1
January 1993


Mani Chandy, Greg Davis, Svetlana Kryukova, Berna Massingill, Dan Meiron, Sean Mauch, Steve Roy, Caltech;
Ian Foster, Argonne National Laboratory

Editor's note: Previously, this newsletter's "Research Focus" articles have examined the work of one of the CRPC's main research thrusts. As the work of these groups begins to converge toward the main goal of parallel computing, it becomes necessary to examine the collaborations between these groups. The following article describes one of several of these collaborations.

Most computer users are concerned primarily with their applications and only secondarily with the process of computing. The success of a computational tool depends on how well it meets the needs of a class of users who need help with a few specific applications. For example, spreadsheets are so successful because they meet very specific accounting needs, and they meet these needs very well. Computational tools span the spectrum from being general to specific. Hardware, operating systems, and most programming languages are general—they can be used for any application. Spreadsheets, fluid dynamics simulation programs, and computer-aided design tools for architecture are examples of domain-specific tools.

Sequential programming tools have been developed over four decades, from very general tools to very specific tools. The explosive growth of the personal computer market shows the power of the strategy of pyramid tool development, starting with a few general tools (such as the PowerPC, x86s, Windows, C) and ending with an immense variety of application- specific tools.

Rapid transfer of parallel computing technologies suggests that researchers use the pyramid strategy for tool development. A great deal of research has gone into the most general parallel tools--machines, object-oriented libraries, and languages such as HPF and HPC++. Research on specific parallel applications has focused on developing the bridging technologies that facilitate the exploitation of general parallel tools for specific applications.

Programming deals with five basic aspects:

  1. structure of the program itself,
  2. methods of developing a program from its specification in a systematic manner,
  3. correctness: methods for reasoning about the correctness of the program, test suites, and methods of testing,
  4. performance: analysis of performance with suggestions for tuning an application to obtain the best performance on specific machines, and
  5. documentation: user manual, installation guidelines, and description of the program.

A technology that bridges the general to the specific must deal with these five aspects. Therefore, this research effort, called Parallel Program Archetypes, deals with tools for providing a bridge between general tools and specific applications in five areas: program structure, systematic development, correctness, performance, and documentation.

The central idea is that there are classes of parallel applications with common program structures, arguments for correctness, performance analysis, and documentation. The group's goal is to encapsulate each class into an archetypal program that can then be tailored to obtain specific applications. What distinguishes this research is that it attempts to deal with all aspects of an application, not merely its program structure. There are many research groups working on higher-order functional programming, frameworks, templates, and meta-libraries. The Parallel Program Archetypes group believes that this work should be extended to deal with archetypal methods of reasoning about correctness, archetypal performance tuning for different machines, and archetypal documentation structures. Our emphasis on archetype-specific tools for performance, correctness, and documentation is one of the unique features of this effort.

Initial efforts in parallel archetypes constitute joint work between the CRPC Parallel Paradigm Integration group and the Parallel Algorithms for Physical Simulation group. Current focus is on two areas: (a) mesh-spectral computations and (b) search problems.

Mesh-spectral computations are used in a variety of domains, including fluid dynamics, computational electromagnetics, and environmental modeling. Tree-search methods are used in a wide range of optimization problems. These problems were chosen because many CRPC researchers are developing applications based on these methods and mesh-spectral computations have a very different structure from tree-search computations. Research on mesh- spectral computations is being carried out by Berna Massingill and Greg Davis. Research on search archetypes is being done by Svetlana Kryukova. Initial results are available through the World Wide Web page at http://www.etext.caltech.edu. An important aspect of this research effort is that significant contributions were made by undergraduate women from universities all over the United States, under the auspices of the CRPC Summer Women's Program.

An important characteristic of parallel archetypes is that they are language-independent. The group's initial efforts have used Fortran M, a task-parallel version of Fortran that was developed in collaboration with CRPC researcher Ian Foster and his colleagues at Argonne National Laboratory. However, the group has also ported the archetype structure very easily to Fortran and C codes by using standard message passing libraries, such as PVM and MPI, or architecture specific libraries such as Intel's NX. Ports to CC++, a language extension, are particularly interesting because C++ supports template abstractions. A goal is to structure archetypes so that porting across languages and libraries is straightforward and can even be accomplished automatically using source-to-source translation.

The group has used parallel archetypes to develop applications in fluid dynamics, electromagnetics, and optimization. There is currently an ongoing research effort to use this idea to encapsulate more complicated dynamic algorithms, such as adaptive mesh refinement and fast multipole methods.

A yardstick for evaluating the success of the archetype approach is the relative ease with which the total application (including reasoning about correctness, performance tuning, and documentation) was developed. At this point, the group's experience is largely anecdotal, but it is very positive and suggests that they continue their efforts. In the coming year, the group plans to obtain archetype-specific performance tools, develop archetypes in Fortran D, and develop archetypes for other areas of parallel simulation.

Table of Contents

News | From the Director | Parallel Profile | Research Focus | Work in Progress | Education / Outreach | Resources | Calendar | CRPC Home