October 16, 1999
 Contact email: {abk,caldwell,imarkov}@cs.ucla.edu

         Two Placement and Routing Datamodels: Variable Die vs Fixed Die 

 Standard-cell row-based placement and routing can be performed in two
 major ways: variable-die or fixed-die.    Variable-die methodology dates
 back to 2-layer metal (2-LM) processes.   Fixed-die methodology is the
 modern standard, and is appropriate to N-layer metal (N-LM) processes,
 N >= 3.   Details of the two approaches are as follows.

 Variable-die:  Inter-row spacings (and possibly row lengths) are not fixed
 -------------  a priori, but rather are determined during placement 
                and routing.  In particular, congestion is relieved by 
                spreading rows (increasing the number of tracks between 
                consecutive rows).    Channel routers are typically used 
                with the variable-die approach.    Issues such as "feedthrough
                insertion" appear in relevant literature, because of the
                2-LM standard-cell heritage.

 Fixed-die:     The number/geometry of cell sites in cell rows are fixed before 
 ----------     placement.    In particular, all inter-row spacings are fixed.
                The fixed-die approach has its heritage from gate-array
                methodology.   Area routers are typically used.  (Routability
                thus becomes paramount:   (i) congestion analysis and
                hot-spot removal, and (ii) floorplan (site map) optimization
                such as VSize or DSO, become key parts of the P&R strategy.)
                The use of fixed-die approaches is driven by (hierarchical)
                design methodology: the presence of macros, a fixed floorplan,
                and fixed power and clock distribution networks together
                make the variable-die approach less relevant today.
                Fixed-die is also driven by the process:  with N-LM processes
                blocks have high site utilization (<1% of "whitespace" is 
                not uncommon);  the use of "double-back" (shared power/ground
                rail) cell row architecture also fixes the row pitch.


 Fixed-Die vs. Variable-Die Data Models 
 --------------------------------------
 LEF/DEF formats from Cadence Design Systems, Inc.
 are based on the fixed-die data model.   Hence, all 
 P&R tools that natively work with LEF/DEF follow the
 fixed-die data model.

 One variable-die placer is distributed by InternetCad 
 (formerly TimberWolf).   While academic literature has used
 TimberWolf for comparison, the market share for variable-die
 placement does not appear large.    (A recent market survey
 by a noted EDA consulting firm does not list the tool under
 P&R options.)  To our knowledge, all startup efforts as well
 as P&R offerings from the major vendors (Cadence, Avant!, 
 Mentor, Synopsys) are using the fixed-die model for standard-cell
 blocks. 
 
 Comparisons of placement results for fixed-die placers versus
 variable-die are not straightforward and should, at minimum,
 take the die size into the account.

----------------------------------------------------------------------
 Subject: iTools discussion, etc.
    Date: Wed, 20 Oct 1999 16:17:27 -0700
    From: abk@nexus.cs.ucla.edu (Andrew B. Kahng)
      To: caldwell@CS.UCLA.EDU, imarkov@CS.UCLA.EDU, pmadden@cs.binghamton.edu
      CC: abk@nexus.cs.ucla.edu

I just talked to Bill Swartz for about 40 minutes, and have
thought about possible "fair" methods for comparing against
TWolf placements.

Here is where I am at the moment.  I use "TW" == iCAD/iTools/etc.

0.  Old Munich group comparisons w/TW set inter-row spacing = 
    cell height (e.g., 15-grid high cell rows would be on a
    30-grid pitch).  This is irrelevant today.
1.  TW measures WL as HPWL before routing. It uses actual
    port locations (closest port when a logical pin has multiple
    physical ports).
2.  Bill says that TW global placement today has four modes, none 
    of which maps well to fixed-die. The standard mode will shove 
    all cells to the left without any feedthroughs.  This is not
    necessarily a routable placement or even a legal placement
    (it may have overlaps in at least one mode).  It has 
    essentially no whitespace.  We could pass the site plan
    to a fixed-die placer but it is not clear what this means.
    On the plus side, the TW global placer has pure min-WL as
    its objective, so that would be fair to compare against.
2'. Bill says that fundamentally there is no way to compare
    a fixed-die placer to a variable-die placer !!!
3.  TW global routing has the ability to change cell row spacing,
    insert feedthroughs, and change cell placements/sizings.
    but its result is not necessarily routable either.  Also,
    its objective is no longer pure "minimum wirelength", so 
    saving this perturbed placement as a site map, then running
    a fixed-die placer, is not *too* meaningful either.
4.  I understand that Patrick has run TW and collected some
    placements, from which he preserves site maps and generates
    a Bookshelf format fixed-die instance.
    - there are feedthroughs, which means the placements were
      collected after TW global (+detailed?) routing???
    - we could run fixed-die placers on the site map to minimize HPWL.   
    - this is "unfair" to TW because:
      - our placements are not necessarily routable, while TW's are
      - we are minimizing HPWL, while TW's router-driven placement
        changes were no longer minimizing HPWL.
    - given this "unfairness", if TW's HPWL is still less than
      our HPWL's, this is a meaningful indicator (IMO) that TW
      is superior in terms of placement quality.


-- Andrew