Projects

A1: Basics of Invasive Computing

Principal Investigators:

Prof. Teich, Prof. Snelting

Scientific Researchers:

Andreas Weichlsgartner, Stefan Wildermann, Andreas Zwinkau

Abstract

Investigated are the basics of invasion, that is, the fundamental programming model for invasive and resource-aware computation. This includes a) the definition of required functionality, and b) the development of a mathematical model for quantitative performance, resource efficiency (utilisation) and overhead analysis for different types of invasive architecture targets.
Investigated will also be a programming notation for invasive programming: Here, c) the syntax, semantics and type system of an abstract invasive core language is defined, which will be the basis for d) the definition of a concrete invasive language and its system interfaces.

Synopsis

Subproject A1 is divided into two major fields of research. Whereas the first area is devoted to basic concepts, features and analysis of invasive programs in general and independent of a language implementation and target architecture, the second part defines language support for invasive programming concepts. The individual questions addressed are summarised as follows:

1. The basic concepts of invasion must be tackled and corresponding features and parameters defined. The fundamental system model and programming model for invasion and resource-aware computation must be developed and exercised on various preliminary examples on paper. Different levels of abstraction for invasive processes must be defined, such as static candidates, dynamic instances and executable incarnations (so-called "i-lets").
2. A mathematical model for performance and overhead analysis shall be developed. Dynamic decisions about invasion will depend on data distribution, load balancing and the dynamic state of resources. The definition of corresponding overhead functions for resource utilisation and efficiency is important to show if invasive programming allows to achieve utilisation close to 100%. The overhead functions can be used in the design of invasive algorithms and help to dynamically decide if and where invasion should happen.
3. An abstract core language, which incorporates the insights from 1.) will be defined. This abstract language will be the basis for a concrete language and its interfaces. The concrete language (which is to be built on top of a host language such as X10) must exploit modern language theory, respect the above-mentioned abstraction levels, and provide interfaces to dynamic resource parameters as well as to existing technology for parallel programming. It should utilise generic mechanisms, instead of introducing lots of low-level, adhoc syntactic constructs.
4. The concrete language must be exercised on real algorithms and problems. Expressiveness and usability must be evaluated for all different types of potential target architectures ranging from tightly- over loosely-coupled Multi-Processor System-on-a-Chip (MPSoC) architectures to high-performance computing (HPC) machines.
5. Later, an operational semantics of the core language, together with a resource-aware type system will be defined. This allows to prove type safety and is likely to prove other fundamental properties such as resource bounds of the dynamic computational structure, as well.

Approach

Consider the following program fragment, which shows the three basic constructs invade, infect, and retreat:

val claim = Claim.invade( constraints );
claim.infect( ilet );
claim.retreat();


The static method Claim.invade takes constraints and returns a claim object, which represents the allocated resources, a set of processing elements (PEs). A claim provides an infect method to distribute computations across the PEs. The argument of infect is an i-let object, which contains the code to execute together with initial data. The infect call blocks the program, until all i-let computations finish. Afterwards, the retreat method frees all resources within a claim, such that the claim is empty. While such a claim can still be infected, this would do nothing. Now consider the ilet variable of the example above. It could be declared as follows:

val ilet = (id: IncarnationID ) => {
Console.OUT.println("Hello! ("+id+")");
};

The first class of constraints we identified were so-called predicate constraints, which specify a predicate for processing elements. An application might require the demanded processing elements to (1) be under a certain load, (2) be under a certain temperature, (3) have an FPU, (4) have certain amount of local memory, (5) have a scratch pad memory, (6) be of a certain type, (7) have a certain cache size, (8) be migratable, or (9) not be scheduled preemptively. Such constraints impose a simple filter operation over the set of available processing elements within an invade operation. The second class of constraints are order constraints, which provide an ordering of processing elements according to (1) load, (2) temperature, (3) memory, or (4) speed. Using these constraints an application can communicate its preferences, whether it is IO- or CPU-bound. By giving multiple of these constraints, the programmer can impose a secondary or tertiary ordering.

Constraint hierarchy for invasive computing

The third class of constraints are set constraints, as they specify conditions for a set of processing elements as a whole. The most common constraint is the (1) quantity of processing elements to be claimed, but there are also partition constraints, (2) a certain physical layout of the PEs, (3) place coherence, which means that the PEs have shared memory, (4) type homogeneity, in terms of the instruction set architecture, (5) cache type homogeneity.
Additionally, there are the two operators AND and OR to combine constraints. At last, the programmer can give nonbinding hints, which can be used to hand complex information like efficiency curves of parameters to the run-time system of the underlying MPSoC architecture. These constraints are implemented as a class hierarchy as shown in Figure above, which is available to the programmer. The constraints above form the leafs of the hierarchy tree and abstract classes, drawn as boxes, partition the tree into categories.

Publications