×

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
First Claim
Patent Images

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.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×