# US 2008/0126571 A1 · Computer system and method using efficient module and backplane tiling to interconnect computer nodes via a Kautz-like digraph

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2008/0126571 A1
- Document ID: US20080126571A1
- Status: Published application
- Kind: A1
- Application number: 11/594,416
- Filed: 2006-11-08
- Published: 2008-05-29
- Earliest claimed: 2006-11-08
- Assignees: SiCortex, Inc.
- Inventors: Judson S. Leonard; Matthew H. Reilly; Lawrence C. Stewart; Washington Taylor
- Web page: https://patentgrep.com/patent/US20080126571A1

## CPC

- G06F 15/173: using an interconnection network, e.g. matrix, shuffle, pyramid, star, snowflake
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Computer systems and methods using efficient module and backplane tiling to interconnect computer nodes via a Kautz-like digraph. A multinode computing system includes a large plurality of computing nodes interconnected via a Kautz topology having order O, diameter n, and degree k. The order equals (k+1)kn−1. The interconnections from a node x to a node y in the topology satisfy the relationship y=(−x*k−j) mod O, where 1≦j≦k, and the computing nodes are arranged onto a plurality of modules. Each module has an equal plurality of computing nodes on it. A majority of the inter-node connections are contained on the plurality of modules and a minority of the inter-node connections are inter-module connections. Inter-module connections are routed among modules in parallel on an inter-module connection plane.

## Claims

### Claim 1

A multinode computing system, comprising:
a large plurality of computing nodes interconnected via a Kautz topology having order O, diameter n, and degree k;
wherein the order=(k+1)kn−1;
wherein the interconnections from a node x to a node y in the topology satisfies the relationship y=(−x*k−j) mod O, where 1≦j≦k; and
wherein the computing nodes are arranged onto a plurality of modules each module having an equal plurality of computing nodes thereon.

### Claim 2 (depends on 1)

The system of claim 1 wherein a majority of the inter-node connections are contained on the plurality of modules and a minority of the inter-node connections are inter-module connections.

### Claim 3 (depends on 1)

The system of claim 1 wherein the amount of inter-node connections contained on the plurality of modules is a substantially optimal amount.

### Claim 4 (depends on 1)

The system of claim 1 wherein a subset of the inter-node connections are inter-module connections and the subset are routed among modules in parallel on an inter-module connection plane.

### Claim 5

A multinode computing system, comprising:
a large plurality of computing nodes interconnected via a Kautz topology having order O, diameter n, and degree k;
wherein the order=(k+1)kn−1;
wherein the interconnections from a node x to a node y in the topology satisfies the relationship y=(−x*k−j) mod O, where 1≦j≦k; and
wherein the computing nodes are arranged onto a plurality of modules;
wherein each module has km nodes, and each node on the module can be assigned a label d1 . . . dmεZkm such that inter-node connections that are intra-module correspond to a subset of the edges (d1 . . . dm, d2 . . . dm+1) of a de Bruijn graph of diameter m and degree k, subject to the condition that there are no directed closed loops formed from the inter-node connections on a module.

### Claim 6 (depends on 5)

The system of claim 5 wherein the number of intra-module connections is substantially optimal.

### Claim 7 (depends on 5)

The system of claim 5 wherein the di's are expressed as a function of the node labels s0 . . . sn of the Kautz graph through
di=f(ci+n−m,ci)
wherein f(x,y) is a function which for fixed X acts a permutation on Zk through y→f (X,y) and which for fixed Y acts as a permutation on Zk through x→f(x,Y) and where ci's encode the Kautz coordinates si through
ci=si−si−1−1 mod(k+1)

### Claim 8 (depends on 7)

The system of claim 7 wherein f(x,y) equals x+y mod k.

### Claim 9 (depends on 7)

The system of claim 7 wherein f(x,y) equals x−y mod k.

### Claim 10 (depends on 5)

The system of claim 5 wherein each module is degree 3 and contains 27 computing nodes.

### Claim 11 (depends on 5)

The system of claim 5 wherein a subset of the inter-node connections are inter-module connections and the subset are routed among modules in parallel on an inter-module connection plane.

### Claim 12

A multinode computing system, comprising:
a large plurality of computing nodes interconnected via a de Bruijn topology having order O, diameter n, and degree k;
wherein the order O=kn;
wherein the interconnections from a node x to a node y in the topology satisfies the relationship y=(x*k+j) mod O, where 0≦j≦k−1; and
wherein the computing nodes are arranged onto a plurality of modules each module having an equal plurality of computing nodes thereon.
