Programming abstractions for

4.5. RESEARCH PLAN

4.5

Research Plan

The notion of a separation of concerns around expressing semantics and exerting control, and the taxonomy

of data and execution policy controls offer a clearer framework in which to fit current and ongoing research.

Some relevant promising research areas are then

• Identify where and how the type system should be augmented in standard languages like C++ to

better convey semantics, for example for multidimensional arrays

• Extend the reflection capabilities of standard languages, to ease programmer effort and to remove

barriers to freedom of abstraction. See below for more detail.

• Experiment with and promote the use of libraries that enable the separation of semantic expression

from target-specific implementations of data and execution policy controls such as iterators.

• Identify and close gaps in the completeness of data and execution policy controls in existing embedded

DSLs.

• Identifying other language extensions needed to facilitate data layout abstractions such as tiling.

As we proceed along the course of the research plan suggested above, the following questions need to be

evaluated:

• Are some frameworks for providing data and execution policy controls limited in their portability

across architectures? Where performance portability and generality is sacrificed, is that specialization

worthwhile? Do those specializations tend to be domain specific?

• Is there a minimal set of data or execution policy controls that are found to be of highest impact, that

we can recommend to be covered by most all data layout optimization frameworks?

• Can we generalize our formulations of costs for various optimization alternatives into a more general

data model that we can use to reason about locality?

• As systems mature, is there a natural progression from total control by a user, to select control only

when heuristics aren’t good enough, to default heuristics that are good enough for most users? Do our

frameworks provide an opportunity to offer users the full range of ease of use through automation to

total control and visibility?

• Which data and execution policy controls are best implemented by each of the user, a static compiler,

or a dynamic runtime?

• Identifying other language extensions needed to facilitate data layout abstractions

Augmenting C++ reflection capabilities is a key enabler for some forms of data layout abstraction.

Since the C++ language committe is showing interest in this, there is an opportunity to drive proposals for

solutions in this area. Better reflection support can make template-based techniques more tractable, and

can enable embedded DSLs.

• Template-based techniques can be used to introduce an abstraction that maps a programmer-focused

logical layout to a performant physical storage layout. But since a complete mapping is bidirectional,

the designer of the template-based solution has to create a dual mapping, which is laborious and error

prone. This is relevant to Arrow Street and SIMD Building Blocks, mentioned above. The introspection

aspect of reflection allows walking struct or class members and references to infer the reverse mapping,

so that this can be performed by an automated system instead of manually. This could significantly

enable ease of use.

• Language rules can inhibit the freedom of expression at multiple abstraction layers. For example,

suppose an embedded DSL is used to express a data layout abstraction. One might think that a source

to source translator could be used to map from the DSL to C/C++ code, and the compiler could remain

Programming Abstractions for Data Locality

22

---

4.5. RESEARCH PLAN

free to create an alternate physical storage layout that’s more performant. Unfortunately, C and C++

expose physical data layout, establishing a contract with the programmer that limits a compiler’s

ability to modify the data layout without changing the semantics. The source to source translator

can’t “reach around” the C/C++ front end in order to directly modify the compiler’s internal abstract

syntax tree (AST). But C++ extensions to provide the intercession aspect of reflection could enable

direct modification of the AST.

Programming Abstractions for Data Locality

23

---

Chapter 5

Language and Compiler Support for Data

Locality

The concept of locality has not yet become a first-class citizen in general-purpose programming languages. As

a result, although application programmers are often confronted with the necessity of restructuring program

codes to better exploit locality inherent in their algorithms, even a simple simulation code can become highly

non-intuitive, difficult to maintain, and non-portable across diverse architectures.

The overarching vision of this workshop is to solve these issues by presenting application programmers

with proper abstractions for expressing locality. In this chapter, we explore data locality management in the

context of parallel programming languages and compiler technologies More specifically, we discuss language

concepts for data locality, their delivery in general-purpose languages, domain-specific languages and active

libraries, and the compiler technology to support them.

Language-based solutions may come in the form of new, general-purpose parallel programming lan-

guages. In addition to supporting intuitive syntax, language-based approaches enable ambitious compilation

techniques, sophisticated use of type systems, and compile-time checking of important program properties.

Language concepts for locality can also be delivered within existing languages, supported in libraries, through

metaprogramming in C++, and in “active libraries” with library-specific analysis and optimizations.

Locality is about data, and locality abstractions often refer to abstract data types. Multidimensional

arrays are a crucial starting point. Many more complex domains can be characterized by the abstract,

distributed data structures on which parallel computation occurs. Domain-specific tools are often focused

on particular data structures—graphs, meshes, octrees, structured adaptive-mesh multigrids, etc. While

Chapter 4 tackles particular data structures, in this chapter we look at how to build tools to support

programmers who build such abstractions.

Locality is also about affinity—the placement of computations (e.g., tasks) relative to the data they

access. Dominant HPC programming models have typically been based on long-running tasks executing in

fixed locations fetching remote data. Emerging architectures may also compel us to pursue languages in

which computations are moved to the data they wish to access. To implement such models, languages will

need to also support the creation of remote tasks or activities.

The following terms are used in this chapter:

• Active library: a library which comes with a mechanism for delivering library-specific optimizations [89].

Active library technologies differ in how this is achieved - examples include template metaprogramming

in C++, Lightweight Modular Staging in Scala [81], source-to-source transformation (for example using

tools like ROSE [94]), and run-time code generation, driven either by delayed evaluation of library

calls [82], or explicit run-time construction of problem representations or data flow graphs.

• Embedded domain-specific language: a technique for delivering a language-based solution within a

host, general-purpose language [46]. Active libraries often achieve this to some extent, commonly by

overloading to capture expression structure. Truly syntactic embedding is also possible with more

ambitious tool support [32].

24

---