src/opt/fxu/fxu.c File Reference

#include "fxuInt.h"
#include "fxu.h"
Include dependency graph for fxu.c:

Go to the source code of this file.

Functions

Fxu_Matrix * Fxu_CreateMatrix (Fxu_Data_t *pData)
void Fxu_CreateCovers (Fxu_Matrix *p, Fxu_Data_t *pData)
int Fxu_FastExtract (Fxu_Data_t *pData)
void Fxu_MatrixRingCubesUnmark (Fxu_Matrix *p)
void Fxu_MatrixRingVarsUnmark (Fxu_Matrix *p)
char * Fxu_MemFetch (Fxu_Matrix *p, int nBytes)
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 264 of file fxuCreate.c.

00265 {
00266     Fxu_Cube * pCube, * pCubeFirst, * pCubeNext;
00267     char * pSopCover;
00268     int iNode, n;
00269 
00270     // get the first cube of the first internal node 
00271     pCubeFirst = Fxu_CreateCoversFirstCube( p, pData, 0 );
00272 
00273     // go through the internal nodes
00274     for ( n = 0; n < pData->nNodesOld; n++ )
00275     if ( pSopCover = pData->vSops->pArray[n] )
00276     {
00277         // get the number of this node
00278         iNode = n;
00279         // get the next first cube
00280         pCubeNext = Fxu_CreateCoversFirstCube(  p, pData, iNode + 1 );
00281         // check if there any new variables in these cubes
00282         for ( pCube = pCubeFirst; pCube != pCubeNext; pCube = pCube->pNext )
00283             if ( pCube->lLits.pTail && pCube->lLits.pTail->iVar >= 2 * pData->nNodesOld )
00284                 break;
00285         if ( pCube != pCubeNext )
00286             Fxu_CreateCoversNode( p, pData, iNode, pCubeFirst, pCubeNext );
00287         // update the first cube
00288         pCubeFirst = pCubeNext;
00289     }
00290 
00291     // add the covers for the extracted nodes
00292     for ( n = 0; n < pData->nNodesNew; n++ )
00293     {
00294         // get the number of this node
00295         iNode = pData->nNodesOld + n;
00296         // get the next first cube
00297         pCubeNext = Fxu_CreateCoversFirstCube( p, pData, iNode + 1 );
00298         // the node should be added
00299         Fxu_CreateCoversNode( p, pData, iNode, pCubeFirst, pCubeNext );
00300         // update the first cube
00301         pCubeFirst = pCubeNext;
00302     }
00303 }

Fxu_Matrix* Fxu_CreateMatrix ( Fxu_Data_t *  pData  ) 

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 DEFINITIONS ///Function*************************************************************

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

Description []

SideEffects []

SeeAlso []

Definition at line 50 of file fxuCreate.c.

00051 {
00052     Fxu_Matrix * p;
00053     Fxu_Var * pVar;
00054     Fxu_Cube * pCubeFirst, * pCubeNew;
00055     Fxu_Cube * pCube1, * pCube2;
00056     Vec_Int_t * vFanins;
00057     char * pSopCover;
00058     char * pSopCube;
00059     int * pOrder, nBitsMax;
00060     int i, v, c;
00061     int nCubesTotal;
00062     int nPairsTotal;
00063     int nPairsStore;
00064     int nCubes;
00065     int iCube, iPair;
00066     int nFanins;
00067 
00068     // collect all sorts of statistics
00069     nCubesTotal =  0;
00070     nPairsTotal =  0;
00071     nPairsStore =  0;
00072     nBitsMax    = -1; 
00073     for ( i = 0; i < pData->nNodesOld; i++ )
00074         if ( pSopCover = pData->vSops->pArray[i] )
00075         {
00076             nCubes       = Abc_SopGetCubeNum( pSopCover );
00077             nFanins      = Abc_SopGetVarNum( pSopCover );
00078             assert( nFanins > 1 && nCubes > 0 );
00079 
00080             nCubesTotal += nCubes;
00081             nPairsTotal += nCubes * (nCubes - 1) / 2;
00082             nPairsStore += nCubes * nCubes;
00083             if ( nBitsMax < nFanins )
00084                 nBitsMax = nFanins;
00085         }
00086     if ( nBitsMax <= 0 )
00087     {
00088         printf( "The current network does not have SOPs to perform extraction.\n" );
00089         return NULL;
00090     }
00091 
00092     if ( nPairsStore > 50000000 )
00093     {
00094         printf( "The problem is too large to be solved by \"fxu\" (%d cubes and %d cube pairs)\n", nCubesTotal, nPairsStore );
00095         return NULL;
00096     }
00097 
00098     // start the matrix
00099         p = Fxu_MatrixAllocate();
00100     // create the column labels 
00101     p->ppVars = ALLOC( Fxu_Var *, 2 * (pData->nNodesOld + pData->nNodesExt) );
00102     for ( i = 0; i < 2 * pData->nNodesOld; i++ )
00103         p->ppVars[i] = Fxu_MatrixAddVar( p );
00104 
00105     // allocate storage for all cube pairs at once
00106     p->pppPairs = ALLOC( Fxu_Pair **, nCubesTotal + 100 );
00107     p->ppPairs  = ALLOC( Fxu_Pair *,  nPairsStore + 100 );
00108     memset( p->ppPairs, 0, sizeof(Fxu_Pair *) * nPairsStore );
00109     iCube = 0;
00110     iPair = 0;
00111     for ( i = 0; i < pData->nNodesOld; i++ )
00112         if ( pSopCover = pData->vSops->pArray[i] )
00113         {
00114             // get the number of cubes
00115             nCubes = Abc_SopGetCubeNum( pSopCover );
00116             // get the new var in the matrix
00117             pVar = p->ppVars[2*i+1];
00118             // assign the pair storage
00119             pVar->nCubes     = nCubes;
00120             if ( nCubes > 0 )
00121             {
00122                 pVar->ppPairs    = p->pppPairs + iCube;
00123                 pVar->ppPairs[0] = p->ppPairs  + iPair;
00124                 for ( v = 1; v < nCubes; v++ )
00125                     pVar->ppPairs[v] = pVar->ppPairs[v-1] + nCubes;
00126             }
00127             // update
00128             iCube += nCubes;
00129             iPair += nCubes * nCubes;
00130         }
00131     assert( iCube == nCubesTotal );
00132     assert( iPair == nPairsStore );
00133 
00134 
00135     // allocate room for the reordered literals
00136     pOrder = ALLOC( int, nBitsMax );
00137     // create the rows
00138     for ( i = 0; i < pData->nNodesOld; i++ )
00139     if ( pSopCover = pData->vSops->pArray[i] )
00140     {
00141         // get the new var in the matrix
00142         pVar = p->ppVars[2*i+1];
00143         // here we sort the literals of the cover
00144         // in the increasing order of the numbers of the corresponding nodes
00145         // because literals should be added to the matrix in this order
00146         vFanins = pData->vFanins->pArray[i];
00147         s_pLits = vFanins->pArray;
00148         // start the variable order
00149         nFanins = Abc_SopGetVarNum( pSopCover );
00150         for ( v = 0; v < nFanins; v++ )
00151             pOrder[v] = v;
00152         // reorder the fanins
00153         qsort( (void *)pOrder, nFanins, sizeof(int),(int (*)(const void *, const void *))Fxu_CreateMatrixLitCompare);
00154         assert( s_pLits[ pOrder[0] ] < s_pLits[ pOrder[nFanins-1] ] );
00155         // create the corresponding cubes in the matrix
00156         pCubeFirst = NULL;
00157         c = 0;
00158         Abc_SopForEachCube( pSopCover, nFanins, pSopCube )
00159         {
00160             // create the cube
00161                 pCubeNew = Fxu_MatrixAddCube( p, pVar, c++ );
00162             Fxu_CreateMatrixAddCube( p, pCubeNew, pSopCube, vFanins, pOrder );
00163             if ( pCubeFirst == NULL )
00164                 pCubeFirst = pCubeNew;
00165             pCubeNew->pFirst = pCubeFirst;
00166         }
00167         // set the first cube of this var
00168         pVar->pFirst = pCubeFirst;
00169         // create the divisors without preprocessing
00170         if ( nPairsTotal <= pData->nPairsMax )
00171         {
00172                     for ( pCube1 = pCubeFirst; pCube1; pCube1 = pCube1->pNext )
00173                             for ( pCube2 = pCube1? pCube1->pNext: NULL; pCube2; pCube2 = pCube2->pNext )
00174                                     Fxu_MatrixAddDivisor( p, pCube1, pCube2 );
00175         }
00176     }
00177     FREE( pOrder );
00178 
00179     // consider the case when cube pairs should be preprocessed
00180     // before adding them to the set of divisors
00181 //    if ( pData->fVerbose )
00182 //        printf( "The total number of cube pairs is %d.\n", nPairsTotal );
00183     if ( nPairsTotal > 10000000 )
00184     {
00185         printf( "The total number of cube pairs of the network is more than 10,000,000.\n" );
00186         printf( "Command \"fx\" takes a long time to run in such cases. It is suggested\n" );
00187         printf( "that the user changes the network by reducing the size of logic node and\n" );
00188         printf( "consequently the number of cube pairs to be processed by this command.\n" );
00189         printf( "One way to achieve this is to run the commands \"st; multi -m -F <num>\"\n" );
00190         printf( "as a proprocessing step, while selecting <num> as approapriate.\n" );
00191         return NULL;
00192     }
00193     if ( nPairsTotal > pData->nPairsMax )
00194         if ( !Fxu_PreprocessCubePairs( p, pData->vSops, nPairsTotal, pData->nPairsMax ) )
00195             return NULL;
00196 //    if ( pData->fVerbose )
00197 //        printf( "Only %d best cube pairs will be used by the fast extract command.\n", pData->nPairsMax );
00198 
00199     // add the var pairs to the heap
00200     Fxu_MatrixComputeSingles( p, pData->fUse0, pData->nSingleMax );
00201 
00202     // print stats
00203     if ( pData->fVerbose )
00204     {
00205         double Density;
00206         Density = ((double)p->nEntries) / p->lVars.nItems / p->lCubes.nItems;
00207             fprintf( stdout, "Matrix: [vars x cubes] = [%d x %d]  ",
00208             p->lVars.nItems, p->lCubes.nItems );
00209             fprintf( stdout, "Lits = %d  Density = %.5f%%\n", 
00210             p->nEntries, Density );
00211             fprintf( stdout, "1-cube divs = %6d. (Total = %6d)  ",  p->lSingles.nItems, p->nSingleTotal );
00212             fprintf( stdout, "2-cube divs = %6d. (Total = %6d)",  p->nDivsTotal, nPairsTotal );
00213             fprintf( stdout, "\n" );
00214     }
00215 //    Fxu_MatrixPrint( stdout, p );
00216     return p;
00217 }

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 55 of file fxu.c.

00056 {
00057         Fxu_Matrix * p;
00058     Fxu_Single * pSingle;
00059     Fxu_Double * pDouble;
00060         int Weight1, Weight2, Weight3;
00061     int Counter = 0;
00062 
00063     s_MemoryTotal = 0;
00064     s_MemoryPeak  = 0;
00065 
00066         // create the matrix
00067         p = Fxu_CreateMatrix( pData );
00068     if ( p == NULL )
00069         return -1;
00070 //    if ( pData->fVerbose )
00071 //        printf( "Memory usage after construction: Total = %d. Peak = %d.\n", s_MemoryTotal, s_MemoryPeak );
00072 //Fxu_MatrixPrint( NULL, p );
00073 
00074     if ( pData->fOnlyS )
00075     {
00076         pData->nNodesNew = 0;
00077             do
00078         {
00079                     Weight1 = Fxu_HeapSingleReadMaxWeight( p->pHeapSingle );
00080             if ( pData->fVerbose )
00081                 printf( "Div %5d : Best single = %5d.\r", Counter++, Weight1 );
00082             if ( Weight1 > 0 || Weight1 == 0 && pData->fUse0 )
00083                             Fxu_UpdateSingle( p );
00084             else
00085                 break;
00086         }
00087         while ( ++pData->nNodesNew < pData->nNodesExt );
00088     }
00089     else if ( pData->fOnlyD )
00090     {
00091         pData->nNodesNew = 0;
00092             do
00093         {
00094                     Weight2 = Fxu_HeapDoubleReadMaxWeight( p->pHeapDouble );
00095             if ( pData->fVerbose )
00096                 printf( "Div %5d : Best double = %5d.\r", Counter++, Weight2 );
00097             if ( Weight2 > 0 || Weight2 == 0 && pData->fUse0 )
00098                             Fxu_UpdateDouble( p );
00099             else
00100                 break;
00101         }
00102         while ( ++pData->nNodesNew < pData->nNodesExt );
00103     }
00104     else if ( !pData->fUseCompl )
00105     {
00106         pData->nNodesNew = 0;
00107             do
00108         {
00109                     Weight1 = Fxu_HeapSingleReadMaxWeight( p->pHeapSingle );
00110                     Weight2 = Fxu_HeapDoubleReadMaxWeight( p->pHeapDouble );
00111 
00112             if ( pData->fVerbose )
00113                 printf( "Div %5d : Best double = %5d. Best single = %5d.\r", Counter++, Weight2, Weight1 );
00114 //Fxu_Select( p, &pSingle, &pDouble );
00115 
00116             if ( Weight1 >= Weight2 )
00117             {
00118                 if ( Weight1 > 0 || Weight1 == 0 && pData->fUse0 )
00119                                 Fxu_UpdateSingle( p );
00120                 else
00121                     break;
00122             }
00123             else
00124             {
00125                 if ( Weight2 > 0 || Weight2 == 0 && pData->fUse0 )
00126                                 Fxu_UpdateDouble( p );
00127                 else
00128                     break;
00129             }
00130         }
00131         while ( ++pData->nNodesNew < pData->nNodesExt );
00132     }
00133     else
00134     { // use the complement
00135         pData->nNodesNew = 0;
00136             do
00137         {
00138                     Weight1 = Fxu_HeapSingleReadMaxWeight( p->pHeapSingle );
00139                     Weight2 = Fxu_HeapDoubleReadMaxWeight( p->pHeapDouble );
00140 
00141             // select the best single and double
00142             Weight3 = Fxu_Select( p, &pSingle, &pDouble );
00143             if ( pData->fVerbose )
00144                 printf( "Div %5d : Best double = %5d. Best single = %5d. Best complement = %5d.\r", 
00145                     Counter++, Weight2, Weight1, Weight3 );
00146 
00147             if ( Weight3 > 0 || Weight3 == 0 && pData->fUse0 )
00148                 Fxu_Update( p, pSingle, pDouble );
00149             else
00150                 break;
00151         }
00152         while ( ++pData->nNodesNew < pData->nNodesExt );
00153     }
00154 
00155     if ( pData->fVerbose )
00156         printf( "Total single = %3d. Total double = %3d. Total compl = %3d.                    \n", 
00157         p->nDivs1, p->nDivs2, p->nDivs3 );
00158 
00159     // create the new covers
00160     if ( pData->nNodesNew )
00161         Fxu_CreateCovers( p, pData );
00162         Fxu_MatrixDelete( p );
00163 //    printf( "Memory usage after deallocation:   Total = %d. Peak = %d.\n", s_MemoryTotal, s_MemoryPeak );
00164     if ( pData->nNodesNew == pData->nNodesExt )
00165         printf( "Warning: The limit on the number of extracted divisors has been reached.\n" );
00166     return pData->nNodesNew;
00167 }

void Fxu_MatrixRingCubesUnmark ( Fxu_Matrix *  p  ) 

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

Synopsis [Unmarks the cubes in the ring.]

Description []

SideEffects []

SeeAlso []

Definition at line 181 of file fxu.c.

00182 {
00183         Fxu_Cube * pCube, * pCube2;
00184     // unmark the cubes
00185     Fxu_MatrixForEachCubeInRingSafe( p, pCube, pCube2 )
00186         pCube->pOrder = NULL;
00187     Fxu_MatrixRingCubesReset( p );
00188 }

void Fxu_MatrixRingVarsUnmark ( Fxu_Matrix *  p  ) 

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

Synopsis [Unmarks the vars in the ring.]

Description []

SideEffects []

SeeAlso []

Definition at line 202 of file fxu.c.

00203 {
00204         Fxu_Var * pVar, * pVar2;
00205     // unmark the vars
00206     Fxu_MatrixForEachVarInRingSafe( p, pVar, pVar2 )
00207         pVar->pOrder = NULL;
00208     Fxu_MatrixRingVarsReset( p );
00209 }

char* Fxu_MemFetch ( Fxu_Matrix *  p,
int  nBytes 
)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 223 of file fxu.c.

00224 {
00225     s_MemoryTotal += nBytes;
00226     if ( s_MemoryPeak < s_MemoryTotal )
00227         s_MemoryPeak = s_MemoryTotal;
00228 //    return malloc( nBytes );
00229     return Extra_MmFixedEntryFetch( p->pMemMan );
00230 }

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

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 243 of file fxu.c.

00244 {
00245     s_MemoryTotal -= nBytes;
00246 //    free( pItem );
00247     Extra_MmFixedEntryRecycle( p->pMemMan, pItem );
00248 }

Variable Documentation

int s_MemoryPeak [static]

Definition at line 31 of file fxu.c.

int s_MemoryTotal [static]

Definition at line 30 of file fxu.c.

Generated on Tue Jan 5 12:19:25 2010 for abc70930 by  doxygen 1.6.1