# US 2006/0049468 A1 · Interconnection architecture and method of assessing interconnection architecture

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

- Number: US 2006/0049468 A1
- Document ID: US20060049468A1
- Status: Published application
- Kind: A1
- Application number: 10/526,523
- Filed: 2003-09-09
- Published: 2006-03-09
- Earliest claimed: 2002-09-10
- Assignees: The Regents of the University of California
- Inventors: Chung-Kuan Cheng; Honggy Chen; Bo Yao; Ronald Graham; Esther Cheng; Feng Zhou
- Web page: https://patentgrep.com/patent/US20060049468A1

## CPC

- G06F 30/394: Routing (G06F30/396 takes precedence)
- G06F 15/8023: {Two dimensional arrays, e.g. mesh, torus}
- H10D 89/00: Aspects of integrated devices not covered by groups H10D84/00 - H10D88/00
- H10W 20/43: Layouts of interconnections
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H10D: INORGANIC ELECTRIC SEMICONDUCTOR DEVICES
- H10W: GENERIC PACKAGES, INTERCONNECTIONS, CONNECTORS OR OTHER CONSTRUCTIONAL DETAILS OF DEVICES COVERED BY CLASS H10

## Abstract

A multi-celled chip. The chip includes a plurality of hexagonal cells arranged in an array. A plurality of interconnects including Y's connect the cells in clusters of three cells each, so that each of the cells is interconnected.

## Claims

### Claim 1

A chip comprising:
an array of hexagonal cells;
a plurality of interconnects including Y's connecting the cells in clusters of three cells each wherein the cells in the clusters are interconnected.

### Claim 2 (depends on 1)

The chip of claim 1 wherein the Y connecting each cluster has a node and three interconnects connecting the node to respective ones of the cells within a cluster;
wherein each Y connects each cell of its respective cell group to the node.

### Claim 3 (depends on 2)

The chip of claim 2 wherein the plurality of interconnects are formed on a plurality of levels, wherein nodes of Y's connecting clusters of a lower level are interconnected by Y's of a higher level;

### Claim 4 (depends on 3)

The chip of claim 3 wherein each of the Y's on a particular level is oriented in a direction that is rotated by 90° from the Y's on a next lower level and is rotated by 90° from the Y's on a next higher level.

### Claim 5 (depends on 1)

The chip of claim 1 wherein the chip has a shape of a convex polygon having at least five sides.

### Claim 6 (depends on 5)

The chip of claim 5 wherein the polygon is symmetrical to directions of the interconnect.

### Claim 7 (depends on 1)

The chip of claim 1 wherein each of the clusters comprises three cells arranged and routed in three symmetrical directions.

### Claim 8 (depends on 7)

The chip of claim 7 wherein the cells of each cluster are arranged and routed at directions of 0°, 60°, and 120° with respect to the node.

### Claim 9

A chip comprising:
a plurality of circuit elements disposed on a layer;
a hierarchical, nonblocking interconnection architecture connecting the plurality of circuit elements;
wherein the interconnection includes a plurality of interconnects joining clusters of the circuit elements, and wherein the plurality of interconnects form a mesh that is symmetrical with respect to directions of the interconnects.

### Claim 10 (depends on 9)

The chip of claim 9 wherein the array has a non-rectilinear structure.

### Claim 11

A method of selecting a nonblocking routing architecture including a plurality of interconnects interconnecting a plurality of cells, the method comprising:
determining a length L of each of the plurality of interconnects in each of a plurality of the routing architectures;
determining a shortest route length D along the plurality of wires between each pair of cells in the plurality of cells for each of the plurality of interconnects in each of a plurality of the routing architectures;
multiplying L×D to determine a cost M for each of the plurality of interconnects in each of a plurality of the routing architectures;
selecting one of the plurality of architectures having the smallest M.

### Claim 12 (depends on 11)

The method of claim 11 further comprising:
determining a derivative benefit for each of the plurality of routing architectures, where the derivative benefit is
I
=
-
Δ
⁢
⁢
D
Δ
⁢
⁢
L
,
where ΔD represents the change of D and ΔL represents the change of L;
selecting one of the plurality of architectures having a maximum derivative benefit.

### Claim 13 (depends on 11)

The method of claim 11 wherein
L=Σ length of each wire; and wherein
D
=
∑
1
≤
i
<
j
<
≤
P
⁢
d
i
,
j
for all values i and j where di,j is a shortest route length between a node i and a node j.

### Claim 14

A method of adding an interconnect to a plurality of cells in a chip, the plurality of cells being connected by a hierarchical architecture, the method comprising:
selecting a location between a pair of adjacent cells wherein the pair of adjacent cells is connected to each other only at a root of the hierarchical architecture;
forming a bridge between the pair of adjacent cells at the selected location.

### Claim 15 (depends on 14)

The method of claim 14 wherein the bridge is arranged to be a shortest Euclidean distance connection between the pair of adjacent cells.

### Claim 16

A multicell chip comprising:
an interconnection architectures, the interconnection architecture comprising a plurality of interconnects interconnecting a plurality of cells, the interconnects having a tree structure;
the plurality of cells including a pair of physically adjacent cells having a single lowest common ancestor;
the interconnection architecture further comprising a bridge connecting the pair of adjacent cells and providing a direct connection between the adjacent cells.

### Claim 17

A multicell chip comprising:
an array of cells;
a plurality of interconnects interconnecting the array of cells, the plurality of interconnects being arranged in k hierarchical layers, adjacent hierarchical layers comprising interconnects in respectively different directions;
n-k layers comprising a connection path for providing a signal to the k hierarchical layers;
at least one via extending from the n-k layers and through at least one of the k layers;
the k hierarchical layers further comprising at least one tunnel for detouring one of the interconnects on a hierarchical layer around the via, the at least one tunnel including a detouring wire on a hierarchical layer connected to the interconnect to complete a signal path.

### Claim 18 (depends on 17)

The multicell array of claim 17 further comprising:
a bank of tunnels for detouring around a plurality of vias, each of the tunnels of the bank being arranged in a similar pattern and each of the tunnels including detouring interconnects routed in a hierarchical layer different from the layer of the interconnects connected to the tunnel, the detouring interconnects forming a complete signal path with the interconnects.

### Claim 19 (depends on 4)

The chip of claim 4 wherein all cells are interconnected to other cells.

### Claim 20 (depends on 10)

The chip of claim 10 wherein the chip has a hexagonal shape.

### Claim 21 (depends on 16)

The chip of claim 16 wherein the interconnection architecture comprises an X-architecture having a root at n level, and wherein the bridge connects nodes at a level n−2.

### Claim 22 (depends on 16)

The chip of claim 16 wherein the interconnection architecture comprises a H-architecture having a root at n level, and wherein the bridge connects nodes at a level n−3.

### Claim 23 (depends on 16)

The chip of claim 16 wherein the interconnection architecture comprises a Y-architecture having a root at n level, and wherein the bridge connects nodes at a level n−2.
