diff options
Diffstat (limited to 'src/map/mapper/mapperMatch.c')
| -rw-r--r-- | src/map/mapper/mapperMatch.c | 596 |
1 files changed, 596 insertions, 0 deletions
diff --git a/src/map/mapper/mapperMatch.c b/src/map/mapper/mapperMatch.c new file mode 100644 index 00000000..bfa72601 --- /dev/null +++ b/src/map/mapper/mapperMatch.c @@ -0,0 +1,596 @@ +/**CFile**************************************************************** + + FileName [mapperMatch.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: mapperMatch.c,v 1.7 2004/09/30 21:18:10 satrajit Exp $] + +***********************************************************************/ + +#include "mapperInt.h" + +/* + A potential improvement: + When an internal node is not used in the mapping, its required times + are set to be +infinity. So when we recover area, we try to find the + best match for area and completely disregard the delay for the nodes + that are not currently used in the mapping because any match whose + arrival times are less than the required times (+infinity) can be used. + It may be possible to develop a better approach to recover area for + the nodes that are not currently used in the mapping... +*/ + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static int Map_MatchNodePhase( Map_Man_t * p, Map_Node_t * pNode, int fPhase ); +static int Map_MatchNodeCut( Map_Man_t * p, Map_Node_t * pNode, Map_Cut_t * pCut, int fPhase, float fWorstLimit ); + +static void Map_MappingSetPiArrivalTimes( Map_Man_t * p ); +static void Map_NodeTryDroppingOnePhase( Map_Man_t * p, Map_Node_t * pNode ); +static void Map_NodeTransferArrivalTimes( Map_Man_t * p, Map_Node_t * pNode ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Computes the best matches of the nodes.] + + Description [Uses parameter p->fMappingMode to decide how to assign + the matches for both polarities of the node. While the matches are + being assigned, one of them may turn out to be better than the other + (in terms of delay, for example). In this case, the worse match can + be permanently dropped, and the corresponding pointer set to NULL.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_MappingMatches( Map_Man_t * p ) +{ + ProgressBar * pProgress; + Map_Node_t * pNode; + int i; + + assert( p->fMappingMode >= 0 && p->fMappingMode <= 4 ); + + // use the externally given PI arrival times + if ( p->fMappingMode == 0 ) + Map_MappingSetPiArrivalTimes( p ); + + // estimate the fanouts + if ( p->fMappingMode == 0 ) + Map_MappingEstimateRefsInit( p ); + else if ( p->fMappingMode == 1 ) + Map_MappingEstimateRefs( p ); + + // the PI cuts are matched in the cut computation package + // in the loop below we match the internal nodes + pProgress = Extra_ProgressBarStart( stdout, p->vAnds->nSize ); + for ( i = 0; i < p->vAnds->nSize; i++ ) + { + // skip primary inputs and secondary nodes if mapping with choices + pNode = p->vAnds->pArray[i]; + if ( !Map_NodeIsAnd( pNode ) || pNode->pRepr ) + continue; + + // make sure that at least one non-trival cut is present + if ( pNode->pCuts->pNext == NULL ) + { + printf( "\nError: A node in the mapping graph does not have feasible cuts.\n" ); + return 0; + } + + // match negative phase + if ( !Map_MatchNodePhase( p, pNode, 0 ) ) + return 0; + // match positive phase + if ( !Map_MatchNodePhase( p, pNode, 1 ) ) + return 0; + + // make sure that at least one phase is mapped + if ( pNode->pCutBest[0] == NULL && pNode->pCutBest[1] == NULL ) + { + printf( "\nError: Could not match both phases of AIG node %d.\n", pNode->Num ); + printf( "Please make sure that the supergate library has equivalents of AND2 or NAND2.\n" ); + printf( "If such supergates exist in the library, report a bug.\n" ); + return 0; + } + + // if both phases are assigned, check if one of them can be dropped + Map_NodeTryDroppingOnePhase( p, pNode ); + // set the arrival times of the node using the best cuts + Map_NodeTransferArrivalTimes( p, pNode ); + + // update the progress bar + Extra_ProgressBarUpdate( pProgress, i, "Matches ..." ); + } + Extra_ProgressBarStop( pProgress ); + return 1; +} + +/**Function************************************************************* + + Synopsis [Find the matching of one polarity of the node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_MatchNodePhase( Map_Man_t * p, Map_Node_t * pNode, int fPhase ) +{ + Map_Match_t MatchBest, * pMatch; + Map_Cut_t * pCut, * pCutBest; + float Area1, Area2, fWorstLimit; + + // skip the cuts that have been unassigned during area recovery + pCutBest = pNode->pCutBest[fPhase]; + if ( p->fMappingMode != 0 && pCutBest == NULL ) + return 1; + + // recompute the arrival times of the current best match + // because the arrival times of the fanins may have changed + // as a result of remapping fanins in the topological order + if ( p->fMappingMode != 0 ) + { + Map_TimeCutComputeArrival( pNode, pCutBest, fPhase, MAP_FLOAT_LARGE ); + // make sure that the required times are met + assert( pCutBest->M[fPhase].tArrive.Rise < pNode->tRequired[fPhase].Rise + p->fEpsilon ); + assert( pCutBest->M[fPhase].tArrive.Fall < pNode->tRequired[fPhase].Fall + p->fEpsilon ); + } + + // recompute the exact area of the current best match + // because the exact area of the fanins may have changed + // as a result of remapping fanins in the topological order + if ( p->fMappingMode == 2 || p->fMappingMode == 3 ) + { + pMatch = pCutBest->M + fPhase; + if ( pNode->nRefAct[fPhase] > 0 || + (pNode->pCutBest[!fPhase] == NULL && pNode->nRefAct[!fPhase] > 0) ) + pMatch->AreaFlow = Area1 = Map_CutDeref( pCutBest, fPhase ); + else + pMatch->AreaFlow = Area1 = Map_CutGetAreaDerefed( pCutBest, fPhase ); + } + else if ( p->fMappingMode == 4 ) + { + pMatch = pCutBest->M + fPhase; + if ( pNode->nRefAct[fPhase] > 0 || + (pNode->pCutBest[!fPhase] == NULL && pNode->nRefAct[!fPhase] > 0) ) + pMatch->AreaFlow = Area1 = Map_SwitchCutDeref( pNode, pCutBest, fPhase ); + else + pMatch->AreaFlow = Area1 = Map_SwitchCutGetDerefed( pNode, pCutBest, fPhase ); + } + + // save the old mapping + if ( pCutBest ) + MatchBest = pCutBest->M[fPhase]; + else + Map_MatchClean( &MatchBest ); + + // select the new best cut + fWorstLimit = pNode->tRequired[fPhase].Worst; + for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext ) + { + pMatch = pCut->M + fPhase; + if ( pMatch->pSupers == NULL ) + continue; + + // find the matches for the cut + Map_MatchNodeCut( p, pNode, pCut, fPhase, fWorstLimit ); + if ( pMatch->pSuperBest == NULL || pMatch->tArrive.Worst > fWorstLimit + p->fEpsilon ) + continue; + + // if the cut can be matched compare the matchings + if ( Map_MatchCompare( p, &MatchBest, pMatch, p->fMappingMode ) ) + { + pCutBest = pCut; + MatchBest = *pMatch; + // if we are mapping for delay, the worst-case limit should be tightened + if ( p->fMappingMode == 0 ) + fWorstLimit = MatchBest.tArrive.Worst; + } + } + + if ( pCutBest == NULL ) + return 1; + + // set the new mapping + pNode->pCutBest[fPhase] = pCutBest; + pCutBest->M[fPhase] = MatchBest; + + // reference the new cut if it used + if ( p->fMappingMode >= 2 && + (pNode->nRefAct[fPhase] > 0 || + (pNode->pCutBest[!fPhase] == NULL && pNode->nRefAct[!fPhase] > 0)) ) + { + if ( p->fMappingMode == 2 || p->fMappingMode == 3 ) + Area2 = Map_CutRef( pNode->pCutBest[fPhase], fPhase ); + else if ( p->fMappingMode == 4 ) + Area2 = Map_SwitchCutRef( pNode, pNode->pCutBest[fPhase], fPhase ); + else + assert( 0 ); + assert( Area2 < Area1 + p->fEpsilon ); + } + + // make sure that the requited times are met + assert( MatchBest.tArrive.Rise < pNode->tRequired[fPhase].Rise + p->fEpsilon ); + assert( MatchBest.tArrive.Fall < pNode->tRequired[fPhase].Fall + p->fEpsilon ); + return 1; +} + +/**Function************************************************************* + + Synopsis [Find the best matching of the cut.] + + Description [The parameters: the node (pNode), the cut (pCut), the phase to be matched + (fPhase), and the upper bound on the arrival times of the cut (fWorstLimit). This + procedure goes through the matching supergates up to the phase assignment, and selects the + best supergate, which will be used to map the cut. As a result of calling this procedure + the matching information is written into pMatch.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_MatchNodeCut( Map_Man_t * p, Map_Node_t * pNode, Map_Cut_t * pCut, int fPhase, float fWorstLimit ) +{ + Map_Match_t MatchBest, * pMatch = pCut->M + fPhase; + Map_Super_t * pSuper; + int i, Counter; + + // save the current match of the cut + MatchBest = *pMatch; + // go through the supergates + for ( pSuper = pMatch->pSupers, Counter = 0; pSuper; pSuper = pSuper->pNext, Counter++ ) + { + p->nMatches++; + // this is an attempt to reduce the runtime of matching and area + // at the cost of rare and very minor increase in delay + // (the supergates are sorted by increasing area) + if ( Counter == 30 ) + break; + + // go through different phases of the given match and supergate + pMatch->pSuperBest = pSuper; + for ( i = 0; i < (int)pSuper->nPhases; i++ ) + { + p->nPhases++; + // find the overall phase of this match + pMatch->uPhaseBest = pMatch->uPhase ^ pSuper->uPhases[i]; + if ( p->fMappingMode == 0 ) + { + // get the arrival time + Map_TimeCutComputeArrival( pNode, pCut, fPhase, fWorstLimit ); + // skip the cut if the arrival times exceed the required times + if ( pMatch->tArrive.Worst > fWorstLimit + p->fEpsilon ) + continue; + // get the area (area flow) + pMatch->AreaFlow = Map_CutGetAreaFlow( pCut, fPhase ); + } + else + { + // get the area (area flow) + if ( p->fMappingMode == 2 || p->fMappingMode == 3 ) + pMatch->AreaFlow = Map_CutGetAreaDerefed( pCut, fPhase ); + else if ( p->fMappingMode == 4 ) + pMatch->AreaFlow = Map_SwitchCutGetDerefed( pNode, pCut, fPhase ); + else + pMatch->AreaFlow = Map_CutGetAreaFlow( pCut, fPhase ); + // skip if the cut is too large + if ( pMatch->AreaFlow > MatchBest.AreaFlow + p->fEpsilon ) + continue; + // get the arrival time + Map_TimeCutComputeArrival( pNode, pCut, fPhase, fWorstLimit ); + // skip the cut if the arrival times exceed the required times + if ( pMatch->tArrive.Worst > fWorstLimit + p->fEpsilon ) + continue; + } + + // if the cut is non-trivial, compare it + if ( Map_MatchCompare( p, &MatchBest, pMatch, p->fMappingMode ) ) + { + MatchBest = *pMatch; + // if we are mapping for delay, the worst-case limit should be reduced + if ( p->fMappingMode == 0 ) + fWorstLimit = MatchBest.tArrive.Worst; + } + } + } + // set the best match + *pMatch = MatchBest; + + // recompute the arrival time and area (area flow) of this cut + if ( pMatch->pSuperBest ) + { + Map_TimeCutComputeArrival( pNode, pCut, fPhase, MAP_FLOAT_LARGE ); + if ( p->fMappingMode == 2 || p->fMappingMode == 3 ) + pMatch->AreaFlow = Map_CutGetAreaDerefed( pCut, fPhase ); + else if ( p->fMappingMode == 4 ) + pMatch->AreaFlow = Map_SwitchCutGetDerefed( pNode, pCut, fPhase ); + else + pMatch->AreaFlow = Map_CutGetAreaFlow( pCut, fPhase ); + } + return 1; +} + +/**Function************************************************************* + + Synopsis [Cleans the match.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MatchClean( Map_Match_t * pMatch ) +{ + memset( pMatch, 0, sizeof(Map_Match_t) ); + pMatch->AreaFlow = MAP_FLOAT_LARGE; // unassigned + pMatch->tArrive.Rise = MAP_FLOAT_LARGE; // unassigned + pMatch->tArrive.Fall = MAP_FLOAT_LARGE; // unassigned + pMatch->tArrive.Worst = MAP_FLOAT_LARGE; // unassigned +} + +/**Function************************************************************* + + Synopsis [Compares two matches.] + + Description [Returns 1 if the second match is better. Otherwise returns 0.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_MatchCompare( Map_Man_t * pMan, Map_Match_t * pM1, Map_Match_t * pM2, int fDoingArea ) +{ + if ( !fDoingArea ) + { + // compare the arrival times + if ( pM1->tArrive.Worst < pM2->tArrive.Worst - pMan->fEpsilon ) + return 0; + if ( pM1->tArrive.Worst > pM2->tArrive.Worst + pMan->fEpsilon ) + return 1; + // compare the areas or area flows + if ( pM1->AreaFlow < pM2->AreaFlow - pMan->fEpsilon ) + return 0; + if ( pM1->AreaFlow > pM2->AreaFlow + pMan->fEpsilon ) + return 1; + // compare the fanout limits + if ( pM1->pSuperBest->nFanLimit > pM2->pSuperBest->nFanLimit ) + return 0; + if ( pM1->pSuperBest->nFanLimit < pM2->pSuperBest->nFanLimit ) + return 1; + // compare the number of leaves + if ( pM1->pSuperBest->nFanins < pM2->pSuperBest->nFanins ) + return 0; + if ( pM1->pSuperBest->nFanins > pM2->pSuperBest->nFanins ) + return 1; + // otherwise prefer the old cut + return 0; + } + else + { + // compare the areas or area flows + if ( pM1->AreaFlow < pM2->AreaFlow - pMan->fEpsilon ) + return 0; + if ( pM1->AreaFlow > pM2->AreaFlow + pMan->fEpsilon ) + return 1; + // compare the arrival times + if ( pM1->tArrive.Worst < pM2->tArrive.Worst - pMan->fEpsilon ) + return 0; + if ( pM1->tArrive.Worst > pM2->tArrive.Worst + pMan->fEpsilon ) + return 1; + // compare the fanout limits + if ( pM1->pSuperBest->nFanLimit > pM2->pSuperBest->nFanLimit ) + return 0; + if ( pM1->pSuperBest->nFanLimit < pM2->pSuperBest->nFanLimit ) + return 1; + // compare the number of leaves + if ( pM1->pSuperBest->nFanins < pM2->pSuperBest->nFanins ) + return 0; + if ( pM1->pSuperBest->nFanins > pM2->pSuperBest->nFanins ) + return 1; + // otherwise prefer the old cut + return 0; + } +} + +/**Function************************************************************* + + Synopsis [Sets the PI arrival times.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingSetPiArrivalTimes( Map_Man_t * p ) +{ + Map_Node_t * pNode; + int i; + for ( i = 0; i < p->nInputs; i++ ) + { + pNode = p->pInputs[i]; + // set the arrival time of the positive phase + pNode->tArrival[1] = p->pInputArrivals[i]; + // set the arrival time of the negative phase + pNode->tArrival[0].Rise = pNode->tArrival[1].Fall + p->pSuperLib->tDelayInv.Rise; + pNode->tArrival[0].Fall = pNode->tArrival[1].Rise + p->pSuperLib->tDelayInv.Fall; + pNode->tArrival[0].Worst = MAP_MAX(pNode->tArrival[0].Rise, pNode->tArrival[0].Fall); + } +} + + +/**Function************************************************************* + + Synopsis [Attempts dropping one phase of the node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_NodeTryDroppingOnePhase( Map_Man_t * p, Map_Node_t * pNode ) +{ + Map_Match_t * pMatchBest0, * pMatchBest1; + float tWorst0Using1, tWorst1Using0; + int fUsePhase1, fUsePhase0; + + // nothing to do if one of the phases is already dropped + if ( pNode->pCutBest[0] == NULL || pNode->pCutBest[1] == NULL ) + return; + + // do not drop while recovering area flow + if ( p->fMappingMode == 1 )//|| p->fMappingMode == 2 ) + return; + + // get the pointers to the matches of the best cuts + pMatchBest0 = pNode->pCutBest[0]->M + 0; + pMatchBest1 = pNode->pCutBest[1]->M + 1; + + // get the worst arrival times of each phase + // implemented using the other phase with inverter added + tWorst0Using1 = Map_TimeMatchWithInverter( p, pMatchBest1 ); + tWorst1Using0 = Map_TimeMatchWithInverter( p, pMatchBest0 ); + + // consider the case of mapping for delay + if ( p->fMappingMode == 0 ) + { + // if the arrival time of a phase is larger than the arrival time + // of the opposite phase plus the inverter, drop this phase + if ( pMatchBest0->tArrive.Worst > tWorst0Using1 + p->fEpsilon ) + pNode->pCutBest[0] = NULL; + else if ( pMatchBest1->tArrive.Worst > tWorst1Using0 + p->fEpsilon ) + pNode->pCutBest[1] = NULL; + return; + } + + // do not perform replacement if one of the phases is unused + if ( pNode->nRefAct[0] == 0 || pNode->nRefAct[1] == 0 ) + return; + + // check if replacement of each phase is possible using required times + fUsePhase0 = fUsePhase1 = 0; + if ( p->fMappingMode == 2 ) + { + fUsePhase0 = (pNode->tRequired[1].Worst > tWorst1Using0 + 3*p->pSuperLib->tDelayInv.Worst + p->fEpsilon); + fUsePhase1 = (pNode->tRequired[0].Worst > tWorst0Using1 + 3*p->pSuperLib->tDelayInv.Worst + p->fEpsilon); + } + else if ( p->fMappingMode == 3 || p->fMappingMode == 4 ) + { + fUsePhase0 = (pNode->tRequired[1].Worst > tWorst1Using0 + p->fEpsilon); + fUsePhase1 = (pNode->tRequired[0].Worst > tWorst0Using1 + p->fEpsilon); + } + if ( !fUsePhase0 && !fUsePhase1 ) + return; + + // if replacement is possible both ways, use the one that works better + if ( fUsePhase0 && fUsePhase1 ) + { + if ( pMatchBest0->AreaFlow < pMatchBest1->AreaFlow ) + fUsePhase1 = 0; + else + fUsePhase0 = 0; + } + // only one phase should be used + assert( fUsePhase0 ^ fUsePhase1 ); + + // set the corresponding cut to NULL + if ( fUsePhase0 ) + { + // deref phase 1 cut if necessary + if ( p->fMappingMode >= 2 && pNode->nRefAct[1] > 0 ) + Map_CutDeref( pNode->pCutBest[1], 1 ); + // get rid of the cut + pNode->pCutBest[1] = NULL; + // ref phase 0 cut if necessary + if ( p->fMappingMode >= 2 && pNode->nRefAct[0] == 0 ) + Map_CutRef( pNode->pCutBest[0], 0 ); + } + else + { + // deref phase 0 cut if necessary + if ( p->fMappingMode >= 2 && pNode->nRefAct[0] > 0 ) + Map_CutDeref( pNode->pCutBest[0], 0 ); + // get rid of the cut + pNode->pCutBest[0] = NULL; + // ref phase 1 cut if necessary + if ( p->fMappingMode >= 2 && pNode->nRefAct[1] == 0 ) + Map_CutRef( pNode->pCutBest[1], 1 ); + } +} + + +/**Function************************************************************* + + Synopsis [Transfers the arrival times from the best cuts to the node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_NodeTransferArrivalTimes( Map_Man_t * p, Map_Node_t * pNode ) +{ + // if both phases are available, set their arrival times + if ( pNode->pCutBest[0] && pNode->pCutBest[1] ) + { + pNode->tArrival[0] = pNode->pCutBest[0]->M[0].tArrive; + pNode->tArrival[1] = pNode->pCutBest[1]->M[1].tArrive; + } + // if only one phase is available, compute the arrival time of other phase + else if ( pNode->pCutBest[0] ) + { + pNode->tArrival[0] = pNode->pCutBest[0]->M[0].tArrive; + pNode->tArrival[1].Rise = pNode->tArrival[0].Fall + p->pSuperLib->tDelayInv.Rise; + pNode->tArrival[1].Fall = pNode->tArrival[0].Rise + p->pSuperLib->tDelayInv.Fall; + pNode->tArrival[1].Worst = MAP_MAX(pNode->tArrival[1].Rise, pNode->tArrival[1].Fall); + } + else if ( pNode->pCutBest[1] ) + { + pNode->tArrival[1] = pNode->pCutBest[1]->M[1].tArrive; + pNode->tArrival[0].Rise = pNode->tArrival[1].Fall + p->pSuperLib->tDelayInv.Rise; + pNode->tArrival[0].Fall = pNode->tArrival[1].Rise + p->pSuperLib->tDelayInv.Fall; + pNode->tArrival[0].Worst = MAP_MAX(pNode->tArrival[0].Rise, pNode->tArrival[0].Fall); + } + else + { + assert( 0 ); + } + + assert( pNode->tArrival[0].Rise < pNode->tRequired[0].Rise + p->fEpsilon ); + assert( pNode->tArrival[0].Fall < pNode->tRequired[0].Fall + p->fEpsilon ); + + assert( pNode->tArrival[1].Rise < pNode->tRequired[1].Rise + p->fEpsilon ); + assert( pNode->tArrival[1].Fall < pNode->tRequired[1].Fall + p->fEpsilon ); +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// |