# US 11,451,490 B1 · VLSI layouts of fully connected generalized and pyramid networks with locality exploitation > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,451,490 B1 - Document ID: US11451490B1 - Status: Granted - Kind: B1 - Application number: 17/167,082 - Filed: 2021-02-04 - Granted: 2022-09-20 - Earliest claimed: 2009-10-16 - Assignees: Konda Technologies Inc. - Applicants: Venkat Konda - Inventors: Venkat Konda - Web page: https://patentgrep.com/patent/US11451490B1 ## CPC - H04L 49/10: characterised by the switching fabric construction - G06F 30/34: for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD] - G06F 30/394: Routing (G06F30/396 takes precedence) - H04L 12/12: Arrangements for remote connection or disconnection of substations or of equipment thereof - H04L 12/50: Circuit switching systems, i.e. systems in which the path is physically permanent during the communication - H04L 49/1507: {Distribute and route fabrics, e.g. sorting-routing or Batcher-Banyan} - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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 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. ## Claims ### Claim 1 A multi-stage network implemented in a non-transitory medium comprising: a plurality of blocks, a plurality of inlet links, and a plurality of outlet links, said plurality of blocks arranged in a two-dimensional grid of a plurality of rows and a plurality of columns; and each block of said plurality of blocks comprising a maximum of y stages namely 1st stage to yth stage, where y>2 and y is an integer, wherein 1st stage is hereinafter input stage, yth stage is hereinafter output stage and the remaining stages of said y stages hereinafter middle stages, and each stage of said y stages comprising one or more switches of size di×do, where di, do are integers, and di≥2 and do≥2, each switch of said one or more switches of size di×do having di incoming links and do outgoing links; and said di incoming links of said one or more switches of size di×do of said y stages excepting for input stage comprise one or more straight middle links and one or more cross middle links, and said do outgoing links of said one or more switches of size di×do of said y stages excepting for output stage comprise one or more straight middle links and one or more cross middle links; and wherein each outlet link of said plurality of outlet links is connected from a first outgoing link of said do outgoing links of a first switch of said one or more switches of size di×do 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 connected to a first incoming link of said di incoming links of one or more switches of said one or more switches of size di×do of the input stage of said y stages of a first block of said plurality of blocks; and wherein each straight middle link of said one or more straight middle links connected from a first switch of said one or more switches of size di×do of a first stage of said y stages of a first block of said plurality of blocks to input of a second switch of said one or more switches of size di×do of a second stage of said y stages of said first block of said plurality of blocks; and each cross middle link of said plurality of cross middle links connected from a first switch of said one or more switches of size di×do of a first stage of said y stages of a first block of said plurality of blocks to a second switch of one or more switches of size di×do of a second stage of said y stages of a second block of said plurality of blocks wherein said plurality of cross middle links also comprise pyramid links; and wherein one or more cross middle links of said one or more cross middle links are one of a) connected between switches of said one or more switches of size di×do in same stages of two blocks of said plurality of blocks and b) connected between switches of said one or more switches of size di×do in different stages of two blocks of said plurality of blocks. ### Claim 2 (depends on 1) The multi-stage network implemented in a non-transitory medium of claim 1, wherein said one or more cross middle links are connected as either vertical tracks, or horizontal tracks. ### Claim 3 (depends on 1) The multi-stage network implemented in a non-transitory medium of claim 1, wherein said one or more cross middle links of said one or more cross middle links are connected between at least one same stage in all said plurality of blocks, or said one or more cross middle links of said one or more cross middle links are connected between at least two not same stages of said y stages in all said plurality of blocks, or said one or more cross middle links are connected between same stages of said y stages in all stages of said y stages of all said plurality of blocks. ### Claim 4 (depends on 1) The multi-stage network implemented in a non-transitory medium of claim 1, wherein said one or more cross middle links are implemented in two or more metal layers, or each switch of said one or more switches of size di×do is configurable by Static Random Access Memory cells or Flash Cells, or said one or more cross middle links use a plurality of buffers to amplify signals driven through them; and said buffers are either inverting or non-inverting buffers. ### Claim 5 (depends on 1) The multi-stage network implemented in a non-transitory medium of claim 1, wherein said one or more switches of size di×do are either fully populated or partially populated, or said plurality of blocks are implemented in a 3D-FPGA. ### Claim 6 (depends on 1) The multi-stage network implemented in a non-transitory medium of claim 1, wherein each switch of said one or more switches of size di×do comprises one of a) a forward switch and a backward switch, and b) a forward switch, a backward switch and a U-turn switch. ### Claim 7 (depends on 1) The multi-stage network implemented in a non-transitory medium of claim 1, wherein a first block of the plurality of blocks comprises one of a) a same number and b) a different number of said y stages as a second block of the plurality of blocks; a first stage of said y stages comprises one of a) a same number and b) a different number of said one or more switches of size di×do as a second stage of said y stages; and a first switch of said one or more switches of size di×do in each stage of said y stages is one of a) a same size and b) a different size as a second switch of said one or more switches of size di×do. ### Claim 8 A multi-stage network implemented in a non-transitory medium comprising: a plurality of blocks, a plurality of inlet links, and a plurality of outlet links, said plurality of blocks arranged in a two-dimensional grid of a plurality of rows and a plurality of columns; and each block of said plurality of blocks comprising a maximum of y stages namely 1st stage to yth stage, where y>2 and y is an integer, wherein 1st stage is hereinafter input stage, yth stage is hereinafter output stage and the remaining stages of said y stages hereinafter middle stages, and each stage of said y stages comprising one or more switches of size di×do, where di, do are integers, and di≥2 and do≥2, each switch of said one or more switches of size di×do having di incoming links and do outgoing links; and said di incoming links of said one or more switches of size di×do of said y stages excepting for input stage comprise one or more straight middle links and one or more cross middle links, and said do outgoing links of said one or more switches of size di×do of said y stages excepting for output stage comprise one or more straight middle links and one or more cross middle links; and wherein each outlet link of said plurality of outlet links is connected from a first outgoing link of said do outgoing links of a first switch of said one or more switches of size di×do 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 connected to a first incoming link of said d, incoming links of one or more switches of said one or more switches of size di×do of the input stage of said y stages of a first block of said plurality of blocks; and wherein each straight middle link of said one or more straight middle links connected from a first switch of said one or more switches of size di×do of a first stage of said y stages of a first block of said plurality of blocks to input of a second switch of said one or more switches of size di×do of a second stage of said y stages of said first block of said plurality of blocks; and wherein each cross middle link of said one or more cross middle links connected from a first switch of one or more switches of size di×do of a first stage of said y stages of a first block of said plurality of blocks to one or more inputs of said d inputs of a second switch of said one or more switches of size di×do of either same stage or an immediately succeeding stage or an immediately preceding stage of said y stages of a second block of said plurality of blocks; and wherein one or more cross middle links of said one or more cross middle links are connected between switches of said one or more switches of size di×do in same stages of two blocks of said plurality of blocks. ### Claim 9 (depends on 8) The multi-stage network implemented in a non-transitory medium of claim 8, wherein said one or more cross middle links are connected as either vertical tracks, or horizontal tracks. ### Claim 10 (depends on 8) The multi-stage network implemented in a non-transitory medium of claim 8, wherein said one or more cross middle links of said one or more cross middle links are connected between at least one same stage of all said plurality of blocks, or said one or more cross middle links of said one or more cross middle links are connected between at least two not same stages of said y stages of all said plurality of blocks, or said one or more cross middle links are connected between same stages of said y stages in all stages of said y stages of all said plurality of blocks. ### Claim 11 (depends on 8) The multi-stage network implemented in a non-transitory medium of claim 8, wherein said one or more cross middle links are implemented in two or more metal layers, or each switch is configurable by Static Random Access Memory cells or Flash Cells, or said one or more cross middle links use a plurality of buffers to amplify signals driven through them; and said buffers are either inverting or non-inverting buffers. ### Claim 12 (depends on 8) The multi-stage network implemented in a non-transitory medium of claim 8, wherein said one or more switches of size di×do are either fully populated or partially populated, or said plurality of blocks are implemented in a 3D-FPGA. ### Claim 13 (depends on 8) The multi-stage network implemented in a non-transitory medium of claim 8, wherein each switch of said one or more switches of size di×do comprises one of a) a forward switch and a backward switch, and b) a forward switch, a backward switch and a U-turn switch. ### Claim 14 A multi-stage network implemented in a non-transitory medium comprising: a plurality of blocks, a plurality of inlet links, and a plurality of outlet links, said plurality of blocks arranged in a two-dimensional grid of a plurality of rows and a plurality of columns; and each block of said plurality of blocks comprising a maximum of y stages namely 1st stage to yth stage, where y>2 and y is an integer, wherein 1st stage is hereinafter input stage, yth stage is hereinafter output stage and the remaining stages of said y stages hereinafter middle stages, and each stage of said y stages comprising one or more switches of size di×do, where di, do are integers, and di≥2 and do≥2, each switch of said one or more switches of size di×do having di incoming links and do outgoing links; and said di incoming links of said one or more switches of size di×do of said y stages excepting for input stage comprise one or more straight middle links and one or more cross middle links, and said do outgoing links of said one or more switches of size di×do of said y stages excepting for output stage comprise one or more straight middle links and one or more cross middle links; and wherein each outlet link of said plurality of outlet links is connected from a first outgoing link of said do outgoing links of a first switch of said one or more switches of size di×do 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 connected to a first incoming link of said di incoming links of one or more switches of said one or more switches of size di×do of the input stage of said y stages of a first block of said plurality of blocks; and wherein each straight middle link of said one or more straight middle links connected from a first switch of said one or more switches of size di×do of a first stage of said y stages of a first block of said plurality of blocks to input of a second switch of said one or more switches of size di×do of a second stage of said y stages of said first block of said plurality of blocks; and wherein each cross middle link of said one or more cross middle links connected from a first switch of one or more switches of size di×do of a first stage of said y stages of a first block of said plurality of blocks to a second switch of said one or more switches of size di×do of either same stage or an immediately succeeding stage or an immediately preceding stage of said y stages of a second block of said plurality of blocks; and wherein one or more cross middle links of said one or more cross middle links are either connected between one or more switches of size di×do in same stages in two blocks of said plurality of blocks or connected between switches of said one or more switches of size di×do in different stages in two blocks of said plurality of blocks. ### Claim 15 (depends on 14) The multi-stage network implemented in a non-transitory medium of claim 14, wherein said one or more cross middle links are connected as either vertical tracks, or horizontal tracks. ### Claim 16 (depends on 14) The multi-stage network implemented in a non-transitory medium of claim 14, wherein said one or more cross middle links of said one or more cross middle links are connected between at least one same stage in all said plurality of blocks, or said one or more cross middle links of said one or more cross middle links are connected between at least two not same stages of said y stages of all said plurality of blocks, or said one or more cross middle links are connected between same stages of said y stages in all stages of said y stages of all said plurality of blocks. ### Claim 17 (depends on 14) The multi-stage network implemented in a non-transitory medium of claim 14, wherein said one or more cross middle links are implemented in two or more metal layers, or each switch of said one or more switches of size di×do is configurable by Static Random Access Memory cells or Flash Cells, or said one or more cross middle links use a plurality of buffers to amplify signals driven through them; and said buffers are either inverting or non-inverting buffers. ### Claim 18 (depends on 14) The multi-stage network implemented in a non-transitory medium of claim 14, wherein said one or more switches of size di×do are either fully populated or partially populated, or said plurality of blocks are implemented in a 3D-FPGA. ### Claim 19 (depends on 14) The multi-stage network implemented in a non-transitory medium of claim 14, wherein each switch of said one or more switches of size di×do comprises one of a) a forward switch and a backward switch, and b) a forward switch, a backward switch and a U-turn switch. ### Claim 20 (depends on 14) The multi-stage network implemented in a non-transitory medium of claim 14, wherein a first block of the plurality of blocks comprises one of a) a same number and b) a different number of said stages as a second block of the plurality of blocks; a first stage of said y stages comprises one of a) a same number and b) a different number of said one or more switches of size as a second stage of said stages; and a first switch of said one or more switches of size in each stage of said y stages is one of a) a same size and b) a different size as a second switch of said one or more switches of size.