Why verification issues in network-on-chip (NoC) design

Within the quickly evolving semiconductor business, protecting tempo with Moore’s Legislation presents alternatives and challenges, notably in system-on-chip (SoC) designs. Notably, the variety of transistors in microprocessors soared to an unprecedented trillion.

Due to this fact, as trendy purposes demand rising complexity and performance, enhancing transistor utilization effectivity with out sacrificing power effectivity has grow to be a key purpose. Thus, the network-on-chip (NoC) idea has been launched, an answer designed to handle the constraints of conventional bus-based methods by enabling environment friendly, scalable, and versatile on-chip knowledge transmission.

Designing an NoC entails defining necessities, deciding on an structure, selecting a routing algorithm, planning the bodily structure, and conducting verification to make sure efficiency and reliability. As the ultimate checkpoint earlier than a NoC will be deemed prepared for deployment, a impasse/livelock-free system will be constructed, rising confidence in design verification.

On this article, we are going to dive deeper right into a complete methodology for formally verifying an NoC, showcasing the approaches and methods that guarantee our NoC designs are sturdy, environment friendly, and able to meet the challenges of recent computing environments.

05.01.2024

04.18.2024

04.18.2024

Emergence of network-on-chip

NoCs have revolutionized knowledge communications inside SoCs by organizing chip parts into networks that facilitate the simultaneous transmission of knowledge by way of a number of paths.

The community consists of assorted parts, together with routers, hyperlinks, and community interfaces, which facilitate communication between processing parts (PEs) resembling CPU cores, reminiscence blocks, and different specialised IP cores. Communication happens by way of packet-switched knowledge transmission the place knowledge is split into packets and routed by way of the community to its vacation spot.

One overview of the complexity of SoC design emphasizes the combination of a number of IP blocks and highlights the necessity for automated NoC options throughout totally different SoC classes, from primary to superior. It advocates utilizing NoCs in SoC designs to successfully obtain optimum knowledge switch and efficiency.

On the coronary heart of NoC structure are a number of key parts:

1. Hyperlinks: Bundles of wires that transmit alerts.
2. Switches/routers: Units routing packets from enter to output channels primarily based on a routing algorithm.
3. Channels: Logical connections facilitating communication between routers or switches.
4. Nodes: Routers or switches inside the community.
5. Messages and packets: Items of switch inside the community, with messages being divided into a number of packets for transmission.
6. Flits: Circulation management models inside the community, dividing packets for environment friendly routing.

Architectural design and circulate management

NoC topology performs a vital position in optimizing knowledge circulate, with Mesh, Ring, Torus, and Butterfly topologies providing varied benefits (Determine 1). Circulation management mechanisms, resembling circuit switching and wormhole circulate management, guarantee environment friendly knowledge transmission and decrease congestion and latency.

Determine 1 The topology of an NoC performs an vital position in optimizing knowledge circulate, as proven with Mesh and Ring (prime left and proper) and Torus and Butterfly (backside left and proper). Supply: Axiomise

Position of routing algorithms in NoC effectivity

As we delve into the complexity of NoC design, one integral side that deserves consideration is the routing algorithm, the brains behind the NoC that determines how packets transfer by way of the advanced community from supply to vacation spot. They should be environment friendly, scalable, and versatile sufficient to adapt to totally different communication wants and community situations.

A few of the widespread routing algorithms for network-on-chip embrace:

1. XY routing algorithm: It is a deterministic routing algorithm normally utilized in grid-structured NoCs. It first routes to the vacation spot columns alongside the X-axis after which to the vacation spot rows alongside the Y-axis. It has some great benefits of simplicity and predictability, but it surely might not be the shortest path and doesn’t accommodate hyperlink failures.
2. Parity routing algorithm: This algorithm goals to scale back community congestion and enhance fault tolerance of the community. It avoids congestion by selecting totally different paths (primarily based on the parity of the supply and vacation spot) in numerous conditions.
3. Adaptive routing algorithms: These algorithms dynamically change routing selections primarily based on the present state of the community (for instance, hyperlink congestion). They’re extra versatile than XY routing algorithms and might optimize paths primarily based on community situations, however they’re extra advanced to implement.
4. Shortest path routing algorithms: These algorithms discover the shortest path from the supply node to the vacation spot node. They’re much less generally utilized in NoC design as a result of calculating the trail in real-time will be expensive, however they can be used for path pre-computation or heuristic adjustment.

Benefits of NoCs

1. Scalability: As chip designs grow to be extra advanced and incorporate extra parts, NoCs present a scalable answer to handle interconnects effectively. They facilitate the addition of latest parts with out considerably impacting the present communication infrastructure.
2. Parallelism: NoCs allow parallel knowledge transfers, which may considerably enhance the throughput of the system. A number of knowledge packets can traverse the community concurrently alongside totally different paths, decreasing knowledge congestion and enhancing efficiency.
3. Energy consumption: By offering shorter and extra direct paths for knowledge switch, NoCs can scale back the chip’s general energy consumption. Environment friendly routing and switching mechanisms additional contribute to energy financial savings.
4. Improved efficiency: The flexibility to handle knowledge visitors effectively and decrease bottlenecks by way of routing algorithms enhances the general efficiency of the SoC. NoCs can adapt to the various bandwidth necessities of various IP blocks, offering optimized knowledge switch charges.
5. High quality of service (QoS): NoCs can help QoS options, guaranteeing that vital knowledge transfers are given precedence over much less pressing communications. That is essential for purposes requiring excessive reliability and real-time processing.
6. Flexibility and customization: The pliability and customization of the NoC structure is basically because of its means to make use of a wide range of routing algorithms primarily based on particular design necessities and utility eventualities.
7. Alternative of routing algorithm: Routing algorithms in an NoC decide the community path of a packet from its supply to its vacation spot. The selection of routing algorithm can considerably impression the efficiency, effectivity, and fault restoration of the community.

NoC verification challenges

Designing an NoC and guaranteeing it really works per specification is a formidable problem. Energy, efficiency, and space (PPA) optimizations—together with purposeful security, safety, and impasse and livelock detection—add a big chunk of additional verification work to purposeful verification, which is generally centred on routing, knowledge transport, knowledge integrity, protocol verification, arbitration, and hunger checking.

Deadlocks and livelocks could cause a chip respin. For contemporary-day AI/ML chips, it might price $25 million in some circumstances. Constrained random simulation methods usually are not ample for NoC verification. Furthermore, simulation or emulation can’t present any ensures of correctness. So, formal strategies rooted in proof-centric program reasoning are the one means of guaranteeing bug absence.

Formal verification to the rescue

Industrial-grade formal verification (FV) depends on utilizing formal property verification (FPV) to carry out program reasoning, whereby a requirement expressed utilizing the formal syntax of System Verilog Assertions (SVA) is checked in opposition to the design mannequin through an clever state-space search algorithm to conclude whether or not the meant requirement holds on all reachable states of the design.

This system reasoning effort terminates with both a proof or a disproof, producing counter-example waveforms. No stimulus is generated by human engineers, and the formal verification know-how mechanically generates virtually an infinite set of stimuli solely restricted by the scale of inputs. This side of verifying designs through proof with none human-driven stimulus and with virtually an infinite set of stimuli is on the coronary heart of formal verification.

It provides us the power to select corner-case points within the design in addition to choose nasty deadlocks and livelocks lurking within the design. Deep interactions in state area are examined shortly, revealing control-intensive points within the design because of concurrent arbitration and routing visitors within the NoC.

With NoCs that includes quite a few interconnected parts working in tandem, simulating the complete vary of potential states and behaviors utilizing constrained-random simulation turns into computationally burdensome and impractical. It’s as a result of intense effort wanted for driving stimuli into the NoC that’s wanted to unravel the state-space interplay, which isn’t simply potential. This limitation undermines the reliability and precision of simulation outcomes.

Compelling benefits of NoC architectures tout the advantages of integrating FV into the design and verification course of utilizing easy-to-understand finite state machine notations and utilizing protocol checkers developed for FV in chip and system integration testing will increase confidence and aids error detection and isolation.

The effectiveness of this strategy and the challenges of verifying advanced methods with giant state areas are emphasised when in comparison with conventional system simulation successes.

An NoC formal verification methodology

Within the advanced means of chip design verification, reaching simplicity and effectivity amid complexity is the important thing. This journey is guided by way of syntactic and semantic simplification and revolutionary abstraction methods.

Along with these primary methods, utilizing invariants and an inside assumption assurance course of additional accelerates proof occasions, leveraging microarchitectural insights to bridge the hole between testbench and design below take a look at (DUT). This advanced verification dance is refined by way of case splitting and situation discount, breaking down advanced interactions into manageable checks to make sure complete protection with out overwhelming the verification course of.

Symmetry discount and structural decomposition handle verification challenges arising from the advanced habits of huge designs. These strategies, together with inference-rule discount and initial-value abstraction (IVA), present a path that successfully covers each potential situation, guaranteeing that even probably the most daunting designs will be confidently verified.

Fee circulate and hopping methods present revolutionary options to handle the circulate of messages and the complexity launched by deep sequential states. Lastly, black-box and cut-pointing methods are employed to simplify the verification surroundings additional, eliminating inside logic indirectly topic to scrutiny and focusing verification efforts the place they’re most wanted.

By means of these subtle methods, the purpose of an intensive and environment friendly verification course of turns into a tangible actuality, demonstrating the state-of-the-art of recent chip design and verification strategies.

Safeguarding NoCs in opposition to deadlocks

When establishing NoCs, it’s vital for channels to be unbiased, but it surely’s not straightforward to make sure of this. Dependencies between channels can result in troublesome deadlocks, the place the complete system halts even when only one element fails.

Formal verification additionally contributes to fault tolerance, essential in NoCs the place quite a few parts talk. When a element fails, it’s vital to grasp how shut the system is to a everlasting impasse.

Formal verification exhaustively explores all potential system states, providing the perfect means to make sure fault tolerance. With the fitting strategy, weaknesses of an NoC will be recognized and addressed. Catching them early on can save the costly respin.

Optimizing routing guidelines to go well with the wants is widespread and significant for efficiency, however it may be difficult and onerous to completely take a look at in simulation. A whole lot of latest take a look at circumstances might emerge simply by introducing one new routing rule.

So, modelling all of the optimizations in formal verification is essential. If completed correctly, it might catch nook case bugs shortly or show that optimizations behave as anticipated, stopping sudden points.

Within the subsequent part, we describe at a excessive stage how some bugs will be caught with formal verification.

Formal verification case research

Message dependence brought on impasse

A bug originated from a flaw within the circulate management mechanism the place each request and response packets shared the identical FIFO. On this situation, when a number of supply ports provoke requests, the circulate management methodology results in a impasse. For example, when supply port 0 sends a request reqs0, consisting of header flit h0req, physique b0req, and tail t0req, it will get moved efficiently.

Subsequently, the response resps0 manufactured from (h1resp, b1resp, t1resp) meant additionally for supply port 0 arrive, it causes no subject. Nonetheless, when a subsequent request reqs2 from supply port 2 with header flit h2req, physique b2req, and tail t2req entered the FIFO, solely its header and physique transfer ahead, however the tail is blocked from being sampled within the FIFO because the response’s header h2resp has blocked the tail t2req as a result of they arrive in the identical clock cycle.

Consequently, supply port 2 was left ready for the tail t2, and located itself blocked by the response header, leading to a impasse. In the meantime, supply port 1, additionally ready for a response, would by no means get one, additional exacerbating the impasse scenario. This impasse situation paralyzed the complete NoC grid, highlighting the vital flaw within the circulate management mechanism.

Determine 2 Dependence between request and response causes impasse. Supply: Axiomise

Routing error brought on impasse

Within the context of the beforehand talked about circulate management methodology, every supply port awaits a response after sending a request. Nonetheless, a impasse arises because of a flaw within the routing operate. When a request is mistakenly routed to an incorrect goal port, triggering the assertion of the “wrong_dest” sign, the packet is discarded. Consequently, the supply port stays in a state of impasse, unable to proceed with additional requests whereas awaiting a response that may by no means arrive.

Determine 3 A impasse within the circulate is brought on by a routing error and is unable to proceed. Supply: Axiomise

Redundant logic revealing PPA points

Sure design selections within the routing algorithm, resembling prohibiting-specific turns, result in conditions the place a number of FIFOs by no means have push asserted, and a few arbiters deal with lower than two requestors.

This has been recognized in the course of the verification course of, revealing that these parts—and consequently, hundreds of thousands of gates—are going unused within the design however nonetheless occupy chip space and, when clocked, would burn energy whereas not contributing to any efficiency. Eliminating these superfluous gates considerably lowered manufacturing prices and improved design effectivity.

The case for formal verification in NoC

An NoC-based cloth is important for any trendy high-performance computing or AI/ML machine. NoCs improve efficiency by environment friendly routing to keep away from congestion. Whereas NoCs are designed to be environment friendly at knowledge transmission through routing, they usually encounter deadlocks and livelocks along with the same old purposeful correctness challenges between supply and vacation spot nodes.

With a variety of topologies potential for routing, directing simulation sequences to cowl all potential supply/vacation spot pairs is sort of inconceivable for dynamic simulation. Detecting deadlocks, hunger and livelocks is sort of inconceivable for any simulation and even emulation-based verification.

Formal strategies drive an virtually infinite quantity of stimulus to cowl all obligatory pairs encountered in any topology. With the ability of exhaustive proofs, we will set up conclusively that there isn’t a impasse or a livelock or hunger with formal.

Editor’s Be aware: Axiomise printed a whitepaper in 2022, summarizing a variety of virtually environment friendly formal verification methods used for verifying high-performance NoCs.

Zifei Huang is a proper verification engineer at Axiomise, specializing in NoC and RISC-V architectures.

Adeel Liaquat is an engineering supervisor at Axiomise, specializing in formal verification methodologies.

Ashish Darbari is founder and CEO of Axiomise, an organization providing coaching, consulting, companies, and verification IP to varied semiconductor companies.

Associated Content material