Method and apparatus for network with multilayer metalization

• US 20050063373A1
• Filed: 07/23/2004
• Published: 03/24/2005
• Est. Priority Date: 07/24/2003
• Status: Active Grant

• Current Assignee: California Institute of Technology
• Original Assignee: California Institute of Technology
• Inventors: DeHon, Andre, Rubin, Raphael
• Granted Patent: US 7,285,487 B2
• Time in Patent Office: Days
• US Class Current: 370/380
• CPC Class Codes: G06F 15/8023 Two dimensional arrays, e.g. mesh, torus
• CPC Class Codes: H03K 19/17736 Structural details of routing resources
• CPC Class Codes: H03K 19/1778 Structural details for adapting physical parameters
• CPC Class Codes: H03K 19/17796 for physical disposition of blocks

Abstract

A network for interconnecting processing element nodes which supports rich interconnection while having a number of switching elements which is linear in the number of processing elements interconnected. Processing elements connect to the lowest level of the tree and the higher levels of the tree make connections between the processing elements. The processing elements may be laid out in a two dimensional grid and one or more horizontal and vertical trees may be used to connect between the processing elements with corner switches used to connect between the horizontal and vertical trees. The levels of the tree can be accommodated in multiple layers of metalization such that the entire layout requires a two-dimensional area which is linear in the number of processing elements supported.

Claims

1. An apparatus comprising:

a plurality of processing elements;

one or more first dimension channels;

each first dimension channel comprising;

a plurality of first dimension interconnect paths, wherein at least some of the first dimension interconnect paths are coupled to at least some of the processing elements; and

a plurality of first dimension interconnect switches, wherein at least some first dimension interconnect switches are coupled to at least some of the first dimension interconnect paths to connect selected processing elements to other selected processing elements, and

wherein the plurality of first dimension interconnect paths and the plurality of first dimension interconnect switches are arranged to form one or more first dimension hierarchical levels, each first dimension hierarchical level comprising one or more first dimension parent segments, each first dimension parent segment having one or more corresponding first dimension child segments, the one or more corresponding first dimension child segments connected to the corresponding first dimension parent segment and wherein at least one first dimension child segment is also connected to a different first dimension parent segment within the same first dimension hierarchical level or wherein at least one first dimension child segment is also connected to a different first dimension parent segment at a different first dimension hierarchical level; and

one or more second dimension channels;

each second dimension channel comprising;

a plurality of second dimension interconnect paths, wherein at least some of the second dimension interconnect paths are coupled to at least some of the processing elements; and

a plurality of second dimension interconnect switches, wherein at least some second dimension interconnect switches are coupled to at least some of the second dimension interconnect paths to connect selected processing elements to other selected processing elements, and

wherein the plurality of second dimension interconnect paths and the plurality of second dimension interconnect switches are arranged to form one or more second dimension hierarchical levels, each second dimension hierarchical level comprising one or more second dimension parent segments, each second dimension parent segment having one or more corresponding second dimension child segments, the one or more corresponding second dimension child segments connected to the corresponding second dimension parent segment and wherein at least one second dimension child segment is also connected to a different second dimension parent segment within the same second dimension hierarchical level or wherein at least one second dimension child segment is also connected to a different second dimension parent segment at a different second dimension hierarchical level, and

wherein each processing element is either connected to at least one first dimension child segment at a lowest level of the first dimension hierarchical levels, or is connected to at least one second dimension child segment at a lowest level of the second dimension hierarchical levels, or is connected to at least one first dimension child segment at a lowest level of the first dimension hierarchical levels and to at least one second dimension child segment at a lowest level of the second dimension hierarchical levels.

2. The apparatus according to claim 1, wherein the plurality of processing elements are disposed in a two-dimensional grid and the one or more first dimension channels comprise horizontal channels and the one or more second dimension channels comprise vertical channels.

3. The apparatus according to claim 1, wherein the apparatus comprises a semiconductor device having a plurality of metal layers providing interconnects and the plurality of first dimension interconnect paths and the plurality of second dimension interconnect paths are distributed among the plurality of metal layers.

4. The apparatus according to claim 1, wherein the number of first dimension and/or second dimension child segments connected to the parent segment of the first dimension and/or second dimension child segments varies according to the level of the hierarchy at which the first dimension and/or second dimension child segments are disposed.

5. The apparatus according to claim 1, wherein the plurality of processing elements are disposed in a two dimensional grid and the one or more first dimension channels comprise one or more horizontal trees and the one or more second dimension channels comprise one or more vertical trees.

6. The apparatus according to claim 5, further comprising one or more corner switches, wherein the one or more corner switches connect one or more portions of the one or more horizontal trees to one or more portions of the one or more vertical trees.

7. The apparatus according to claim 1, wherein the apparatus comprises a semiconductor device having a plurality of metal layers to provide interconnects and the plurality of horizontal interconnect paths are disposed in one or more metal layers of the plurality of metal layers and the vertical interconnect paths are disposed in a different one or more metal layers of the plurality of metal layers.

8. The apparatus according to claim 1, wherein at least one interconnect switch of the plurality of first dimension and/or second dimension interconnect switches comprises a buffered switch.

9. The apparatus according to claim 1, wherein at least one interconnect path of the plurality of first dimension and/or second dimension interconnect paths comprises a buffered wire run.

10. The apparatus according to claim 1 further comprising:

one or more shortcut switches; and

one or more shortcut runs,

wherein the one or more shortcut switches couple to the one or more shortcut runs to couple selected segments of at least one first dimension channel or at least one second dimension channel.

11. The apparatus according to claim 10, wherein the one or more shortcut switches couple the selected segments at the same hierarchical level.

12. The apparatus according to claim 1, wherein at least one processing element comprises an element selected from the group comprising:

one or more look-up tables, fixed gates, processors, memories, programmable logic arrays, blocks of look-up tables, and any combination thereof.

13. The apparatus according to claim 1, wherein the apparatus further comprises:

one or more extra-dimensional channels;

each extra-dimensional channel comprising;

a plurality of extra-dimensional interconnect paths, wherein at least some of the extra-dimensional interconnect paths are coupled to at least some of the processing elements; and

a plurality of extra-dimensional interconnect switches, wherein at least some extra-dimensional interconnect switches are coupled to at least some of the extra-dimensional interconnect paths to connect selected processing elements to other selected processing elements, and

wherein the plurality of extra-dimensional interconnect paths and the plurality of extra-dimensional interconnect switches are arranged to form one or more extra-dimensional hierarchical levels, each extra-dimensional hierarchical level comprising one or more extra-dimensional parent segments, each extra-dimensional parent segment having one or more corresponding extra-dimensional child segments, the one or more corresponding extra-dimensional child segments connected to the corresponding extra-dimensional parent segment and wherein at least one child segment is also connected to a different extra-dimensional parent segment within the same extra-dimensional hierarchical level or wherein at least one child segment is also connected to a different extra-dimensional parent segment at a different extra-dimensional hierarchical level.

14. The apparatus according to claim 13, wherein said processing elements are distributed among multiple levels in a structure.

15. The apparatus according to claim 1, wherein each processing element connected to a first dimension child segment of a first dimension channel has a constant number of first dimension interconnect switches connecting the first dimension interconnect paths to the processing element or wherein each processing element connected to a second dimension child segment of a second dimension channel has a constant number of second dimension interconnect switches connecting the second dimension interconnect paths to the processing element.

16. The apparatus according to claim 1 wherein at least one first dimension interconnect switch and/or at least one second dimension interconnect switch comprises a device selected from the group consisting of:

a via programmable switch;

a fusable switch;

an antifusable switch;

a time switched device;

a circuit switched device;

a packet switched device, and any combination thereof.

17. The apparatus according to claim 3, wherein the plurality of first dimension interconnect switches and the plurality of second dimension interconnect switches comprise programmable vias on a designated programmable via layer.

18. The apparatus according to claim 1, wherein each processing element has a constant upper bound on the number of first dimension interconnect switches and/or second dimension interconnect switches associated with the processing element and wherein the constant upper bound is invariant with the total number of processing elements in the apparatus.

19. The apparatus according to claim 1, wherein each processing element has a constant upper bound on the number of switches associated with the processing element and wherein the constant upper bound is invariant as the apparatus is scaled to a greater number or lesser number of processing elements.

20. The apparatus according to claim 1, wherein each processing element has a constant upper bound on the number of switches associated with the processing element and wherein the constant upper bound depends on the Rent growth rate factor and not on the total number of processing elements being interconnected.

21. A method of providing connections between a plurality of processing elements comprising:

providing a plurality of first dimension interconnect paths, wherein some of the first dimension interconnect paths are coupled to processing elements;

providing a plurality of first dimension interconnect switches, the plurality of first dimension interconnect switches connecting selected first dimension interconnect paths to other selected first dimension interconnect paths;

configuring the plurality of first dimension interconnect paths and the plurality of first dimension interconnect switches to form one or more first dimension trees, each first dimension tree having one or more levels of first dimension parent-child hierarchy, wherein at least one processing element is connected to at least one first dimension child at a lowest level of the first dimension parent-child hierarchy and at least one first dimension child has a plurality of first dimension parents;

providing a plurality of second dimension interconnect paths, wherein some of the second dimension interconnect paths are coupled to processing elements;

providing a plurality of second dimension interconnect switches, the plurality of second dimension interconnect switches connecting selected second dimension interconnect paths to other selected second dimension interconnect paths; and

configuring the plurality of second dimension interconnect paths and the plurality of second dimension interconnect switches to form one or more second dimension trees, each second dimension tree having one or more levels of second dimension parent-child hierarchy, wherein at least one processing element is connected to at least one second dimension child at a lowest level of the second dimension parent-child hierarchy and at least one second dimension child has a plurality of second dimension parents.

22. The method according to claim 21, wherein the plurality of first dimension and second dimension interconnect paths are disposed in one or more metal layers of a semiconductor device.

23. The method according to claim 21, wherein at least one first dimension and/or second dimension tree is formed having an arity other than two.

24. The method according to claim 23, wherein the number of segments of a first level connected to a level immediately above the first level varies according to the level of the first dimension and/or second dimension hierarchy at which the first level is disposed.

25. The method according to claim 21 further comprising:

disposing corner switches to connect one or more portions of the one or more first dimension trees to one or more portions of the one or more second dimension trees.

26. The method according to claim 21 further comprising;

forming a plurality of metal layers in a semiconductor device;

disposing the first dimension interconnect paths in one or more metal layers of the plurality of metal layers; and

disposing the second dimension interconnect paths in a different one or more metal layers of the plurality of metal layers.

27. The method according to claim 21, wherein at least one first dimension and/or second dimension interconnect switch comprises a buffered switch.

28. The method according to claim 21, wherein at least one first dimension and/or second dimension interconnect path comprises a buffered wire run.

29. The method according to claim 21 further comprising:

disposing one or more shortcut runs;

disposing shortcut switches at each end of the one or more shortcut runs; and

coupling selected segments of at least one first dimension tree and/or second dimension tree with the shortcut switches and the one or more shortcut runs.

30. The method according to claim 29, wherein the one or more shortcut switches couple the selected segments at the same hierarchical level.

31. The method according to claim 21, wherein the levels of at least one first dimension tree and/or second dimension tree are staggered.

32. The method according to claim 21, wherein the one or more first dimension trees and/or the one or more second dimension trees which are present in a same channel are staggered relative to each other.

33. The method according to claim 21, wherein at least one processing element comprises an element selected from the group comprising:

one or more look-up tables, fixed gates, processors, memories, programmable logic arrays, blocks of look-up tables, and any combination thereof.

34. The method according to claim 21, wherein each processing element connected to a first dimension child segment of a first dimension tree has a constant number of first dimension interconnect switches connecting the first dimension interconnect paths to the processing element or wherein each processing element connected to a second dimension child segment of a second dimension tree has a constant number of second dimension interconnect switches connecting the second dimension interconnect paths to the processing element.

35. The method according to claim 21, wherein each processing element has a constant upper bound on the number of first dimension interconnect switches and/or second dimension interconnect switches associated with the processing element and wherein the constant upper bound is invariant with the total number of processing elements being connected.

36. The method according to claim 21, wherein each processing element has a constant upper bound on the number of switches associated with the processing element and wherein the constant upper bound is invariant as additional tree levels are added to accommodate a greater number of processing elements or as tree levels are deleted to accommodate a smaller number of processing elements.

37. The method according to claim 21, wherein each processing element has a constant upper bound on the number of switches associated with the processing element and wherein the constant upper bound depends on the Rent growth rate factor and not on the total number of processing elements being interconnected.

38. The method according to claim 21, wherein the method further comprises:

providing a plurality of extra-dimensional interconnect paths, wherein some of the extra-dimensional interconnect paths are coupled to processing elements;

providing a plurality of extra-dimensional interconnect switches, the plurality of extra-dimensional interconnect switches connecting selected extra-dimensional interconnect paths to other selected extra-dimensional interconnect paths; and

configuring the plurality of extra-dimensional interconnect paths and the plurality of extra-dimensional interconnect switches to form one or more extra-dimensional trees, each extra-dimensional tree having one or more levels of extra-dimensional parent-child hierarchy, wherein at least one processing element is connected to at least one extra-dimensional child at a lowest level of the extra-dimensional parent-child hierarchy and at least one extra-dimensional child has a plurality of extra-dimensional parents.

39. The method according to claim 21, wherein the method is used to provide routing in a programmable semiconductor device.

40. The method according to claim 21, wherein the plurality of processing elements are disposed in a two-dimensional grid and the one or more first dimension trees comprise horizontal trees and the one or more second dimension trees comprise vertical trees.

41. The method according to claim 21, wherein the method further comprises allocating additional switches for connections beyond a minimum number of switches required for connectivity of the one or more first dimension trees and/or the one or more second dimension trees.

42. The method according to claim 41, wherein allocating additional switches comprises:

identifying all possible shortcuts, corner turns, and/or uplinks that may be associated with a processing element;

allocating a fixed number of shortcuts for each processing element;

allocating a fixed number of corner turns for each processing element;

allocating a fixed number of uplinks for each processing element;

randomly assigning added shortcut switches up to the fixed number of shortcuts for each processing element;

randomly assigning added corner turn switches up to the fixed number of corner turns for each processing element; and

randomly assigning added uplink switches up to the fixed number of uplinks for each processing element.

43. The method according to claim 41, wherein allocating additional switches comprises:

identifying all possible shortcuts, corner turns, and/or uplinks that may be associated with a processing element;

allocating a total number of switches for each processing element;

randomly assigning added shortcut switches for each processing element;

randomly assigning added corner turn switches for each processing element; and

randomly assigning added uplink switches for each processing element,

wherein the number of randomly assigned switches for each processing element does not exceed the total number of switches allocated for each processing element.

44. The method according to claim 43, wherein fixed percentages are selected for the total numbers of added shortcut switches, corner turn switches, and uplink switches.

45. A method for providing placement and routing of a network having multiple nodes laid out in a two-dimensional pattern, said method comprising:

partitioning the circuit into multiple partitions having a hierarchy;

using the partition hierarchy to associate nodes with processing elements;

forming one or more vertical trees based on the partition hierarchy, wherein each vertical tree has multiple levels and each vertical child at a first vertical level is connected to a vertical parent at second vertical level above the first vertical level, and at least one node is connected to a vertical child at the lowest vertical level, and wherein connections between vertical children and vertical parents are provided by vertical switches;

forming one or more horizontal trees based on the partition hierarchy, wherein each horizontal tree has multiple levels and each horizontal child at a first horizontal level is connected to a horizontal parent at second horizontal level above the first horizontal level, and at least one node is connected to a horizontal child at the lowest horizontal level, and wherein connections between horizontal children and horizontal parents are provided by horizontal switches;

constructing at least one vertical tree and/or one horizontal tree to provide a minimum number of switches between a first node and a second node; and

providing one or more corner switches to switch between at least one vertical tree and at least one horizontal tree.

46. The method according to claim 45, further comprising:

placing wire segments;

performing a route of network connections on at least one vertical tree and/or at least one horizontal tree; and

using switch selections in routing the at least one vertical tree and/or the at least one horizontal tree to connect wire segments to realize the network.

47. The method according to claim 45, wherein the one or more corner switches are applied at different levels of the hierarchy of the at least vertical tree and the at least one horizontal tree.

48. The method according to claim 47, wherein at least one level of the hierarchy of at least one vertical tree and/or at least one horizontal tree has more children than other levels of the hierarchy of the least one vertical tree and/or at least one horizontal tree.

49. A method a placing a graph with multiple nodes in two dimensions to provide routing connections between processing elements in a circuit, wherein the circuit is realized in a structure having multiple metal layers, the method comprising:

partitioning the circuit into multiple partitions to provide a partition hierarchy;

associating the nodes with processing elements based on the partition hierarchy;

assigning partitions to successive halves of a Butterfly Fat Tree network, wherein the Butterfly Fat Tree network has a plurality of horizontal channels and/or a plurality of vertical channels;

routing connections between nodes in the Butterfly Fat Tree topology;

adding one or more links between one or more nodes in at least one horizontal channel to one or more nodes in one or more other horizontal channels, wherein the one or more nodes are at a same logical level in the horizontal channels and/or adding one or more links between one or more nodes in at least one vertical channel to one or more nodes in one or more other vertical channels, wherein the one or more nodes are at a same logical level in the vertical channels; and

using an assignment of node to Butterfly Fat Tree links and a physical layout of the Butterfly Fat Tree links to define physical routes between nodes.

50. A method for providing interconnection between a plurality of processing elements comprising:

providing a plurality of switches;

arranging the plurality of switches to provide one or more tree structures, each tree structure having a plurality of branches and a plurality of levels;

associating each processing element in the plurality of processing elements with a corresponding lowest level switch at a lowest level of each tree by coupling the processing element to the corresponding lowest level switch;

recursively building each tree structure by;

coupling each switch to one or more switches at a same level in the tree structure and/or to one or more switches at a higher level in the tree structure; and

continue coupling the switches until there is a path for each processing element from one or more common points at a top level of the tree structure to each processing element,

wherein the number of switches in the path between at least one common point and the processing element is the same for each processing element and wherein at least one tree structure has an arity other than two and/or has a Rent exponent other than 0.5.

51. The method according to claim 50, wherein the one or more tree structures comprise one or more first dimension tree structures and one or more second dimension tree structures and one or more switches in the plurality of switches connect an upper level of at least one first dimension tree structure to an upper level of at least one second dimension tree structure.

52. A method for constructing a hierarchical synchronous reconfigurable array or Butterfly Fat Tree comprising:

providing a plurality of horizontal channels and/or vertical channels, wherein the plurality of horizontal channels and/or vertical channels are configured according to horizontal channels and/or vertical channels of a mesh of trees topology;

adding one or more links between one or more switching nodes in at least one horizontal channel to one or more switching nodes in one or more other horizontal channels, wherein the one or more switching nodes are at a same logical level in the horizontal channels; and

/or

adding one or more links between one or more switching nodes in at least one vertical channel to one or more switching nodes in one or more other vertical channels, wherein the one or more switching nodes are at a same logical level in the vertical channels.

53. The method according to claim 52, wherein if the horizontal channels are configured in mesh of trees topology, the vertical channels are arranged in a non-augmented mesh of trees topology and if the vertical channels are configured in mesh of trees topology, the horizontal channels are arranged in a non-augmented mesh of trees topology.

54. The method according to claim 52, wherein either the horizontal channels or the vertical channels are configured in a non-augmented mesh of trees topology.

55. The method according to claim 52, further comprising:

adding one or more links between one or more switching nodes in at least one horizontal channel to one or more switching nodes in one or more vertical channels, wherein the one or more switching nodes are at a same logical level in the horizontal and vertical channels.

56. The method according to claim 52, wherein adding one or more links between one or more switching nodes in at least one horizontal channel to one or more switching nodes in one or more other horizontal channels comprises using links in one or more vertical channels and/or adding one or more links between one or more switching nodes in at least one vertical channel to one or more switching nodes in one or more other vertical channels comprises using links in one or more horizontal channels.

57. The method according to claim 52 further comprising:

adding orthogonal interchanges comprising homogeneous upper level corner turns between one or more horizontal channels and one or more vertical channels.

58. The method according to claim 52, wherein the hierarchical reconfigurable synchronous array or butterfly fat tree is implemented in a structure having multiple metal layers.

59. The method according to claim 52 further comprising adding orthogonal interchanges between at least one horizontal channel and at least one vertical channel.

60. A method of designing a network comprising:

parameterizing a mesh of trees topology by selecting or determining one or more of the following parameters;

base channels, Rent exponents, growth rate per level, arity, flattening, shortcuts, upper level corner turns, and staggering; and

optimizing the parameters for desired network performance characteristics

wherein the network is constructed according to the method of claim 52.

61. A method for mapping a graph of connected nodes:

recursively bisecting the graph;

assigning graph partitions from the bisection to successive halves of a Butterfly Fat Tree;

building the Butterfly Fat Tree with a plurality of hierarchical horizontal and vertical channels, wherein at least one horizontal channel and/or vertical channel has at least one child segment connected to a plurality of parent segments at the same or different levels in the hierarchical horizontal and/or vertical channels; and

,

routing the mapped network on the Butterfly Fat Tree.

62. The method according to claim 61, wherein building the Butterfly Fat Tree comprises adding one or more links between one or more switching nodes in at least one horizontal channel to one or more switching nodes in one or more other horizontal channels, wherein the one or more switching nodes are at a same logical level in the horizontal channels and/or adding one or more links between one or more switching nodes in at least one vertical channel to one or more switching nodes in one or more other vertical channels, wherein the one or more switching nodes are at a same logical level in the vertical channels.

63. The method according to claim 61, wherein the method further comprises allocating additional switches for connections.

64. The method according to claim 63, wherein allocating additional switches comprises:

identifying all possible shortcuts, corner turns, and/or uplinks that may be associated with a node;

allocating a fixed number of shortcuts for each node;

allocating a fixed number of corner turns for each node;

allocating a fixed number of uplinks for each node;

randomly assigning added shortcut switches up to the fixed number of shortcuts for each node;

randomly assigning added corner turn switches up to the fixed number of corner turns for each node; and

randomly assigning added uplink switches up to the fixed number of uplinks for each node.

65. The method according to claim 63, wherein allocating additional switches comprises:

identifying all possible shortcuts, corner turns, and/or uplinks that may be associated with a node;

allocating a total number of switches for each node;

randomly assigning added shortcut switches for each node;

randomly assigning added corner turn switches for each node; and

randomly assigning added uplink switches for each node,

wherein the number of randomly assigned switches for each node does not exceed the total number of switches allocated for each node.

66. The method according to claim 65, wherein fixed percentages are selected for the total numbers of added shortcut switches, corner turn switches, and uplink switches.

67. A method for laying out a plurality of processing elements in a structure having multiple metal layers at different levels comprising:

connecting the plurality of processing elements to plurality of hierarchical horizontal and vertical trees, wherein at least one horizontal channel and/or vertical channel has at least one child segment connected to a plurality of parent segments at the same or different levels in the hierarchical horizontal and/or vertical channels;

associating switches providing inter-tree-level routing in each horizontal and vertical tree with a corresponding processing element; and

assigning wiring for different tree levels to metal layers at different or same levels.

68. The method according to claim 67, wherein the switches are disposed on a selected layer and the method further comprises providing one or more via channels to connect wire runs on different or same levels to the switches.

69. The method according to claim 68, wherein the switches and processing elements are located on a substrate.

70. The method according to claim 68, wherein the one or more via layers are disposed between metal layers.

71. The method according to claim 68, wherein customization of network connectivity is provided by one or more customizable via layers.

72. The method according to claim 67, wherein associating switches comprises:

associating switches at lowest levels of the one or more horizontal and/or vertical trees with the corresponding processing element;

associating switches at progressively higher levels of the one or more horizontal and/or vertical trees with corresponding processing elements until there are only half as many switches at a level as at the lowest level of the one or more horizontal and/or vertical trees;

associate the switches at this level with one half of the processing elements;

repeat the association of switches at progressively higher levels with corresponding processing elements within the one half of the processing elements until there is an association of switches to half as many processing elements as at a previous level so that there are half as many switches as this level as there are processing elements that have not had upper level switches assigned;

select one half of the remaining switches and assign to the corresponding processing elements; and

continue associating switches in this manner until switches at all levels are assigned.

73. The method according to claim 67, wherein associating switches comprises:

identifying the lowest, successive tree level where the number of switches out of the parent stage is half the number of switches in a present level;

grouping subtree switching between these two stages into a macro switch;

associating each macro switch with a processing element, within a span of processing elements which are children of the macro switch, which does not already have a macro switch associated with it; and

setting the present level as the last set of macro switches placed; and

repeating the identifying, grouping and associating processes for successive levels until all switches have been placed.

74. The method according to claim 67, wherein associating switches comprises:

associating switches at a lowest level of one or more horizontal and/or vertical trees with corresponding processing elements;

moving up a level in the one or more horizontal and/or vertical trees;

distributing the switches at this next level to the processing element within a span of the switches with the least number of assigned switches; and

repeating the associating, moving, and distributing processes until all switches have been placed.

75. The method according to claim 72, wherein switches to higher levels of the horizontal and/or vertical trees are uplink switches and the method further comprises adding shortcut connections by associating a shortcut switch with the same processing element as the associated uplink switch.

76. The method according to claim 74, wherein switches to higher levels of the horizontal and/or vertical trees are uplink switch and the method further comprises adding shortcut connections by associating a shortcut switch with the same processing element as the associated uplink switch.

77. The method according to claim 75, wherein one or more shortcut switches are placed on one side of the shortcut connections and another side of the shortcut connections are direct connections with the associated shortcut switches.

78. The method according to claim 76, wherein one or more shortcut switches are placed on one side of the shortcut connections and another side of the shortcut connections are direct connections with the associated shortcut switches.

79. The method according to claim 73, wherein at least one macro switch is extended with one or more links for shortcut connections.

80. The method according to claim 72, wherein the plurality of horizontal trees comprises a plurality of horizontal channels configured according to horizontal channels of a mesh of trees topology and the plurality of vertical trees comprise a plurality of vertical channels configured according to vertical channels of a mesh of trees topology and the method further comprises:

adding one or more links between one or more switching nodes in at least one horizontal channel to one or more switching nodes in one or more other horizontal channels, wherein the one or more switching nodes are at a same logical level in the horizontal channels and/or adding one or more links between one or more switching nodes in at least one vertical channel to one or more switching nodes in one or more other vertical channels, wherein the one or more switching nodes are at a same logical level in the vertical channels.

81. The method according to claim 80, wherein links are routed along orthogonal interconnect channels.

82. The method according to claim 81, wherein one or more added links comprise one or more added wires.

83. The method according to claim 81, wherein one or more added links comprise one or more wires already present in channels being used.

84. The method according to claim 74, wherein the plurality of horizontal trees comprises a plurality of horizontal channels configured according to horizontal channels of a mesh of trees topology and the plurality of vertical trees comprise a plurality of vertical channels configured according to vertical channels of a mesh of trees topology and the method further comprises:

adding one or more links between one or more switching nodes in at least one horizontal channel to one or more switching nodes in one or more other horizontal channels, wherein the one or more switching nodes are at a same logical level in the horizontal channels and/or adding one or more links between one or more switching nodes in at least one vertical channel to one or more switching nodes in one or more other vertical channels, wherein the one or more switching nodes are at a same logical level in the vertical channels.

85. The method according to claim 67, wherein associating switches comprises:

associating switches at lowest levels of the one or more horizontal and/or vertical trees with corresponding processing elements; and

associating switches at progressively higher levels of the one or more horizontal and/or vertical trees in blocks covered by arity-1 children over tails of said children.

86. The method according to claim 85, wherein associating switches at progressively higher levels comprises using one slot from a last block of each child and/or using a last block from each subsequent descendent recursively.

87. The method according to claim 85, wherein associating switches at progressively higher levels comprises finding a least populated block, associating a switch, and repeating until all switches are assigned.