# US 9,519,605 B2 · Interconnection network topology for large scale high performance computing (HPC) systems > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,519,605 B2 - Document ID: US9519605B2 - Status: Granted - Kind: B2 - Application number: 14/326,208 - Filed: 2014-07-08 - Published: 2016-01-14 - Granted: 2016-12-13 - Earliest claimed: 2014-07-08 - Assignees: International Business Machines Corporation - Applicants: International Business Machines Corporation - Inventors: Baba L. Arimilli; Wolfgang Denzel; Philip Heidelberger; German Rodriguez Herrera; Christopher J. Johnson; Lonny Lambrecht; Cyriel Minkenberg; Bogdan Prisacari - Web page: https://patentgrep.com/patent/US9519605B2 ## CPC - G06F 13/4022: {using switching circuits, e.g. switching matrix, connection or expansion network (G06F13/4009 takes precedence)} - G06F 13/4027: {using bus bridges (G06F13/4022 takes precedence)} - G06F 13/4036: {and deadlock prevention} - G06F 13/4221: {being an input/output bus, e.g. ISA bus, EISA bus, PCI bus, SCSI bus} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A multiprocessor computer system includes a plurality of processor nodes and at least a three-tier hierarchical network interconnecting the processor nodes. The hierarchical network includes a plurality of routers interconnected 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≧3 tiers (T1, . . . , Tn); the plurality of routers are partitioned into disjoint groups at the first tier T1, the groups at tier Ti being partitioned into disjoint groups (of complete Ti groups) at the next tier Ti+1 and a top tier Tn including a single group containing all of the plurality of routers; and for all tiers 1≦i≦n, each tier-Ti−1 subgroup within a tier Ti group is connected by at least one link to all other tier-Ti−1 subgroups within the same tier Ti group. ## Claims ### Claim 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 (T1, . . . , Tn) where n is at least three; the plurality of routers are partitioned into disjoint groups at a first tier T1, groups of routers at each intermediate tier Ti are partitioned into disjoint groups at a next higher tier Ti+1, and a top tier Tn includes a single group containing all of the plurality of routers; for all tiers 1≦i≦n, each tier-Ti−1 subgroup within a tier Ti group is connected by at least one link to all other tier-Ti−1 subgroups within a same tier Ti group. ### Claim 2 (depends on 1) The multiprocessor computer system of claim 1, wherein each group of at least one specific tier Ti is connected to each other group within a same tier Ti+1 group by a plurality of links, such that multiple but less than all Ti−1 routers from one T group are connected to different Ti−1 routers in its peer Ti group. ### Claim 3 (depends on 2) The multiprocessor computer system of claim 2, wherein a number of links connecting each pair of Ti subgroups is an integer divisor of the number of routers times the number of tier-i links per router in each Ti subgroup. ### Claim 4 (depends on 3) The multiprocessor computer system of claim 3, wherein: bundling factors at tiers (T1, . . . , Tn) equal (b1, . . . , bn); a number of subgroups that comprise a tier Ti group equals G i ′ = ( ∏ j = 1 n - 1 ⁢ ⁢ G j ′ ) ⁢ h i b i + 1 , where hi is a number of peer ports per router for tier Ti; a total number of routers Si′ that comprise a tier Ti group equals S i ′ = ∏ j = 1 i ⁢ ⁢ G j ′ ; and for all i, bundling factor bi is an integer divisor of Si′·hi. ### Claim 5 (depends on 1) The multiprocessor computer system of claim 1, wherein a number of links provided by each router to connect to other groups at respective tiers (T1, T2, . . . , Tn) equals (h1, . . . , hn), such that the number Gi of subgroups that comprise a tier Ti group equals G n = ( ∏ j = 1 n - 1 ⁢ ⁢ G j ) · h n + 1 and a total number Si of routers that comprise a tier Ti group equals S i = ( ∏ j = 1 i ⁢ ⁢ G j ) . ### Claim 6 (depends on 1) 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 (T1, T2, . . . , Tn) equals (2n−1, 2n−2, . . . , 1). ### Claim 7 (depends on 1) The multiprocessor computer system of claim 1, wherein each router provides, for each link corresponding to a connection between subgroups at tier Ti, at least 2n−i distinct virtual channels for deadlock-free shortest-path routing, for 1≦i≦n. ### Claim 8 (depends on 7) The multiprocessor computer system of claim 7, wherein routers perform a virtual channel mapping of traffic arriving on an incoming virtual channel number vcx of a link corresponding to tier Tx to a link corresponding to outgoing tier Ty to an outgoing virtual channel number vcy depending on index x, index y, and the incoming virtual channel number vcx 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. ### Claim 9 (depends on 1) The multiprocessor computer system of claim 1, wherein each router provides, for each link corresponding to a connection between subgroups at tier Ti, at least 2n−i+2n−i−1 distinct virtual channels for deadlock-free indirect routing, for 1≦i