Browse Prior Art Database

Efficient Algorithm for Finding the Largest Rectangle Exactly

IP.com Disclosure Number: IPCOM000109416D
Original Publication Date: 1992-Aug-01
Included in the Prior Art Database: 2005-Mar-24

Publishing Venue

IBM

Related People

Malik, AA: AUTHOR

Abstract

Several problems in logic synthesis involve finding the largest rectangle of a matrix. An example of such a problem is common cube extraction. Another example is factoring of Boolean networks consisting of primitive gates. Due to its abstract nature, the largest rectangle problem is likely to find more applications in Logic Synthesis and other areas. Approximate methods have been used in the past for finding the largest rectangle. This article presents an exact algorithm and provides proof of its correctness. The algorithm has been implemented in our new logic synthesis system where it has been very useful for several logic minimization operations. Another algorithm for finding the largest rectangle is derived from the one for finding all kernels of a given sum of products.

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

Efficient Algorithm for Finding the Largest Rectangle Exactly

       Several problems in logic synthesis involve finding the
largest rectangle of a matrix.  An example of such a problem is
common cube extraction.  Another example is factoring of Boolean
networks consisting of primitive gates.  Due to its abstract nature,
the largest rectangle problem is likely to find more applications in
Logic Synthesis and other areas.  Approximate methods have been used
in the past for finding the largest rectangle.  This article presents
an exact algorithm and provides proof of its correctness.  The
algorithm has been implemented in our new logic  synthesis system
where it has been very useful for several logic minimization
operations.  Another algorithm for finding the largest rectangle is
derived from the one for finding all kernels of a given sum of
products.  The comparison with the kernel based algorithm
demonstrates that it is up to 1,000% slower than the efficient
algorithm for matrices encountered in our synthesis system during the
optimization of industrial logic networks.  The Achilles' heel matrix
for the kernel based algorithm is presented.  The kernel based
algorithm is 4,281% slower than the efficient algorithm for Achilles'
heel matrix of order 100.  Since the computation of the largest
rectangle is done extensively in our synthesis system, an efficient
algorithm is essential.
1. Introduction

      A rectangle of a matrix can be thought of as a submatrix that
consists only of nonzero entries.  The largest rectangle of a matrix
is the one with the largest number of entries.  Several optimization
problems in logic synthesis can use a matrix formulation with the
property that the largest rectangle of the matrix gives the optimum
solution.

      One such problem is called common cubes extraction (1).  Common
cube extraction is a part of MIS (2).  For an example of common cube
extraction, consider the sum of products expression f = ABCEF + ABDEF
ABDEF + ABCDE.  The expression can be rewritten as DE(ABF + C) +
ABCEF + ABCDE or as ABDF(C + E) + ABCEF + CDE.  Many representations
in the form cf1 + f2 are possible where c is the common cube (product
term); f1 and f2 are sums of products.  The objective is to obtain a
representation with the minimum number of literals.  The problem can
be transformed to that of finding the largest rectangle of a
matrix$M.  M has a row for each literal and a column for each product
term in f.  M(i,j) = 1 if literal i is present in product term j;
otherwise, M(i,j) = 0.  Once the largest rectangle of M is found, c
consists of literals corresponding to the rows in the largest
rectangle.  f1 consists of product terms corresponding to columns in
the largest rectangle with literals in c removed.  Finally, f2
consists of product terms corresponding to columns not in the largest
rectangle.  The minimum literal representation for f obtained from
the largest rectangle is ABF(CE + CD +...