fxuint.h

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

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

  FileName    [fxuInt.h]

  PackageName [MVSIS 2.0: Multi-valued logic synthesis system.]

  Synopsis    [Internal declarations of fast extract for unate covers.]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - February 1, 2003.]

  Revision    [$Id: fxuInt.h,v 1.13 2003/05/27 23:15:49 alanmi Exp $]

***********************************************************************/
 
#ifndef __FXU_INT_H__
#define __FXU_INT_H__

////////////////////////////////////////////////////////////////////////
///                          INCLUDES                                ///
////////////////////////////////////////////////////////////////////////

#include "util.h"
#include "extra.h"

////////////////////////////////////////////////////////////////////////
///                         PARAMETERS                               ///
////////////////////////////////////////////////////////////////////////
#define PRT(a,t)     printf("%s = ", (a)); printf( "%6.2f sec\n", (float)(t)/(float)(CLOCKS_PER_SEC) )

// uncomment this macro to switch to standard memory management
//#define USE_SYSTEM_MEMORY_MANAGEMENT 

////////////////////////////////////////////////////////////////////////
///                    STRUCTURE DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

/*  
	Here is an informal description of the FX data structure.
	(1) The sparse matrix is filled with literals, associated with 
	    cubes (row) and variables (columns). The matrix contains 
        all the cubes of all the nodes in the network.
	(2) A cube is associated with 
	    (a) its literals in the matrix,
	    (b) the output variable of the node, to which this cube belongs,
	(3) A variable is associated with 
	    (a) its literals in the matrix and
		(b) the list of cube pairs in the cover, for which it is the output
	(4) A cube pair is associated with two cubes and contains the counters
	    of literals in the base and in the cubes without the base
	(5) A double-cube divisor is associated with list of all cube pairs 
        that produce it and its current weight (which is updated automatically 
        each time a new pair is added or an old pair is removed). 
	(6) A single-cube divisor is associated the pair of variables. 
*/

// sparse matrix
typedef struct FxuMatrix        Fxu_Matrix;     // the sparse matrix

// sparse matrix contents: cubes (rows), vars (columns), literals (entries)
typedef struct FxuCube          Fxu_Cube;       // one cube in the sparse matrix
typedef struct FxuVar           Fxu_Var;        // one literal in the sparse matrix
typedef struct FxuLit           Fxu_Lit;        // one entry in the sparse matrix

// double cube divisors
typedef struct FxuPair          Fxu_Pair;       // the pair of cubes
typedef struct FxuDouble        Fxu_Double;     // the double-cube divisor
typedef struct FxuSingle        Fxu_Single;     // the two-literal single-cube divisor

// various lists
typedef struct FxuListCube      Fxu_ListCube;   // the list of cubes
typedef struct FxuListVar       Fxu_ListVar;    // the list of literals
typedef struct FxuListLit       Fxu_ListLit;    // the list of entries
typedef struct FxuListPair      Fxu_ListPair;   // the list of pairs
typedef struct FxuListDouble    Fxu_ListDouble; // the list of divisors
typedef struct FxuListSingle    Fxu_ListSingle; // the list of single-cube divisors

// various heaps
typedef struct FxuHeapDouble    Fxu_HeapDouble; // the heap of divisors
typedef struct FxuHeapSingle    Fxu_HeapSingle; // the heap of variables


// various lists

// the list of cubes in the sparse matrix 
struct FxuListCube
{
	Fxu_Cube *       pHead;
	Fxu_Cube *       pTail;
	int              nItems;
};

// the list of literals in the sparse matrix 
struct FxuListVar
{
	Fxu_Var *        pHead;
	Fxu_Var *        pTail;
	int              nItems;
};

// the list of entries in the sparse matrix 
struct FxuListLit
{
	Fxu_Lit *        pHead;
	Fxu_Lit *        pTail;
	int              nItems;
};

// the list of cube pair in the sparse matrix 
struct FxuListPair
{
	Fxu_Pair *       pHead;
	Fxu_Pair *       pTail;
	int              nItems;
};

// the list of divisors in the sparse matrix 
struct FxuListDouble
{
	Fxu_Double *     pHead;
	Fxu_Double *     pTail;
	int              nItems;
};

// the list of divisors in the sparse matrix 
struct FxuListSingle
{
	Fxu_Single *     pHead;
	Fxu_Single *     pTail;
	int              nItems;
};


// various heaps

// the heap of double cube divisors by weight
struct FxuHeapDouble
{
	Fxu_Double **    pTree;
	int              nItems;
	int              nItemsAlloc;
	int              i;
};

// the heap of variable by their occurrence in the cubes
struct FxuHeapSingle
{
	Fxu_Single **    pTree;
	int              nItems;
	int              nItemsAlloc;
	int              i;
};



// sparse matrix
struct FxuMatrix // ~ 30 words
{
    // information about the network
    int              fMvNetwork;  // set to 1 if the network has MV nodes
    int *            pValue2Node; // the mapping of values into nodes
	// the cubes
	Fxu_ListCube     lCubes;      // the double linked list of cubes
    // the values (binary literals)
	Fxu_ListVar      lVars;       // the double linked list of variables
  	Fxu_Var **       ppVars;      // the array of variables
	// the double cube divisors
	Fxu_ListDouble * pTable;      // the hash table of divisors
	int              nTableSize;  // the hash table size
    int              nDivs;       // the number of divisors in the table
    int              nDivsTotal;  // the number of divisors in the table
	Fxu_HeapDouble * pHeapDouble;    // the heap of divisors by weight
    // the single cube divisors
    Fxu_ListSingle   lSingles;    // the linked list of single cube divisors  
	Fxu_HeapSingle * pHeapSingle; // the heap of variables by the number of literals in the matrix
    // storage for cube pairs
    Fxu_Pair ***     pppPairs;
    Fxu_Pair **      ppPairs;
	// temporary storage for cubes 
    Fxu_Cube *       pOrderCubes;
    Fxu_Cube **      ppTailCubes;
	// temporary storage for variables 
    Fxu_Var *        pOrderVars;
    Fxu_Var **       ppTailVars;
	// temporary storage for variables
	Fxu_Var **       pVarsTemp;
	int              nVarsTemp;
    // temporary storage for pairs
	Fxu_Pair **      pPairsTemp;
	int              nPairsTemp;
	int              nPairsMax;
	// statistics
	int              nEntries;    // the total number of entries in the sparse matrix
	int              nDivs1;      // the single cube divisors taken
	int              nDivs2;      // the double cube divisors taken
	int              nDivs3;      // the double cube divisors with complement
	// memory manager
	mm_fixed *       pMemMan;     // the memory manager for all small sized entries
};

// the cube in the sparse matrix
struct FxuCube // 9 words
{
	int              iCube;       // the number of this cube in the cover
	Fxu_Cube *       pFirst;      // the pointer to the first cube of this cover
	Fxu_Var *        pVar;        // the variable representing the output of the cover
	Fxu_ListLit      lLits;       // the row in the table 
	Fxu_Cube *       pPrev;       // the previous cube
	Fxu_Cube *       pNext;       // the next cube
    Fxu_Cube *       pOrder;      // the specialized linked list of cubes
};

// the variable in the sparse matrix
struct FxuVar // 10 words
{
	int              iVar;        // the number of this variable
    int              nCubes;      // the number of cubes assoc with this var
    Fxu_Cube *       pFirst;      // the first cube assoc with this var
    Fxu_Pair ***     ppPairs;     // the pairs of cubes assoc with this var
	Fxu_ListLit      lLits;       // the column in the table 
	Fxu_Var *        pPrev;       // the previous variable
	Fxu_Var *        pNext;       // the next variable
    Fxu_Var *        pOrder;      // the specialized linked list of variables
};

// the literal entry in the sparse matrix 
struct FxuLit // 8 words
{
	int              iVar;        // the number of this variable
	int              iCube;       // the number of this cube
	Fxu_Cube *       pCube;       // the cube of this literal
	Fxu_Var *        pVar;        // the variable of this literal
	Fxu_Lit *        pHPrev;      // prev lit in the cube
	Fxu_Lit *        pHNext;      // next lit in the cube
	Fxu_Lit *        pVPrev;      // prev lit of the var     
	Fxu_Lit *        pVNext;      // next lit of the var   
};

// the cube pair
struct FxuPair // 10 words
{
	int              nLits1;      // the number of literals in the two cubes
	int              nLits2;      // the number of literals in the two cubes
	int              nBase;       // the number of literals in the base
	Fxu_Double *     pDiv;        // the divisor of this pair
	Fxu_Cube *       pCube1;      // the first cube of the pair
	Fxu_Cube *       pCube2;      // the second cube of the pair
	int              iCube1;      // the first cube of the pair
	int              iCube2;      // the second cube of the pair
	Fxu_Pair *       pDPrev;      // the previous pair in the divisor
	Fxu_Pair *       pDNext;      // the next pair in the divisor
};

// the double cube divisor
struct FxuDouble // 10 words
{
	int              Num;         // the unique number of this divisor
	int              HNum;        // the heap number of this divisor
	int              Weight;      // the weight of this divisor
	unsigned         Key;         // the hash key of this divisor
	Fxu_ListPair     lPairs;      // the pairs of cubes, which produce this divisor
	Fxu_Double *     pPrev;       // the previous divisor in the table
	Fxu_Double *     pNext;       // the next divisor in the table
    Fxu_Double *     pOrder;      // the specialized linked list of divisors
};

// the single cube divisor
struct FxuSingle // 7 words
{
	int              Num;         // the unique number of this divisor