Multi-chip device partitioning process

• US 5,675,500 A
• Filed: 10/18/1994
• Issued: 10/07/1997
• Est. Priority Date: 10/18/1994
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kung, David Shing-Ki, Reddy, Lakshmi Narasimha
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): PHAN, THAI Q
• Application Number:
  US08/324,847
• Time in Patent Office: 1,085 Days
• Field of Search: 364/489, 364/490, 364/491, 364/488
• US Class Current: 716/125
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

An efficient method for partitioning, for example, FPGA devices is described which optimizes the number of devices required to implement a design. The method involves generating a hierarchical graph of a feasible bipartition of the cells of the design. Feasible pairs are merged, followed by flattening of the hierarchical graph. The number of I/O pins of the new partition is then reduced, upon which a hierarchical graph is derived. A perturbed partition is then generated, followed by restoration of feasibility.

Claims

1. A method for constructing an integrated circuit with a near optimum number of devices, the circuit comprising a plurality of cells, the method comprising the computer implemented steps of:

(a) iteratively bi-partitioning the design to generate an initial feasible partition of the cells of the design;

(b) generating a hierarchical graph of the initial partition;

(c) pair-wise merging feasible segments of the hierarchical graph;

(d) flattening the hierarchical graph after the merging;

(e) generating a new partition with a reduced number of I/O pins;

(f) creating a new hierarchical graph based upon the partition in (e);

(g) recording the partitioning state of the hierarchical graph;

(h) forming a perturbed partition by merging a perturbed segment of the hierarchical graph with one or more other segments of the hierarchical graph;

(i) relaxing the perturbed partition to make it feasible by moving cells between segments in descending order of a cost function, wherein the cost function is defined as;

space="preserve" listing-type="equation">C=k*U*q(v,i,j)+g(v,i,j)

where C is the cost, K is a constant controlling priority given to moves that reduce I/O pins of the perturbed segment versus moves that reduce global I/O pins, U is an upper bound of the change in the number of I/O pins of the perturbed partition for each move, q(v,i,j) is the number of I/O pins reduced from a perturbed segment p if cell v is moved from segment i to segment j if either i=p or j=p and is zero otherwise, and g(v,i,j) is the number of I/O pins reduced in the entire partition if node v is moved from segment i to segment j;

(j) repeating steps (g)-(i) until optimized;

(k) constructing the circuit with devices partitioned in accordance with the foregoing steps.

2. The method of claim 1, wherein the iterative partitioning is performed using the Fiduccia-Mattheyses technique.

3. The method of claim 1, wherein the number of I/O pins is reduced using the Fiduccia-Mattheyses technique.

4. The method of claim 1, wherein the devices are field programmable gate arrays (FPGA).

5. The method of claim 4, wherein the FPGA'"'"'s each have a like cell limit and a like input-output pin limit.

6. The method of claim 1, wherein the step of restoring feasibility comprises:

flattening the hierarchical graph that represents the perturbed partition;

determining a cost for each possible move of a node from one segment to another segment, wherein the cost reflects a change in the number of device pins reduced from the perturbed segment and the number of device pins reduced in the entire partition;

repeatedly moving nodes from one segment to another in descending order of cost to reduce the number of device pins to a feasible level until no more moves can be accomplished.

7. The method of claim 1, wherein the step of merging cells in the new hierarchical graph to form a perturbed partition comprises:

determining from among all possible segment merges a merge which will result in a perturbed segment and which will maximize the I/O slack of the resulting partition.

8. The method of claim 1, wherein the perturbed partition comprises a single perturbed segment.

9. The method of claim 1, wherein the step of generating a new partition is accomplished using the Fidducia-Mattheyses technique.