Projects

A1: Basics of Invasive Computing

Principal Investigators:

Prof. J. Teich, Prof. G. Snelting, Dr. S. Wildermann

Scientific Researchers:

M. Braun, Prof. M. Glaß, Dr. J. Falk, B. Pourmohseni, T. Schwarzer, M. Wagner, A. Zwinkau

Abstract

Project A1 investigates the basics of invasion, that is, the fundamental programming model for invasive and resource-aware computation as well as concepts, features and analysis of invasive programs and of run-time management strategies in invasive systems.

In the first funding phase, we investigated the fundamental programming model for invasive and resource-aware computation. Our research was divided into two major areas: The first area was devoted to the basic concepts, features, and analysis of invasive programs. The second area defined the language support for invasive programming concepts. The result of this phase was the invasive programming language InvadeX10 which is based on X10 and offers resource-aware programming and dynamic reservation of processor, memory, and communication bandwidth.

Programs written in InvadeX10 are able to adapt their resource usage and degree of parallelism to the number and types of dynamically available resources, which is affecting functional and non-functional properties of their execution. By enforcing (temporally and spatially) exclusive resource usage, resource conflicts and congestion can be avoided. In the second funding phase, these properties of invasive computing will be used to increase the predictability of program execution – one of the most challenging problems today for the successful introduction of manycore technology in many embedded and often time-, safety-, or security-critical system applications.

Synopsis

Project A1 aims to increase the usability and predictability of invasive programming for different application domains. On the one hand, a generic programming framework will be provided for common invasive programming patterns, e.g. for malleable algorithms or parallel divide-and-conquer algorithms. Main contributions will be realised as extensions to the programming language as well as expansions of theoretical foundations. On the other hand, the research is focused on ways how to increase the predictability and how to guarantee multiple qualities of program execution through invasive computing. To achieve this, we will provide a means for an application programmer to specify a set of non-functional requirements, e.g. with respect to execution time, security, and reliability of application execution. Another point of investigation is the introduction of a more abstract level of the invasive programming language. Here, an actor programming model will be introduced that allows to specify concurrent program segments (actors) which perform parallel data processing based on exchanged messages and data. Invasive programming patterns, actors, and requirements will be subsequently transformed into more low-level InvadeX10 constructs and constraints.

Predictability also requires theoretical foundations concerning the programming language and system analysis techniques. Formal semantics and a memory model for invasive programming are necessary to provide truly predictable behaviour and guarantees such as type safety, cache coherence, or data race freedom. This formalisation will also be used to provide guarantees for resource usage (e.g. bounded resources or upper bounds for parallelism), which are similar to type safety guarantees but based on resource-dependent types and type derivations.

Furthermore, A1 will extend its analysis techniques developed in the first funding phase to prove feasibility, convergence, and optimality of decentralised run-time management strategies also for the (a) multi-objective and (b) heterogeneous case. Particularly, (c) the predictability of certain qualities of execution shall be expressed by additional objectives to be quantified.

Approach

Overview

Above figure gives an overview of the flow for predictable invasive computing. Program analysis and characterisation (Project A4) automatically extract various operating points for program execution from InvadeX10 code which uses the new programming extensions. Via compilation (Project C3), this information is handed to the invasive run-time support system (Project C1) which is based on formally analyzed run-time management strategies to enable feasible and optimized program execution.

Invade X10

The invasive programming language InvadeX10 developed in the first funding phase provides constructs to enable resource-aware computation and serves as the basis for further developments in the second funding phase. 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.

A comprehensive summary of the major achievements of the first funding phase can be found by accessing Project A1 first phase website.

Publications