Programming abstractions for

1.2. ORGANIZATION OF THIS REPORT

1.2

Organization of this Report

Chapter 3 discusses the requirements of applications and their wish list from the programming environ-

ments. There are numerous abstractions for multidimensional arrays through tiling, array views, layouts

and iterators to managing data locality, which are described in Chapter 4 and their language and compiler

approaches are discussed in Chapter 5 of this document. These abstractions also extend to task-oriented

asynchronous programming paradigms (Chapter 6) and to system-level optimization issues (Chapter 7), such

as optimizing the mapping of the application communication topology to the underlying network topology.

These programming model abstractions can expose crucial information about data locality to the compiler

and runtime system to enable performance-portable code. The research question is to identify the right level

of abstraction, which includes techniques that range from template libraries all the way to new languages

to achieve this goal. By bringing together pioneers in the field of developing new data-centric programming

models, there is an opportunity to identify commonalities in strategy to enable us to combine the best of

these concepts to develop a comprehensive approach to expressing and managing data locality on exascale

programming systems.

1.3

Summary of Findings and Recommendations

In this section, we provide a succinct list of findings and recommendations that are derived from the conclu-

sions of five panels at the workshop

1. Motivating applications and their requirements,

2. Data structure and layout abstractions,

3. Language and compiler support for data locality,

4. Data locality in runtimes for task models, and

5. State-scale data locality management.

The details of findings and recommendations are discussed in their respective chapters.

1.3.1

Motivating Applications and Their Requirements

Findings: Applications must be refactored to work within the constraints of anticipated exascale machine

architectures. Being able to express the latent data locality is critical, however, there are no real options

for doing so in the current programming environments. The available options usually force a choice between

performance and portability, and often act as inhibitors instead of aiding compilers in extracting the locality

information. Because the need is urgent, and application developers are chary of dependencies they cannot

rely on, if there are no formal agreements on mechanisms for expressing locality, there is a real possibility

that every application will develop its own ad-hoc solution. This is clearly suboptimal because of the massive

duplication of efforts in development and long-term cost incurred by continued maintenance of numerous

ad-hoc implementations. It will be much harder to get applications to change after they have integrated a

coping mechanism that works.

Recommendations: Application developers must be part of the conversation regarding the development of

new programming environment support. Finding commonalities across the many constituent applications

can provide guidance to developers of data-centric programming models and tools. Getting functioning

abstractions for data locality into the hands of application and algorithm developers early in the process of

code refactoring is critical. The window of opportunity for this interaction will be open for a few generations

of systems on the path towards exascale at the end of the decade.

Programming Abstractions for Data Locality

3

---

1.3. SUMMARY OF FINDINGS AND RECOMMENDATIONS

1.3.2

Data Structures and Layout Abstractions

Findings: There are a number of existing library, annotation, and compiler-based techniques that are built

around the abstraction of data structures and layout that rely upon very similar underlying semantics. These

semantics include the association of additional metadata with array types that describe data decomposition

(e.g., tiling) and data layouts and the use of lambda functions (anonymous functions that are now part of

the C++11 standard) to abstract loop ordering and to promote array dimensionality a first-class citizen.

There are a broad array of examples of variations on these same themes of data layout abstractions that

have demonstrated valuable performance portability properties, and are even being pressed into service for

production codes in library form (Dash, TiDA, Gridtools, and Kokkos).

Recommendations: In the area of Data Structures and Layout Abstractions, the various formulations that

use common underlying semantics (lambdas, dimensionality, and metadata describing tiling and layout) are

well positioned for some form of standardization of practices through meetings and agreements between

the many parties who have created implementations of these formulations. The value of a standardization

effort would be to enable a common runtime system to serve the needs of multiple implementations of these

constructs, and also to pave the way for compiler support. A prerequisite for extensions to any language

standard is such standardization of the underlying semantics.

1.3.3

Language and Compiler Support for Data Locality

Findings: While locality-aware programming can be expressed using library-based notations (such as em-

bedded DSLs implemented via template metaprogramming), we identified several benefits of raising such

abstractions to the language level, including: support for clearer syntax, which can clarify a program’s local-

ity decisions for a human reader while also making the author’s intention manifest to the compiler; support

for stronger semantic checks and type-system-based guarantees within the compilation environment; and

optimization opportunities in which the compiler can improve the code’s execution in ways that a strictly

library-based solution could not. A common theme across most of the programming languages surveyed in

the workshop (not to mention the library-based approaches) was the specification of locality concerns as part

of a program’s declarations rather than its computation sections—for example, by describing how an array

is distributed to a set of memories as part of its declaration rather than annotating each individual loop nest

or array operation with such information. This approach permits a programmer to switch between distinct

locality options in a data-centric way, allowing the compiler and/or runtime to propagate those choices down

to the computations, thereby minimizing the amount of code that must be modified as architectures and

program requirements change.

Recommendations: Our recommendation is to continue pursuing library-based programming notations as

a means of prototyping new abstractions, but to simultaneously invest in language- and compiler-based

solutions in order to maximize the return on the user’s investment via the strengths afforded by a language-

based approach. We recommend pursuing languages that support a multiresolution philosophy in which

programmers can seamlessly move from higher-level declarative abstractions to lower-level imperative control

as needed by their algorithm or its requirements; in such an approach, programmers should also be able to

author and deploy their own higher-level abstractions (e.g., distributed data structures) using the lower-

level concepts. To maximize adoptability and avoid throwing highly-tuned code away, such languages must

remain interoperable with conventional ones. There was also a strong consensus among the group to avoid

compiler-based techniques that prematurely lower high-level abstractions to an equivalent but simplified

internal representation, thereby discarding crucial locality-oriented semantic information. A key example is

the lowering of multidimensional arrays to 1D arrays with per-dimension offsets and multipliers.

1.3.4

Data Locality in Runtimes for Task Models

Findings: Task models have historically focused on balancing computational work among parallel processing

elements using simple mechanisms such as work-stealing and self-scheduling. However, as we move forward

a locality agnostic balancing mechanism will optimize computational load-imbalances in a manner that runs

at cross purposes to the need to minimize data movement. Models that make use of functional semantics

Programming Abstractions for Data Locality

4

---