VLSI layouts of fully connected generalized and pyramid networks with locality exploitation

• US 9,529,958 B2
• Filed: 10/24/2014
• Issued: 12/27/2016
• Est. Priority Date: 10/24/2014
• Status: Active Grant

• Current Assignee: Konda Technologies, Inc.
• Original Assignee: Konda Technologies, Inc.
• Inventors: Konda, Venkat
• Primary Examiner(s): TAT, BINH C
• Application Number:
  US14/522,599
• Publication Number:
  US 20150046895A1
• Time in Patent Office: 795 Days
• Field of Search: 716126-130
• US Class Current: 1/1
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]
• CPC Class Codes: G06F 30/347 Physical level, e.g. placement or routing
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence
• CPC Class Codes: H04L 12/50 Circuit switching systems, i.e. systems in which the path is physically permanent during the communication
• CPC Class Codes: H04L 49/10 characterised by the switching fabric construction
• CPC Class Codes: H04L 49/1507 Distribute and route fabrics, e.g. sorting-routing or Batcher-Banyan

Abstract

VLSI layouts of generalized multi-stage and pyramid networks for broadcast, unicast and multicast connections are presented using only horizontal and vertical links with spacial locality exploitation. 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. Furthermore the shuffle exchange links are employed between different sub-integrated circuit blocks so that spacially nearer sub-integrated circuit blocks are connected with shorter links compared to the shuffle exchange links between spacially farther sub-integrated circuit blocks. 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 with spacial locality exploitation presented are applicable to generalized multi-stage and pyramid networks, generalized folded multi-stage and pyramid networks, generalized butterfly fat tree and pyramid networks, generalized multi-link multi-stage and pyramid networks, generalized folded multi-link multi-stage and pyramid networks, generalized multi-link butterfly fat tree and pyramid networks, generalized hypercube networks, and generalized cube connected cycles networks for speedup of s≧1. 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

1. A two-dimensional layout of hierarchical routing network implemented in a non-transitory medium comprising:

a total of a×

b blocks with one side of said layout having the size of “

a”

blocks and the other side of said layout having the size of “

b”

blocks where a≧

1 and b≧

1, and

said routing network comprising a total of N₁ inlet links and a total of N₂ outlet links and y hierarchical stages where y≧

1, N₁>

1 and N₂>

1 wherein either

N₂=N₁×

p₂, N₁=(a×

b)×

p, and said each block comprising at most p inlet links and at most p×

p₂ outlet links;

or

N₁=N₂×

p₁, N₂=(a×

b)×

p, and said each block comprising at most p outlet links and at most p×

p₁ inlet links, where p≧

1, p₁≧

1 and p₂≧

1, and

said each stage comprising at least one switch of size d×

d, where d≧

2 and each said switch of size d×

d having d incoming links and d outgoing links; and

said each block may not be comprising the same number of said inlet links and may not be comprising the same number of said out links;

said each block may not be comprising the same number of said stages;

said each stage may not be comprising the same number of switches; and

said each switch in said each stage may not be of the same size d,

Said inlet links directly connected to one or more said incoming links, and said outgoing links directly connected to one or more said outlet links,

said incoming links and outgoing links in each switch in said each stage of said each block comprising a plurality of forward connecting links connected from switches in lower stage to switches in the immediate succeeding higher stage, and also comprising a plurality of backward connecting links connected from switches in higher stage to switches in the immediate preceding lower stage; and

said forward connecting links comprising a plurality of straight links connected from a switch in a stage in a block to a switch in another stage in the same block and also comprising a plurality of cross links connected from a switch in a stage in a block to a switch in another stage in a different block, and

said backward connecting links comprising a plurality of straight links connected from a switch in a stage in a block to a switch in another stage in the same block and also comprising a plurality of cross links connected from a switch in a stage in a block to a switch in another stage in a different block; and

said all cross links are connected as either vertical or horizontal links between switches in two different said blocks.

2. The two-dimensional layout of hierarchical routing network implemented in a non-transitory medium of claim 1, wherein either said cross links from switches in a stage in one of said blocks are connected to switches in the succeeding stage in another of said blocks so that said cross links are either vertical links or horizontal links and vice versa, and hereinafter such cross links are “

shuffle exchange links”

).

3. The two-dimensional layout of hierarchical routing network implemented in a non-transitory medium of claim 2, wherein said all horizontal shuffle exchange links are connected, in each said stage, between two sets of different blocks with each said set being separated by blocks of size d^x where 0≦

x≦

y such that x=0 for the lowest stage and x=y for the highest stage and each block in one of the said sets is connected to at least one block in said second set excepting when the number of blocks in one of the sets are less than the number of blocks in said second set, and

said all vertical shuffle exchange links are connected, in each said stage, between two sets of different blocks with each said set being separated by blocks of size d^x where 0≦

x≦

y such that x=0 for the lowest stage and x=y for the highest stage and each block in one of the said sets is connected to at least one block in said second set excepting when the number of blocks in one of the sets are less than the number of blocks in said second set.

4. The two-dimensional layout of hierarchical routing network implemented in a non-transitory medium of claim 3, 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 two-dimensional layout, and

the shortest horizontal shuffle exchange links are connected at the lowest stage and between switches in two nearest neighboring said blocks, and length of the horizontal shuffle exchange links is doubled in each succeeding stage;

and the shortest vertical shuffle exchange links are connected at the lowest stage and between switches in two nearest neighboring said blocks, and length of the vertical shuffle exchange links is doubled in each succeeding stage.

5. The two-dimensional layout of hierarchical routing network implemented in a non-transitory medium of claim 3, wherein said all horizontal shuffle exchange links between switches of a block one in each said two sets of blocks in any two corresponding said succeeding stages are connected so that the two nearest neighbors are connected first and then the two nearest neighbors are connected in the remaining blocks which is repeated until the switches in all the blocks are connected, and said all vertical shuffle exchange links between switches of a block one in each said two sets of blocks in any two corresponding said succeeding stages are connected so that the two nearest neighbors are connected first and then the two nearest neighbors are connected in the remaining blocks which is repeated until the switches in all the blocks are connected in the entire said two-dimensional layout.

6. The two-dimensional layout of hierarchical routing network implemented in a non-transitory medium of claim 4, wherein y≧

(log₂(N₁)) when N₂=N₁×

p₂, or y≧

(log₂(N₂)) when N₁=N₂×

p₁ 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 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 blocks.

7. The two-dimensional layout of hierarchical routing network implemented in a non-transitory medium of claim 6, wherein d=2 and there is only one switch in each said stage in each said block connected said forward connecting links and there is only one switch in each said stage in each said block connected said backward connecting links and said routing network is rearrangeably nonblocking for unicast Benes network with full bandwidth.

8. The two-dimensional layout of hierarchical routing network implemented in a non-transitory medium of claim 6, wherein d=2 and there are at least two switches in each said stage in each said block connected said forward connecting links and there are at least two switches in each said stage in each said block connected 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.

9. The two-dimensional layout of hierarchical routing network implemented in a non-transitory medium of claim 6, wherein d=2 and there are at least three switches in each said stage in each said block connected said forward connecting links and there are at least three switches in each said stage in each said block connected said backward connecting links and said routing network is strictly nonblocking for arbitrary fan-out multicast Benes network with full bandwidth.

10. The two-dimensional layout of hierarchical routing network implemented in a non-transitory medium of claim 4, wherein y≧

(log₂(N₁)) when N₂=N₁×

d₂, or y≧

(log₂(N₂)) when N₁=N₂×

d₁ 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 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 blocks, and

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

11. The two-dimensional layout of hierarchical routing network implemented in a non-transitory medium of claim 10, wherein d=2 and there is only one switch in each said stage in each said block connected said forward connecting links and there is only one switch in each said stage in each said block connected said backward connecting links and said routing network is rearrangeably nonblocking for unicast butterfly fat tree network with full bandwidth.

12. The two-dimensional layout of hierarchical routing network implemented in a non-transitory medium of claim 10, wherein d=2 and there are at least two switches in each said stage in each said block connected said forward connecting links and there are at least two switches in each said stage in each said block connected 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.

13. The two-dimensional layout of hierarchical routing network implemented in a non-transitory medium of claim 10, wherein d=2 and there are at least three switches in each said stage in each said block connected said forward connecting links and there are at least three switches in each said stage in each said block connected said backward connecting links and said routing network is strictly nonblocking for arbitrary fan-out multicast butterfly fat tree network with full bandwidth.

14. The two-dimensional layout of hierarchical routing network implemented in a non-transitory medium of claim 1, wherein said physical medium is an electrical substrate and said switches comprising active and reprogrammable cross points and said each cross point is programmable by an SRAM cell or a Flash Cell, or

said switches are implemented by multiplexers and said each multiplexer is controlled by an SRAM cell or a Flash cell and;

said horizontal and vertical links are implemented on two or more different layers.

15. The two-dimensional layout of hierarchical routing network implemented in a non-transitory medium of claim 14, wherein said blocks further comprising Lookup Tables (hereinafter “

LUTs”

) having outlet links connected to inlet links of said routing network and further having inlet links connected from outlet links of said routing network and said two-dimensional layout with said blocks of LUTs is a field programmable gate array (FPGA) integrated circuit device or field programmable gate array (FPGA) block embedded in another integrated circuit device, or

said blocks further comprising AND or OR gates having outlet links connected to inlet links of said routing network and further having inlet links connected from outlet links of said routing network and said two-dimensional layout with said blocks of AND or OR gates is a programmable logic device (PLD).

16. A hierarchical network implemented in a non-transitory medium comprising a plurality of sub-networks arranged in a two dimensional layout of rows and columns, said each sub-network comprising a plurality of inlet links and a plurality of outlet links, and said each sub-network further comprising a plurality of stages, and said plurality of stages in a said sub-network comprising a plurality of multiplexers where each said multiplexer may be different size of d:

1, where d>

=1;

a first multiplexer of said plurality of multiplexers in a first stage of said plurality of stages of a first sub-network of said plurality of sub-networks having inputs connected from, hereinafter “

incoming links”

, the output of either a second multiplexer of said plurality of multiplexers in said first stage of said plurality of stages of said first sub-network of said plurality of sub-networks or a second multiplexer of said plurality of multiplexers in a second stage of said plurality of stages in said first sub-network of said plurality of sub-networks, or a second multiplexer of said plurality of multiplexers in a second stage of said plurality of stages of a second sub-network of said plurality of sub-networks, or from one of said outlet links;

a first multiplexer of said plurality of multiplexers in a first stage of said plurality of stages of a first sub-network of said plurality of sub-networks having output connected to, hereinafter “

outgoing links”

, one of the inputs of either a second multiplexer of said plurality of multiplexers in said first stage of said plurality of stages of said first sub-network of said plurality of sub-networks or a second multiplexer of said plurality of multiplexers in a second stage of said plurality of stages in said first sub-network of said plurality of sub-networks, or a second multiplexer of said plurality of multiplexers in a second stage of said plurality of stages of a second sub-network of said plurality of sub-networks, or from one of said outlet links;

said plurality of multiplexers in a first stage of said plurality of stages may be different in number from said plurality of multiplexers in a second stage of said plurality of stages;

said plurality of stages in a first of said plurality of sub-networks may be different in number from said plurality of stages in a second of said plurality of sub-networks;

said each row of said two dimensional layout may not have the same number of said plurality of subnetworks;

said each column of said two dimensional layout may not have the same number of said plurality of subnetworks;

said each sub-network may not have the same number of said inlet links and said each sub-network may not have the same number of said outlet links;

one or more of said incoming links and said outgoing links between any two said sub-networks are connected either as horizontal wires or as vertical wires.

17. A method for setting up one or more new multicast connections in a network comprising a plurality of sub-networks arranged in a two dimensional layout of rows and columns, said each sub-network comprising a plurality of inlet links and a plurality of outlet links, and said each sub-network further comprising a plurality of stages, and said plurality of stages in a said sub-network comprising a plurality of multiplexers where each said multiplexer may be different size of d>

=1;

a first multiplexer of said plurality of multiplexers in a first stage of said plurality of stages of a first sub-network of said plurality of sub-networks having inputs connecting from, hereinafter “

incoming links”

, the output of either a second multiplexer of said plurality of multiplexers in said first stage of said plurality of stages of said first sub-network of said plurality of sub-networks or a second multiplexer of said plurality of multiplexers in a second stage of said plurality of stages in said first sub-network of said plurality of sub-networks, or a second multiplexer of said plurality of multiplexers in a second stage of said plurality of stages of a second sub-network of said plurality of sub-networks, or from one of said outlet links;

a first multiplexer of said plurality of multiplexers in a first stage of said plurality of stages of a first sub-network of said plurality of sub-networks having output connecting to, hereinafter “

outgoing links”

, one of the inputs of either a second multiplexer of said plurality of multiplexers in said first stage of said plurality of stages of said first sub-network of said plurality of sub-networks or a second multiplexer of said plurality of multiplexers in a second stage of said plurality of stages in said first sub-network of said plurality of sub-networks, or a second multiplexer of said plurality of multiplexers in a second stage of said plurality of stages of a second sub-network of said plurality of sub-networks, or from one of said outlet links;

said plurality of multiplexers in a first stage of said plurality of stages may be different in number from said plurality of multiplexers in a second stage of said plurality of stages;

said plurality of stages in a first of said plurality of sub-networks may be different in number from said plurality of stages in a second of said plurality of sub-networks;

said each row of said two dimensional layout may not have the same number of said plurality of subnetworks;

said each column of said two dimensional layout may not have the same number of said plurality of subnetworks;

said each sub-network may not have the same number of said inlet links and said each sub-network may not have the same number of said outlet links;

one or more of said incoming links and said outgoing links between any two said sub-networks are connected either as horizontal wires or as vertical wires, said method comprising;

receiving a multicast connection at said one of inlet links;

fanning out said multicast connection through one or more of the multiplexers having said inlet link as input, to set up said multicast connection to a plurality of outlet links, wherein said plurality of outlet links are specified as destinations of said multicast connection, wherein multiplexers are available in one or more sub-networks including the sub-network having said inlet link and sub-networks having said outlet links with said multiplexers belonging to one or more said stages of said sub-networks and also the straight links or cross links are available which are connecting said multiplexers of said all sub-networks;

wherein a connection exists through said network and said method further comprising;

checking if any of said plurality of multiplexers is used to setup more than one said multicast connections and,

if necessary, changing said connection to pass through another plurality of said multiplexers of said stages of said sub-networks, act hereinafter “

rearranging connection”

.

18. The method of claim 17 further comprising:

disconnecting a plurality of previously set up multicast connections when at least one of said multiplexers of said stages of said sub-networks is used by both said new multicast connection and said plurality of previously set up multicast connections and;

setting up said plurality of previously set up multicast connections as other new multicast connections, through another plurality of said multiplexers of said stages of said sub-networks and;

repeating said acts of disconnecting said plurality of previously set up connections and setting up as said other new multicast connections for all the remaining previously set up connections.

19. The method of claim 17 further comprising:

setting up said new multicast connection through another plurality of said multiplexers of said stages of said sub-networks which are already in use by one or more existing multicast connections (hereinafter called “

incompatible existing connections”

); and

disconnecting said incompatible existing connections and;

for all said incompatible existing connections recursively repeating said acts of disconnecting and setting up connections, until all said incompatible existing multicast connections are set up.

20. The method of claim 17 wherein any of said acts of checking, setting, disconnecting and rearranging are performed repeatedly in a plurality of passes or iterations until none of said plurality of said multiplexers of said stages of said sub-networks are used by more than one said multicast connection, or

any of said acts of checking, setting, disconnecting and rearranging are performed recursively in a plurality of passes or iterations until none of said plurality of said multiplexers of said stages of said sub-networks are used by more than one said multicast connection.