XOR-basierte Logiksynthese

| project staff | project description | project software | publications |

Logic synthesis and verification are central components of computer-aided circuit design. Due to technological developments, particularly on the field of FPGAs, circuits which are constructed with additional help of EXORs, have gained in importance. At the same time data structures for boolean functions have been improved by using EXOR-based decompositions. The logic synthesis-subarea of the project will be illustrated more clearly in the following:

Logic synthesis deals with all tasks and problems which have to be managed in connection with an optimal realization of combinational and sequential logic resp. different cost functions.

Starting from an initial description, „classical“ logic synthesis provides an optimized two- or multi-level design of the circuit, which is based on the usage of logic gates, e.g. AND, OR, NOT. Hereby the optimization criteria is usually the used area. Potentials made possible through technological progress also have increased the demands on logic synthesis: First it is possible to realize more and more complex functions on one chip, which certainly should be able to be processed with the logic synthesis tool. Second also optimization intentions have changed and grown. Next to area also timing behaviour, power consumption and testability properties as optimization criteria have grown in importance.

FPGA-based (Field Programmable Gate Arrays) technologies for which EXOR-gates as basic gates can be viewed with the same delay times as standard gates are a mentionable example. This is a reason why logic synthesis, which has the objective to integrate EXOR-gates, has gained in importance and interest in theory as well as in practice. Furthermore at least for two-stage realizations of certain circuit-categories it is possible to show that AND/EXOR allows a more compact design than the use of AND/OR does. In addition two-level AND/EXOR-based realizations have (under certain conditions) good testability qualities. Despite these advantages there are still almost no tools, which make logicsynthesis possible nearly as efficient as the AND/OR-based synthesis when involving EXORs for circuits with “many” inputs. The common algorithms only work for a small number of inputs and usually are limited for two-stage designs.

Classic logic synthesis already requires the solution of NP-complete problems. For the requirements regarding quality and quantity, which were illustrated above, the efficiency of data structures and basic operations for the design and manipulation of the examined objects are of special importance. Here Ordered Binary Decision Diagrams (OBDDs) for the representation of boolean functions constantly gain in attention. They could be used in computer-aided logic synthesis very successfully. Advantages are the clarity of representation and the efficient realization of basic operations, e.g. equivalence test, tautology test, boolean AND(OR,…) of two OBDDs. These advantages can be achieved with the risk that the size of the representation is exponential in the number of variables. This is always the case for e.g. multipliers. An “explosion” of the OBDDs can be prevented in many practical cases by designing OBDD-algorithms very accurately and problem adjusted and trying to decrease the representation size dynamically. Another possibility is to search for alternative designs. Here there are different attempts, which can be classified grossly into the following directions: on the one hand the structural attributes should be eased; on the other hand other decompositions besides the Shannon-decomposition, which leads to the BDD-representation, are tested. In this connection EXOR-based decompositions were observed. They finally lead to the launch of Ordered Kronecker Functional Decision Diagrams (OKFDDs). EXOR-based decompositions correspond with synthesis methods, which allow EXORs as basic cells, in a natural way.

Even if logic synthesis allows the integration of several optimization goals, such as time response or testability, it may still be necessary to effect systematic improvements within the scope of post-processing. A common example is the possibility of testability-preserving transformations, which retain testability on the on hand and decrease area on the other. Attempts to extend this concept into the direction of other optimization goals, can be seen in several different and independent topics.

Starting with the obtained results the following key aspects are set on the field of logic synthesis:

usage of EXOR as basic cell (besides AND,OR,NOT) in the (two- and multi-level) circuit synthesis with respect to the optimization goals time, area and testability

quality improvement of synthesized circuits by using local transformations during and after synthesis

Decision Diagrams are used for the design and manipulation of boolean functions in modern tools of circuitdesign. The class of Ordered Kronecker Functional Decision Diagrams (OKFDDs) turned out to be especially efficient.

The software-packet PUMA for the administration of OKFDDs was already developed before the start of the project and is used in many cases today. At which not only applications of the sector of the project and the own professorship are included. PUMA is also used by research groups of other universities and the industry.

PUMA is disposable and can be obtained over FTP from the server ftp.informatik.uni-freiburg.de in the register pub/puma or directly over the www-page with the documentatiom of PUMA.