Research > Productivity Layer
We believe the key to generating a successful software developer community for manycore is to maximally leverage the efforts of parallel programming experts by encapsulating their software for use by the programming masses. As mentioned above, we plan to reuse expert work through parallel libraries and programming frameworks. Productivity layer programmers will compose these into applications with the help of a composition and coordination language [Lucco and Sharp 1991; Gelernter and Carriero 1992]. The language will be implicitly parallel (i.e., the composition will have serial semantics), which means that the composed programs will be safe (e.g., race-free) and virtualized w.r.t. processor resources. The language will document and check interface restrictions to avoid concurrency bugs resulting from incorrect composition; for example, if instantiating a framework with a stateful function when a stateless one is required. Finally, the language will support definition of domain-specific abstractions to support construction of application frameworks, offering a programming experience similar to that in MatLab [Karnofsky 1996], SQL [Date 1989], or Sawzall [Pike 2005]. Our audio and browser applications both involve the construction and use of such domain-specific frameworks.
To illustrate the responsibilities of the composition language, consider a structured grid framework, which may require independence of its plug-ins. The programmer writes a stencil operation that reads a limited domain of one grid and writes to a single point in another grid. (The unstructured grid framework is similar, but the data structure is an arbitrary graph.) The side-effect properties of the stencil plug-in will be enforced either by (conceptually) copying input arguments, or by supplying the framework with partition functions that are guaranteed to produce non-overlapping results. The partition operations may be simple array slices, or a graph partitioner that is guaranteed to output non-overlapping partitions. Thus, a graph partitioner library would have associated semantic properties (independence) with its output; these will be written in the coordination language, although the library itself may be written in expert programmers’ languages of choice.
The key problem in composing parallel code is correctness. To understand what restrictions we place on composition to make correctness easier to achieve, it helps to consider two kinds of codes: parallel (P) and serial (S). Their composition can be divided into four types: S->S, S->P, P->S, and P->P (here the “->” refers to a calling relationship, i.e., S->P means serial code calls parallel code). S->S is well supported in existing languages, and S->P is a common invocation of a parallel library, so we focus on P->S and P->P composition. We believe that P->P is only for experts and is only allowed in the efficiency layer. P->S corresponds to parameterizing a parallel framework with a component that has a serial interface.
The ability to compose parallel pieces also introduces potential performance problems, since it involves combinations of parallel schedulers [Cosnard, Jeannot et al. 2001; Gürsoy and Kale 2004; Cicotti and Baden 2006]. For example, after composition, a scheduler designed to carefully map a fixed set of computations on an equal number of cores may be used within the computations in a task-stealing framework. To allow for scheduler cooperation, frameworks will be parameterized by their resource requirements so that they can adapt to the context in which a framework is running. These requirements may change across program phases. We will develop tools to custom-generate thread scheduling code from the coordination and composition language.