Multi-chip device partitioning process
AssigneeInternational Business Machines Corporation
InventorsDavid Shing-Ki Kung, Lakshmi Narasimha Reddy
Life of this patent
Estimating the term…
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.
Claims9
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:
- 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.
Dependencies are inferred from the claim text.