From c347f2b90b1164fe50b4bb061b3cd4e63bbfeda4 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Fri, 16 Mar 2012 15:43:08 -0700 Subject: Alternative way of computing delay in SOP balancing. --- src/map/if/if.h | 1 + src/map/if/ifMap.c | 8 +++ src/map/if/ifTime.c | 155 +++++++++++++++++++++++++++++++++++++++++++++++++++- 3 files changed, 161 insertions(+), 3 deletions(-) (limited to 'src/map/if') diff --git a/src/map/if/if.h b/src/map/if/if.h index aa851d9d..6dda12a7 100644 --- a/src/map/if/if.h +++ b/src/map/if/if.h @@ -486,6 +486,7 @@ extern void If_ManImproveMapping( If_Man_t * p ); extern int If_ManPerformMappingSeq( If_Man_t * p ); /*=== ifTime.c ============================================================*/ extern int If_CutDelaySopCost( If_Man_t * p, If_Cut_t * pCut ); +extern int If_CutDelaySopCost2( If_Man_t * p, If_Cut_t * pCut ); extern Vec_Wrd_t * If_CutDelaySopArray( If_Man_t * p, If_Cut_t * pCut ); extern float If_CutDelay( If_Man_t * p, If_Obj_t * pObj, If_Cut_t * pCut ); extern void If_CutPropagateRequired( If_Man_t * p, If_Obj_t * pObj, If_Cut_t * pCut, float Required ); diff --git a/src/map/if/ifMap.c b/src/map/if/ifMap.c index f40244ca..2e0115ef 100644 --- a/src/map/if/ifMap.c +++ b/src/map/if/ifMap.c @@ -159,7 +159,11 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPrep if ( p->pPars->fUserRecLib ) pCut->Delay = If_CutDelayRecCost(p, pCut, pObj); else if(p->pPars->fDelayOpt) + { +// pCut->Delay = If_CutDelaySopCost(p,pCut); +// pCut->Delay = If_CutDelaySopCost2(p,pCut); pCut->Delay = If_CutDelaySopCost(p,pCut); + } else pCut->Delay = If_CutDelay( p, pObj, pCut ); // assert( pCut->Delay <= pObj->Required + p->fEpsilon ); @@ -230,7 +234,11 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPrep if ( p->pPars->fUserRecLib ) pCut->Delay = If_CutDelayRecCost(p, pCut, pObj); else if (p->pPars->fDelayOpt) + { +// pCut->Delay = If_CutDelaySopCost(p, pCut); +// pCut->Delay = If_CutDelaySopCost2(p, pCut); pCut->Delay = If_CutDelaySopCost(p, pCut); + } else pCut->Delay = If_CutDelay( p, pObj, pCut ); //if ( pCut->Cost == IF_COST_MAX ) diff --git a/src/map/if/ifTime.c b/src/map/if/ifTime.c index b2687a77..95a856b8 100644 --- a/src/map/if/ifTime.c +++ b/src/map/if/ifTime.c @@ -34,6 +34,9 @@ static float s_ExtraDel[2][3] = { {1.0, 1.0, (float)0.1}, {1.0, 1.0, (float)0.1} static void If_CutSortInputPins( If_Man_t * p, If_Cut_t * pCut, int * pPinPerm, float * pPinDelays ); +int s_timeNew; +int s_timeOld; + //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// @@ -249,21 +252,25 @@ Vec_Wrd_t * If_CutDelaySopAnds( If_Man_t * p, If_Cut_t * pCut, Vec_Int_t * vCove ***********************************************************************/ Vec_Wrd_t * If_CutDelaySopArray( If_Man_t * p, If_Cut_t * pCut ) { + int clk; Vec_Wrd_t * vAnds; int RetValue; if ( p->vCover == NULL ) - { p->vCover = Vec_IntAlloc(0); + if ( p->vAnds == NULL ) p->vAnds = Vec_WrdAlloc(100); + if ( p->vAndGate == NULL ) p->vAndGate = Vec_WrdAlloc(100); + if ( p->vOrGate == NULL ) p->vOrGate = Vec_WrdAlloc(100); - - } RetValue = Kit_TruthIsop( If_CutTruth(pCut), If_CutLeaveNum(pCut), p->vCover, 1 ); if ( RetValue == -1 ) return NULL; assert( RetValue == 0 || RetValue == 1 ); + + clk = clock(); vAnds = If_CutDelaySopAnds( p, pCut, p->vCover, RetValue ^ pCut->fCompl ); + s_timeOld += clock() - clk; /* if ( pCut->nLeaves <= 5 ) { @@ -384,7 +391,9 @@ int If_CutDelaySopCost( If_Man_t * p, If_Cut_t * pCut ) { Delay = If_CutDelayLeafDepth( vAnds, i ); pCut->pPerm[i] = (char)(Delay == -IF_BIG_CHAR ? IF_BIG_CHAR : Delay); +//printf( "%d ", pCut->pPerm[i] ); } +//printf( " (%d)\n", Leaf.Delay ); // verify the delay // Delay = If_CutDelay( p, pObj, pCut ); // assert( (int)Leaf.Delay == Delay ); @@ -392,7 +401,147 @@ int If_CutDelaySopCost( If_Man_t * p, If_Cut_t * pCut ) } +/**Function************************************************************* + + Synopsis [Alternative computation of delay.] + + Description [] + + SideEffects [] + + SeeAlso [] +***********************************************************************/ +word If_CutDelayCountFormula( Vec_Int_t * vNums ) +{ + word Count = 0; + int i, Entry; + Vec_IntForEachEntry( vNums, Entry, i ) + { + if ( Entry < 0 ) + continue; + assert( Entry < 60 ); + Count += ((word)1) << Entry; + } + return Count; +} +int If_CutDelayUseFormula( Vec_Int_t * vNums ) +{ + int i, k, fChanges = 1; +// word Count = If_CutDelayCountFormula( vNums ); +// Vec_IntPrint( vNums ); + while ( fChanges ) + { + fChanges = 0; + for ( i = Vec_IntSize(vNums) - 1; i > 0; i-- ) + if ( vNums->pArray[i] == vNums->pArray[i-1] ) + { + vNums->pArray[i-1]++; + for ( k = i; k < Vec_IntSize(vNums) - 1; k++ ) + vNums->pArray[k] = vNums->pArray[k+1]; + Vec_IntShrink( vNums, Vec_IntSize(vNums)-1 ); + fChanges = 1; + } + } +// assert( Count == If_CutDelayCountFormula(vNums) ); +// Vec_IntPrint( vNums ); +// printf( "\n" ); + if ( Vec_IntSize(vNums) == 1 ) + return vNums->pArray[0]; + return Vec_IntEntryLast(vNums) + 1; +} +int If_CutDelaySopAnds2( If_Man_t * p, If_Cut_t * pCut, Vec_Int_t * vCover, int fCompl, int * pArea ) +{ + Vec_Int_t * vOrGate2 = (Vec_Int_t *)p->vOrGate; + Vec_Int_t * vAndGate2 = (Vec_Int_t *)p->vAndGate; + int Arrivals[16]; + If_Obj_t * pLeaf; + int i, k, Entry, Literal; + *pArea = 0; + if ( Vec_IntSize(vCover) == 0 ) // const 0 + { + assert( fCompl == 0 ); + return 0; + } + if ( Vec_IntSize(vCover) == 1 && Vec_IntEntry(vCover, 0) == 0 ) // const 1 + { + assert( fCompl == 0 ); + return 0; + } + If_CutForEachLeaf( p, pCut, pLeaf, k ) + Arrivals[k] = (int)If_ObjCutBest(pLeaf)->Delay; + // iterate through the cubes + Vec_IntClear( vOrGate2 ); + Vec_IntForEachEntry( vCover, Entry, i ) + { + Vec_IntClear( vAndGate2 ); + for ( k = 0; k < (int)pCut->nLeaves; k++ ) + { + Literal = 3 & (Entry >> (k << 1)); + if ( Literal == 1 ) // neg literal + Vec_IntPushOrder( vAndGate2, Arrivals[k] ); + else if ( Literal == 2 ) // pos literal + Vec_IntPushOrder( vAndGate2, Arrivals[k] ); + else if ( Literal != 0 ) + assert( 0 ); + } + *pArea += Vec_IntSize(vAndGate2) - 1; + Vec_IntPushOrder( vOrGate2, If_CutDelayUseFormula(vAndGate2) ); + } + *pArea += Vec_IntSize(vOrGate2) - 1; + return If_CutDelayUseFormula(vOrGate2); +} +int If_CutDelaySopArray2( If_Man_t * p, If_Cut_t * pCut, int * pArea ) +{ + int clk; + int RetValue; + if ( p->vCover == NULL ) + p->vCover = Vec_IntAlloc(0); + if ( p->vAndGate == NULL ) + p->vAndGate = Vec_WrdAlloc(100); + if ( p->vOrGate == NULL ) + p->vOrGate = Vec_WrdAlloc(100); + RetValue = Kit_TruthIsop( If_CutTruth(pCut), If_CutLeaveNum(pCut), p->vCover, 1 ); + if ( RetValue == -1 ) + return -1; + assert( RetValue == 0 || RetValue == 1 ); + + clk = clock(); + RetValue = If_CutDelaySopAnds2( p, pCut, p->vCover, RetValue ^ pCut->fCompl, pArea ); +// RetValue = If_CutDelaySopAnds2_( p, pCut, p->vCover, RetValue ^ pCut->fCompl, pArea ); + s_timeNew += clock() - clk; + return RetValue; +} +int If_CutDelaySopCost2( If_Man_t * p, If_Cut_t * pCut ) +{ + If_Obj_t * pLeaf; + int i, DelayMax, Area; + // mark cut as a user cut + pCut->fUser = 1; + DelayMax = If_CutDelaySopArray2( p, pCut, &Area ); + if ( DelayMax == -1 ) + { + assert( 0 ); + return ABC_INFINITY; + } + // get the cost + if ( pCut->nLeaves > 2 ) + pCut->Cost = Area; + else + pCut->Cost = 1; + // get the permutation + If_CutForEachLeaf( p, pCut, pLeaf, i ) + { + assert( DelayMax == 0 || DelayMax >= (int)If_ObjCutBest(pLeaf)->Delay ); + pCut->pPerm[i] = (char)(DelayMax - (int)If_ObjCutBest(pLeaf)->Delay); +// printf( "%d ", pCut->pPerm[i] ); + } +// printf( "(%d) ", DelayMax ); + // verify the delay +// Delay = If_CutDelay( p, pObj, pCut ); +// assert( (int)Leaf.Delay == Delay ); + return DelayMax; +} -- cgit v1.2.3