In the Transregional Collaborative Research Center Invasive Computing (abbr. InvasIC), we are investigating a novel paradigm for the design and resource-aware programming of future parallel computing systems. For systems with 1000 and more cores on a chip, resource-aware programming is of utmost importance to obtain high utilisation as well as computational and energy efficiency numbers. With this goal in mind, invasive computing was introduced to give a programmer explicit handles to specify and argue about resource requirements desired or required in different phases of execution. InvasIC is currently being funded by the Deutsche Forschungsgemeinschaft in its third period of four years (July 2018 - June 2022), aggregating researchers from three excellent sites in Germany (Friedrich-Alexander-Universität Erlangen-Nürnberg, Karlsruher Institut für Technologie, Technische Universität München). This scientific team includes specialists in algorithm engineering for parallel algorithm design, hardware architects for reconfigurable MPSoC development as well as language, tool and application, and operating system designers.
Movie: Invasive Computing for Dummies
The Idea of Invasive Computing
Our CRC/Transregio systematically investigates the novel paradigm of invasive computing for designing and programming future parallel computing systems. For systems with 1,000 or more cores on a chip, resource-aware programming is of utmost importance to obtain high utilisation as well as computational and energy and power efficiency. With this goal in mind, invasive computing was introduced to provide a programmer explicit handles to specify and argue about resource requirements desired or required in different phases of execution: In an invade phase, an application asks the operating system to allocate a set of processor, memory and communication resources to be claimed. In a subsequent infect phase, the parallel workload is spread and executed on the obtained claim of resources. Finally, if the degree of parallelism should be lower again, a retreat operation frees the claim again, and the application resumes a sequential execution. To support this idea of self-adaptive and resource-aware programming, not only new programming concepts, languages, compilers, and operating systems were needed to be developed, but also revolutionary architectural changes in the design of MPSoCs (multiprocessor systems-on-a-chip) to efficiently support invasion, infection, and retreat operations. Latter include new concepts for dynamic processor, interconnect, and memory reconfiguration, to give some examples.
Simulation of multiple applications (shown in different colors) invading, infecting, and retreating sets of resources on demand. This animation was created using the InvadeSIM simulator developed by Project C2. If you want to learn how to write and simulate your own invasive programs on a virtual and self-defined invasive architecture, download and test InvadeSIM.
Necessity and First Achievements
As predicted at the start of our journey in 2010, we see systems with more than 1,000 processor cores integrated on a single chip today. Yet, programming such large-scale processor systems is a nightmare if resource awareness is a must and certain execution qualities must be guaranteed. Using invasive computing, a programmer may specify and, if available, the application will obtain as many exclusive resources to deliver a desired quality of execution. This dynamic and application-driven isolation is unique. Starting off from scratch in terms of invasive processor hardware, language, compiler, and operating system, we have truly fostered the fundamentals of invasive computing in the first funding phase: These include the definition of programming language elements for invasion primitives as well as constraints to argue about number, types, and state of resources that may be invaded (the invasive command space, project area A). A first language based on the language X10 by IBM as well as a compiler for translation of invasive X10 programs (project area C) onto invasive multi-tile architectures (architected by project area B) and a run-time system (iRTSS) is available on an FPGA-based prototype (Project Z2). Invasive applications exploiting different types of processor and communication resources of an invasive network-on-chip (iNoC) have shown considerable gains in resource utilisation and efficiency in comparison with their non-invasive counterparts.
Predictability. Or: Sharing is Not Caring!
By the fact that resources are temporally claimed (by default) in an exclusive manner, interference by other applications due to resource sharing may be reduced if not avoided completely. This isolation, combined with run-to-completion as the default mode of thread execution and bandwidth guarantees on communication links, allow us to provide predictable QoS also for communication. In the second funding phase, we played out this ace systematically by tackling (a) predictability of (b) multiple execution qualities of parallel invasive programs and including their (c) mapping optimisation. Here, our findings include new language constructs to define so-called requirements on desired, respectively amended qualities of execution. Addressed qualities include performance (e.g., execution time, throughput, etc.), security and fault tolerance. Through the analysis of application requirements from different domains including stream processing and malleable task applications, not only efficiency but also predictable execution qualities were demonstrated for applications stemming from robotics, imaging, as well as HPC. As another new yet very important facet of invasive computing, a special focus of the second funding phase was devoted to the problem of dark silicon and energy- and power-efficient computing.
Movie: Invasive Computing for Experts
The Missing Link: Beating Run-Time Uncertainties and Run-Time Requirement Enforcement
The isolation gained by invasive computing is essential to establish composability. This, in turn, paved the way for an independent and static analysis of individual program qualities in dependence on only claim properties, giving an unprecedented gain in predictability. Yet, even if this *-predictability (boundedness of any of the above non-functional properties through the invasion of resources) can be shown to hold, (a) the effective bounds (either lower or upper) as well as (b) their variability might still be too big or too coarse to be desirable or affordable in practical application fields such as embedded real-time control. Also, claiming resources exclusively might keep these either underutilised (in case of low application workload demands) or inefficiently used (e.g. when running a claim always at maximal processor speeds) in order to safely guarantee timing bounds also for the worst case input. The third funding phase was therefore dedicated to the missing link: Beating the uncertainty caused by program input, machine state and environment variation at run time. The envisioned solution: Run-time requirement enforcement. Here, we investigated hybrid techniques combining (a) static analysis of the robustness of desired qualities in dependence on input and state fluctuations and (b) systematic generation of suitable run-time requirement enforcers (RRE) (additional code that either locally or globally observes and controls the satisfaction of requirements in respective corridors at run time). This also includes the generation of necessary program-specific run-time requirement monitors (RRM). With these techniques, we reached our final goals and vision formulated already at the beginning of our mission: Invasive computing has become a—if not the—vehicle for providing resource awareness for a mixture of best-effort and predictable quality applications. We do believe huge application and business fields in embedded systems will become accessible for multicore technology through the foundations of invasive computing.
Long Term Vision
With the aforementioned fundamental investigations in mind, we intend to demonstrate that invasive computing will be a - if not the- vehicle for solving many current problems of multicore computing today by providing resource awareness for a mixture of best-effort applications and applications with predictable quality. We do expect that a huge application and business field in embedded system applications might be accessed through the foundations of invasive computing.