Granted Patent B2

US 12,438,829 · App. 17/953,350 · Granted Oct 7, 2025

Inventors: Benoit de Lescure (Campbell, CA); Moez Cherif (Santa Cruz, CA)

Assignee: ARTERIS, INC.

H04L49/55H04L49/109H04L49/25

Abstract

Claims (48)

1. A method of designing a network-on-chip (NoC), the method comprising:

searching for a potential deadlock in a topology of the NoC, the potential deadlock caused by an external dependency in which input of data into the NoC is dependent on output of data from the NoC;

modifying the NoC topology to resolve the potential deadlock;

searching for at least one additional potential deadlock in the topology and modifying the NoC topology to resolve each additional deadlock,

wherein the NoC includes a plurality of network interface units configured to interface with initiators (initiator NIUs) and a plurality of network interface units configured to interface with targets (target NIUs),

wherein the NoC includes a plurality of network interface units configured to interface with initiators (initiator NIUs) and a plurality of network interface units configured to interface with targets (target NIUs) and wherein searching for a potential deadlock includes examining the topology for segments that form loops with respect to an initiator NIU and a target NIU having an external dependency, a potential deadlock detected if a loop is detected,

wherein searching for a potential deadlock includes examining the topology for segments that form loops with respect to an initiator NIU and a target NIU having an external dependency, a potential deadlock detected if a loop is detected,

wherein for each target NIU, a chain of dependent segments is traversed to determine whether the chain forms a loops,

wherein examining the topology for segments that form loops includes:

creating a first list of segments in the NoC topology, where each segment is a directed connection between two components in the NoC topology;

adding to the first list segments between target NIUs having external dependencies to initiator NIUs;

for each segment in the first list, creating a second list of downstream dependent segments, where each dependent segment depends on forward progress of packets from an upstream segment, whereby a set of second lists is created; and

for each initiator NIU in the topology, traversing the set of second lists of dependent segments until reaching a target NIU with no external dependencies or until finding at least one loop.

2. The method of claim 1 , further comprising generating a register transfer level (RTL) description of the NoC from the modified NoC topology.

3. The method of claim 2 , wherein the NoC is implemented in a system-on-chip (SoC) and the method further comprises:

generating a topology description of the NoC,

wherein a description of external dependencies is received from an architect of the SoC, and

wherein the NoC topology description and the external dependency description are used to search for a potential deadlock; and

delivering the RTL description of the NoC to the architect.

4. A method of designing a network-on-chip (NoC), the method comprising:

searching for a potential deadlock in a topology of the NoC, the potential deadlock caused by an external dependency in which input of data into the NoC is dependent on output of data from the NoC;

modifying the NoC topology to resolve the potential deadlock;

searching for at least one additional potential deadlock in the topology and modifying the NoC topology to resolve each additional deadlock,

wherein the NoC includes a plurality of network interface units configured to interface with initiators (initiator NIUs) and a plurality of network interface units configured to interface with targets (target NIUs),

wherein the NoC includes a plurality of network interface units configured to interface with initiators (initiator NIUs) and a plurality of network interface units configured to interface with targets (target NIUs) and wherein searching for a potential deadlock includes examining the topology for segments that form loops with respect to an initiator NIU and a target NIU having an external dependency, a potential deadlock detected if a loop is detected,

wherein searching for a potential deadlock includes examining the topology for segments that form loops with respect to an initiator NIU and a target NIU having an external dependency, a potential deadlock detected if a loop is detected,

wherein examining the topology for segments that form loops includes:

creating all possible lists that originate from an initiator NIU and that contain segments S( 0 ), S( 1 ) . . . S(N), where a segment S(i) in one such list is followed immediately by a segment S(i+1), if and only if S(i+1) is a downstream dependent segment of S(i); and

for each initiator NIU in the topology, traversing the lists until reaching a target NIU with no external dependencies or until finding at least one loop of segments.

5. A method of designing a network-on-chip (NoC), the method comprising:

searching for a potential deadlock in a topology of the NoC, the potential deadlock caused by an external dependency in which input of data into the NoC is dependent on output of data from the NoC;

modifying the NoC topology to resolve the potential deadlock;

searching for at least one additional potential deadlock in the topology and modifying the NoC topology to resolve each additional deadlock,

wherein the NoC includes a plurality of network interface units configured to interface with initiators (initiator NIUs) and a plurality of network interface units configured to interface with targets (target NIUs),

wherein the NoC includes a plurality of network interface units configured to interface with initiators (initiator NIUs) and a plurality of network interface units configured to interface with targets (target NIUs) and wherein searching for a potential deadlock includes examining the topology for segments that form loops with respect to an initiator NIU and a target NIU having an external dependency, a potential deadlock detected if a loop is detected,

wherein searching for a potential deadlock includes examining the topology for segments that form loops with respect to an initiator NIU and a target NIU having an external dependency, a potential deadlock detected if a loop is detected,

wherein loop detection with respect to a selected initiator NIU includes:

creating an empty set of lists;

populating the set with a first search list having a segment originating from the selected initiator NIU;

making, if the list is not empty, a list current and making current a segment at end of the current list;

indicating, if the current segment appears twice in the current list, that a loop has been detected;

removing, if the current segment terminates at a target NIU and has no dependent downstream segments, the current list from the set;

creating a new list for each dependent downstream segment of the current segment;

adding each new list to the set;

removing the current list from the set; and

making the list current and making current the segment at the end of the list made current.

6. The method of claim 5 , wherein the loop detection further includes indicating, if the set is empty, that a loop is not detected for the selected NIU.

7. The method of claim 5 , wherein creating a new list includes cloning the current list and appending a downstream dependent segment of the current segment.

Assignments (1)

Continuity (2)

References Cited (164)