Interconnection network topology for large scale high performance computing (HPC) systems

1. A method of constructing a multiprocessor computer system comprising:

providing a plurality of processor nodes; and

coupling the plurality of processor nodes with a multi-tier hierarchical interconnection network including a plurality of routers, such that:

each router is connected to a subset of the plurality of processor nodes;

the plurality of routers are arranged in a hierarchy of n tiers (T 1 , . . . , T n ) where n is at least three;

the plurality of routers are partitioned into disjoint groups at a first tier T 1 , groups of routers at each intermediate tier T i are partitioned into disjoint groups at a next higher tier T i+1 , and a top tier T n includes a single group containing all of the plurality of routers;

for all tiers 1≦i≦n , each tier-T i−1 subgroup within a tier T i group is connected by at least one link to all other tier-T i−1 subgroups within a same tier T i group.

2. The method of claim 1 , wherein the coupling includes connecting each group of at least one specific tier T i to each other group within a same tier T i+1 by a plurality of links, such that multiple but less than all T i−1 routers from one T i group are connected to different T i−1 routers in its peer Ti group.

3. The method of claim 2 , wherein a number of links connecting each pair of T i subgroups is an integer divisor of the number of routers times the number of tier-i links per router in each T i subgroup.

4. The method of claim 3 , wherein:

bundling factors at tiers (T 1 , . . . , T n ) equal (b 1 , . . . , b n );

a number of subgroups that comprise a tier T i group equals

G

i

′

=

(

∏

j

=

1

n

-

1

⁢

⁢

G

j

′

)

⁢

h

i

b

i

+

1

,

where h i is a number of peer ports per router for tier T i ;

a total number of routers S′ i that comprise a tier T i group equals

S

i

′

=

∏

j

=

1

i

⁢

⁢

G

j

′

;

and

for all i, bundling factor b i is an integer divisor of S′ i ·h i .

5. The method of claim 1 , wherein the coupling includes coupling a number of links (h 1 , . . . , h n ) of each router to other groups at respective tiers (T 1 , T 2 , . . . , T n ), such that the number G i of subgroups that comprise a tier T i group equals

G

n

=

(

∏

j

=

1

n

-

1

⁢

⁢

G

j

)

·

h

n

+

1

and a total number S i of routers that comprise a tier T i group equals

S

i

=

(

∏

j

=

1

i

⁢

⁢

G

j

)

.

6. The method of claim 1 , wherein a ratio between a number of links per router used to connect to groups at respective tiers (T 1 , T 2 , . . . , T n ) equals (2 n−1 , 2 n−2 , . . . , 1).

7. The method of claim 1 , and further comprising each router providing, for each link corresponding to a connection between subgroups at tier T i , at least 2 n−i distinct virtual channels for deadlock-free shortest-path routing, for 1≦i≦n.

8. The method of claim 7 , and further comprising:

the plurality of routers performing a virtual channel mapping of traffic arriving on an incoming virtual channel number vc x of a link corresponding to tier T x to a link corresponding to outgoing tier T y to an outgoing virtual channel number vc y depending on index x, index y, and the incoming virtual channel number vc x according to:

v

⁢

⁢

c

y

=

⁢

⌊

v

⁢

⁢

c

x

/

2

λ

⌋

,

y

>

x

=

⁢

v

⁢

⁢

c

x

·

2

λ

+

2

λ

-

1

,

y

<

x

,

where λ=|x−y| equals an absolute difference between incoming and outgoing tier indices.

9. The method of claim 1 , and further comprising:

each router providing, for each link corresponding to a connection between subgroups at tier T i , at least 2 n−i +2 n−i−1 distinct virtual channels for deadlock-free indirect routing, for 1≦i<n and at least two distinct virtual channels for tier T n .

10. The method of claim 1 , wherein the coupling includes coupling one of the plurality of processing nodes to one of the plurality of routers within a common integrated circuit chip.