Browse Prior Art Database

Method of Partitioning Data Path Macros into Multiple Stacks in Data Path VLSI Chips

IP.com Disclosure Number: IPCOM000109067D
Original Publication Date: 1992-Jul-01
Included in the Prior Art Database: 2005-Mar-23
Document File: 6 page(s) / 251K

Publishing Venue

IBM

Related People

Dean, AA: AUTHOR [+4]

Abstract

In high-density data-path chip designs, several stacks are often required to place and wire the macros and logic devices within the given chip area. The overall objective is to find partitions which have smallest total cost of wires crossing all the stack boundaries (smallest cut-cost) without violating the stack height requirements of each stack. A bit-stack consists of many functional elements, such as registers, adders, shifters, and buffers called data-path macros, which are made up of basic repeating "bit cells". These macros are stacked up vertically and wired almost exclusively with vertical wires.

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

Method of Partitioning Data Path Macros into Multiple Stacks in Data Path VLSI Chips

       In high-density data-path chip designs, several stacks
are often required to place and wire the macros and logic devices
within the given chip area.  The overall objective is to find
partitions which have smallest total cost of wires crossing all the
stack boundaries (smallest cut-cost) without violating the stack
height requirements of each stack.  A bit-stack consists of many
functional elements, such as registers, adders, shifters, and buffers
called data-path macros, which are made up of basic repeating "bit
cells".  These macros are stacked up vertically and wired almost
exclusively with vertical wires.

      Our approach is to find minimum cut-cost partitions of pairs of
stacks, with effective estimation of stack wires, stack height, and
the inclusion of stack height into the partitioning objective
function.  Both the data-path macros and other logic devices (random
logic) are taken into account during the partitioning.  We also show
that the minimization of global wire connections is directly related
to the minimization of overall chip area.  The same partitioning
procedure can be used to minimize the global data-bus traffic and/or
wire delay in critical timing-paths.
Stack Height Estimation

      Stack height is a function of the following four elements.
      1.   Data-path macro height - This is a constant for a given
macro in the data-path macro library.
      2.   Internal multi-bit nets - When an inter-macro connection
is required between two separate bits in the same stack, a horizontal
wiring track must be opened between macros to do the bit-crossing.
See Fig. 1.
      3.   Flush-through nets - When a stack is placed in the middle
part of the chip, the logic on either side of the stack communicates
via the horizontal wiring tracks through the middle stack.  Thus,
each flush-through wiring channel directly adds to the height of the
intervening stack being flushedthrough.  See Fig. 2.
      4.   External data nets - All stack data inputs and outputs are
serviced with horizontal wiring tracks.  For the stacks at the sides
of the chip, all data nets leave the stack on the same side and,
therefore, are a direct adder to the stack height.  On stacks located
in the middle regions of the chip, stack data I/Os can go either
left, right or both.  See Fig.  2.

      So the total stack height of a stack is the sum of these
components:
     stackHeight = SmacroHeight + flushThroughWire + k1 multiBitNet
leftRightDataNet + MAX(leftOnlyDataNet, rightOnlyDataNet) + k2
MIN(leftOnlyDataNet, rightOnlyDataNet)
where k1 and k2 are some constants between 0 and 1.  The net
connections that cross the stack boundaries are directly related to
the terms flushThroughWire, leftRightDataNet, leftOnlyDataNet and
rightOnlyDataNet, macroHeight is constant, and multiBit has only
secondary effect on stackHei...