Projects


A1: Basics of Invasive Computing

Principal Investigators:

Prof. J. Teich, Prof. G. Snelting, Dr. S. Wildermann

Scientific Researchers:

M. Braun Prof. M. Glaß, B. Pourmohensi, T. Schwarzer, A. Weichlsgartner, A. Zwinkau

Abstract

Project A1 investigates the basics of invasion, that is, the fundamental programming model for invasive and resource-aware computation as well as concepts, features and analysis of invasive programs and of run-time management strategies in invasive systems.

In the first funding phase, we investigated the fundamental programming model for invasive and resource-aware computation. Our research was divided into two major areas: The first area was devoted to the basic concepts, features, and analysis of invasive programs. The second area defined the language support for invasive programming concepts. The result of this phase was the invasive programming language InvadeX10 which is based on X10 and offers resource-aware programming and dynamic reservation of processor, memory, and communication bandwidth.

Programs written in InvadeX10 are able to adapt their resource usage and degree of parallelism to the number and types of dynamically available resources, which is affecting functional and non-functional properties of their execution. By enforcing (temporally and spatially) exclusive resource usage, resource conflicts and congestion can be avoided. In the second funding phase, these properties of invasive computing will be used to increase the predictability of program execution – one of the most challenging problems today for the successful introduction of manycore technology in many embedded and often time-, safety-, or security-critical system applications.

Synopsis

Project A1 aims to increase the usability and predictability of invasive programming for different application domains. On the one hand, a generic programming framework will be provided for common invasive programming patterns, e.g. for malleable algorithms or parallel divide-and-conquer algorithms. Main contributions will be realised as extensions to the programming language as well as expansions of theoretical foundations. On the other hand, the research is focused on ways how to increase the predictability and how to guarantee multiple qualities of program execution through invasive computing. To achieve this, we will provide a means for an application programmer to specify a set of non-functional requirements, e.g. with respect to execution time, security, and reliability of application execution. Another point of investigation is the introduction of a more abstract level of the invasive programming language. Here, an actor programming model will be introduced that allows to specify concurrent program segments (actors) which perform parallel data processing based on exchanged messages and data. Invasive programming patterns, actors, and requirements will be subsequently transformed into more low-level InvadeX10 constructs and constraints.

Predictability also requires theoretical foundations concerning the programming language and system analysis techniques. Formal semantics and a memory model for invasive programming are necessary to provide truly predictable behaviour and guarantees such as type safety, cache coherence, or data race freedom. This formalisation will also be used to provide guarantees for resource usage (e.g. bounded resources or upper bounds for parallelism), which are similar to type safety guarantees but based on resource-dependent types and type derivations.

Furthermore, A1 will extend its analysis techniques developed in the first funding phase to prove feasibility, convergence, and optimality of decentralised run-time management strategies also for the (a) multi-objective and (b) heterogeneous case. Particularly, (c) the predictability of certain qualities of execution shall be expressed by additional objectives to be quantified.

Approach

Overview


Above figure gives an overview of the flow for predictable invasive computing. Program analysis and characterisation (Project A4) automatically extract various operating points for program execution from InvadeX10 code which uses the new programming extensions. Via compilation (Project C3), this information is handed to the invasive run-time support system (Project C1) which is based on formally analyzed run-time management strategies to enable feasible and optimized program execution.

Invade X10

The invasive programming language InvadeX10 developed in the first funding phase provides constructs to enable resource-aware computation and serves as the basis for further developments in the second funding phase. Consider the following program fragment, which shows the three basic constructs invade, infect, and retreat:

val claim = Claim.invade( constraints );
claim.infect( ilet );
claim.retreat();


The static method Claim.invade takes constraints and returns a claim object, which represents the allocated resources, a set of processing elements (PEs). A claim provides an infect method to distribute computations across the PEs. The argument of infect is an i-let object, which contains the code to execute together with initial data. The infect call blocks the program, until all i-let computations finish. Afterwards, the retreat method frees all resources within a claim, such that the claim is empty. While such a claim can still be infected, this would do nothing. Now consider the ilet variable of the example above. It could be declared as follows:

val ilet = (id: IncarnationID ) => {
Console.OUT.println("Hello! ("+id+")");
};

The first class of constraints we identified were so-called predicate constraints, which specify a predicate for processing elements. An application might require the demanded processing elements to (1) be under a certain load, (2) be under a certain temperature, (3) have an FPU, (4) have certain amount of local memory, (5) have a scratch pad memory, (6) be of a certain type, (7) have a certain cache size, (8) be migratable, or (9) not be scheduled preemptively. Such constraints impose a simple filter operation over the set of available processing elements within an invade operation. The second class of constraints are order constraints, which provide an ordering of processing elements according to (1) load, (2) temperature, (3) memory, or (4) speed. Using these constraints an application can communicate its preferences, whether it is IO- or CPU-bound. By giving multiple of these constraints, the programmer can impose a secondary or tertiary ordering.


Constraint hierarchy for invasive computing

The third class of constraints are set constraints, as they specify conditions for a set of processing elements as a whole. The most common constraint is the (1) quantity of processing elements to be claimed, but there are also partition constraints, (2) a certain physical layout of the PEs, (3) place coherence, which means that the PEs have shared memory, (4) type homogeneity, in terms of the instruction set architecture, (5) cache type homogeneity.
Additionally, there are the two operators AND and OR to combine constraints. At last, the programmer can give nonbinding hints, which can be used to hand complex information like efficiency curves of parameters to the run-time system of the underlying MPSoC architecture. These constraints are implemented as a class hierarchy as shown in Figure above, which is available to the programmer. The constraints above form the leafs of the hierarchy tree and abstract classes, drawn as boxes, partition the tree into categories.

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

Publications

[1] Jürgen Teich. Application mapping methodologies for noc-based mpsocs. Invited Talk University of California, Irvine, USA, November 14, 2017.
[2] Jürgen Teich. Application mapping methodologies for noc-based mpsocs. Invited Talk University Lübeck, September 6, 2017.
[3] Andreas Weichslgartner. Application Mapping Methodologies for Invasive NoC-Based Architectures. Dissertation, Hardware/Software Co-Design, Department of Computer Science, Friedrich-Alexander-Universität Erlangen-Nürnberg, Germany, January 24, 2017.
[4] Jürgen Teich. Run-time monitoring and enforcement of non-functional program properties of invasive programs: Terms and definitions. Technical Report 01-2017, Hardware/Software Co-Design, Friedrich-Alexander-Universität Erlangen-Nürnberg, Department of Computer Science, Erlangen, Germany, January 2017.
[5] Soonhoi Ha and Jürgen Teich, editors. The Handbook of Hardware/Software Codesign. Springer, 2017.
[6] Tobias Schwarzer, Andreas Weichslgartner, Michael Glaß, Stefan Wildermann, Peter Brand, and Jürgen Teich. Symmetry-eliminating Design Space Exploration for Hybrid Application Mapping on Many-Core Architectures. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2017. doi: 10.1109/TCAD.2017.2695894. [ DOI ]
[7] Jürgen Teich. Invasive computing – editorial. it – Information Technology, 58(6):263–265, November 24, 2016. [ DOI ]
[8] Stefan Wildermann, Michael Bader, Lars Bauer, Marvin Damschen, Dirk Gabriel, Michael Gerndt, Michael Glaß, Jörg Henkel, Johny Paul, Alexander Pöppl, Sascha Roloff, Tobias Schwarzer, Gregor Snelting, Walter Stechele, Jürgen Teich, Andreas Weichslgartner, and Andreas Zwinkau. Invasive computing for timing-predictable stream processing on MPSoCs. it – Information Technology, 58(6):267–280, September 30, 2016. [ DOI ]
[9] Gabor Drescher, Christoph Erhardt, Felix Freiling, Johannes Götzfried, Daniel Lohmann, Pieter Maene, Tilo Müller, Ingrid Verbauwhede, Andreas Weichslgartner, and Stefan Wildermann. Providing security on demand using invasive computing. it – Information Technology, 58(6):281–295, September 30, 2016. [ DOI ]
[10] Jürgen Teich, Michael Glaß, Sascha Roloff, Wolfgang Schröder-Preikschat, Gregor Snelting, Andreas Weichslgartner, and Stefan Wildermann. Language and compilation of parallel programs for *-predictable MPSoC execution using invasive computing. In Proceedings of the 10th IEEE International Symposium on Embedded Multicore/Many-core Systems-on-Chip (MCSoC), pages 313–320, Lyon, France, September 2016. [ DOI ]
[11] Jürgen Teich. Predictability, fault tolerance, and security on demand using invasive computing. Invited Talk, University of Lübeck, Germany, July 29, 2016.
[12] Jürgen Teich. Invasive Computing - The DFG Transregional Research Center 89. DTC 2016, The Munich Workshop on Design Technology Coupling, Munich, Germany, June 30, 2016.
[13] Sascha Roloff, Alexander Pöppl, Tobias Schwarzer, Stefan Wildermann, Michael Bader, Michael Glaß, Frank Hannig, and Jürgen Teich. ActorX10: An actor library for X10. In Proceedings of the 6th ACM SIGPLAN X10 Workshop (X10), pages 24–29. ACM, June 14, 2016. [ DOI ]
[14] Jürgen Teich. Predictable MPSoC stream processing using invasive computing. Seminar Talk, Electrical and Computer Engineering, The University of Texas at Austin, USA, June 6, 2016.
[15] Andreas Weichslgartner, Stefan Wildermann, Johannes Götzfried, Felix Freiling, Michael Glaß, and Jürgen Teich. Design-time/run-time mapping of security-critical applications in heterogeneous mpsocs. In Proceedings of the 19th International Workshop on Software and Compilers for Embedded Systems (SCOPES), pages 153–162. ACM, May 23, 2016. [ DOI ]
[16] Andreas Weichslgartner and Jürgen Teich. Position paper: Towards redundant communication through hybrid application mapping. In Proceedings of the third International Workshop on Multi-Objective Many-Core Design (MOMAC) in conjunction with International Conference on Architecture of Computing Systems (ARCS). IEEE, April 4, 2016.
[17] Jürgen Teich. Adaptive restriction and isolation for predictable MPSoC stream procesing. Invited Talk, DATE 2016 Friday Workshop on Resource Awareness and Application Autotuning in Adaptive and Heterogeneous Computing, Dresden, Germany, March 18, 2016.
[18] Jürgen Teich. Symbolic loop parallelization for adaptive multi-core systems - recent advances and benefits. Keynote, IMPACT 2016, the 6th International Workshop on Polyhedral Compilation Techniques, 19 January, 2016, Prague, Czech Republic, January 19, 2016.
[19] Jürgen Teich. The role of restriction and isolation for increasing the predictability of MPSoC stream processing. Keynote, 8th Workshop on Rapid Simulation and Performance Evaluation: Methods and Tools (RAPIDO 2016), Prague, Czech Republic, January 18, 2016.
[20] Stefan Wildermann. Time-predictable multi-core programming using invasive computing. Invited Talk at ESSEI TecDay: Multicore – The challenge in avionics, October 13, 2015.
[21] Sascha Roloff, Stefan Wildermann, Frank Hannig, and Jürgen Teich. Invasive computing for predictable stream processing: A simulation-based case study. In Proceedings of the 13th IEEE Symposium on Embedded Systems for Real-time Multimedia (ESTIMedia). IEEE, October 2015. [ DOI ]
[22] Jürgen Teich. Adaptive isolation for predictable mpsoc stream processing. Keynote, SCOPES 2015, 18th International Workshop on Software and Compilers for Embedded Systems, Schloss Rheinfels, St. Goar, Germany, June 2, 2015.
[23] Jürgen Teich. Adaptive isolation for predictable mpsoc stream processing. In Proceedings of the 18th International Workshop on Software and Compilers for Embedded Systems (SCOPES 2015), pages 1–2, June 2015. [ DOI ]
[24] Stefan Wildermann, Andreas Weichslgartner, and Jürgen Teich. Design methodology and run-time management for predictable many-core systems. In Proceedings of the 6th IEEE Workshop on Self-Organizing Real-Time Systems (SORT), pages 1–8, April 13, 2015.
[25] Stefan Wildermann. Wieviele prozessoren passen in eine hosentasche? Invited Talk at Öffentliche Vortragsreihe Faszination Technik, April 2015.
[26] Jürgen Teich. Invasive computing. Invited Talk, SE 2015, Software Engineering and Management, Special Session Software Engineering in der DFG, Dresden, Germany, March 19, 2015.
[27] Sebastian Buchwald, Manuel Mohr, and Andreas Zwinkau. Malleable invasive applications. In Proceedings of the 8th Working Conference on Programming Languages (ATPS), Lecture Notes in Computer Science (LNCS). Springer Berlin Heidelberg, March 2015.
[28] Jürgen Teich. Reconfigurable computing for mpsoc. Invited Lecture, Winter School Design and Applications of Multi Processor System on Chip, Tunis, Tunesia, November 26, 2014.
[29] Jürgen Teich. Invasive computing – concepts and benefits. Keynote, DASIP 2014, Conference on Design and Architectures for Signal and Image Processing, Madrid, Spain, October 8, 2014.
[30] Andreas Weichslgartner, Deepak Gangadharan, Stefan Wildermann, Michael Glaß, and Jürgen Teich. Daarm: Design-time application analysis and run-time mapping for predictable execution in many-core systems. In Proceedings of the International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS 2014), pages 1–10, October 2014. [ DOI ]
[31] Jürgen Teich. System-level design automation of embedded systems. Invited Talk, Tagung Deutsche Forschungsgesellschaft für Automatisierung und Mikroelektronik e.V. (DFAM), September 25, 2014.
[32] Jürgen Teich. Foundations and benefits of invasive computing. Seminar, Mc Gill University, Montreal, July 29, 2014.
[33] Jürgen Teich. Introduction to invasive computing. Workshop on Resource Awareness and Adaptivity in Multi-Core Computing (Racing 2014), Paderborn, Germany, Tutorial Talk, May 29, 2014.
[34] Jürgen Teich. Foundations and benefits of invasive computing. University of Bologna, Italy, Invited Talk in the Seminar Series Trends in Electronics, May 23, 2014.
[35] Michael Glaß, Michael Bader, Jürgen Teich, and Stefan Wildermann. Assisting run-time optimization of many-core systems by design-time characterization. HiPEAC Spring Computing Systems Week, Barcelona, Invited Talk, May 13, 2014.
[36] Frank Hannig and Jürgen Teich, editors. Proceedings of the First Workshop on Resource Awareness and Adaptivity in Multi-Core Computing (Racing 2014). May 2014. [ arXiv ]
[37] Deepak Gangadharan, Alexandru Tanase, Frank Hannig, and Jürgen Teich. Timing analysis of a heterogeneous architecture with massively parallel processor arrays. In DATE Friday Workshop on Performance, Power and Predictability of Many-Core Embedded Systems (3PMCES). ECSI, March 28, 2014. [ http ]
[38] Stefan Wildermann, Michael Glaß, and Jürgen Teich. Multi-objective distributed run-time resource management for many-cores. In Proceedings of Design, Automation and Test in Europe (DATE), pages 1–6, March 2014. [ DOI ]
[39] Jan Heisswolf, Aurang Zaib, Andreas Weichslgartner, Martin Karle, Maximilian Singh, Thomas Wild, Jürgen Teich, Andreas Herkersdorf, and Jürgen Becker. The invasive network on chip - a multi-objective many-core communication infrastructure. In Proceedings of the first International Workshop on Multi-Objective Many-Core Design (MOMAC) in conjunction with International Conference on Architecture of Computing Systems (ARCS). IEEE, February 25, 2014.
[40] Sascha Roloff, Frank Hannig, and Jürgen Teich. Towards actor-oriented programming on PGAS-based multicore architectures. In Workshop Proceedings of the 27th International Conference on Architecture of Computing Systems (ARCS). VDE Verlag, February 2014.
[41] Jan Heisswolf, Aurang Zaib, Andreas Zwinkau, Sebastian Kobbe, Andreas Weichslgartner, Jürgen Teich, Jörg Henkel, Gregor Snelting, Andreas Herkersdorf, and Jürgen Becker. Cap: Communication aware programming. In 51th ACM/EDAC/IEEE Design Automation Conference (DAC), pages 105:1–105:6, 2014.
[42] Jürgen Teich. Invasive computing – the quest for many-core efficiency and predictability. Keynote Talk, Sixth Swedish Workshop on Multicore Computing, Halmstad, Sweden, November 25, 2013.
[43] Jürgen Teich. Invasive computing - the quest for many-core efficiency and predictability. Invited Talk, 5th tubs.CITY Symposium, Managing change and autonomy or critical applications, Braunschweig, Germany, October 30, 2013.
[44] Jürgen Teich. The invasive computing paradigm as a solution for highly adaptive and efficient multi-core systems. Talk, Special Session on Run-Time Adaption for Highly-Compley Multi-Core Systems, CODES+ISSS 2013, Montral, Canada, September 30, 2013.
[45] Jörg Henkel, Vijaykrishnan Narayanan, Sri Parameswaran, and Jürgen Teich. Run-time adaptation for highly-complex multi-core systems. In Proceedings of the IEEE International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS), September 2013. [ DOI ]
[46] Jürgen Teich. Invasive computing - the quest for many-core efficiency and predictability. Invited Keynote, Doctoral Workshop GNARP 2013 (The 20th annual ASCI Computing Workshop), Soesterberg, The Netherlands, April 25, 2013.
[47] Jürgen Teich. More cores = less predictability? Invited Talk, University of Amsterdam, The Netherlands, April 24, 2013.
[48] Jürgen Teich. More cores = less predictability? Innovation Forum Smart Systems, Bavarian Information and Communication Technology Cluster (BICCNet), Munich, Germany, April 18, 2013.
[49] Sefan Wildermann, Tobias Ziermann, and Jürgen Teich. Game-theoretic analysis of decentralized core allocation schemes on many-core systems. In Proceedings of Design, Automation and Test in Europe Conference (DATE), pages 1498–1503, March 2013. [ DOI ]
[50] Jürgen Teich. Invasive computing - the quest for many-core efficiency and predictability. Invited Keynote Speech, 26th International Conference on Architecture of Computing Systems (ARCS), Prague, Czech Republic, February 20, 2013.
[51] Jürgen Teich. Safe(r) loop computations on multi-cores. Invited Talk, 2nd Workshop on Design Tools and Architectures for Multi-Core Embedded Computing Platforms (DITAM 2013), Berlin, Germany, January 22, 2013.
[52] Hans-Joachim Bungartz, Christoph Riesinger, Martin Schreiber, Gregor Snelting, and Andreas Zwinkau. Invasive computing in HPC with X10. In X10 Workshop (X10'13), X10 '13, pages 12–19, New York, NY, USA, 2013. ACM. [ DOI ]
[53] Jürgen Teich, Wolfgang Schröder-Preikschat, and Andreas Herkersdorf. Invasive computing - common terms and granularity of invasion. CoRR, abs/1304.6067, 2013.
[54] Tobias Ziermann, Stefan Wildermann, and Jürgen Teich. Self-organizing core allocation. In Parallel-Algorithmen, -Rechnerstrukturen und -Systemsoftware (PARS), number ISSN 0177-0454 in PARS Mitteilungen GI. ACM German Chapter, Gesellschaft für Informatik e.V., 2013.
[55] Andreas Zwinkau, Sebastian Buchwald, and Gregor Snelting. Invadex10 documentation v0.5. Technical Report 7, Karlsruhe Institute of Technology, 2013. [ .pdf ]
[56] Jürgen Teich. Invasive computing - or - how to tame 1000+ cores on a chip? Invited Talk, IBM, Böblingen, Germany, October 26, 2012.
[57] Jürgen Teich. Invasive computing - or - how to tame 1000+ cores on a chip. Models and Assistive Tools for Programming Emerging Architectures, Invited Talk, HiPEAC CSW 2012, Ghent, Belgium, October 15, 2012.
[58] Jürgen Teich. Invasive computing - or - how to tame 1000+ cores on a chip? Invited Talk, Intel, Braunschweig, Germany, September 20, 2012.
[59] Jürgen Teich, Andreas Weichslgartner, Benjamin Oechslein, and Wolfgang Schröder-Preikschat. Invasive computing – concepts and overheads. In Proceedings of the Forum on Specification and Design Languages (FDL), pages 193–200, September 2012.
[60] Jürgen Teich. Invasive computing - or - how to tame 1000+ cores on a chip? Invited Talk, University of Auckland, New Zealand, August 9, 2012.
[61] Jürgen Teich. Domain-specific and resource-aware computing on multi-core architectures. HiPEAC Summer School ACACES, Lecture, Lecture, Fiuggi, Italy, July 8, 2012.
[62] Jürgen Teich. Hardware/software co-design: The past, present, and predicting the future. Proceedings of the IEEE, 100(Centennial-Issue):1411–1430, May 2012. [ DOI ]
[63] Jürgen Teich. Actor-based virtual prototype generation. Workshop: Quo Vadis, Virtual Platforms? Challenges and Solutions for Today and Tomorrow, Invited Talk, date 2012, Dresden, Germany, March 16, 2012.
[64] Jürgen Teich. Introduction to invasive computing and overhead analysis for a shared-memory mpsoc. 3rd Workshop on Parallel Programming and Run-Time Management Techniques for Many-core Architectures, Munich, Germany, February 29, 2012.
[65] Matthias Braun, Sebastian Buchwald, Manuel Mohr, and Andreas Zwinkau. An X10 compiler for invasive architectures. Technical Report 9, Karlsruhe Institute of Technology, 2012. [ http ]
[66] Jürgen Teich. Programming invasively parallel – an introduction. Pervasive Parallelism Laboratory (PPL) Seminar Talk, Stanford University, CA, USA, July 25, 2011.
[67] Jürgen Teich. Invasive parallel computing – an introduction. Par Lab and AMP Lab Seminar Talk, UC Berkeley, CA, USA, July 22, 2011.
[68] Georgia Kouveli, Frank Hannig, Jan-Hugo Lupp, and Jürgen Teich. Towards resource-aware programming on Intel's single-chip cloud computer processor. In 3rd Many-core Applications Research Community (MARC) Symposium, volume 7598 of KIT Scientific Reports, pages 111–114. KIT Scientific Publishing, July 2011.
[69] Frank Hannig, Sascha Roloff, Gregor Snelting, Jürgen Teich, and Andreas Zwinkau. Resource-aware programming and simulation of MPSoC architectures through extension of X10. In Proceedings of the 14th International Workshop on Software and Compilers for Embedded Systems (SCOPES), pages 48–55. ACM Press, June 2011. [ DOI ]
[70] Andreas Weichslgartner, Stefan Wildermann, and Jürgen Teich. Dynamic decentralized mapping of tree-structured applications on NoC architectures. In Proceedings of the Fifth ACM/IEEE International Symposium on Networks-on-Chip (NOCS), pages 201–208, May 2011. [ DOI ]
[71] Jürgen Teich, Jörg Henkel, Andreas Herkersdorf, Doris Schmitt-Landsiedel, Wolfgang Schröder-Preikschat, and Gregor Snelting. Invasive computing: An overview. In Michael Hübner and Jürgen Becker, editors, Multiprocessor System-on-Chip – Hardware Design and Tool Integration, pages 241–268. Springer, Berlin, Heidelberg, 2011. [ DOI ]
[72] Jürgen Teich. Invasive computing – basic concepts and foreseen benefits. Artist Network of Excellence on Embedded System Design Summer School Europe 2010, Autrans, France, Invited Tutorial, September 7, 2010.
[73] Jürgen Teich. Invasive algorithms and architectures. it - Information Technology, 50(5):300–310, 2008.
[74] Andreas Zwinkau. Resource awareness for efficiency in high-level programming languages. Technical Report 12, Karlsruhe Institute of Technology. [ .pdf ]