Projects

C3: Compilation and Code Generation for Invasive Programs

Principal Investigators:

Prof. G. Snelting, Prof. J. Teich

Scientific Researchers:

Jorge A. Echavarria, A. Fried, S. Graf, PD Dr. F. Hannig, M. Witterauf

Abstract

Project C3 considers compilation and code generation as well as program transformation and optimisation techniques for non-regular (procedural) code as well as for task-level and regularly-structured (i.e. loop-level) code.

In the first funding phase, a compiler for the concrete language defined in Project A1 has been developed. The compiler is based on an existing X10 compiler, but has been extended with new transformation phases to support tightly coupled processor arrays (TCPAs) as well as SPARC processors and i-Cores through libFIRM. For TCPAs, the loop compiler LoopInvader was developed that detects and extracts nested loop programs from a given X10 input program and transforms these loop nests into single assignment code. A breakthrough in symbolic compilation techniques was achieved here by being able to determine an optimal mapping of loop iterations to processors as well as their latency-optimal scheduling in dependence of an unknown number of available processors (claim size). For RISC cores, a new transformation phase builds the intermediate representation FIRM and then generates code using a newly developed SPARC back end. Additionally, an invasive X10 run-time library has been created to efficiently map X10 language constructs to operating system interfaces.

In the second funding phase, a major focus of research has been the quest for (higher) predictability of non-functional aspects of invasive parallel program execution, i.e. performance, fault tolerance, and security. Based on the pioneering work from the first phase, we investigated new compilation techniques in the polyhedron model for the resource-adaptive parallel execution of invasive loop programs on processor arrays. Furthermore, in order to counter the increasing proneness to errors of modern, complex systems we developed new fault tolerance measures. Here, we proposed new techniques that leverage the advantages of invasive computing to implement fault tolerance on TCPAs adaptively and on demand. Regarding the code generation for RISC targets, we focused on verification and optimisation, both on the level of the intermediate representation (IR) and in the language runtime. Furthermore, we proposed a novel technique to avoid serialization when copying pointered data structures between shared memory partitions on non-cache-coherent architectures.

In the third funding phase, the major focus will be run-time enforcement of multiple non-functional execution qualities such as user-specified performance and energy corridors. The major research topics in the second phase include (a) constant latency/throughput loop processing, (b) approximate loop processing including language extensions to specify imprecise loop variables, (c) a symbolic code generator for TCPA targets shall be developed that will support the symbolic loop parallelisation techniques developed in the previous funding phases, (d) compiler optimisations for the i-Core, (e) optimisations for FPGAs, (f) discovery of invasive programming patterns.

Synopsis

This project investigates compilation techniques for invasive computing architectures. Its central role is the development of a compiler framework for code generation as well as program transformations and optimisations for a wide range of heterogeneous invasive architectures, including RISC cores, TCPAs (tightly coupled processor arrays), and i-Core reconfigurable processors.

In Phase III, a major focus of research will be the theme of run-time enforcement of multiple non-functional execution qualities, such as user-specified performance and energy corridors. It is well known that in many programs, a considerable portion of execution time is spent in the processing of inner loops. To enforce any non-functional requirements on an application at run time therefore heavily implies the need for run-time requirement enforcement techniques specific to loops. Loops, however, inherently add uncertainty to an application because their bounds are often parameters, that means unknown until run time. Our goal is to develop compiler techniques that allow for the run-time enforcement of execution qualities such as latency bounds of loop execution on TCPAs under the uncertainty of loop bounds that become known only at run time. Here, we plan to investigate mainly two particular techniques: compilation of constant-latency loops and approximate loop processing. While constant-latency loops facilitate run-time enforcement of latency requirements by splitting a problem into smaller, more fine-grained loops, approximate loop processing trades off the accuracy of results for the sake of improved other non-functional qualities.

Additionally, our research focuses on symbolic code generation. So far in our research, we developed theories and theorems for automatic symbolic parallelisation of loop programs by determining latency-minimal symbolic schedules. But how can we generate machine code according to a symbolic schedule where the schedule of iterations of a loop nest materialises only at run time? This yet unanswered, but important question poses unique challenges because TCPAs by design have only highly limited instruction memories and run-time compilation is not feasible. We therefore aim to implement a symbolic code generation back end, which emits symbolic code chunks that will be composed on-the-fly at the time of loading the programs and in a way that minimises any run-time overhead and code size per processing element.

Overview of compiler framework

Overview of the compiler framework for invasive computing. The front end is based on the X10 compiler, which is open source. The back end for SPARC targets is generated using the FIRM compiler infrastructure. The back end for invasive parallel loop codes to run on tightly coupled processor arrays (TCPAs) is provided by the tool LoopInvader.

Approach

Symbolic loop Parallelization

We investigated new compilation techniques in the polyhedron model for the resource-adaptive parallel execution of invasive loop programs on processor arrays. The goal was to find optimal symbolic assignments and schedules of loop iterations at compile time for an array of processors where the number of available cores is only known at run time. This symbolic loop parallelisation step is essential for invasive programming on MPSoCs, because the claimed region of processors, whose shape and size determines the forms of tiles during parallelisation, is not known at compile time. Furthermore, it avoids just-in-time compilation as well as the need of a compiler resident on the MPSoC. Based on the pioneering work on symbolic loop parallelisation of the previous phase, we considered extensions towards locally parallel, globally sequential (LPGS) schemes. Here, invasive loop nests are mapped onto a processor array of unknown size at compile time while being independent of the problem size. The loop iterations within a tile are assigned to one processor each for parallel execution, yet the tiles are started to be executed in a sequential order. We proved analytically that it is possible to derive such parametrised LPGS schedules statically by using a mixed compile-/run-time approach. However, while satisfying memory requirements, the resulting schedules may result in I/O requirements that exceed the capacities of the processor array architecture. To match the required I/O-capacities and local memory sizes at a fine scale, we proposed a symbolic multi-level parallelisation approach that balances necessary I/O-bandwidth and memory size to fit a given TCPA architecture.

Iteration space of a 2D loop nest. Each node represents an iteration of the loop program. Each directed edge represents a data dependence between two iterations. (b) Iteration space hierarchically and symbolically tiled on 2 levels.

This is demonstrated in the figure above, where an iteration space of a 2D loop nest is hierarchically and symbolically tiled on 2 levels, represented by the gray and blue tiles, respectively. Next, in order to assign to each iteration a start time, we analytically proved that it is possible to derive a scheduling scheme that assigns start times to iterations within tiles that are scheduled sequentially on the first and last level and parallel start times to all tile origins on all the other levels.

Fault-tolerant loop processing

Since the feature sizes of silicon devices have continued to shrink, it is imperative to counter the increasing proneness to errors of modern, complex systems by applying appropriate fault tolerance measures. In order to achieve this goal, we proposed new techniques that leverage the advantages of invasive computing to implement fault tolerance on TCPAs (as investigated in Project B2) adaptively and on demand. Here, we have presented a compile-time transformation that introduces modular redundancy into a loop program to protect it against soft errors.

Possible voting schemes for TMR with voting placement (a) for every loop iteration (immediate voting), (b) at the border of each PE's iteration space (early voting), and (c) at the border of the array (late voting). The replicated iteration space of a one-dimensional loop nest is also shown. The coloured edges represent the extra dependencies introduced by voting: red edges show the propagation of the voting results, green and brown edges show the propagation of results from the first and third replica to the second replica where voting on them takes place.

The above figure illustrates our approach, where an invasive loop application claims three linear array replicas (shown in different colours) in order to implement a TMR scheme. It uses the abundant number of processing elements (PEs) within a TCPA to claim not only one region of a processor array, but instead two (for double modular redundancy (DMR)) or three (for triple modular redundancy (TMR)) contiguous neighbouring regions of PEs. Next,voting operations into the replicated loop program. Here, we proposed three different variants to detect, respectively correct errors: for each variable to be protected, (a) in every loop iteration (immediate voting), (b) once per PE (early voting), and (c) at the border of the allocated processor array region (late voting). Each of these variants exhibits a different trade-off in terms of latency (time to finish computation) and error detection latency (EDL) (time to detect a fault).

Integrated Code Generation for FPGAs

The elements of a Special Instruction: The Address Generation Units stream data from and to main memory in regular patterns. The computation to be done on this data is compiled to a hardware description language, which is then synthesised into the i-Core's reconfigurable fabric.

We have already investigated accelerating applications through the use of Special Instructions (SIs) in the previous funding phases, specifically the i-Core developed in Project B1. The basic idea behind SIs is to identify a particular computation that could accelerate an application if it were (partly) implemented in hardware. The desired functionality is then implemented in an SI by specifying a configuration for the i-Core's FPGA fabrics, and a micro-program that connects the fabrics and streams data from and to main memory. From the point of view of the application, the SI appears as an additional assembly instruction, which invokes the micro-program and executes the specified computation on the i-Core. At the DFG assessment of Phase II, we were able to demonstrate the benefit of SIs in a simulation of wave propagation.

However, efficient SIs currently still have to be written separately in a hardware description language. This is because the usual compiler optimizations assume a classical CPU as their target. Especially in the embedded sector, this is an increasingly unrealistic assumption. We will therefore investigate compiler optimizations specific to FPGA targets, which will enable us to compile the same high-level source code to fast software as well as efficient virtual hardware.

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

Publications