Browse Prior Art Database

Logic Optimization And Mapping to Arbitrary N-Input Functions Under Constraints

IP.com Disclosure Number: IPCOM000103272D
Original Publication Date: 1990-Oct-01
Included in the Prior Art Database: 2005-Mar-17
Document File: 4 page(s) / 146K

Publishing Venue

IBM

Related People

Devries, C: AUTHOR [+4]

Abstract

Some hardware simulation engines require a logic representation such that every node in the logic is an arbitrary N-input 1-output function. (The term "arbitrary" means that the functions are not limited to a given set of functions, but that all of the 2**N possible N-input 1- output logic functions can be used.) In order to simulate the logic design, the source language description of the logic must be translated into this form. This can be done by first breaking down complex functions into 1-output functions with N or fewer inputs (mapping), and then optimizing this primitive logic into N-input 1-output functions.

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

Logic Optimization And Mapping to Arbitrary N-Input Functions Under Constraints

       Some hardware simulation engines require a logic
representation such that every node in the logic is an arbitrary
N-input 1-output function.  (The term "arbitrary" means that the
functions are not limited to a given set of functions, but that all
of the 2**N possible N-input 1- output logic functions can be used.)
In order to simulate the logic design, the source language
description of the logic must be translated into this form.  This can
be done by first breaking down complex functions into 1-output
functions with N or fewer inputs (mapping), and then optimizing this
primitive logic into N-input 1-output functions.

      The mapping step can be done, for example, by expressing the
logic in terms of And, Or and Invert functions.  This is
straightforward.  It is the second step, optimization, which this
article addresses.

      Often constraints are placed by a designer which require the
identity of certain logic connections to be preserved through this
process.  For example, the user may want to query the value of
certain nets during or after the simulation.  Such constraints are
necessary for proper evaluation of the simulation results.

      What such a constraint means is that the functional
relationships among certain user-specified nodes must not change
during the translation process.  In other words, if a node X is a
function of nodes (Y1,Y2,...,Yk) before translation, then node X must
still be the same function of those same k nodes.  We call this
preserving the cause of node X.  An immediate consequence of this is
the effect relationship.  If a node X affects nodes (Z1,Z2,...Zm)
before the translation, then after the translation of node X must
affect those same m nodes in the same manner.

      Present and past approaches to the mapping and optimization
process operate in a piecemeal manner.  In these approaches, the
logic is taken through a series of transformations with a goal of
reducing the number of nodes in the model.  There are two problems
with these approaches. First, they do not take advantage of the fact
that the logic can be mapped into a set of any arbitrary N-input
functions. Usually, they can handle only a limited number of logic
functions, such as And, Or, Xor, DFLOP, etc.  Second, they attack the
problem based on a traditional local transformation philosophy where
any sub-optimality is viewed narrowly for further optimization.  That
is, only a small portion of the logic is optimized at one time,
typically, a single node and its predecessors or successors.  This
philosophy works well for logic synthesis where the target technology
has a limited number of functions.  But, when you have an unlimited
function set, this yields poor results.  Also, it is awkward to apply
this philosophy under the constraints of preserving cause and effect
relationships among the user-specified nodes in the logi...