Fast scheduling and optimization of 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 comprising a plurality of inlet links and a plurality of outlet links, said multi-stage hierarchical network comprising a plurality of partial multi-stage networks wherein each programmable logic block of said plurality of programmable logic blocks is coupled with at least one partial multi-stage network of said plurality of partial multi-stage networks, said plurality of programmable logic blocks coupled with said plurality of partial multi-stage networks arranged in a two-dimensional grid of a plurality of rows and a plurality of columns;
• and
• each partial multi-stage network of said plurality of partial multi-stage networks comprising one or more slices, each slice of said one or more slices comprising one or more rings, each ring of said one or more rings comprising y stages, where y≥2;
• and
• each stage of said y stages comprising at least one switch of size di×d0, where di≥2 and do≥2, each switch of said at least one switch of size di×d0 having di incoming links and d0 outgoing links, each switch of said at least one switch of size di×d0 comprising a plurality of multiplexers of size d≥2 with each multiplexer of said plurality of multiplexers comprising d inputs and one output;
• and
• wherein said at least one switch of size di×d0 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, U-turn switch, and a reverse U-turn switch, e) a forward switch, a backward switch, U-turn switch, and a reverse U-turn switch without 180-degree turn paths, and f) 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 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 to the output of a first multiplexer of said plurality of multiplexers of a first switch of said at least one switch of size di×d0 of a first stage of said y stages of a first partial multi-stage network of said plurality of partial multi-stage 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 at least one switch of size di×d0 of one or more stages of said y stages of one or more partial multi-stage networks of said plurality of partial multi-stage 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 at least one switch of size di×d0 of a first stage of said y 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 at least one switch of size di×d0 of a second stage of said y 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 at least one switch of size di×d0 of a stage of said y stages of a first ring of said one or more rings of a first slice of said one or more slices 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 at least one switch of size di×d0 of one or more stages of said y stages of one or more rings different from the first ring of said one or more rings of the first slice of said one or more slices;
• 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 at least one switch of size di×d0 of a stage of said y stages of a ring of said one or more rings of a slice of said one or more slices of a first partial multi-stage network of said plurality of partial multi-stage 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 at least one switch of size di×d0 of one or more stages of said y stages of said one or more rings of a slice of said one or more slices of one or more partial multi-stage networks different from the first partial multi-stage network of said plurality of partial multi-stage networks;
• and
• wherein said at least one switch of size di×d0 of said y stages of said one or more rings of said one or more slices of said plurality of partial multi-stage hierarchical networks are either 1) fully connected or 2) not fully connected or alternatively optimized.

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 comprising a plurality of inlet links and a plurality of outlet links, said multi-stage hierarchical network comprising a plurality of partial multi-stage networks wherein each programmable logic block of said plurality of programmable logic blocks is coupled with at least one partial multi-stage network of said plurality of partial multi-stage networks, said plurality of programmable logic blocks coupled with said plurality of partial multi-stage networks arranged in a two-dimensional grid having a plurality of rows and a plurality of columns;
• and
• each partial multi-stage network of said plurality of partial multi-stage networks comprising one or more slices, each slice of said one or more slices comprising one or more rings, each ring of said one or more rings comprising y stages, where y≥2;
• and
• each stage of said y stages comprising at least one switch of size di×d0 where di≥2 and do≥2, each switch of said at least one switch of size di×d0 having di incoming links and d0 outgoing links, each switch of said at least one switch of size di×d0 comprising a plurality of multiplexers of size d≥2 with each multiplexer of said plurality of multiplexers comprising d inputs and one output;
• 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 inlet link of said plurality of inlet links is connected to the output of a first multiplexer of said plurality of multiplexers of a first switch of said at least one switch of size di×d0 of a first stage of said y stages of a first partial multi-stage network of said plurality of partial multi-stage 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 at least one switch of size di×d0 of one or more stages of said y stages of one or more partial multi-stage networks of said plurality of partial multi-stage 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 at least one switch of size di×d0 of a first stage of said y 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 at least one switch of size di×d0 of a second stage of said y 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 at least one switch of size di×d0 of a stage of said y stages of a first ring of said one or more rings of a first slice of said one or more slices 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 at least one switch of size di×d0 of one or more stages of said y stages of one or more rings different from the first ring of said one or more rings of the first slice of said one or more slices;
• 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 at least one switch of size di×d0 of a stage of said y stages of a ring of said one or more rings of a slice of said one or more slices of a first partial multi-stage network of said plurality of partial multi-stage 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 at least one switch of size di×d0 of one or more stages of said y stages of said one or more rings of a slice of said one or more slices of one or more partial multi-stage networks different from the first partial multi-stage network of said plurality of partial multi-stage networks;
• and
• wherein said at least one switch of size di×d0 of said y stages of said one or more rings of said one or more slices of said plurality of partial multi-stage hierarchical networks are either 1) fully connected or 2) not fully connected or alternatively optimized.