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

1. A multiprocessor computer system comprising:

a plurality of processor nodes; and

a multi-tier hierarchical network interconnecting the processor nodes, wherein the multi-tier hierarchical network includes a plurality of routers, wherein:

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 multiprocessor computer system of claim 1 , wherein each group of at least one specific tier T i is connected to each other group within a same tier T i+1 group by a plurality of links, such that multiple but less than all T i−1 routers from one T group are connected to different T i−1 routers in its peer T i group.

3. The multiprocessor computer system 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 multiprocessor computer system 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 multiprocessor computer system of claim 1 , wherein a number of links provided by each router to connect to other groups at respective tiers (T 1 , T 2 , . . . , T n ) equals (h 1 , . . . , h 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 multiprocessor computer system 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 multiprocessor computer system of claim 1 , wherein each router provides, 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 multiprocessor computer system of claim 7 , wherein routers perform 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:

vc

y

=

⁢

⌊

vc

x

/

2

λ

⌋

,

y

>

x

=

⁢

vc

x

·

2

λ

+

2

λ

+

1

,

y

<

x

.

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

9. The multiprocessor computer system of claim 1 , wherein each router provides, 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 multiprocessor computer system of claim 1 , wherein at least one of the plurality of routers is integrated with one of the plurality of processing nodes.