IP Library › Granted Patent US 50,417
Granted Patent E1
US 50,417 · App. 16/202,067 · Granted May 6, 2025

VLSI layouts of fully connected generalized networks

Inventor: Venkat Konda (San Jose, CA)
Assignee: Konda Technologies Inc.
G09G3/3266H03K19/177
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 50,417
App. No.
16/202,067
Granted
May 6, 2025
Kind
E1
Abstract

In accordance with the invention, VLSI layouts of generalized multi-stage networks for broadcast, unicast and multicast connections are presented using only horizontal and vertical links. The VLSI layouts employ shuffle exchange links where outlet links of cross links from switches in a stage in one sub-integrated circuit block are connected to inlet links of switches in the succeeding stage in another sub-integrated circuit block so that said cross links are either vertical links or horizontal and vice versa. In one embodiment the sub-integrated circuit blocks are arranged in a hypercube arrangement in a two-dimensional plane. The VLSI layouts exploit the benefits of significantly lower cross points, lower signal latency, lower power and full connectivity with significantly fast compilation. The VLSI layouts presented are applicable to generalized multi-stage networks V(N 1 , N 2 , d, s), generalized folded multi-stage networks V fold (N 1 , N 2 , d, s), generalized butterfly fat tree networks V bft (N 1 , N 2 , d, s), generalized multi-link multi-stage networks V mlink (N 1 , N 2 , d, s), generalized folded multi-link multi-stage networks V fold-mlink (N 1 , N 2 , d, s), generalized multi-link butterfly fat tree networks V mlink-bft (N 1 , N 2 , d, s), and generalized hypercube networks V hcube (N 1 , N 2 , d, s) for s=1, 2, 3 or any number in general. The embodiments of VLSI layouts are useful in wide target applications such as FPGAs, CPLDs, pSoCs, ASIC placement and route tools, networking applications, parallel & distributed computing, and reconfigurable computing.

Claims (116)

1. An integrated circuit device comprising a plurality of sub-integrated circuit blocks and a routing network, and

Said each plurality of sub-integrated circuit blocks comprising a plurality of inlet links and a plurality of outlet links; and

Said routing network comprising of a plurality of stages y, in each said sub-integrated circuit block, starting from the lowest stage of 1 to the highest stage of y, where y≥1; and

Said routing network comprising a plurality of switches of size d×d, where d≥2, in each said stage and each said switch of size d×d having d inlet links and d outlet links; and

Said plurality of outlet links of said each sub-integrated circuit block are directly connected to said inlet links of said switches of its corresponding said lowest stage of 1, and said plurality of inlet links of said each sub-integrated circuit block are directly connected from said outlet links of said switches of its corresponding said lowest stage of 1; and

Said each sub-integrated circuit block comprising a plurality of forward connecting links connecting from switches in a lower stage to switches in its immediate succeeding higher stage, and also comprising a plurality of backward connecting links connecting from switches in a higher stage to switches in its immediate preceding lower stage; and

Said each sub-integrated circuit block comprising a plurality straight links in said forward connecting links from switches in said each lower stage to switches in its immediate succeeding higher stage and a plurality cross links in said forward connecting links from switches in said each lower stage to switches in its immediate succeeding higher stage, and further comprising a plurality of straight links in said backward connecting links from switches in said each higher stage to switches in its immediate preceding lower stage and a plurality of cross links in said backward connecting links from switches in said each higher stage to switches in its immediate preceding lower stage,

said plurality of sub-integrated circuit blocks arranged in a two-dimensional grid of rows and columns, and

said all straight links are connecting from switches in each said sub-integrated circuit block are connecting to switches in the same said sub-integrated circuit block; and said all cross links are connecting as either vertical or horizontal links between switches in two different said sub-integrated circuit blocks which are either placed vertically above or below, or placed horizontally to the left or to the right,

each said plurality of sub-integrated circuit blocks comprising same number of said stages and said switches in each said stage, regardless of the size of said two-dimensional grid so that each said plurality of sub-integrated circuit block with its corresponding said stages and said switches in each stage is replicable in both vertical direction or horizontal direction of said two-dimensional grid.

2. The integrated circuit device of claim 1 ,

said two-dimensional grid of said sub-integrated circuit blocks with their corresponding said stages and said switches in each stage is scalable by any power of 2, and,

for each multiplication of 2 of the size of total said sub-integrated circuit blocks, by adding one more stage of switches and the layout is placed in hypercube format and also the cross links between said one more stage of switches are connected in hypercube format.

3. The integrated circuit device of claim 2 , wherein said cross links in succeeding stages are connecting as alternative vertical and horizontal links between switches in said sub-integrated circuit blocks.

4. The integrated circuit device of claim 3 , wherein said cross links from switches in a stage in one of said sub-integrated circuit blocks are connecting to switches in the succeeding stage in another of said sub-integrated circuit blocks so that said cross links are either vertical links or horizontal and vice versa, and hereinafter such cross links are “shuffle exchange links”).

5. The integrated circuit device of claim 4 , wherein said all horizontal shuffle exchange links between switches in any two corresponding said succeeding stages are substantially of equal length and said vertical shuffle exchange links between switches in any two corresponding said succeeding stages are substantially of equal length in the entire said integrated circuit device.

6. The integrated circuit device of claim 5 , wherein the shortest horizontal shuffle exchange links are connecting at the lowest stage and between switches in two nearest neighboring said sub-integrated circuit blocks, and length of the horizontal shuffle exchange links is doubled in each succeeding stage; and the shortest vertical shuffle exchange links are connecting at the lowest stage and between switches in two nearest neighboring said sub-integrated circuit blocks, and length of the vertical shuffle exchange links is doubled in each succeeding stage.

7. The integrated circuit device of claim 6 , wherein y≥(log 2 N), where N>1, so that the length of the horizontal shuffle exchange links in the highest stage is equal to half the size of the horizontal size of said two dimensional grid of sub-integrated circuit blocks and the length of the vertical shuffle exchange links in the highest stage is equal to half the size of the vertical size of said two dimensional grid of sub-integrated circuit blocks.

8. The integrated circuit device of claim 7 , wherein d=2 and there is only one switch in each said stage in each said sub-integrated circuit block connecting said forward connecting links and there is only one switch in each said stage in each said sub-integrated circuit block connecting said backward connecting links and said routing network is rearrangeably nonblocking for unicast Benes network with full bandwidth.

9. The integrated circuit device of claim 7 , wherein d=2 and there are at least two switches in each said stage in each said sub-integrated circuit block connecting said forward connecting links and there are at least two switches in each said stage in each said sub-integrated circuit block connecting said backward connecting links and said routing network is strictly nonblocking for unicast Benes network and rearrangeably nonblocking for arbitrary fan-out multicast Benes network with full bandwidth.

10. The integrated circuit device of claim 7 , wherein d=2 and there are at least three switches in each said stage in each said sub-integrated circuit block connecting said forward connecting links and there are at least three switches in each said stage in each said sub-integrated circuit block connecting said backward connecting links and said routing network is strictly nonblocking for arbitrary fan-out multicast Benes network with full bandwidth.

11. The integrated circuit device of claim 6 , wherein y≥(log 2 N), where N>1, so that the length of the horizontal shuffle exchange links in the highest stage is equal to half the size of the horizontal size of said two dimensional grid of sub-integrated circuit blocks and the length of the vertical shuffle exchange links in the highest stage is equal to half the size of the vertical size of said two dimensional grid of sub-integrated circuit blocks, and

said each sub-integrated circuit block further comprising a plurality of U-turn links within switches in each of said stages in each of said sub-integrated circuit blocks.

12. The integrated circuit device of claim 11 , wherein d=2 and there is only one switch in each said stage in each said sub-integrated circuit block connecting said forward connecting links and there is only one switch in each said stage in each said sub-integrated circuit block connecting said backward connecting links and said routing network is rearrangeably nonblocking for unicast butterfly fat tree network with full bandwidth.

13. The integrated circuit device of claim 11 , wherein d=2 and there are at least two switches in each said stage in each said sub-integrated circuit block connecting said forward connecting links and there are at least two switches in each said stage in each said sub-integrated circuit block connecting said backward connecting links and said routing network is strictly nonblocking for unicast butterfly fat tree network and rearrangeably nonblocking for arbitrary fan-out multicast butterfly fat tree network with full bandwidth.

14. The integrated circuit device of claim 11 , wherein d=2 and there are at least three switches in each said stage in each said sub-integrated circuit block connecting said forward connecting links and there are at least three switches in each said stage in each said sub-integrated circuit block connecting said backward connecting links and said routing network is strictly nonblocking for arbitrary fan-out multicast butterfly fat tree network with full bandwidth.

15. The integrated circuit device of claim 1 , wherein said horizontal and vertical links are implemented on two or more metal layers.

16. The integrated circuit device of claim 1 , wherein said switches comprising active and reprogrammable cross points and said each cross point is programmable by an SRAM cell or a Flash Cell.

17. The integrated circuit device of claim 1 , wherein said sub-integrated circuit blocks are of equal die size.

18. The integrated circuit device of claim 15 , wherein said sub-integrated circuit blocks are Lookup Tables (hereinafter “LUTs”) and said integrated circuit device is a field programmable gate array (FPGA) device or field programmable gate array (FPGA) block embedded in another integrated circuit device.

19. The integrated circuit device of claim 15 , wherein said sub-integrated circuit blocks are AND or OR gates and said integrated circuit device is a programmable logic device (PLD).

20. The integrated circuit device of claim 1 , wherein said sub-integrated circuit blocks comprising any arbitrary hardware logic or memory circuits.

21. The integrated circuit device of claim 1 , wherein said switches comprising active one-time programmable cross points and said integrated circuit device is a mask programmable gate array (MPGA) device or a structured ASIC device.

22. The integrated circuit device of claim 1 , wherein said switches comprising passive cross points or just connection of two links or not and said integrated circuit device is a Application Specific Integrated Circuit (ASIC) device.

23. The integrated circuit device of claim 1 , wherein said sub-integrated circuit blocks further recursively comprise one or more super-sub-integrated circuit blocks and a sub-routing network.

24. The integrated circuit device of claim 4 , wherein said all horizontal shuffle exchange links between switches in any two corresponding said succeeding stages are of different length and said vertical shuffle exchange links between switches in any two corresponding said succeeding stages are of different length and y≥(log 2 N) where N>1.

25. The integrated circuit device of claim 24 , wherein d=2 and there is only one switch in each said stage in each said sub-integrated circuit block connecting said forward connecting links and there is only one switch in each said stage in each said sub-integrated circuit block connecting said backward connecting links and said routing network is rearrangeably nonblocking for unicast generalized multi-stage network with full bandwidth.

26. The integrated circuit device of claim 24 , wherein d=2 and there are at least two switches in each said stage in each said sub-integrated circuit block connecting said forward connecting links and there are at least two switches in each said stage in each said sub-integrated circuit block connecting said backward connecting links and said routing network is strictly nonblocking for unicast generalized multi-stage network and rearrangeably nonblocking for arbitrary fan-out multicast generalized multi-stage network with full bandwidth.

27. The integrated circuit device of claim 24 , wherein d=2 and there are at least three switches in each said stage in each said sub-integrated circuit block connecting said forward connecting links and there are at least three switches in each said stage in each said sub-integrated circuit block connecting said backward connecting links and said routing network is strictly nonblocking for arbitrary fan-out multicast generalized multi-stage network with full bandwidth.

28. The integrated circuit device of claim 4 , wherein said all horizontal shuffle exchange links between switches in any two corresponding said succeeding stages are of different length and said vertical shuffle exchange links between switches in any two corresponding said succeeding stages are of different length and y≥(log 2 N), where N>1, and

said each sub-integrated circuit block further comprising a plurality of U-turn links within switches in each of said stages in each of said sub-integrated circuit blocks.

29. The integrated circuit device of claim 28 , wherein d=2 and there is only one switch in each said stage in each said sub-integrated circuit block connecting said forward connecting links and there is only one switch in each said stage in each said sub-integrated circuit block connecting said backward connecting links and said routing network is rearrangeably nonblocking for unicast generalized butterfly fat tree network with full bandwidth.

30. The integrated circuit device of claim 28 , wherein d=2 and there are at least two switches in each said stage in each said sub-integrated circuit block connecting said forward connecting links and there are at least two switches in each said stage in each said sub-integrated circuit block connecting said backward connecting links and said routing network is strictly nonblocking for unicast generalized butterfly fat tree Network and rearrangeably nonblocking for arbitrary fan-out multicast generalized butterfly fat tree network with full bandwidth.

31. The integrated circuit device of claim 28 , wherein d=2 and there are at least three switches in each said stage in each said sub-integrated circuit block connecting said forward connecting links and there are at least three switches in each said stage in each said sub-integrated circuit block connecting said backward connecting links and said routing network is strictly nonblocking for arbitrary fan-out multicast generalized butterfly fat tree network with full bandwidth.

32. The integrated circuit device of claim 1 , wherein said straight links connecting from switches in each said sub-integrated circuit block are connecting to switches in the same said sub-integrated circuit block; and

said cross links are connecting as vertical or horizontal or diagonal links between two different said sub-integrated circuit blocks.

33. The integrated circuit device of claim 7 , wherein d=4 and there is only one switch in each said stage in each said sub-integrated circuit block connecting said forward connecting links and there is only one switch in each said stage in each said sub-integrated circuit block connecting said backward connecting links and said routing network is rearrangeably nonblocking for unicast multi-link Benes network with full bandwidth.

34. The integrated circuit device of claim 7 , wherein d=4 and there are at least two switches in each said stage in each said sub-integrated circuit block connecting said forward connecting links and there are at least two switches in each said stage in each said sub-integrated circuit block connecting said backward connecting links and said routing network is strictly nonblocking for unicast multi-link Benes network and rearrangeably nonblocking for arbitrary fan-out multicast multi-link Benes network with full bandwidth.

35. The integrated circuit device of claim 7 , wherein d=4 and there are at least three switches in each said stage in each said sub-integrated circuit block connecting said forward connecting links and there are at least three switches in each said stage in each said sub-integrated circuit block connecting said backward connecting links and said routing network is strictly nonblocking for arbitrary fan-out multicast multi-link Benes network with full bandwidth.

36. The integrated circuit device of claim 11 , wherein d=4 and there is only one switch in each said stage in each said sub-integrated circuit block connecting said forward connecting links and there is only one switch in each said stage in each said sub-integrated circuit block connecting said backward connecting links and said routing network is rearrangeably nonblocking for unicast multi-link butterfly fat tree network with full bandwidth.

37. The integrated circuit device of claim 11 , wherein d=4 and there are at least two switches in each said stage in each said sub-integrated circuit block connecting said forward connecting links and there are at least two switches in each said stage in each said sub-integrated circuit block connecting said backward connecting links and said routing network is strictly nonblocking for unicast multi-link butterfly fat tree network and rearrangeably nonblocking for arbitrary fan-out multicast multi-link butterfly fat tree network with full bandwidth.

38. The integrated circuit device of claim 11 , wherein d=4 and there are at least three switches in each said stage in each said sub-integrated circuit block connecting said forward connecting links and there are at least three switches in each said stage in each said sub-integrated circuit block connecting said backward connecting links and said routing network is strictly nonblocking for arbitrary fan-out multicast multi-link butterfly fat tree network with full bandwidth.

39. The integrated circuit device of claim 4 , wherein said all horizontal shuffle exchange links between switches in any two corresponding said succeeding stages are of different length and said vertical shuffle exchange links between switches in any two corresponding said succeeding stages are of different length and y≥(log 2 N), where N>1.

40. The integrated circuit device of claim 39 , wherein d=4 and there is only one switch in each said stage in each said sub-integrated circuit block connecting said forward connecting links and there is only one switch in each said stage in each said sub-integrated circuit block connecting said backward connecting links and said routing network is rearrangeably nonblocking for unicast generalized multi-link multi-stage network with full bandwidth.

41. The integrated circuit device of claim 39 , wherein d=4 and there are at least two switches in each said stage in each said sub-integrated circuit block) connecting said forward connecting links and there are at least two switches in each said stage in each said sub-integrated circuit block connecting said backward connecting links and said routing network is strictly nonblocking for unicast generalized multi-link multi-stage network and rearrangeably nonblocking for arbitrary fan-out multicast generalized multi-link multi-stage network with full bandwidth.

42. The integrated circuit device of claim 39 , wherein d=4 and there are at least three switches in each said stage in each said sub-integrated circuit block connecting said forward connecting links and there are at least three switches in each said stage in each said sub-integrated circuit block connecting said backward connecting links and said routing network is strictly nonblocking for arbitrary fan-out multicast generalized multi-link multi-stage network with full bandwidth.

43. The integrated circuit device of claim 4 , wherein said all horizontal shuffle exchange links between switches in any two corresponding said succeeding stages are of different length and said vertical shuffle exchange links between switches in any two corresponding said succeeding stages are of different length and y≥(log 2 N), where N>1, and

said each sub-integrated circuit block further comprising a plurality of U-turn links within switches in each of said stages in each of said sub-integrated circuit blocks.

44. The integrated circuit device of claim 43 , wherein d=4 and there is only one switch in each said stage in each said sub-integrated circuit block connecting said forward connecting links and there is only one switch in each said stage in each said sub-integrated circuit block connecting said backward connecting links and said routing network is rearrangeably nonblocking for unicast generalized multi-link butterfly fat tree network with full bandwidth.

45. The integrated circuit device of claim 43 , wherein d=4 and there are at least two switches in each said stage in each said sub-integrated circuit block connecting said forward connecting links and there are at least two switches in each said stage in each said sub-integrated circuit block connecting said backward connecting links and said routing network is strictly nonblocking for unicast generalized multi-link butterfly fat tree Network and rearrangeably nonblocking for arbitrary fan-out multicast generalized multi-link butterfly fat tree network with full bandwidth.

46. The integrated circuit device of claim 43 , wherein d=4 and there are at least three switches in each said stage in each said sub-integrated circuit block connecting said forward connecting links and there are at least three switches in each said stage in each said sub-integrated circuit block connecting said backward connecting links and said routing network is strictly nonblocking for arbitrary fan-out multicast generalized multi-link butterfly fat tree network with full bandwidth.

47. The integrated circuit device of claim 1 , wherein said plurality of forward connecting links use a plurality of buffers to amplify signals driven through them and said plurality of backward connecting links use a plurality of buffers to amplify signals driven through them; and said buffers can be inverting or non-inverting buffers.

48. The integrated circuit device of claim 1 , wherein said all switches of size d×d are either fully populated or partially populated.

49. A multi-stage network comprising: a plurality of blocks and a plurality of inlet links and a plurality of outlet links; and

wherein each block of said plurality of blocks comprising a y stages namely stage 1 to stage y, where y>2 and y is an integer, wherein stage 1 is hereinafter a input stage, stage y is hereinafter a output stage and remaining stages of said y stages hereinafter a middle stages, and

wherein each stage of said y stages comprising one or more switches of size d i ×d 0 , where d i ,d 0 are integers, and d i ≥2 and d 0 ≥2, each switch of said one or more switches of size d i ×d 0 having d i incoming links and d 0 outgoing links; and

wherein each outlet link of said plurality of outlet links is directly connected from a first outgoing link of said d 0 outgoing links of a first switch of said one or more switches of size d i ×d 0 of the output stage of said y stages of a first block of said plurality of blocks and each inlet link of said plurality of inlet links is directly connected to a first incoming link of said d i incoming links of one or more switches of said one or more switches of size d i ×d 0 of the input stage of said y stages of a first block of said plurality of blocks; and

each block of said plurality of blocks comprising a plurality of forward connecting links connecting from said one or more switches in each stage of said y stages except stage y to said one or more switches in an immediate succeeding stage of said y stages, and also comprising a plurality of backward connecting links connecting from said one or more switches in each stage of said y stages except stage 1 to said one or more switches in an immediate preceding stage of said y stages; and

said plurality of blocks arranged in a two-dimensional grid of a plurality of rows and a plurality of columns, and

said plurality of forward connecting links and said plurality of backward connecting links comprise a plurality of straight middle links connecting from said one or more switches of a first stage of said y stages in a first block of said plurality of blocks to said one or more switches of an immediate succeeding or an immediate preceding stage of said first stage of said y stages in said first block of said plurality of blocks; and

said plurality of forward connecting links and said plurality of backward connecting links comprise a plurality of cross middle links connecting from switches of said one or more switches in a stage of said y stages in a first block of said plurality of blocks to switches of said one or more switches in a succeeding stage or a preceding stage of a second block of said plurality of blocks which is either placed vertically above or below, or placed horizontally to left or to right of said first block of said plurality of blocks, wherein said plurality of cross middle links are either vertical tracks or horizontal tracks, and

wherein each block of said plurality of blocks comprising same number of said y stages, and each stage of said y stages comprising same number of said one or more switches of size d i ×d 0 is replicable in both vertical direction or horizontal direction of said two-dimensional grid of said plurality of rows and said plurality of columns regardless of the size of said two-dimensional grid of said plurality of rows and said plurality of columns, and

said plurality of cross middle links in succeeding stages of said y stages are connected alternately as vertical tracks and horizontal tracks (hereinafter “a hypercube topology”).

50. The multi-stage network of claim 49 , said plurality of blocks comprising said y stages arranged in a two-dimensional grid is scalable by any power of 2, and,

for each multiplication of 2 of size of total said plurality of blocks, by adding one more stage to said y stages and said hypercube topology is extended and placed in said hypercube topology and the cross middle links between said one more stage to said y stages of switches of said one or more switches are connected in said hypercube topology.

51. The multi-stage network of claim 49 , wherein said plurality of cross middle links between switches in any two same succeeding stages of said y stages are of equal length, and

a shortest cross middle links of said plurality of cross middle links are connected at stage 1 of said y stages and between switches of said one or more switches in two nearest neighboring said plurality of blocks, and length of the cross middle links is doubled in each succeeding stage of said y stages in either said vertical tracks or said horizontal tracks.

52. The multi-stage network of claim 51 , wherein y≥(log 2 N), where N>2, wherein length or width of the plurality of cross middle links in stage y is equal to half the length or width of said two dimensional grid of said plurality of blocks, and wherein d=2 and either

each stage of said y stages in each block of said plurality of blocks comprises only one switch of said one or more switches connecting said plurality of forward connecting links and each stage of said y stages in each block of said plurality of blocks comprises only one switch of said one or more switches connecting said plurality of backward connecting links and said multi-stage network is rearrangeably nonblocking for unicast Benes network, or

each stage of said y stages in each block of said plurality of blocks comprises at least two switches of said one or more switches connecting said plurality of forward connecting links and each stage of said y stages in each block of said plurality of blocks comprises at least two switches of said one or more switches connecting said plurality of backward connecting links and said multi-stage network is strictly nonblocking for unicast Benes network and is rearrangeably nonblocking for arbitrary fan-out multicast Benes network, or

each stage of said y stages in each block of said plurality of blocks comprises at least three switches of said one or more switches connecting said plurality of forward connecting links and each stage of said y stages in each block of said plurality of blocks comprises at least three switches of said one or more switches connecting said plurality of backward connecting links and said multi-stage network is strictly nonblocking for arbitrary fan-out multicast Benes network.

53. The multi-stage network of claim 51 , wherein y≥(log 2 N), where N>2, wherein length or width of the plurality of cross middle links in stage y is equal to half the length or width of said two dimensional grid of said plurality of blocks, and

each block of said plurality of blocks further comprising a plurality of U-turn links within switches of said one or more switches in each stage of said y stages in each block of said plurality of blocks, and wherein d=2 and either

each stage of said y stages in each block of said plurality of blocks comprises only one switch of said one or more switches connecting said plurality of forward connecting links and each stage of said y stages in each block of said plurality of blocks comprises only one switch of said one or more switches connecting said plurality of backward connecting links and said multi-stage network is rearrangeably nonblocking for unicast butterfly fat tree network, or

each stage of said y stages in each block of said plurality of blocks comprises at least two switches of said one or more switches connecting said plurality of forward connecting links and each stage of said y stages in each block of said plurality of blocks comprises at least two switches of said one or more switches connecting said plurality of backward connecting links and said multi-stage network is strictly nonblocking for unicast butterfly fat tree network and rearrangeably nonblocking for arbitrary fan-out multicast butterfly fat tree network, or

each stage of said y stages in each block of said plurality of blocks comprises at least three switches of said one or more switches connecting said plurality of forward connecting links and each stage of said y stages in each block of said plurality of blocks comprises at least three switches of said one or more switches connecting said plurality of backward connecting links and said multi-stage network is strictly nonblocking for arbitrary fan-out multicast butterfly fat tree network.

54. The multi-stage network of claim 49 , wherein said one or more switches comprising a plurality of reprogrammable cross points and said plurality of reprogrammable cross point is programmable by SRAM cells or Flash Cells, or

said plurality of forward connecting links use a plurality of buffers to amplify a signals driven through them and said plurality of backward connecting links use a plurality of buffers to amplify a signals driven through them; and said plurality of buffers are either inverting or non-inverting buffers.

55. The multi-stage network of claim 49 , wherein said one or more switches comprising passive cross points or just connection of two links or not.

56. The multi-stage network of claim 49 , wherein said plurality of cross middle links between switches of said one or more switches in any two succeeding stages of said y stages are of different length and said plurality of cross middle links between switches of said one or more switches in any two succeeding stages of said y stages are of different width and y≥(log 2 N), where N>2, and wherein d=2 and either

each stage of said y stages in each block of said plurality of blocks comprises only one switch of said one or more switches connecting said plurality of forward connecting links and each stage of said y stages in each block of said plurality of blocks comprises only one switch of said one or more switches connecting said plurality of backward connecting links and said multi-stage network is rearrangeably nonblocking for unicast generalized multi-stage network, or

each stage of said y stages in each block of said plurality of blocks comprises at least two switches of said one or more switches connecting said plurality of forward connecting links and each stage of said y stages in each block of said plurality of blocks comprises at least two switches of said one or more switches connecting said plurality of backward connecting links and said multi-stage network is strictly nonblocking for unicast generalized multi-stage network and rearrangeably nonblocking for arbitrary fan-out multicast generalized multi-stage network, or

each stage of said y stages in each block of said plurality of blocks comprises at least three switches of said one or more switches connecting said plurality of forward connecting links and each stage of said y stages in each block of said plurality of blocks comprises at least three switches of said one or more switches connecting said plurality of backward connecting links and said multi-stage network is strictly nonblocking for arbitrary fan-out multicast generalized multi-stage network.

57. The multi-stage network of claim 49 , wherein said plurality of cross middle links between switches of said one or more switches in any two succeeding stages of said y stages are of different length and said plurality of cross middle links between switches of said one or more switches in any two succeeding stages of said y stages are of different width and y≥(log 2 N), where N>2, and

each block of said plurality of blocks further comprising a plurality of U-turn links within switches of said one or more switches in each stage of said y stages in each block of said plurality of blocks, and

wherein d=2 and either

each stage of said y stages in each block of said plurality of blocks comprises only one switch of said one or more switches connecting said plurality of forward connecting links and each stage of said y stages in each block of said plurality of blocks comprises only one switch of said one or more switches connecting said plurality of backward connecting links and said multi-stage network is rearrangeably nonblocking for unicast generalized butterfly fat tree network, or

each stage of said y stages in each block of said plurality of blocks comprises at least two switches of said one or more switches connecting said plurality of forward connecting links and each stage of said y stages in each block of said plurality of blocks comprises at least two switches of said one or more switches connecting said plurality of backward connecting links and said multi-stage network is strictly nonblocking for unicast generalized butterfly fat tree Network and rearrangeably nonblocking for arbitrary fan-out multicast generalized butterfly fat tree network, or

each stage of said y stages in each block of said plurality of blocks comprises at least three switches of said one or more switches connecting said plurality of forward connecting links and each stage of said y stages in each block of said plurality of blocks comprises at least three switches of said one or more switches connecting said plurality of backward connecting links and said multi-stage network is strictly nonblocking for arbitrary fan-out multicast generalized butterfly fat tree network.

58. The multi-stage network of claim 51 , wherein y≥(log 2 N), where N>2, wherein length or width of said plurality of cross middle links in stage y is equal to half the size of said two dimensional grid of said plurality of blocks, and wherein d=4 and either

each stage of said y stages in each block of said plurality of blocks comprises only one switch of said one or more switches connecting said plurality of forward connecting links and each stage of said y stages in each block of said plurality of blocks comprises only one switch of said one or more switches connecting said plurality of backward connecting links and said multi-stage network is rearrangeably nonblocking for unicast multi-link Benes network, or

each stage of said y stages in each block of said plurality of blocks comprises at least two switches of said one or more switches connecting said plurality of forward connecting links and each stage of said y stages in each block of said plurality of blocks comprises at least two switches of said one or more switches connecting said plurality of backward connecting links and said multi-stage network is strictly nonblocking for unicast multi-link Benes network and rearrangeably nonblocking for arbitrary fan-out multicast multi-link Benes network, or

each stage of said y stages in each block of said plurality of blocks comprises at least three switches of said one or more switches connecting said plurality of forward connecting links and each stage of said y stages in each block of said plurality of blocks comprises at least three switches of said one or more switches connecting said plurality of backward connecting links and said multi-stage network is strictly nonblocking for arbitrary fan-out multicast multi-link Benes network.

59. The multi-stage network of claim 51 , wherein y≥(log 2 N), where N>2, wherein length or width of said plurality of cross middle links in stage y is equal to half the size of said two dimensional grid of said plurality of blocks, and

each block of said plurality of blocks further comprising a plurality of U-turn links within switches of said one or more switches in each stage of said y stages in each block of said plurality of blocks, and wherein d=4 and either

each stage of said y stages in each block of said plurality of blocks comprises only one switch of said one or more switches connecting said plurality of forward connecting links and each stage of said y stages in each block of said plurality of blocks comprises only one switch of said one or more switches connecting said plurality of backward connecting links and said multi-stage network is rearrangeably nonblocking for unicast multi-link butterfly fat tree network, or

each stage of said y stages in each block of said plurality of blocks comprises at least two switches of said one or more switches connecting said plurality of forward connecting links and each stage of said y stages in each block of said plurality of blocks comprises at least two switches of said one or more switches connecting said plurality of backward connecting links and said multi-stage network is strictly nonblocking for unicast multi-link butterfly fat tree network and rearrangeably nonblocking for arbitrary fan-out multicast multi-link butterfly fat tree network, or

each stage of said y stages in each block of said plurality of blocks comprises at least three switches of said one or more switches connecting said plurality of forward connecting links and each stage of said y stages in each block of said plurality of blocks comprises at least three switches of said one or more switches connecting said plurality of backward connecting links and said multi-stage network is strictly nonblocking for arbitrary fan-out multicast multi-link butterfly fat tree network.

60. The multi-stage network of claim 51 , wherein said plurality of cross middle links between switches of said one or more switches in any two succeeding stages of said y stages are of different length and said plurality of cross middle links between switches of said one or more switches in any two succeeding stages of said y stages are of different width and y≥(log 2 N), where N>2, and wherein d=4 and either

each stage of said y stages in each block of said plurality of blocks comprises only one switch of said one or more switches connecting said plurality of forward connecting links and each stage of said y stages in each block of said plurality of blocks comprises only one switch of said one or more switches connecting said plurality of backward connecting links and said multi-stage network is rearrangeably nonblocking for unicast generalized multi-link multi-stage network, or

each stage of said y stages in each block of said plurality of blocks comprises at least two switches of said one or more switches connecting said plurality of forward connecting links and each stage of said y stages in each block of said plurality of blocks comprises at least two switches of said one or more switches connecting said plurality of backward connecting links and said multi-stage network is strictly nonblocking for unicast generalized multi-link multi-stage network and rearrangeably nonblocking for arbitrary fan-out multicast generalized multi-link multi-stage network, or

each stage of said y stages in each block of said plurality of blocks comprises at least three switches of said one or more switches connecting said plurality of forward connecting links and each stage of said y stages in each block of said plurality of blocks comprises at least three switches of said one or more switches connecting said plurality of backward connecting links and said multi-stage network is strictly nonblocking for arbitrary fan-out multicast generalized multi-link multi-stage network.

61. The multi-stage network of claim 51 , wherein said plurality of cross middle links between switches of said one or more switches in any two succeeding stages of said y stages are of different length and said plurality of cross middle links between switches of said one or more switches in any two succeeding stages of said y stages are of different width and y≥(log 2 N), where N>2, and

each block of said plurality of blocks further comprising a plurality of U-turn links within switches of said one or more switches in each stage of said y stages in each block of said plurality of blocks, and wherein d=4 and either

each stage of said y stages in each block of said plurality of blocks comprises only one switch of said one or more switches connecting said plurality of forward connecting links and each stage of said y stages in each block of said plurality of blocks comprises only one switch of said one or more switches connecting said plurality of backward connecting links and said multi-stage network is rearrangeably nonblocking for unicast generalized multi-link butterfly fat tree network, or

each stage of said y stages in each block of said plurality of blocks comprises at least two switches of said one or more switches connecting said plurality of forward connecting links and each stage of said y stages in each block of said plurality of blocks comprises at least two switches of said one or more switches connecting said plurality of backward connecting links and said multi-stage network is strictly nonblocking for unicast generalized multi-link butterfly fat tree Network and rearrangeably nonblocking for arbitrary fan-out multicast generalized multi-link butterfly fat tree network, or each stage of said y stages in each block of said plurality of blocks comprises at least three switches of said one or more switches connecting said plurality of forward connecting links and each stage of said y stages in each block of said plurality of blocks comprises at least three switches of said one or more switches connecting said plurality of backward connecting links and said multi-stage network is strictly nonblocking for arbitrary fan-out multicast generalized multi-link butterfly fat tree network.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Apr 15, 2019
From: KONDA TECHNOLOGIES INC.
To: KONDA, VENKAT
Reel/Frame 048887/0397 →
Continuity (2)
Provisional Application 60940394 · May 25, 2007
Reissue 12601275 · May 22, 2008
References Cited (64)
US 4813038A · Lee · 1989 [cited by examiner]
US 5153843A · Batcher · 1992 [cited by applicant]
US 5406556A · Widjaja et al. · 1995 [cited by examiner]
US 5451936A · Yang et al. · 1995 [cited by applicant]
US 5856977A · Yang et al. · 1999 [cited by examiner]
US 6018523A · Even · 2000 [cited by applicant]
US 6049542A · Prasad · 2000 [cited by examiner]
US 6157643A · Ma · 2000 [cited by examiner]
US 6185220B1 · Muthukrishnan et al. · 2001 [cited by applicant]
US 6567858B1 · Yang et al. · 2003 [cited by examiner]
US 6940308B2 · Wong · 2005 [cited by examiner]
US 7130920B1 · Sailor · 2006 [cited by examiner]
US 7136380B2 · Li · 2006 [cited by examiner]
US 7154887B2 · Wu et al. · 2006 [cited by examiner]
US 7161906B2 · Dell · 2007 [cited by examiner]
US 7346049B2 · Towles · 2008 [cited by examiner]
US 7349387B2 · Wu · 2008 [cited by examiner]
US 7397796B1 · Smiljani · 2008 [cited by examiner]
US 7424010B2 · Konda · 2008 [cited by examiner]
US 7424011B2 · Konda · 2008 [cited by examiner]
US 7468974B1 · Carr et al. · 2008 [cited by examiner]
US 7924052B1 · Feng et al. · 2011 [cited by examiner]
US 8098081B1 · Trimberger · 2012 [cited by examiner]
US 8170040B2 · Konda · 2012 [cited by applicant]
US 8270400B2 · Konda · 2012 [cited by applicant]
US 8363649B2 · Konda · 2013 [cited by applicant]
US 20100135286A1 · Konda · 2010 [cited by applicant]
US 20100172349A1 · Konda · 2010 [cited by applicant]
US 20110037498A1 · Konda · 2011 [cited by applicant]
US 20110044329A1 · Konda · 2011 [cited by applicant]
WO WO2008109756 · 2008 [cited by applicant]
WO WO2008147928A1 · 2008 [cited by applicant]
WO WO2008147926 · 2008 [cited by applicant]
WO WO2008147927 · 2008 [cited by applicant]
Guy Lemieux et.al., Generating highlyroutablesparse crossbars for PLDs. In ACMISIGDA Int'l. Symposium on Field Programmable Gate Arrays, pp. 155-164, Monterey, CA, Feb. 2000. [cited by applicant]
S. Sivaswamy et al., “HARP: hard-wired routing pattern FPGAs”, FPGA'05, Monterey, California, USA, Feb. 20-22, 2005. [cited by applicant]
Yeh, C.-H., E.A. Varvarigos, and B. Parhami, “Efficient VLSI layouts of hypercubic networks,” Proc. Symp. Frontiers of Massively Parallel Computation, Feb. 1999. [cited by applicant]
C. Clos, “A Study of Non-Blocking Switching Networks,” Bell System Technical Journal, 32:406-424, 1953. [cited by applicant]
A. DeHon, “Balancing Interconnect and Computation in a Reconfigurable Computing Array,” ACM Int. Symp. on FPGA, pp. 69-78, Feb. 1999. [cited by applicant]
Chihming Chang, Rami Melhem, “Arbitrary Size Benes Networks”, Journal: Parallel Processing Letters—PPL , vol. 7, No. 3, pp. 279-284, 1997. [cited by applicant]
Hoda El-Sayed and Abdou Youssef; “The r-truncated Benes Networks and their Randomized Routing Algorithms” 1997 Intl Conf on Parallel and Dist Sys, Seoul, Korea, Dec. 1997. [cited by applicant]
Guy Lemieux and David Lewis, “Using Sparse Crossbars within LUT Clusters”, Procds of the ACM/SIGDA Intl Symp on Field Prog Gate Arrays 2001, Feb. 11-13, 2001, Monterey, CA. [cited by applicant]
P. Manuel, W. K. Qureshi, A. William, A. Muthumalai, “VLSI layout of Benes networks,”, J. of Discrete Math. Sci. & Cryptography, vol. 10, No. 4, pp. 461-472, 2007. [cited by applicant]
Quinn, Michael J, “Parallel Computing: Theory and Practice”, 2nd. ed., 1994, McGraw Hill Series in computer Science, Networks, and parallel computing, ISBN 0-07-051294-9. [cited by applicant]
Ronald I. Greenberg, “The Fat-Pyramid and Universal Parallel Computation Independent of wire delay” IEEE Trans. Computers, 43(12):1358-1364, Dec. 1994. [cited by applicant]
Hypertree: A Multiprocessor Interconnection Topology , by James R. Goodman and Carlo H Sequin, Computer Science Technical Report #427, Dept , of EECS, University of California. [cited by applicant]
Data Movement Techniques for the pyramid computer, Russ Miller and Quentin F. Stout, SIAM Journal on Computing, vol. 16, No. 1, pp. 38-60, Feb. 1987. [cited by applicant]
A. DeHon, “Unifying Mesh- and Tree-Based Programmable Interconnect,” IEEE Trans. on Very Large Scale Int. Systems, vol. 12, No. 10, pp. 1051-1065, Oct. 2004. [cited by applicant]
Guy Lemieux and David Lewis. Analtyical framework for switch block design. In Intl. Conference on Field Programmable Logic and Applications, pp. 122-131, Sep. 2002. [cited by applicant]
Chen, G; Lau, FCM, “A tight layout of the cube-connected cycles”, The 4th International Conference on High Perf. Computing, Bangalore, India, Dec. 18-21, 1997, p. 422-427. [cited by applicant]
Michael Shyu, Yu-Dong Chang, Guang-Ming Wu, and Yao-Wen Chang, Generic universal switch blocks. IEEE Transactions on Computers,49(4):348-359, Apr. 2000. [cited by applicant]
Y. Yamada, et al. , “Folded Fat H-Tree: an interconnection topology for Dynamically Reconfigurable Processor Array”, Embed and Ubiq. Cmpting, Intl Conf. EUC 2004. [cited by applicant]
A. DeHon. Balancing Interconnect and Computation in a Reconfigurable Computing Array (or, why you don't really want 100% LUT utili). In Proc. of intl. symp. on FPGAs, Feb. 1999. [cited by applicant]
André DeHon. Compact, Multilayer Layout for Butterfly Fat-Tree. In Twelfth Annual ACM Symposium on Parallel Algs and Architectures (SPAA 2000), pp. 206-215, Jul. 9-12, 2000. [cited by applicant]
V. P. Roychdowdhury et. al., “Segmented Channel Routing,” IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, No. 1, pp. 79-95, Jan. 1993. [cited by applicant]
Ivo Dobbelaere, Mark Horowitz, and Abbas El Gamal. Regenerative feedback repeaters for programmable interconnections. IEEE Journal of Solid-State Circuits, 30(11), 1995. [cited by applicant]
F. Petrini et. al., k-ary n-trees: High performance networks for massively parallel architectures, in: Proceedings of the 11th Intl Parallel Proc. Symp. , IPPS'97, pp. 87-93. [cited by applicant]
P.Pande et al. “Evaluation of MP-Soc Interconnect Architectures: a Case Study”, Proceedings of 4th IWSOC, Banff, Alberta, Canada, Jul. 19-21, 2004. [cited by applicant]
Yeh, C.-H., Varvarigos, E.A., Parhami, B.: Multilayer VLSI layout for interconnection networks. In: Proc. Intl. Conf. on Parallel Processing, 2000. [cited by applicant]
M. Lin, A. El Gamal, “A Low-Power Field-Programmable Gate Array Routing Fabric,” IEEE Transactions on Very Large Scale Integration, vol. 17, No. 10, pp. 1481-1494, Oct. 2009. [cited by applicant]
Avior, A et. al., A Tight Layout of the Butterfly Network. Proc. 8-th Annual ACM Symp. on Parallel Alg. and Arch. (SPAA '96), ACM Press Ed., 1996, pp. 170-175. [cited by applicant]
A. El Gamal et. al., “An Architecture for Electrically Configurable Gate Arrays,” IEEE Jrnl of Solid-State Circuits, vol. 24, No. 2, pp. 394-398, Apr. 1989. [cited by applicant]
Vaughn Betz et. al., Directional bias and non-uniformity in FPGA global routing architectures. In IEEE/ACM Intl. Conference on Computer-Aided Design, pp. 652-659, san jose, 96. [cited by applicant]
André DeHon. Rent's Rule Based Switching Requirements. In System-Level Interconnect Prediction (SLIP 2001), pp. 197-204, Mar. 31-Apr. 1, 2001. [cited by applicant]