Programming abstractions for

5.4. RESEARCH PLAN

5.3.2

Partition Data vs Partition Computation

One philosophy in building abstractions for locality is to support abstractions for explicit partitioning of

the data. The idea is that this is done in one place, localizing the programmer’s specification of partitioning

policy to one place for each data structure. The partitioning and distribution of computation is derived,

by the compiler, from the data partitioning. By making the partitioning of data explicit the computation

can operate on a local view of each data partition. It has the advantage of reducing the amount of complex

reasoning that must be performed by the runtime to correctly associate the computation with the relevant

data, and also makes communication cost more visible to the programmer.

However, on the negative side, explicit control could lead to composition challenges if the data layout

choices are inconsistent. Data partitioning and distribution choices may turn out to be inconsistent when

computations combine data from different sources, or when operations are composed. Thus, this approach

naturally leads to programmers being required to make communication explicit.

Data partitioning fully constrains partitioning of computation if the implementation is confined to a

uniform placement rule, like “owner computes” - the idea is that the execution of each assignment’s RHS is

determined by the placement of the location it is being assigned to.

In contrast, explicit partitioning and distribution of the computation is attractive as it is a local

decision for example, for each parallel loop separately. The distribution, and movement, of data is then

automatically derived by the compiler. Because the computational code is independent of partitioning it

necessarily has a global view of the data.

Explicit partitioning of computation naturally leads to data movement being hidden - the communication

cost of producing data with one distribution, while using in with another, is an implicit consequence of where

the computation has been placed. There are also problems with other ways of combining software components

- for example, with nested parallel loops and loops that call parallel functions.

5.3.3

Compositional Metadata

Communication and locality are a consequence of the dependences and reuses that arise when software

components are composed. Thus, communication and locality are fundamentally non-compositional - they

belong to the composition, not to the component. To make the idea of software components work - a key

foundation for abstraction - we need to characterize each component in a way that allows the dependences

to be derived when the component is combined with others.

This idea leads to a “do what I mean” model, where computational partitioning, data distribution and

data movement can be derived automatically. The programmer does not, then, have explicit control of

what happens where, or where communication will occur. However, programmers can reason about the

communication cost of data accesses — and profiling tools can apportion communication costs to data

accesses. This approach is advantageous because it offers more flexibility to the runtime in making choices

about how to map data to the underlying hardware, but this also requires a lot of intelligence on the part

of the runtime system to make cogent decisions.

5.4

Research Plan

The consensus from the meeting was that the major research challenges begin with:

• Getting the abstraction right: We need to design abstractions and representations that (1) achieve

a separation of concerns, so that experts at algorithmic levels can develop sophisticated higher-level

methods independently from experts at lower-level performance-focused levels developing sophisticated

implementation techniques. We need to design abstractions that enable programmers to reason at an

appropriate level for their task, and their expertise.

• Multiresolution: We need to support automatic implementation of high-level, abstract models. We

also need tool and language support for explicit management of performance issues, such as partitioning

and movement of data. We need explicit mechanisms for programmers to work at multiple such levels

in a fully supported way.

Programming Abstractions for Data Locality

29

---

5.4. RESEARCH PLAN

• Generality beyond multidimensional arrays: Multidimensional arrays, structured meshes and

regular data structures are important and there is huge scope for more sophisticated tools to support

them - but richer data structures offer enormous scope, particularly for more ambitious methods,

and more complex applications. We need to design tools, languages and abstractions that support

hierarchical, hybrid and unstructured meshes, adaptivity in various forms, sparse representations and

graph-based data.

The meeting brought together researchers pursuing a variety of directions; we highlight the following as

perhaps the most promising:

• Language design and implementation: There is a clearly-demonstrated opportunity for languages

in which locality is a first-class concept. Doing so opens up opportunities for expressivity, performance

and enhanced correctness.

• Compilation, code synthesis and multistage programming: Tools that generate code have

proven enormously powerful - but are often built in ad-hoc ways. There is potential to support code

synthesis, runtimecode generation, and multistage programming as a first-class language feature. Code

generation allows static scheduling to be combined flexibly with dynamic scheduling. Code generation

allows high-level abstractions to be supported in the generator, thus avoiding runtime overheads.

• Programming languages theory, in particular type systems: How can we have polymorphic

collection types without overcommitting to storage layout? Can we use types to track sharing, transfer

of ownership, uniqueness, protocols? There is promising work in all of these areas.

• Close engagement with leading science code communities and their users: There is a long

tradition of tools being developed in isolation from serious use-cases, or deeply embedded within just

one, narrow application context. The most promising strategy must be to develop tools in a context

that allows a broad class of application engagements beyond toy, or benchmark, problems.

• Polyhedral methods: The polyhedral model provides a uniquely powerful model for describing

scheduling and data layout. There are huge opportunities to bring this power to bear in more general

and more complex contexts.

Programming Abstractions for Data Locality

30

---