Systems and methods for switching using hierarchical networks

Patent metadata

Field	Value
Publication number	US-9817933-B2
Application number	US-201414777477-A
Country	US
Kind code	B2
Filing date	Mar 14, 2014
Priority date	Mar 15, 2013
Publication date	Nov 14, 2017
Grant date	Nov 14, 2017

Abstract

Systems and methods for implementing boundary-less hierarchical networks including methods of generating such networks in accordance with embodiments of the invention are disclosed. In one embodiment, a hierarchical network in an integrated circuit that includes a plurality of computing elements, where the plurality of computing elements have M outputs and N inputs, and a plurality of switches arranged into stages of switches wherein the plurality of computing elements are connected to switches in a first stage, the switches in the first stage are connected to the plurality of computing elements and switches in a second stage, where the switches in the second stage are connected to the switches in the first stage, at least M+1 adjacent computing elements can connect to at least two nearest neighboring computing elements via a stage 1 switch, and every computing element can connect with every other computing element within the hierarchical network.

First claim

What is claimed is:

1. A hierarchical network in an integrated circuit, the hierarchical network comprising:
a plurality of computing elements, where the plurality of computing elements have M outputs and N inputs; and
a plurality of switches arranged into a plurality of stages of switches wherein:
the plurality of computing elements are connected to switches in a first stage via routes;
the switches in the first stage are connected to the plurality of computing elements and switches in a second stage via routes, where the switches in the second stage are connected to the switches in the first stage via routes;
each of at least M+1 adjacent computing elements is configured to connect to at least two nearest neighboring computing elements via a single switch of the first stage; and

every computing element is configured to connect with every other computing element within the hierarchical network via the plurality of switches arranged in the plurality of stages to provide communication between computing elements.

2. The hierarchical network for integrated circuits of claim 1 , wherein a plurality of computing elements have M outputs and a plurality of computing elements have M+1 outputs and a plurality of switches in the first stage have M inputs and a plurality of switches of the first stage have M+1 inputs.

3. The hierarchical network for integrated circuits of claim 2 , wherein at least 2 M-1 computing elements have M outputs and at least 2 M-1 switches of the first stage have M inputs.

4. The hierarchical network for integrated circuits of claim 3 , wherein 2 M-1 computing elements have M outputs and the remaining computing elements have M+1 outputs.

5. The hierarchical network for integrated circuits of claim 2 , wherein at least 2 M-1 switches of the first stage have M−1 outputs and at least 2 M-1 switches of the second stage have M−1 inputs.

6. The hierarchical network for integrated circuits of claim 5 , wherein 2 M-1 switches of the first stage have M−1 outputs and the remaining switches of the first stage have M outputs.

7. The hierarchical network for integrated circuits of claim 2 , wherein at least 2 M switches of the second stage have M−1 outputs and 2 M switches of a third stage have M−1 inputs.

8. The hierarchical network for integrated circuits of claim 7 , wherein 2 M switches of the second stage have M−1 outputs and the remaining switches of the second stage have M outputs.

9. The hierarchical network for integrated circuits of claim 1 , wherein the routes are bi-directional double routes.

10. A hierarchical network in an integrated circuit, the hierarchical network comprising:
a plurality of computing elements, where the plurality of computing elements have M outputs and N inputs; and
a plurality of switches arranged into stages of switches wherein:
the plurality of computing elements are connected to switches in a first stage via routes;
the switches in the first stage are connected to the plurality of computing elements and switches in a second stage via routes, where the switches in the second stage are connected to the switches in the first stage via routes;
a plurality of computing elements have M outputs and a plurality of computing elements have M+1 outputs and a plurality of switches in the first stage have M inputs and a plurality of switches in the first stage have M+1 inputs; and
every computing element is configured to connect with every other computing element within the hierarchical network via the plurality of switches arranged in the plurality of stages to provide communication between computing elements.

11. A method for transmitting data between computing elements of a hierarchical network in an integrated circuit, the method comprising:
transmitting data from a computing element to a switch of a first stage within the hierarchical network, where the hierarchical network includes:
a plurality of computing elements having M outputs and N inputs; and
a plurality of switches arranged into stages of switches wherein:
the plurality of computing elements are connected to switches in the first stage via routes; and
the switches in the first stage are connected to the plurality of computing elements and switches in a second stage via routes, where the switches in the second stage are connected to the switches in the first stage via routes; and
transmitting data from the switch in the first stage to another computing element where each of at least M+1 adjacent computing elements is configured to transmit data to at least two nearest neighboring computing elements via a single switch in the first stage.

12. The method of claim 11 , wherein a plurality of computing elements have M outputs and a plurality of computing elements have M+1 outputs and a plurality of switches in the first stage have M inputs and a plurality of switches in the first stage have M+1 inputs.

13. The method of claim 12 , wherein at least 2 M-1 computing elements have M outputs and at least 2 M-1 switches in the first stage have M inputs.

14. The method of claim 13 , wherein 2 M-1 computing elements have M outputs and the remaining computing elements have M+1 outputs.

15. The method of claim 12 , wherein at least 2 M-1 switches in the first stage have M−1 outputs and at least 2 M-1 switches in the second stage have M−1 inputs.

16. The method of claim 15 , wherein 2 M-1 switches in the first stage have M−1 outputs and the remaining switches in the first stage have M outputs.

17. The method of claim 12 , wherein at least 2 M switches in the second stage have M−1 outputs and 2 M switches in a third stage have M−1 inputs.

18. The method of claim 17 , wherein 2 M switches in the second stage have M−1 outputs and the remaining switches in the second stage have M outputs.

19. The method of claim 11 , wherein the routes are bi-directional double routes.

20. A hierarchical network in an integrated circuit, the hierarchical network comprising:
a plurality of computing elements, where the plurality of computing elements have M outputs and N inputs; and
a plurality of switches arranged into stages of switches wherein:
the plurality of computing elements are connected to switches in a first stage via routes;
the switches in the first stage are connected to the plurality of computing elements and switches in a second stage via routes, where the switches in the second stage are connected to the switches in the first stage via routes;
2 M-1 computing elements have M outputs and the remaining computing elements have M+1 outputs, where 2 M-1 switches in the first stage have M inputs and the remaining switches have M+1 inputs;
2 M-1 switches in the first stage have M−1 outputs and the remaining switches in the first stage have M outputs, where 2 M-1 switches in the second stage have M−1 inputs and the remaining switches in the second stage have M inputs;
2 M switches in the second stage have M−1 outputs and the remaining switches in the second stage have M outputs; and
every computing element can connect with every other computing element within the hierarchical network to provide communication between computing elements via the plurality of switches arranged in the plurality of stages.

21. A field programmable gate array, comprising:
a plurality of computing elements, where the plurality of computing elements have M outputs and N inputs; and
a plurality of switches arranged into stages of switches wherein:
the plurality of computing elements are connected to swi

Assignees

• Univ California

Inventors

• Wang Chengcheng
• Markovic Dejan

Classifications

• G06F30/18

  Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling (circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18) · CPC title

• H03K19/17744 Primary

  for input/output signals · CPC title

• G06F15/7867

  with reconfigurable architecture · CPC title

• G06F30/392

  Floor-planning or layout, e.g. partitioning or placement · CPC title

• G06F30/34

  for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD] · CPC title