La. Crowl et Tj. Leblanc, PARALLEL PROGRAMMING WITH CONTROL ABSTRACTION, ACM transactions on programming languages and systems, 16(3), 1994, pp. 524-576
Parallel programming involves finding the potential parallelism in an
application and mapping it to the architecture at hand. Since a typica
l application has more potential parallelism than any single architect
ure can exploit effectively, programmers usually limit their focus to
the parallelism that the available control constructs express easily a
nd that the given architecture exploits efficiently. This approach pro
duces programs that exhibit much less parallelism than exists in the a
pplication, and whose performance depends critically on the underlying
hardware and software. We argue for an alternative approach based on
control abstraction. Control abstraction is the process by which progr
ammers define new control constructs, specifying constraints on statem
ent ordering separately from an implementation of that ordering. With
control abstraction programmers can define and use a rich variety of c
ontrol constructs to represent an algorithm's potential parallelism. S
ince control abstraction separates the definition of a construct from
its implementation, a construct may have several different implementat
ions, each exploiting a different subset of the parallelism admitted b
y the construct. By selecting an implementation for each control const
ruct using annotations, a programmer can vary the parallelism in a pro
gram to best exploit the underlying hardware without otherwise changin
g the source code. This approach produces programs that exhibit most o
f the potential parallelism in an algorithm, and whose performance can
be tuned simply by choosing among the various implementations for the
control constructs in use. We use several example applications to ill
ustrate the use of control abstraction in parallel programming and per
formance tuning and describe our implementation of a prototype program
ming language based on these ideas on the BBN Butterfly.