Selected
CO2P2S Publications and Theses
Summary
John Anvik, Jonathan Schaeffer, Duane Szafron, and Kai Tan. Why Not Use a Pattern-bases Parallel Programming System?, EuroPar, 2003, to appear. A longer version of this paper is available here.
Kai Tan. Pattern-based Parallel Programming in a Distributed Memory Environment, M.Sc. thesis, 2003.
K. Tan, D. Szafron, J. Schaeffer,
J. Anvik, and S. MacDonald, Using Generative Design Patterns to Generate
Parallel Code for a Distributed Memory Environment, to appear in PPoPP'2003:
ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming.
ms. 13, (Abstract or .pdf).
K. Tan, D. Szafron, J. Schaeffer,
J. Anvik, and S. MacDonald, Using Generative Design Patterns to Generate
Parallel Code for a Distributed Memory Environment, to appear in PPoPP'2003:
ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming.
ms. 13, (Abstract or .pdf).
Steve MacDonald, Duane Szafron,
Jonathan Schaeffer, John Anvik, Steve Bromling, Kai Tan, Generative Design
Patterns, 17th IEEE International Conference on Automated Software Engineering
(ASE) September 2002, Edinburgh, UK, 23-34. (Abstract
or .
pdf).
S. Bromling, S. MacDonald,
J. Anvik, J. Schaeffer, D. Szafron, and K. Tan, "Pattern-based Parallel
Programming", submitted to the 2002 International Conference on Parallel
Programming (ICPP-02), Vancouver, British Columbia, August 2002.
(Abstract,
.pdf)
S. MacDonald, S. Bromling,
D. Szafron, J. Schaeffer, J. Anvik and K. Tan, "From Patterns to Frameworks
to Programs", draft paper, 2002.
(Abstract,
.pdf,
.ps)
S. MacDonald, "From Patterns
to Frameworks to Parallel Programs", Ph.D. Thesis, Department of Computing
Science, University of Alberta, 2002.
(Abstract,
.ps,
.ps.gz,
.pdf)
J. Anvik, S. MacDonald, D.
Szafron, J. Schaeffer, S. Bromling and K. Tan, "Generating Parallel Programs
from the Wavefront Design Pattern", to appear in Proceedings of the
7th International Workshop on High-Level Parallel Programming Models and
Supportive Environments (HIPS'02), Fort Lauderdale, Florida, April
2002.
(Abstract,
.pdf)
S. Bromling, "Meta-programming
with Parallel Design Patterns", M.Sc. Thesis, Department of Computing Science,
University of Alberta, 2001.
(Abstract,
.ps)
S. MacDonald, D. Szafron,
J. Schaeffer, and S. Bromling, "From Patterns to Frameworks to Parallel
Programs", submitted to Journal of Parallel and Distributed Computing,
December 2000.
(Abstract,
.ps)
S. MacDonald, D. Szafron,
J. Schaeffer, and S. Bromling, "Generating Parallel Program Frameworks
from Parallel Design Patterns", in Proceedings of the 6th International
Euro-Par Conference (Euro-Par 2000), Munich, Germany, August 2000,
Lecture Notes in Computer Science 1900, Springer-Verlag, pp. 95-104.
(Abstract,
.ps)
S. MacDonald, D. Szafron,
and J. Schaeffer, "Object-Oriented Pattern-Based Parallel Programming with
Automatically Generated Frameworks", in Proceedings of the 5th USENIX
Conference on Object-OrientedTools and Systems (COOTS'99), San Diego,
California, May 1999, pp. 29-43.
(Abstract,
.ps,
.html)
S. MacDonald, J. Schaeffer,
and D. Szafron, "Pattern-based Object-Oriented Parallel Programming", in
Proceedings
of the First International Scientific Computing in Object-Oriented Parallel
Environments Conference (ISCOPE '97), Marina del Rey, California, December
1997, Lecture Notes in Computer Science 1343, Springer-Verlag, pp. 267-274.
(Abstract,
.ps)
Abstract
Using Generative Design Patterns to Generate Parallel
Code for a Distributed Memory Environment
Abstract:
A design pattern is a mechanism
for encapsulating the knowledge of experienced designers into a re-usable
artifact. Parallel design patterns reflect commonly occurring parallel
communication and synchronization structures. Our tools, CO2P3S (Correct
Object-Oriented Pattern-based Parallel Programming System) and MetaCO2P3S,
use generative design patterns. A programmer selects the parallel design
patterns that are appropriate for an application, and then adapts the patterns
for that specific application by selecting from a small set of code-configuration
options. CO2P3S then generates a custom framework for the application that
includes all of the structural code necessary for the application to run
in parallel. The programmer is only required to write simple code that
launches the application and to fill in some applicationspecific sequential
hook routines. We use generative design patterns to take an application
specification (parallel design patterns + sequential user code) and use
it to generate parallel application code that achieves good performance
in shared memory and distributed memory environments. Although our implementations
are for Java, the approach we describe is tool and language independent.
This paper describes generalizing CO2P3S to generate distributed-memory
parallel solutions.
Generative Design Patterns
Abstract:
A design pattern encapsulates the knowledge of object-oriented
designers into re-usable artifacts. A design pattern is a descriptive device
that fosters software design re-use. There are several reasons why design
patterns are not used as generative constructs that support code re-use.
The first reason is that design patterns describe a set of solutions to
a family of related design problems and it is difficult to generate a single
body of code that adequately solves each problem in the family. A second
reason is that it is difficult to construct and edit generative design
patterns. A third major impediment is the lack of a tool-independent representation.
A common representation could lead to a shared repository to make more
patterns available. In this paper we describe a new approach to generative
design patterns that solves these three difficult problems.We illustrate
this approach using tools called CO2P2S and Meta-CO2P2S, but our approach
is tool-independent.
Pattern-based
Parallel Programming
The advantages of pattern-based
programming have been well-documented in the sequential literature. However
patterns have yet to make their way into mainstream parallel computing,
even though several research tools support them. There are two critical
shortcomings of pattern-(or template)-based systems for parallel programming:
lack of extensibility and performance. Patterns are typically limited in
number or scope, thereby narrowing the applicability of a given system.
As well, patterns usually offer generic solutions, which incur additional
runtime overhead that impacts performance. This paper describes our approach
for addressing these problems in the CO2P3S
parallel programming system. CO2P3S
supports multiple levels of abstraction, allowing the user to design an
application with high-level patterns, but move to lower levels of abstraction
for performance tuning. Patterns are implemented as parameterized templates,
allowing the user the ability to customize the pattern to meet their needs.
CO2P3S generates code that is
specific to the pattern/parameter combination selected by the user. The
MetaCO2P3S tool addresses extensibility
by giving users the ability to design and add new pattern templates to
CO2P3S. Since the patterns are
stored in a system-independent format, they are suitable for storing in
a repository to be shared throughout the user community. The CO2P3S/MetaCO2P3S
combination is unique in the parallel computing world.
Return to top.
From Patterns
to Frameworks to Programs
A shortcoming of design patterns
is that they are only applicable at the design phase, offering no support
during the implementation phase of program development. Part of the problem
is that a pattern must be adapted to the problem, a characteristic that
cannot be captured by a single reusable implementation. To solve this problem,
this paper develops a generative design pattern form called a design pattern
template. A pattern template is a pattern form that can be customized using
a set of template parameters, to adapt it to the problem. The customized
template is used to generate object oriented framework code, providing
implementation support. These pattern templates lead to a process for creating
pattern based programming systems that can be the target of tool support.
As an example of such a tool, we present CO2P3S,
one implementation of the process. We further argue the need for meta-templates
to create extensible tools that allow users to add new pattern templates.
To illustrate tool support for meta-templates, we also present MetaCO2P3S.
All of the pattern templates in the latest versions of CO2P3S
have been created using MetaCO2P3S.
Return to top.
From
Patterns to Frameworks to Parallel Programs
Parallel programming offers potentially
large performance benefits for computationally intensive problems. Unfortunately,
it is difficult to obtain these benefits because parallel programs are
more complex than their sequential counterparts. One way to reduce this
complexity is to use a parallel programming system to write parallel programs.
This dissertation shows a new approach to writing object-oriented parallel
programs based on design patterns, frameworks, and multiple layers of abstraction.
This approach is intended as the basis for a new generation of parallel
programming systems. A critical evaluation of existing parallel programming
systems is presented. This evaluation is based on a set of 13 characteristics
of an ideal pattern-based parallel programming system. Based on the results
of this evaluation, the PDP process was created. This process provides
multiple layers of abstraction to support the complete application development
cycle. The first layer supports pattern-based parallel programming by generating
object-oriented frameworks from a design pattern description of the application
structure. The generated code is hidden from the user to ensure correctness.
Lower layers gradually provide access to the generated structural code
and other low-level facilities. The CO2P3S
parallel programming system is an example of a tool that supports the PDP
process. It generates multithreaded Java frameworks for a set of supported
design pattern templates. The utility of this tool is demonstrated by four
example programs which obtain reasonable speedups after being written using
CO2P3S. Further, the results
of a usability experiment are presented. The experiment compared parallel
programming using CO2P3S against
programming in non-CO2P3S Java
with threads. The results show that CO2P3S
users write less application code than their Java counterparts, and that
this code is less complex.
Return to top.
Generating
Parallel Programs from the Wavefront Design Pattern
Object-oriented programming,
design patterns, and frameworks are common techniques that have been used
to reduce the complexity of sequential programming. We have applied these
techniques to the more difficult domain of parallel programming. This paper
describes CO2P3S, a pattern-based
parallel programming system that generates parallel programs from parallel
design patterns. We demonstrate CO2P3S
by applying a new design pattern called the Wavefront pattern to three
problems. We show that it is quick and easy to use CO2P3S
to generate structurally correct parallel programs with good speed-ups
on shared-memory computers.
Return to top.
Meta-programming
with Parallel Design Pattern Templates
A critical shortcoming of template-
or pattern-based systems for parallel programming is their lack of extensibility.
Templates are typically limited in number or scope, thereby narrowing the
applicability of a given system. This dissertation describes my approach
for addressing the extensibility problem in the CO2P3S
parallel programming system. The tool I developed, called MetaCO2P3S,
provides the ability for pattern designers to design and add new pattern
templates to CO2P3S. These pattern
templates are equivalent in form and function to those provided by the
developers of CO2P3S, although
stored in a system-independent format. This makes them suitable for storing
in a repository to be shared throughout the user community. The validity
of MetaCO2P3S is illustrated
through the creation of new pattern templates.
Return to top.
From Patterns
to Frameworks to Parallel Programs
Object-oriented programming,
design patterns, and frameworks are abstraction techniques that have been
used to reduce the complexity of sequential programming. This paper describes
our approach of applying these techniques to the more difficult domain
of parallel programming. We combine these three abstraction techniques
with a fourth kind of abstraction, programming layers. The result is the
Parallel Design Patterns (PDP) process, a new approach to parallel programming
that better matches the needs of parallel programmers. The programmer starts
by selecting a parallel design pattern that matches the structure of the
target application. The system presents the programmer with a pattern template
that includes several parameters that can be set to match the requirements
of the specific application. After the programmer selects the domain-specific
parameters of the pattern template, the system generates a custom framework
that encapsulates all of the parallel structure, including synchronization
and communication code. The generated code serves as the highest of three
layers of application code. At this layer, parallel structure correctness
is guaranteed. Lower layers are used only for performance tuning to make
the code as efficient as necessary. In addition to the PDP process, this
paper briefly describes a parallel programming system called CO2P3S
that implements the process. We use two example applications to illustrate
the process and the CO2P3S system,
and provide some preliminary results from a usability study on the tool.
Return to top.
Generating
Parallel Program Frameworks from Parallel Design Patterns
Object-oriented programming,
design patterns, and frameworks are abstraction techniques that have been
used to reduce the complexity of sequential programming. The CO2P3S
parallel programming system provides a layered development process that
applies these three techniques to the more difficult domain of parallel
programming. The system generates correct frameworks from pattern template
specifications at the highest layer and provides performance tuning opportunities
at lower layers. Each of these features is a solution to a major problem
with current parallel programming systems. This paper describes CO2P3S
and its highest level of abstraction using an example program to demonstrate
the programming model and one of the supported pattern templates. Our results
show that a programmer using the system can quickly generate a correct
parallel structure. Further, applications built using these structures
provide good speedups for a small amount of development effort.
Return to top
Object-Oriented
Pattern-Based Parallel Programming with Automatically Generated Frameworks
The CO2P3S
parallel programming system uses design patterns and object--oriented programming
to reduce the complexities of parallel programming. The system generates
correct frameworks from pattern template specifications and provides a
layered programming model to address both the problems of correctness and
openness. This paper describes the highest level of abstraction in CO2P3S,
using two example programs to demonstrate the programming model and the
supported patterns. Further, we introduce phased parallel design patterns,
a new class of patterns that allow temporal phase relationships in a parallel
program to be specified, and provide two patterns in this class. Our results
show that the frameworks can be used to quickly implement parallel programs,
reusing sequential code where possible. The resulting parallel programs
provide substantial performance gains over their sequential counterparts.
Return to top.
Pattern-based
Object-Oriented Parallel Programming
Over the past five years there
have been several attempts to produce template-based or pattern-based parallel
programming systems (PPS). These attempts have been characterized by a
desire to simplify the production of parallel code and to ensure its correctness,
at the possible expense of performance. In this paper we present the CO2P3S
system, which addresses many of the shortcomings of earlier systems: the
potential for irregularities between the patterns and the code, the lack
of pattern extensibility, the lack of system openness and the difficulties
involved in incremental performance tuning.
Return to top.