IP Library › Granted Patent US 10,116,557

Granted Patent B2

US 10,116,557 · App. 14/986,532 · Granted Oct 30, 2018

Directional two-dimensional router and interconnection network for field programmable gate arrays, and other circuits and applications of the router and network

Inventor: Jan Stephen Gray (Bellevue, WA)

Assignee: Gray Research LLC

H04L45/60 H04L49/106 H04L49/40

View Patent ↗

Loading inventors, assignments & file history…

Monitor This Case

Get email alerts when status or documents change.

Order Certified Copies

Most orders are placed with the USPTO same day — all within 24 business hours.

Order via The Patent Place →

Pre-filled with this patent's details

Quick Facts

Patent No.: US 10,116,557
App. No.: 14/986,532
Filed: Dec 31, 2015
Granted: Oct 30, 2018
Kind: B2
Examiner: KUMAR, SHAILENDRA
Art Unit: 2471
USPC: 370/401

External Links

USPTO Patent Center↗ Full Patent PDF↗

Abstract

A configurable directional 2D router for Networks on Chips (NOCs) is disclosed. The router, which may be bufferless, is designed for implementation in programmable logic in FPGAs, and achieves theoretical lower bounds on FPGA resource consumption for various applications. The router employs an FPGA router switch design that consumes only one 6-LUT or 8-input ALM logic cell per router per bit of router link width. A NOC comprising a plurality of routers may be configured as a directional 2D torus, or in diverse ways, network sizes and topologies, data widths, routing functions, performance-energy tradeoffs, and other options. System on chip designs may employ a plurality of NOCs with different configuration parameters to customize the system to the application or workload characteristics. A great diversity of NOC client cores, for communication amongst various external interfaces and devices, and on-chip interfaces and resources, may be coupled to a router in order to efficiently communicate with other NOC client cores. The router and NOC enable feasible FPGA implementation of large integrated systems on chips, interconnecting hundreds of client cores over high bandwidth links, including compute and accelerator cores, industry standard IP cores, DRAM/HBM/HMC channels, PCI Express channels, and 10G/25G/40G/100G/400G networks.

Claims (191)

1. A signal router, comprising:

a first input node configured to receive a first input signal;

a second input node configured to receive a second input signal;

a first output node;

a second output node;

a switch circuit coupled to the first and second input nodes and to the first and second output nodes; and

a routing circuit configured

to cause the switch circuit

to couple the first input signal to the first output node in response to the first input signal being valid,

to couple the second input signal to the second output node in response to the second input signal being valid, and

to couple the first input signal to the second output node in response to the first input signal being valid and the second input signal being invalid.

2. The signal router of claim 1 , further comprising:

a first-output-valid node;

a second-output-valid node; and

wherein the routing circuit is configured to generate

on the first-output-valid node a first-output-valid signal in response to the first input signal being valid and destined for the first output node, and

on the second-output-valid node a second-output-valid signal in response to the second input signal being valid and destined for the second output node, and in response to the second input signal being invalid and the first input signal being valid and destined for the second output node.

3. The signal router of claim 1 wherein the routing circuit is configured to cause the switch circuit to couple:

the first input signal to the second output node in response to the first input signal being valid, a client of the router being a destination of the first input signal, and the second input signal being invalid; and

the second input signal to the second output node in response to the second input signal being valid and the client of the router being a destination of the second input signal.

4. The signal router of claim 1 , further comprising:

an output-to-client-valid node; and

wherein the routing circuit is configured to generate, on the output-to-client-valid node, an output-to-client-valid signal in response to

the first input signal being valid, a client of the router being a destination of the first input signal, and the second input signal being invalid, and

the second input signal being valid and the client of the router being a destination of the second input signal.

5. The signal router of claim 1 , further comprising:

a client input node coupled to the switch circuit and configured to receive a client input signal from a client of the router; and

wherein the routing circuit is configured to cause the switch circuit to couple the client input signal

to the first output node

in response to the client input signal being valid and destined for the first output node, the first input signal being valid and destined for the second output node, and the second input signal being invalid, and

in response to the client input signal being valid and destined for the first output node, and the first input signal being invalid, and

to the second output node

in response to the client input signal being valid and destined for the second output node, and the first and second input signals being invalid, and

in response to the client input signal being valid and destined for the second output node, the first input signal being valid and destined for the first output node, and the second input signal being invalid.

6. The signal router of claim 1 , further comprising:

a client input node coupled to the switch circuit and configured to receive a client input signal from a client of the router;

a router-ready node coupled to the routing circuit; and

wherein the routing circuit is configured to generate, on the router-ready node, a ready-for-client-input signal in response to

the client input signal being valid and destined for the first output node, the first input signal being valid and destined for the second output node, and the second input signal being invalid,

the client input signal being valid and destined for the first output node, and the first input signal being invalid,

the client input signal being valid and destined for the second output node, and the first and second input signals being invalid, and

the client input signal being valid and destined for the second output node, the first signal being valid and destined for the first output node, and the second input signal being invalid.

7. The signal router of claim 1 , wherein the routing circuit is configured to cause the switch circuit:

to couple the first input signal to the first output node with a first delay; and

to couple the first input signal to the second output node with a second delay that is different from the first delay.

8. The signal router of claim 1 , wherein:

the first input node includes a first-dimension input node,

the second input node includes a second-dimension input node,

the first output node includes a first-dimension output node,

and the second output node includes a second-dimension output node.

9. The signal router of claim 1 , further comprising:

a first-input-valid node configured to receive a first-input-valid signal that indicates whether the first input signal is valid; and

a second-input-valid node configured to receive a second-input-valid signal that indicates whether the second input signal is valid.

10. The signal router of claim 1 , further comprising:

a first-input-valid node configured to receive a first-input-valid signal;

a second-input-valid node configured to receive a second-input-valid signal; and

wherein the routing circuit is configured

to cause the switch circuit

to couple the first input signal to the first output node in response to assertion of the first-input-valid signal, and

to couple the second input signal to the second output node in response to assertion of the second-input-valid signal, and

to couple the first input signal to the second output node in response to assertion of the first input-valid signal and negation of the second-input-valid signal.

11. A method, comprising:

receiving a first input signal on a first input node of a first signal router;

receiving a second input signal on a second input node of the first signal router;

coupling the first input signal to a client, via a second output node of the first signal router, only if the first input signal is valid, the first input signal identifies the client as a destination of the first input signal, and the second input signal is invalid; and

coupling the second input signal to a client, via the second output node of the first signal router, only if the second input signal is valid and identifies the client as a destination of the second input signal.

12. The method of claim 11 , further comprising:

providing to the first input node of the first signal router from a second signal router the first input signal and a first-input-valid signal that indicates whether the first input signal is valid; and

providing to the second input node of the first signal router from a third signal router the second input signal and a second-input-valid signal that indicates whether the second input signal is valid.

13. The method of claim 11 , further comprising:

generating on a first-output-valid node of the first router a first-output-valid signal in response to the first input signal being valid and destined for the first output node; and

generating on a second-output-valid node of the first router a second-output-valid signal in response

to the second input signal being valid and destined for the second output node, and

to the second input signal being invalid and the first input signal being valid and destined for the second output node.

14. The method of claim 11 , further comprising:

coupling the first input signal to the second output node in response to the first input signal being valid, the client being a destination of the first input signal, and the second input signal being invalid; and

coupling the second input signal to the second output node in response to the second input signal being valid and the client being a destination of the second input signal.

15. The method of claim 11 , further comprising generating, on an output-to-client-valid node of the first router, an output-to-client-valid signal in response to:

the first input signal being valid, the client being a destination of the first input signal, and the second input signal being invalid; and

the second input signal being valid and the client being a destination of the second input signal.

16. The method of claim 11 , further comprising:

receiving, on a client input node of the first router, a client input signal from the client;

coupling the client input signal to the first output node of the first router

in response to the client input signal being valid and destined for the first output node, and the first input signal being invalid; and

coupling the client input signal to the second output node of the first router

in response to the client input signal being valid and destined for the second output node, and the first and second input signals being invalid, and

17. The method of claim 11 , further comprising:

receiving, on a client input node of the first router, a client input signal from the client; and

generating, on a router-ready node of the first router, a ready-for-client-input signal in response to

the client input signal being valid and destined for the first output node, the first input signal being valid and destined for the second output node, and the second input signal being invalid,

the client input signal being valid and destined for the first output node, and the first input signal being invalid,

the client input signal being valid and destined for the second output node, and the first and second input signals being invalid, and

the client input signal being valid and destined for the second output node, the first input signal being valid and destined for the first output node, and the second input signal being invalid.

18. The method of claim 11 , further comprising:

coupling the first input signal to the first output node of the first router with a first delay in response to the first input signal being valid and being destined for the first output node; and

coupling the first input signal to the second output node of the first router with a second delay that is different from the first delay in response to the first input signal being valid and being destined for the second output node, and the second input signal being invalid.

19. A non-transitory machine-readable medium storing configuration data that when loaded into a programmable gate array, causes the programmable gate array to instantiate a circuit configured:

to receive a first input signal on a first input node of a first signal router;

to receive a second input signal on a second input node of the first signal router;

to couple the first input signal to a client, via a second output node of the first signal router, only if the first input signal is valid, the first input signal identifies the client as a destination of the first input signal, and the second input signal is invalid; and

to couple the second input signal to a client, via the second output node of the first signal router, only if the second input signal is valid and identifies the client as a destination of the second input signal.

20. The non-transitory machine-readable medium of claim 19 storing configuration data that when loaded into a programmable gate array, causes the programmable gate array to instantiate the circuit further configured:

to provide to the first input node of the first signal router from a second signal router the first input signal and a first input-valid signal that indicates whether the first input signal is valid; and

to provide to the second input node of the first signal router from a third signal router the second input signal and a second input-valid signal that indicates whether the second input signal is valid.

21. The non-transitory machine-readable medium of claim 19 storing configuration data that when loaded into a programmable gate array, causes the programmable gate array to instantiate the circuit further configured:

to generate on a first-output-valid node of the first router a first-output-valid signal in response to the first and second input signals being valid, and in response to the first input signal being valid and destined for the first output node; and

to generate on a second-output-valid node of the first router a second-output-valid signal in response to the second input signal being valid, and in response to the second input signal being invalid and the first input signal being valid and destined for the second output node.

22. The non-transitory machine-readable medium of claim 19 storing configuration data that when loaded into a programmable gate array, causes the programmable gate array to instantiate the circuit further configured:

to couple the first input signal to the second output node in response to the first input signal being valid, the client being a destination of the first input signal, and the second input signal being invalid; and

to couple the second input signal to the second output node in response to the second input signal being valid and the client being a destination of the second input signal.

23. The non-transitory machine-readable medium of claim 19 storing configuration data that when loaded into a programmable gate array, causes the programmable gate array to instantiate the circuit further configured to generate, on an output-to-client-valid node of the first router, an output-to-client-valid signal in response to:

the first input signal being valid, the client being a destination of the first input signal, and the second input signal being invalid; and

the second input signal being valid and the client being a destination of the second input signal.

24. The non-transitory e machine-readable medium of claim 19 storing configuration data that when loaded into a programmable gate array, causes the programmable gate array to instantiate the circuit further configured:

to receive, on a client input node of the first router, a client input signal from the client;

to couple the client input signal to the first output node of the first router

in response to the client input signal being valid and destined for the first output node, and the first input signal being invalid; and

to couple the client input signal to the second output node of the first router

in response to the client input signal being valid and destined for the second output node, and the first and second input signals being invalid, and

25. The non-transitory machine-readable medium of claim 19 storing configuration data that when loaded into a programmable gate array, causes the programmable logic array to instantiate the circuit further configured:

to receive, on a client input node of the first router, a client input signal from the client; and

to generate, on a router-ready node of the first router, a ready-for-client-input signal in response to

the client input signal being valid and destined for the first output node, the first input signal being valid and destined for the second output node, and the second input signal being invalid,

the client input signal being valid and destined for the first output node, and the first input signal being invalid,

the client input signal being valid and destined for the second output node, and the first and second input signals being invalid, and

the client input signal being valid and destined for the second output node, the first input signal being valid and destined for the first output node, and the second input signal being invalid.

26. The non-transitory machine-readable medium of claim 19 storing configuration data that when loaded into a programmable circuit array, causes the programmable gate array to instantiate the circuit further configured:

to couple the first input signal to the first output node of the first router with a first delay in response to the first input signal being valid and being destined for the first output node; and

to couple the first input signal to the second output node of the first router with a second delay that is different from the first delay in response to the first input signal being valid and being destined for the second output node, and the second input signal being invalid.

27. A system, comprising:

a signal router, including

a first input node configured to receive a first input signal,

a second input node configured to receive a second input signal,

a first output node,

a second output node,

a switch circuit coupled to the first- and second input nodes and to the first- and second output nodes, and

a routing circuit configured to cause the switch circuit

to couple the first input signal to the first output node in response to the first input signal being valid,

to couple the second input signal to the second output node in response to the second input signal being valid, and

to couple the first input signal to the second output node in response to the first input signal being valid and the second input signal being invalid; and

a client coupled to the signal router.

28. The system of claim 27 , wherein the client includes a client input node that is coupled to one of the first and second output nodes.

29. A signal router, comprising:

a first input node configured to receive a first input signal;

a second input node configured to receive a second input signal;

a first output node configured to provide a first output signal;

a second output node configured to provide a second output signal;

a first-output-valid node configured to provide a first-output-valid signal that indicates whether the first output signal is valid;

a second-output-valid node configured to provide a second-output-valid signal that indicates whether the second output signal is valid; and

a third-output-valid node configured to provide, to a client, a third-output-valid signal that indicates whether one of the first output signal and the second output signal is valid for the client.

30. The signal router of claim 29 , further comprising:

a first-input-valid node configured to receive a first-input-valid signal that indicates whether the first input signal is valid;

a second-input-valid node configured to receive a second-input-valid signal that indicates whether the second input signal is valid;

a switch circuit coupled to the first and second input nodes and to the first and second output nodes; and

a routing circuit configured to cause the switch circuit

to couple the first input signal to the first output node as the first output signal in response to the first input-valid signal indicating that the first input signal is valid, and

to couple the second input signal to the second output node in response to the second-input-valid signal indicating that the second input signal is valid, and

to couple the first input signal to the second output node as the second output signal in response to the first-input-valid signal indicating that the first input signal is valid and the second-input-valid signal not indicating that the second input signal is valid.

31. The signal router of claim 29 , further comprising:

a switch circuit coupled to the first and second input nodes and to the first and second output nodes; and

a routing circuit configured to cause the switch circuit to couple

the first input signal to the second output node as the second output signal in response to the first-input-valid signal indicating that the first input signal is valid, the client being a destination of the first input signal, and the second-input-valid signal indicating that the second input signal is invalid, and

the second input signal to the second output node as the second output signal in response to the second-input-valid signal indicating that the second input signal is valid and the client being a destination of the second input signal.

32. The signal router of claim 29 , further comprising:

a client input node configured to receive a client input signal from a client of the router;

a router-ready node;

a switch circuit coupled to the first and second input nodes, to the first and second output nodes, and to the client input node; and

a routing circuit configured

to cause the switch circuit to couple the first input signal to the first output node in response to the first-input-valid signal indicating that the first input signal is valid, and

to cause the switch circuit to couple the second input signal to the second output node in response to the second-input-valid signal indicating that the second input signal is valid, and

to cause the switch circuit to couple the first input signal to the second output node in response to the first- and second-input-valid signals indicating, respectively, that the first input signal is valid and the second input signal is invalid, and

to generate, on the router-ready node, a ready-for-client-input signal

in response to the client input signal being valid and destined for the first output node, the first-input-valid signal indicating that the first input signal is valid, the first input signal being destined for the second output node, and the second-input-valid signal indicating that the second input signal is invalid,

in response to the client input signal being valid and destined for the first output node, and the first-input-valid signal indicating that the first input signal is invalid,

in response to the client input signal being valid and destined for the second output node, and the first- and second-input-valid signals indicating, respectively, that the first and second input signals are invalid, and

in response to the client input signal being valid and destined for the second output node, the first-input-valid signal indicating that the first input signal is valid, the first input signal being destined for the first output node, and the second input-valid signal indicating that the second input signal is invalid.

33. A system, comprising:

a signal router, including

a first input node configured to receive a first input signal,

a second input node configured to receive a second input signal,

a first output node,

a second output node,

a circuit coupled to the first and second input nodes and to the first and second output nodes and configured

to couple the first input signal to the first output node in response to the first input signal being valid,

to couple the second input signal to the second output node in response to the second input signal being valid, and

to couple the first input signal to the second output node in response to the first input signal being valid and the second input signal being invalid; and

a client coupled to the signal router.

Assignments (1)

ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Feb 4, 2021

From: GRAY, JAN STEPHEN

To: GRAY RESEARCH LLC

Reel/Frame 055152/0851 →

Continuity (2)

Provisional Application 62165774 · May 22, 2015

Related Publication 20160344629A1 · Nov 24, 2016

Cited By (4)

US 50,504 US 12,406,186 US 12,579,352 US 12,681,893