Automatic construction of deadlock free interconnects

Patent metadata

Field	Value
Publication number	US-9244880-B2
Application number	US-201213599559-A
Country	US
Kind code	B2
Filing date	Aug 30, 2012
Priority date	Aug 30, 2012
Publication date	Jan 26, 2016
Grant date	Jan 26, 2016

Abstract

Systems and methods for automatically building a deadlock free inter-communication network in a multi-core system are described. The example embodiments described herein involve deadlock detection during the mapping of user specified communication pattern amongst blocks of the system. Detected deadlocks are then avoided by re-allocation of channel resources. An example embodiment of the deadlock avoidance scheme is presented on Network-on-chip interconnects for large scale multi-core system-on-chips.

First claim

What is claimed is:

1. A computer implemented method, comprising:
automatically constructing a map of interconnected channels for a Network on Chip (NoC) system such that the NoC system is free of deadlock, based on channels of the NoC system, by
determining the channels of the NoC system from a specification of the NoC system, wherein the specification contains a deadlock;
allocating one of the channels for a link in a route between endpoints of a section of message sequence of the NoC system in a dependency graph;
automatically checking for cyclic dependencies in the dependency graph;
automatically reallocating the channels of the specification of the NoC system until the deadlock is resolved, wherein the automatically reallocating the channels comprises adding one or more additional virtual channels; and
constructing the map of interconnected channels based on the reallocation.

2. The method of claim 1 , further comprising, when no cyclic dependencies are detected:
including the allocation of the one of the channels for the link in the automatic construction of the map;
utilizing the allocated one of the channels or a newly allocated channel for another link in the route in the dependency graph, if the route is not completely mapped; and
automatically checking for cyclic dependencies in the dependency graph, if the route is not completely mapped.

3. The method of claim 1 , further comprising, when cyclic dependencies are detected:
discarding the allocated one from the dependency graph, and
allocating another one of the available channels for the route in the dependency graph.

4. The method of claim 1 , wherein the allocating and the checking for cyclic dependencies is repeated until the sequence is completely mapped or until the channels are all exhausted.

5. A non-transitory computer readable storage medium storing instructions for implementing a method, the instructions comprising:
automatically constructing a map of interconnected channels for a Network on Chip (NoC) system such that the multi-core system is free of deadlock, based on channels of the NoC system, by
determining the channels of the NoC system from a specification of the NoC system, wherein the specification contains a deadlock;
allocating one of the channels for a link in a route between endpoints of a sequence of the NoC system in a dependency graph;
automatically checking for cyclic dependencies in the dependency graph;
automatically reallocating the channels of the specification of the NoC system until the deadlock is resolved, wherein the automatically reallocating the channels comprises adding one or more additional virtual channels; and
constructing the map of interconnected channels based on the reallocation.

6. The non-transitory computer readable storage medium of claim 5 , wherein the instructions further comprise, when no cyclic dependencies are detected:
including the allocation of the one of the channels for the link in the automatic construction of the map;
utilizing the allocated one of the channels or a newly allocated channel for another link in the route in the dependency graph, if the route is not completely mapped; and
automatically checking for cyclic dependencies in the dependency graph, if the route is not completely mapped.

7. The non-transitory computer readable storage medium of claim 5 , wherein the instructions further comprise, when cyclic dependencies are detected:
discarding the allocated one from the dependency graph, and
allocating another one of the available channels for the route in the dependency graph.

8. The non-transitory computer readable storage medium of claim 5 , wherein the allocating and the checking for cyclic dependencies is repeated until the sequence is completely mapped or until the channels are all exhausted.

9. A system, comprising:
a route construction module configured to:
automatically construct a map of interconnected channels for a Network on Chip (NoC) system such that the NoC system is free of deadlock, based on channels of the NoC system;
determine the channels of the NoC system from a specification of the NoC system, wherein the specification contains a deadlock;
automatically utilizing the allocation module to reallocate the channels of the specification of the NoC system until the deadlock is resolved, wherein the automatically reallocating the channels comprises adding one or more additional virtual channels; and
construct the map of interconnected channels based on the reallocation;

an allocation module configured to allocate one of the channels for a link in a route between endpoints of a sequence of the multi-core system in a dependency graph; and
a dependencies module configured to automatically check for cyclic dependencies in the dependency graph.

10. The system of claim 9 , wherein when no cyclic dependencies are detected by the dependencies module, the route construction module is configured to:
include the allocation of the one of the channels for the link in the automatic construction of the map;
instruct the allocation module to utilize the allocated one of the channels or a newly allocated channel for another link in the route in the dependency graph, if the route is not completely mapped; and
instruct the dependencies module to automatically check for cyclic dependencies in the dependency graph, if the route is not completely mapped.

11. The system of claim 9 , wherein when cyclic dependencies are detected by the dependencies module, the allocation module is configured to:
discard the allocated one from the dependency graph, and
allocate another one of the available channels for the route in the dependency graph.

12. The system of claim 9 , wherein the allocation module is configured to repeat the allocation and wherein the dependencies module is configured to repeatedly check for cyclic dependencies until the sequence is completely mapped or until the channels are all exhausted.

13. The system of claim 9 , wherein the channels comprise at least one of a physical channel and a virtual channel.

14. The system of claim 9 , wherein at least one of the route construction module and the allocation module is further configured to address all high level dependencies and network level deadlocks of the multi-core system.

15. The method of claim 1 , wherein the specification comprises one or more intercommunication message patterns, wherein the automatically constructing the map of interconnected channels is conducted such that the multi-core system is free of deadlock for all of the one or more intercommunication message patterns.

Assignees

• Philip Joji
• Kumar Sailesh
• Norige Eric
• Hassan Mahmud
• Mitra Sundari
• Netspeed Systems

Inventors

• Philip Joji
• Kumar Sailesh
• Norige Eric
• Hassan Mahmud
• Mitra Sundari

Classifications

• G06F15/7825

  Globally asynchronous, locally synchronous, e.g. network on chip · CPC title

• H04L45/06

  Deflection routing, e.g. hot-potato routing · CPC title

• G06F15/17312 Primary

  Routing techniques specific to parallel machines, e.g. wormhole, store and forward, shortest path problem congestion (routing on a LAN H04L45/00) · CPC title