Applications typically have several potential sources of parallelism, and in choosing a particular parallelization, the programmer must balance the benefits of each source of parallelism with the corresponding overhead. The trade-offs are often difficult to analyze, as they may depend on the hardware architecture, software environment, input data, and properties of the algorithm. An example of this dilemma occurs in a wide range of problems that involve processing trees, wherein processors can be assigned either to separate subtrees, or to parallelizing the work performed on individual tree nodes. We explore the complexity of the trade-offs involved in this decision by considering alternative parallelizations of combinatorial search, examining the factors that determine the best-performing implementation for this important class of problems. Using subgraph isomorphism as a representative search problem, we show how the density of the solution space, the number of solutions desired, the number of available processors, and the underlying architecture all affect the choice of an efficient parallelization. Our experiments, which span seven different shared-memory multiprocessors and a wide range of input graphs, indicate that relative performance depends on each of these factors. On some machines and for some inputs, a sequential depth-first search of the solution space, applying simple loop-level parallelism at each node in the search tree, performs best. On other machines or other inputs, parallel tree search performs best. In still other cases, a hybrid solution, containing both parallel tree search and loop parallelism, works best. We present a quantitative analysis that explains these results and present experimental data culled from thousands of program executions that validates the analysis. From these experiences we conclude that there is no one "best" parallelization that suffices over a range of machines, inputs, and precise problem specifications. As a corollary, we provide quantitative evidence that programming environments and languages should not focus exclusively on flat data parallelism, since nested parallelism or hybrid forms of parallelism may be required for an efficient implementation of some applications.

Parallel programming involves finding the potential parallelism in an application and mapping it to the architecture at hand. Since a typical application has more potential parallelism than any single architecture can exploit effectively, programmers usually limit their focus to the parallelism that the available control constructs express easily and that the given architecture exploits efficiently. This approach produces programs that exhibit much less parallelism that exists in the application, and whose performance depends critically on the underlying hardware and software. We argue for an alternative approach based oncontrol abstraction. Control abstraction is the process by which programmers define new control constructs, specifying constraints on statement ordering separately from an implementation of that ordering. With control abstraction programmers can define and use a rich variety of control constructs to represent an algorithm's potential parallelism. Since control abstraction separates the definition of a construct from its implementation, a construct may have several different implementations, each exploiting a different subset of the parallelism admitted by the construct. By selecting an implementation for each control construct using annotations, a programmer can vary the parallelism in a program to best exploit the underlying hardware without otherwise changing the source code. This approach produces programs that exhibit most of 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.

Abstract Elmwood is an object‐oriented, multiprocessor operating system designed and implemented during a graduate seminar. It consists of a minimal kernel and a collection of user‐implemented services. The kernel provides two major abstractions:objects, which consist of code and data, and processes, which represent asynchronous activity. Objects, like programs, are passive. To operate on an abstraction or to request a service, processes invoke anentry proceduredefined by the corresponding object. Objects implement their own protection and synchronization policies using minimal kernel mechanisms. We describe the Elmwood kernel interface, an implementation on the BBN Butterfly parallel processor, and our experiences in developing a multiprocessor operating system under rigid time constraints. These experiences illustrate several general lessons regarding kernel design and trade‐offs for implementation expedience.