cuddapprox.c

主要进行大规模的电路综合

/**CFile***********************************************************************

  FileName    [cuddApprox.c]

  PackageName [cudd]

  Synopsis    [Procedures to approximate a given BDD.]

  Description [External procedures provided by this module:
                <ul>
		<li> Cudd_UnderApprox()
		<li> Cudd_OverApprox()
		<li> Cudd_RemapUnderApprox()
		<li> Cudd_RemapOverApprox()
		<li> Cudd_BiasedUnderApprox()
		<li> Cudd_BiasedOverApprox()
		</ul>
	       Internal procedures included in this module:
		<ul>
		<li> cuddUnderApprox()
		<li> cuddRemapUnderApprox()
		<li> cuddBiasedUnderApprox()
		</ul>
	       Static procedures included in this module:
		<ul>
		<li> gatherInfoAux()
		<li> gatherInfo()
		<li> computeSavings()
		<li> UAmarkNodes()
		<li> UAbuildSubset()
		<li> updateRefs()
		<li> RAmarkNodes()
		<li> BAmarkNodes()
		<li> RAbuildSubset()
		</ul>
		]

  SeeAlso     [cuddSubsetHB.c cuddSubsetSP.c cuddGenCof.c]

  Author      [Fabio Somenzi]

  Copyright   [This file was created at the University of Colorado at
               Boulder.  The University of Colorado at Boulder makes no
	       warranty about the suitability of this software for any
	       purpose.  It is presented on an AS IS basis.]

******************************************************************************/

#ifdef __STDC__
#include <float.h>
#else
#define DBL_MAX_EXP 1024
#endif
#include "util.h"
#include "cuddInt.h"

/*---------------------------------------------------------------------------*/
/* Constant declarations                                                     */
/*---------------------------------------------------------------------------*/

#define NOTHING		0
#define REPLACE_T	1
#define REPLACE_E	2
#define REPLACE_N	3
#define REPLACE_TT	4
#define REPLACE_TE	5

#define DONT_CARE	0
#define CARE		1
#define TOTAL_CARE	2
#define CARE_ERROR	3

/*---------------------------------------------------------------------------*/
/* Stucture declarations                                                     */
/*---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*/
/* Type declarations                                                         */
/*---------------------------------------------------------------------------*/

/* Data structure to store the information on each node. It keeps the
** number of minterms of the function rooted at this node in terms of
** the number of variables specified by the user; the number of
** minterms of the complement; the impact of the number of minterms of
** this function on the number of minterms of the root function; the
** reference count of the node from within the root function; the
** reference count of the node from an internal node; and the flag
** that says whether the node should be replaced and how. */
typedef struct NodeData {
    double mintermsP;		/* minterms for the regular node */
    double mintermsN;		/* minterms for the complemented node */
    int functionRef;		/* references from within this function */
    char care;			/* node intersects care set */
    char replace;		/* replacement decision */
    short int parity;		/* 1: even; 2: odd; 3: both */
    DdNode *resultP;		/* result for even parity */
    DdNode *resultN;		/* result for odd parity */
} NodeData;

typedef struct ApproxInfo {
    DdNode *one;		/* one constant */
    DdNode *zero;		/* BDD zero constant */
    NodeData *page;		/* per-node information */
    st_table *table;		/* hash table to access the per-node info */
    int index;			/* index of the current node */
    double max;			/* max number of minterms */
    int size;			/* how many nodes are left */
    double minterms;		/* how many minterms are left */
} ApproxInfo;

/* Item of the queue used in the levelized traversal of the BDD. */
#ifdef __osf__
#pragma pointer_size save
#pragma pointer_size short
#endif
typedef struct GlobalQueueItem {
    struct GlobalQueueItem *next;
    struct GlobalQueueItem *cnext;
    DdNode *node;
    double impactP;
    double impactN;
} GlobalQueueItem;
 
typedef struct LocalQueueItem {
    struct LocalQueueItem *next;
    struct LocalQueueItem *cnext;
    DdNode *node;
    int localRef;
} LocalQueueItem;
#ifdef __osf__
#pragma pointer_size restore
#endif

    
/*---------------------------------------------------------------------------*/
/* Variable declarations                                                     */
/*---------------------------------------------------------------------------*/

#ifndef lint
static char rcsid[] DD_UNUSED = "$Id: cuddApprox.c,v 1.1.1.1 2003/02/24 22:23:51 wjiang Exp $";
#endif

/*---------------------------------------------------------------------------*/
/* Macro declarations                                                        */
/*---------------------------------------------------------------------------*/

/**AutomaticStart*************************************************************/

/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/

static void updateParity ARGS((DdNode *node, ApproxInfo *info, int newparity));
static NodeData * gatherInfoAux ARGS((DdNode *node, ApproxInfo *info, int parity));
static ApproxInfo * gatherInfo ARGS((DdManager *dd, DdNode *node, int numVars, int parity));
static int computeSavings ARGS((DdManager *dd, DdNode *f, DdNode *skip, ApproxInfo *info, DdLevelQueue *queue));
static int updateRefs ARGS((DdManager *dd, DdNode *f, DdNode *skip, ApproxInfo *info, DdLevelQueue *queue));
static int UAmarkNodes ARGS((DdManager *dd, DdNode *f, ApproxInfo *info, int threshold, int safe, double quality));
static DdNode * UAbuildSubset ARGS((DdManager *dd, DdNode *node, ApproxInfo *info));
static int RAmarkNodes ARGS((DdManager *dd, DdNode *f, ApproxInfo *info, int threshold, double quality));
static int BAmarkNodes ARGS((DdManager *dd, DdNode *f, ApproxInfo *info, int threshold, double quality1, double quality0));
static DdNode * RAbuildSubset ARGS((DdManager *dd, DdNode *node, ApproxInfo *info));
static int BAapplyBias ARGS((DdManager *dd, DdNode *f, DdNode *b, ApproxInfo *info, DdHashTable *cache));

/**AutomaticEnd***************************************************************/


/*---------------------------------------------------------------------------*/
/* Definition of exported functions                                          */
/*---------------------------------------------------------------------------*/

/**Function********************************************************************

  Synopsis [Extracts a dense subset from a BDD with Shiple's
  underapproximation method.]

  Description [Extracts a dense subset from a BDD. This procedure uses
  a variant of Tom Shiple's underapproximation method. The main
  difference from the original method is that density is used as cost
  function.  Returns a pointer to the BDD of the subset if
  successful. NULL if the procedure runs out of memory. The parameter
  numVars is the maximum number of variables to be used in minterm
  calculation.  The optimal number should be as close as possible to
  the size of the support of f.  However, it is safe to pass the value
  returned by Cudd_ReadSize for numVars when the number of variables
  is under 1023.  If numVars is larger than 1023, it will cause
  overflow. If a 0 parameter is passed then the procedure will compute
  a value which will avoid overflow but will cause underflow with 2046
  variables or more.]

  SideEffects [None]

  SeeAlso     [Cudd_SubsetShortPaths Cudd_SubsetHeavyBranch Cudd_ReadSize]

******************************************************************************/
DdNode *
Cudd_UnderApprox(
  DdManager * dd /* manager */,
  DdNode * f /* function to be subset */,
  int  numVars /* number of variables in the support of f */,
  int  threshold /* when to stop approximation */,
  int  safe /* enforce safe approximation */,
  double  quality /* minimum improvement for accepted changes */)
{
    DdNode *subset;

    do {
	dd->reordered = 0;
	subset = cuddUnderApprox(dd, f, numVars, threshold, safe, quality);
    } while (dd->reordered == 1);

    return(subset);

} /* end of Cudd_UnderApprox */


/**Function********************************************************************

  Synopsis    [Extracts a dense superset from a BDD with Shiple's
  underapproximation method.]

  Description [Extracts a dense superset from a BDD. The procedure is
  identical to the underapproximation procedure except for the fact that it
  works on the complement of the given function. Extracting the subset
  of the complement function is equivalent to extracting the superset
  of the function.
  Returns a pointer to the BDD of the superset if successful. NULL if
  intermediate result causes the procedure to run out of memory. The
  parameter numVars is the maximum number of variables to be used in
  minterm calculation.  The optimal number
  should be as close as possible to the size of the support of f.
  However, it is safe to pass the value returned by Cudd_ReadSize for
  numVars when the number of variables is under 1023.  If numVars is
  larger than 1023, it will overflow. If a 0 parameter is passed then
  the procedure will compute a value which will avoid overflow but
  will cause underflow with 2046 variables or more.]

  SideEffects [None]

  SeeAlso     [Cudd_SupersetHeavyBranch Cudd_SupersetShortPaths Cudd_ReadSize]

******************************************************************************/
DdNode *
Cudd_OverApprox(
  DdManager * dd /* manager */,
  DdNode * f /* function to be superset */,
  int  numVars /* number of variables in the support of f */,
  int  threshold /* when to stop approximation */,
  int  safe /* enforce safe approximation */,
  double  quality /* minimum improvement for accepted changes */)
{
    DdNode *subset, *g;

    g = Cudd_Not(f);    
    do {
	dd->reordered = 0;
	subset = cuddUnderApprox(dd, g, numVars, threshold, safe, quality);
    } while (dd->reordered == 1);
    
    return(Cudd_NotCond(subset, (subset != NULL)));
    
} /* end of Cudd_OverApprox */


/**Function********************************************************************

  Synopsis [Extracts a dense subset from a BDD with the remapping
  underapproximation method.]

  Description [Extracts a dense subset from a BDD. This procedure uses
  a remapping technique and density as the cost function.
  Returns a pointer to the BDD of the subset if
  successful. NULL if the procedure runs out of memory. The parameter
  numVars is the maximum number of variables to be used in minterm
  calculation.  The optimal number should be as close as possible to
  the size of the support of f.  However, it is safe to pass the value
  returned by Cudd_ReadSize for numVars when the number of variables
  is under 1023.  If numVars is larger than 1023, it will cause
  overflow. If a 0 parameter is passed then the procedure will compute
  a value which will avoid overflow but will cause underflow with 2046
  variables or more.]

  SideEffects [None]

  SeeAlso     [Cudd_SubsetShortPaths Cudd_SubsetHeavyBranch Cudd_UnderApprox Cudd_ReadSize]

******************************************************************************/
DdNode *
Cudd_RemapUnderApprox(
  DdManager * dd /* manager */,
  DdNode * f /* function to be subset */,
  int  numVars /* number of variables in the support of f */,
  int  threshold /* when to stop approximation */,
  double  quality /* minimum improvement for accepted changes */)
{
    DdNode *subset;

    do {
	dd->reordered = 0;
	subset = cuddRemapUnderApprox(dd, f, numVars, threshold, quality);
    } while (dd->reordered == 1);

    return(subset);

} /* end of Cudd_RemapUnderApprox */


/**Function********************************************************************

  Synopsis    [Extracts a dense superset from a BDD with the remapping
  underapproximation method.]

  Description [Extracts a dense superset from a BDD. The procedure is
  identical to the underapproximation procedure except for the fact that it
  works on the complement of the given function. Extracting the subset
  of the complement function is equivalent to extracting the superset
  of the function.
  Returns a pointer to the BDD of the superset if successful. NULL if
  intermediate result causes the procedure to run out of memory. The
  parameter numVars is the maximum number of variables to be used in
  minterm calculation.  The optimal number
  should be as close as possible to the size of the support of f.
  However, it is safe to pass the value returned by Cudd_ReadSize for
  numVars when the number of variables is under 1023.  If numVars is
  larger than 1023, it will overflow. If a 0 parameter is passed then
  the procedure will compute a value which will avoid overflow but
  will cause underflow with 2046 variables or more.]

  SideEffects [None]

  SeeAlso     [Cudd_SupersetHeavyBranch Cudd_SupersetShortPaths Cudd_ReadSize]

******************************************************************************/
DdNode *
Cudd_RemapOverApprox(
  DdManager * dd /* manager */,
  DdNode * f /* function to be superset */,
  int  numVars /* number of variables in the support of f */,
  int  threshold /* when to stop approximation */,
  double  quality /* minimum improvement for accepted changes */)
{
    DdNode *subset, *g;

    g = Cudd_Not(f);    
    do {
	dd->reordered = 0;
	subset = cuddRemapUnderApprox(dd, g, numVars, threshold, quality);
    } while (dd->reordered == 1);
    
    return(Cudd_NotCond(subset, (subset != NULL)));
    
} /* end of Cudd_RemapOverApprox */


/**Function********************************************************************

  Synopsis [Extracts a dense subset from a BDD with the biased
  underapproximation method.]

  Description [Extracts a dense subset from a BDD. This procedure uses
  a biased remapping technique and density as the cost function. The bias
  is a function. This procedure tries to approximate where the bias is 0
  and preserve the given function where the bias is 1.
  Returns a pointer to the BDD of the subset if
  successful. NULL if the procedure runs out of memory. The parameter
  numVars is the maximum number of variables to be used in minterm
  calculation.  The optimal number should be as close as possible to
  the size of the support of f.  However, it is safe to pass the value
  returned by Cudd_ReadSize for numVars when the number of variables
  is under 1023.  If numVars is larger than 1023, it will cause
  overflow. If a 0 parameter is passed then the procedure will compute
  a value which will avoid overflow but will cause underflow with 2046
  variables or more.]

  SideEffects [None]

  SeeAlso     [Cudd_SubsetShortPaths Cudd_SubsetHeavyBranch Cudd_UnderApprox
  Cudd_RemapUnderApprox Cudd_ReadSize]

******************************************************************************/
DdNode *
Cudd_BiasedUnderApprox(
  DdManager *dd /* manager */,
  DdNode *f /* function to be subset */,
  DdNode *b /* bias function */,
  int numVars /* number of variables in the support of f */,
  int threshold /* when to stop approximation */,
  double quality1 /* minimum improvement for accepted changes when b=1 */,
  double quality0 /* minimum improvement for accepted changes when b=0 */)
{
    DdNode *subset;

    do {
	dd->reordered = 0;
	subset = cuddBiasedUnderApprox(dd, f, b, numVars, threshold, quality1,
				       quality0);
    } while (dd->reordered == 1);

    return(subset);

} /* end of Cudd_BiasedUnderApprox */


/**Function********************************************************************

  Synopsis    [Extracts a dense superset from a BDD with the biased
  underapproximation method.]

  Description [Extracts a dense superset from a BDD. The procedure is
  identical to the underapproximation procedure except for the fact that it
  works on the complement of the given function. Extracting the subset
  of the complement function is equivalent to extracting the superset
  of the function.
  Returns a pointer to the BDD of the superset if successful. NULL if
  intermediate result causes the procedure to run out of memory. The
  parameter numVars is the maximum number of variables to be used in
  minterm calculation.  The optimal number
  should be as close as possible to the size of the support of f.
  However, it is safe to pass the value returned by Cudd_ReadSize for
  numVars when the number of variables is under 1023.  If numVars is
  larger than 1023, it will overflow. If a 0 parameter is passed then
  the procedure will compute a value which will avoid overflow but