Projects


B5: Invasive NoCs – Autonomous, Self-Optimising Communication Infrastructures for MPSoCs

Principal Investigators:

Prof. Becker, Prof. Herkersdorf, Prof. Teich

Scientific Researchers:

Jan Heißwolf, Andreas Weichslgartner, Aurang Zaib

Abstract

Subproject B5 will investigate and design invasible Networks-on-a-Chip, in the following called iNoCs with emphasis on three major research fields: a) novel router functions and protocols for invasion of communication channels, b) detailed link characterisation and prediction through run-time monitoring for improving communication and resource utilisation by means of self-adaptation, and c) decentralised algorithms and strategies for low cost and low latency embedding of application-specific communication patterns, i. e., topology requests, while considering contention and temporal faultiness of links and nodes.

Synopsis

This project studies novel NoC concepts and architectures called invasive NoCs or iNoCs. Apart from standard packet routing, an iNoC shall support the invasion of application-specific routing channels and topologies during the lifetime of an application on an MPSoC so to provide guaranteed bandwidth and for optimisation of link resource usage. In this realm, the following three research fields will be investigated:
Decentralised Executive for Invasion of Communication Networks: An iNoC shall be able to perform hardware-assisted allocation and management of i-let specific communication channel requests. Here, novel protocols, methods and interfaces have to be defined that allow to transfer and execute link invade-, infect- and retreat-commands within the iNoC. The distinguishing capabilities of an iNoC include Quality of Service (QoS)-aware routing strategies (selection of different routing algorithms combined), parallel link invasion, run-time mapping of logical communication path requests and topologies onto physical resources (e. g., for trees/arrays, uni-/bidirectional communication, uni-/broadcasts) as well as the allocation of proper routing resources (including link and router-internal buffer allocation).
Monitoring and Self-optimisation: Multiple parallel link invade, infect, and retreat activities might lead to fragmented network resources and states. Here, online link-monitoring, -characterisation, and -prediction techniques shall be investigated and strategies developed so to self-optimise established communication paths by re-routing and re-allocation of iNoC resources. Such a mechanism shall be investigated under the term re-infection. It includes searching for alternative communication routes, change of data communication protocol, reassignment of iNoC resources to communication links and adaption to faults as well as dynamic change of bandwidth requests.
Self-embedding of Application-specific Communication Topologies: A team of i-lets with heavy inter i-let communication may desire to temporally invade a dedicated path of routing channels between chosen sender and receiver nodes, or even a dedicated NoC topology that reflects the data dependencies between each pair of i-lets. Ideally, such an embedding shall be established in a little amount of time and with low area overhead decentrally by the iNoC routers themselves. Important questions are if, which, and how dependence information between i-lets has to be exchanged, and for how long these have to be stored either fully or partially. Which algorithms will be able to provide correct (establishment of a path, if there exists at least one) and good quality (number of involved router nodes, number of occupied links, dilation, etc.) embeddings? Evaluation criteria are latency, and resulting hardware and data overhead. The investigated algorithms shall respect busy and faulty links and nodes. Self-optimisation of such paths, and methods of self-repair shall be consistently applicable.

Approach


The iNoC connects the tiles in the heterogeneous tile based MPSoC architecture. Through the invasive Network Adapter (iNA) the different tiles (TCPA-tiles, iCore-tiles, RISC-tiles, memory-tiles and I/O-tiles) are connected to the iNoC.
The iNoC provides efficient support for reservation and release of communicati- on resources. The reservation of communication resources by applications in the iNoC is realized through dynamically configurable guaranteed service connections.

Publications

[1] Andreas Weichslgartner, Stefan Wildermann, Michael Glaß, and Jürgen Teich. Invasive Computing for Mapping Parallel Programs to Many-Core Architectures. Springer, 2018.
[2] A. Srivatsa, S. Rheindt, T. Wild, and A. Herkersdorf. Region based cache coherence for tiled mpsocs. In 2017 30th IEEE International System-on-Chip Conference (SOCC), September 2017.
Keywords: cache coherence;scalable coherence;dynamic coherency regions;distributed shared memory;scalable multicore architectures
[3] Stephanie Friederich. Automated Hardware Prototyping for 3D Networks on Chips. Dissertation, Institut für Technik der Informationsverarbeitung, Karlsruhe Institute of Technology (KIT), May 23, 2017.
[4] Lukas Meder. Timing Synchronization and Fast-Control for FPGA-based large-scale Readout and Processing Systems. Dissertation, Institut für Technik der Informationsverarbeitung (ITIV), Fakultät für Elektrotechnik und Informationstechnik, Karlsruher Institut für Technologie (KIT), April 1, 2017.
[5] 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.
[6] Soonhoi Ha and Jürgen Teich, editors. The Handbook of Hardware/Software Codesign. Springer, 2017. [ DOI ]
[7] Aurang Zaib, Jan Heisswolf, Andreas Weichslgartner, Thomas Wild, Jürgen Teich, Jürgen Becker, and Andreas Herkersdorf. Efficient task spawning for shared memory and message passing in many-core architectures. Journal of Systems Architecture (JSA), 2017. [ DOI ]
[8] Jürgen Teich. Invasive computing – editorial. it – Information Technology, 58(6):263–265, November 24, 2016. [ DOI ]
[9] Vivek Singh Bhadouria, Alexandru Tanase, Moritz Schmid, Frank Hannig, Jürgen Teich, and Dibyendu Ghoshal. A novel image impulse noise removal algorithm optimized for hardware accelerators. Journal of Signal Processing Systems, 89(2):225–242, November 1, 2016. [ DOI ]
[10] Vahid Lari, Andreas Weichslgartner, Alex Tanase, Michael Witterauf, Faramarz Khosravi, Jürgen Teich, Jürgen Becker, Jan Heißwolf, and Stephanie Friederich. Providing fault tolerance through invasive computing. it – Information Technology, 58(6):309–328, October 19, 2016. [ DOI ]
[11] 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 ]
[12] 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 ]
[13] Stephanie Friederich, Marco Neber, and Jürgen Becker. Power management controller for online power saving in network-on-chips. In International Symposium on Embedded Multicore/Manycore SoCs (MCSoC), volume 10, September 2016.
[14] 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 ]
[15] Jürgen Teich. Predictability, fault tolerance, and security on demand using invasive computing. Invited Talk, University of Lübeck, Germany, July 29, 2016.
[16] 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.
[17] 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.
[18] 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 ]
[19] Jan Heisswolf, Stephanie Friederich, Leonard Masing, Aandreas Weichslgartner, Aurang M. Zaib, Carsten Stein, Marco Duden, Jürgen Teich, Thomas Wild, Andreas Herkersdorf, and Jürgen Becker. A novel noc-architecture for fault tolerance and power saving. 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.
[20] 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.
[21] 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.
[22] 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.
[23] 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.
[24] Stephanie Friederich, Niclas Lehmann, and Jürgen Becker. Adaptive bandwidth router for 3d network-on-chips. In Applied Reconfigurable Computing, pages 352–360, 2016. [ DOI ]
[25] Michael Dreschmann, Jan Heisswolf, Michael Geiger, Manuel Haußecker, and Jürgen Becker. A framework for multi-FPGA interconnection using multi gigabit transceivers. In Proceedings of the 28th Symposium on Integrated Circuits and Systems Design (SBCCI), pages 5:1–5:6. ACM, August 2015. [ DOI ]
[26] Moritz Schmid. Rapid Prototyping for Hardware Accelerators in the Medical Imaging Domain. Dissertation, Hardware/Software Co-Design, Department of Computer Science, Friedrich-Alexander-Universität Erlangen-Nürnberg, Germany, July 24, 2015.
[27] Jan Heisswolf, Andreas Weichslgartner, Aurang Zaib, Stephanie Friederich, Leonard Masing, Carsten Stein, Marco Duden, Roman Klöpfer, Thomas Wild, Andreas Herkersdorf, Jürgen Teich, and Jürgen Becker. Fault-tolerant communication in invasive networks on chip. In Proceedings of the 2015 NASA/ESA Conference on Adaptive Hardware and Systems (AHS), pages 1–8. IEEE, June 2015.
[28] 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.
[29] 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.
[30] Preethi Parayil, Aurang Zaib, Thomas Wild, Stefan Wallentowitz, and Andreas Herkersdorf. Sharer status-based caching in tiled multiprocessor systems-on-chip. In HPC 2015 – 23rd High Performance Computing Symposia, pages 67–74. SCS, The Society for Modeling & Simulation, April 2015.
[31] 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.
[32] Andreas Weichslgartner, Jan Heisswolf, Aurang Zaib, Thomas Wild, Andreas Herkersdorf, Jürgen Becker, and Jürgen Teich. Position paper: Towards hardware-assisted decentralized mapping of applications for heterogeneous noc architectures. In Proceedings of the second International Workshop on Multi-Objective Many-Core Design (MOMAC) in conjunction with International Conference on Architecture of Computing Systems (ARCS). IEEE, March 2015.
[33] Aurang Zaib, Jan Heisswolf, Andreas Weichslgartner, Thomas Wild, Jürgen Teich, Jürgen Becker, and Andreas Herkersdorf. Network interface with task spawning support for noc-based dsm architectures. In 28th GI/ITG International Conference on Architecture of Computing Systems (ARCS), volume 9017 of Lecture Notes in Computer Science (LNCS), pages 186–198. Springer, 2015. [ DOI ]
[34] Christoph Roth. Parallele und kooperative Simulation für eingebettete Multiprozessorsysteme. Dissertation, Institut für Technik der Informationsverarbeitung, Karlsruhe Institute of Technology (KIT), December 2014. [ http ]
[35] 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.
[36] Jan Heisswolf. A Scalable and Adaptive Network on Chip for Many-Core Architectures. Dissertation, Institut für Technik der Informationsverarbeitung, Karlsruhe Institute of Technology (KIT), November 11, 2014. [ http ]
[37] 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.
[38] 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 ]
[39] Stephanie Friederich, Jan Heisswolf, and Jürgen Becker. Hardware/software debugging of large scale many-core architectures. In Proceedings of the 27th Symposium on Integrated Circuits and Systems Design (SBCCI), pages 1–7. IEEE, September 2014. [ DOI ]
[40] Jürgen Teich. Foundations and benefits of invasive computing. Seminar, Mc Gill University, Montreal, July 29, 2014.
[41] 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.
[42] 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.
[43] 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.
[44] Stephanie Friederich, Jan Heisswolf, David May, and Jürgen Becker. Hardware prototyping and software debugging of multi-core architectures. In Proceedings of the Synopsys Users Group Conference (SNUG), 2014.
[45] 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.
[46] J. Heisswolf, S. Bischof, M. Rueckauer, and Jürgen Becker. Efficient memory access in 2d mesh noc architectures using high bandwidth routers. In Proceedings of the 26th Symposium on Integrated Circuits and Systems Design (SBCCI), pages 1–6, September 2013. [ DOI ]
[47] Aurang Zaib, Jan Heisswolf, Andreas Weichslgartner, Thomas Wild, Jürgen Teich, Jürgen Becker, and Andreas Herkersdorf. Auto-gs: Self-optimization of noc traffic through hardware managed virtual connections. In Proceedings of the 16th Euromicro Conference on Digital System Design (DSD), pages 761–768. IEEE, September 2013. [ DOI ]
[48] Jan Heisswolf, Aurang Zaib, Andreas Weichslgartner, Ralf König, Thomas Wild, Jürgen Teich, Andreas Herkersdorf, and Jürgen Becker. Virtual networks – distributed communication resource management. ACM Trans. Reconfigurable Technol. Syst., 6(2):8:1–8:14, August 2013. [ DOI ]
[49] Sascha Roloff, Andreas Weichslgartner, Jan Heißwolf, Frank Hannig, and Jürgen Teich. NoC simulation in heterogeneous architectures for PGAS programming model. In Proceedings of the 16th International Workshop on Software and Compilers for Embedded Systems (M-SCOPES), pages 77–85. ACM, June 2013. [ DOI ]
[50] Jan Heisswolf, Andreas Weichslgartner, Aurang Zaib, Ralf König, T. Wild, A. Herkersdorf, Jürgen Teich, and Jürgen Becker. Hardware supported adaptive data collection for networks on chip. In Proceedings of the 2013 IEEE 27th International Symposium on Parallel and Distributed Processing Workshops and PhD Forum (IPDPSW), pages 153–162, May 2013. [ DOI ]
[51] C. Pham, J. Heisswolf, S. Wenner, Z. Al-Ars, J.A. Becker, and K.L.M. Bertels. Hybrid interconnect design for heterogeneous hardware accelerators. In Proceedings of Design, Automation and Test in Europe Conference (DATE), pages 843–846, March 2013. [ DOI ]
[52] 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.
[53] Jan Heisswolf, Ralf König, M. Kupper, and Jürgen Becker. Multiple hard latency and throughput guarantees for packet switching networks on chip. Computers & Electrical Engineering, 2013. [ DOI ]
[54] Jan Heisswolf, Maximilian Singh, Martin Kupper, Ralf Koenig, and Juergen Becker. Rerouting: Scalable noc self-optimization by distributed hardware-based connection reallocation. In Proceedings of the International Conference on Reconfigurable Computing and FPGAs (ReConFig), 2013.
[55] Christian Schuck. Design and Synthesis of Organic Computing Hardware Architectures. Dissertation, Institut für Technik der Informationsverarbeitung (ITIV), Fakultät für Elektrotechnik und Informationstechnik, Karlsruher Institut für Technologie (KIT), July 10, 2012.
[56] Jan Heisswolf, Ralf König, and Jürgen Becker. A scalable noc router design providing qos support using weighted round robin scheduling. In Parallel and Distributed Processing with Applications (ISPA), 2012 IEEE 10th International Symposium on, pages 625–632, July 2012. [ DOI ]
[57] Jan Heisswolf, Aurang Zaib, Andreas Weichslgartner, Ralf König, Thomas Wild, Jürgen Teich, Andreas Herkersdorf, and Jürgen Becker. Hardware-assisted decentralized resource management for networks on chip with qos. In Proceedings of the 2012 IEEE 26th International Symposium on Parallel and Distributed Processing Workshops and PhD Forum (IPDPSW), pages 234–241, Shanghai, China, May 2012. [ DOI ]
[58] Jürgen Becker, Stephanie Friederich, Jan Heisswolf, Ralf Koenig, and David May. Hardware prototyping of novel invasive multicore architectures. In Proceedings of the 17th Asia and South Pacific Design Automation Conference (ASP-DAC), pages 201–206, January 2012. [ DOI ]
[59] Jörg Henkel, Andreas Herkersdorf, Lars Bauer, Thomas Wild, Michael Hübner, Ravi Kumar Pujari, Artjom Grudnitsky, Jan Heisswolf, Aurang Zaib, Benjamin Vogel, Vahid Lari, and Sebastian Kobbe. Invasive manycore architectures. In Proceedings of the 17th Asia and South Pacific Design Automation Conference (ASP-DAC), pages 193–200, January 2012. [ DOI ]
[60] Alexander Klimm. Computing Architectures for Security Applications on Reconfigurable Hardware in Embedded Systems. Dissertation, Institut für Technik der Informationsverarbeitung (ITIV), Fakultät für Elektrotechnik und Informationstechnik, Karlsruher Institut für Technologie (KIT), December 22, 2011.
[61] 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 ]
[62] 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 ]
[63] Jürgen Teich. Invasive algorithms and architectures. it - Information Technology, 50(5):300–310, 2008.