Browse Prior Art Database

Transitive Closure Algorithm for Reducing Simulation Model Sizes

IP.com Disclosure Number: IPCOM000123551D
Original Publication Date: 1999-Jan-01
Included in the Prior Art Database: 2005-Apr-05
Document File: 2 page(s) / 79K

Publishing Venue

IBM

Related People

Dunsmoor, AS: AUTHOR [+2]

Abstract

Disclosed is a transitive closure algorithm for reducing simulation model sizes. The size of modern designs are escalating and simulating these designs is becoming progressively more resource intensive. For instance, the number of machines required (in the order of 1000s of 595Hs in IBM) is a direct function of the design sizes being simulated. In some cases large designs (16-way Nighthawk) cannot be simulated because we simply do not have the capacity. A factor of 2 reduction of the model size translates to millions of dollars saved in simulation resources each year. In this disclosure we present an enhancement, transitive closure computation, that facilitates further reduction of simulation model sizes.

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

Transitive Closure Algorithm for Reducing Simulation Model Sizes

   Disclosed is a transitive closure algorithm for reducing
simulation model sizes.  The size of modern designs are escalating
and simulating these designs is becoming progressively more resource
intensive.  For instance, the number of machines required (in the
order of 1000s of 595Hs in IBM) is a direct function of the design
sizes being simulated.  In some cases large designs (16-way
Nighthawk) cannot be simulated because we simply do not have the
capacity.  A factor of 2 reduction of the model size translates to
millions of dollars saved in simulation resources each year.  In this
disclosure we present an enhancement, transitive closure computation,
that facilitates further reduction of simulation model sizes.
Application of this in conjunction with our other techniques
(xxx,xxx,xxx) have yeilded factors of reduction in model sizes.

   The design is input to the reduction step as a set of
boolean formulas.
  xi = f1(v1,v2,v3,.,vj,...,vn), where  xi (the formula name)
  my or may not be equal to vj (variable name), i.e. a formula
  which is also a ariable may or may not be a function of
  itself.  For example the formulas below (lt275871_1) is that
  of a latch, where lt275871_1 is a function of itself.
  lt275871_1: ( OR ( AND TRUE sg1097356 ) ( AND ( NOT TRUE )
                lt275871_1 ) )
  sg1097356: ( OR ( AND ( NOT ( NOT sg147 ) ) sg715 )
               ( AND ( NOT sg147 ) FALSE ) )
  sg715: ( OR ( NOT sg89 ) lt308082_11 )

   As is evident from the above expressions that formulas
feed into other formulas, since gate outputs feed into other gate
inputs in the design.

   The reduction algorithm works by symbolically computing
equivalences in sets of expressions and substituting the
equivalences in subsequent "users" in an iterative manner.  In order
to save computation, the list of equivalences is scanned once in
order and all occurrences of a variable are replaced by the
equivalent variable.  In this disclosure we illustrate one of the
problems with indiscriminate substitution and we present our
solution.
  Given a function,
    f1 = g(a,b,c,d);
    and the equivalence relations a=b,b=c,c=d;

   The order of substitution makes a difference in the
reduction achieved.  For instance, if the equivalences are
substituted in f1 in the order a=b,b=c,...