edith@ai.toronto.edu (Edith Fraser) (03/02/90)
Department of Computer Science, University of Toronto
(SF = Sandford Fleming Building, 10 King's College Road)
-------------------------------------------------------------
SYSTEMS
SF3202, at 2:00 p.m., Friday 16 March 1990
Kathy Yelick
MIT Laboratory for Computer Science
"Writing Fast and Correct Parallel Programs"
It is well-known that writing parallel programs that are both fast and
correct is significantly harder than writing sequential ones. We look at
the specifics of what makes parallel programs more complex to build, and
present an approach that simplifies their construction. The approach is
intended for explicitly parallel, imperative programs, and was developed
from the experience of writing symbolic programs for a shared memory
multiprocessor.
A fundamental problem in parallel programming is the inability to compose
modules; two procedures that work correctly in isolation may behave
unpredictably when run in parallel. Notions related to serializability
have been proposed to define correctness for procedures running in
parallel. While these notions address the module composition problem, they
are sometimes too restrictive, leading to implementations that are overly
complex or inefficient. We show how these notions, which are theoretically
attractive, can be made practical. A second problem is that scheduling
decisions, such as task granularity and order of evaluation, can have a
tremendous impact on performance. Many programming projects have therefore
used application-specific schedulers, which unfortunately complicate the
program structure. In our approach, the programmer has control over
scheduling, but decisions are delayed until late in the design process, and
performance tuning can be done without affecting the basic correctness
conditions of the program.
In this talk, an example is used to illustrate the approach, showing the
entire design process from high level Lamport-style specifications through
performance tuning. The example, term matching, is too small to be
practical, but it forces attention on the important issues of scheduling,
correctness notions, synchronization, and contention. The approach has
also been used to design a much larger program to solve the completion
problem for term rewriting systems.