Two-Level Exclusive Sum-of-Product Minimization

EXORCISM-4 is a fast heuristic ESOP minimizer developed by Alan Mishchenko. The new minimizer has been designed in the rich tradition of exact and heuristic ESOP minimization (EXORCISM-2 and EXORCISM-3) established by Prof. Marek Perkowski and his students at Portland State University [1,2,3].

EXORCISM-4 relies on a mixture of explicit and implicit techniques for the transformation of ESOP covers. The following algorithms have been integrated and fine-tuned to achieve the high performance minimization:

Implicit computation of the starting ESOP cover using an algorithm for exact minimization of Pseudo-Kronecker Reed-Muller expansions for symmetric functions, due to R. Drechsler [4].

ExorLink operation for distances 2, 3, and 4.

Improved look-ahead based on the heuristic "backtrack until the first success".

Efficient explicit representation of the ESOP cover using cube lists and cube pair queques.

• Improving branch-and-bound heuristics

After some experimentation with EXORCISM-4, a set of good heuristic rules has been found to make decisions about what cube pairs should be transformed first. It is obvious that these rules can be further improved to achieve better quality/runtime trade-off without redesigning the minimization framework.
 
• Development of an efficient heuristic minimization procedure based on implicit representation

Currently the most time consuming part of ESOP minimization consists in reshaping the cover using ExorLink operation in order to reduce the number of cubes. In the process, the cover is represented explicitly as a list of cubes encoded in the positional notation. It would be interesting to represent the cube cover by ZDDs. The first attempt to use ZDDs has failed because ExorLink operation requires considering cubes on the individual basis, which is incompatible with the implicit paradigm of processing many cubes at the same time. Introducing the implicit representation may require transformation of the ExorLink operation and changing the search strategy.
 
• Including the support of don't-cares

Currently, if an incompletely specified function is given for processing, EXORCISM-4 will minimize the on-set and disregard the dc-set.

[1] M. Helliwell, M. A. Perkowski. A Fast Algorithm to Minimize Multi-Output Mixed-Polarity Generalized Reed-Muller Forms. Proc. DAC’88. pp. 427-432.
[2] N. Song, M. Perkowski. EXORCISM-MV-2: Minimization of Exclusive Sum of Product Expressions for Multiple-Valued Input Incompletely Specified Functions. Proc. ISMVL 1993, pp. 132-137.
[3] N. Song, M. Perkowski. Minimization of Exclusive Sum of Products Expressions for Multi-Output Multiple-Valued Input, Incompletely Specified Functions. IEEE Trans. on CAD, Vol. 15, No. 4, April 1996, pp. 385-395.
[4] R. Drechsler. Pseudo-Kronecker Expressions for Symmetric Functions. IEEE Trans. Comp. Vol. 48. No. 8, Sept. 1999, pp. 987-990.
[5] A. Mishchenko, M. Perkowski. Fast Heuristic Minimization of Exclusive Sum-of-Products. Submitted to the 5th International Reed-Muller Workshop, August 2001, Starkville, Mississippi.