diff options
Diffstat (limited to 'src/map/mapper/mapperTime.c')
| -rw-r--r-- | src/map/mapper/mapperTime.c | 433 |
1 files changed, 172 insertions, 261 deletions
diff --git a/src/map/mapper/mapperTime.c b/src/map/mapper/mapperTime.c index ce909e24..6915116c 100644 --- a/src/map/mapper/mapperTime.c +++ b/src/map/mapper/mapperTime.c @@ -20,63 +20,40 @@ ABC_NAMESPACE_IMPL_START - //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// -static void Map_TimePropagateRequired( Map_Man_t * p, Map_NodeVec_t * vNodes ); -static void Map_TimePropagateRequiredPhase( Map_Man_t * p, Map_Node_t * pNode, int fPhase ); -static float Map_MatchComputeReqTimes( Map_Cut_t * pCut, int fPhase, Map_Time_t * ptArrRes ); - //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// -/**function************************************************************* - - synopsis [Computes the exact area associated with the cut.] - - description [] - - sideeffects [] - - seealso [] - -***********************************************************************/ -float Map_TimeMatchWithInverter( Map_Man_t * p, Map_Match_t * pMatch ) -{ - Map_Time_t tArrInv; - tArrInv.Fall = pMatch->tArrive.Rise + p->pSuperLib->tDelayInv.Fall; - tArrInv.Rise = pMatch->tArrive.Fall + p->pSuperLib->tDelayInv.Rise; - tArrInv.Worst = MAP_MAX( tArrInv.Rise, tArrInv.Fall ); - return tArrInv.Worst; -} - /**Function************************************************************* - Synopsis [Computes the arrival times of the cut recursively.] + Synopsis [Computes the maximum arrival times.] - Description [When computing the arrival time for the previously unused - cuts, their arrival time may be incorrect because their fanins have - incorrect arrival time. This procedure is called to fix this problem.] + Description [] SideEffects [] SeeAlso [] ***********************************************************************/ -void Map_TimeCutComputeArrival_rec( Map_Cut_t * pCut, int fPhase ) +float Map_TimeComputeArrivalMax( Map_Man_t * p ) { - int i, fPhaseLeaf; - for ( i = 0; i < pCut->nLeaves; i++ ) + float tReqMax, tReq; + int i, fPhase; + // get the critical PO arrival time + tReqMax = -MAP_FLOAT_LARGE; + for ( i = 0; i < p->nOutputs; i++ ) { - fPhaseLeaf = Map_CutGetLeafPhase( pCut, fPhase, i ); - if ( pCut->ppLeaves[i]->nRefAct[fPhaseLeaf] > 0 ) + if ( Map_NodeIsConst(p->pOutputs[i]) ) continue; - Map_TimeCutComputeArrival_rec( pCut->ppLeaves[i]->pCutBest[fPhaseLeaf], fPhaseLeaf ); + fPhase = !Map_IsComplement(p->pOutputs[i]); + tReq = Map_Regular(p->pOutputs[i])->tArrival[fPhase].Worst; + tReqMax = MAP_MAX( tReqMax, tReq ); } - Map_TimeCutComputeArrival( NULL, pCut, fPhase, MAP_FLOAT_LARGE ); + return tReqMax; } /**Function************************************************************* @@ -160,217 +137,7 @@ float Map_TimeCutComputeArrival( Map_Node_t * pNode, Map_Cut_t * pCut, int fPhas /**Function************************************************************* - Synopsis [Computes the maximum arrival times.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float Map_TimeComputeArrivalMax( Map_Man_t * p ) -{ - float tReqMax, tReq; - int i, fPhase; - // get the critical PO arrival time - tReqMax = -MAP_FLOAT_LARGE; - for ( i = 0; i < p->nOutputs; i++ ) - { - if ( Map_NodeIsConst(p->pOutputs[i]) ) - continue; - fPhase = !Map_IsComplement(p->pOutputs[i]); - tReq = Map_Regular(p->pOutputs[i])->tArrival[fPhase].Worst; - tReqMax = MAP_MAX( tReqMax, tReq ); - } - return tReqMax; -} - -/**Function************************************************************* - - Synopsis [Computes the required times of all nodes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Map_TimeComputeRequiredGlobal( Map_Man_t * p ) -{ - p->fRequiredGlo = Map_TimeComputeArrivalMax( p ); - // update the required times according to the target - if ( p->DelayTarget != -1 ) - { - if ( p->fRequiredGlo > p->DelayTarget + p->fEpsilon ) - { - if ( p->fMappingMode == 1 ) - printf( "Cannot meet the target required times (%4.2f). Continue anyway.\n", p->DelayTarget ); - } - else if ( p->fRequiredGlo < p->DelayTarget - p->fEpsilon ) - { - if ( p->fMappingMode == 1 && p->fVerbose ) - printf( "Relaxing the required times from (%4.2f) to the target (%4.2f).\n", p->fRequiredGlo, p->DelayTarget ); - p->fRequiredGlo = p->DelayTarget; - } - } - Map_TimeComputeRequired( p, p->fRequiredGlo ); -} - -/**Function************************************************************* - - Synopsis [Computes the required times of all nodes.] - - Description [This procedure assumes that the nodes used in the mapping - are collected in p->vMapping.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Map_TimeComputeRequired( Map_Man_t * p, float fRequired ) -{ - Map_Time_t * ptTime, * ptTimeA; - int fPhase, i; - - // clean the required times - for ( i = 0; i < p->vAnds->nSize; i++ ) - { - p->vAnds->pArray[i]->tRequired[0].Rise = MAP_FLOAT_LARGE; - p->vAnds->pArray[i]->tRequired[0].Fall = MAP_FLOAT_LARGE; - p->vAnds->pArray[i]->tRequired[0].Worst = MAP_FLOAT_LARGE; - p->vAnds->pArray[i]->tRequired[1].Rise = MAP_FLOAT_LARGE; - p->vAnds->pArray[i]->tRequired[1].Fall = MAP_FLOAT_LARGE; - p->vAnds->pArray[i]->tRequired[1].Worst = MAP_FLOAT_LARGE; - } - - // set the required times for the POs - for ( i = 0; i < p->nOutputs; i++ ) - { - fPhase = !Map_IsComplement(p->pOutputs[i]); - ptTime = Map_Regular(p->pOutputs[i])->tRequired + fPhase; - ptTimeA = Map_Regular(p->pOutputs[i])->tArrival + fPhase; - - // if external required time can be achieved, use it - if ( p->pOutputRequireds && p->pOutputRequireds[i].Worst > 0 && ptTimeA->Worst <= p->pOutputRequireds[i].Worst )//&& p->pOutputRequireds[i].Worst <= fRequired ) - ptTime->Rise = ptTime->Fall = ptTime->Worst = p->pOutputRequireds[i].Worst; - // if external required cannot be achieved, set the earliest possible arrival time - else if ( p->pOutputRequireds && p->pOutputRequireds[i].Worst > 0 && ptTimeA->Worst > p->pOutputRequireds[i].Worst ) - ptTime->Rise = ptTime->Fall = ptTime->Worst = ptTimeA->Worst; - // otherwise, set the global required time - else - ptTime->Rise = ptTime->Fall = ptTime->Worst = fRequired; - } - - // sorts the nodes in the decreasing order of levels - // this puts the nodes in reverse topological order -// Map_MappingSortByLevel( p, p->vMapping ); - // the array is already sorted by construction in Map_MappingSetRefs() - - Map_TimePropagateRequired( p, p->vMapping ); -} - -/**Function************************************************************* - - Synopsis [Computes the required times of the given nodes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Map_TimePropagateRequired( Map_Man_t * p, Map_NodeVec_t * vNodes ) -{ - Map_Node_t * pNode; - Map_Time_t tReqOutTest, * ptReqOutTest = &tReqOutTest; - Map_Time_t * ptReqIn, * ptReqOut; - int fPhase, k; - - // go through the nodes in the reverse topological order - for ( k = 0; k < vNodes->nSize; k++ ) - { - pNode = vNodes->pArray[k]; - - // this computation works for regular nodes only - assert( !Map_IsComplement(pNode) ); - // at least one phase should be mapped - assert( pNode->pCutBest[0] != NULL || pNode->pCutBest[1] != NULL ); - // the node should be used in the currently assigned mapping - assert( pNode->nRefAct[0] > 0 || pNode->nRefAct[1] > 0 ); - - // if one of the cuts is not given, project the required times from the other cut - if ( pNode->pCutBest[0] == NULL || pNode->pCutBest[1] == NULL ) - { -// assert( 0 ); - // get the missing phase - fPhase = (pNode->pCutBest[1] == NULL); - // check if the missing phase is needed in the mapping - if ( pNode->nRefAct[fPhase] > 0 ) - { - // get the pointers to the required times of the missing phase - ptReqOut = pNode->tRequired + fPhase; -// assert( ptReqOut->Fall < MAP_FLOAT_LARGE ); - // get the pointers to the required times of the present phase - ptReqIn = pNode->tRequired + !fPhase; - // propagate the required times from the missing phase to the present phase - // tArrInv.Fall = pMatch->tArrive.Rise + p->pSuperLib->tDelayInv.Fall; - // tArrInv.Rise = pMatch->tArrive.Fall + p->pSuperLib->tDelayInv.Rise; - ptReqIn->Fall = MAP_MIN( ptReqIn->Fall, ptReqOut->Rise - p->pSuperLib->tDelayInv.Rise ); - ptReqIn->Rise = MAP_MIN( ptReqIn->Rise, ptReqOut->Fall - p->pSuperLib->tDelayInv.Fall ); - } - } - - // finalize the worst case computation - pNode->tRequired[0].Worst = MAP_MIN( pNode->tRequired[0].Fall, pNode->tRequired[0].Rise ); - pNode->tRequired[1].Worst = MAP_MIN( pNode->tRequired[1].Fall, pNode->tRequired[1].Rise ); - - // skip the PIs - if ( !Map_NodeIsAnd(pNode) ) - continue; - - // propagate required times of different phases of the node - // the ordering of phases does not matter since they are mapped independently - if ( pNode->pCutBest[0] && pNode->tRequired[0].Worst < MAP_FLOAT_LARGE ) - Map_TimePropagateRequiredPhase( p, pNode, 0 ); - if ( pNode->pCutBest[1] && pNode->tRequired[1].Worst < MAP_FLOAT_LARGE ) - Map_TimePropagateRequiredPhase( p, pNode, 1 ); - } - - // in the end, we verify the required times - // for this, we compute the arrival times of the outputs of each phase - // of the supergates using the fanins' required times as the fanins' arrival times - // the resulting arrival time of the supergate should be less than the actual required time - for ( k = 0; k < vNodes->nSize; k++ ) - { - pNode = vNodes->pArray[k]; - if ( !Map_NodeIsAnd(pNode) ) - continue; - // verify that the required times are propagated correctly -// if ( pNode->pCutBest[0] && (pNode->nRefAct[0] > 0 || pNode->pCutBest[1] == NULL) ) - if ( pNode->pCutBest[0] && pNode->tRequired[0].Worst < MAP_FLOAT_LARGE/2 ) - { - Map_MatchComputeReqTimes( pNode->pCutBest[0], 0, ptReqOutTest ); -// assert( ptReqOutTest->Rise < pNode->tRequired[0].Rise + p->fEpsilon ); -// assert( ptReqOutTest->Fall < pNode->tRequired[0].Fall + p->fEpsilon ); - } -// if ( pNode->pCutBest[1] && (pNode->nRefAct[1] > 0 || pNode->pCutBest[0] == NULL) ) - if ( pNode->pCutBest[1] && pNode->tRequired[1].Worst < MAP_FLOAT_LARGE/2 ) - { - Map_MatchComputeReqTimes( pNode->pCutBest[1], 1, ptReqOutTest ); -// assert( ptReqOutTest->Rise < pNode->tRequired[1].Rise + p->fEpsilon ); -// assert( ptReqOutTest->Fall < pNode->tRequired[1].Fall + p->fEpsilon ); - } - } - -} - -/**Function************************************************************* - - Synopsis [Computes the required times of the given nodes.] + Synopsis [] Description [] @@ -446,20 +213,6 @@ void Map_TimePropagateRequiredPhase( Map_Man_t * p, Map_Node_t * pNode, int fPha assert( pNode->tArrival[fPhase].Rise < ptReqOut->Rise + p->fEpsilon ); assert( pNode->tArrival[fPhase].Fall < ptReqOut->Fall + p->fEpsilon ); } - -/**Function************************************************************* - - Synopsis [Computes the arrival times of the cut.] - - Description [Computes the arrival times of the cut if it is implemented using - the given supergate with the given phase. Uses the constraint-type specification - of rise/fall arrival times.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ float Map_MatchComputeReqTimes( Map_Cut_t * pCut, int fPhase, Map_Time_t * ptArrRes ) { Map_Time_t * ptArrIn; @@ -518,6 +271,164 @@ float Map_MatchComputeReqTimes( Map_Cut_t * pCut, int fPhase, Map_Time_t * ptArr } +/**Function************************************************************* + + Synopsis [Computes the required times of all nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_TimePropagateRequired( Map_Man_t * p ) +{ + Map_Node_t * pNode; + Map_Time_t tReqOutTest, * ptReqOutTest = &tReqOutTest; + Map_Time_t * ptReqIn, * ptReqOut; + int fPhase, k; + + // go through the nodes in the reverse topological order + for ( k = p->vMapObjs->nSize - 1; k >= 0; k-- ) + { + pNode = p->vMapObjs->pArray[k]; + if ( pNode->nRefAct[2] == 0 ) + continue; + + // propagate required times through the buffer + if ( Map_NodeIsBuf(pNode) ) + { + assert( pNode->p2 == NULL ); + Map_Regular(pNode->p1)->tRequired[ Map_IsComplement(pNode->p1)] = pNode->tRequired[0]; + Map_Regular(pNode->p1)->tRequired[!Map_IsComplement(pNode->p1)] = pNode->tRequired[1]; + continue; + } + + // this computation works for regular nodes only + assert( !Map_IsComplement(pNode) ); + // at least one phase should be mapped + assert( pNode->pCutBest[0] != NULL || pNode->pCutBest[1] != NULL ); + // the node should be used in the currently assigned mapping + assert( pNode->nRefAct[0] > 0 || pNode->nRefAct[1] > 0 ); + + // if one of the cuts is not given, project the required times from the other cut + if ( pNode->pCutBest[0] == NULL || pNode->pCutBest[1] == NULL ) + { +// assert( 0 ); + // get the missing phase + fPhase = (pNode->pCutBest[1] == NULL); + // check if the missing phase is needed in the mapping + if ( pNode->nRefAct[fPhase] > 0 ) + { + // get the pointers to the required times of the missing phase + ptReqOut = pNode->tRequired + fPhase; +// assert( ptReqOut->Fall < MAP_FLOAT_LARGE ); + // get the pointers to the required times of the present phase + ptReqIn = pNode->tRequired + !fPhase; + // propagate the required times from the missing phase to the present phase + // tArrInv.Fall = pMatch->tArrive.Rise + p->pSuperLib->tDelayInv.Fall; + // tArrInv.Rise = pMatch->tArrive.Fall + p->pSuperLib->tDelayInv.Rise; + ptReqIn->Fall = MAP_MIN( ptReqIn->Fall, ptReqOut->Rise - p->pSuperLib->tDelayInv.Rise ); + ptReqIn->Rise = MAP_MIN( ptReqIn->Rise, ptReqOut->Fall - p->pSuperLib->tDelayInv.Fall ); + } + } + + // finalize the worst case computation + pNode->tRequired[0].Worst = MAP_MIN( pNode->tRequired[0].Fall, pNode->tRequired[0].Rise ); + pNode->tRequired[1].Worst = MAP_MIN( pNode->tRequired[1].Fall, pNode->tRequired[1].Rise ); + + // skip the PIs + if ( !Map_NodeIsAnd(pNode) ) + continue; + + // propagate required times of different phases of the node + // the ordering of phases does not matter since they are mapped independently + if ( pNode->pCutBest[0] && pNode->tRequired[0].Worst < MAP_FLOAT_LARGE ) + Map_TimePropagateRequiredPhase( p, pNode, 0 ); + if ( pNode->pCutBest[1] && pNode->tRequired[1].Worst < MAP_FLOAT_LARGE ) + Map_TimePropagateRequiredPhase( p, pNode, 1 ); + } + + // in the end, we verify the required times + // for this, we compute the arrival times of the outputs of each phase + // of the supergates using the fanins' required times as the fanins' arrival times + // the resulting arrival time of the supergate should be less than the actual required time + for ( k = p->vMapObjs->nSize - 1; k >= 0; k-- ) + { + pNode = p->vMapObjs->pArray[k]; + if ( pNode->nRefAct[2] == 0 ) + continue; + if ( !Map_NodeIsAnd(pNode) ) + continue; + // verify that the required times are propagated correctly +// if ( pNode->pCutBest[0] && (pNode->nRefAct[0] > 0 || pNode->pCutBest[1] == NULL) ) + if ( pNode->pCutBest[0] && pNode->tRequired[0].Worst < MAP_FLOAT_LARGE/2 ) + { + Map_MatchComputeReqTimes( pNode->pCutBest[0], 0, ptReqOutTest ); +// assert( ptReqOutTest->Rise < pNode->tRequired[0].Rise + p->fEpsilon ); +// assert( ptReqOutTest->Fall < pNode->tRequired[0].Fall + p->fEpsilon ); + } +// if ( pNode->pCutBest[1] && (pNode->nRefAct[1] > 0 || pNode->pCutBest[0] == NULL) ) + if ( pNode->pCutBest[1] && pNode->tRequired[1].Worst < MAP_FLOAT_LARGE/2 ) + { + Map_MatchComputeReqTimes( pNode->pCutBest[1], 1, ptReqOutTest ); +// assert( ptReqOutTest->Rise < pNode->tRequired[1].Rise + p->fEpsilon ); +// assert( ptReqOutTest->Fall < pNode->tRequired[1].Fall + p->fEpsilon ); + } + } +} +void Map_TimeComputeRequiredGlobal( Map_Man_t * p ) +{ + Map_Time_t * ptTime, * ptTimeA; + int fPhase, i; + // update the required times according to the target + p->fRequiredGlo = Map_TimeComputeArrivalMax( p ); + if ( p->DelayTarget != -1 ) + { + if ( p->fRequiredGlo > p->DelayTarget + p->fEpsilon ) + { + if ( p->fMappingMode == 1 ) + printf( "Cannot meet the target required times (%4.2f). Continue anyway.\n", p->DelayTarget ); + } + else if ( p->fRequiredGlo < p->DelayTarget - p->fEpsilon ) + { + if ( p->fMappingMode == 1 && p->fVerbose ) + printf( "Relaxing the required times from (%4.2f) to the target (%4.2f).\n", p->fRequiredGlo, p->DelayTarget ); + p->fRequiredGlo = p->DelayTarget; + } + } + // clean the required times + for ( i = 0; i < p->vMapObjs->nSize; i++ ) + { + p->vMapObjs->pArray[i]->tRequired[0].Rise = MAP_FLOAT_LARGE; + p->vMapObjs->pArray[i]->tRequired[0].Fall = MAP_FLOAT_LARGE; + p->vMapObjs->pArray[i]->tRequired[0].Worst = MAP_FLOAT_LARGE; + p->vMapObjs->pArray[i]->tRequired[1].Rise = MAP_FLOAT_LARGE; + p->vMapObjs->pArray[i]->tRequired[1].Fall = MAP_FLOAT_LARGE; + p->vMapObjs->pArray[i]->tRequired[1].Worst = MAP_FLOAT_LARGE; + } + // set the required times for the POs + for ( i = 0; i < p->nOutputs; i++ ) + { + fPhase = !Map_IsComplement(p->pOutputs[i]); + ptTime = Map_Regular(p->pOutputs[i])->tRequired + fPhase; + ptTimeA = Map_Regular(p->pOutputs[i])->tArrival + fPhase; + + // if external required time can be achieved, use it + if ( p->pOutputRequireds && p->pOutputRequireds[i].Worst > 0 && ptTimeA->Worst <= p->pOutputRequireds[i].Worst )//&& p->pOutputRequireds[i].Worst <= p->fRequiredGlo ) + ptTime->Rise = ptTime->Fall = ptTime->Worst = p->pOutputRequireds[i].Worst; + // if external required cannot be achieved, set the earliest possible arrival time + else if ( p->pOutputRequireds && p->pOutputRequireds[i].Worst > 0 && ptTimeA->Worst > p->pOutputRequireds[i].Worst ) + ptTime->Rise = ptTime->Fall = ptTime->Worst = ptTimeA->Worst; + // otherwise, set the global required time + else + ptTime->Rise = ptTime->Fall = ptTime->Worst = p->fRequiredGlo; + } + // visit nodes in the reverse topological order + Map_TimePropagateRequired( p ); +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// |