Automatic multi-stage fabric generation for FPGAs
Systems and methods to automatically or manually generate various multi-stage pyramid network based fabrics, either partially connected or fully connected, are disclosed by changing different parameters of multi-stage pyramid network including such as number of slices, number of rings, number of stages, number of switches, number of multiplexers, the size of the multiplexers in any switch, connections between stages of rings either between the same numbered stages (same level stages) or different numbered stages, single or multi-drop hop wires, hop wires of different hop lengths, hop wires outgoing to different directions, hop wires incoming from different directions, number of hop wires based on the number and type of inlet and outlet links of large scale sub-integrated circuit blocks. One or more parameters are changed in each iteration so that optimized fabrics are generated, at the end of iterations, to route a given set of benchmarks or designs having a specific connection requirements.
1. A system for generating a multi-stage pyramid network,
said multi-stage pyramid network including connections to a plurality of computational blocks of a semiconductor integrated circuit arranged in a two-dimensional grid of a plurality of rows and a plurality of columns,
said plurality of computational blocks comprising a plurality of inlet links and a plurality of outlet links; and
wherein said multi-stage pyramid network comprising a plurality of partial multi-stage pyramid networks wherein each computational block of said plurality of computational blocks coupled to at least one of said plurality of partial multi-stage pyramid networks via said plurality of inlet links and said plurality of outlet links; and
each partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks comprising a slice, said slice comprising one or more rings, each ring of said one or more rings comprising a three or more stages; and
each stage of said three or more stages comprising one or more switches of size d i ×d o , where d i , d o are integers, d i ≥2 and d o >2, each switch of said one or more switches of size d i ×d o having d o incoming links and d o outgoing links, each switch of said one or more switches of size d i ×d o comprising a plurality of multiplexers of size d≥2, where d is an integer, with each multiplexer of said plurality of multiplexers comprising d inputs and one output; and
wherein said at least one switch of size d i ×d o comprises one of a) a forward switch, b) both a forward switch and a U-turn switch, c) a forward switch, a backward switch and a U-turn switch, d) a forward switch, a backward switch, a U-turn switch and a reverse U-turn switch e) a forward switch, a backward switch, a U-turn switch and a reverse U-turn switch without 180-degree turn paths, f) an integrated switch of a forward switch, a backward switch and U-turn switch, g) an integrated switch of a forward switch, a backward switch and a U-turn switch without 180 degree turn paths h) an integrated switch of a forward switch, a backward switch, a U-turn switch and a reverse U-turn switch and i) an integrated switch comprising a forward switch, a backward switch, a U-turn switch and a reverse U-turn switch without 180-degree turn paths; and
wherein said d o incoming links and said d o outgoing links comprise one or more internal connections and one or more hop wires; and
wherein each inlet link of said plurality of inlet links is connected to the output of a multiplexer of said plurality of multiplexers of a switch of said one or more switches of a stage of said three or more stages of a ring of said one or more rings of a said slice of a partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks, and each outlet link of said plurality of outlet links is connected to a first input of said d inputs of one or more multiplexers of said plurality of multiplexers of one or more switches of said one or more switches of one or more stages of said three or more stages of one or more rings of said one or more rings of said slice of one or more partial multi-stage pyramid networks of said plurality of partial multi-stage pyramid networks; and
wherein a first partial multi-stage network of said plurality of partial multi-stage networks comprises one of a) a same number and b) a different number of said plurality of inlet links as a second partial multi-stage network of said plurality of partial multi-stage networks; and a first partial multi-stage network of said plurality of partial multi-stage networks comprises one of a) a same number and b) a different number of said plurality of outlet links as a second partial multi-stage network of said plurality of partial multi-stage networks; a first ring of said one or more rings comprises one of a) a same number and b) a different number of said three or more stages as a second ring of said one or more rings; and a first stage of said three or more stages comprises one of a) a same number and b) a different number of said one or more switches of size d i ×d o as a second stage of said three or more stages: a first switch of said one or more switches of size d i ×d o is one of a) a same size and b) a different size as a second switch of said one or more switches of size d i ×d o ; and a first multiplexer in said plurality of multiplexers of size d≥2 is one of a) a same size and b) a different size as a second multiplexer in said plurality of multiplexers of size d≥2; and
wherein each internal connection of said one or more internal connections connected from the output of a first multiplexer of said plurality of multiplexers of a first switch of said one or more switches of a first stage of said three or more stages of a first ring of said one or more rings to one of the d inputs of a second multiplexer of said plurality of multiplexers of a second switch of said one or more switches of a second stage of said three or more stages of said first ring of said one or more rings; and
wherein said one or more hop wires comprise one or more internal hop wires and one or more external hop wires; and
wherein each internal hop wire of said one or more internal hop wires connected from the output of a first multiplexer of said plurality of multiplexers of a first switch of said one or more switches of a first stage of said three or more stages of a first ring of said one or more rings of said slice of a first partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks to one or more of the d inputs of one or more different multiplexers from said first multiplexer of said plurality of multiplexers of one or more different switches from said first switch of said one or more switches of one or more different stages from said first stage of said three or more stages of one or more different rings from said first ring of said one or more rings of said slice of said first partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks; and
wherein each external hop wire of said one or more external hop wires connected from the output of a multiplexer of said plurality of multiplexers of a switch of said one or more switches of a stage of said three or more stages of a ring of said one or more rings of said slice of a first said partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks to one or more inputs of said d inputs of one or more multiplexers of said plurality of multiplexers of one or more switches of said one or more switches of said three or more stages of one or more stages of said one or more rings of said slice of one or more partial multi-stage pyramid networks different from first said partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks; and
wherein one or more external hop wires of said one or more of external hop wires are one of a) connected between multiplexers of said plurality of multiplexers of switches of said one or more switches of same stages of said three or more stages in two or more different partial multi-stage pyramid networks of said plurality of partial multi-stage pyramid networks and b) connected between multiplexers of said plurality of multiplexers of switches of said one or more switches of in different stages said three or more stages in two or more different partial multi-stage pyramid networks of said plurality of partial multi-stage pyramid networks; and
wherein said one or more external hop wires are connected vertically or horizontally,
said system comprising:
one or more processors;
a memory arrangement coupled to said one or more processors, the memory arrangement configured with computer executable instructions that when executed by said one or more processors cause said one or more processors to perform operations including;
setting up size of said one or more rings, setting up size of said three or more stages, setting up size of said one or more switches, setting up size of said plurality of multiplexers, setting up number of inputs of each multiplexer of said plurality of multiplexers;
setting up connections of said plurality of inlet links and said plurality of outlet links to said plurality of partial multi-stage pyramid networks;
setting up connections of said one or more internal connections between said three or more stages of said ring of said one or more rings;
selecting hop length of each external hop wire of said one or more external hop wires setting up connections of said one or more external hop wires between said plurality of partial multi-stage pyramid networks:
setting up connections of said one or more internal hop wires between said one or more rings of the slice of a partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks;
setting up size of said plurality of rows and size of said plurality of columns in said two-dimensional grid;
simulating said semiconductor integrated circuit with said plurality of rows and said plurality of columns of said plurality of partial multi-stage pyramid networks;
routing one or more benchmarks on said semiconductor integrated circuit;
checking if said one or more benchmarks are successfully routed;
checking if all benchmarks of said one or more benchmarks are successfully routed, then computing a plurality of metrics including area, power, performance of benchmark and routing speed;
checking if all benchmarks of said one or more benchmarks have met a criteria and saving said multi-stage pyramid network, or
checking if said one or more benchmarks are not successfully routed, then changing either a) said size of said one or more rings, or b) said size of said three or more stages, or c) said size of said one or more switches, or d) said size of said plurality of multiplexers, or e) said number of inputs of each multiplexer of said plurality of multiplexers, or f) said connections of said plurality of inlet links and said plurality of outlet links to said plurality of partial multi-stage pyramid networks, or g) said hop length of each external hop wire of said one or more external hop wires, or h) said setting up of connections of said one or more external hop wires between said plurality of partial multi-stage pyramid networks, or i) said setting up of connections of said one or more internal hop wires between said one or more rings, or j) said setting up of connections of said one or more internal connections between said three or more stages of said ring of said one or more rings, or k) said size of said plurality of rows in said two-dimensional grid, or l) said size of said plurality of columns in said two-dimensional grid.
2. The system of claim 1 , wherein said operations,
Said setting up size of said one or more rings, said setting up size of said three or more stages, said setting up size of said one or more switches, said setting up size of said plurality of multiplexers, said setting up number of inputs of each multiplexer of said plurality of multiplexers;
said setting up connections of said plurality of inlet links and said plurality of outlet links to said plurality of partial multi-stage pyramid networks;
said setting up connections of said one or more internal connections between said three or more stages of said ring of said one or more rings, and
said selecting hop length of each external hop wire of said one or more external hop wires wherein size determines hop length, said setting up connections of said one or more external hop wires between said plurality of partial multi-stage pyramid networks;
said setting up connections of said one or more internal hop wires between said one or more rings of the slice of a partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks;
said setting up size of said plurality of rows and size of said plurality of columns in said two-dimensional grid;
said simulating said semiconductor integrated circuit with said plurality of rows and said plurality of columns of said plurality of partial multi-stage pyramid networks;
said routing one or more benchmarks on said semiconductor integrated circuit;
said checking if said one or more benchmarks are successfully routed;
said checking if all benchmarks of said one or more benchmarks are successfully routed, then computing a plurality of metrics including area, power, performance of benchmark and routing speed;
said checking if all benchmarks of said one or more benchmarks have met a criteria and saving said multi-stage pyramid network, or
said checking if said one or more benchmarks are not successfully routed, then changing either a) said size of said one or more rings, or b) said size of said three or more stages, or c) said size of said one or more switches, or d) said size of said plurality of multiplexers, or e) said number of inputs of each multiplexer of said plurality of multiplexers, or f) said connections of said plurality of inlet links and said plurality of outlet links to said plurality of partial multi-stage pyramid networks, or g) said hop length of each external hop wire of said one or more external hop wires, or h) said setting up of connections of said one or more external hop wires between said plurality of partial multi-stage pyramid networks, or i) said setting up of connections of said one or more internal hop wires between said one or more rings, or j) said setting up of connections of said one or more internal connections between said three or more stages of said ring of said one or more rings, or k) said size of said plurality of rows in said two-dimensional grid, or ml) said size of said plurality of columns in said two-dimensional grid,
are repeated in a plurality of iterations, until said one or more benchmarks have met said criteria and saving said multi-stage pyramid network.
3. The system of claim 1 , wherein each partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks is replicated in either said rows or said columns of said two-dimensional grid.
4. The system of claim 1 , wherein one or more said operations are performed manually.
5. The system of claim 2 , wherein in an iteration of said plurality of iterations, either one or more multiplexers of said plurality of multiplexers are removed including connections to its said inputs and said output or one or more multiplexers are added to said plurality of multiplexers including connections to its said inputs from one or more multiplexers of said plurality of multiplexers and connection to its said output to a first multiplexer of said plurality of multiplexers.
6. The system of claim 1 , wherein in an iteration of said plurality of iterations, either one or more internal connections of said one or more internal connections are removed, or
one or more internal hop wires of said one or more internal hop wires are removed, or one or more external hop wires of said one or more external hop wires are removed, or
one or more internal connections are added to said one or more internal connections, or
one or more internal hop wires are added to said one or more internal hop wires, or one or more external hop wires are added to said one or more external hop wires.
7. The system of claim 1 , wherein said plurality of computational blocks comprise either LUTs or memory or DSP processing block.
8. The system of claim 1 , wherein said semiconductor integrated circuit comprises a field programmable gate array.
9. A method of generating a multi-stage pyramid network,
said multi-stage pyramid network including connections to a plurality of computational blocks of a semiconductor integrated circuit arranged in a two-dimensional grid of a plurality of rows and a plurality of columns,
said plurality of computational blocks comprising a plurality of inlet links and a plurality of outlet links; and
wherein said multi-stage pyramid network comprising a plurality of partial multi-stage pyramid networks and each partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks coupled to at least one of said plurality of computational blocks via said plurality of inlet links and said plurality of outlet links; and
each partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks comprising one or more slices a slice, each said slice of said one or more slices comprising one or more rings, each ring of said one or more rings comprising a three or more stages; and
each stage of said three or more stages comprising one or more switches of size d i ×d o , where did, are integers, d i >2 and d o ≥2, each switch of said one or more switches of size d i ×d o having d o incoming links and d o outgoing links, each switch of said one or more switches of size d i ×d o comprising a plurality of multiplexers of size d≥2, where d is an integer, with each multiplexer of said plurality of multiplexers comprising d inputs and one output; and
wherein said at least one switch of size d i ×d o comprises one of a) a forward switch, b) both a forward switch and a U-turn switch, c) a forward switch, a backward switch and a U-turn switch, d) a forward switch, a backward switch, a U-turn switch and a reverse U-turn switch e) a forward switch, a backward switch, a U-turn switch and a reverse U-turn switch without 180-degree turn paths, f) an integrated switch of a forward switch, a backward switch and U-turn switch, g) an integrated switch of a forward switch, a backward switch and a U-turn switch without 180 degree turn paths h) an integrated switch of a forward switch, a backward switch, a U-turn switch and a reverse U-turn switch and i) an integrated switch comprising a forward switch, a backward switch, a U-turn switch and a reverse U-turn switch without 180-degree turn paths; and
wherein said d o incoming links and said d o outgoing links comprises one or more internal connections and one or more hop wires; and
wherein each inlet link of said plurality of inlet links is connected to the output of a multiplexer of said plurality of multiplexers of a first switch of said one or more switches of a stage of said three or more stages of a ring of said one or more rings of said slice of a partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks, and each outlet link of said plurality of outlet links is connected to a input of said d inputs of one or more multiplexers of said plurality of multiplexers of one or more switches of said one or more switches of one or more stages of said three or more stages of one or more rings of said one or more rings of said of one or more partial multi-stage pyramid networks of said plurality of partial multi-stage pyramid networks; and
wherein a first partial multi-stage network of said plurality of partial multi-stage networks comprises one of a) a same number and b) a different number of said plurality of inlet links as a second partial multi-stage network of said plurality of partial multi-stage networks; and a first partial multi-stage network of said plurality of partial multi-stage networks comprises one of a) a same number and b) a different number of said plurality of outlet links as a second partial multi-stage network of said plurality of partial multi-stage networks; a first ring of said one or more rings comprises one of a) a same number and b) a different number of said three or more stages as a second ring of said one or more rings;
and a first stage of said three or more stages comprises one of a) a same number and b) a different number of said one or more switches of size d i ×d o as a second stage of said three or more stages; a first switch of said one or more switches of size d i ×d o is one of a) a same size and b) a different size as a second switch of said one or more switches of size d i ×d o ; and a first multiplexer in said plurality of multiplexers of size d≥2 is one of a) a same size and b) a different size as a second multiplexer in said plurality of multiplexers of size d≥2; and
wherein each internal connection of said one or more internal connections connected from the output of a first multiplexer of said plurality of multiplexers of a first switch of said one or more switches of a first stage of said three or more stages of a first ring of said one or more rings to one of the d inputs of a second multiplexer of said plurality of multiplexers of a second switch of said one or more switches of a second stage of said three or more stages of said first ring of said one or more rings; and
wherein said hop wires comprise one or more internal hop wires and one or more external hop wires; and
wherein each internal hop wire of said one or more internal hop wires connected from the output of a first multiplexer of said plurality of multiplexers of a first switch of said one or more switches of a first stage of said three or more stages of a first ring of said one or more rings of a said slice of a first partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks to one or more of the d inputs of one or more different multiplexers from said first multiplexer of said plurality of multiplexers of one or more different switches from said first switch of said one or more switches of one or more different stages from said first stage of said three or more stages of one or more different rings from said first ring of said one or more rings of said slice of said first partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks; and
wherein each external hop wire of said one or more external hop wires connected from the output of a multiplexer of said plurality of multiplexers of a switch of said one or more switches of a stage of said three or more stages of a ring of said one or more rings of said slice of a first said partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks to one or more inputs of said d inputs of one or more multiplexers of said plurality of multiplexers of one or more switches of said one or more switches of said three or more stages of one or more stages of said one or more rings of said slice of one or more partial multi-stage pyramid networks different from first said partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks; and
wherein one or more external hop wires of said one or more external hop wires are one of a) connected between multiplexers of said plurality of multiplexers of switches of said one or more switches of same stages of said three or more stages in two or more different partial multi-stage pyramid networks of said plurality of partial multi-stage pyramid networks and b) connected between multiplexers of said plurality of multiplexers of switches of said one or more switches of in different stages said three or more stages in two or more different partial multi-stage pyramid networks of said plurality of partial multi-stage pyramid networks; and
wherein said one or more external hop wires are connected vertically or horizontally,
said method comprising:
using one or more programmed processors to perform steps including:
setting up size of said one or more rings, setting up size of said three or more stages, setting up size of said one or more switches, setting up size of said plurality of multiplexers, setting up number of inputs of each multiplexer of said plurality of multiplexers:
setting up connections of said plurality of inlet links and said plurality of outlet links to said plurality of partial multi-stage pyramid networks:
setting up connections of said one or more internal connections between said three or more stages of said ring of said one or more rings:
selecting hop length of each external hop wire of said one or more external hop wires setting up connections of said one or more external hop wires between said plurality of partial multi-stage pyramid networks:
setting up connections of said one or more internal hop wires between said one or more rings of the slice of a partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks:
setting up size of said plurality of rows and size of said plurality of columns in said two-dimensional grid:
simulating said semiconductor integrated circuit with said plurality of rows and said plurality of columns of said plurality of partial multi-stage pyramid networks:
routing one or more benchmarks on said semiconductor integrated circuit:
checking if said one or more benchmarks are successfully routed:
checking if all benchmarks of said one or more benchmarks are successfully routed, then computing a plurality of metrics including area, power, performance of benchmark and routing speed:
checking if all benchmarks of said one or more benchmarks have met a criteria and saving said multi-stage pyramid network, or
checking if said one or more benchmarks are not successfully routed, then changing either a) said size of said one or more rings, or b) said size of said three or more stages, or c) said size of said one or more switches, or d) said size of said plurality of multiplexers, or e) said number of inputs of each multiplexer of said plurality of multiplexers, or f) said connections of said plurality of inlet links and said plurality of outlet links to said plurality of partial multi-stage pyramid networks, or g) said hop length of each external hop wire of said one or more external hop wires, or h) said setting up of connections of said one or more external hop wires between said plurality of partial multi-stage pyramid networks, or i) said setting up of connections of said one or more internal hop wires between said one or more rings, or j) said setting up of connections of said one or more internal connections between said three or more stages of said ring of said one or more rings, or k) said size of said plurality of rows in said two-dimensional grid, or l) said size of said plurality of columns in said two-dimensional grid.
10. The method of claim 9 , wherein said steps, Said setting up size of said one or more rings, said setting up size of said three or more stages, said setting up size of said one or more switches, said setting up size of said plurality of multiplexers, said setting up number of inputs of each multiplexer of said plurality of multiplexers:
said setting up connections of said plurality of inlet links and said plurality of outlet links to said plurality of partial multi-stage pyramid networks;
said setting up connections of said one or more internal connections between said three or more stages of said ring of said one or more rings;
said selecting hop length of each external hop wire of said one or more external hop wires wherein size determines hop length, said setting up connections of said one or more external hop wires between said plurality of partial multi-stage pyramid networks;
said setting up connections of said one or more internal hop wires between said one or more rings of the slice of a partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks;
said setting up size of said plurality of rows and size of said plurality of columns in said two-dimensional grid;
said simulating said semiconductor integrated circuit with said plurality of rows and said plurality of columns of said plurality of partial multi-stage pyramid networks;
said routing one or more benchmarks on said semiconductor integrated circuit;
said checking if said one or more benchmarks are successfully routed;
said checking if all benchmarks of said one or more benchmarks are successfully routed, then computing a plurality of metrics including area, power, performance of benchmark and routing speed;
said checking if all benchmarks of said one or more benchmarks have met a criteria and saving said multi-stage pyramid network, or
said checking if said one or more benchmarks are not successfully routed, then changing either a) said size of said one or more rings, or b) said size of said three or more stages, or c) said size of said one or more switches, or d) said size of said plurality of multiplexers, or e) said number of inputs of each multiplexer of said plurality of multiplexers, or f) said connections of said plurality of inlet links and said plurality of outlet links to said plurality of partial multi-stage pyramid networks, or g) said hop length of each external hop wire of said one or more external hop wires, or h) said setting up of connections of said one or more external hop wires between said plurality of partial multi-stage pyramid networks, or i) said setting up of connections of said one or more internal hop wires between said one or more rings, or j) said setting up of connections of said one or more internal connections between said three or more stages of said ring of said one or more rings, or k) said size of said plurality of rows in said two-dimensional grid, or l) said size of said plurality of columns in said two-dimensional grid,
are repeated in a plurality of iterations, until said one or more benchmarks have met said criteria and saving said multi-stage pyramid network.
11. The method of claim 9 , wherein each partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks is replicated in either said rows or said columns of said two-dimensional grid.
12. The method of claim 9 , wherein one or more said steps are performed manually.
13. The method of claim 10 , wherein in an iteration of said plurality of iterations, either one or more multiplexers of said plurality of multiplexers are removed including connections to its said inputs and said output or one or more multiplexers are added to said plurality of multiplexers including connections to its said inputs from one or more multiplexers of said plurality of multiplexers and connection to its said output to a first multiplexer of said plurality of multiplexers.
14. The method of claim 9 , wherein in an iteration of said plurality of iterations, either one or more internal connections of said one or more internal connections are removed, or
one or more internal hop wires of said one or more internal hop wires are removed, or one or more external hop wires of said one or more external hop wires are removed, or
one or more internal connections are added to said one or more internal connections, or
one or more internal hop wires are added to said one or more internal hop wires, or one or more external hop wires are added to said one or more external hop wires.
15. The method of claim 9 , wherein said plurality of computational blocks comprise either LUTs or memory or DSP processing block.
16. The method of claim 9 , wherein said semiconductor integrated circuit comprises a field programmable gate array.
17. An article of manufacture, comprising:
a computer readable non-transitory storage medium configured with computer executable instructions for generating a multi-stage pyramid network,
said multi-stage pyramid network including connections to a plurality of computational blocks of a semiconductor integrated circuit arranged in a two-dimensional grid of a plurality of rows and a plurality of columns,
said plurality of computational blocks comprising a plurality of inlet links and a plurality of outlet links; and
said multi-stage pyramid network comprising a plurality of partial multi-stage pyramid networks and each partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks coupled to at least one of said plurality of computational blocks via said plurality of inlet links and said plurality of outlet links; and
each partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks comprising a slice, said slice comprising one or more rings, each ring of said one or more rings comprising a three or more stages; and
each stage of said three or more stages comprising one or more switches of size d i ×d o , where d i , d o are integers, d i >2 and d o ≥2, each switch of said one or more switches of size d i ×d o having d o incoming links and d o outgoing links, each switch of said one or more switches of size d i ×d o comprising a plurality of multiplexers of size d≥2, where d is an integer, with each multiplexer of said plurality of multiplexers comprising d inputs and one output; and
wherein said at least one switch of size d i ×d o comprises one of a) a forward switch, b) both a forward switch and a U-turn switch, c) a forward switch, a backward switch and a U-turn switch, d) a forward switch, a backward switch, a U-turn switch and a reverse U-turn switch e) a forward switch, a backward switch, a U-turn switch and a reverse U-turn switch without 180-degree turn paths, f) an integrated switch of a forward switch, a backward switch and U-turn switch, g) an integrated switch of a forward switch, a backward switch and a U-turn switch without 180 degree turn paths h) an integrated switch of a forward switch, a backward switch, a U-turn switch and a reverse U-turn switch and i) an integrated switch comprising a forward switch, a backward switch, a U-turn switch and a reverse U-turn switch without 180-degree turn paths; and
wherein said d o incoming links and said d o outgoing links comprises one or more internal connections and one or more hop wires; and
wherein each inlet link of said plurality of inlet links is connected to the output of a multiplexer of said plurality of multiplexers of a switch of said one or more switches of a stage of said three or more stages of a ring of said one or more rings of a said slice of a partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks, and each outlet link of said plurality of outlet links is connected to a input of said d inputs of one or more multiplexers of said plurality of multiplexers of one or more switches of said one or more switches of one or more stages of said three or more stages of one or more rings of said one or more rings of said slice of one or more partial multi-stage pyramid networks of said plurality of partial multi-stage pyramid networks; and
wherein a first partial multi-stage network of said plurality of partial multi-stage networks comprises one of a) a same number and b) a different number of said plurality of inlet links as a second partial multi-stage network of said plurality of partial multi-stage networks; and a first partial multi-stage network of said plurality of partial multi-stage networks comprises one of a) a same number and b) a different number of said plurality of outlet links as a second partial multi-stage network of said plurality of partial multi-stage networks; a first ring of said one or more rings comprises one of a) a same number and b) a different number of said three or more stages as a second ring of said one or more rings; and a first stage of said three or more stages comprises one of a) a same number and b) a different number of said one or more switches of size d i ×d o as a second stage of said three or more stages; a first switch of said one or more switches of size d i ×d o is one of a) a same size and b) a different size as a second switch of said one or more switches of size d i ×d o ; and a first multiplexer in said plurality of multiplexers of size d≥2 is one of a) a same size and b) a different size as a second multiplexer in said plurality of multiplexers of size d≥2; and
wherein each internal connection of said one or more internal connections connected from the output of a first multiplexer of said plurality of multiplexers of a first switch of said one or more switches of a first stage of said three or more stages of a first ring of said one or more rings to one of the d inputs of a second multiplexer of said plurality of multiplexers of a second switch of said one or more switches of a second stage of said three or more stages of said first ring of said one or more rings; and
said hop wires comprises one or more internal hop wires and one or more external hop wires; and
wherein each internal hop wire of said one or more internal hop wires connected from the output of a first multiplexer of said plurality of multiplexers of a first switch of said one or more switches of a first stage of said three or more stages of a first ring of said one or more rings of said slice of a first partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks to one or more of the d inputs of one or more different multiplexers from said first multiplexer of said plurality of multiplexers of one or more different switches from said first switch of said one or more switches of one or more different stages from said first stage of said three or more stages of one or more different rings from said first ring of said one or more rings of said slice of said first partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks; and
wherein each external hop wire of said one or more external hop wires connected from the output of a multiplexer of said plurality of multiplexers of a switch of said one or more switches of a stage of said three or more stages of a ring of said one or more rings of said slice of a first said partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks to one or more inputs of said d inputs of one or more multiplexers of said plurality of multiplexers of one or more switches of said one or more switches of said three or more stages of one or more stages of said one or more rings of said slice of one or more partial multi-stage pyramid networks different from first said partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks; and
wherein one or more external hop wires of said one or more external hop wires are one of a) connected between multiplexers of said plurality of multiplexers of switches of said one or more switches of same stages of said three or more stages in two or more different partial multi-stage pyramid networks of said plurality of partial multi-stage pyramid networks and b) connected between multiplexers of said plurality of multiplexers of switches of said one or more switches of in different stages said three or more stages in two or more different partial multi-stage pyramid networks of said plurality of partial multi-stage pyramid networks; and
wherein said one or more external hop wires are connected vertically or horizontally, said instructions when executed by a computer causing said computer to perform operations including:
setting up size of said one or more rings, setting up size of said three or more stages, setting up size of said one or more switches, setting up size of said plurality of multiplexers, setting up number of inputs of each multiplexer of said plurality of multiplexers;
setting up connections of said plurality of inlet links and said plurality of outlet links to said plurality of partial multi-stage pyramid networks:
setting up connections of said one or more internal connections between said three or more stages of said ring of said one or more rings;
selecting hop length of each external hop wire of said one or more external hop wires setting up connections of said one or more external hop wires between said plurality of partial multi-stage pyramid networks;
setting up connections of said one or more internal hop wires between said one or more rings of the slice of a partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks;
setting up size of said plurality of rows and size of said plurality of columns in said two-dimensional grid:
simulating said semiconductor integrated circuit with said plurality of rows and said plurality of columns of said plurality of partial multi-stage pyramid networks;
routing one or more benchmarks on said semiconductor integrated circuit;
checking if said one or more benchmarks are successfully routed;
checking if all benchmarks of said one or more benchmarks are successfully routed, then computing a plurality of metrics including area, power,
performance of benchmark and routing speed;
checking if all benchmarks of said one or more benchmarks have met a criteria and saving said multi-stage pyramid network, or
checking if said one or more benchmarks are not successfully routed, then changing either a) said size of said one or more rings, or b) said size of said three or more stages, or c) said size of said one or more switches, or d) said size of said plurality of multiplexers, or e) said number of inputs of each multiplexer of said plurality of multiplexers, or f) said connections of said plurality of inlet links and said plurality of outlet links to said plurality of partial multi-stage pyramid networks, or g) said hop length of each external hop wire of said one or more external hop wires, or h) said setting up of connections of said one or more external hop wires between said plurality of partial multi-stage pyramid networks, or i) said setting up of connections of said one or more internal hop wires between said one or more rings, or j) said setting up of connections of said one or more internal connections between said three or more stages of said ring of said one or more rings, or k) said size of said plurality of rows in said two-dimensional grid, or l) said size of said plurality of columns in said two-dimensional grid.
18. The article of manufacture of claim 17 , wherein said operations,
Said setting up size of said one or more rings, said setting up size of said three or more stages, said setting up size of said one or more switches, said setting up size of said plurality of multiplexers, said setting up number of inputs of each multiplexer of said plurality of multiplexers;
said setting up connections of said plurality of inlet links and said plurality of outlet links to said plurality of partial multi-stage pyramid networks;
said setting up connections of said one or more internal connections between said three or more stages of said ring of said one or more rings;
said selecting hop length of each external hop wire of said one or more external hop wires wherein size determines hop length, said setting up connections of said one or more external hop wires between said plurality of partial multi-stage pyramid networks;
said setting up connections of said one or more internal hop wires between said one or more rings of the slice of a partial multi-stage pyramid network of said plurality of partial multi-stage pyramid networks;
said setting up size of said plurality of rows and size of said plurality of columns in said two-dimensional grid;
said simulating said semiconductor integrated circuit with said plurality of rows and said plurality of columns of said plurality of partial multi-stage pyramid networks;
said routing one or more benchmarks on said semiconductor integrated circuit;
said checking if said one or more benchmarks are successfully routed;
said checking if all benchmarks of said one or more benchmarks are successfully routed, then computing a plurality of metrics including area, power, performance of benchmark and routing speed;
said checking if all benchmarks of said one or more benchmarks have met a criteria and saving said multi-stage pyramid network, or
said checking if said one or more benchmarks are not successfully routed, then changing either a) said size of said one or more rings, or b) said size of said three or more stages, or c) said size of said one or more switches, or d) said size of said plurality of multiplexers, or e) said number of inputs of each multiplexer of said plurality of multiplexers, or f) said connections of said plurality of inlet links and said plurality of outlet links to said plurality of partial multi-stage pyramid networks, or g) said hop length of each external hop wire of said one or more external hop wires, or h) said setting up of connections of said one or more external hop wires between said plurality of partial multi-stage pyramid networks, or i) said setting up of connections of said one or more internal hop wires between said one or more rings, or j) said setting up of connections of said one or more internal connections between said three or more stages of said ring of said one or more rings, or k) said size of said plurality of rows in said two-dimensional grid, or l) said size of said plurality of columns in said two-dimensional grid,
are repeated in a plurality of iterations, until said one or more benchmarks have met said criteria and then saving said multi-stage pyramid network or,
one or more said operations are performed manually.
19. The article of manufacture of claim 18 , wherein in an iteration of said plurality of iterations, either one or more multiplexers of said plurality of multiplexers are removed including connections to its said inputs and said output or one or more multiplexers are added to said plurality of multiplexers including connections to its said inputs from one or more multiplexers of said plurality of multiplexers and connection to its said output to a first multiplexer of said plurality of multiplexers, or one or more internal connections of said one or more internal connections are removed, or
one or more internal hop wires of said one or more internal hop wires are removed, or one or more external hop wires of said one or more external hop wires are removed, or
one or more multiplexers are added to said plurality of multiplexers including connections to its said inputs and said output, or
one or more internal connections are added to said one or more internal connections, or
one or more internal hop wires are added to said one or more internal hop wires, or one or more external hop wires are added to said one or more external hop wires.
20. The article of manufacture of claim 17 , wherein said plurality of computational blocks comprise either LUTs or memory or DSP processing block, or said semiconductor integrated circuit comprises a field programmable gate array.