Fast scheduling and optmization of multi-stage hierarchical networks

1. A programmable integrated circuit comprising a plurality of programmable logic blocks and a network,

each programmable logic block of said plurality of programmable logic blocks comprising a plurality of inlet links and a plurality of outlet links; and

said 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 of said plurality of partial multi-stage networks; and

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 further comprising one or more slices, each slice of said one or more slices further comprising one or more rings, each ring of said one or more rings further comprising y stages, where y≥1; and

each stage of said y stages comprising at least one switch of size d i ×d 0 , where d i ≥2 and d 0 ≥2 and each switch of said at least one switch of size d i ×d 0 having d i incoming links and d 0 outgoing links; and each switch of said at least one switch of size d i ×d 0 further comprising a plurality of multiplexers of size d≥2 with each multiplexer of said plurality of multiplexers comprising d inputs and one output; and

said at least one switch of size d i ×d 0 comprises either only a forward switch, or only a backward switch, or both a forward switch and a backward switch, or a forward switch, a backward switch and U-turn switch, or a forward switch, a backward switch and a U-turn switch without 180 degree turn paths or a forward switch, a backward switch, a U-turn switch and a reverse U-turn switch or a forward switch, a backward switch, a U-turn switch and a reverse U-turn switch without 180 degree turn paths, or an integrated switch of a forward switch, a backward switch and U-turn switch, or an integrated switch of a forward switch, a backward switch and a U-turn switch without 180 degree turn paths or an integrated switch of a forward switch, a backward switch, a U-turn switch and a reverse U-turn switch or an integrated switch of a forward switch, a backward switch, a U-turn switch and a reverse U-turn switch without 180 degree turn paths; and

said d i incoming links and said d 0 outgoing links comprises a plurality of internal connections and a plurality of hop wires; and said plurality of hop wires further comprising a plurality of internal hop wires or a plurality of external hop wires; and

each inlet link of said plurality of inlet links is connected to the output of one of said plurality of multiplexers of one switch of said at least one switch of size d i ×d 0 of one stage of said y stages of one 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 one of the inputs of one or more of said plurality of multiplexers of one or more said switches of said at least one switch of size d i ×d 0 of one or more said stages of said y stages of one or more said plurality of partial multi-stage networks; and

a first programmable logic block of said plurality of programmable logic blocks comprising the same or different number of said plurality of inlet links as a second programmable logic block of said plurality of programmable logic blocks and a first programmable logic block of said plurality of programmable logic blocks comprising the same or different number of said plurality of outlet links as a second programmable logic block of said plurality of programmable logic blocks; a first partial multi-stage network of said plurality of partial multi-stage networks comprising the same or different number of said one or more slices as a second partial multi-stage network of said plurality of partial multi-stage networks; a first slice of said one or more slices comprising the same or different number of said one or more rings as a second slice of said one or more slices; a first ring of said one or more rings comprising the same or different number of said y stages as a second ring of said one or more rings; and a first stage of said y stages comprising the same or different number of said at least one switch of size d i ×d 0 as a second stage of said y stages; a first switch of said at least one switch of size d i ×d 0 is the same or different size as a second switch of said at least one switch of size d i ×d 0 a first multiplexer in said plurality of multiplexers of size d≥2 is the same or different size as a second multiplexer in said plurality of multiplexers of size d≥2; and

each internal connection of said plurality of 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 d i ×d 0 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 d i ×d 0 of a second stage of said y stages of the first ring of said one or more rings; and

each internal hop wire of said plurality of 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 d i ×d 0 of a stage of said y stages of a first ring of said one or more rings of a slice of said one or more slices 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 d i ×d 0 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 same slice of said one or more slices; and

each external hop wire of said plurality of 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 d i ×d 0 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 d i ×d 0 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

one or more external hop wires of said plurality of external hop wires are either connected between multiplexers of said plurality of multiplexers of switches of said at least one switch of size d i ×d 0 in same numbered stages of said y stages in two or more partial multi-stage networks of said plurality of partial multi-stage networks or connected between multiplexers of said plurality of multiplexers of switches of said at least one switch of size d i ×d 0 in different numbered stages of said y stages , when y≥2, in two or more partial multi-stage networks of said plurality of partial multi-stage networks.

2. The programmable integrated circuit of claim 1 , wherein said plurality of external hop wires are connected vertically (hereinafter “vertical links”), or horizontally (hereinafter “horizontal links”), or by both vertical links and horizontal links; and

each partial multi-stage network of said plurality of partial multi-stage networks comprising said one or more slices is replicated in either said plurality of rows or said plurality of columns of the two-dimensional grid, or

each partial multi-stage network of said plurality of partial multi-stage networks comprising said horizontal links and said vertical is replicated in either said plurality of rows or said plurality of columns of the two-dimensional grid, or

each partial multi-stage network of said plurality of partial multi-stage networks comprising both said one or more slices, and said horizontal links and said vertical links is replicated in either said plurality of rows or said plurality of columns of the two-dimensional grid.

3. The programmable integrated circuit of claim 1 , wherein said plurality of external hop wires are cascaded through only one multiplexer of said plurality of multiplexers at each switch of said at least one switch of size d i ×d 0 .

4. The programmable integrated circuit of claim 1 , wherein said one or more external hop wires of said plurality of external hop wires are connected between at least one same numbered stage in all said plurality of partial multi-stage networks, or

one or more external hop wires of said plurality of external hop wires are connected between at least two not same numbered stages of said y stages in all said plurality of partial multi-stage networks; or

said plurality of external hop wires are all connected between same numbered stages of said y stages in all stages of said y stages of all said plurality of partial multi-stage networks.

5. The programmable integrated circuit of claim 1 , wherein one or more stages of said y stages in one partial multi-stage network of said plurality of partial multi-stage networks are not connected to any other stages of said y stages in another partial multi-stage network of said plurality of partial multi-stage networks, or,

one or more stages of said y stages in one partial multi-stage network of said plurality of partial multi-stage networks are connected to stages of said y stages in another partial multi-stage network of said plurality of partial multi-stage networks by one or more external hop wires of said plurality of external hop wires, only when said two-dimensional grid is replicated by increasing said plurality of rows or said plurality of columns.

6. The programmable integrated circuit of claim 1 , wherein one or more of external hop wires of said plurality of external hop wires are implemented in two or more metal layers, or

each multiplexer of said plurality of multiplexers of size d≥2 is configurable by SRAM cells or Flash Cells, or

said plurality of external hop wires use a plurality of buffers to amplify signals driven through them; and said plurality of buffers are either inverting or non- inverting buffers, or

one or more stages of said y stages in one partial multi-stage network of said plurality of partial multi-stage networks comprising a switch of size (d i +m)×(d 0 +n), where d i ≥2, d 0 ≥2, m≥0, n≥0 or

one or more of said y stages in one partial multi-stage network of said plurality of partial multi-stage networks comprising six 2:1 multiplexers, or eight 2:1 multiplexers, or four 3:1 multiplexers, or four 4:1 multiplexers.

7. The programmable integrated circuit of claim 1 , wherein said at least one switch of size d i ×d 0 of said y stages are either fully populated or partially populated, or

said plurality of partial multi-stage networks are implemented in a 3D integrated circuit device.

8. A programmable integrated circuit comprising a plurality of programmable logic blocks and a network,

each programmable logic block of said plurality of programmable logic blocks comprising a plurality of inlet links and a plurality of outlet links; and

said 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 of said plurality of partial multi-stage networks; and

said plurality of networks 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 further comprising one or more slices, each slice of said one or more slices further comprising one or more rings, each ring of said one or more rings further comprising y stages, where y≥1; and

each stage of said y stages comprising at least one switch of size d i ×d 0 , where d i ≥2 and d 0 2 and each switch of said at least one switch of size d i ×d 0 having d i incoming links and d 0 outgoing links; and each switch of said at least one switch of size d i ×d 0 further comprising a plurality of multiplexers of size d≥2 with each multiplexer of said plurality of multiplexers comprising d inputs and one output; and

said at least one switch of size d i x d 0 comprises either only a forward switch, or only a backward switch, or both a forward switch and a backward switch, or a forward switch, a backward switch and U-turn switch, or a forward switch, a backward switch and a U-turn switch without 180 degree turn paths, or an integrated switch of a forward switch, a backward switch and U-turn switch, or an integrated switch of a forward switch, a backward switch and a U-turn switch without 180 degree turn paths; and

said d i incoming links and said d 0 outgoing links comprises a plurality of internal connections and a plurality of hop wires; and said plurality of hop wires further comprising a plurality of internal hop wires or a plurality of external hop wires; and

each inlet link of said plurality of inlet links is connected to the output of one of said plurality of multiplexers of one switch of said at least one switch of size d i ×d 0 of one stage of said y stages of one 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 one of the inputs of one or more of said plurality of multiplexers of one or more said switches of said at least one switch of size d i ×d 0 of one or more said stages of said y stages of one or more said plurality of partial multi-stage networks; and

a first programmable logic block of said plurality of programmable logic blocks comprising the same or different number of said plurality of inlet links as a second programmable logic block of said plurality of programmable logic blocks and a first programmable logic block of said plurality of programmable logic blocks comprising the same or different number of said plurality of outlet links as a second programmable logic block of said plurality of programmable logic blocks; a first partial multi-stage network of said plurality of partial multi-stage networks comprising the same or different number of said one or more slices as a second partial multi-stage network of said plurality of partial multi-stage networks; a first slice of said one or more slices comprising the same or different number of said one or more rings as a second slice of said one or more slices; a first ring of said one or more rings comprising the same or different number of said y stages as a second ring of said one or more rings; and a first stage of said y stages comprising the same or different number of said at least one switch of size d i ×d 0 as a second stage of said y stages; a first switch of said at least one switch of size d i ×d 0 is the same or different size as a second switch of said at least one switch of size d i ×d 0 ; a first multiplexer in said plurality of multiplexers of size d≥2 is the same or different size as a second multiplexer in said plurality of multiplexers of size d≥2; and

each internal connection of said plurality of 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 d i ×d 0 of one said 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 d i ×d 0 of a second stage of said y stages of the first ring of said one or more rings; and

each internal hop wire of said plurality of 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 d i ×d 0 of a stage of said y stages of a first ring of said one or more rings of a 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 d i ×d 0 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 same slice of said one or more slices; and

each external hop wire of said plurality of 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 d i ×d 0 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 d i ×d 0 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

one or more external hop wires of said plurality of external hop wires are either connected between multiplexers of said plurality of multiplexers of switches of said at least one switch of size d i ×d 0 in same numbered stages of said y stages in two or more partial multi-stage networks of said plurality of partial multi-stage networks or connected between multiplexers of said plurality of multiplexers of switches of said at least one switch of size d i ×d 0 in different numbered stages of said y stages , when y≥2, in two or more partial multi-stage networks of said plurality of partial multi-stage networks.

9. The programmable integrated circuit of claim 8 , wherein said plurality of external hop wires are connected vertically (hereinafter “vertical links”), or horizontally (hereinafter “horizontal links”), or by both vertical links and horizontal links; and

each partial multi-stage network of said plurality of partial multi-stage networks comprising said one or more slices is replicated in either said plurality of rows or said plurality of columns of the two-dimensional grid, or

each partial multi-stage network of said plurality of partial multi-stage networks comprising said horizontal links and said vertical links is replicated in either said plurality of rows or said plurality of columns of the two-dimensional grid, or

each partial multi-stage network of said plurality of partial multi-stage networks comprising both said one or more slices, and said horizontal links and said vertical links is replicated in either said plurality of rows or said plurality of columns of the two-dimensional grid.

10. The programmable integrated circuit of claim 8 , wherein said cross links plurality of external hop wires are cascaded through only one multiplexer of said plurality of multiplexers at each switch of said at least one switch of size d i x d 0 .

11. The programmable integrated circuit of claim 8 , wherein said one or more external hop wires of said plurality of external hop wires are connected between at least one same numbered stage in all said plurality of partial multi-stage networks, or

one or more external hop wires of said plurality of external hop wires are connected between at least two not same numbered stages of said y stages in all said plurality of partial multi-stage networks; or

said plurality of external hop wires are all connected between same numbered stages of said y stages in all stages of said y stages of all said plurality of partial multi-stage networks.

12. The programmable integrated circuit of claim 8 , wherein said one or more stages of said y stages in a one partial multi-stage network of said plurality of partial multi-stage networks are not connected to any other stages of said y stages in another partial multi-stage network of said plurality of partial multi-stage networks, or,

one or more stages of said y stages in one partial multi-stage network of said plurality of partial multi-stage networks are connected to stages of said y stages in another partial multi-stage network of said plurality of partial multi-stage networks by one or more external hop wires of said plurality of external hop wires, only when said two-dimensional grid is replicated by increasing said plurality of rows or said plurality of columns.

13. The programmable integrated circuit of claim 8 , wherein one or more of external hop wires of said plurality of external hop wires are implemented in two or more metal layers, or

each multiplexer of said plurality of multiplexers of size 2 is configurable by SRAM cells or Flash Cells, or

said plurality of external hop wires use a plurality of buffers to amplify signals driven through them; and said plurality of buffers are either inverting or non-inverting buffers, or

one or more stages of said y stages in one partial multi-stage network of said plurality of partial multi-stage networks comprising a switch of size (d i +m)×(d 0 +n), where d i ≥2, d 0 ≥2, m≥0, n≥0 or

one or more of said y stages in one partial multi-stage network of said plurality of partial multi-stage networks comprising six 2:1 multiplexers, or eight 2:1 multiplexers, or four 3:1 multiplexers, or four 4:1 multiplexers.

14. The programmable integrated circuit of claim 8 , wherein said at least one switch of size d i ×d 0 of said y stages are either fully populated or partially populated, or

said plurality of partial multi-stage networks are implemented in a 3D integrated circuit device.

15. A programmable integrated circuit comprising a plurality of programmable logic blocks and a network,

each programmable logic block of said plurality of programmable logic blocks comprising a plurality of inlet links and a plurality of outlet links; and

said 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 of said plurality of partial multi-stage networks; and

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 further comprising one or more slices, each slice of said one or more slices further comprising one or more rings, each ring of said one or more rings further comprising y stages, where y≥1; and

each stage of said y stages comprising at least one switch of size d i ×d 0 , where d≥2 and d 0 ≥2 and each switch of said at least one switch of size d i ×d 0 having d i incoming links and d 0 outgoing links; and each switch of said at least one switch of size d i ×d 0 further comprising a plurality of multiplexers of size d≥2 with each multiplexer of said plurality of multiplexers comprising d inputs and one output; and

said at least one switch of size d i ×d 0 comprises either only a forward switch, or only a backward switch, or both a forward switch and a backward switch, or a forward switch, a backward switch and U-turn switch, or a forward switch, a backward switch and a U-turn switch without 180 degree turn paths, or an integrated switch of a forward switch, a backward switch and U-turn switch, or an integrated switch of a forward switch, a backward switch and a U-turn switch without 180 degree turn paths; and

said d i incoming links and said d 0 outgoing links comprises a plurality of internal connections and a plurality of hop wires; and said plurality of hop wires further comprising a plurality of internal hop wires or a plurality of external hop wires; and

each inlet link of Said plurality of inlet links is connected to the output of one of said plurality of multiplexers of one switch of said at least one switch of size d i ×d 0 of one stage of said y stages of one 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 one of the inputs of one or more of said plurality of multiplexers of one or more said switches of said at least one switch of size d i x d 0 of

one or more said stages of said y stages of one or more said plurality of partial multi-stage networks; and

a first programmable logic block of said plurality of programmable logic blocks comprising the same or different number of said plurality of inlet links as a second programmable logic block of said plurality of programmable logic blocks and a first programmable logic block of said plurality of programmable logic blocks comprising the same or different number of said plurality of outlet links as a second programmable logic block of said plurality of programmable logic blocks; a first partial multi-stage network of said plurality of partial multi-stage networks comprising the same or different number of said one or more slices as a second partial multi-stage network of said plurality of partial multi-stage networks; a first slice of said one or more slices comprising the same or different number of said one or more rings as a second slice of said one or more slices; a first ring of said one or more rings comprising the same or different number of said y stages as a second ring of said one or more rings; and a first stage of said y stages comprising the same or different number of said at least one switch of size d i ×d 0 as a second stage of said y stages; a first switch of said at least one switch of size d i ×d 0 is the same or different size as a second switch of said at least one switch of size d i ×d 0 a first multiplexer in said plurality of multiplexers of size d≥2 is the same or different size as a second multiplexer in said plurality of multiplexers of size d≥2; and

each internal connection of said plurality of 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 d i ×d 0 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 d i ×d 0 of a second stage of said y stages of the first ring of said one or more rings; and

each internal hop wire of said plurality of 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 d i ×d 0 of a stage of said y stages of a first ring of said one or more rings of a 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 d i ×d 0 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 same slice of said one or more slices; and

each external hop wire of said plurality of 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 d i ×d 0 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 d i ×d 0 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

one or more external hop wires of said plurality of external hop wires are either connected between multiplexers of said plurality of multiplexers of switches of said at least one switch of size d i ×d 0 in same numbered stages of said y stages in three or more partial multi-stage networks of said plurality of partial multi-stage networks or connected between multiplexers of said plurality of multiplexers of switches of said at least one switch of size d i ×d 0 in different numbered stages of said y stages, when y≥2, in three or more partial multi-stage networks of said plurality of partial multi-stage networks.

16. The programmable integrated circuit of claim 15 , wherein said plurality of external hop wires are connected vertically (hereinafter “vertical links”), or horizontally (hereinafter “horizontal links”), or by both vertical links and horizontal links; and

each partial multi-stage network of said plurality of partial multi-stage networks comprising said one or more slices is replicated in either said plurality of rows or said plurality of columns of the two-dimensional grid, or

each partial multi-stage network of said plurality of partial multi-stage networks comprising said horizontal links and said vertical links is replicated in either said plurality of rows or said plurality of columns of the two-dimensional grid, or

each partial multi-stage network of said plurality of partial multi-stage networks comprising both said one or more slices, and said horizontal links and said vertical links is replicated in either said plurality of rows or said plurality of columns of the two-dimensional grid.

17. The programmable integrated circuit of claim 15 , wherein said plurality of external hop wires are cascaded through only one multiplexer of said plurality of multiplexers at each switch of said at least one switch of size d i ×d 0 .

18. The programmable integrated circuit of claim 15 , wherein said one or more external hop wires of said plurality of external hop wires are connected between at least one same numbered stage in all said plurality of partial multi-stage networks, or

one or more external hop wires of said plurality of external hop wires are connected between at least two not same numbered stages of said y stages in all said plurality of partial multi-stage networks; or

said plurality of external hop wires are all connected between same numbered stages of said y stages in all stages of said y stages of all said plurality of partial multi-stage networks.

19. The programmable integrated circuit of claim 15 , wherein one or more stages of said y stages in one partial multi-stage network of said plurality of partial multi-stage networks are not connected to any other stages of said y stages in another partial multi-stage network of said plurality of partial multi-stage networks, or,

one or more stages of said y stages in one partial multi-stage network of said plurality of partial multi-stage networks are connected to stages of said y stages in another partial multi-stage network of said plurality of partial multi-stage networks by one or more external hop wires of said plurality of external hop wires, only when said two-dimensional grid is replicated by increasing said plurality of rows or said plurality of columns.

20. The programmable integrated circuit of claim 15 , wherein one or more of external hop wires of said plurality of external hop wires are implemented in two or more metal layers, or

each multiplexer of said plurality of multiplexers of size d 2 is configurable by SRAM cells or Flash Cells, or

said plurality of external hop wires use a plurality of buffers to amplify signals driven through them; and said plurality of buffers are either inverting or non-inverting buffers, or

one or more stages of said y stages in one partial multi-stage network of said plurality of partial multi-stage networks comprising a switch of size (d i +m)×(d 0 +n), where d i ≥2, d 0 d≥2, m≥0, n≥0 or

one or more of said y stages in one partial multi-stage network of said plurality of partial multi-stage networks comprising six 2:1 multiplexers, or eight 2:1 multiplexers, or four 3:1 multiplexers, or four 4:1 multiplexers, or

said at least one switch of size d i ×d 0 of said y stages are either fully populated or partially populated, or

said plurality of partial multi-stage networks are implemented in a 3D integrated circuit device.