Projects

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

Principal Investigators:

Prof. J. Becker, Prof. A. Herkersdorf, Prof. J. Teich

Scientific Researchers:

N. Anantharajaiah, L. Masing, B. Pourmohensi, S. Rheindt, A. Srivatsa,

Abstract

Project B5 investigates and designs the invasible Networks-on-a-Chip, in the following called iNoC.

In the first funding phase, a NoC architecture consisting of hardware modules and protocols was developed and implemented. This iNoC provides the possibility to invade communication resources. Through invasion of communication links, certain Quality-of-Service (QoS) guarantees can be given in terms of upper bounds for bandwidth and latency. Besides this elementary invasion capability, various decentralised and self-optimising mechanisms were investigated. Self-embedding, for instance, enables the decentralised hardware-assisted mapping of communication topologies. Rerouting helps to reduce congestion through remapping of connections and through monitoring of the traffic inside the network adapter links can be invaded autonomously (Auto-GS).

In the second funding phase the research will focus on increasing the predictability of the execution properties of concurrent applications. Here, the hardware support inside the iNoC for mapping actor-oriented task models to a NoC is needed. Tighter bounds for communication latency shall be feasible through novel circuit switching concepts. Additionally, other non-functional properties such as security, fault tolerance, and energy consumption will be investigated. Finally, novel NoC topologies (i.e. 3D NoCs) and cache coherence are topics of investigation.

Synopsis

In the first funding phase, general principles of the invasion of NoC resources were investigated and implemented. The iNoC realises the communication infrastructure for invasive architectures and can already give guarantees for throughput and worst-case latency. In Phase II, predictability will, as a main topic, be even more in focus of our collaborative research. Here, Project B5 will investigate circuit-switched networks, which can offer precise bounds on communication latency. Also, the invasive actor-oriented programming model, which will be introduced by Project A1, will be supported by the iNoC. Moreover, other non-functional properties including fault tolerance and security are addressed by Project B5 in the second funding phase. Here, the main goal is to ensure such properties through different layers and levels. Security issues, for example, do not only concern the hardware or the software part of a system. Only in close cooperation with Project C5 will this goal be reached. The same holds for fault tolerance. To ensure a certain robustness against faults, the communication infrastructure as well as computing resources like TCPA and RISC tiles Project B2 , Project B3, Project B4) are involved to find a holistic solution.

Predictability is the topic of one of the four working groups in our CRC/Transregio. Yet Project B5 will contribute as well with research topics to the other three working groups. In the research area of power efficiency and dark silicon , e.g. the iNoC will be enhanced by shutdown mechanisms and low-power techniques. This makes it possible to power down a whole chip region including network resources and processing elements without affecting the communication of the other regions and without preventing global communication. The investigations of region-based cache coherence complements the working group of memory hierarchy. In the first funding phase, coherency was supported only within a single tile. However applications tend to require more processing and/or memory resources than are available within a tile. Commonly, explicit software messages (MPI) which require additional programming effort are used for inter-tile communication. We believe that these alterations can be avoided by enabling hardware supported inter-tile cache coherence. Global coherence does not scale in a cost efficient manner and is not even required for applications with limited degrees of parallelism. Therefore, the goal here is to create flexible cache coherent regions beyond tile borders whilst limiting hardware overheads.

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 communication resources. The reservation of communication resources by applications in the iNoC is realized through dynamically configurable guaranteed service connections.

We investigated protocols and routers that support dynamic link invasion. This also provides the basis for autonomous mapping of communication graphs. The developed router, network adapter, and the protocols support different types of communication that cooperatively share router's resources. As topology for the invasive architecture, a mesh topology was chosen, thus most routers have five input and five output ports (routers at the borders or corners have four and three ports, respectively), which are connected through a crossbar. To increase the NoC's throughput, Virtual Channels (VC) are the state-of-the-art approach to multiplex the physical link. Therefore, every VC has a buffer at every input port and all parts of one flow are directed to the same input buffer. In addition to the data links, dedicated wires between the routers signal in which VC buffer the data should be stored. To prevent the buffers from overflowing a credit-based flow control can be used. Hard QoS guarantees can be given by reserving Guaranteed Service (GS) communication channels while Best Effort (BE) communication channels can be used where no guarantees are required without the need of any channel reservation. Thereby, BE channels may utilise resources that are not occupied by GS at that moment. To realise this, we proposed a weighted round-robin assignment of VCs to local time slots (TS). In this respect, it is possible to specify the needed bandwidth guarantee by a Service Level (SL). In following Figure, an example with concurrent data transmission is shown: C1 is an established GS connection using SL 3, thus, in each router the VC used by the connection is assigned to 3 time slots. Different time slots can be used in each router. C2 is a GS connection using SL 1.

As part of the overall decentralised resource management, we investigated the feasibility of decentralised embedding of communication topologies called self-embedding within the iNoC. The main idea of this approach is that each process embeds its own succeeding tasks with data dependencies, only considering the local view of neighbouring nodes in the NoC. This can be done in parallel in contrast to a centralised approach which has to map the tasks sequentially. Especially for streaming applications and applications with a huge amount of periodical communication data, not only the mapping of the functionality, but also of the communication onto the NoC channels is important. We presented the formal model for algorithms and showed that the decentralised mapping of tree-shaped applications and reservation of bandwidth can compete with central approaches in terms of average network utilisation, but offering a better scalability. The self-embedding functionality is implemented as a hardware component as a part of the iNoC router and communicates with other self-embedding components in other routers over a control network.

Monitor data, which are provided by Project B4, play a crucial role in resource-aware computing. In order to efficiently access the hardware status inside regions, which are only defined during run time, we investigated several mechanisms. Three mechanisms are shown schematically in the following Figure. Each example shows a region of a tile-based architecture.

Mechanism (a) represents a method to collect data within the given region using only point-to-point communication. A separate request is transmitted to each node. The nodes respond by sending the requested information. This mechanism is named Request-Response. Mechanism (b) shows a technique we call Round-Trip. A Hamiltonian cycle through all nodes of the region is used to transfer the request as well as the requested data of the addressed nodes. Mechanism (c) represents a combination of the previous two strategies. Hence, it is called Mixed. The request is transmitted on a Hamiltonian path and the response is transferred directly from each node of the region to the requesting node using unicast communication enabled, e.g. by xy-routing. Compared to Request-Response , the mixed mechanism reduces the NoC utilisation by using one Hamiltonian path for the requests instead of multiple request packets to each node. The results show that the choice of the strategy depends on different parameters such as region size and data set size. Round-Trip and Mixed outperform the straight forward implementation called Request-Response for most cases.

A modular approach is followed to design the network adapter. It consists of a tile interface, the FIFO and the iNoC interface layer. The modular approach shall simplify the connection of the different tile types of our heterogeneous architectures. Only the tile interface layer needs to be replaced depending on the tile type. Inside the network adapter, a mechanism called Auto-GS was researched to automatically detect communication partners which are addressed frequently. After a detection, the network adapter then automatically can setup a GS connection to such nodes to improve the performance of the communication and reduce the energy consumption for communication.

Region-based cache coherence (RBCC) is a concept where a subset of tiles in a large MPSoC system can be grouped into a coherency region. This approach limits the size of data structures in the directories significantly compared to traditional schemes by only tracking tiles within a region, making it scalable for large MPSoCs. The figure below illustrates the normalised savings that can be achieved with RBCC for varying tile counts (N) and region sizes (M_max).

We introduced a programmable coherency region manager (CRM) in every tile. The CRM allows to dynamically setup and remove variably sized coherency regions and administers a coherent view for all tiles within a region. Based on the required regions, every CRM is fed with information that enables a tile to be aware of its valid sharers. The CRM is coupled with a reduced directory structure for book-keeping. To verify our RBCC concept, we developed a highly configurable SystemC-based simulation model. Our experiments demonstrated that operating multiple compute tiles in a coherency region can increase performance by a factor of up to 2.5 compared to a single tile structure with nominally identical computing and memory resources. For hardware evaluation, we have developed and integrated a prototype of the CRM module onto the invasive computing FPGA-based target platform. We plan to run traditional shared memory programming benchmarks spanning multiple tiles enabled with region-based coherence support. We plan to analyse the performance of region-based coherence by varying the size and spatial location of the regions, running multiple applications on overlapping regions, etc. Finally we plan to evaluate the performance of applications running with region-based coherence to that of existing software-(MPI) based schemes

Manufacturing defects and ageing effects are expected to cause permanent faults in future highly integrated technology nodes which are targeted by NoC-based architectures. To deal with permanent faults, the errors need to be localised first. Afterwards, redundant hardware units or routing paths must exist to circumvent the broken nodes and links. In an effort to tackle this challenge, we employ software techniques for the fault detection in an effort to minimise hardware overhead. The concept is based on systematic flooding of the iNoC, or a region of it, by the use of special test packets. These packets are analysed after reception to determine the location of the fault or error. By using a synchronised test pattern generation, the pair of communicating nodes for error localisation is known to the test software. Due to the knowledge about the expected test data, erroneous sections of the iNoC can be identified. Once a fault is detected and located, fault treatment techniques need to be employed. We introduced a lightweight second-layer network (SLN) which takes over the duties of defective routers. This second layer acts as a transparent bypass to circumvent faulty routers. The bypass is activated on demand to form a ring around a defective router. The full implementation of the SLN is shown in figure below.

It can be noted, that the routers in the corner of the mesh can also be bridged with a full ring around them. A configuration for bypassing a single defective router is shown in figure, illustrating the circular flow of packets on the ring. The infrastructure for the second layer consists of switches to enable the injection and ejection of flits from and to the primary network, as well as multiplexers to connect the switches to form the bypass on demand. The evaluation of the SLN shows that 51% of all faults in the complex iNoC design can be detected and localised. Additional analysis exhibited that 100% of link errors can be detected and localised. Depending on the design-time configuration of the second layer network, it can be used to bypass a faulty router with a negligible impact on performance at the cost of an area overhead of only up to 18%.

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

Publications