fmimage.c

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

	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 * fmImageDisjointSupport( DdManager * dd, array_t * pParts )
{
	array_t * pArray = NULL, * pPartNew;
	char ** pMatrix, * pSet, * pAll;
	int i, k, c, nComps, nCompsTotal;
	partinfo * 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( partinfo *, 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( partinfo *, pParts, i );
			p2 = array_fetch( partinfo *, 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] );
			printf( "\n" );
		}
	}

	// allocate the place for the set
	pSet = ALLOC( char, array_n(pParts) );
	pAll = ALLOC( char, array_n(pParts) );
	memset( pAll, 0, sizeof(char) * array_n(pParts) );

	// isolate strongly connected components
	nCompsTotal = 0;
	while ( nCompsTotal < array_n(pParts) )
	{
		// find the next comp
		nComps = 0;
		for ( i = 0; i < array_n(pParts); i++ )
			if ( pAll[i] == 0 )
			{
				// add this comp
				pAll[i]        = 1;
				pSet[nComps++] = i;
				nCompsTotal++;
				break;
			}
		// add all the related comps
		for ( c = 0; c < nComps; c++ )
			for ( k = 0; k < array_n(pParts); k++ )
				if ( pAll[k] == 0 && pMatrix[pSet[c]][k] )
				{
					pAll[k]        = 1;
					pSet[nComps++] = k;
					nCompsTotal++;
				}
		// add this set of components to the result
		if ( nComps < array_n(pParts) )
		{
			if ( pArray == NULL )
				pArray = array_alloc( array_t *, 5 );
			// create the new set of partitions
			pPartNew = array_alloc( partinfo *, 10 );
			for ( i = 0; i < nComps; i++ )
			{
				p1 = array_fetch( partinfo *, pParts, pSet[i] );
				array_insert_last( partinfo *, pPartNew, p1 );
			}
			// insert the new set
			array_insert_last( array_t *, pArray, pPartNew );
		}
	}
	assert( nCompsTotal == array_n(pParts) );
	free( pMatrix[0] );
	free( pMatrix );
	free( pSet );
	free( pAll );

	if ( fPrintPartitions && pArray )
	{
		partinfo * p;
		array_t * pComp;
		int i, k;

		printf( "The total number of components = %d.\n", array_n(pParts) );
		for ( i = 0; i < array_n(pArray); i++ )
		{
			pComp = array_fetch( array_t *, pArray, i );
			printf( "The number of components = %d.\n", array_n(pComp) );
			for ( k = 0; k < array_n(pComp); k++ )
			{
				p = array_fetch( partinfo *, pComp, k );
//				PRB( dd, p->bSupp );
			}
		}
		i = 0;
	}

	return pArray;
}


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

  Synopsis    [Solves small problems using monolithic transition relation.]

  Description [Returns NULL if the problem is larger than the given size. 
  Otherwise, returns the solution.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
DdNode * fmImageSmallSize( DdManager * dd, array_t * pParts, int nBddSize )
{
	DdNode * bTransRel, * bSupps;
	DdNode * bComp, * bTemp, * bImage;
	partinfo * pCur;
	int i, nNodes;

	assert( array_n(pParts) > 1 );

	nNodes = 0;
	for ( i = 0; i < array_n(pParts); i++ )
	{
		pCur    = array_fetch( partinfo *, pParts, i );
		nNodes += pCur->BddSize;
		if ( nNodes >= nBddSize )
			return NULL;
	}

	// build the transition relation mapping X space into P space using bPFuncs
	bTransRel = b1;  Cudd_Ref( b1 );
	bSupps    = b1;  Cudd_Ref( b1 );
	for ( i = 0; i < array_n(pParts); i++ )
	{
		if ( s_Timeout && clock() > s_TimeLimit )
		{
			Cudd_RecursiveDeref( dd, bTransRel );
			Cudd_RecursiveDeref( dd, bSupps );
			return NULL;
		}

		// get the partition
		pCur = array_fetch( partinfo *, pParts, i );
		// get the component
		bComp = Cudd_bddXnor( dd, pCur->bPart, pCur->bVar );	Cudd_Ref( bComp );
		// multiply this component with the transitive relation
		bTransRel = Cudd_bddAnd( dd, bTemp = bTransRel, bComp );  Cudd_Ref( bTransRel );
		Cudd_RecursiveDeref( dd, bTemp );
		Cudd_RecursiveDeref( dd, bComp );
		// multiply this component with the support
		bSupps = Cudd_bddAnd( dd, bTemp = bSupps, pCur->bSupp );  Cudd_Ref( bSupps );
		Cudd_RecursiveDeref( dd, bTemp );
	}

	bImage = Cudd_bddExistAbstract( dd, bTransRel, bSupps );    Cudd_Ref( bImage );
	Cudd_RecursiveDeref( dd, bTransRel );
	Cudd_RecursiveDeref( dd, bSupps );

	Cudd_Deref( bImage );
	return bImage;
}


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

  Synopsis    [Allocates the data structure to store one partition.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
partinfo * fmImagePartInfoAllocate()
{
	return ALLOC( partinfo, 1 );
}

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

  Synopsis    [Deallocates the data structure.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void fmImagePartInfoDeallocate( DdManager * dd, partinfo * p )
{
	if ( p->bPart )   Cudd_RecursiveDeref( dd, p->bPart );
	if ( p->bSupp )   Cudd_RecursiveDeref( dd, p->bSupp );
	free( p );
}

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

  Synopsis    [Compares two partitions by their BDD size.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int fmImagePartCompareBddSize( partinfo ** ppPart1, partinfo ** ppPart2 )
{
    if ( (*ppPart1)->BddSize < (*ppPart2)->BddSize )
        return  1;
    if ( (*ppPart1)->BddSize > (*ppPart2)->BddSize )
        return -1;
    return 0;
}

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

  Synopsis    [Frees the array of partitions.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void fmImagePartInfoArrayFree( DdManager * dd, array_t * pParts )
{
	int i;
	partinfo * pCur;
	// free the partitions
	for ( i = 0; i < array_n(pParts); i++ )
	{
		pCur = array_fetch( partinfo *, pParts, i );
		fmImagePartInfoDeallocate( dd, pCur );
	}
	array_free( pParts );
}


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

  Synopsis    [Sets the timeout.]

  Description []

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
void fmImageTimeoutSet( int timeout )
{
	s_Timeout = timeout;
}


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

  Synopsis    [Resets the timeout.]

  Description []

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
void fmImageTimeoutReset()
{
	s_Timeout = 0;
}



////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////