Browse Prior Art Database

Partitioning Logic On to Graph Structures

IP.com Disclosure Number: IPCOM000100148D
Original Publication Date: 1990-Feb-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 7 page(s) / 278K

Publishing Venue

IBM

Related People

Vijayan, G: AUTHOR

Abstract

This disclosure concerns the problem of partitioning logic (i.e., a hypergraph) on to the vertices of a partition graph G, in which the cost function to be minimized is the cost of global routing, namely, the cost of routing the nets of the logic on the edges of the graph G. We refer to this as the Min-Cost Partitioning on a Graph (MCPG) problem.

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

Partitioning Logic On to Graph Structures

       This disclosure concerns the problem of partitioning
logic (i.e., a hypergraph) on to the vertices of a partition graph G,
in which the cost function to be minimized is the cost of global
routing, namely, the cost of routing the nets of the logic on the
edges of the graph G.  We refer to this as the Min-Cost Partitioning
on a Graph (MCPG) problem.

      Using the MCPG model, logic can be partitioned on to any
arbitrary graph structure.  For example, the 2x2 grid used in the
quadrisection approach can be extended to a 3x3 grid.  Another
application is in the partitioning of residual logic after the
preplacement of certain predesigned blocks, such as RAMs.  In this
application, the partition graph is the planar dual of a rectangular
dissection of the residual area on the chip.  The MCPG model is very
general to be used in many other partitioning applications that arise
in VLSI physical design.

      One such application of the MCPG model is in a partitioning
after floorplanning approach.  In timing-critical VLSI designs, it is
desirable, and many times imperative, to influence the logic design
process using physical design constraints.  One such method is to do
early floorplanning using the functional blocks and their
connectivity before the synthesis of the logic within the functional
blocks.  The floorplan can then be used to drive the logic synthesis
process, so as to minimize delays on critical paths that traverse
across many blocks of the floorplan.  The synthesis of the functional
blocks actually gives an initial and rough partition of the logic on
to the blocks of the floorplan, which satisfies the timing
constraints.  The partition graph is the planar dual of floorplan.
Each edge of this partition graph has a capacity assigned to it,
which is the maximum number of nets that can cross the dual edge of
the floorplan.  Each edge may also have a weight, which may be
function of various parameters, such as capacity, length and
criticality.  It may be possible to improve this initial partition
with regard to global routing of the nets between the blocks, without
affecting the timing delays on the critical paths.  The MCPG model is
well suited to perform this task.

      Definitions and Problem Statement: We are given a logic network
(i.e., an hypergraph) L=(U,H), where U is the set of nodes of the
logic and H is the set of nets (i.e., hyperedges).  A net heH is a
subset of U.  We are also given a partition graph G=(V,E), where V is
the set of vertices and E is the set of edges. Throughout the
article, we use the term nodes for the logic network and the term
vertices for the partition graph. The following is a list of
parameters associated with the nodes, nets, vertices and edges.

                            (Image Omitted)

1.  For each node ueU, su denotes its size.
2.  For each vertex veV, Sv denotes its size, which is an upper b...