Optimization of multi-stage hierarchical networks for practical routing applications

A multi-stage hierarchical network comprising:

• a plurality of partial multi-stage hierarchical networks, a plurality of inlet links and a plurality of outlet links, said plurality of partial multi-stage hierarchical networks arranged in a two-dimensional grid having a plurality of rows and a plurality of columns;
• and
• wherein each partial multi-stage hierarchical network of said plurality of partial multi-stage hierarchical networks comprising at least one ring and each ring of said at least one ring comprising a plurality of stages;
• and
• each stage of said plurality of stages comprise one or more switches of size di×d0, where di≥2 and do≥2, each switch of said one or more switches of size di×d0 having di incoming links and d0 outgoing links, each switch of said one or more switches of size di×d0 comprise a plurality of multiplexers of size d≥2 with each multiplexer of said plurality of multiplexers of size d≥2 comprising a d inputs and an output;
• and
• wherein said one or more switches of size di×d0 comprises one of a) a forward switch, b) 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, U-turn switch, and a reverse U-turn switch, and e) a forward switch, a backward switch, U-turn switch, and a reverse U-turn switch without 180-degree turn paths;
• and
• wherein said di incoming links and said d0 outgoing links comprise a one or more internal connections and a one or more hop wires where said one or more hop wires comprise a one or more internal hop wires or a one or more external hop wires;
• and
• wherein each outlet link of said plurality of outlet links is connected from the output of a first multiplexer of said plurality of multiplexers of size d≥2 of a first switch of said one or more switches of size di×d0 of a first stage of said plurality of stages of each ring of said at least one ring of a first partial multi-stage hierarchical network of said plurality of partial multi-stage hierarchical networks, and each inlet link of said plurality of inlet 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 plurality of stages of each ring of said at least one ring of one or more partial multi-stage hierarchical networks of said plurality of partial multi-stage hierarchical networks;
• and
• wherein each internal connection of said one or more internal connections connected from output of a first multiplexer of said plurality of multiplexers of size d≥2 of a first switch of said one or more switches of a first stage of said plurality of stages of a first ring of said at least one ring of a first partial multi-stage hierarchical network of said plurality of partial multi-stage hierarchical networks to a first input of said d inputs of a second multiplexer of said plurality of multiplexers of size d≥2 of a second switch of said one or more switches of a second stage of said plurality of stages of said first ring of said at least one ring of said first partial multi-stage hierarchical network of said plurality of partial multi-stage hierarchical networks;
• and
• wherein each internal hop wire of said one or more internal hop wires is connected from the output of a first multiplexer of said plurality of multiplexers of size d≥2 of a first switch of said one or more switches of a first stage of said plurality stages of a first ring of said at least one ring of a first partial multi-stage hierarchical network of said plurality of partial multi-stage hierarchical networks to a first input of said d inputs of a second multiplexer of said plurality of multiplexers size d≥2 of one or more switches of said one or more switches of one or more stages of said plurality of stages to a second ring of said at least one ring different from the first ring of said at least one ring of said first partial multi-stage hierarchical network of said plurality of partial multi-stage hierarchical networks;
• and
• wherein each external hop wire of said one or more external hop wires connected from said output of a first multiplexer of said plurality of multiplexers of size d≥2 of a first switch of said one or more switches of a first stage of said plurality of stages of a first ring of said at least one ring of a first partial multi-stage hierarchical network of said plurality of partial multi-stage hierarchical networks to one or more inputs of said d inputs of one or more multiplexers of said plurality of multiplexers d≥2 of a second switch of said one or more switches of a second stage of said plurality of stages of a second ring of said at least one ring of a second partial multi-stage hierarchical network different from said first partial multi-stage hierarchical network of said plurality of partial multi-stage hierarchical networks.

A programmable integrated circuit comprising:

• a plurality of programmable logic blocks and a multi-stage hierarchical network, each programmable logic block of said plurality of programmable logic blocks comprises a plurality of inlet links and a plurality of outlet links, said multi-stage hierarchical network comprises a plurality of partial multi-stage hierarchical networks wherein each programmable logic block of said plurality of programmable logic blocks is coupled to only one partial multi-stage hierarchical network of said plurality of partial multi-stage hierarchical networks and each partial multi-stage hierarchical network of said plurality of partial multi-stage hierarchical networks is coupled to only one programmable logic block of said plurality of programmable logic blocks, said plurality of programmable logic blocks coupled to said plurality of partial multi-stage hierarchical networks arranged in a two-dimensional grid having a plurality of rows and a plurality of columns;
• and
• each partial multi-stage hierarchical network of said plurality of partial multi-stage hierarchical networks comprises one or more rings, each ring of said one or more rings comprises a plurality of stages;
• and
• each stage of said plurality of stages comprises one or more switches of size di×d0, where di≥2 and do≥2, each switch of said one or more switches of size di×d0 having di incoming links and d0 outgoing links, each switch of said one or more switches of size di×d0 comprises a plurality of multiplexers of size d≥2 with each multiplexer of said plurality of multiplexers comprises d inputs and an output;
• and
• wherein said one or more switches of size di×d0 comprise one of a) a forward switch, b) 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, U-turn switch, and a reverse U-turn switch, and e) a forward switch, a backward switch, U-turn switch, and a reverse U-turn switch without 180-degree turn paths;
• and
• wherein said di incoming links and said d0 outgoing links comprise either a one or more internal connections, a one or more internal hop wires, or a one or more external hop wires;
• and
• wherein each inlet link of said plurality of inlet links is connected from the output of a first multiplexer of said plurality of multiplexers of a first switch of said one or more switches of size di×d0 of a first stage of said plurality of stages of said one or more rings of a first partial multi-stage hierarchical network of said plurality of partial multi-stage hierarchical 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 size di×d0 of one or more stages of said plurality of stages of said one or more rings of one or more partial multi-stage hierarchical networks of said plurality of partial multi-stage hierarchical networks;
• 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 size di×d0 of a first stage of said plurality of stages of a first ring of said one or more rings to a first input of said d inputs of a second multiplexer of said plurality of multiplexers of a second switch of said one or more switches of size di×d0 of a second stage of said plurality of stages of the first ring of said one or more rings;
• and
• wherein each internal hop wire of said one or more internal hop wires is connected from the output of a multiplexer of said plurality of multiplexers of a switch of said one or more switches of size di×d0 of a stage of said plurality of stages of a first ring of said one or more rings 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 size di×d0 of one or more stages of said plurality of stages of one or more rings different from the first ring of said one or more rings;
• and
• wherein each external hop wire of said one or more external hop wires is connected from the output a multiplexer of said plurality of multiplexers of a switch of said one or more switches of size di×d0 of a stage of said plurality of stages of a ring of said one or more rings of a first partial multi-stage hierarchical network of said plurality of partial multi-stage hierarchical networks to an 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 size di×d0 of one or more stages of said plurality of stages of said one or more rings of one or more partial multi-stage hierarchical networks different from the first partial multi-stage hierarchical network of said plurality of partial multi-stage hierarchical networks.