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 second period of four years (July 2014 - June 2018), 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.
The Idea of Invasive Computing
The main idea and novelty of invasive computing is to introduce resource-aware programming support in the sense that a given program gets the ability to explore and dynamically spread its computations to processors similar to a phase of invasion, then to execute portions of code of high parallelism degree in parallel based on the available (invasible) region on a given multi-processor architecture. Afterwards, once the program terminates or if the degree of parallelism should be lower again, the program may enter a retreat phase, deallocate resources and resume execution again, for example, sequentially on a single processor. To support this idea of self-adaptive and resource-aware programming new programming concepts, languages, compilers and operating systems are necessary as well as architectural changes in the design of MPSoCs (Multi-Processor Systems-on-a-Chip) to efficiently support invasion, infection and retreat operations by involving concepts for dynamic processor, interconnect and memory reconfiguration. Decreasing feature sizes have also led to a rethinking in the design of multi-million transistor system-on-chip (SoC) architectures, envisioning dramatically increasing rates of temporary and permanent faults and feature variations.
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.
As we can foresee SoCs with 1000 or more processors on a single chip in the year 2020, static and central management concepts to control the execution of all resources might have met their limits long before and are therefore not appropriate. Invasion might provide the required self-organising behaviour to conventional programs for being able to provide scalability, higher resource utilisation, required fault tolerance, and of course also performance gains by adjusting the amount of allocated resources to the temporal needs of a running application. This thought opens a new way of thinking about parallel algorithm design. Based on algorithms utilising invasion and negotiating resources with others, we can imagine that corresponding programs become personalised objects, competing with other applications running simultaneously on an MPSoC.
A Transregional Collaborative Research Center aggregating the best researchers from three excellent sites in Germany provides an ideal base to investigate the above revolutionary ideas. Starting off at basically zero in terms of invasive processor hardware, language, compiler, and operating-system availability, we have truly fostered the fundamentals of invasive computing in our first funding phase: These include the definition of required programming language elements for the specification of invasion operations as well as a set of constraints to argue about number, types, and state of resources that may be invaded defining the invasive command space (project area A). A first invasive language based on the language X10 by IBM as well as a compiler for translation of invasive X10 programs (project area C) onto a heterogeneous invasive multi-tile architecture that has also been successfully jointly architected (project area B) is meanwhile ready for experimentation on an FPGA-based prototype (project Z2). The compiler interfaces to the invasive run-time support system irtss that provides for dedicated operating-system support for invasive computing. First invasive applications exploiting different types of processor and communication resources of an invasive network-on-chip (iNoC) are running successfully and have shown considerable gains in resource utilisation and computational efficiencies in comparison with their non-invasive counterparts.
Next Scientific Goals
A unique jewel of invasive computing, however, has not been exploited at all so far: By the fact that resources are temporally claimed (by default) in an exclusive manner, interferences due to multiple applications sharing the same resources being the reality on today's multicore systems may be reduced if not avoided completely. Moreover, run-to-completion is the default mode of thread execution. Finally, memory reconfiguration and isolation as well as bandwidth guarantees on the designed network-on-chip allow us also to provide predictable QoS also for communication. In the second funding phase, we want to play out this ace systematically by tackling (a) predictability of (b) multi-objective execution qualities of parallel invasive programs and including their (c) optimisation and exploration of design space. Our joint investigations include new language constructs to define so-called requirements on desired, respectively amended qualities of execution. Application-specified qualities will not only be of type performance (e.g. execution time, throughput, etc.), but also include aspects of security and fault tolerance. Through analysis of application requirements from different domains including stream processing and malleable task applications, not only efficiency but also predictable execution qualities shall be demonstrated for applications stemming from robotics, imaging, as well as HPC. As another new yet very important facet of invasive computing, a special focus in the second funding phase is devoted to the problem of dark silicon and energy-efficient 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.