Projects

A1: Basics of Invasive Computing

Principal Investigators:

Prof. G. Snelting, Prof. J. Teich

Scientific Researchers:

K. Esper, Dr. J. Falk, PD Dr. F. Hannig, B. Pourmohseni, M. Wagner, Dr. S. Wildermann

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.

In the second funding phase, we exploited the effect of invasions to isolate applications from each other on future massively parallel processor systems to establish *-predictability. With this term, we understand the predictability of several non-functional properties of execution such as timeliness, security and fault tolerance on demand of a program or only for individual sections thereof. For this purpose, we introduced so-called requirements into the language. Such non-functional requirements are of ultimate importance for the applicability of multicore technology in the vast and growing market of embedded systems.

A strict isolation of resources, although allowing us to give even worst-case execution time guarantees for many applications on invasive computing architectures, may not always be desired because of over-provisioning resources or under-utilising them at times. One reason being the remaining variability of the above aspects also due to the uncertainty of input or the system itself, e.g. a power manager that may independently change the processor frequencies at any time. In the third funding phase, one of the main topics of investigation is run-time requirement enforcement (RRE) of non-functional properties of program execution. For this purpose, we will investigate (a) centralised vs. distributed run-time requirement enforcement, (b) strict vs. loose run-time requirement enforcement, (c) verification of run-time properties, and (d) formalising the X10 memory mode.

Synopsis

The static invasion of resources may provide desired bounded execution qualities (predictability), as was investigated in Phase II. Yet the price may still be high, as isolation alone may not reduce undesired jitters, e.g. in execution times, typically caused by uncertainty stemming from unknown or varying input and environmental execution conditions. Consequently, resources may be underutilised if claims are composed to reflect the worst case of input and environment. As a remedy, we want to investigate by which techniques requirements may be enforced at run time. This focal CRC topic is called Run-Time Requirement Enforcement (RRE).

Here, Project A1 will investigate novel centralised as well as distributed RRE techniques that will be based on sub-corridor partitioning. In the first, a central control instance shall be generated to enforce the desired non-functional qualities of execution based on statically analysed knowledge about the criticality and thus importance of certain design decisions such as computational requirements of an actor, etc. In the latter, requirement ranges shall be identified and statically partitioned into intervals called corridors. Moreover, in the case of hard requirements, techniques for strict enforcement shall be investigated. Here, sound formal proof techniques must be derived at compile time that an RRE technique will control a given program quality (e.g. by DVFS) to never leave a given requirement corridor.

An example of such a requirement to be verified is a hard execution deadline of an application graph as specified in ActorX10. Other important non-functional properties for which bounds shall be formally proven include memory requirements (tile-local and global memory), communication times, and load. In the case of soft requirements, temporal violations might be tolerable. Here, multi-objective control theory with the control laws derived from an analysis of the importances of tasks and their mapping on the quality under control may provide efficient enforcement solutions. Also, statistical analysis techniques might be candidates for loose requirement enforcement.

Approach

It might be difficult or even impossible for a programmer to specify by hand constraints on number and type of resources in order to achieve the desired quality of program execution, for example worst-case execution time. We therefore allow the programmer to specify requirements on execution qualities rather than constraints on resources. These requirements, such as a timing requirement of a maximal latency bound or a throughput requirement will be analysed at design time. We distinguish between soft and hard requirements. Hard requirements must never be violated for whatever reason. Whereas, soft requirements shall be satisfied most of the times, but their occasional violation may still be tolerated.

For predictable multicore program execution, we proposed a design flow which automatically determines claim constraints that will fulfil a set of given requirements, and then replaces the requirement pragmas in the source code by the respective set of claim constraints. The flow developed in cooperation with Project A4 implements a hybrid application mapping (HAM) approach for achieving run-time predictability by combining design-time analysis of application mappings with their run-time management as shown in the figure below.

Proposed hybrid application mapping.

Previous approaches to hybrid mapping focused on computation resources and either ignored communication details or made significantly simplifying assumptions like unlimited bandwidth or exclusive usage. But, actual manycore systems consist of constrained and shared computation and communication resources where the run-time decision of whether a feasible application binding on a set of preoccupied resources exists or not is an NP-complete problem. As a remedy, our hybrid application mapping approach considers constrained shared communication and computation resources. The developed methodology summarised in figure above consists of (a) a design space exploration (DSE) coupled with a formal performance analysis. This delivers several resource reservation configurations, so-called operating points, with verified satisfaction of the bounds as specified by requirements. The set of operating points is then transformed to (b) an efficient intermediate representation which can be expressed by constraints. This representation is passed to the run-time management by the invade-call. Assembling a claim adhering to these constraints is then the task of (c) run-time resource reservation (claim search and assignment).

In the area of language design and implementation, an actor-based language called ActorX10 has been defined on top of X10 in cooperation with Project A4 and Project C2. This actor-based description of applications with data-dependent tasks and requiring not only one or multiple cores, but different types of resources and also guaranteed communication bandwidth on NoC and to memory when executing, will also be a foundation to start our research on run-time requirement enforcement (RRE).

X10 provides the concept of a place as a shared memory domain within the language. Influenced from MPI, the major distributed HPC paradigm, X10 places were assumed static in number during the run time of a program. This assumption does not hold for programs invading and retreating from resources. Already in the first funding phase, we adapted the runtime to handle a changing number of places by adapting X10's runtime and standard library. In the second funding phase, we went further and changed language semantics: Each claim has its own view of places. This provides isolation between claims, which usually correspond with a notion of application. In X10, shared memory can be used for communication on the same tile. Between tiles, claims provide a method similar to infect. This provides language-level isolation between claims, which is the weakest level defined by Project C5, but the goal here is primarily to improve debugging and maintenance, not security.

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

Publications