Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Time-Driven CMOS Gate Placement

IP.com Disclosure Number: IPCOM000100917D
Original Publication Date: 1990-Jun-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 2 page(s) / 72K

Publishing Venue

IBM

Related People

Luijten, R: AUTHOR

Abstract

The physical design for chips consists of two phases: placement and wiring. The invention described here presents a new method for placement which takes timing information from the logic design into account for placement. Up to now only connectivity and sometimes critical nets have been a driving factor for placement algorithms, resulting in less optimal placement. This has put an extra burden on the wiring algorithms.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Time-Driven CMOS Gate Placement

       The physical design for chips consists of two phases:
placement and wiring.  The invention described here presents a new
method for placement which takes timing information from the logic
design into account for placement.  Up to now only connectivity and
sometimes critical nets have been a driving factor for placement
algorithms, resulting in less optimal placement.  This has put an
extra burden on the wiring algorithms.

      In the following, "critical path" means a chain of gates and
nets with timing constraints, and "disjoint paths" means paths that
contain gates which are not contained in other paths.

      The algorithm described below applies to CMOS circuits in which
the added delay per gate is a function of the fixed gate delay plus
the delay caused by the capacitive load on the gate output.  This
capacitive delay consists of a fixed-part due to input capacity of
the destination gates and capacitance that is a constant factor times
the wire length.

      Following are the steps taken in the new placement algorithm:
1.   Find all critical paths in the logic design. Relinquish time as
critical parameter until all gates in design are contained in at
least one path.
2.   Combine all critical paths into disjoint sets of critical paths.
3.   Grow those sets by adding all other paths in, relinquishing time
as a critical parameter.
4.   Within one set of paths, take the most critical path from this
set and place the gates as far apart on a virtual grid as the added
delay from the manhattan distance allows.  The gates are placed
equally spaced on a straight line if the critical path does not end
in the same place where it started; otherwise, the path is formed in
a circle.  All gates to which a gate in the critical path fans out
are placed....