From 5fb7c676c27c689a4a10773c6e4b28af32db3e8b Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sat, 7 Jul 2012 13:13:32 -0700 Subject: Procedure to compute truth tables for POs of GIA. --- src/aig/gia/gia.h | 5 ++ src/aig/gia/giaMan.c | 1 + src/aig/gia/giaUtil.c | 192 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/base/abci/abc.c | 3 +- 4 files changed, 199 insertions(+), 2 deletions(-) (limited to 'src') diff --git a/src/aig/gia/gia.h b/src/aig/gia/gia.h index e56e88aa..a5c075c3 100644 --- a/src/aig/gia/gia.h +++ b/src/aig/gia/gia.h @@ -155,6 +155,10 @@ struct Gia_Man_t_ word nHashHit; // hash table hit word nHashMiss; // hash table miss int fVerbose; // verbose reports + Vec_Wrd_t * vTtMemory; // truth table memory + int nTtVars; // truth table variables + int nTtWords; // truth table words + int iTtNum; // truth table current number }; @@ -942,6 +946,7 @@ extern Vec_Int_t * Gia_VtaConvertToGla( Gia_Man_t * p, Vec_Int_t * vVta extern Vec_Int_t * Gia_VtaConvertFromGla( Gia_Man_t * p, Vec_Int_t * vGla, int nFrames ); extern Vec_Int_t * Gia_FlaConvertToGla( Gia_Man_t * p, Vec_Int_t * vFla ); extern Vec_Int_t * Gia_GlaConvertToFla( Gia_Man_t * p, Vec_Int_t * vGla ); +extern unsigned * Gia_ManComputePoTt( Gia_Man_t * p, Gia_Obj_t * pObj ); /*=== giaCTas.c ===========================================================*/ typedef struct Tas_Man_t_ Tas_Man_t; diff --git a/src/aig/gia/giaMan.c b/src/aig/gia/giaMan.c index 61283e09..d610882c 100644 --- a/src/aig/gia/giaMan.c +++ b/src/aig/gia/giaMan.c @@ -86,6 +86,7 @@ void Gia_ManStop( Gia_Man_t * p ) Vec_IntFreeP( &p->vObjClasses ); Vec_IntFreeP( &p->vLevels ); Vec_IntFreeP( &p->vTruths ); + Vec_WrdFreeP( &p->vTtMemory ); Vec_IntFree( p->vCis ); Vec_IntFree( p->vCos ); ABC_FREE( p->pTravIds ); diff --git a/src/aig/gia/giaUtil.c b/src/aig/gia/giaUtil.c index 1a6789b5..bef6c229 100644 --- a/src/aig/gia/giaUtil.c +++ b/src/aig/gia/giaUtil.c @@ -1431,6 +1431,198 @@ Vec_Int_t * Gia_GlaConvertToFla( Gia_Man_t * p, Vec_Int_t * vGla ) return vFla; } +/**Function************************************************************* + + Synopsis [Testing the speedup due to grouping POs into batches.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Gia_ManCollectObjs_rec( Gia_Man_t * p, int iObjId, Vec_Int_t * vObjs, int Limit ) +{ + Gia_Obj_t * pObj; + if ( Vec_IntSize(vObjs) == Limit ) + return; + if ( Gia_ObjIsTravIdCurrentId(p, iObjId) ) + return; + Gia_ObjSetTravIdCurrentId(p, iObjId); + pObj = Gia_ManObj( p, iObjId ); + if ( Gia_ObjIsAnd(pObj) ) + { + Gia_ManCollectObjs_rec( p, Gia_ObjFaninId0p(p, pObj), vObjs, Limit ); + if ( Vec_IntSize(vObjs) == Limit ) + return; + Gia_ManCollectObjs_rec( p, Gia_ObjFaninId1p(p, pObj), vObjs, Limit ); + if ( Vec_IntSize(vObjs) == Limit ) + return; + } + Vec_IntPush( vObjs, iObjId ); +} +unsigned * Gia_ManComputePoTruthTables( Gia_Man_t * p, int nBytesMax ) +{ + int nVars = Gia_ManPiNum(p); + int nTruthWords = Abc_TruthWordNum( nVars ); + int nTruths = nBytesMax / (sizeof(unsigned) * nTruthWords); + int nTotalNodes = 0, nRounds = 0; + Vec_Int_t * vObjs; + Gia_Obj_t * pObj; + clock_t clk = clock(); + int i; + printf( "Var = %d. Words = %d. Truths = %d.\n", nVars, nTruthWords, nTruths ); + vObjs = Vec_IntAlloc( nTruths ); + Gia_ManIncrementTravId( p ); + Gia_ManForEachPo( p, pObj, i ) + { + Gia_ManCollectObjs_rec( p, Gia_ObjFaninId0p(p, pObj), vObjs, nTruths ); + if ( Vec_IntSize(vObjs) == nTruths ) + { + nRounds++; +// printf( "%d ", i ); + nTotalNodes += Vec_IntSize( vObjs ); + Vec_IntClear( vObjs ); + Gia_ManIncrementTravId( p ); + } + } +// printf( "\n" ); + nTotalNodes += Vec_IntSize( vObjs ); + Vec_IntFree( vObjs ); + + printf( "Rounds = %d. Objects = %d. Total = %d. ", nRounds, Gia_ManObjNum(p), nTotalNodes ); + Abc_PrintTime( 1, "Time", clock() - clk ); + + return NULL; +} + + +/**Function************************************************************* + + Synopsis [Computing the truth table of one PO.] + + Description [The truth table should be used (or saved into the user's + storage) before this procedure is called next time!] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Gia_ManComputePoTt_rec( Gia_Man_t * p, Gia_Obj_t * pObj ) +{ + word * pTruth0, * pTruth1, * pTruth, * pTruthL; + if ( Gia_ObjIsTravIdCurrent(p, pObj) ) + return pObj->Value; + Gia_ObjSetTravIdCurrent(p, pObj); + assert( Gia_ObjIsAnd(pObj) ); + pTruth0 = Vec_WrdArray(p->vTtMemory) + p->nTtWords * Gia_ManComputePoTt_rec( p, Gia_ObjFanin0(pObj) ); + pTruth1 = Vec_WrdArray(p->vTtMemory) + p->nTtWords * Gia_ManComputePoTt_rec( p, Gia_ObjFanin1(pObj) ); + assert( p->nTtWords * p->iTtNum < Vec_WrdSize(p->vTtMemory) ); + pTruth = Vec_WrdArray(p->vTtMemory) + p->nTtWords * p->iTtNum++; + pTruthL = Vec_WrdArray(p->vTtMemory) + p->nTtWords * p->iTtNum; + if ( Gia_ObjFaninC0(pObj) ) + { + if ( Gia_ObjFaninC1(pObj) ) + while ( pTruth < pTruthL ) + *pTruth++ = ~*pTruth0++ & ~*pTruth1++; + else + while ( pTruth < pTruthL ) + *pTruth++ = ~*pTruth0++ & *pTruth1++; + } + else + { + if ( Gia_ObjFaninC1(pObj) ) + while ( pTruth < pTruthL ) + *pTruth++ = *pTruth0++ & ~*pTruth1++; + else + while ( pTruth < pTruthL ) + *pTruth++ = *pTruth0++ & *pTruth1++; + } + return p->iTtNum-1; +} +unsigned * Gia_ManComputePoTt( Gia_Man_t * p, Gia_Obj_t * pObj ) +{ + Gia_Obj_t * pTemp; + word * pTruth; + int i, k; + // this procedure works only for primary outputs + assert( Gia_ObjIsCo(pObj) ); + if ( p->vTtMemory == NULL ) + { + word Truth6[7] = { + 0x0000000000000000, + 0xAAAAAAAAAAAAAAAA, + 0xCCCCCCCCCCCCCCCC, + 0xF0F0F0F0F0F0F0F0, + 0xFF00FF00FF00FF00, + 0xFFFF0000FFFF0000, + 0xFFFFFFFF00000000 + }; + p->nTtVars = Gia_ManPiNum( p ); + p->nTtWords = (p->nTtVars <= 6 ? 1 : (1 << (p->nTtVars - 6))); + p->vTtMemory = Vec_WrdStart( p->nTtWords * 256 ); + for ( i = 0; i < 7; i++ ) + for ( k = 0; k < p->nTtWords; k++ ) + Vec_WrdWriteEntry( p->vTtMemory, i * p->nTtWords + k, Truth6[i] ); + } + else + { + // make sure the number of primary inputs did not change + // since the truth table computation storage was prepared + assert( p->nTtVars == Gia_ManPiNum(p) ); + } + // mark const and PIs + Gia_ManIncrementTravId( p ); + Gia_ObjSetTravIdCurrent( p, Gia_ManConst0(p) ); + Gia_ManConst0(p)->Value = 0; + Gia_ManForEachPi( p, pTemp, i ) + { + Gia_ObjSetTravIdCurrent( p, pTemp ); + pTemp->Value = i+1; + } + p->iTtNum = 7; + // compute truth table for the fanin node + pTruth = Vec_WrdArray(p->vTtMemory) + p->nTtWords * Gia_ManComputePoTt_rec(p, Gia_ObjFanin0(pObj)); + // complement if needed + if ( Gia_ObjFaninC0(pObj) ) + { + word * pTemp = pTruth; + assert( p->nTtWords * p->iTtNum < Vec_WrdSize(p->vTtMemory) ); + pTruth = Vec_WrdArray(p->vTtMemory) + p->nTtWords * p->iTtNum; + for ( k = 0; k < p->nTtWords; k++ ) + pTruth[k] = ~pTemp[k]; + } + return (unsigned *)pTruth; +} + +/**Function************************************************************* + + Synopsis [Testing truth table computation.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Gia_ManComputePoTtTest( Gia_Man_t * p ) +{ + Gia_Obj_t * pObj; + unsigned * pTruth; + clock_t clk = clock(); + int i; + Gia_ManForEachPo( p, pObj, i ) + { + pTruth = Gia_ManComputePoTt( p, pObj ); +// Extra_PrintHex( stdout, pTruth, Gia_ManPiNum(p) ); printf( "\n" ); + } + Abc_PrintTime( 1, "Time", clock() - clk ); +} + + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c index 5e74a943..590e5875 100644 --- a/src/base/abci/abc.c +++ b/src/base/abci/abc.c @@ -28944,8 +28944,7 @@ int Abc_CommandAbc9Test( Abc_Frame_t * pAbc, int argc, char ** argv ) // Gia_ManStopP( &pTemp ); // Gia_ManSuppSizeTest( pAbc->pGia ); // Gia_VtaTest( pAbc->pGia, 10, 100000, 0, 0, 1 ); - - Gia_IsoTest( pAbc->pGia, fVerbose ); +// Gia_IsoTest( pAbc->pGia, fVerbose ); return 0; usage: Abc_Print( -2, "usage: &test [-svh]\n" ); -- cgit v1.2.3