×

Method and system for placing cells using quadratic placement and a spanning tree model

  • US 5,818,729 A
  • Filed: 05/23/1996
  • Issued: 10/06/1998
  • Est. Priority Date: 05/23/1996
  • Status: Expired due to Term
First Claim
Patent Images

1. A computer controlled method for placing cells of an integrated circuit design represented as an unplaced netlist comprising the computer implemented steps of:

  • (a) generating first connectivity matrices for each net of said netlist utilizing clique models to represent spatial affinities for cells within each multi-pin net wherein said first connectivity matrices contain non-zero entries representing spatial affinities between cells of each net;

    (b) performing global quadratic optimization based placement on said design utilizing said first connectivity matrices to produce a rough placement of said cells of said netlist;

    (c) generating spanning tree connectivity relationships for multi-pin nets of said netlist by performing a spanning tree procedure on said multi-pin nets utilizing cell locations of said rough placement of said cells of said netlist;

    (d) generating second connectivity matrices for each multi-pin net of said netlist utilizing said spanning tree connectivity relationships wherein said second connectivity matrices contain non-zero entries representing spatial affinities between cells of each net; and

    (e) performing said global quadratic optimization based placement on said design utilizing said second connectivity matrices to produce a placed netlist.

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