公开(公告)号：US11811683B1

公开(公告)日：2023-11-07

申请号：US17938928

申请日：2022-09-06

申请人： Venkat Konda

发明人： Venkat Konda

IPC分类号： G06F30/394 ,  H04L49/15 ,  G06F30/34 ,  H04L12/50 ,  H04L49/10

CPC分类号： H04L49/1507 ,  G06F30/34 ,  G06F30/394 ,  H04L12/50 ,  H04L49/10

摘要： 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 spatially nearer sub-integrated circuit blocks are connected with shorter links compared to the shuffle exchange links between spatially 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.

公开(公告)号：US10992597B2

公开(公告)日：2021-04-27

申请号：US16562450

申请日：2019-09-06

申请人： Venkat Konda

发明人： Venkat Konda

IPC分类号： H04L12/933

摘要： Significantly optimized multi-stage networks including scheduling methods for faster scheduling of connections, useful in wide target applications, with VLSI layouts using only horizontal wires and vertical wires to route large scale partial multi-stage hierarchical networks having inlet and outlet links, and laid out in an integrated circuit device in a two-dimensional grid arrangement of blocks are disclosed. The optimized multi-stage networks in each block employ one or more slices of rings of stages of switches with inlet and outlet links of partial multi-stage hierarchical networks connecting to rings from either left-hand side or right-hand side; and employ hop wires or multi-drop hop wires wherein hop wires or multi-drop wires are connected from switches of stages of rings of slices of a first partial multi-stage hierarchical network switches of stages of a rings of slices of the first or a second partial multi-stage hierarchical network.

公开(公告)号：US08270400B2

公开(公告)日：2012-09-18

申请号：US12530207

申请日：2008-03-06

申请人： Venkat Konda

发明人： Venkat Konda

IPC分类号： H04L12/28

CPC分类号： H04Q3/68 ,  H04Q2213/1302 ,  H04Q2213/1304 ,  H04Q2213/13242 ,  H04Q2213/1334 ,  H04Q2213/13341

摘要： A multi-stage network comprising (2×logd N)−1 stages is operated in strictly nonblocking manner for unicast, also in rearrangeably nonblocking manner for arbitrary fan-out multicast when s≧2 , and is operated in strictly nonblocking manner for arbitrary fan-out multicast when s≧3 , includes an input stage having N d switches with each of them having d inlet links and s×d outgoing links connecting to second stage switches, an output stage having N d switches with each of them having d outlet links and s×d incoming links connecting from switches in the penultimate stage. The network also has (2×logd N)−3 middle stages with each middle stage having s × N d switches, and each switch in the middle stage has d incoming links connecting from the switches in its immediate preceding stage, and d outgoing links connecting to the switches in its immediate succeeding stage. Also each multicast connection is set up by use of at most two outgoing links from the input stage switch.

摘要翻译： 包括（2×logd N）-1级的多级网络在s≥2时以严格非阻塞的方式进行单播操作，并且对于任意扇出组播也以可重排的非阻塞方式操作，并且以严格的非阻塞方式操作任意风扇 当s≥3时，包括具有N d个开关的输入级，其中每个具有d个入口链路和连接到第二级交换机的s×d个输出链路，具有N d个开关的输出级，每个具有d个开关 链接和s×d进入链路在倒数第二阶段从交换机连接。 网络还具有（2×logd N）-3个中间阶段，每个中间阶段具有s×N d个交换机，并且中间阶段的每个交换机具有从其前一阶段中的交换机连接的d个入口链路，以及d个出站链路 在其后续阶段连接到交换机。 此外，每个组播连接通过使用来自输入级交换机的至多两个输出链路来建立。

公开(公告)号：US20060165085A1

公开(公告)日：2006-07-27

申请号：US11321287

申请日：2005-12-27

申请人： Venkat Konda

发明人： Venkat Konda

IPC分类号： H04L12/56 ,  H04Q3/00 ,  H04H1/00

CPC分类号： H04Q3/68 ,  H04L12/28 ,  H04L49/1515 ,  H04L49/201 ,  H04Q1/00 ,  H04Q3/00 ,  H04Q2213/1302 ,  H04Q2213/1304 ,  H04Q2213/13146 ,  H04Q2213/13242 ,  H04Q2213/1334 ,  H04Q2213/13341

摘要： A rearrangeably nonblocking multicast network includes an input stage having r1 switches and n1 inlet links for each of r1 switches, an output stage having r2 switches and n2 outlet links for each of r2 switches. The network also has a middle stage of m switches, and each middle switch has at least one link connected to each input switch for a total of at least r1 first internal links and at least one link connected to each output switch for a total of at least r2 second internal links, where m≧n1+n2. The network has all multicast connections set up such that each multicast connection passes through at most two middle switches to be connected to the destination outlet links. When the number of inlet links in each input switch n1 is equal to the number of outlet links in each output switch n2, and n1=n2=n, a three-stage network is operated in rearrangeably nonblocking manner, where m≧2*n. Also a three-stage network having m>n1+n2 is operated in rearrangeably nonblocking manner even if some multicast connections are set up using more than two middle switches as long as each connection has available links into at least two middle switches.

摘要翻译： 可重排的非阻塞组播网络包括具有用于r 1交换机中的每一个的r 1个交换机和n个1个入口链路的输入级，输出级具有 r 2开关和n 2个开关的n 2个插座。 网络还具有m个交换机的中间阶段，并且每个中间交换机具有连接到每个输入交换机的至少一个链路，用于总共至少第一个第一内部链路和至少一个链路连接到 每个输出开关总共具有至少r 2 2个第二内部链路，其中m> = n 1 + n 2 2。 网络具有所有多播连接的设置，使得每个组播连接最多通过两个中间交换机连接到目的出口链路。 当每个输入开关n 1中的入口连接件的数量等于每个输出开关n 2 2中的出口连接件的数量，并且n 1 = n <2> N，三级网络以可重排的非阻塞方式运行，其中m≥2* n。 而且，即使使用多于两个中间交换机的多个组播连接长时间，也可以以可重新布置的非阻塞方式操作具有m> n <1> N + 2＆lt; 2＆lt; 2＆gt; 2的三级网络 因为每个连接具有至少两个中间交换机的可用链路。

公开(公告)号：US20060159078A1

公开(公告)日：2006-07-20

申请号：US11384646

申请日：2006-03-19

申请人： Venkat Konda

发明人： Venkat Konda

IPC分类号： H04L12/50 ,  H04L12/56

CPC分类号： H04L45/00 ,  H04L45/16

摘要： A three-stage network is operated in strictly nonblocking manner includes an input stage having r1 switches and n1 inlet links for each of r1 switches, an output stage having r2 switches and n2 outlet links for each of r2 switches. The network also has a middle stage of m switches, and each middle switch has at least one link connected to each input switch for a total of at least r1 first internal links and at least one link connected to each output switch for a total of at least r2 second internal links, where m≧└√{square root over (r2)}┘*MIN(n1,n2) when └√{square root over (r2)}┘ is >1 and odd, or when └√{square root over (r2)}┘=2, m≧(└√{square root over (r2)}┘−1)*MIN(n1,n2) when ┘√{square root over (r2)}┘ is >2 and even, and m≧n1+n2−1 when └√{square root over (r2)}┘=1. Each multicast connection is set up through such a three-stage network by use of only one switch in the middle stage.

摘要翻译： 三级网络以严格的非阻塞方式操作，包括具有r 1个交换机的输入级和用于r 1中的每一个的n <1个< 开关，具有用于r 2开关中的每一个的r 2开关和n 2个/ 2个出口连接器的输出级。 网络还具有m个交换机的中间阶段，并且每个中间交换机具有连接到每个输入交换机的至少一个链路，用于总共至少第一个第一内部链路和至少一个链路连接到 每个输出开关用于总共至少r 2个2个第二内部链路，其中m≥= {平方根（（r 2/2））} MIN（n < 当“（平方根超过（r 2 2 }”）为> 1且为奇数时，或当Λ{{square 根（+ 2）}┘= 2，m> =（└√{root}}}}}}}}}}}} * * * * * * * * * * 当平方根超过（r2> 2）}时，“2”和“2”，并且m> = n ）}┘= 1时，。。。。。。。。。。。。。。。。。。。。。 通过在中间阶段只使用一个交换机，通过这样的三级网络建立每个组播连接。

公开(公告)号：US10977413B1

公开(公告)日：2021-04-13

申请号：US16671177

申请日：2019-11-01

申请人： Venkat Konda

发明人： Venkat Konda

IPC分类号： G06F30/33 ,  G06F30/394 ,  G06F30/34

摘要： 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 spatially nearer sub-integrated circuit blocks are connected with shorter links compared to the shuffle exchange links between spatially 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.

公开(公告)号：US20200076744A1

公开(公告)日：2020-03-05

申请号：US16562450

申请日：2019-09-06

申请人： Venkat Konda

发明人： Venkat Konda

IPC分类号： H04L12/933

摘要： Significantly optimized multi-stage networks with scheduling methods for faster scheduling of connections, useful in wide target applications, with VLSI layouts using only horizontal and vertical links to route large scale sub-integrated circuit blocks having inlet and outlet links, and laid out in an integrated circuit device in a two-dimensional grid arrangement of blocks are presented. The optimized multi-stage networks in each block employ several slices of rings of stages of switches with inlet and outlet links of sub-integrated circuit blocks connecting to rings from either left-hand side only, or from right-hand side only, or from both left-hand side and right-hand side; and employ multi-drop links where outlet links of cross links from switches in a stage of a ring in one sub-integrated circuit block are connected to either inlet links of switches in the another stage of a ring in the same or another sub-integrated circuit block.

公开(公告)号：US20170070449A1

公开(公告)日：2017-03-09

申请号：US15351453

申请日：2016-11-15

申请人： Venkat Konda

发明人： Venkat Konda

IPC分类号： H04L12/933 ,  G06F17/50 ,  H04L12/50

CPC分类号： H04L49/1507 ,  G06F17/5054 ,  G06F17/5077 ,  H04L12/50 ,  H04L49/10

摘要： 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.

摘要翻译： 具有空间位置开发的VLSI布局适用于广义多阶段和金字塔网络，广义折叠多阶段和金字塔网络，广义蝴蝶胖树和金字塔网络，广义多链路多阶段和金字塔网络，广义折叠多 连锁多级和金字塔网络，广义多链路蝴蝶胖树和金字塔网络，广义超立方网络和广义立方连接周期网络，用于加速s≥1。 VLSI布局的实施例在诸如FPGA，CPLD，pSoC，ASIC布局和路由工具，网络应用，并行和分布式计算以及可重配置计算的广泛目标应用中是有用的。

公开(公告)号：US07378938B2

公开(公告)日：2008-05-27

申请号：US10999649

申请日：2004-11-27

申请人： Venkat Konda

发明人： Venkat Konda

IPC分类号： H03K17/00 ,  H04Q3/68

CPC分类号： H04Q3/68 ,  H04Q2213/1302 ,  H04Q2213/13034 ,  H04Q2213/13242

摘要： A three-stage network is operated in strictly nonblocking manner and includes an input stage having r1 switches and n1 inlet links for each of r1 switches, an output stage having r2 switches and n2 outlet links for each of r2 switches. The network also has a middle stage of m switches, and each middle switch has at least one link connected to each input switch for a total of at least r1 first internal links and at least one link connected to each output switch for a total of at least r2 second internal links, where m≧2*n1+n2−1. In one embodiment, each multicast connection is set up through such a three-stage network by use of at most two switches in the middle stage.

摘要翻译： 三级网络以严格的非阻塞方式操作，并且包括具有r 1个开关的输入级和用于r 1中的每一个的1 <1 入口链路 >开关，具有用于r 2开关中的每一个的r 2开关和n 2个/ 2个出口连接器的输出级。 网络还具有m个交换机的中间阶段，并且每个中间交换机具有连接到每个输入交换机的至少一个链路，用于总共至少第一个第一内部链路和至少一个链路连接到 每个输出开关用于总共至少r 2 2个第二内部链路，其中m≥2* n 1 + n 2 2 -1。 在一个实施例中，通过在中间阶段使用至多两个交换机，通过这样的三级网络来建立每个组播连接。

公开(公告)号：US20070053356A1

公开(公告)日：2007-03-08

申请号：US10976664

申请日：2004-10-29

申请人： Venkat Konda

发明人： Venkat Konda

IPC分类号： H04L12/56

CPC分类号： H04L47/10 ,  H04L45/00 ,  H04L47/125 ,  H04L47/15 ,  H04L47/50 ,  H04L47/521 ,  H04L49/1523 ,  H04L49/201 ,  H04L49/254 ,  H04L49/3018 ,  H04L49/3027

摘要： A system for scheduling multirate multicast packets through an interconnection network having a plurality of input ports, a plurality of output ports, and a plurality of input queues, comprising multirate multicast packets with rate weight, at each input port is operated in nonblocking manner in accordance with the invention by scheduling corresponding to the packet rate weight, at most as many packets equal to the number of input queues from each input port to each output port. The scheduling is performed so that each multicast packet is fan-out split through not more than two interconnection networks and not more than two switching times. The system is operated at 100% throughput, work conserving, fair, and yet deterministically thereby never congesting the output ports. The system performs arbitration in only one iteration, with mathematical minimum speedup in the interconnection network. The system operates with absolutely no packet reordering issues, no internal buffering of packets in the interconnection network, and hence in a truly cut-through and distributed manner. In another embodiment each output port also comprises a plurality of output queues and each packet is transferred corresponding to the packet rate weight, to an output queue in the destined output port in deterministic manner and without the requirement of segmentation and reassembly of packets even when the packets are of variable size. In one embodiment the scheduling is performed in strictly nonblocking manner with a speedup of at least three in the interconnection network. In another embodiment the scheduling is performed in rearrangeably nonblocking manner with a speedup of at least two in the interconnection network. The system also offers end to end guaranteed bandwidth and latency for multirate multicast packets from input ports to output ports. In all the embodiments, the interconnection network may be a crossbar network, shared memory network, clos network, hypercube network, or any internally nonblocking interconnection network or network of networks.