src/map/mapper/mapperUtils.c File Reference

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

Go to the source code of this file.

Defines

#define MAP_CO_LIST_SIZE   5

Functions

static void Map_MappingDfs_rec (Map_Node_t *pNode, Map_NodeVec_t *vNodes, int fCollectEquiv)
static int Map_MappingCountLevels_rec (Map_Node_t *pNode)
static float Map_MappingSetRefsAndArea_rec (Map_Man_t *pMan, Map_Node_t *pNode)
static float Map_MappingSetRefsAndSwitch_rec (Map_Man_t *pMan, Map_Node_t *pNode)
static float Map_MappingSetRefsAndWire_rec (Map_Man_t *pMan, Map_Node_t *pNode)
static void Map_MappingDfsCuts_rec (Map_Node_t *pNode, Map_NodeVec_t *vNodes)
static float Map_MappingArea_rec (Map_Man_t *pMan, Map_Node_t *pNode, Map_NodeVec_t *vNodes)
static int Map_MappingCompareOutputDelay (Map_Node_t **ppNode1, Map_Node_t **ppNode2)
static void Map_MappingFindLatest (Map_Man_t *p, int *pNodes, int nNodesMax)
static unsigned Map_MappingExpandTruth_rec (unsigned uTruth, int nVars)
static void Map_MappingGetChoiceLevels (Map_Man_t *pMan, Map_Node_t *p1, Map_Node_t *p2, int *pMin, int *pMax)
static float Map_MappingGetChoiceVolumes (Map_Man_t *pMan, Map_Node_t *p1, Map_Node_t *p2)
static int Map_MappingCountUsedNodes (Map_Man_t *pMan, int fChoices)
Map_NodeVec_t * Map_MappingDfs (Map_Man_t *pMan, int fCollectEquiv)
Map_NodeVec_t * Map_MappingDfsNodes (Map_Man_t *pMan, Map_Node_t **ppCuts, int nNodes, int fEquiv)
void Map_MappingDfsMarked1_rec (Map_Node_t *pNode, Map_NodeVec_t *vNodes, int fFirst)
void Map_MappingDfsMarked2_rec (Map_Node_t *pNode, Map_NodeVec_t *vNodes, Map_NodeVec_t *vBoundary, int fFirst)
void Map_MappingDfsMarked3_rec (Map_Node_t *pNode, Map_NodeVec_t *vNodes)
void Map_MappingDfsMarked4_rec (Map_Node_t *pNode, Map_NodeVec_t *vNodes)
int Map_MappingCountLevels (Map_Man_t *pMan)
void Map_MappingUnmark (Map_Man_t *pMan)
void Map_MappingUnmark_rec (Map_Node_t *pNode)
void Map_MappingMark_rec (Map_Node_t *pNode)
void Map_MappingPrintOutputArrivals (Map_Man_t *p)
void Map_MappingSetupTruthTables (unsigned uTruths[][2])
void Map_MappingSetupTruthTablesLarge (unsigned uTruths[][32])
void Map_MappingSetupMask (unsigned uMask[], int nVarsMax)
int Map_ManCheckConsistency (Map_Man_t *p)
int Map_MappingNodeIsViolator (Map_Node_t *pNode, Map_Cut_t *pCut, int fPosPol)
float Map_MappingGetAreaFlow (Map_Man_t *p)
int Map_CompareNodesByLevel (Map_Node_t **ppS1, Map_Node_t **ppS2)
void Map_MappingSortByLevel (Map_Man_t *pMan, Map_NodeVec_t *vNodes)
int Map_CompareNodesByPointer (Map_Node_t **ppS1, Map_Node_t **ppS2)
int Map_MappingCountDoubles (Map_Man_t *pMan, Map_NodeVec_t *vNodes)
st_table * Map_CreateTableGate2Super (Map_Man_t *pMan)
void Map_ManCleanData (Map_Man_t *p)
void Map_MappingExpandTruth (unsigned uTruth[2], int nVars)
float Map_MappingComputeDelayWithFanouts (Map_Man_t *p)
int Map_MappingGetMaxLevel (Map_Man_t *pMan)
int Map_MappingUpdateLevel_rec (Map_Man_t *pMan, Map_Node_t *pNode, int fMaximum)
void Map_MappingSetChoiceLevels (Map_Man_t *pMan)
void Map_MappingReportChoices (Map_Man_t *pMan)

Variables

static Map_Man_t * s_pMan = NULL

Define Documentation

#define MAP_CO_LIST_SIZE   5

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

FileName [mapperUtils.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
mapperUtils.c,v 1.8 2004/11/03 22:41:45 satrajit Exp

] DECLARATIONS ///

Definition at line 25 of file mapperUtils.c.

Function Documentation

int Map_CompareNodesByLevel ( Map_Node_t **  ppS1,
Map_Node_t **  ppS2 
)

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

Synopsis [Compares the supergates by their level.]

Description []

SideEffects []

SeeAlso []

Definition at line 697 of file mapperUtils.c.

00698 {
00699     Map_Node_t * pN1 = Map_Regular(*ppS1);
00700     Map_Node_t * pN2 = Map_Regular(*ppS2);
00701     if ( pN1->Level > pN2->Level )
00702         return -1;
00703     if ( pN1->Level < pN2->Level )
00704         return 1;
00705     return 0;
00706 }

int Map_CompareNodesByPointer ( Map_Node_t **  ppS1,
Map_Node_t **  ppS2 
)

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

Synopsis [Compares the supergates by their pointer.]

Description []

SideEffects []

SeeAlso []

Definition at line 738 of file mapperUtils.c.

00739 {
00740     if ( *ppS1 < *ppS2 )
00741         return -1;
00742     if ( *ppS1 > *ppS2 )
00743         return 1;
00744     return 0;
00745 }

st_table* Map_CreateTableGate2Super ( Map_Man_t *  pMan  ) 

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 788 of file mapperUtils.c.

00789 {
00790     Map_Super_t * pSuper;
00791     st_table * tTable;
00792     int i, nInputs, v;
00793     tTable = st_init_table(strcmp, st_strhash);
00794     for ( i = 0; i < pMan->pSuperLib->nSupersAll; i++ )
00795     {
00796         pSuper = pMan->pSuperLib->ppSupers[i];
00797         if ( pSuper->nGates == 1 )
00798         {
00799             // skip different versions of the same root gate
00800             nInputs = Mio_GateReadInputs(pSuper->pRoot);
00801             for ( v = 0; v < nInputs; v++ )
00802                 if ( pSuper->pFanins[v]->Num != nInputs - 1 - v )
00803                     break;
00804             if ( v != nInputs )
00805                 continue;
00806 //            printf( "%s\n", Mio_GateReadName(pSuper->pRoot) );
00807             if ( st_insert( tTable, (char *)pSuper->pRoot, (char *)pSuper ) )
00808             {
00809                 assert( 0 );
00810             }
00811         }
00812     }
00813     return tTable;
00814 }

int Map_ManCheckConsistency ( Map_Man_t *  p  ) 

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

Synopsis [Verify one useful property.]

Description [This procedure verifies one useful property. After the FRAIG construction with choice nodes is over, each primary node should have fanins that are primary nodes. The primary nodes is the one that does not have pNode->pRepr set to point to another node.]

SideEffects []

SeeAlso []

Definition at line 602 of file mapperUtils.c.

00603 {
00604     Map_Node_t * pNode;
00605     Map_NodeVec_t * pVec;
00606     int i;
00607     pVec = Map_MappingDfs( p, 0 );
00608     for ( i = 0; i < pVec->nSize; i++ )
00609     {
00610         pNode = pVec->pArray[i];
00611         if ( Map_NodeIsVar(pNode) )
00612         {
00613             if ( pNode->pRepr )
00614                 printf( "Primary input %d is a secondary node.\n", pNode->Num );
00615         }
00616         else if ( Map_NodeIsConst(pNode) )
00617         {
00618             if ( pNode->pRepr )
00619                 printf( "Constant 1 %d is a secondary node.\n", pNode->Num );
00620         }
00621         else
00622         {
00623             if ( pNode->pRepr )
00624                 printf( "Internal node %d is a secondary node.\n", pNode->Num );
00625             if ( Map_Regular(pNode->p1)->pRepr )
00626                 printf( "Internal node %d has first fanin that is a secondary node.\n", pNode->Num );
00627             if ( Map_Regular(pNode->p2)->pRepr )
00628                 printf( "Internal node %d has second fanin that is a secondary node.\n", pNode->Num );
00629         }
00630     }
00631     Map_NodeVecFree( pVec );
00632     return 1;
00633 }

void Map_ManCleanData ( Map_Man_t *  p  ) 

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

Synopsis [Get the FRAIG node with phase.]

Description []

SideEffects []

SeeAlso []

Definition at line 827 of file mapperUtils.c.

00828 {
00829     int i;
00830     for ( i = 0; i < p->vNodesAll->nSize; i++ )
00831         p->vNodesAll->pArray[i]->pData0 = p->vNodesAll->pArray[i]->pData1 = 0;
00832 }

static float Map_MappingArea_rec ( Map_Man_t *  pMan,
Map_Node_t *  pNode,
Map_NodeVec_t *  vNodes 
) [static]
int Map_MappingCompareOutputDelay ( Map_Node_t **  ppNode1,
Map_Node_t **  ppNode2 
) [static]

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

Synopsis [Compares the outputs by their arrival times.]

Description []

SideEffects []

SeeAlso []

Definition at line 406 of file mapperUtils.c.

00407 {
00408     Map_Node_t * pNode1 = Map_Regular(*ppNode1);
00409     Map_Node_t * pNode2 = Map_Regular(*ppNode2);
00410     int fPhase1 = !Map_IsComplement(*ppNode1);
00411     int fPhase2 = !Map_IsComplement(*ppNode2);
00412     float Arrival1 = pNode1->tArrival[fPhase1].Worst;
00413     float Arrival2 = pNode2->tArrival[fPhase2].Worst;
00414     if ( Arrival1 < Arrival2 )
00415         return -1;
00416     if ( Arrival1 > Arrival2 )
00417         return 1;
00418     return 0;
00419 }

float Map_MappingComputeDelayWithFanouts ( Map_Man_t *  p  ) 

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

Synopsis [Compute the arrival times.]

Description []

SideEffects []

SeeAlso []

Definition at line 888 of file mapperUtils.c.

00889 {
00890     Map_Node_t * pNode;
00891     float Result;
00892     int i;
00893     for ( i = 0; i < p->vAnds->nSize; i++ )
00894     {
00895         // skip primary inputs
00896         pNode = p->vAnds->pArray[i];
00897         if ( !Map_NodeIsAnd( pNode ) )
00898             continue;
00899         // skip a secondary node
00900         if ( pNode->pRepr )
00901             continue;
00902         // count the switching nodes
00903         if ( pNode->nRefAct[0] > 0 )
00904             Map_TimeCutComputeArrival( pNode, pNode->pCutBest[0], 0, MAP_FLOAT_LARGE );
00905         if ( pNode->nRefAct[1] > 0 )
00906             Map_TimeCutComputeArrival( pNode, pNode->pCutBest[1], 1, MAP_FLOAT_LARGE );
00907     }
00908     Result = Map_TimeComputeArrivalMax(p);
00909     printf( "Max arrival times with fanouts = %10.2f.\n", Result );
00910     return Result;
00911 }

int Map_MappingCountDoubles ( Map_Man_t *  pMan,
Map_NodeVec_t *  vNodes 
)

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

Synopsis [Counts how many AIG nodes are mapped in both polarities.]

Description []

SideEffects []

SeeAlso []

Definition at line 758 of file mapperUtils.c.

00759 {
00760     Map_Node_t * pNode;
00761     int Counter, i;
00762     // count the number of equal adjacent nodes
00763     Counter = 0;
00764     for ( i = 0; i < vNodes->nSize; i++ )
00765     {
00766         pNode = vNodes->pArray[i];
00767         if ( !Map_NodeIsAnd(pNode) )
00768             continue;
00769         if ( (pNode->nRefAct[0] && pNode->pCutBest[0]) && 
00770              (pNode->nRefAct[1] && pNode->pCutBest[1]) )
00771             Counter++;
00772     }
00773     return Counter;
00774 }

int Map_MappingCountLevels ( Map_Man_t *  pMan  ) 

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

Synopsis [Computes the number of logic levels not counting PIs/POs.]

Description []

SideEffects [Note that this procedure will reassign the levels assigned originally by NodeCreate() because it counts the number of levels with choices differently!]

SeeAlso []

Definition at line 280 of file mapperUtils.c.

00281 {
00282     int i, LevelsMax, LevelsCur;
00283     // perform the traversal
00284     LevelsMax = -1;
00285     for ( i = 0; i < pMan->nOutputs; i++ )
00286     {
00287         LevelsCur = Map_MappingCountLevels_rec( Map_Regular(pMan->pOutputs[i]) );
00288         if ( LevelsMax < LevelsCur )
00289             LevelsMax = LevelsCur;
00290     }
00291     for ( i = 0; i < pMan->nOutputs; i++ )
00292         Map_MappingUnmark_rec( Map_Regular(pMan->pOutputs[i]) );
00293     return LevelsMax;
00294 }

int Map_MappingCountLevels_rec ( Map_Node_t *  pNode  )  [static]

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

Synopsis [Recursively computes the number of logic levels.]

Description []

SideEffects []

SeeAlso []

Definition at line 307 of file mapperUtils.c.

00308 {
00309     int Level1, Level2;
00310     assert( !Map_IsComplement(pNode) );
00311     if ( !Map_NodeIsAnd(pNode) )
00312     {
00313         pNode->Level = 0;
00314         return 0;
00315     }
00316     if ( pNode->fMark0 )
00317         return pNode->Level;
00318     pNode->fMark0 = 1;
00319     // visit the transitive fanin
00320     Level1 = Map_MappingCountLevels_rec( Map_Regular(pNode->p1) );
00321     Level2 = Map_MappingCountLevels_rec( Map_Regular(pNode->p2) );
00322     // set the number of levels
00323     pNode->Level = 1 + ((Level1>Level2)? Level1: Level2);
00324     return pNode->Level;
00325 }

int Map_MappingCountUsedNodes ( Map_Man_t *  pMan,
int  fChoices 
) [static]

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

Synopsis [Computes the maximum and minimum levels of the choice nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 1140 of file mapperUtils.c.

01141 {
01142     Map_NodeVec_t * vNodes;
01143     int Result;
01144     vNodes = Map_MappingDfs( pMan, fChoices );
01145     Result = vNodes->nSize;
01146     Map_NodeVecFree( vNodes );
01147     return Result;    
01148 }

Map_NodeVec_t* Map_MappingDfs ( Map_Man_t *  pMan,
int  fCollectEquiv 
)

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

Synopsis [Computes the DFS ordering of the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 58 of file mapperUtils.c.

00059 {
00060     Map_NodeVec_t * vNodes;
00061     int i;
00062     // perform the traversal
00063     vNodes = Map_NodeVecAlloc( 100 );
00064     for ( i = 0; i < pMan->nOutputs; i++ )
00065         Map_MappingDfs_rec( Map_Regular(pMan->pOutputs[i]), vNodes, fCollectEquiv );
00066     for ( i = 0; i < vNodes->nSize; i++ )
00067         vNodes->pArray[i]->fMark0 = 0;
00068 //    for ( i = 0; i < pMan->nOutputs; i++ )
00069 //        Map_MappingUnmark_rec( Map_Regular(pMan->pOutputs[i]) );
00070     return vNodes;
00071 }

void Map_MappingDfs_rec ( Map_Node_t *  pNode,
Map_NodeVec_t *  vNodes,
int  fCollectEquiv 
) [static]

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

Synopsis [Recursively computes the DFS ordering of the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 108 of file mapperUtils.c.

00109 {
00110     assert( !Map_IsComplement(pNode) );
00111     if ( pNode->fMark0 )
00112         return;
00113     // visit the transitive fanin
00114     if ( Map_NodeIsAnd(pNode) )
00115     {
00116         Map_MappingDfs_rec( Map_Regular(pNode->p1), vNodes, fCollectEquiv );
00117         Map_MappingDfs_rec( Map_Regular(pNode->p2), vNodes, fCollectEquiv );
00118     }
00119     // visit the equivalent nodes
00120     if ( fCollectEquiv && pNode->pNextE )
00121         Map_MappingDfs_rec( pNode->pNextE, vNodes, fCollectEquiv );
00122     // make sure the node is not visited through the equivalent nodes
00123     assert( pNode->fMark0 == 0 );
00124     // mark the node as visited
00125     pNode->fMark0 = 1;
00126     // add the node to the list
00127     Map_NodeVecPush( vNodes, pNode );
00128 }

static void Map_MappingDfsCuts_rec ( Map_Node_t *  pNode,
Map_NodeVec_t *  vNodes 
) [static]
void Map_MappingDfsMarked1_rec ( Map_Node_t *  pNode,
Map_NodeVec_t *  vNodes,
int  fFirst 
)

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

Synopsis [Recursively computes the DFS ordering of the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 143 of file mapperUtils.c.

00144 {
00145     assert( !Map_IsComplement(pNode) );
00146     if ( pNode->fMark0 )
00147         return;
00148     // visit the transitive fanin
00149     if ( Map_NodeIsAnd(pNode) )
00150     {
00151         Map_MappingDfsMarked1_rec( Map_Regular(pNode->p1), vNodes, 0 );
00152         Map_MappingDfsMarked1_rec( Map_Regular(pNode->p2), vNodes, 0 );
00153     }
00154     // visit the equivalent nodes
00155     if ( !fFirst && pNode->pNextE )
00156         Map_MappingDfsMarked1_rec( pNode->pNextE, vNodes, 0 );
00157     // make sure the node is not visited through the equivalent nodes
00158     assert( pNode->fMark0 == 0 );
00159     // mark the node as visited
00160     pNode->fMark0 = 1;
00161     // add the node to the list
00162     Map_NodeVecPush( vNodes, pNode );
00163 }

void Map_MappingDfsMarked2_rec ( Map_Node_t *  pNode,
Map_NodeVec_t *  vNodes,
Map_NodeVec_t *  vBoundary,
int  fFirst 
)

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

Synopsis [Recursively computes the DFS ordering of the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 176 of file mapperUtils.c.

00177 {
00178     assert( !Map_IsComplement(pNode) );
00179     if ( pNode->fMark1 )
00180         return;
00181     if ( pNode->fMark0 || Map_NodeIsVar(pNode) )
00182     {
00183         pNode->fMark1 = 1;
00184         Map_NodeVecPush(vBoundary, pNode);
00185         return;
00186     }
00187     // visit the transitive fanin
00188     if ( Map_NodeIsAnd(pNode) )
00189     {
00190         Map_MappingDfsMarked2_rec( Map_Regular(pNode->p1), vNodes, vBoundary, 0 );
00191         Map_MappingDfsMarked2_rec( Map_Regular(pNode->p2), vNodes, vBoundary, 0 );
00192     }
00193     // visit the equivalent nodes
00194     if ( !fFirst && pNode->pNextE )
00195         Map_MappingDfsMarked2_rec( pNode->pNextE, vNodes, vBoundary, 0 );
00196     // make sure the node is not visited through the equivalent nodes
00197     assert( pNode->fMark1 == 0 );
00198     // mark the node as visited
00199     pNode->fMark1 = 1;
00200     // add the node to the list
00201     Map_NodeVecPush( vNodes, pNode );
00202 }

void Map_MappingDfsMarked3_rec ( Map_Node_t *  pNode,
Map_NodeVec_t *  vNodes 
)

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

Synopsis [Recursively computes the DFS ordering of the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 216 of file mapperUtils.c.

00217 {
00218     assert( !Map_IsComplement(pNode) );
00219     if ( pNode->fMark0 )
00220         return;
00221     // visit the transitive fanin
00222     if ( Map_NodeIsAnd(pNode) )
00223     {
00224         Map_MappingDfsMarked3_rec( Map_Regular(pNode->p1), vNodes );
00225         Map_MappingDfsMarked3_rec( Map_Regular(pNode->p2), vNodes );
00226     }
00227     // make sure the node is not visited through the equivalent nodes
00228     assert( pNode->fMark0 == 0 );
00229     // mark the node as visited
00230     pNode->fMark0 = 1;
00231     // add the node to the list
00232     Map_NodeVecPush( vNodes, pNode );
00233 }

void Map_MappingDfsMarked4_rec ( Map_Node_t *  pNode,
Map_NodeVec_t *  vNodes 
)

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

Synopsis [Recursively computes the DFS ordering of the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 246 of file mapperUtils.c.

00247 {
00248     assert( !Map_IsComplement(pNode) );
00249     if ( pNode->fMark1 )
00250         return;
00251     // visit the transitive fanin
00252     if ( Map_NodeIsAnd(pNode) )
00253     {
00254         Map_MappingDfsMarked4_rec( Map_Regular(pNode->p1), vNodes );
00255         Map_MappingDfsMarked4_rec( Map_Regular(pNode->p2), vNodes );
00256     }
00257     // make sure the node is not visited through the equivalent nodes
00258     assert( pNode->fMark1 == 0 );
00259     // mark the node as visited
00260     pNode->fMark1 = 1;
00261     // add the node to the list
00262     Map_NodeVecPush( vNodes, pNode );
00263 }

Map_NodeVec_t* Map_MappingDfsNodes ( Map_Man_t *  pMan,
Map_Node_t **  ppCuts,
int  nNodes,
int  fEquiv 
)

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

Synopsis [Computes the DFS ordering of the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 84 of file mapperUtils.c.

00085 {
00086     Map_NodeVec_t * vNodes;
00087     int i;
00088     // perform the traversal
00089     vNodes = Map_NodeVecAlloc( 200 );
00090     for ( i = 0; i < nNodes; i++ )
00091         Map_MappingDfs_rec( ppCuts[i], vNodes, fEquiv );
00092     for ( i = 0; i < vNodes->nSize; i++ )
00093         vNodes->pArray[i]->fMark0 = 0;
00094     return vNodes;
00095 }

void Map_MappingExpandTruth ( unsigned  uTruth[2],
int  nVars 
)

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

Synopsis [Expand the truth table]

Description []

SideEffects []

SeeAlso []

Definition at line 845 of file mapperUtils.c.

00846 {
00847     assert( nVars < 7 );
00848     if ( nVars == 6 )
00849         return;
00850     if ( nVars < 5 )
00851     {
00852         uTruth[0] &= MAP_MASK( (1<<nVars) );
00853         uTruth[0]  = Map_MappingExpandTruth_rec( uTruth[0], nVars );
00854     }
00855     uTruth[1] = uTruth[0];
00856 }

unsigned Map_MappingExpandTruth_rec ( unsigned  uTruth,
int  nVars 
) [static]

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

Synopsis [Expand the truth table]

Description []

SideEffects []

SeeAlso []

Definition at line 869 of file mapperUtils.c.

00870 {
00871     assert( nVars < 6 );
00872     if ( nVars == 5 )
00873         return uTruth;
00874     return Map_MappingExpandTruth_rec( uTruth | (uTruth << (1 << nVars)), nVars + 1 );    
00875 }

void Map_MappingFindLatest ( Map_Man_t *  p,
int *  pNodes,
int  nNodesMax 
) [static]

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

Synopsis [Finds given number of latest arriving COs.]

Description []

SideEffects []

SeeAlso []

Definition at line 432 of file mapperUtils.c.

00433 {
00434     int nNodes, i, k, v;
00435     assert( p->nOutputs >= nNodesMax );
00436     pNodes[0] = 0;
00437     nNodes = 1;
00438     for ( i = 1; i < p->nOutputs; i++ )
00439     {
00440         for ( k = nNodes - 1; k >= 0; k-- )
00441             if ( Map_MappingCompareOutputDelay( &p->pOutputs[pNodes[k]], &p->pOutputs[i] ) >= 0 )
00442                 break;
00443         if ( k == nNodesMax - 1 )
00444             continue;
00445         if ( nNodes < nNodesMax )
00446             nNodes++;
00447         for ( v = nNodes - 1; v > k+1; v-- )
00448             pNodes[v] = pNodes[v-1];
00449         pNodes[k+1] = i;
00450     }
00451 }

float Map_MappingGetAreaFlow ( Map_Man_t *  p  ) 

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

Synopsis [Computes the total are flow of the network.]

Description []

SideEffects []

SeeAlso []

Definition at line 662 of file mapperUtils.c.

00663 {
00664     Map_Node_t * pNode;
00665     Map_Cut_t * pCut;
00666     float aFlowFlowTotal = 0;
00667     int fPosPol, i;
00668     for ( i = 0; i < p->nOutputs; i++ )
00669     {
00670         pNode = Map_Regular(p->pOutputs[i]);
00671         if ( !Map_NodeIsAnd(pNode) )
00672             continue;
00673         fPosPol = !Map_IsComplement(p->pOutputs[i]);
00674         pCut = pNode->pCutBest[fPosPol];
00675         if ( pCut == NULL )
00676         {
00677             fPosPol = !fPosPol;
00678             pCut = pNode->pCutBest[fPosPol];
00679         }
00680         aFlowFlowTotal += pNode->pCutBest[fPosPol]->M[fPosPol].AreaFlow;
00681     }
00682     return aFlowFlowTotal;
00683 }

void Map_MappingGetChoiceLevels ( Map_Man_t *  pMan,
Map_Node_t *  p1,
Map_Node_t *  p2,
int *  pMin,
int *  pMax 
) [static]

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

Synopsis [Computes the maximum and minimum levels of the choice nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 1057 of file mapperUtils.c.

01058 {
01059     Map_NodeVec_t * vNodes;
01060     Map_NodeVec_t * vBoundary;
01061     Map_Node_t * pNode;
01062     int i, Min, Max;
01063 
01064     vNodes    = Map_NodeVecAlloc( 100 );
01065     vBoundary = Map_NodeVecAlloc( 100 );
01066     Map_MappingDfsMarked1_rec( p1, vNodes, 1 );
01067     Map_MappingDfsMarked2_rec( p2, vNodes, vBoundary, 1 );
01068     // clean the marks
01069     Min =  100000;
01070     Max = -100000;
01071     for ( i = 0; i < vBoundary->nSize; i++ )
01072     {
01073         pNode = vBoundary->pArray[i];
01074         if ( Min > (int)pNode->Level )
01075             Min = pNode->Level;
01076         if ( Max < (int)pNode->Level )
01077             Max = pNode->Level;
01078     }
01079     Map_NodeVecFree( vBoundary );
01080     for ( i = 0; i < vNodes->nSize; i++ )
01081     {
01082         pNode = vNodes->pArray[i];
01083         pNode->fMark0 = pNode->fMark1 = 0;
01084     }
01085     Map_NodeVecFree( vNodes );
01086     *pMin = Min;
01087     *pMax = Max;
01088 }

float Map_MappingGetChoiceVolumes ( Map_Man_t *  pMan,
Map_Node_t *  p1,
Map_Node_t *  p2 
) [static]

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 1102 of file mapperUtils.c.

01103 {
01104     Map_NodeVec_t * vNodes;
01105     Map_Node_t * pNode;
01106     int i, nVolumeTotal, nVolumeUnique;
01107 
01108     vNodes    = Map_NodeVecAlloc( 100 );
01109     Map_MappingDfsMarked3_rec( p1, vNodes );
01110     Map_MappingDfsMarked4_rec( p2, vNodes );
01111     // clean the marks
01112     nVolumeTotal = nVolumeUnique = 0;
01113     for ( i = 0; i < vNodes->nSize; i++ )
01114     {
01115         pNode = vNodes->pArray[i];
01116         if ( !Map_NodeIsAnd(pNode) )
01117             continue;
01118         nVolumeTotal++;
01119         if ( pNode->fMark0 ^ pNode->fMark1 )
01120             nVolumeUnique++;
01121         pNode->fMark0 = pNode->fMark1 = 0;
01122     }
01123     Map_NodeVecFree( vNodes );
01124 //    return ((float)nVolumeUnique)/nVolumeTotal;
01125     return (float)nVolumeUnique;
01126 }

int Map_MappingGetMaxLevel ( Map_Man_t *  pMan  ) 

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

Synopsis [Sets up the mask.]

Description []

SideEffects []

SeeAlso []

Definition at line 925 of file mapperUtils.c.

00926 {
00927     int nLevelMax, i;
00928     nLevelMax = 0;
00929     for ( i = 0; i < pMan->nOutputs; i++ )
00930         nLevelMax = ((unsigned)nLevelMax) > Map_Regular(pMan->pOutputs[i])->Level? 
00931                 nLevelMax : Map_Regular(pMan->pOutputs[i])->Level;
00932     return nLevelMax;
00933 }

void Map_MappingMark_rec ( Map_Node_t *  pNode  ) 

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 382 of file mapperUtils.c.

00383 {
00384     assert( !Map_IsComplement(pNode) );
00385     if ( pNode->fMark0 == 1 )
00386         return;
00387     pNode->fMark0 = 1;
00388     if ( !Map_NodeIsAnd(pNode) )
00389         return;
00390     // visit the transitive fanin of the selected cut
00391     Map_MappingMark_rec( Map_Regular(pNode->p1) );
00392     Map_MappingMark_rec( Map_Regular(pNode->p2) );
00393 }

int Map_MappingNodeIsViolator ( Map_Node_t *  pNode,
Map_Cut_t *  pCut,
int  fPosPol 
)

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

Synopsis [Returns 1 if current mapping of the node violates fanout limits.]

Description []

SideEffects []

SeeAlso []

Definition at line 646 of file mapperUtils.c.

00647 {
00648     return pNode->nRefAct[fPosPol] > (int)pCut->M[fPosPol].pSuperBest->nFanLimit;
00649 }

void Map_MappingPrintOutputArrivals ( Map_Man_t *  p  ) 

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

Synopsis [Prints a bunch of latest arriving outputs.]

Description []

SideEffects []

SeeAlso []

Definition at line 464 of file mapperUtils.c.

00465 {
00466     int pSorted[MAP_CO_LIST_SIZE];
00467     Map_Time_t * pTimes;
00468     Map_Node_t * pNode;
00469     int fPhase, Limit, i;
00470     int MaxNameSize;
00471 
00472     // determine the number of nodes to print
00473     Limit = (p->nOutputs > MAP_CO_LIST_SIZE)? MAP_CO_LIST_SIZE : p->nOutputs;
00474 
00475     // determine the order
00476     Map_MappingFindLatest( p, pSorted, Limit );
00477 
00478     // determine max size of the node's name
00479     MaxNameSize = 0;
00480     for ( i = 0; i < Limit; i++ )
00481         if ( MaxNameSize < (int)strlen(p->ppOutputNames[pSorted[i]]) )
00482             MaxNameSize = strlen(p->ppOutputNames[pSorted[i]]);
00483 
00484     // print the latest outputs
00485     for ( i = 0; i < Limit; i++ )
00486     {
00487         // get the i-th latest output
00488         pNode  = Map_Regular(p->pOutputs[pSorted[i]]);
00489         fPhase =!Map_IsComplement(p->pOutputs[pSorted[i]]);
00490         pTimes = pNode->tArrival + fPhase;
00491         // print out the best arrival time
00492         printf( "Output  %-*s : ", MaxNameSize + 3, p->ppOutputNames[pSorted[i]] );
00493         printf( "Delay = (%5.2f, %5.2f)  ", (double)pTimes->Rise, (double)pTimes->Fall );
00494         printf( "%s", fPhase? "POS" : "NEG" );
00495         printf( "\n" );
00496     }
00497 }

void Map_MappingReportChoices ( Map_Man_t *  pMan  ) 

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

Synopsis [Reports statistics on choice nodes.]

Description [The number of choice nodes is the number of primary nodes, which has pNextE set to a pointer. The number of choices is the number of entries in the equivalent-node lists of the primary nodes.]

SideEffects []

SeeAlso []

Definition at line 1017 of file mapperUtils.c.

01018 {
01019     Map_Node_t * pNode, * pTemp;
01020     int nChoiceNodes, nChoices;
01021     int i, LevelMax1, LevelMax2;
01022 
01023     // report the number of levels
01024     LevelMax1 = Map_MappingGetMaxLevel( pMan );
01025     pMan->nTravIds++;
01026     for ( i = 0; i < pMan->nOutputs; i++ )
01027         Map_MappingUpdateLevel_rec( pMan, Map_Regular(pMan->pOutputs[i]), 0 );
01028     LevelMax2 = Map_MappingGetMaxLevel( pMan );
01029 
01030     // report statistics about choices
01031     nChoiceNodes = nChoices = 0;
01032     for ( i = 0; i < pMan->vAnds->nSize; i++ )
01033     {
01034         pNode = pMan->vAnds->pArray[i];
01035         if ( pNode->pRepr == NULL && pNode->pNextE != NULL )
01036         { // this is a choice node = the primary node that has equivalent nodes
01037             nChoiceNodes++;
01038             for ( pTemp = pNode; pTemp; pTemp = pTemp->pNextE )
01039                 nChoices++;
01040         }
01041     }
01042     printf( "Maximum level: Original = %d. Reduced due to choices = %d.\n", LevelMax1, LevelMax2 );
01043     printf( "Choice stats:  Choice nodes = %d. Total choices = %d.\n", nChoiceNodes, nChoices );
01044 }

void Map_MappingSetChoiceLevels ( Map_Man_t *  pMan  ) 

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

Synopsis [Resets the levels of the nodes in the choice graph.]

Description [Makes the level of the choice nodes to be equal to the maximum of the level of the nodes in the equivalence class. This way sorting by level leads to the reverse topological order, which is needed for the required time computation.]

SideEffects []

SeeAlso []

Definition at line 996 of file mapperUtils.c.

00997 {
00998     int i;
00999     pMan->nTravIds++;
01000     for ( i = 0; i < pMan->nOutputs; i++ )
01001         Map_MappingUpdateLevel_rec( pMan, Map_Regular(pMan->pOutputs[i]), 1 );
01002 }

static float Map_MappingSetRefsAndArea_rec ( Map_Man_t *  pMan,
Map_Node_t *  pNode 
) [static]
static float Map_MappingSetRefsAndSwitch_rec ( Map_Man_t *  pMan,
Map_Node_t *  pNode 
) [static]
static float Map_MappingSetRefsAndWire_rec ( Map_Man_t *  pMan,
Map_Node_t *  pNode 
) [static]
void Map_MappingSetupMask ( unsigned  uMask[],
int  nVarsMax 
)

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

Synopsis [Sets up the mask.]

Description []

SideEffects []

SeeAlso []

Definition at line 577 of file mapperUtils.c.

00578 {
00579     if ( nVarsMax == 6 )
00580         uMask[0] = uMask[1] = MAP_FULL;
00581     else
00582     {
00583         uMask[0] = MAP_MASK(1 << nVarsMax);
00584         uMask[1] = 0;
00585     }
00586 }

void Map_MappingSetupTruthTables ( unsigned  uTruths[][2]  ) 

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

Synopsis [Sets up the truth tables.]

Description []

SideEffects []

SeeAlso []

Definition at line 510 of file mapperUtils.c.

00511 {
00512     int m, v;
00513     // set up the truth tables
00514     for ( m = 0; m < 32; m++ )
00515         for ( v = 0; v < 5; v++ )
00516             if ( m & (1 << v) )
00517                 uTruths[v][0] |= (1 << m);
00518     // make adjustments for the case of 6 variables
00519     for ( v = 0; v < 5; v++ )
00520         uTruths[v][1] = uTruths[v][0];
00521     uTruths[5][0] = 0;
00522     uTruths[5][1] = MAP_FULL;
00523 }

void Map_MappingSetupTruthTablesLarge ( unsigned  uTruths[][32]  ) 

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

Synopsis [Sets up the truth tables.]

Description []

SideEffects []

SeeAlso []

Definition at line 536 of file mapperUtils.c.

00537 {
00538     int m, v;
00539     // clean everything
00540     for ( m = 0; m < 32; m++ )
00541         for ( v = 0; v < 10; v++ )
00542             uTruths[v][m] = 0;
00543     // set up the truth tables
00544     for ( m = 0; m < 32; m++ )
00545         for ( v = 0; v < 5; v++ )
00546             if ( m & (1 << v) )
00547             {
00548                 uTruths[v][0] |= (1 << m);
00549                 uTruths[v+5][m] = MAP_FULL;
00550             }
00551     // extend this info for the rest of the first 5 variables
00552     for ( m = 0; m < 32; m++ )
00553         for ( v = 0; v < 5; v++ )
00554             uTruths[v][m] = uTruths[v][0];
00555 /*
00556     // verify
00557     for ( m = 0; m < 1024; m++, printf("\n") )
00558         for ( v = 0; v < 10; v++ )
00559             if ( Map_InfoReadVar( uTruths[v], m ) )
00560                 printf( "1" );
00561             else
00562                 printf( "0" );
00563 */
00564 }

void Map_MappingSortByLevel ( Map_Man_t *  pMan,
Map_NodeVec_t *  vNodes 
)

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

Synopsis [Orders the nodes in the decreasing order of levels.]

Description []

SideEffects []

SeeAlso []

Definition at line 719 of file mapperUtils.c.

00720 {
00721     qsort( (void *)vNodes->pArray, vNodes->nSize, sizeof(Map_Node_t *), 
00722             (int (*)(const void *, const void *)) Map_CompareNodesByLevel );
00723 //    assert( Map_CompareNodesByLevel( vNodes->pArray, vNodes->pArray + vNodes->nSize - 1 ) <= 0 );
00724 }

void Map_MappingUnmark ( Map_Man_t *  pMan  ) 

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

Synopsis [Unmarks the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 338 of file mapperUtils.c.

00339 {
00340     int i;
00341     for ( i = 0; i < pMan->nOutputs; i++ )
00342         Map_MappingUnmark_rec( Map_Regular(pMan->pOutputs[i]) );
00343 }

void Map_MappingUnmark_rec ( Map_Node_t *  pNode  ) 

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

Synopsis [Recursively unmarks the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 356 of file mapperUtils.c.

00357 {
00358     assert( !Map_IsComplement(pNode) );
00359     if ( pNode->fMark0 == 0 )
00360         return;
00361     pNode->fMark0 = 0;
00362     if ( !Map_NodeIsAnd(pNode) )
00363         return;
00364     Map_MappingUnmark_rec( Map_Regular(pNode->p1) );
00365     Map_MappingUnmark_rec( Map_Regular(pNode->p2) );
00366     // visit the equivalent nodes
00367     if ( pNode->pNextE )
00368         Map_MappingUnmark_rec( pNode->pNextE );
00369 }

int Map_MappingUpdateLevel_rec ( Map_Man_t *  pMan,
Map_Node_t *  pNode,
int  fMaximum 
)

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

Synopsis [Analyses choice nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 946 of file mapperUtils.c.

00947 {
00948     Map_Node_t * pTemp;
00949     int Level1, Level2, LevelE;
00950     assert( !Map_IsComplement(pNode) );
00951     if ( !Map_NodeIsAnd(pNode) )
00952         return pNode->Level;
00953     // skip the visited node
00954     if ( pNode->TravId == pMan->nTravIds )
00955         return pNode->Level;
00956     pNode->TravId = pMan->nTravIds;
00957     // compute levels of the children nodes
00958     Level1 = Map_MappingUpdateLevel_rec( pMan, Map_Regular(pNode->p1), fMaximum );
00959     Level2 = Map_MappingUpdateLevel_rec( pMan, Map_Regular(pNode->p2), fMaximum );
00960     pNode->Level = 1 + MAP_MAX( Level1, Level2 );
00961     if ( pNode->pNextE )
00962     {
00963         LevelE = Map_MappingUpdateLevel_rec( pMan, pNode->pNextE, fMaximum );
00964         if ( fMaximum )
00965         {
00966             if ( pNode->Level < (unsigned)LevelE )
00967                 pNode->Level = LevelE;
00968         }
00969         else
00970         {
00971             if ( pNode->Level > (unsigned)LevelE )
00972                 pNode->Level = LevelE;
00973         }
00974         // set the level of all equivalent nodes to be the same minimum
00975         if ( pNode->pRepr == NULL ) // the primary node
00976             for ( pTemp = pNode->pNextE; pTemp; pTemp = pTemp->pNextE )
00977                 pTemp->Level = pNode->Level;
00978     }
00979     return pNode->Level;
00980 }

Variable Documentation

Map_Man_t* s_pMan = NULL [static]

Definition at line 40 of file mapperUtils.c.

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