Alan Mishchenko's Homepage - SOP Minimization

Two Level Sum-of-Product Minimization

RONDO is a new minimizer for the Sum-of-Product (SOP) representation of multi-output incompletely-specified Boolean functions developed by Alan Mishchenko at Portland State University. RONDO follows the implicit paradigm for exact SOP minimization established by O. Coudert [1]. This paradigm relies on decision diagrams (BDDs and ZDDs) for efficient processing of Boolean functions and cube covers. For large test cases, RONDO can be significantly faster than ESPRESSO [2,3].

Here is an experimental evaluation of Rondo vs. ESPRESSO for those test cases, which take more than 3 sec of ESPRESSO runtime.

The current version of RONDO implements the following algorithms and minimization steps:

Fast implicit computation of the Irredundant Sum-of-Products [4,5,6].
Transformation of a multi-output SOP minimization problem into a single-output one [1].
Implicit reduction of the covering matrix and computation of essential cubes [1].
Finding the minimum-literal prime cover of the essential cubes [1].
An exact explicit solution of the cyclic core using MINCOV package borrowed from SIS [7].
A fast heuristic solution of the cyclic core using implicit representation.

A Windows executable of RONDO is available. Run the executable without command line arguments to get the summary of minimization options.
Judging by the experimental results, RONDO can efficiently perform exact SOP minimization for functions with very large sets of prime implicants (up to 50,000) as long as (1) the cyclic core after the covering matrix reduction step is relatively small (say, less than 1000 rows by 1000 columns) and (2) the size of implicit representation of functions and cube sets is managable (say, less than 50,000 DD nodes). Some benchmark functions and random functions do not have compact DD representation and/or small cyclic cores. For these functions, the exact SOP minimization as currently implemented in RONDO is not practical.

The future work in SOP minimization includes:

Development of an efficient heuristic minimization procedure based on implicit representation

Computation of the essential primes without generation of all primes
Efficient implicit counterparts of REDUCE, EXPAND, IRREDUNDANT, and LAST_GASP implemented in ESPRESSO [2,3]

Integration of the improvement to the solutions of large unate covering problems [8,9]

References:

[1] O. Coudert. Two-Level Logic Minimization: An Overview. Integration. Vol. 17, No. 2, pp. 97-140, October 1994.
[2] R.K.Brayton, G.D.Hachtel, C.T.McMullen, A.L.Sangiovanni-Vincentelli. Logic Minimization Algorithms for VLSI Synthesis. Kluwer Academic Publishers, Dordrecht, 1984.
[3] R. Rudell, A. Sangiovanni-Vincentelli. Multiple-Valued Minimization for PLA Optimization. IEEE Trans. on CAD. Vol. CAD-6, No. 5, September 1987, pp. 727-750.
[4] E. Morreale. Recursive Operators for Prime Implicant and Irredundant Normal Form Determination. IEEE Trans. Comp., C-19(6), 1970, pp. 504-509.
[5] S. Minato. Fast Generation of Irredundant Sum-of-Product Forms from Binary Decision Diagrams. Proc. of SASIMI'92 (Synthesis And SImulation Meeting and International Interchange), pp. 64-73, April 1992.
[6] O. Coudert, J. C. Madre, H. Fraisse, H. Touati. Implicit Prime Cover Computation: An Overview. Proc. of SASIMI'93 (Synthesis And SImulation Meeting and International Interchange), Nara, Japan, October 1993.
[7] SIS source code.
[8] O. Coudert, J. C. Madre. New Ideas for Solving Covering Problems, Proc. of 32nd DAC, San Francisco CA, June 1995.
[9] E.I. Goldberg, L.P. Carloni, T. Villa, R. K. Brayton, A.L. Sangiovanni-Vincentelli. Negative Thinking in Branch-and-Bound: the Case of Unate Covering. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 19, No. 3, March 2000.

Alan Mishchenko's Home Page

This page has been last modified on May 10, 2001.