PARALLEL PROGRAMMING WITH CONTROL ABSTRACTION

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.