# US 2006/0156265 A1 · Method and system to redistribute white space for minimizing wire length

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

- Number: US 2006/0156265 A1
- Document ID: US20060156265A1
- Status: Published application
- Kind: A1
- Application number: 11/034,098
- Filed: 2005-01-12
- Published: 2006-07-13
- Earliest claimed: 2005-01-12
- Assignees: International Business Machines Corporation
- Inventors: Xiaoping Tang
- Web page: https://patentgrep.com/patent/US20060156265A1

## CPC

- G06F 30/392: Floor-planning or layout, e.g. partitioning or placement
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Disclosed are a method and a system for redistributing white space on an integrated circuit. The method comprises the steps of providing a series of circuit blocks for the integrated circuit, and placing the blocks on the integrated circuit to obtain a predefined optimal wire length. In accordance with the preferred embodiment of the invention, we first show that the problem of placing the blocks to obtain an optimal wire length, can be formulated as linear programming. Then, we find it can be solved by efficient min-cost flow implementation instead of general and slow linear programming. The approach guarantees to obtain the minimum total wire length for a given floorplan topology. We also show that the approach is capable of handling various constraints such as fixed-frame (fixed area), IO pins, pre-placed blocks, boundary blocks, range placement, alignment and abutment, rectilinear blocks, cluster placement, and bounded net delay, without loss of optimality.

## Claims

### Claim 1

A method of redistributing white space on an integrated circuit, comprising the steps of:
providing a series of circuit blocks for the integrated circuit; and
placing the circuit blocks on the integrated circuit to obtain a predefined optimal wire length.

### Claim 2 (depends on 1)

A method according to claim 1, wherein the placing step includes the step of using a linear programming procedure to determine where to place the blocks on the integrated circuit.

### Claim 3 (depends on 2)

A method according to claim 2, wherein the using step includes the step of using a min-cost flow based approach to determine where to place the blocks on the integrated circuit.

### Claim 4 (depends on 1)

A method according to claim 1, wherein said predefined optimal wire length is the minimum total wire length in polynomial time for a given floorplan topology.

### Claim 5 (depends on 1)

A method according to claim 1, wherein:
the placing step includes the step of placing the circuit blocks on the integrated circuit subject to a given set of constraints; and
the given set of constraints include one or more of the following: fixed area, IO pins, pre-placed blocks, boundary blocks, range placement, alignment and abutment, rectilinear blocks, cluster placement, and bounded net delay.

### Claim 6 (depends on 1)

A method according to claim 1, wherein:
the floorplan is represented as a sequence pair; and
the sequence pair is a pair of sequences of n elements representing a list of n blocks, and the pair of sequences specifies the geometric relations between each pair of n blocks.

### Claim 7 (depends on 1)

A method according to claim 1, wherein the placing step includes the step of deriving a constraint graph from a representation of the floorplan.

### Claim 8 (depends on 1)

A method according to claim 1, wherein the placing step includes the steps of:
constructing a pair of network graphs GH and GV;
applying a min-cost flow algorithm on GH and GV;
deriving residual graphs of GH and GV; and
applying a shortest path algorithm on the residual graphs to compute the positions of the blocks.

### Claim 9

A system for redistributing white space on an integrated circuit, comprising the steps of:
a series of circuit blocks for the integrated circuit; and
means for determining where to place the circuit blocks on the integrated circuit to obtain a predefined optimal wire length.

### Claim 10 (depends on 9)

A system according to claim 9, wherein the means for determining includes means for using a linear programming procedure and a min-cost flow based approach to determine where to place the blocks on the integrated circuit.

### Claim 11 (depends on 9)

A system according to claim 9, wherein:
the placing step includes the step of placing the circuit blocks on the integrated circuit subject to a given set of constraints; and
the given set of constraints include one or more of the following: fixed area, IO pins, pre-placed blocks, boundary blocks, range placement, alignment and abutment, rectilinear blocks, cluster placement, and bounded net delay.

### Claim 12 (depends on 1)

A system according to claim 1, wherein:
the floorplan is represented as a sequence pair; and
the sequence pair is a pair of sequences of n elements representing a list of n blocks, and the pair of sequences specify the geometric relations between each pair of n blocks.

### Claim 13 (depends on 9)

A system according to claim 9, wherein the means for determining includes:
means for constructing a pair of network graphs GH and GV;
means for applying a min-cost flow algorithm on GH and GV;
means for deriving residual graphs of GH and GV; and
means for applying a shortest path algorithm on the residual graphs to compute the positions of the blocks.

### Claim 14

A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for redistributing white space on an integrated circuit, the method steps comprising:
providing a series of circuit blocks for the integrated circuit; and
placing the circuit blocks on the integrated circuit to obtain a predefined optimal wire length.

### Claim 15 (depends on 14)

A program storage device according to claim 14, wherein the placing step includes the step of using a linear programming procedure and a min-cost flow based approach to determine where to place the blocks on the integrated circuit.

### Claim 16 (depends on 14)

A program according to claim 14, wherein:
the placing step includes the step of placing the circuit blocks on the integrated circuit subject to a given set of constraints; and
the given set of constraints include one or more of the following: fixed area, IO pins, pre-placed blocks, boundary blocks, range placement, alignment and abutment, rectilinear blocks, cluster placement, and bounded net delay.

### Claim 17 (depends on 14)

A program storage device according to claim 14, wherein:
the floorplan is represented as a sequence pair; and
the sequence pair is a pair of sequences of n elements representing a list of n blocks, and the pair of sequences specify the geometric relations between each pair of n blocks.

### Claim 18 (depends on 14)

A program storage device according to claim 14, wherein the placing step includes the steps of:
constructing a pair of network graphs GH and GV;
applying a min-cost flow algorithm on GH and GV;
deriving residual graphs of GH and GV; and
applying a shortest path algorithm on the residual graphs to compute the positions of the blocks.
