fmimagemv.c

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

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

  FileName    [fmImageMv.c]

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

  Synopsis    [The binary MV image computation by output splitting.]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

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

  Revision    [$Id: fmImageMv.c,v 1.4 2003/05/27 23:15:33 alanmi Exp $]

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

#include "fmInt.h"

////////////////////////////////////////////////////////////////////////
///                       DATA STRUCTURES                            ///
////////////////////////////////////////////////////////////////////////

// information about one partition of MV functions
typedef struct FmImagePartInfoStruct    Fm_ImagePartInfo_t;
struct FmImagePartInfoStruct
{
    int       nValues;   // the number of values of this MV var
    int       BddSize;   // the number of nodes in the shared BDD of i-sets
	DdNode *  bSupp;     // the support of this partition (one supp var per MV var)
	DdNode ** pbFuncs;   // the partition functions of this MV var (nValues)
	DdNode ** pbCodes;   // the MV cubes for the image of this MV var (nValues)
};


////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

static DdNode *   fmImageMvCompute( DdManager * dd, DdNode * bCare, DdNode ** pbFuncs, int nFuncs, 
                    Vmx_VarMap_t * pVmxGlo, Vmx_VarMap_t * pVmxLoc, DdNode ** pbVars, int nBddSize );
static DdNode *   fmImageMv_rec( DdManager * dd, array_t * pParts, DdNode * bCubeIn, Vmx_VarMap_t * pVmxGlo, int nBddSize );
static DdNode *   fmImageMvValue_rec( DdManager * dd, array_t * pParts, int iPart, DdNode * bCubeIn, Vmx_VarMap_t * pVmxGlo, int nBddSize );
static DdNode *   fmImageMvSmallSize( DdManager * dd, array_t * pParts, DdNode * bCubeIn, int nBddSize );
static array_t *  fmImageMvDisjointSupport( DdManager * dd, array_t * pParts );

static Fm_ImagePartInfo_t * fmImageMvPartAllocate( DdNode * bSupp, DdNode ** pbFuncs, DdNode ** pbCodes, int nValues );
static Fm_ImagePartInfo_t * fmImageMvPartCreate( DdManager * dd, DdNode * bCare, DdNode * pbFuncs[], DdNode * pbCodes[], int nValues, Vmx_VarMap_t * pVmxGlo, DdNode ** pbImagePart, bool fUseAnd );

static void       fmImageMvPartFree( DdManager * dd, Fm_ImagePartInfo_t * p );
static int        fmImageMvPartCompareBddSize( Fm_ImagePartInfo_t ** ppPart1, Fm_ImagePartInfo_t ** ppPart2 );
static void       fmImageMvPartDeref( DdManager * dd, DdNode ** pbFuncs, int nFuncs );
static void       fmImageMvPartConstrain( DdManager * dd, DdNode * bCare, DdNode ** pbFuncs, int nValues, DdNode * pbConstrs[], bool fUseAnd );
static DdNode *   fmImageMvPartSupport( DdManager * dd, DdNode ** pbFuncs, int nFuncs, Vmx_VarMap_t * pVmxGlo );
static DdNode *   fmImageMvPartConvolve( DdManager * dd, DdNode ** pbFuncs, DdNode ** pbCodes, int nFuncs );
static DdNode *   fmImageMvPartImage( DdManager * dd, DdNode * bCubeIn, Fm_ImagePartInfo_t * p );
static void       fmImageMvPartArrayFree( DdManager * dd, array_t * pParts );


// these are needed to implement timeout
static int s_Timeout   = 0;
static int s_TimeLimit = 0; 

////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFITIONS                           ///
////////////////////////////////////////////////////////////////////////


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

  Synopsis    [Computes the MV image of a set of function.]

  Description [Computes the image of the care set (dd,bCare) with the set 
  of global functions (pbFuncs,nFuncs). The variable maps (pVmxGlo,pVmxLoc)
  characterize the global/local spaces. Stops iterative splitting when 
  the shared BDD size of the global functions is less than nBddSize. ]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
DdNode * Fm_ImageMvCompute( DdManager * dd, DdNode * bCare, DdNode ** pbFuncs, int nFuncs, 
    Vmx_VarMap_t * pVmxGlo, Vmx_VarMap_t * pVmxLoc, DdNode ** pbVars, int nBddSize )
{
    Vm_VarMap_t * pVm;
    DdNode ** pbCodesExt, * pbCodesLocal[32];
    DdNode * pbCofs[32], * pbImages[32];
    DdNode * bCubeOut, * bImage;
    int nVarsIn, nValuesOut, i;

    pVm = Vmx_VarMapReadVm( pVmxGlo );
    nVarsIn = Vm_VarMapReadVarsInNum(pVm);
    nValuesOut = Vm_VarMapReadValuesOutNum(pVm);
    assert( Vm_VarMapReadVarsOutNum(pVm) == 1 );

    // create the local copy of the codes w.r.t. to the parameter (output) var
    pbCodesExt = Vmx_VarMapEncodeVar( dd, pVmxGlo, nVarsIn );
    for ( i = 0; i < nValuesOut; i++ )
    {
        pbCodesLocal[i] = pbCodesExt[i]; Cudd_Ref( pbCodesLocal[i] );
    }
    Vmx_VarMapEncodeDeref( dd, pVmxGlo, pbCodesExt );

    // derive the cofactors
    bCubeOut = Vmx_VarMapCharCubeOutput( dd, pVmxGlo );  Cudd_Ref( bCubeOut );
    for ( i = 0; i < nValuesOut; i++ )
    {
        pbCofs[i] = Cudd_bddAndAbstract( dd, bCare, pbCodesLocal[i], bCubeOut ); 
        Cudd_Ref( pbCofs[i] );
    }
    Cudd_RecursiveDeref( dd, bCubeOut ); 

    // solve the image computation problem for the cofactors
    for ( i = 0; i < nValuesOut; i++ )
    {
        pbImages[i] = fmImageMvCompute( dd, pbCofs[i], pbFuncs, nFuncs, pVmxGlo, pVmxLoc, pbVars, nBddSize );  
        if ( pbImages[i] == NULL )
        {
            fmImageMvPartDeref( dd, pbImages, i - 1 );
            fmImageMvPartDeref( dd, pbCofs, nValuesOut );
            fmImageMvPartDeref( dd, pbCodesLocal, nValuesOut );
            return NULL;
        }
        Cudd_Ref( pbImages[i] );
    }
    bImage = fmImageMvPartConvolve( dd, pbImages, pbCodesLocal, nValuesOut ); Cudd_Ref( bImage );
    fmImageMvPartDeref( dd, pbCofs, nValuesOut );
    fmImageMvPartDeref( dd, pbImages, nValuesOut );
    fmImageMvPartDeref( dd, pbCodesLocal, nValuesOut );
    Cudd_Deref( bImage );
    return bImage;
}

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

  Synopsis    [Computes the MV image of a set of function.]

  Description [Assumes that the care-set does not depend on the parameter variables.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
DdNode * fmImageMvCompute( DdManager * dd, DdNode * bCare, DdNode ** pbFuncs, int nFuncs, 
    Vmx_VarMap_t * pVmxGlo, Vmx_VarMap_t * pVmxLoc, DdNode ** pbVars, int nBddSize )
{
    DdNode ** pbCodes, * bCubeIn, * bTemp;
	DdNode * bImage, * bImagePart, * bImageProper;
    Vm_VarMap_t * pVm;
	Fm_ImagePartInfo_t * pNew;
	array_t * pParts;
	int i, nVarsIn, nValuesIn, iValue;
    int * pValues;

    // set the timeout
	s_TimeLimit = (int)(s_Timeout /* in miliseconds */ * (float)(CLOCKS_PER_SEC) / 1000 ) + clock();

    // get the parameters
    pVm       = Vmx_VarMapReadVm( pVmxLoc );
    nVarsIn   = Vm_VarMapReadVarsInNum( pVm );
    nValuesIn = Vm_VarMapReadValuesInNum( pVm );
    pValues   = Vm_VarMapReadValuesArray( pVm );
    // the number of functions should be equal to the number of input values in the local space
    assert( nFuncs == nValuesIn );

	// create the array of partitions
	pParts = array_alloc( Fm_ImagePartInfo_t *, nVarsIn );

    // encode the local space
    pbCodes = Vmx_VarMapEncodeMapUsingVars( dd, pbVars, pVmxLoc );

	// constrain the functions
	bImage = b1;  Cudd_Ref( bImage );
    iValue = 0;
	for ( i = 0; i < nVarsIn; i++ )
	{
        // create the partition corresponding to the i-th MV variable
        pNew = fmImageMvPartCreate( dd, bCare, pbFuncs + iValue, 
            pbCodes + iValue, pValues[i], pVmxGlo, &bImagePart, 1 );
        if ( pNew == NULL )
        { // the partition is trivial, the image has been computed instead
            // bImagePart comes referenced
            bImage = Cudd_bddAnd( dd, bTemp = bImage, bImagePart );  Cudd_Ref( bImage );
			Cudd_RecursiveDeref( dd, bTemp );
			Cudd_RecursiveDeref( dd, bImagePart );
        }
        else
        { // store away this partition
            assert( bImagePart == NULL );
			array_insert_last( Fm_ImagePartInfo_t *, pParts, pNew );
        }
        // add to the values
        iValue += pValues[i];
	}
    assert( iValue == nValuesIn );

    // deref the codes of the local space
    Vmx_VarMapEncodeDeref( dd, pVmxLoc, pbCodes );

    if ( array_n(pParts) > 0 )
    {
        array_sort( pParts, fmImageMvPartCompareBddSize );
        // get the cube of input vars
        bCubeIn = Vmx_VarMapCharCubeInput( dd, pVmxGlo );  Cudd_Ref( bCubeIn );
	    // call the recursive image computation
	    bImageProper = fmImageMv_rec( dd, pParts, bCubeIn, pVmxGlo, nBddSize );  
	    if ( bImageProper == NULL )
	    {
		    Cudd_RecursiveDeref( dd, bImage );
	        Cudd_RecursiveDeref( dd, bCubeIn );
		    fmImageMvPartArrayFree( dd, pParts );
		    return NULL;
	    }
	    Cudd_Ref( bImageProper );
	    Cudd_RecursiveDeref( dd, bCubeIn );

	    // add to the image
	    bImage = Cudd_bddAnd( dd, bTemp = bImage, bImageProper );  Cudd_Ref( bImage );
	    Cudd_RecursiveDeref( dd, bTemp );
	    Cudd_RecursiveDeref( dd, bImageProper );
    }
    fmImageMvPartArrayFree( dd, pParts );
	Cudd_Deref( bImage );
	return bImage;
}

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

  Synopsis    [Recursively computes the image for a set of partitions.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
DdNode * fmImageMv_rec( DdManager * dd, array_t * pParts, DdNode * bCubeIn, Vmx_VarMap_t * pVmxGlo, int nBddSize )
{
	DdNode * bImage;
    DdNode * pbImages[32];
	array_t * pDisjs, * pArray;
	Fm_ImagePartInfo_t * pStart;
	int i, k;

    assert( array_n(pParts) > 0 );

	// trivial case when there is only one partition
	if ( array_n(pParts) == 1 )
    {
        pStart = array_fetch( Fm_ImagePartInfo_t *, pParts, 0 );
        return fmImageMvPartImage( dd, bCubeIn, pStart );
    }

	// checking for disjoint supports
	pDisjs = fmImageMvDisjointSupport( dd, pParts );
	if ( pDisjs != NULL ) // there are disjoint support groups
	{
		DdNode * bImageNew, * bTemp;
		bImage = b1; Cudd_Ref( bImage );
		for ( i = 0; i < array_n(pDisjs); i++ )
		{
			pArray = array_fetch( array_t *, pDisjs, i );
			bImageNew = fmImageMv_rec( dd, pArray, bCubeIn, pVmxGlo, nBddSize );   
			if ( bImageNew == NULL )
			{
				Cudd_RecursiveDeref( dd, bImage );
				for ( k = i; k < array_n(pDisjs); k++ )
				{
					pArray = array_fetch( array_t *, pDisjs, k );
					array_free(pArray);
				}
				array_free( pDisjs );
				return NULL;
			}
			Cudd_Ref( bImageNew );

			bImage = Cudd_bddAnd( dd, bTemp = bImage, bImageNew );  Cudd_Ref( bImage );
			Cudd_RecursiveDeref( dd, bTemp );
			Cudd_RecursiveDeref( dd, bImageNew );
			array_free(pArray);
		}
		array_free( pDisjs );
		Cudd_Deref( bImage );
		return bImage;
	}

	// checking the BDD size
	if ( bImage = fmImageMvSmallSize( dd, pParts, bCubeIn, nBddSize ) )
		return bImage;

	if ( s_Timeout && clock() > s_TimeLimit )
		return NULL;

	// the regular case - split around the first partition
	pStart  = array_fetch( Fm_ImagePartInfo_t *, pParts, 0 );
    for ( i = 0; i < pStart->nValues; i++ )
    {
        pbImages[i] = fmImageMvValue_rec( dd, pParts, i, bCubeIn, pVmxGlo, nBddSize );  
        if ( pbImages[i] == NULL )
        {
            fmImageMvPartDeref( dd, pbImages, i - 1 );
            return NULL;
        }
        Cudd_Ref( pbImages[i] );
    }
    bImage = fmImageMvPartConvolve( dd, pbImages, pStart->pbCodes, pStart->nValues );
    Cudd_Ref( bImage );
    fmImageMvPartDeref( dd, pbImages, pStart->nValues );
    Cudd_Deref( bImage );
    return bImage;
}


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

  Synopsis    [Recursively computes one cofactor of the image of a set of partitions.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
DdNode * fmImageMvValue_rec( DdManager * dd, array_t * pParts, int iPart, DdNode * bCubeIn, Vmx_VarMap_t * pVmxGlo, int nBddSize )
{
	DdNode * bImageProper, * bImagePart;
	DdNode * bImage, * bTemp, * bCare;
	Fm_ImagePartInfo_t * pCur, * pStart, * pNew;
	array_t * pPartsNew;
	int i;

    // get the current partition
    pStart  = array_fetch( Fm_ImagePartInfo_t *, pParts, 0 );
    // get the care set
    bCare = pStart->pbFuncs[iPart];

	// create the array of partitions
	pPartsNew = array_alloc( Fm_ImagePartInfo_t *, array_n(pParts)-1 );
	// constrain the functions
	bImage = b1;  Cudd_Ref( bImage );
	for ( i = 1; i < array_n(pParts); i++ )
	{
        // get the partition corresponding to the i-th MV var
        pCur = array_fetch( Fm_ImagePartInfo_t *, pParts, i );
        // create the partition corresponding to the i-th MV variable
        pNew = fmImageMvPartCreate( dd, bCare, pCur->pbFuncs, 
            pCur->pbCodes, pCur->nValues, pVmxGlo, &bImagePart, 1 );
        if ( pNew == NULL )
        { // the partition is trivial, the image has been computed instead
            // bImagePart comes referenced
            bImage = Cudd_bddAnd( dd, bTemp = bImage, bImagePart );  Cudd_Ref( bImage );
			Cudd_RecursiveDeref( dd, bTemp );
			Cudd_RecursiveDeref( dd, bImagePart );
        }
        else
        { // store away this partition
			array_insert_last( Fm_ImagePartInfo_t *, pPartsNew, pNew );
        }
	}

    if ( array_n(pPartsNew) > 0 )
    {
        array_sort( pPartsNew, fmImageMvPartCompareBddSize );
	    // call the recursive image computation
	    bImageProper = fmImageMv_rec( dd, pPartsNew, bCubeIn, pVmxGlo, nBddSize );  
	    if ( bImageProper == NULL )
	    {
		    Cudd_RecursiveDeref( dd, bImage );
		    fmImageMvPartArrayFree( dd, pPartsNew );
		    return NULL;
	    }
	    Cudd_Ref( bImageProper );

	    // add to the image
	    bImage = Cudd_bddAnd( dd, bTemp = bImage, bImageProper );  Cudd_Ref( bImage );
	    Cudd_RecursiveDeref( dd, bTemp );
	    Cudd_RecursiveDeref( dd, bImageProper );
    }
    fmImageMvPartArrayFree( dd, pPartsNew );
	Cudd_Deref( bImage );
	return bImage;
}


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

  Synopsis    [Splits the image using disjoint support of the functions.]

  Description [Returns NULL, if there is no way to split. Otherwise, returns
  the array of arrays holding the sets of disjoint partitions.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
array_t * fmImageMvDisjointSupport( DdManager * dd, array_t * pParts )
{
	array_t * pArray = NULL, * pPartNew;
	char ** pMatrix, * pSet, * pAll;
	int i, k, c, nComps, nCompsTotal;
	Fm_ImagePartInfo_t * p1, * p2;
	int fPrintPartitions = 0;
	
	assert( array_n(pParts) > 1 );

	// allocate the interaction matrix
	pMatrix = ALLOC( char *, array_n(pParts) );
	pMatrix[0] = ALLOC( char, array_n(pParts) * array_n(pParts) );
	for ( i = 1; i < array_n(pParts); i++ )
		pMatrix[i] = pMatrix[i-1] + sizeof(char) * array_n(pParts);

	if ( fPrintPartitions )
	{
		for ( i = 0; i < array_n(pParts); i++ )
		{
			p1 = array_fetch( Fm_ImagePartInfo_t *, pParts, i );
//			PRB( dd, p1->bSupp );
		}
	}

	// fill in the matrix
	for ( i = 0; i < array_n(pParts); i++ )
	{
		pMatrix[i][i] = 0;
		for ( k = i + 1; k < array_n(pParts); k++ )
		{
			p1 = array_fetch( Fm_ImagePartInfo_t *, pParts, i );
			p2 = array_fetch( Fm_ImagePartInfo_t *, pParts, k );
			pMatrix[i][k] = Extra_bddSuppOverlapping( dd, p1->bSupp, p2->bSupp );
			pMatrix[k][i] = pMatrix[i][k];
		}
		if ( fPrintPartitions )
		{
			for ( k = 0; k < array_n(pParts); k++ )
				printf( "%d", pMatrix[i][k] );