fxu.c File Reference

#include "fxuInt.h"
#include "fxu.h"

Go to the source code of this file.

Functions
ABC_NAMESPACE_IMPL_START Fxu_Matrix *	Fxu_CreateMatrix (Fxu_Data_t *pData)
	DECLARATIONS ///. More...
void	Fxu_CreateCovers (Fxu_Matrix *p, Fxu_Data_t *pData)
int	Fxu_FastExtract (Fxu_Data_t *pData)
	FUNCTION DEFINITIONS ///. More...
void	Fxu_MatrixRingCubesUnmark (Fxu_Matrix *p)
void	Fxu_MatrixRingVarsUnmark (Fxu_Matrix *p)
char *	Fxu_MemFetch (Fxu_Matrix *p, int nBytes)
	FUNCTION DEFINITIONS ///. More...
void	Fxu_MemRecycle (Fxu_Matrix *p, char *pItem, int nBytes)

Variables
static int	s_MemoryTotal
static int	s_MemoryPeak

Function Documentation

void Fxu_CreateCovers	(	Fxu_Matrix *	p,
		Fxu_Data_t *	pData
	)

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

Synopsis [Creates the new array of Sop covers from the sparse matrix.]

Description []

SideEffects []

SeeAlso []

Definition at line 278 of file fxuCreate.c.

{
    Fxu_Cube * pCube, * pCubeFirst, * pCubeNext;
    char * pSopCover;
    int iNode, n;

    // get the first cube of the first internal node 
    pCubeFirst = Fxu_CreateCoversFirstCube( p, pData, 0 );

    // go through the internal nodes
    for ( n = 0; n < pData->nNodesOld; n++ )
    if ( (pSopCover = (char *)pData->vSops->pArray[n]) )
    {
        // get the number of this node
        iNode = n;
        // get the next first cube
        pCubeNext = Fxu_CreateCoversFirstCube(  p, pData, iNode + 1 );
        // check if there any new variables in these cubes
        for ( pCube = pCubeFirst; pCube != pCubeNext; pCube = pCube->pNext )
            if ( pCube->lLits.pTail && pCube->lLits.pTail->iVar >= 2 * pData->nNodesOld )
                break;
        if ( pCube != pCubeNext )
            Fxu_CreateCoversNode( p, pData, iNode, pCubeFirst, pCubeNext );
        // update the first cube
        pCubeFirst = pCubeNext;
    }

    // add the covers for the extracted nodes
    for ( n = 0; n < pData->nNodesNew; n++ )
    {
        // get the number of this node
        iNode = pData->nNodesOld + n;
        // get the next first cube
        pCubeNext = Fxu_CreateCoversFirstCube( p, pData, iNode + 1 );
        // the node should be added
        Fxu_CreateCoversNode( p, pData, iNode, pCubeFirst, pCubeNext );
        // update the first cube
        pCubeFirst = pCubeNext;
    }
}

ABC_NAMESPACE_IMPL_START Fxu_Matrix* Fxu_CreateMatrix

(

Fxu_Data_t *

pData

)

DECLARATIONS ///.

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

FileName [fxu.c]

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

Synopsis [The entrance into the fast extract module.]

Author [MVSIS Group]

Affiliation [UC Berkeley]

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

Revision [

Id:

fxu.c,v 1.0 2003/02/01 00:00:00 alanmi Exp

]

DECLARATIONS ///.

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

Synopsis [Creates the sparse matrix from the array of SOPs.]

Description []

SideEffects []

SeeAlso []

Definition at line 52 of file fxuCreate.c.

{
    Fxu_Matrix * p;
    Fxu_Var * pVar;
    Fxu_Cube * pCubeFirst, * pCubeNew;
    Fxu_Cube * pCube1, * pCube2;
    Vec_Int_t * vFanins;
    char * pSopCover;
    char * pSopCube;
    int * pOrder, nBitsMax;
    int i, v, c;
    int nCubesTotal;
    int nPairsTotal;
    int nPairsStore;
    int nCubes;
    int iCube, iPair;
    int nFanins;

    // collect all sorts of statistics
    nCubesTotal =  0;
    nPairsTotal =  0;
    nPairsStore =  0;
    nBitsMax    = -1; 
    for ( i = 0; i < pData->nNodesOld; i++ )
        if ( (pSopCover = (char *)pData->vSops->pArray[i]) )
        {
            nCubes       = Abc_SopGetCubeNum( pSopCover );
            nFanins      = Abc_SopGetVarNum( pSopCover );
            assert( nFanins > 1 && nCubes > 0 );

            nCubesTotal += nCubes;
            nPairsTotal += nCubes * (nCubes - 1) / 2;
            nPairsStore += nCubes * nCubes;
            if ( nBitsMax < nFanins )
                nBitsMax = nFanins;
        }
    if ( nBitsMax <= 0 )
    {
        printf( "The current network does not have SOPs to perform extraction.\n" );
        return NULL;
    }

    if ( nPairsStore > 50000000 )
    {
        printf( "The problem is too large to be solved by \"fxu\" (%d cubes and %d cube pairs)\n", nCubesTotal, nPairsStore );
        return NULL;
    }

    // start the matrix
    p = Fxu_MatrixAllocate();
    // create the column labels 
    p->ppVars = ABC_ALLOC( Fxu_Var *, 2 * (pData->nNodesOld + pData->nNodesExt) );
    for ( i = 0; i < 2 * pData->nNodesOld; i++ )
        p->ppVars[i] = Fxu_MatrixAddVar( p );

    // allocate storage for all cube pairs at once
    p->pppPairs = ABC_ALLOC( Fxu_Pair **, nCubesTotal + 100 );
    p->ppPairs  = ABC_ALLOC( Fxu_Pair *,  nPairsStore + 100 );
    memset( p->ppPairs, 0, sizeof(Fxu_Pair *) * nPairsStore );
    iCube = 0;
    iPair = 0;
    for ( i = 0; i < pData->nNodesOld; i++ )
        if ( (pSopCover = (char *)pData->vSops->pArray[i]) )
        {
            // get the number of cubes
            nCubes = Abc_SopGetCubeNum( pSopCover );
            // get the new var in the matrix
            pVar = p->ppVars[2*i+1];
            // assign the pair storage
            pVar->nCubes     = nCubes;
            if ( nCubes > 0 )
            {
                pVar->ppPairs    = p->pppPairs + iCube;
                pVar->ppPairs[0] = p->ppPairs  + iPair;
                for ( v = 1; v < nCubes; v++ )
                    pVar->ppPairs[v] = pVar->ppPairs[v-1] + nCubes;
            }
            // update
            iCube += nCubes;
            iPair += nCubes * nCubes;
        }
    assert( iCube == nCubesTotal );
    assert( iPair == nPairsStore );


    // allocate room for the reordered literals
    pOrder = ABC_ALLOC( int, nBitsMax );
    // create the rows
    for ( i = 0; i < pData->nNodesOld; i++ )
    if ( (pSopCover = (char *)pData->vSops->pArray[i]) )
    {
        // get the new var in the matrix
        pVar = p->ppVars[2*i+1];
        // here we sort the literals of the cover
        // in the increasing order of the numbers of the corresponding nodes
        // because literals should be added to the matrix in this order
        vFanins = (Vec_Int_t *)pData->vFanins->pArray[i];
        s_pLits = vFanins->pArray;
        // start the variable order
        nFanins = Abc_SopGetVarNum( pSopCover );
        for ( v = 0; v < nFanins; v++ )
            pOrder[v] = v;
        // reorder the fanins
        qsort( (void *)pOrder, nFanins, sizeof(int),(int (*)(const void *, const void *))Fxu_CreateMatrixLitCompare);
        assert( s_pLits[ pOrder[0] ] < s_pLits[ pOrder[nFanins-1] ] );
        // create the corresponding cubes in the matrix
        pCubeFirst = NULL;
        c = 0;
        Abc_SopForEachCube( pSopCover, nFanins, pSopCube )
        {
            // create the cube
            pCubeNew = Fxu_MatrixAddCube( p, pVar, c++ );
            Fxu_CreateMatrixAddCube( p, pCubeNew, pSopCube, vFanins, pOrder );
            if ( pCubeFirst == NULL )
                pCubeFirst = pCubeNew;
            pCubeNew->pFirst = pCubeFirst;
        }
        // set the first cube of this var
        pVar->pFirst = pCubeFirst;
        // create the divisors without preprocessing
        if ( nPairsTotal <= pData->nPairsMax )
        {
            for ( pCube1 = pCubeFirst; pCube1; pCube1 = pCube1->pNext )
                for ( pCube2 = pCube1? pCube1->pNext: NULL; pCube2; pCube2 = pCube2->pNext )
                    Fxu_MatrixAddDivisor( p, pCube1, pCube2 );
        }
    }
    ABC_FREE( pOrder );

    // consider the case when cube pairs should be preprocessed
    // before adding them to the set of divisors
//    if ( pData->fVerbose )
//        printf( "The total number of cube pairs is %d.\n", nPairsTotal );
    if ( nPairsTotal > 10000000 )
    {
        printf( "The total number of cube pairs of the network is more than 10,000,000.\n" );
        printf( "Command \"fx\" takes a long time to run in such cases. It is suggested\n" );
        printf( "that the user changes the network by reducing the size of logic node and\n" );
        printf( "consequently the number of cube pairs to be processed by this command.\n" );
        printf( "It can be achieved as follows: \"st; if -K <num>\" or \"st; renode -s -K <num>\"\n" );
        printf( "as a proprocessing step, while selecting <num> as approapriate.\n" );
        return NULL;
    }
    if ( nPairsTotal > pData->nPairsMax )
        if ( !Fxu_PreprocessCubePairs( p, pData->vSops, nPairsTotal, pData->nPairsMax ) )
            return NULL;
//    if ( pData->fVerbose )
//        printf( "Only %d best cube pairs will be used by the fast extract command.\n", pData->nPairsMax );

    if ( p->lVars.nItems > 1000000 )
    {
        printf( "The total number of variables is more than 1,000,000.\n" );
        printf( "Command \"fx\" takes a long time to run in such cases. It is suggested\n" );
        printf( "that the user changes the network by reducing the size of logic node and\n" );
        printf( "consequently the number of cube pairs to be processed by this command.\n" );
        printf( "It can be achieved as follows: \"st; if -K <num>\" or \"st; renode -s -K <num>\"\n" );
        printf( "as a proprocessing step, while selecting <num> as approapriate.\n" );
        return NULL;
    }


    // add the var pairs to the heap
    Fxu_MatrixComputeSingles( p, pData->fUse0, pData->nSingleMax );

    // print stats
    if ( pData->fVerbose )
    {
        double Density;
        Density = ((double)p->nEntries) / p->lVars.nItems / p->lCubes.nItems;
        fprintf( stdout, "Matrix: [vars x cubes] = [%d x %d]  ",
            p->lVars.nItems, p->lCubes.nItems );
        fprintf( stdout, "Lits = %d  Density = %.5f%%\n", 
            p->nEntries, Density );
        fprintf( stdout, "1-cube divs = %6d. (Total = %6d)  ",  p->lSingles.nItems, p->nSingleTotal );
        fprintf( stdout, "2-cube divs = %6d. (Total = %6d)",  p->nDivsTotal, nPairsTotal );
        fprintf( stdout, "\n" );
    }
//    Fxu_MatrixPrint( stdout, p );
    return p;
}

int Fxu_FastExtract

(

Fxu_Data_t *

pData

)

FUNCTION DEFINITIONS ///.

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

Synopsis [Performs fast_extract on a set of covers.]

Description [All the covers are given in the array p->vSops. The resulting covers are returned in the array p->vSopsNew. The entries in these arrays correspond to objects in the network. The entries corresponding to the PI and objects with trivial covers are NULL. The number of extracted covers (not exceeding p->nNodesExt) is returned. Two other things are important for the correct operation of this procedure: (1) The input covers do not have duplicated fanins and are SCC-free. (2) The fanins array contains the numbers of the fanin objects.]

SideEffects []

SeeAlso []

Definition at line 58 of file fxu.c.

{
    int fScrollLines = 0;
    Fxu_Matrix * p;
    Fxu_Single * pSingle;
    Fxu_Double * pDouble;
    int Weight1, Weight2, Weight3;
    int Counter = 0;

    s_MemoryTotal = 0;
    s_MemoryPeak  = 0;

    // create the matrix
    p = Fxu_CreateMatrix( pData );
    if ( p == NULL )
        return -1;
//    if ( pData->fVerbose )
//        printf( "Memory usage after construction: Total = %d. Peak = %d.\n", s_MemoryTotal, s_MemoryPeak );
//Fxu_MatrixPrint( NULL, p );

    if ( pData->fOnlyS )
    {
        pData->nNodesNew = 0;
        do
        {
            Weight1 = Fxu_HeapSingleReadMaxWeight( p->pHeapSingle );
            if ( pData->fVerbose )
                printf( "Div %5d : Best single = %5d.%s", Counter++, Weight1, fScrollLines?"\n":"\r" );
            if ( Weight1 > pData->WeightMin || (Weight1 == 0 && pData->fUse0) )
                Fxu_UpdateSingle( p );
            else
                break;
        }
        while ( ++pData->nNodesNew < pData->nNodesExt );
    }
    else if ( pData->fOnlyD )
    {
        pData->nNodesNew = 0;
        do
        {
            Weight2 = Fxu_HeapDoubleReadMaxWeight( p->pHeapDouble );
            if ( pData->fVerbose )
                printf( "Div %5d : Best double = %5d.%s", Counter++, Weight2, fScrollLines?"\n":"\r" );
            if ( Weight2 > pData->WeightMin || (Weight2 == 0 && pData->fUse0) )
                Fxu_UpdateDouble( p );
            else
                break;
        }
        while ( ++pData->nNodesNew < pData->nNodesExt );
    }
    else if ( !pData->fUseCompl )
    {
        pData->nNodesNew = 0;
        do
        {
            Weight1 = Fxu_HeapSingleReadMaxWeight( p->pHeapSingle );
            Weight2 = Fxu_HeapDoubleReadMaxWeight( p->pHeapDouble );

            if ( pData->fVerbose )
                printf( "Div %5d : Best double = %5d. Best single = %5d.%s", Counter++, Weight2, Weight1, fScrollLines?"\n":"\r" );
//Fxu_Select( p, &pSingle, &pDouble );

            if ( Weight1 >= Weight2 )
            {
                if ( Weight1 > pData->WeightMin || (Weight1 == 0 && pData->fUse0) )
                    Fxu_UpdateSingle( p );
                else
                    break;
            }
            else
            {
                if ( Weight2 > pData->WeightMin || (Weight2 == 0 && pData->fUse0) )
                    Fxu_UpdateDouble( p );
                else
                    break;
            }
        }
        while ( ++pData->nNodesNew < pData->nNodesExt );
    }
    else
    { // use the complement
        pData->nNodesNew = 0;
        do
        {
            Weight1 = Fxu_HeapSingleReadMaxWeight( p->pHeapSingle );
            Weight2 = Fxu_HeapDoubleReadMaxWeight( p->pHeapDouble );

            // select the best single and double
            Weight3 = Fxu_Select( p, &pSingle, &pDouble );
            if ( pData->fVerbose )
                printf( "Div %5d : Best double = %5d. Best single = %5d. Best complement = %5d.%s", 
                    Counter++, Weight2, Weight1, Weight3, fScrollLines?"\n":"\r" );

            if ( Weight3 > pData->WeightMin || (Weight3 == 0 && pData->fUse0) )
                Fxu_Update( p, pSingle, pDouble );
            else
                break;
        }
        while ( ++pData->nNodesNew < pData->nNodesExt );
    }

    if ( pData->fVerbose )
        printf( "Total single = %3d. Total double = %3d. Total compl = %3d.                    \n", 
        p->nDivs1, p->nDivs2, p->nDivs3 );

    // create the new covers
    if ( pData->nNodesNew )
        Fxu_CreateCovers( p, pData );
    Fxu_MatrixDelete( p );
//    printf( "Memory usage after deallocation:   Total = %d. Peak = %d.\n", s_MemoryTotal, s_MemoryPeak );
    if ( pData->nNodesNew == pData->nNodesExt )
        printf( "Warning: The limit on the number of extracted divisors has been reached.\n" );
    return pData->nNodesNew;
}

void Fxu_MatrixRingCubesUnmark

(

Fxu_Matrix *

p

)

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

Synopsis [Unmarks the cubes in the ring.]

Description []

SideEffects []

SeeAlso []

Definition at line 185 of file fxu.c.

{
    Fxu_Cube * pCube, * pCube2;
    // unmark the cubes
    Fxu_MatrixForEachCubeInRingSafe( p, pCube, pCube2 )
        pCube->pOrder = NULL;
    Fxu_MatrixRingCubesReset( p );
}

void Fxu_MatrixRingVarsUnmark

(

Fxu_Matrix *

p

)

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

Synopsis [Unmarks the vars in the ring.]

Description []

SideEffects []

SeeAlso []

Definition at line 206 of file fxu.c.

{
    Fxu_Var * pVar, * pVar2;
    // unmark the vars
    Fxu_MatrixForEachVarInRingSafe( p, pVar, pVar2 )
        pVar->pOrder = NULL;
    Fxu_MatrixRingVarsReset( p );
}

char* Fxu_MemFetch	(	Fxu_Matrix *	p,
		int	nBytes
	)

FUNCTION DEFINITIONS ///.

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 227 of file fxu.c.

{
    s_MemoryTotal += nBytes;
    if ( s_MemoryPeak < s_MemoryTotal )
        s_MemoryPeak = s_MemoryTotal;
//    return ABC_ALLOC( char, nBytes );
    return Extra_MmFixedEntryFetch( p->pMemMan );
}

void Fxu_MemRecycle	(	Fxu_Matrix *	p,
		char *	pItem,
		int	nBytes
	)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 247 of file fxu.c.

{
    s_MemoryTotal -= nBytes;
//    ABC_FREE( pItem );
    Extra_MmFixedEntryRecycle( p->pMemMan, pItem );
}

Variable Documentation

int s_MemoryPeak

static

Definition at line 34 of file fxu.c.

int s_MemoryTotal

static

Definition at line 33 of file fxu.c.