Projects

C3: Compilation and Code Generation for Invasive Programs

Principal Investigators:

Prof. G. Snelting, Prof. J. Teich

Scientific Researchers:

M. Braun, S. Buchwald, Jorge A. Echavarria, A. Fried, Dr. F. Hannig, M. Mohr, É. R. Sousa, Dr. A. Tanase, 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 will be the quest for (higher) predictability of non-functional aspects of invasive parallel program execution, i.e. performance, fault tolerance, and security. While predictable performance in terms of latency and throughput shall be proven for loop nests compiled to TCPA targets, we will also investigate compiler support to improve the predictability of invasive software and hardware in general. The major research topics in the second phase include (a) compilation methods exploiting different fault tolerance schemes for loops, (b) multi-level symbolic loop tiling transformations, (c) performance predictability proofs for TCPAs, (d) approaches for automatic program invasification, (e) optimisations tailored to invasive architectures, and (f) information flow control for invasive applications.

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 II, a major focus of research of this central project on invasive program compilation will be driven by the quest for (higher) predictability of non-functional aspects of invasive parallel program execution, i.e. performance, fault tolerance, and security. While predictable performance in terms of latency and throughput shall be proven for loop nests compiled to TCPA targets, we will also investigate compiler support to improve the predictability of invasive system software and hardware. Moreover, the trusted handling of sensitive application data using information flow control will be a focus for RISC targets. Due to a growing vulnerability of complex MPSoC designs to failures, compilation methods exploiting fault tolerance schemes such as dual (DMR) and triple modular (TMR) redundancy for loop programs shall also be exploited systematically for TCPA targets. This poses also challenges to support such schemes on demand by dynamic i-Core reconfiguration and for compilation with a fault tolerance option.

Additionally, our research efforts are guided by the quest for productivity and automation. Automatic program invasification shall reduce programmer burden by automatically identifying and transforming program parts that benefit from resource invasion. Moreover, by devising compiler optimisations tailored to invasive architectures, we will facilitate the development of efficient invasive programs. Concerning TCPA targets, balance loop iterations to an unknown number symbolic multi-level tiling schemes must balance memory and communication requirements. As such, symbolic multi-level tiling schemes shall be investigated and automated as compiler transformations. Finally, as a requirement of massively-parallel loop processing on TCPAs, compilation aids for the control of data transport to and from an array tile need to be investigated.

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

X10 front end

The existing X10 compiler has two back ends: A Java back end and a C++ back end. We added another back end that targets our compiler's intermediate representation FIRM without involving a high-level intermediate language. This is the first X10 back end that does not rely on a full-blown post compiler for code generation. Consequently, we need to handle some high-level constructs, such as generic classes and methods, in the compiler itself instead of leaving the handling to a post compiler. Additionally, we created the library lib00, which eases the FIRM construction for object-oriented language features as, for example, dynamic dispatch. FIRM is based on static single assignment (SSA) form. For the construction of SSA form, the most efficient algorithms require a non-SSA intermediate representation that features a control flow graph (CFG). In contrast, we wanted to create FIRM directly from X10's abstract syntax tree (AST). Thus, we developed a novel SSA construction algorithm that directly constructs an intermediate representation in SSA form. We have shown that this optimisation leads to minimal SSA form for programs with reducible control flow. Since our algorithm constructs pruned SSA form by design, we end up with minimal and pruned SSA form.

LoopInvader front end

Loop programs play an important role in parallel computing in general and invasive computing in particular. In order to exploit invasive computing concepts at the level of loop programs and massively-parallel architectures such as TCPAs as investigated in Project B2, a compiler tool called LoopInvader (see the above compiler overview picture) has been developed. Its front end extracts potential invasive loop candidates from a given X10 program. Here, an interface was defined based on the X10 abstract syntax tree (AST) to extract X10 loop candidates and convert these automatically into a single assignment form including the static dependence analysis of array references. This step is necessary to reveal the entire data parallelism hidden in a loop nest for subsequent mapping to massively-parallel processor array targets, such as TCPAs. The challenge posed by the principles of invasive computing is that the size of the available processor array region is not known at compile time. The major theoretic results and achievements of a required theory and transformations for symbolic loop parallelisation are reported later.

SPARC back end

The general purpose cores found in our investigated invasive computing platform have a SPARC instruction set, optionally with i-Core extensions. There will be variants with and without floating-point support. To this end, a new back end has been developed using the existing infrastructure in libFIRM. This involved creating code selection strategies, and handling the SPARC calling convention, which employs register windows. Register allocation and scheduling is performed with the generic libFIRM infrastructure. We further developed peephole optimisations and special code generation phases to fill delay slots and respect the stack alignment requirements of the application binary interface. To handle software floating-point, a new pass has been created that replaces arithmetic operations with calls to an emulating library. We are in the process of extending our register allocator to support aliased floating-point registers as found in the SPARC architecture. The back end has matured to a point where efficient code is generated. Furthermore, the back end now passes a full run of the SPEC CPU2000 benchmark suite with the large input data sets.

The collaboration with Project B1 allowed us to explore extended instruction sets. Our previous work shows that register allocation for programs in SSA form leads to an optimal assignment of registers. Translating out of SSA form, however, requires parallel copy constructs, which are traditionally implemented by sequences of register-register copy and exchange instructions. Minimising the number of needed parallel copies is an NP-hard problem. This means that in practice, the number of remaining parallel copies depends on the register allocation quality. Hence, fast register allocators, e.g. allocators suitable for just-in-time compilation scenarios, produce a large number of parallel copy operations. To reduce the cost of implementing parallel copies, we developed an instruction set extension comprising additional instructions to permute the register contents within a single cycle. The extended instruction set has been defined in its final form in collaboration with Project B1. We have developed an efficient compilation approach that is able to generate good code for all practically relevant parallel copy constructs using the additional instructions. Multiple register allocators that were already implemented have been adapted to support the generation of permutation instructions. Furthermore, we have modified a SPARC emulator to support the additional instructions in order to get accurate measurements on the number of saved instructions. Together with the FPGA-based hardware implementation provided by Project B1, we were able to conduct benchmarks using real programs.

Code generation for invasive constructs

Besides supporting a range of architectures including SPARC, TCPA, and the i-Core, a compiler targeting invasive computing platforms has to use the iRTSS operating system and leverage the iNoC for DMA transfers. We tackled these requirements by writing a custom back end for the existing X10 compiler front end and called this extended X10 front end iX10. The programs analysed by this front end are transformed into the FIRM intermediate representation to facilitate generating SPARC code and supporting the i-Core extensions. This transformation also converts parallel programming constructs like async, at, invade, and infect into the lower level APIs provided by the iRTSS. Since the X10 run-time library partly implements functionality that is already provided by the iRTSS, we adapted the X10 run-time library to use the iRTSS API instead. The compiler correctly transforms X10 programs with all modern language features, such as closures, generic code, parallelisation, and synchronisation through async, at, and finish. We also support serialisation and deserialisation, which is needed for inter-tile communication via at.

Compiler validation and demonstrator activities

All three newly developed components described in the previous sections, i.e. (1) the X10 front end, (2) the SPARC back end, and (3) the mapping of X10 run-time calls to OctoPOS (developed in Project C1) interfaces, were extensively tested both in isolation (where possible) and in conjunction with each other. For testing the compiler parts in isolation, we reused existing infrastructure and took care to only change one parameter at a time. To ensure the valid transformation of X10 to FIRM in our X10 front end, we implemented the X10 runtime using POSIX interfaces. This makes it possible to transform the X10 AST into FIRM, use libFIRM's existing and well-tested IA32 back end to generate code and run the generated executables on standard hardware. As input programs, we assembled a test suite currently consisting of 150 X10 programs. Additionally, we used the official X10 compiler test suite provided by IBM that contains over 1000 test cases. Furthermore, we also tested the complete compiler chain involving all components. To this end, we compiled all X10 tests contained in our test suite to SPARC executables using a SPARC version of the OctoPOS variant of our X10 runtime as well as the SPARC version of OctoPOS. All executables were successfully run on the CHIPit demonstrator platform as well as on a Xilinx XUPV5 FPGA board. In both cases, we used the invasive hardware design that was current at that point. Additionally, a few selected test cases from other projects, including a parallel matrix multiplication provided by Project D3, were successfully executed on the CHIPit demonstrator platform. We have also adapted the invasive computing paradigm to other tiled architectures, namely Tilera's TILEPro64 and Intel's Single-Chip Cloud Computer which have 64 and 48 processors, respectively. For porting our resource-aware programming concepts, proper software libraries have been designed that provide support for the basic invasive language constructs. We studied the overheads of invasion on these architectures and analysed the trade-offs of centralised versus distributed resource management approaches. Moreover, computationally intensive loop kernels stemming from Project D1, i.e. optical flow and Harris corner detection algorithms were successfully mapped onto TCPAs in collaboration with Project D1.

Symbolic loop parallelisation

We investigated fundamental compiler transformations for the parallel execution of invasive loop programs on processor arrays such as TCPAs. A simplified drawing of a TCPA, developed in Project B2, with 24 processor elements (PEs) is sketched in the center of the figure below. Here, the highlighted rectangular areas denote three applications running simultaneously on the array.

In this realm, we proposed and formalised for the first time symbolic tiling as an automatic program transformation for symbolic parallelisation of nested loop programs with uniform data dependencies. 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 until run time. Indeed, tiling is needed as an important compiler transformation that partitions the iteration space of a given loop nest into typically congruent and parallelepiped or orthotope shapes. In that case, the size and shape of each tile may be described by a so-called tiling matrix P. Often, the iterations of each tile are uniquely assigned to one processor each. Accordingly, the tile size is typically chosen statically to reflect the number of available processors in the architecture. Then, all intra-tile iterations need to be executed by one processor sequentially (or in a pipelined manner with overlapped execution of consecutive iterations (software pipelining)). For illustration, consider the nested loop program on the left hand side presented in the illustration below. As can be seen, tiling increases the depth of the loop nest of our example from a double-nested loop to a quad-nested loop.

Loop parallelisation for tightly coupled processor arrays (TCPAs)

In (a), a 2D invasive TCPA is shown where three concurrently running applications (shown by different
colours) have invaded the set of processing elements. In (b), a statically tiled code is shown that matches
a 4 × 2 processor array. In (c), symbolically tiled code is shown. This code may be subsequently mapped
onto an arbitrarily-sized array configuration later by symbolic scheduling of the computations of the parameterised iteration spaces.

The figure above shows on the right hand side the resulting code of a loop whose iteration space has been statically tiled into 4 × 2 tiles corresponding to a mapping onto a 4 × 2 processor array region within the TCPA (in this example represented by the orange region). After tiling, the outer loops iterate over the iterations contained in a tile and the inner loops iterate over the origins of tiles. However, when the number of available processors in the array is not known at compile time, a new approach needs to be considered. Here, we have studied the idea of symbolic loop tiling: We consider a tiling transformation to be specified by a parametric tiling matrix P = diag(p_i). If for example, at run time, a processor array of size n × m has been successfully invaded, a tiling of size p₁ = ⌈N/n⌉, p₂ = ⌈M/m⌉ would be needed to map the loop program onto the considered processor array. An example of a symbolically tiled loop nest and the corresponding symbolic tiling matrix P is shown in the above picture on the right hand side.

Whereas tiling is used mainly for the assignment of iterations to processors, a breakthrough was achieved in this project to also be able to symbolically schedule nested loop programs in a latency-optimal way while satisfying data dependencies and resource constraints. A loop schedule assigns each loop iteration a start time of execution. A loop schedule is called symbolic if it may contain expressions involving iteration vectors and tile size parameters. Finally, a symbolic schedule vector is called feasible if it satisfies all data dependencies of the tiled algorithm. In the case of symbolic tiling, unfortunately, it is not possible to solve the problem of finding both a latency optimising inter-tile and intra-tile schedule vector in closed form because of products of tile parameters in corresponding scheduling constraints. Similar products of parameters and variables appear in the objective function. However, in this project, for the first time we proved that is possible to solve such a problem by using a four-step analytical methodology. At run time, only a few latency expressions must be evaluated, and the corresponding minimal latency schedule then uniquely determines which of the statically determined processor program configurations need to be loaded and executed on the invaded array.

Our symbolic loop parallelisation theory has been presented at ASAP 2013 (entitled: Symbolic Parallelization of Loop Programs for Massively Parallel Processor Arrays) and has received the best paper award among more than 150 submissions.

Code generation for TCPAs

In order to map loop programs onto TCPAs, appropriate assembly code generation techniques for the processors based on a given tiling and scheduling of iterations are necessary. Here, in close collaboration with Project B2, we tackled the problem of efficient yet compact code generation for massively-parallel processor arrays that are typically dominated by an abundance of computation resources at the cost of lacking memory resources. This is completely opposite to standard multiprocessors where more than 70% of the MPSoC chip area may be dominated by dispatch units, register files, and one or two levels of instruction and data caches. Therefore, due to the constraint of tiny instruction memories available in each of the hundreds of processors in a TCPA, we proposed novel code generation techniques, which are problem-size independent in (a) the loop bounds as well as in (b) the size of the available processor array. Based on a given tiling and schedule of instructions for the whole loop program, so-called processor classes are distinguished first. Each processor belonging to the same class will obtain the same binary program to execute. So, the number of different programs to generate may be reduced for many applications to a constant number. Subsequently, instead of generating flat code instruction by instruction for each processor, looping of repetitive code sequences is exploited and represented in a special data structure called program block control graph. Finally, for preserving a given schedule of instructions, zero-loop overhead techniques are proposed such that the repetitive execution of each unique program block does not cause any extra cycles.

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

Publications