Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Method for Identifying Technology Primitives in Logic Functions

IP.com Disclosure Number: IPCOM000108351D
Original Publication Date: 1992-May-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 3 page(s) / 166K

Publishing Venue

IBM

Related People

Damiano, R: AUTHOR [+6]

Abstract

Disclosed is a method for changing a logic design specified in terms of technology-independent Boolean primitives into a network made up of primitives from a gate-array or standard cell technology library.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 40% of the total text.

Method for Identifying Technology Primitives in Logic Functions

       Disclosed is a method for changing a logic design
specified in terms of technology-independent Boolean primitives into
a network made up of primitives from a gate-array or standard cell
technology library.

      Logic synthesis systems typically take a "high-level"
specification of a logic function and translate the description into
a logic graph which is independent of the target technology.
Technology- independent optimizations are then applied to improve the
area, testability and timing of the logic.  The graph is then
"technology mapped", which means that the nodes in the graph are
transformed from technology-independent entities into valid usages of
the primitives of a technology library.

      Current techniques for technology mapping usually divide the
problem into two pieces:  pattern generation and graph covering.  In
pattern generation, the possible matches of the library to the logic
are attached to the nodes and edges of the logic graph.  The graph
covering phase chooses among the generated patterns based on
considerations of the speed or area of the design.

      This article describes a method for the pattern matching part
of the technology mapping process.

      Currently, the two most prevalent forms of pattern matching are
function-specific matching and Ordered Binary Decision Diagram (OBDD)
matching.  In the first, the program "knows" what function or
functions it is creating.  For example, a pattern generator for XORs
would look for common configurations of XORs expressed as other
Boolean functions. Typical library primitives found by such programs
include multiplexers, decoders, parities, arithmetics, AND-OR, OR-AND
and selectors.  The disadvantages of using this method are the
limited number of configurations recognized and the large and
ever-increasing number of programs that must be written and
maintained.

      OBDDs are a canonical way of representing logic functions.  The
idea in using OBDDs is that OBDDs are developed for each of the
library elements in an offline process.  During mapping, the logic is
partitioned into sections and an OBDD is computed for the section.
The OBDD for the logic is then compared to the OBDD for the library
elements (comparison of OBDDs is a linear process) to find a match.
There are three main disadvantages of the OBDD method:  computing
OBDDs is intractable for some logic functions, such as multipliers;
OBDDs are sensitive to "variable ordering" (which variable in the
pattern is assigned to a variable in the logic), and they do not
handle multiple output functions gracefully.

      The method disclosed here is closest to the OBDD approach in
that the program does not "understand" the function it is matching.
In the proposed algorithm, the library elements are represented by
"truth tables".  For an n-input, m-output function, the truth table
is a matrix of binary values w...