dsdProc.c File Reference

#include "dsdInt.h"

Include dependency graph for dsdProc.c:

Go to the source code of this file.

Functions
ABC_NAMESPACE_IMPL_START void	dsdKernelDecompose (Dsd_Manager_t *pDsdMan, DdNode **pbFuncs, int nFuncs)
	FUNCTION DECLARATIONS ///.
void	Dsd_Decompose (Dsd_Manager_t *pDsdMan, DdNode **pbFuncs, int nFuncs)
	DECOMPOSITION FUNCTIONS ///.
Dsd_Node_t *	Dsd_DecomposeOne (Dsd_Manager_t *pDsdMan, DdNode *bFunc)

Function Documentation

Dsd_Decompose()

void Dsd_Decompose	(	Dsd_Manager_t *	pDsdMan,
		DdNode **	pbFuncs,
		int	nFuncs )

DECOMPOSITION FUNCTIONS ///.

Function*************************************************************

Synopsis [Performs DSD for the array of functions represented by BDDs.]

Description [This function takes the DSD manager, which should be previously allocated by the call to Dsd_ManagerStart(). The resulting DSD tree is stored in the DSD manager (pDsdMan->pRoots, pDsdMan->nRoots). Access to the tree is through the APIs of the manager. The resulting tree is a shared DSD DAG for the functions given in the array. For one function the resulting DAG is always a tree. The root node pointers can be complemented, as discussed in the literature referred to in "dsd.h". This procedure can be called repeatedly for different functions. There is no need to remove the decomposition tree after it is returned, because the next call to the DSD manager will "recycle" the tree. The user should not modify or dereference any data associated with the nodes of the DSD trees (the user can only change the contents of a temporary mark associated with each node by the calling to Dsd_NodeSetMark()). All the decomposition trees and intermediate nodes will be removed when the DSD manager is deallocated at the end by calling Dsd_ManagerStop().]

SideEffects []

SeeAlso []

Definition at line 113 of file dsdProc.c.

{
    DdManager * dd = pDsdMan->dd;
    int i;
    abctime clk;
    Dsd_Node_t * pTemp;
    int SumMaxGateSize = 0;
    int nDecOutputs = 0;
    int nCBFOutputs = 0;
/*
s_Loops1 = 0;
s_Loops2 = 0;
s_Loops3 = 0;
s_Case4Calls = 0;
s_Case4CallsSpecial = 0;
s_Case5 = 0;
s_Loops2Useless = 0;
*/
    // resize the number of roots in the manager
    if ( pDsdMan->nRootsAlloc < nFuncs )
    {
        if ( pDsdMan->nRootsAlloc > 0 )
            ABC_FREE( pDsdMan->pRoots );
        pDsdMan->nRootsAlloc = nFuncs;
        pDsdMan->pRoots = (Dsd_Node_t **) ABC_ALLOC( char, pDsdMan->nRootsAlloc * sizeof(Dsd_Node_t *) );
    }
 
    if ( pDsdMan->fVerbose )
        printf( "\nDecomposability statistics for individual outputs:\n" );
 
    // set the counter of decomposition nodes
    s_nDecBlocks = 0;
 
    // perform decomposition for all outputs
    clk = Abc_Clock();
    pDsdMan->nRoots = 0;
    s_nCascades = 0;
    for ( i = 0; i < nFuncs; i++ )
    {
        int nLiteralsPrev;
        int nDecBlocksPrev;
        int nExorGatesPrev;
        int nReusedBlocksPres;
        int nCascades;
        int MaxBlock;
        int nPrimeBlocks;
        abctime clk;
 
        clk = Abc_Clock();
        nLiteralsPrev     = s_nLiterals;
        nDecBlocksPrev    = s_nDecBlocks;
        nExorGatesPrev    = s_nExorGates;
        nReusedBlocksPres = s_nReusedBlocks;
        nPrimeBlocks      = s_nPrimeBlocks;
 
        pDsdMan->pRoots[ pDsdMan->nRoots++ ] = dsdKernelDecompose_rec( pDsdMan, pbFuncs[i] );
 
        Dsd_TreeNodeGetInfoOne( pDsdMan->pRoots[i], &nCascades, &MaxBlock );
        s_nCascades = ddMax( s_nCascades, nCascades );
        pTemp = Dsd_Regular(pDsdMan->pRoots[i]);
        if ( pTemp->Type != DSD_NODE_PRIME || pTemp->nDecs != Extra_bddSuppSize(dd,pTemp->S) )
            nDecOutputs++;
        if ( MaxBlock < 3 )
            nCBFOutputs++;
        SumMaxGateSize += MaxBlock;
 
        if ( pDsdMan->fVerbose )
        {
            printf("#%02d: ", i );                              
            printf("Ins=%2d. ", Cudd_SupportSize(dd,pbFuncs[i]) );                  
            printf("Gts=%3d. ", Dsd_TreeCountNonTerminalNodesOne( pDsdMan->pRoots[i] ) ); 
            printf("Pri=%3d. ", Dsd_TreeCountPrimeNodesOne( pDsdMan->pRoots[i] ) ); 
            printf("Max=%3d. ", MaxBlock ); 
            printf("Reuse=%2d. ", s_nReusedBlocks-nReusedBlocksPres ); 
            printf("Csc=%2d. ", nCascades ); 
            printf("T= %.2f s. ", (float)(Abc_Clock()-clk)/(float)(CLOCKS_PER_SEC) ) ;
            printf("Bdd=%2d. ", Cudd_DagSize(pbFuncs[i]) ); 
            printf("\n");
            fflush( stdout );
        }
    }
    assert( pDsdMan->nRoots == nFuncs );
 
    if ( pDsdMan->fVerbose )
    {
        printf( "\n" );
        printf( "The cumulative decomposability statistics:\n" );
        printf( "  Total outputs                             = %5d\n", nFuncs );
        printf( "  Decomposable outputs                      = %5d\n", nDecOutputs );
        printf( "  Completely decomposable outputs           = %5d\n", nCBFOutputs );
        printf( "  The sum of max gate sizes                 = %5d\n", SumMaxGateSize );
        printf( "  Shared BDD size                           = %5d\n", Cudd_SharingSize( pbFuncs, nFuncs ) );
        printf( "  Decomposition entries                     = %5d\n", st__count( pDsdMan->Table ) );
        printf( "  Pure decomposition time                   =  %.2f sec\n", (float)(Abc_Clock() - clk)/(float)(CLOCKS_PER_SEC) );
    }
/*
    printf( "s_Loops1 = %d.\n", s_Loops1 );
    printf( "s_Loops2 = %d.\n", s_Loops2 );
    printf( "s_Loops3 = %d.\n", s_Loops3 );
    printf( "s_Case4Calls = %d.\n", s_Case4Calls );
    printf( "s_Case4CallsSpecial = %d.\n", s_Case4CallsSpecial );
    printf( "s_Case5 = %d.\n", s_Case5 );
    printf( "s_Loops2Useless = %d.\n", s_Loops2Useless );
*/
}

Here is the call graph for this function:

Here is the caller graph for this function:

Dsd_DecomposeOne()

Dsd_Node_t * Dsd_DecomposeOne	(	Dsd_Manager_t *	pDsdMan,
		DdNode *	bFunc )

Function*************************************************************

Synopsis [Performs decomposition for one function.]

Description []

SideEffects []

SeeAlso []

Definition at line 230 of file dsdProc.c.

{
    return dsdKernelDecompose_rec( pDsdMan, bFunc );
}

dsdKernelDecompose()

ABC_NAMESPACE_IMPL_START void dsdKernelDecompose	(	Dsd_Manager_t *	pDsdMan,
		DdNode **	pbFuncs,
		int	nFuncs )

FUNCTION DECLARATIONS ///.

CFile****************************************************************

FileName [dsdProc.c]

PackageName [DSD: Disjoint-support decomposition package.]

Synopsis [The core procedures of the package.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 8.0. Started - September 22, 2003.]

Revision [

Id

dsdProc.c,v 1.0 2002/22/09 00:00:00 alanmi Exp

]