Projects

C2: Simulative Design Space Exploration

Principal Investigators:

Dr. F. Hannig

Scientific Researchers:

M. Witterauf

Abstract

In the first funding phase, Project C2 developed both techniques and the framework InvadeSIM for the timed functional simulation of invasive resource-aware programs on heterogeneous tiled architectures. This enabled us to gain important insights into the concepts of invasive computing across different platform layers, i.e., modelling of different heterogeneous tiled architectures, invasion strategies (solving of constraint satisfaction problems by agents), and resource-aware application programming. Based on this foundation, in the second funding phase, the main focus of Project C2 is the systematic co-exploration across all these platform layers. Investigated is the systematic co-exploration of optimal architecture configurations and invasion strategies fitting best a given mix of resource-aware applications. The research includes (a) design space exploration techniques based on (semi-)simulative and probabilistic methods, (b) the classification of invasive applications into parallel computing patterns, and (c) modelling the dynamic behaviour of invasive applications.

Synopsis

In the first funding phase, Project C2 investigated novel simulation techniques that enable the validation and variants' exploration of all essential features of invasive computing. It had two major research fields: (a) Timed functional simulation of invasive resource-aware programs and (b) performance evaluation of individual architectures and an integrated simulation methodology to co-simulate different types of invasive architectures. In order to handle the complexity and diversity of the considered architectures as well as different invasive programming, resource management and invasion strategies, new methods for the modularisation and orthogonalisation of these exploration concerns have been developed. Such simulation facilities enabled the optimisation of the concepts of invasive computing across all project areas, especially, without the need to have full hardware or software implementations available. One fundamental development was the timed functional simulation framework InvadeSIM for the simulation of invasive resource-aware programs on heterogeneous tiled architectures. It enables us to gain important insights into the concepts of invasive computing across all different platform layers including architectures, invasion strategies, and applications. Based on this foundation, in the second funding phase, the main focus of Project C2 is the automatic co-exploration across all these platform layers as shown in Figure 1.

Figure 1: Overview of the design space exploration.

More specifically, we intend to investigate important research questions such as: How does an optimal invasive architecture configuration look like for a given set of characteristic applications? And: How to model the inherent dynamic behaviour of resource-aware programs as well as of multiple competing applications? In this realm, we want to study variants of invasive architectures and evaluate them for several application scenarios for multiple objectives (e.g., cost, performance, power, predictability). Furthermore, we want to classify and model invasive applications and sets of them by invasive parallel patterns.

Approach

The main contribution of the first funding phase and the basis for our research goals in the second funding phase is the simulation framework InvadeSIM, which will be explained in the next sections in more detail. The main goal of a timed functional simulation framework is to provide simulation capabilities comprising invasive architecture and run-time simulation for parallel invasive applications written in X10. In order to fulfil these requirements, the simulation platform InvadeSIM has been developed providing (a) a fast simulation approach for hundreds of competing applications on large heterogeneous architectures, (b) allowing the modelling of customised heterogeneous invasive multi-tile architectures, and (c) supporting the simulation of the complete set of X10 language constructs as well as (d) all novel invasive programming constructs such as invade, infect, etc. as provided by the InvadeX10 language extension. As a final result of these goals, we can state that all parts were successfully accomplished. This required a close cooperation with several projects of the TCRC (A1, B5, C1, D1, D3). In the following paragraphs, we will explain our achievements in more detail and relevant additional work that was achieved.

An overview of the developed timed functional simulation platform InvadeSIM, which will be also called simulator in the following, is depicted in Figure 2. The simulator allows to quickly customise an invasive multi-tile architecture to be evaluated by changing a number of parameters such as topology, network parameters, or number of tiles and processor types in each tile. This is denoted as architecture model in Figure 2. Applications using InvadeSIM are written in X10 and may use the InvadeX10 framework for exploiting the invasive command set. This is denoted as application modelling in the figure. The main concepts of the timed functional simulation approach are shown in the centre of the figure. Shown are the core components to simulate several parallel applications on a modelled heterogeneous multi-tile architecture. These contain a novel concept of approximately timed simulation and a discrete event synchronisation mechanism between multiple processor simulations that will be explained in the following. The simulation results may be visualised by a graphical user interface or by a trace viewer.

Figure 2: Overview of the resource-aware timed functional simulation platform InvadeSIM.

In order to provide a fast simulation of invasive parallel program behaviour on heterogeneous multi-tile MPSoCs, we developed a completely novel processor simulation approach, which is able to tackle the complexity as well as the heterogeneity of current and future large-scale multicore platforms. Existing simulation frameworks for heterogeneous MPSoCs including either cycle-accurate or trace-based approaches are typically much too slow. Our processor simulation approach is a hybrid approach based on performance counters and analytic models, which we call time warping. A synchronisation mechanism preserves the causality of simulation events in case of multiple processor simulations. The basic ideas of both parts are depicted in the central box of Figure 2. The discrete event simulation approach combines the functional execution of an application i-let with the timing simulation corresponding to the computational properties of the target processor on which it was mapped at run time. This is done by scaling the time elapsed on the simulation host to the time the code would have taken on the simulated processor. As experiments have shown, our simulation is much faster than cycle-accurate simulation. Moreover, this work was presented at the HiPEAC ACACES Summer School 2012.

For the architectural model, we consider typical invasive heterogeneous tiled architectures consisting of multiple tiles that are connected by a network-on-chip. Here, each tile is customisable in size and types of local memory, a CiC, and number and types of processing elements, such as RISC CPUs, i-Cores, or TCPAs. The CiC schedules the application i-lets that are spawned on a tile to the processors contained in the claim of the application. Furthermore, each processor is characterised by a set of attributes like cycles per instruction (CPI), clock frequency and other processor-specific features. An architecture configuration file is used to describe these configuration settings of a given invasive architecture. A remarkable highlight of the architecture model is the design and implementation of a flit-accurate (in NoCs, network packets consist of small pieces called flow control digits [flits]) simulation model of an invasive network-on-chip (iNoC) in X10, which was developed in close cooperation with Project B5. This enables the simulation of network latencies between communicating i-lets on different tiles where the interference of different communications at the same time is also taken into account. Furthermore, we have investigated concepts of accelerating the network simulation by proposing an analytic calculation of network latencies in case of guaranteed service communications.

As mentioned earlier, the application model for our simulations are real applications written and supporting full X10. Especially the simulation of spawning, starting, blocking and locking of i-lets as well as the communication between i-lets across tiles is a feature of InvadeSIM and all X10 language constructs for parallelism (e.g., async), synchronisation (e.g., finish, when, or clocks) and communication (e.g., at, dist arrays, remote arrays) are supported. In this realm, we have modified the X10 run-time system and during simulation each of these primitives is re-directed to our simulator kernel. As an example, the primitives for communication between tiles, which are invoked by an at call, are re-directed to our network simulation kernel to calculate the latency of the corresponding data transfer instead of calling the real X10 communication library. This integration of our simulation methodology into the X10 run-time system was an important step towards fulfilling the requirements of the application projects of the TCRC. Here, Project D3 and Project D1 provided example applications for testing purposes.

Finally, in order to support all invasion commands and constructs, the InvadeX10 as developed by Project A1 was integrated into our simulation framework. Here, the most crucial task was the design and implementation of an agent-based invasive run-time system at X10 level. This required an interface to exchange information between the invasive run-time system and the simulated hardware. Whereas Project C1 primarily developed and evaluated agent-based resource allocation strategies for a very simplified application model of task graphs, Project C2 considers the execution of entire X10 applications and thus can also simulate application-inherent dynamic behaviour. We implemented different resource management strategies in cooperation with Project A1 (resource management based on game theory) and Project C1 (DistRM). We evaluated these resource management strategies in terms of quality (e.g., average speedup of multiple applications), computation and communication overheads.

Besides the achievements mentioned above, an interactive visualisation tool to show the invasion status of processors during simulation was developed in order to represent the simulation results in a handy way instead of just viewing the raw information of a trace file. Here, different information about the processors and tiles (e.g., invasion status, infection status, load, temperature, etc.) may be displayed in an architectural view at a certain point of simulation time. A final contribution was the realisation of a task graph library in X10, which will be a starting point for the investigations of Project A1 in the second funding phase for modelling and mapping of streaming applications invasively. Using this task graph extension of X10, we started to model a communicating task chain of a robot object tracking application, which is composed of three sub-algorithms: Harris corner detection, SIFT feature description and SIFT feature matching. This work was done with a class of thirteen selected students in a two week summer school during the Sarntal Academy 2013 and finally tuned in cooperation with Project D1. Furthermore, we organised a TCRC-internal simulation workshop where the participants were taught how to use the simulation framework and got the opportunity to contribute to its development with knowledge in their specific area.

Summarising, the fast simulation of the interplay between invasive program behaviour and the resulting states of the underlying processing resources such as their load, temperature, or faultiness in dependence of their state of invasion is one of the key features of our developed timed functional simulation platform InvadeSIM. It delivers important timing information about the invasion states and parallel execution of several applications running on an invasive architecture, taking into account the computational properties of the different processing elements. Therefore, it provides a backbone and will pave also the way to investigate different invasive architecture platform configurations during architectural exploration and to validate invasive programming concepts before real hardware is available.

A comprehensive summary of the major achievements of the first funding phase can be found by accessing Project C2 first phase website.
Project C2 terminated after the second funding phase.

Publications