Search

2D-NoCs have been the mainstream approach used to interconnect multi-core systems. 3D-NoCs have emerged to compensate for deficiencies of 2D-NoCs such as long latency and power overhead. A low-latency routing algorithm for 3D-NoC is designed to accommodate high-speed communication between cores. Both simulation and analytical models are applied to estimate the communication latency of NoCs. Generally, simulations are time-consuming and slow down the design process. Analytical models provide, within a fraction of the time, nearly accurate results which can be used by simulation to fine-tune the design. In this paper, a high performance and adaptive routing algorithm has been proposed for partially connected 3D-NoCs. Latency of the routing algorithm under different traffic patterns, different number of elevators and different elevator assignment mechanisms are reported. An analytical model, tailored to the adaptivity of the algorithm and under low traffic scenarios, has been developed and the results have been verified by simulation. According to the results, simulation and analytical results are consistent within a 10 percent margin. [ABSTRACT FROM AUTHOR]

In modern many-core architectures, advanced on-chip networks provide the means of communication for the cores. This greatly complicates the design and verification of the cache coherence protocols deployed by those cores. A common approach to deal with this complexity is to decompose the whole system into the protocol and the network. This decomposition is, however, not always possible. For example, unexpected deadlocks can emerge when a deadlock-free protocol and a deadlock-free network are combined. This paper proposes a compositional methodology: prove properties over a network, prove properties over a protocol, and infer properties over the system as a whole. Our methodology is based on theorems that show that such decomposition is possible by having sufficiently large local buffers at the cores. We apply this methodology to verify several protocols such as MI, MSI, MESI and MEUSI running on top of advanced interconnects with adaptive routing. [ABSTRACT FROM AUTHOR]

Biased-Temperature-Instability (BTI) aging mechanism reduces Static-Noise-Margin (SNM) of SRAM cells. This leads to a higher Soft-Error-Rate (SER), lower reliability, and lower SRAMs’ stability in FPGAs. SNM partially improves by leveraging the recovery phase of BTI through flipping SRAM content. We propose STABLE, a three-step post-synthesis stress-aware technique, in order to reduce the impact of BTI-induced SNM reduction in FPGA Look-up-Tables (LUTs) using the SAT-based Boolean Matching (BM) algorithm. STABLE partitions Data-Flow-Graph (DFG) of the implemented design into different cones. First, the SAT-based BM algorithm finds a new configuration for each cone while their functionalities are preserved and all SRAMs are flipped. Second, cones that did not pass the first step can benefit from unused SRAMs in their partially-used LUTs for storing the flipped configurations of such LUTs. Finally, flipped configurations of fully-used LUTs are stored in the closest unused LUTs. The main configuration of the implemented FPGA design is swapped by the new flipped configuration, periodically. Our extensive experimental analysis demonstrates 69 and 70 percent on average improvements in the SNM reduction () and the SER increase ( $\Delta SER$), respectively. Since the proposed methodology is deployed after the FPGA placement and routing of the application, the overhead is negligible. [ABSTRACT FROM PUBLISHER]

Fault-tolerant minimal routing algorithms aim at finding a Manhattan path between the source and destination nodes and route around all faulty nodes. Additionally, some non-faulty nodes that are helpless to make up of a fault-tolerant minimal path should also be routed around. How to label such non-faulty nodes efficiently is a major challenge. State-of-the-art solutions could not address it very well. We propose a path-counter method. It can label every node that are helpless to make up of a fault-tolerant minimal path with low time complexity. By counter the number of fault-tolerant minimal paths, it can: support arbitrary fault distribution, check the existence of fault-tolerant minimal paths, not sacrifice any available fault-tolerant minimal paths. [ABSTRACT FROM AUTHOR]

Cache coherence plays a major role in manycore systems. The verification of deadlocks is a challenge in particular, because deadlock freedom is an emerging property. Formal methods often decouple verification of the protocol from verification of the communication interconnect. Modern communication fabrics, however, become more advanced and include a network topology, routing, arbitration, synchronization, and more. In this paper, an integrated approach is proposed that allows cross-layer verification of both the cache coherence protocol and the communication fabric all at once. An automated methodology for deriving cross-layer invariants is proposed. These invariants relate the state of the application-layer protocols to en route packets in the communication fabric. Using the invariants, we derive formal proofs of deadlock-freedom for two case studies: a directory-based MI protocol in a 2D mesh, and a ring-based snoopy protocol in a 2D torus. Additionally, we show that our methodology can be used to derive the smallest possible queue sizes that ensure absence of deadlocks. Our methodology is generally applicable and shows promising scalability. [ABSTRACT FROM PUBLISHER]