BDD-based Logic Synthesis with Applcations to mixed CMOS/PTL Circuits
      ---------------------------------------------------------------------

                        Maciej Ciesielski
         Department of Electrical & Computer Engineering
                University of Massachusetts, Amherst
        http://www.ecs.umass.edu/ece/labs/vlsicad/ciesielski.html
                        ciesiel@ecs.umass.edu


There are two major approaches to the synthesis of logic circuits.
One is based on a predominantly algebraic factorization leading to an
AND/OR logic decomposition and optimization. The other one is based on a
classical Reed-Muller decomposition and its related decision diagrams;
it has been shown to be efficient for XOR-intensive arithmetic functions.
Both approaches share the same weakness: while one is strong at one class 
of functions, it is weak at the other.

This talk will present a new BDD-based logic optimization method which 
proves very efficient at handling both AND/OR- and XOR-intensive functions.
The method is based on an iterative BDD decomposition using various BDD 
structures, called dominators. Detailed analysis of those structures and the 
explanation how they lead to efficient AND/OR, XOR and MUX decompositions,
will be presented. Our synthesis results for AND/OR-intensive functions are 
comparable to those of SIS, while computed within a significantly shorter 
CPU time. On the other hand, the results for XOR-intensive functions are 
comparable to those obtained with techniques targeting specifically XOR 
decomposition. By the nature of the decomposition and the availability of
XOR and MUX structures, the method is directly applicable to pass transistor 
logic (PTL), and can be used for synthesis of mixed CMOS/PTL circuits.

Finally, an overview of a complete BDD-based logic synthesis system, BDS,
will be given. BDS supports both algebraic and Boolean factorization and
uses new techniques crucial to the manipulation of BDDs in a partitioned
Boolean network environment.
The experimental results show that BDS has capability to handle very large 
circuits. Overall, it offers a superior runtime advantage over SIS, with 
comparable results in terms of circuit area and often improved delay.


	---------------   Bio ------------------------

Maciej Ciesielski received his M.S. in Electrical Engineering from 
Warsaw Technical University in 1974, and Ph.D. in Electrical 
Engineering from the University of Rochester in 1983.

From 1983 to 1986 he worked at GTE Laboratories, Waltham, MA, 
on SILC silicon compilation project.
Currently he is Associate Professor in the Department of Electrical &
Computer Engineering at the University of Massachusetts, Amherst.

He has been performing research in the area of CAD for VLSI systems 
and circuit. His specific research interests include:
logic synthesis and optimization from behavioral and logic specifications;
design validation and verification; VLSI layout synthesis; 
performance optimization of IC's; and algorithms and mathematical optimization
methods. He is a senior member of the IEEE, Circuits and Systems Society.


-----------------------------------------------------------------------------
Maciej Ciesielski, Associate Professor          ciesiel@ecs.umass.edu
ECE Dept,   KEB 209 B                           phone: (413) 545-0401
University of Massachusetts                     fax:   (413) 545-1993
Amherst, MA 01003-4410
        http://www.ecs.umass.edu/ece/labs/vlsicad/ciesielski.html
-----------------------------------------------------------------------------