NoC-based hardware software co-design framework for dataflow thread management

Dataflow models have a long history, from both hardware [20, 21], data structures, system software, and software perspectives [22‐24]. It could be argued they hide behind superscalar processors’ out-of-order engines; are still actively used for digital signal processing circuits in embedded systems thanks to variations around dataflow, such as Synchronous Data Flow [25]; and more recently, explicitly dataflow-inspired constructs have been added to programming languages, e.g., OpenMP [26].

The original dataflow PXM specifies a firing rule: a dataflow actor is ready to fire when all of its input data tokens are present, and there are no remaining output data tokens to be consumed. This rule is relaxed in further iterations of dataflow PXMs, e.g., to allow for general recursion. A dataflow program can be represented as a directed graph, called a dataflow graph (DFG). Its vertices are dataflow actors, and its arcs indicate in which direction data tokens flow from one actor to the other. DFGs naturally expose parallelism, which both hardware and software systems can then exploit.

Since the 1990s, several hybrid von Neumann-dataflow PXMs have been proposed to take advantage of more traditional off-the-shelf high-performance microprocessors, such as e.g., EARTH-MANNA [27, 28], which combines a compiler to write dataflow-inspired programs into C combined with a low-level run-time system. These hybrid systems provide a ‘macro-dataflow’ programming environment to express computations, and then map the resulting generated code to the underlying hardware thanks to a combination of compiler-generated code and run-time system calls.

The last dataflow-inspired architectures include explicit multi-threading (XMT) architecture, which introduces an abstract execution model, where switching from serial to parallel execution is made through explicit spawn/join instructions [29]. Another dataflow-inspired high-performance hardware system is the Maxeler processing platform [30]. Readers can refer to the survey for more [31].

With the rise of massively parallel chip multiprocessing systems, i.e., manycore systems, the early 2010s saw a renewed interest in examining dataflow-based PXMs to exploit the increasing amount of parallelism contained in a single chip, but also between CMPs. One of the resulting PXMs is the Codelet Model [32, 33]. Much like EARTH [28], it is a hybrid von Neumann-dataflow model designed for massively parallel multicore systems. However, it is event-driven: on top of the data tokens of dataflow, hardware and software resources may also be expressed as dependencies to help the system decide how to map the computation on the underlying hardware. Hence, a codelet may only fire if all of its data and resource dependencies are met.

While they are the quantum of execution of the PXM, codelets cannot be called directly by the programmer. Instead, they are stored in a Threaded Procedure. Threaded Procedures are essentially asynchronous functions, and act as a container for a small codelet graph, and a data frame to hold inputs, outputs, and intermediate values shared by the threaded procedure’s codelets. A threaded procedure descriptor can be sent to any cluster of cores, but once it has been assigned to a given cluster to be executed, its codelets can only run on the cores of the selected clusters. This helps maintain data locality, e.g., if the cluster features some cache or scratchpad memory available to all its cores. Codelets have a read-write access to its threaded procedure’s frame, and rely on the programmer and compiler to have produced a well-behaved codelet graph.

On top of defining a way to represent a unit of computation, the Codelet model also defines an abstract machine model. In the model, the target system is comprised of hundreds of cores, grouped into clusters. Each cluster comprises several compute units, and a single synchronisation unit. Each compute unit is equipped with a codelet pool, which can hold one or more codelets ready to run, whereas synchronisation units are tasked with distributing such codelets to the various compute units of their cluster. At the same time, synchronisation units are also in charge of tracking local thread procedure invocations, and must then manage the memory pools tied to them. They must be software-managed to deal with dynamic memory allocation issues. An unknown number of thread procedures (in particular, the data frame sizes vary with inputs, outputs, and intermediate values) will be stored in the pools and can be ‘fed’ with additional thread procedure descriptors from other synchronisation units.

The 2D mesh topology has become popular due to its advantages compared to other alternatives regarding wiring area, power cost, and fault tolerance [34]. The left side of Fig. 2 depicts the typical organisation of 2D mesh-based CMP: processing elements (PEs—white squares) communicate with routers (black squares) which are connected through a 2D mesh (black lines). In such a topology, the active communication elements (i.e., the routers) have five input/output channels each, which map to the four communication directions of the mesh (i.e., north, south, east and west links) and the local communication link with the PE. The right side of Fig. 2 shows an example of a virtual topology mapping, with groups of adjacent PEs communicating through virtual rings (blue lines), which are further connected through a virtual mesh (purple lines). Mapping the physical topology with the desired virtual one requires the underlying routers’ architecture to expose additional functionalities. In particular, links should be enabled/disabled or bypassed, i.e., the traffic flowing in it is directly injected in another link without passing the switching/routing process. In other words, data packets are directly forwarded to the following router. In the right side of Fig. 2, for instance, routers of PE 3 and PE 5 (PEs are numbered in the top-left corner) can disable respectively south and north links, while the router of PE 6 can configure the north link in bypass mode so that its traffic is directly injected in the south link of PE 8. An example of an NoC architecture supporting this kind of dynamic mapping is Panther [35]. Although it allows significant power savings in principle, the entire NoC architecture uses routers based on a conventional microarchitecture, which becomes power hungry (i.e., the majority of the dissipated power is due to the crossbar switch and link drivers) when the number of PEs to connect grows as in manycore. [36] proposed a method to perform high-level mapping of cores onto various NoC topologies based on multiple objective functions. Readers can refer to the survey paper [37], which reviews existing routing and selection techniques for 2D mesh topology considering various NoC-related performance parameters.

For a small number of cores, ring topology is demonstrated to be very effective, requiring a low-radix router (i.e., a packet-switching element with a low number of input/output ports connecting to the other elements of the network). Interestingly, a ring topology can outperform a mesh topology for moderate to high memory access locality-based workloads [38]. Various efforts have been made to connect local and global rings via special routers called bridges to improve scalability together with performance and better energy consumption [16, 39]. Due to scalability and a high level of fault tolerance, 2D mesh topology has become very popular to efficiently connect a moderate number of cores (e.g., Polaris chip [12]). However, 2D mesh topology suffers from space and power trade-offs for a vast number of connected cores [12].

Hybridization has been explored as an effective way to exploit the benefits of each topology at different scales (i.e., when a different number of cores to connect varies). Kim et al. propose using ring-based routers to implement a scalable 2D mesh topology [40]. Despite the relatively lower cost of the proposed packet-switching elements, the network’s physical topology remains fixed, with links kept active in all of these elements, thus leading to low resource usage for lightly used connections and larger overall power consumption.

In [41], the authors proposed a hybrid NoC architecture with high-speed transmission lines. It uses an adaptive routing technique to send long-distance packets. Manzoor et al. proposed a deadlock-free congestion-aware routing algorithm for a 2D mesh network while not using any virtual channels [42]. The proposed algorithm fuses deterministic and partially adaptive algorithms. [43] presents a routing algorithm based on a four-step method for a 2D mesh network. The proposed method collects the congestion information that enhances the regional traffic information. [44] proposed an application-to-cores mapping along with a modified 2D mesh NoC. Next, the proposed approach implements techniques to determine the congestion level of the NoC links dynamically and thus adjust the application-to-cores mapping accordingly. In another work, a Chisel NoC generator is proposed for enabling design exploration and evaluation of heterogeneous NoCs [45].

Hierarchical rings with deflection is a hierarchical ring-based NoC design for improved energy efficiency, where buffers within individual rings are avoided while needing up to four levels of hierarchy to connect a modest number of cores [16]. CSquare proposes a way of clustering routers so that clusters adopt an internal tree-like organisation [46]. The authors showed that this topological design improves throughput while lowering the average latency over mesh-like topologies under the uniform traffic pattern. Transportation network-inspired NoC is another hierarchical ring topology that employs a hybrid packet-flit, credit-based flow control mechanism for better scalability and priority-based arbitration for better performance [47]. It allocates channels (i.e., links) with flit granularity, while buffers are allocated with packet granularity to reduce buffer counts. 2D-HERT is a hierarchical expansion of a ring topology, focusing on optical NoCs [48]. Kilo-NoC is a topology-aware quality-of-service (QoS)-oriented architecture, adopting a low-diameter (i.e., the largest, minimal hop count over all pairs of cores) topology [49]. It provides a service guarantee for applications with reduced power and area costs. It reduces the extent of hardware support to portions of the die, reducing router complexity to support large core counts. In [50], authors present a hybrid architecture where a 2D mesh network is partitioned into several smaller sub-meshes. Next, the sub-meshes are connected using a hierarchical ring interconnect for delivering global traffic. This work uses a bridge module to drive traffic to the different levels of the hierarchy. The addressing and routing scheme has also been modified to support the proposed topology.

Employed PXM allows the construction of the DFG at compile time, explicitly showing data dependencies among threads. The thread context includes the (data) frame and a unique thread identifier. Each thread holds a local storage space (frame) used to receive input data from producer threads and to write intermediate results. It also contains a scheduling slot (SS) counting the number of inputs still required for the execution. To preserve locality and allow for better latency hiding, threads are grouped into asynchronous functions (AFs). As part of the hashing mechanism, the framework dynamically groups cores to form virtual nodes (VNs), forcing threads within an AF to be executed on the same VN. To expose these characteristics at the programming level, the proposed architecture extends the core instruction set architecture (ISA) with a reduced set of dedicated instructions (possibly wrapped by high-level programming language functions, e.g., C/C++) as follows:The compiler can aggregate multiple writes (e.g., dealing with large loops) and use a single DecreaseSS signalling operation to update the corresponding SS field to optimise the execution.

A PE within the current VN is automatically selected and signalled whenever a new thread is spawned. Similarly, whenever a thread creates a new AF, the destination PE is selected within the whole chip. Hence, the creation of a new AF is led back to the scheduling of the root thread of the DFG contained in the AF. Figure 3 shows an example of a simple kernel application consisting of four AFs, each with its DFG. Both AFs and threads are directly managed by the compiler, which is responsible for mapping high-level programming constructs (e.g., #pragma omp for when using OpenMP) with the correct sequence of CreateAF and CreateThread instructions. Figure 3 also shows that AF scheduling requests and writing operations remain well confined to the local VN. By monitoring scheduling slots, the hardware unit automatically fires threads that become runnable without explicit instruction. On the contrary, the execution completion is signalled by the DeleteThread instruction that allows freeing resources held by the thread.

The target CMP-based platform comprises many cores tied to lightweight routers supporting a 2D mesh topology. A core-router complex is referred to as a tile. Figure 4 shows how a 2D mesh NoC connects a large group of tiles covering the entire chip area. Routers are augmented with our (fine-grain) dataflow thread distribution hardware support: a local unit called Thread Dispatcher (TD) manages the threads during their lifetime. In particular, it allocates internal space for storing thread contexts every time new threads are created, removes previously allocated resources whenever threads are complete, and reads from (respectively writes to) associated frames. Since the software controls the behaviour of threads through the extended instruction set, the TD directly interacts with the decoding stage of the PE. We assume that only one thread at a time can be executed in each PE.

We used hashing for thread distribution in a resource-constrained environment. The hashing mechanism must avoid creating hot spots (i.e., assigning a large number of threads to a single PE that can create large resource contention and generate large traffic towards other PEs) in the chip. An imbalance in the load distribution quickly and significantly increases the i.e.power and temperature of the more stressed portion of the chip, thus contributing to a decrease in the overall reliability, which may accelerate device ageing. Load imbalance can also create congestion in the network since some links drive more traffic than others. On the other hand, the hashing mechanism used to distribute the threads must guarantee the locality of computations. To this end, our hashing scheme allows placing a group of dependent threads (i.e., asynchronous function) on the same group of PEs (i.e., VN), while still preserving a fair thread distribution within the VN by randomly selecting PEs. Similarly, the hashing scheme allows the scheduling of AFs randomly on different VNs across the whole chip, avoiding the need to explicitly find an allocation of PEs that minimise the communication distance between producer and consumer threads (in a minimal amount of clock cycles). Furthermore, our PXM implies more than one producer thread can generate input data for a single thread, and producers can be scheduled and executed at different points in time.

Each thread in the system is identified by a unique thread identifier (\(T_{id}\)) over the whole application execution. It is composed of three main fields: the source field, the destination field, and a local counter (CNT). The source and destination fields are in turn, formed by two sub-fields representing the core identifier of the PE (\(C_{id}\)), and the virtual node identifier (\(N_{id}\)). While the content of the source field is fixed for each tile (once the number of cores in each VN has been selected), the content of the destination field is produced at run-time by the hashing function \(H(\cdot )\). These fields allow the system to generate unique identifiers that are conveniently stored in a 64-bit register.

The organisation of the \(T_{id}\) is illustrated in Fig. 5. By passing to the \(H(\cdot )\) module both the size of VNs (\(N_{pe}\)) and the indication of the executed instruction \(I_{ex}\) (i.e., the CreateThread or the CreateAF instruction), it uniquely identifies the PE responsible for the execution of the newly generated thread (i.e., \(\langle N_{id}, C_{id} \rangle _{dst} = H(N_{pe},I_{ex})\)). Once selected, the PE is signalled by sending a message over the network. Since the destination is encoded in the \(T_{id}\), any subsequent operation on the thread can easily be forwarded to its corresponding PE without any calculation. This contributes to the overall speedup of the system.

The basis of our system is a 2D mesh NoC implemented with lightweight ring-based routers (see Sect. 4.2.2). Such routers allow the implementation of a flexible 2D mesh topology on top of four unidirectional rings. An internal table describes how traffic flows in the links. The internal crossbar switch is substituted with four ring stations, each capable of driving network traffic in the same direction or steering it to the opposite dimension. The ring stations are coupled with two additional modules (inter-ring switch – IRS) that are responsible for ejecting traffic travelling in one dimension or injecting traffic in the opposite dimension.

Thread descriptor table (TDT) is a data structure used to manage threads organised in two fixed-size local memory arrays. The total area is comparable to an L1 instruction cache (see Sect. 5.2). It is interesting to note that we may ‘lose’ some information while having the TDT, but we can reclaim some of it because we use scratchpads and not actual caches for the thread frames. Input and intermediate data are stored in the scratchpad memory. Every time the context of a thread is updated, the \(T_{id}\) is used as a search key within the content-addressable memory. In the case of a match, the returned base address of the frame \(F_b\) is added to an offset \(F_o\) to determine the location access (i.e., \(l = F_b + F_o\)). Finally, a priority encoder selects the thread with the lowest \(T_{id}\) among those runnable (\(\textrm{SS} = 0\), see Fig. 5). Every time the selected PE is devoid of free resources, it can access a larger but slower and less energy-efficient memory area called Thread Storage, which is implemented as a 3D stacked DRAM layer². It is organised by banks (one for each PE) representing a larger TDT structure. When a PE receives a new thread, it first selects the entry in the local TDT and compares the SS value of the new thread with the one currently stored. The thread with the highest SS will be swapped to the DRAM memory bank.

Hash scheduling function \(H(\cdot )\) is used to map new threads to PEs for their efficient execution and contains a set of maximum-length linear-feedback shift registers. In our case, the hardware module assigns to the newly created thread the tuple \(\langle N_{id}, C_{id} \rangle _{\textrm{dst}}\), depending on the VN size and the executed instruction. To be effective, the scheduling function \(H(\cdot )\) has to distribute CreateAF and CreateThread requests among the available resources fairly. The effectiveness of the hashing function derives from the ability to avoid collisions, i.e., to limit the number of times two distinct input values result in the same output value for the hashing. In our distributed scheduling scheme, this translates into avoiding different PEs selecting the same destination, given two different \(T_{id}\). In that case, the PEs’ load (i.e., the number of threads to execute) is balanced, thus avoiding the formation of hot spots and increasing the overall system reliability.

A good hash function must provide determinism, meaning that it has to provide the same set of hash values for the same set of input keys. More importantly, hash functions must exhibit uniformity: given a set of n input keys and m output buckets, each bucket must show a load \(\lambda = \frac{n}{m}\). It directly translates to the same probability for each output bucket to be selected, thus limiting the number of collisions. Finally, since we are not considering cryptographic applications, it is not strictly required for the function being non-invertible. Indeed, it is more desirable to keep hardware implementation efficient regarding area and power consumption.

The mentioned hashing scheme offers good results while maintaining a low area overhead and preserving the capability of dynamically changing VN sizes (see Sect. 5 for more details). Another important aspect of our scheme is that it works in an entirely distributed fashion, meaning that there is no single point of failure, as is desired in a system potentially equipped with thousands of PEs.

The ISA extension we presented in Sect. 4.1.1 has been further extended with a few instructions to manage the reconfiguration phases and to monitor the links’ traffic. The combination of both proposed ISA extensions allows us to deal with a SDNoC. As in the case of instructions used to manage the dataflow thread distribution. Here, each instruction can be conveniently wrapped by a function in standard high-level languages (e.g., C/C++) as follows:Each router is equipped with a \(16\times 1\) SRAM containing the switch table (ST). It describes how traffic entering a link can flow into other links. More precisely, the memory content is logically arranged as a \(4\times 4\) matrix. Each row of the matrix corresponds to an input link, while the four columns in a row represent output links. An element \(s_{i,j} \in ST\) is set to one if the traffic travelling in the direction i (e.g., west) can be forwarded on the direction j (e.g., north). The content of the ST, and the values of bits enabling the bypass and power-gating logic (respectively BP and PG bits), are stored in memory in the form of a bitstream. Every time the SetRouterCfg instruction is executed, it generates a corresponding message sent to a specific router. The destination router directly accesses the memory location (actually, the PE performs this operation), where the configuration is stored, by adding a fixed offset to the basic address (Rs). The operation can be parallelized if multiple routers need to be configured.

Figure 6 merges the benefits of lightweight and scalable router microarchitecture with those of dynamic reconfiguration [40, 52]. Four separate rings allow communication to flow in the north, south, east and west directions, while specific bits control the status of each link. The communication in each of the four directions (i.e., north (N), south (S), east (E), and west (W)) is ensured by dedicated ring stations (RSs), which are essentially responsible for forwarding the traffic coming from the injection port (inj) to the output port or the ejection port (ejc). An RS manages the traffic from a physical ring in the same direction. During the configuration phase via the customised instruction, the links can be set in three different modes: normal, bypass (BP), or power-gated (PG). Bypass and power-gated modes disable links partially or fully, thus allowing the network to save power and implement different topologies.

The original router design uses a single inter-ring switch (IRS) to switch traffic travelling horizontally (i.e., E-to-W, or from W-to-E) to one of the vertical directions (i.e., N-to-S, or from S-to-N), but prevent the opposite traffic steering (i.e., from vertical to the horizontal direction) [52]. This choice was imposed by implementing the X-Y routing algorithm on top of the ring-based architecture. Although this organisation ensures chip-level communication within the physical mesh, it does not support mapping virtual topologies.

To compensate, we provide a more flexible architecture: two symmetrical IRS, i.e., an X2Y switch and a Y2X switch allow the traffic to spill from horizontal directions to vertical ones, and vice-versa. To this end, the design uses the X-Y deterministic routing algorithm without the restriction of forwarding traffic first horizontally and then vertically, i.e., packets can be routed alternatively on the X and Y dimensions as a first routing step. Each IRS is composed of two multiplexers (MUXs). One is responsible for selecting which of the inputs (e.g., traffic coming from the local PE, E-to-W direction, or W-to-E direction) has to be transferred to the injection ports of the RS in the opposite dimension (e.g., the traffic is injected in the N-to-S or the S-to-N direction). The second one selects which traffic to present to the output port (i.e., this is the spill point, where traffic coming from the network is presented to the PE). For instance, the X2Y switch can present to the output port of the traffic coming from the ejection port of the RS-W and RS-E (see Fig. 6). The other two separate ports in each IRS (highlighted in red) control their state, thus allowing for selectively power-gating one of the two internal MUXs or both. Considering the X2Y switch (similar to the Y2X switch), the MUX connected to the output port can be disabled only when the RS-W and RS-E are in power-gated mode. The MUXs are responsible for forwarding the traffic in the opposite dimension are power-gated when both RS-N and RS-S are in power-gated mode. Similarly to IRS, each RS is provided with two additional ports controlling the station’s state. A power-gated port (highlighted in red) entirely disables the RS, dropping traffic at the input port. A bypassed port (highlighted in blue) partially disables the RS, allowing the traffic arriving at the port of entry to be directly injected into the output link. These ports are controlled by two corresponding configuration bits: PG and BP. While the configuration of the IRS depends on the state of the RS controlling them, the state of an RS can be set independently from the others. Furthermore, the power-gated mode is dominant in the bypass mode, meaning that the configuration \(\langle BP, PG \rangle = \langle 1,1 \rangle\) leads the RS to be set with the power-gated mode.

The internal organisation of an RS is depicted in Fig. 7. Traffic arriving at the input port (IN) can continue travelling in the same direction or be extracted. This decision is implemented within the demultiplexer (DMUX) as part of the routing logic and requires only analysis of the destination field of incoming packets. Every time input traffic has to be ejected (i.e., extracted by the local PE or deflected in the opposite dimension), it is temporarily stored in a local buffer (S-BUF). Similarly, the buffer R-BUF temporarily stores packets that continue to flow in the same direction. It is worth noting that both buffers can be tiny compared to input buffers in conventional routers. The limited storage space required by the buffer is mainly due to the adoption of a traffic prioritisation policy, which allows the RS to privilege traffic that flows in the same direction as the one coming from the injection port. This policy is implemented as part of the selection mechanism of the output MUX. It is also worth noting that multiple R-BUF and S-BUF buffers can be used to support virtual channels (VCs). Another MUX (i.e., BP-MUX) selects which traffic to inject on the output link (OUT) when the RS is set in the bypass mode. In this mode, both the internal buffers, the input DMUX, and the output MUX is disconnected from the power source (power-gated). At the same time, traffic on the injection port is directly injected into the output link. In this way, the RS can save energy and limit the packet traversal delay. Interestingly, in this case, the drivers on the output link are still fully active. On the contrary, whenever the RS is set to power-gated mode, all internal components and link drivers are switched off. Four additional OR gates ensure that BP or PG bits control power-gate and bypass functionality for the internal components. As already mentioned, the PG bit overrides the BP signal. Finally, a counter is available for each output link: depending on the granularity at which traffic is monitored and the frequency of captured events, the size of the counter can be varied from small (16-bits) to large (64-bits). Every time a packet (flit) traverses the link, the counter is automatically incremented. A single bit of the control router logic allows selecting the granularity at which traffic is monitored (i.e. if counters are updated when packets or single flits traverse the links). Figure 8 shows an example of mapping a hierarchical topology (i.e., local rings and a global mesh) upon a \(4\times 4\) physical 2D mesh.

Figure 10 depicts the internal organisation of the mesh router, while Table 1 provides its main architectural characteristics. The router employs an \(8\times 8\) crossbar switch to support global traffic movement in both dimensions (i.e., N-S and E-W) and traffic exchange with local ringlets. Four channels are used to drive traffic within the 2D mesh network (i.e., global traffic). The other four input channels are used to steer traffic to/from the ringlets (i.e., local traffic). Each ringlet is associated with a dedicated channel, so the traffic exchange with the master ring switch happens through this dedicated link. In general, routers can have a significant number of VCs to hold a large amount of incoming traffic. For each input link, two VCs are introduced, which allow for better QoS support and also prevent deadlocks. In Figure 10, the path taken by the control information carried by the packet headers is highlighted in red, with blue lines showing the control signals activated by the internal router stages.

Conversely, output channels do not use VCs, thus contributing to saving power. Large buffer requirements and QoS overheads reduce the ability to support many cores with an efficient area and energy usage [49]. Also, a large number of VCs consume a huge chunk of energy since more input buffers are needed to keep traffic separated. It is worth mentioning that buffers are one of the largest leakage power sources in the router. Their power consumption can represent up to 64% of the total router’s leakage power [53], and also a significant amount of dynamic power [54].

Interestingly, single-flit packets represent a large segment of the network traffic for real applications [55]. Following this, the router is optimised for managing a single flit packet. The design selects a packet length of 42-bits, where 32-bits are used to transport data, and the remaining 10-bits are devoted to carrying header information. The packet size has been chosen considering the performance improvements [56] and also the overhead, i.e., increasing the packet size leads to a quadratic increment of the internal crossbar switch overhead.

The internal router is organised into a four-stage pipeline: routing stage, flow-control stage, VC allocation stage, and switch allocation stage. However, to reduce the latency of the packets to traverse the router, the proposed design has been optimised so that the operations performed by the four stages can happen in parallel, thus reducing the overall latency to one cycle. The entire packet transfer can be restricted to a single cycle thanks to the following design choices: (i) the adoption of the store-and-forward mode; (ii) the optimisation of the routing logic for processing a single-flit packet with a reduced overall size. These design choices lead to a router architecture with a latency of one cycle in most cases (see sect. 5.4). Wormhole and virtual-cut-through are not chosen because, in this case, the routing is parallel, and the entire packet will be routed out simultaneously. Hence, both of them do not offer any advantage compared to the store-and-forward approach. The employed routing mechanism is based on the X-Y dimension order routing (XY-DoR) algorithm since it provides a simple implementation with a deterministic routing latency. By decoupling the traffic between local ringlets and 2D mesh, the probability of congestion in the 2D mesh level becomes negligible, so the need for an adaptive algorithm disappears [37].

In particular, the routing logic with the flow-control module is fused. A speculative allocation technique for both the VC allocation stage (VCA) and the switch allocator stage (SA) has also been implemented. If the pre-arbitration fails, the packet is buffered while VCA and SA arbitration are performed sequentially. In that case, the latency increases up to four cycles. The timing of the proposed 2D mesh router in the event of pre-arbitration success is shown in Fig. 11a, while the event of failure is represented in Fig. 11b. Every time there is an incoming packet, the following operations are performed by the router’s modules:

A bidirectional ring is implemented upon the structure of a ring switch (RSW) to achieve high performance while keeping power consumption low. An RSW comprises two main MUXs that manage the traffic within the ring. An RSW drives traffic within the ring and steers it towards a 2D mesh router or local PE. Figure 12 depicts the microarchitecture of the RSW. The microarchitecture has incorporated buffers (similar to VCs), which allow traffic management going to/coming from the 2D mesh router.

To avoid complex control logic, an RSW prioritises the traffic travelling in the same dimension (i.e., traffic that remains within the ring and moves in the same direction). Prioritisation also helps to reduce the size of internal buffers (buffers Buf-1 and Buf-2, see Fig. 12). In particular, one of the two directions is selected with high priority, thus moving first in the RSW. The prioritisation mechanism is implemented directly in the control logic of input-output MUXs.

The interface with the local PE is implemented using a dedicated buffer (i.e., Buf-3), which is written by the PE and read by the RSW (i.e., the PE injects traffic in the ring). The buffer is accessible by PE within its address space. Similarly, traffic that is ejected by the ring is collected temporarily in a local output buffer, from where the PE can extract the payload. The interface with the 2D mesh router is implemented similarly: traffic injected into the 2D mesh is stored temporarily in a small buffer, from where it is transferred to the router’s input link. Traffic ejected from the 2D mesh router is moved within a VC buffer. When the 2D mesh router tries to access RSW, two VCs are implemented to support resource contention better. From this viewpoint, the RSW implements a round-robin selection strategy between the two VCs to keep control logic simple. When packets move within the ring or between the ring and the 2D mesh router, the following steps are performed by the RSW:It is worth noting that, to minimise the number of resources used by routing structures, RSW modules that are not connected to the 2D mesh router have the same structure depicted in Fig. 12, except for the interface with the router. In that case, this interface has been removed to save area and power.

In the proposed design, for the implementation of a single block unit (i.e., four ringlets and associated modified 2D mesh router), the total number of used Lookup Tables (LUTs), flip-flops (FFs) and block random access memories (BRAMs) is 2434, 2768 and 48 respectively. Specifically, four ringlets consume 1076 LUTs, 1800 FFs and 40 BRAMs. In Table 2, the resource utilisation and power consumption between a standard 2D mesh router and the proposed design are compared. Unlike a typical router, the modified one can support sixteen cores via four ringlets with around \(2\times\) increment in the resource consumption compared to a traditional mesh router and with a less than 0.4 W increment of power consumption. Regarding power consumption, the values of static power (due to leakage currents and which depend on the manufacturing process) and dynamic power are presented separately. Results show that the proposed design consumes 1.0 mW and 28.0 mW more, respectively, regarding static and dynamic power. This result is strictly related to a large number of internal memory access by the proposed design.

Next, we compare the resource (area) utilisation of our single block (connecting 16 PEs in total) with the publicly available FPGA-friendly NoC generator CONNECT [60]. It is worth noting that CONNECT only works in 150 MHz, and CONNECT consumed 9600 LUTs, 4576 FFs and 1728 Distributed RAMs (DRAMs), each 64-bits in size to support 16 PEs. In comparison, the proposed model used 2434 LUTs, 2768 FFs and 48 BRAMs, each 36-Kbits in size. It is essential to highlight that such smaller DRAM elements have a higher cost regarding wires than BRAMs. We can see our design saves a substantial number of LUTs and FFs compared to CONNECT⁴.

Furthermore, we used 64 modified mesh routers and 256 ringlets to support 1024 PEs. From Table 3, we can see that our model is very resource efficient compared to the standard flattened 2D mesh design. The NoC subsystem consumes up to 155776 LUTs, 177152 FFs and 3072 BRAM blocks (four FPGA devices were used, interconnected to each other through dedicated links). For connecting sixteen cores (one block), our design can save (on average) 2% LUTs, 0.7% FFs and 2.2% of BRAM. It might seem a small saving when the design is scaled to 1024 cores, then the total average resource-saving (over all the four FPGAs) increases to 129.3% for LUTs, 47.2% for FFs and 139.3% for BRAMs.

Figure 15 presents the power consumption comparison between the proposed model and the standard 2D mesh. For one topology block (16 PEs), the power consumption is 0.399 W and 0.492 W, respectively, for the mesh router and the ringlet. However, as the network’s size grows, the ringlets’ total power consumption starts to dominate. For instance, for 16 topology blocks (i.e., 256 cores), the power consumption of routers is 1.276 W while the 64 ringlets consume 2.703 W, which is more than \(2\times\) the total router energy consumption. Following this trend, for a 1024-core configuration, all the ringlets consume around \(2.5\times\) of the entire router’s power consumption. Apart from that, for a network size of 16 cores, the proposed design and the 2D mesh consume almost the same amount of power. However, as the network grows, the 2D mesh consumes more power. For instance, with a \(16\times 8\) cores configuration, the proposed model consumes 2.4 W while the conventional design consumes 4.5 W. The situation worsens when it touches 32.8 W for connecting 1024 cores, which represents \(141.26\%\) relatively more power compared to the proposed design.

Figure 16a,b,c show the average packet latency as a function of the four injection rates when the three different traffic patterns are used. Bars show that the network latency increases with the increased size of the injection rate, and the increase of the network size. Overall, the proposed system offers scalable performance with increasing network configuration. Because of the low injection rates (i.e., \(I_r = \{0.25, 0.50\}\)), the latency for each traffic pattern remains very consistent with the others. When increasing the injection rate up to \(I_r = 0.75\) packets/cycle and using the bit-reversal traffic pattern, the latency is minimised. The worst case for the packet latency is represented by the transpose traffic pattern with an injection rate of 1.00 packets/cycle.

When comparing the proposed architecture with conventional 2D mesh, it was found that for all three traffic patterns, the proposed design outperforms traditional NoC design (by keeping the latency low) thanks to the traffic localisation inside the ringlets. Specifically, analysing the behaviour of the 2D mesh NoC, it is found that the 2D mesh design is very consistent for latency increments for all the cases. At the same time, it also has its largest latency for the transpose traffic pattern with the injection rate of \(I_r = 1.00\) packets/cycle (similar to the proposed). For all three traffic patterns, the proposed architecture outperforms the standard 2D mesh by \(\approx 10\%\) for the smallest network configurations (i.e., 16 cores) and \(\approx 67\%\) for 1024 cores.

We also compared how the proposed hybrid NoC model performed while scaling up the network size. We have presented the average latency (averaging over all three traffic patterns considering four types of injection rates) versus the network size in Fig. 17. In all cases, standard 2D mesh NoC increases latency, while the latency increment in the proposed NoC comparatively is very low. The minimum latency saving is \(10\%\) for the smallest network size, and as the network size increases, the proposed model improves its performance. Proposed hybrid NoC model’s latency improvements climb up more than \(100\%\) for 16x32 and 16x64 network sizes.

Figure 18a,b,c show the NoC throughput for all three traffic patterns. Like latency, the network throughput is consistent with the offered packet injection rate. In the proposed design, the average throughput increases as the number of PEs increases. From this viewpoint, by analysing the number of packets delivered per cycle, an increase of the \(2\times\) factor with the increase in the number of PEs in the network has been observed. For instance, with an injection rate equal to \(I_r = 1.00\) packets/cycle and a uniform random traffic pattern, the average throughput increases from 12 packets/cycle for a single block unit (i.e., 16 cores) to 22 packets/cycle for two block units (i.e., 32 cores). Similarly, for a configuration with 512 cores, the average throughput is 344.5 packets/cycle, while it increases up to 680 packets/cycle for a 1024-core configuration. Again, it represents approximately an improvement of a \(2\times\) factor with the network size doubling. This trend is also followed by the proposed design when other traffic patterns are considered. It clearly shows that the proposed NoC architecture is capable enough to offer higher performance and scalability compared to traditional 2D mesh. A similar trend in 2D mesh throughput has also been observed. The proposed design has performed better for the transpose traffic pattern⁵, when the injection rate is low (i.e., \(I_r = \{0.25, 0.50\}\) packets/cycle). For an injection rate equal to 0.75 packets/cycle, the proposed design performed well for all the traffic patterns. The design shows the best throughput for transpose traffic patterns for the largest network configuration (i.e., 1024 cores). However, considering the worst injection rate case, it is worth noting that the best throughput is achieved with uniform-random traffic, while the traditional 2D mesh topology did not demonstrate a similar consistency among the patterns.

These results clearly show that the proposed design can improve the performance of the NoC regarding higher throughput and lower average latency compared to the traditional 2D mesh topology. The capability of this design to sustain such performance also with high injection rates and random traffic patterns (which represent a critical pattern) can be mainly ascribed to the hierarchical organisation of the network.

Finally, we compared how the proposed hybrid NoC model performs (throughput) while scaling up the network size. We have presented the average throughput (averaging over all three traffic patterns considering four types of injection rates) versus the network size in Fig. 19. It can be seen that in all cases, the proposed NoC outperform traditional 2D mesh. The advantage can be counted in the percentage scale from \(3.24\%\) for 16x4 network size to \(9.95\%\) for 16 x 2 network size. The proposed design has shown robust performance by improving latency and throughput.