src/map/mapper/mapperTable.c File Reference

#include "mapperInt.h"
Include dependency graph for mapperTable.c:

Go to the source code of this file.

Defines

#define MAP_TABLE_HASH(u1, u2, nSize)   (((u1) + 2003 * (u2)) % nSize)

Functions

static void Map_SuperTableResize (Map_HashTable_t *pLib)
Map_HashTable_t * Map_SuperTableCreate (Map_SuperLib_t *pLib)
void Map_SuperTableFree (Map_HashTable_t *p)
int Map_SuperTableInsertC (Map_HashTable_t *p, unsigned uTruthC[], Map_Super_t *pGate)
int Map_SuperTableInsert (Map_HashTable_t *p, unsigned uTruth[], Map_Super_t *pGate, unsigned uPhase)
Map_Super_t * Map_SuperTableLookupC (Map_SuperLib_t *p, unsigned uTruth[])
Map_Super_t * Map_SuperTableLookup (Map_HashTable_t *p, unsigned uTruth[], unsigned *puPhase)
int Map_SuperTableCompareSupergates (Map_Super_t **ppS1, Map_Super_t **ppS2)
int Map_SuperTableCompareGatesInList (Map_Super_t **ppS1, Map_Super_t **ppS2)
void Map_SuperTableSortSupergates (Map_HashTable_t *p, int nSupersMax)
void Map_SuperTableSortSupergatesByDelay (Map_HashTable_t *p, int nSupersMax)

Define Documentation

#define MAP_TABLE_HASH ( u1,
u2,
nSize   )     (((u1) + 2003 * (u2)) % nSize)

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

FileName [mapperTable.c]

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

Synopsis [Generic technology mapping engine.]

Author [MVSIS Group]

Affiliation [UC Berkeley]

Date [Ver. 2.0. Started - June 1, 2004.]

Revision [

Id
mapperTable.c,v 1.6 2005/01/23 06:59:44 alanmi Exp

] DECLARATIONS ///

Definition at line 26 of file mapperTable.c.

Function Documentation

int Map_SuperTableCompareGatesInList ( Map_Super_t **  ppS1,
Map_Super_t **  ppS2 
)

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

Synopsis [Compares the supergates by the number of times they are used.]

Description []

SideEffects []

SeeAlso []

Definition at line 290 of file mapperTable.c.

00291 {
00292 //   if ( (*ppS1)->tDelayMax.Rise > (*ppS2)->tDelayMax.Rise )
00293     if ( (*ppS1)->Area > (*ppS2)->Area )
00294         return -1;
00295 //   if ( (*ppS1)->tDelayMax.Rise < (*ppS2)->tDelayMax.Rise )
00296     if ( (*ppS1)->Area < (*ppS2)->Area )
00297         return 1;
00298     return 0;
00299 }

int Map_SuperTableCompareSupergates ( Map_Super_t **  ppS1,
Map_Super_t **  ppS2 
)

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

Synopsis [Compares the supergates by the number of times they are used.]

Description []

SideEffects []

SeeAlso []

Definition at line 270 of file mapperTable.c.

00271 {
00272     if ( (*ppS1)->nUsed > (*ppS2)->nUsed )
00273         return -1;
00274     if ( (*ppS1)->nUsed < (*ppS2)->nUsed )
00275         return 1;
00276     return 0;
00277 }

Map_HashTable_t* Map_SuperTableCreate ( Map_SuperLib_t *  pLib  ) 

FUNCTION DEFINITIONS ///Function*************************************************************

Synopsis [Creates the hash table for supergates.]

Description []

SideEffects []

SeeAlso []

Definition at line 45 of file mapperTable.c.

00046 {
00047     Map_HashTable_t * p;
00048     // allocate the table
00049     p = ALLOC( Map_HashTable_t, 1 );
00050     memset( p, 0, sizeof(Map_HashTable_t) );
00051     p->mmMan = pLib->mmEntries;
00052     // allocate and clean the bins
00053     p->nBins = Cudd_Prime(20000);
00054     p->pBins = ALLOC( Map_HashEntry_t *, p->nBins );
00055     memset( p->pBins, 0, sizeof(Map_HashEntry_t *) * p->nBins );
00056     return p;
00057 }

void Map_SuperTableFree ( Map_HashTable_t *  p  ) 

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

Synopsis [Deallocates the supergate hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 71 of file mapperTable.c.

00072 {
00073     FREE( p->pBins );
00074     FREE( p );
00075 }

int Map_SuperTableInsert ( Map_HashTable_t *  p,
unsigned  uTruth[],
Map_Super_t *  pGate,
unsigned  uPhase 
)

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

Synopsis [Inserts a new entry into the library.]

Description [This function inserts the new gate (pGate), which will be accessible through its unfolded function (uTruth).]

SideEffects []

SeeAlso []

Definition at line 134 of file mapperTable.c.

00135 {
00136     Map_HashEntry_t * pEnt;
00137     unsigned Key;
00138     // resize the table
00139     if ( p->nEntries >= 2 * p->nBins )
00140         Map_SuperTableResize( p );
00141     // check if this entry already exists
00142     Key = MAP_TABLE_HASH( uTruth[0], uTruth[1], p->nBins );
00143     for ( pEnt = p->pBins[Key]; pEnt; pEnt = pEnt->pNext )
00144         if ( pEnt->uTruth[0] == uTruth[0] && pEnt->uTruth[1] == uTruth[1] )
00145             return 1;
00146     // add the new hash table entry to the table
00147     pEnt = (Map_HashEntry_t *)Extra_MmFixedEntryFetch( p->mmMan );
00148     memset( pEnt, 0, sizeof(Map_HashEntry_t) );
00149     pEnt->uTruth[0] = uTruth[0];
00150     pEnt->uTruth[1] = uTruth[1];
00151     pEnt->pGates    = pGate;
00152     pEnt->uPhase    = uPhase;
00153     // add the hash table to the corresponding linked list in the table
00154     pEnt->pNext   = p->pBins[Key];
00155     p->pBins[Key] = pEnt;
00156     p->nEntries++;
00157 /*
00158 printf( "Adding gate: %10u ", Key );
00159 Map_LibraryPrintSupergate( pGate );
00160 Extra_PrintBinary( stdout, uTruth, 32 );
00161 printf( "\n" );
00162 */
00163     return 0;
00164 }

int Map_SuperTableInsertC ( Map_HashTable_t *  p,
unsigned  uTruthC[],
Map_Super_t *  pGate 
)

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

Synopsis [Inserts a new entry into the hash table.]

Description [This function inserts the new gate (pGate), which will be accessible through its canonical form (uTruthC).]

SideEffects []

SeeAlso []

Definition at line 89 of file mapperTable.c.

00090 {
00091     Map_HashEntry_t * pEnt;
00092     unsigned Key;
00093     // resize the table
00094     if ( p->nEntries >= 2 * p->nBins )
00095         Map_SuperTableResize( p );
00096     // check if another supergate with the same canonical form exists
00097     Key = MAP_TABLE_HASH( uTruthC[0], uTruthC[1], p->nBins );
00098     for ( pEnt = p->pBins[Key]; pEnt; pEnt = pEnt->pNext )
00099         if ( pEnt->uTruth[0] == uTruthC[0] && pEnt->uTruth[1] == uTruthC[1] )
00100             break;
00101     // create a new entry if it does not exist
00102     if ( pEnt == NULL )
00103     {
00104         // add the new entry to the table
00105         pEnt = (Map_HashEntry_t *)Extra_MmFixedEntryFetch( p->mmMan );
00106         memset( pEnt, 0, sizeof(Map_HashEntry_t) );
00107         pEnt->uTruth[0] = uTruthC[0];
00108         pEnt->uTruth[1] = uTruthC[1];
00109         // add the hash table entry to the corresponding linked list in the table
00110         pEnt->pNext   = p->pBins[Key];
00111         p->pBins[Key] = pEnt;
00112         p->nEntries++;
00113     }
00114     // add the supergate to the entry
00115     pGate->pNext = pEnt->pGates;
00116     pEnt->pGates = pGate;
00117     return 0;
00118 }

Map_Super_t* Map_SuperTableLookup ( Map_HashTable_t *  p,
unsigned  uTruth[],
unsigned *  puPhase 
)

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

Synopsis [Looks up an entry in the library.]

Description [This function looks up the function, given by its truth table, and return two things: (1) the linked list of supergates, which can implement the functions of this N-class; (2) the phase, which should be applied to the given function, in order to derive the canonical form of this N-class.]

SideEffects []

SeeAlso []

Definition at line 205 of file mapperTable.c.

00206 {
00207     Map_HashEntry_t * pEnt;
00208     unsigned Key;
00209     Key = MAP_TABLE_HASH( uTruth[0], uTruth[1], p->nBins );
00210     for ( pEnt = p->pBins[Key]; pEnt; pEnt = pEnt->pNext )
00211         if ( pEnt->uTruth[0] == uTruth[0] && pEnt->uTruth[1] == uTruth[1] )
00212         {
00213             *puPhase = pEnt->uPhase;
00214             return pEnt->pGates;
00215         }
00216     return NULL;
00217 }

Map_Super_t* Map_SuperTableLookupC ( Map_SuperLib_t *  p,
unsigned  uTruth[] 
)

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

Synopsis [Looks up an entry in the library.]

Description [This function looks up the function, given by its truth table, and return two things: (1) the linked list of supergates, which can implement the functions of this N-class; (2) the phase, which should be applied to the given function, in order to derive the canonical form of this N-class.]

SideEffects []

SeeAlso []

Definition at line 180 of file mapperTable.c.

00181 {
00182     Map_HashEntry_t * pEnt;
00183     unsigned Key;
00184     Key = MAP_TABLE_HASH( uTruth[0], uTruth[1], p->tTableC->nBins );
00185     for ( pEnt = p->tTableC->pBins[Key]; pEnt; pEnt = pEnt->pNext )
00186         if ( pEnt->uTruth[0] == uTruth[0] && pEnt->uTruth[1] == uTruth[1] )
00187             return pEnt->pGates;
00188     return NULL;
00189 }

void Map_SuperTableResize ( Map_HashTable_t *  p  )  [static]

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

Synopsis [Resizes the table.]

Description []

SideEffects []

SeeAlso []

Definition at line 230 of file mapperTable.c.

00231 {
00232     Map_HashEntry_t ** pBinsNew;
00233     Map_HashEntry_t * pEnt, * pEnt2;
00234     int nBinsNew, Counter, i, clk = clock();
00235     unsigned Key;
00236     // get the new table size
00237     nBinsNew = Cudd_Prime(2 * p->nBins); 
00238     // allocate a new array
00239     pBinsNew = ALLOC( Map_HashEntry_t *, nBinsNew );
00240     memset( pBinsNew, 0, sizeof(Map_HashEntry_t *) * nBinsNew );
00241     // rehash the entries from the old table
00242     Counter = 0;
00243     for ( i = 0; i < p->nBins; i++ )
00244         for ( pEnt = p->pBins[i], pEnt2 = pEnt? pEnt->pNext: NULL; pEnt; 
00245               pEnt = pEnt2, pEnt2 = pEnt? pEnt->pNext: NULL )
00246         {
00247             Key = MAP_TABLE_HASH( pEnt->uTruth[0], pEnt->uTruth[1], nBinsNew );
00248             pEnt->pNext   = pBinsNew[Key];
00249             pBinsNew[Key] = pEnt;
00250             Counter++;
00251         }
00252     assert( Counter == p->nEntries );
00253     // replace the table and the parameters
00254     free( p->pBins );
00255     p->pBins = pBinsNew;
00256     p->nBins = nBinsNew;
00257 }

void Map_SuperTableSortSupergates ( Map_HashTable_t *  p,
int  nSupersMax 
)

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

Synopsis [Sorts supergates by usefulness and prints out most useful.]

Description []

SideEffects []

SeeAlso []

Definition at line 312 of file mapperTable.c.

00313 {
00314     Map_HashEntry_t * pEnt;
00315     Map_Super_t ** ppSupers;
00316     Map_Super_t * pSuper;
00317     int nSupers, i;
00318 
00319     // copy all the supergates into one array
00320     ppSupers = ALLOC( Map_Super_t *, nSupersMax );
00321     nSupers = 0;
00322     for ( i = 0; i < p->nBins; i++ )
00323         for ( pEnt = p->pBins[i]; pEnt; pEnt = pEnt->pNext )
00324             for ( pSuper = pEnt->pGates; pSuper; pSuper = pSuper->pNext )
00325                 ppSupers[nSupers++] = pSuper;
00326 
00327     // sort by usage
00328     qsort( (void *)ppSupers, nSupers, sizeof(Map_Super_t *), 
00329             (int (*)(const void *, const void *)) Map_SuperTableCompareSupergates );
00330     assert( Map_SuperTableCompareSupergates( ppSupers, ppSupers + nSupers - 1 ) <= 0 );
00331 
00332     // print out the "top ten"
00333 //    for ( i = 0; i < nSupers; i++ )
00334     for ( i = 0; i < 10; i++ )
00335     {
00336         if ( ppSupers[i]->nUsed == 0 )
00337             break;
00338         printf( "%5d : ",        ppSupers[i]->nUsed );
00339         printf( "%5d   ",        ppSupers[i]->Num );
00340         printf( "A = %5.2f   ",  ppSupers[i]->Area );
00341         printf( "D = %5.2f   ",  ppSupers[i]->tDelayMax.Rise );
00342         printf( "%s",            ppSupers[i]->pFormula );
00343         printf( "\n" );
00344     }
00345     free( ppSupers );
00346 }

void Map_SuperTableSortSupergatesByDelay ( Map_HashTable_t *  p,
int  nSupersMax 
)

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

Synopsis [Sorts supergates by max delay for each truth table.]

Description []

SideEffects []

SeeAlso []

Definition at line 359 of file mapperTable.c.

00360 {
00361     Map_HashEntry_t * pEnt;
00362     Map_Super_t ** ppSupers;
00363     Map_Super_t * pSuper;
00364     int nSupers, i, k;
00365 
00366     ppSupers = ALLOC( Map_Super_t *, nSupersMax );
00367     for ( i = 0; i < p->nBins; i++ )
00368         for ( pEnt = p->pBins[i]; pEnt; pEnt = pEnt->pNext )
00369         {
00370             // collect the gates in this entry
00371             nSupers = 0;
00372             for ( pSuper = pEnt->pGates; pSuper; pSuper = pSuper->pNext )
00373             {
00374                 // skip supergates, whose root is the AND gate
00375 //                if ( strcmp( Mio_GateReadName(pSuper->pRoot), "and" ) == 0 )
00376 //                    continue;
00377                 ppSupers[nSupers++] = pSuper;
00378             }
00379             pEnt->pGates = NULL;
00380             if ( nSupers == 0 )
00381                 continue;
00382             // sort the gates by delay
00383             qsort( (void *)ppSupers, nSupers, sizeof(Map_Super_t *), 
00384                     (int (*)(const void *, const void *)) Map_SuperTableCompareGatesInList );
00385             assert( Map_SuperTableCompareGatesInList( ppSupers, ppSupers + nSupers - 1 ) <= 0 );
00386             // link them in the reverse order
00387             for ( k = 0; k < nSupers; k++ )
00388             {
00389                 ppSupers[k]->pNext = pEnt->pGates;
00390                 pEnt->pGates = ppSupers[k];
00391             }
00392             // save the number of supergates in the list
00393             pEnt->pGates->nSupers = nSupers;
00394         }
00395     FREE( ppSupers );
00396 }

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