06/01/1994 09:00 AM
Computer Engineering
This thesis explores logic minimization techniques for Boolean functions represented as if-then-else DAGs. In particular the thesis presents algorithms for two areas of multi-level logic minimization: Rectangle Covering and Variable Ordering. Rectangle covering is the process of factoring and extracting common sub-expressions in Boolean functions. Boolean functions are represented as Boolean matrices, and rectangles of these matrices represent either a factor of a function or a sub-expression that can be shared among several functions. An efficient heuristic algorithm two- column rectangle replacement for finding rectangles of a Boolean matrix is presented. The heuristic is particular well suited for optimizing circuits for area, while controlling the delay. A slight variation of the heuristic optimizes with respect to delay. Variable ordering is a problem specific to canonical if-then-else DAGs and ordered binary decision diagrams. This thesis presents an improved depth-first ordering heuristic based on reconvergent fanout. This heuristic is fast and produces variable orders resulting in smaller canonical forms than previously published traversal-based ordering heuristics, and is suitable when using canonical form for verification purposes. The thesis also presents a new ordering heuristic called {\\em SplitOrder}, which is especially well suited for finding good variable orders for ordered binary decision diagrams (OBDDs). SplitOrder constructs the variable order by building an OBDD top-down one level at a time, choosing the next variable such that the corresponding level in the OBDD has few nodes and represents expressions that are as small as possible. SplitOrder is compared to several depth-first ordering heuristics and show that when converting to OBDDs SplitOrder averages 25% fewer nodes than taking the best of 8 depth-first techniques (37% better than the best single depth-first technique). Finally it is demonstrated that applying SplitOrder to a set of expressions already represented as an OBDD often results in significantly better variable orders, thus making it beneficial to iterate SplitOrder. All of the algorithms presented in this thesis have been implemented, tested, and installed as part of the logic minimizer ITEM. Notes: Ph.D. Thesis
