US 8,898,611 B2Granted

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

AssigneeKonda Technologies Inc.

InventorVenkat Konda

Life of this patent

Estimating the term…

Loading patent…

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.

Claims20

Dependent claims

An electrical network on an electrical substrate comprising a plurality of sub-networks corresponding to blocks arranged in a two dimensional layout for a total of a×b said sub-networks with one side of said layout having the size of a sub-networks and the other side of said layout having the size of b sub-networks where a≧1 and b≧1, and

Said electrical network on an electrical substrate comprising at most N1 inlet links and at most N2 outlet links where N1>1 and N2>1 wherein either
N2=N1×p2, N1=(a×b)×p, and said each sub-network comprising at most p inlet links and at most p×p2 outlet links;
or
N1=N2×p1, N2=(a×b)×p, and said each sub-network comprising at most p outlet links and at most p×p1 inlet links, and
Said each sub-network comprising at most y stages, starting from the lowest stage of 1 to the highest stage of y, where y≧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 sub-network may not be comprising the same number of said inlet links and may not be comprising the same number of said outlet links;
Said each sub-network 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 incoming links and said outgoing links in each said switch in said each stage of said each sub-network comprising a plurality of forward connecting links connecting from switches in lower stage to said switches one of succeeding higher stages, and also comprising a plurality of backward connecting links connecting from said switches in higher stage to said switches one of preceding lower stage;
and
Said forward connecting links comprising a plurality of straight links connecting from a said switch in a said stage in a said sub-network to a said switch in another stage in the same said sub-network and also comprising a plurality of cross links connecting from a said switch in a said stage in a sub-network to a said switch in another said stage in a different said sub-network, and
Said backward connecting links comprising a plurality of straight links connecting from a said switch in a said stage in a said sub-network to a said switch in another said stage in the same said sub-network and also comprising a plurality of cross links connecting from a said switch in a said stage in a said sub-network to a said switch in another said stage in a different said sub-network,
said all cross links are connecting as either vertical or horizontal links between said switches between each two different said sub-networks, which are either placed vertically above or below, or placed horizontally to the left or to the right.

14 more elements

A method for setting up one or more new electrical multicast connections in a network comprising a plurality of sub-networks corresponding to blocks arranged in a two dimensional layout for a total of a×b said sub-networks with one side of said layout having the size of a sub-networks and the other side of said layout having the size of b sub-networks where a≧1 and b≧1 and

Said network comprising at most N1 inlet links and at most N2 outlet links where N1>1 and N2>1 wherein either
N2=N1×p2, N1=(a×b)×p, and said each sub-network comprising at most p inlet links and at most p×p2 outlet links;
or
N=N2×p1, N2=(a×b)×p, and said each sub-network comprising at most p outlet links and at most p×p1 inlet links, and
Said each sub-network comprising at most y stages, starting from the lowest stage of 1 to the highest stage of y, where y≧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 sub-network may not be comprising the same number of said inlet links and may not be comprising the same number of said outlet links;
Said each sub-network 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 incoming links and said outgoing links in each said switch in said each stage of said each sub-network comprising a plurality of forward connecting links connecting from switches in lower stage to said switches one of succeeding higher stages, and also comprising a plurality of backward connecting links connecting from said switches in higher stage to said switches one of preceding lower stages;
and
Said forward connecting links comprising a plurality of straight links connecting from a said switch in a said stage in a said sub-network to a said switch in another stage in the same said sub-network and also comprising a plurality of cross links connecting from a said switch in a said stage in a sub-network to a said switch in another said stage in a different said sub-network, and
Said backward connecting links comprising a plurality of straight links connecting from a said switch in a said stage in a said sub-network to a said switch in another said stage in the same said sub-network and also comprising a plurality of cross links connecting from a said switch in a said stage in a said sub-network to a said switch in another said stage in a different said sub-network,
Said all cross links are connecting as either vertical or horizontal links between said switches between each two different said sub-networks, which are either placed vertically above or below, or placed horizontally to the left or to the right, said method comprising:
receiving an electrical multicast connection at said one of inlet links;
fanning out said electrical multicast connection through one or more of the switches having said inlet link as input, to set up said electrical multicast connection to a plurality of outlet links, wherein said plurality of outlet links are specified as destinations of said electrical multicast connection, wherein switches 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 switches 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 switches of said all sub-networks;
wherein a connection exists through said network and said method further comprising:
if necessary, changing said connection to pass through another plurality of said switches of said stages of said sub-networks, act hereinafter “rearranging connection”.

18 more elements

Dependencies are inferred from the claim text.

Facts

Application: 13/502,207Filed 16 Oct 2010 · us provisional application
Priority: 16 Oct 2009
Published: US 2012/0269190 A125 Oct 2012
Granted: 25 Nov 2014
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

H04L 49/1515
Interconnection of switching modules: non-blocking multistage, e.g. Clos
G06F 30/18
Geometric CAD: network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air…
G06F 30/34
Circuit design: for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]
G06F 30/347
For reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]: physical level, e.g. placement or routing