diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2015-09-30 20:21:40 -0700 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2015-09-30 20:21:40 -0700 |
commit | 0e0f2e64af4a101f8a60d236f29b95dd7cfd1fbf (patch) | |
tree | 2ddc566f4d593cc058dde05238de870cd568434b /src/aig/gia | |
parent | 10c31c6576cfee6d070e255b8878e23574529737 (diff) | |
download | abc-0e0f2e64af4a101f8a60d236f29b95dd7cfd1fbf.tar.gz abc-0e0f2e64af4a101f8a60d236f29b95dd7cfd1fbf.tar.bz2 abc-0e0f2e64af4a101f8a60d236f29b95dd7cfd1fbf.zip |
Naive LUT packing algorithm (command &pack).
Diffstat (limited to 'src/aig/gia')
-rw-r--r-- | src/aig/gia/giaPack.c | 207 | ||||
-rw-r--r-- | src/aig/gia/module.make | 1 |
2 files changed, 208 insertions, 0 deletions
diff --git a/src/aig/gia/giaPack.c b/src/aig/gia/giaPack.c new file mode 100644 index 00000000..0cbf96d8 --- /dev/null +++ b/src/aig/gia/giaPack.c @@ -0,0 +1,207 @@ +/**CFile**************************************************************** + + FileName [giaPack.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Scalable AIG package.] + + Synopsis [LUT packing.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: giaPack.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "gia.h" + +ABC_NAMESPACE_IMPL_START + + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Collects LUT nodes in the increasing order of distance from COs.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Int_t * Gia_ManLutCollect2( Gia_Man_t * p ) +{ + Gia_Obj_t * pObj; + Vec_Int_t * vOrder; + int i, k, Id, iFan; + vOrder = Vec_IntAlloc( Gia_ManLutNum(p) ); + Gia_ManIncrementTravId( p ); + Gia_ManForEachCoDriver( p, pObj, i ) + { + if ( !Gia_ObjIsAnd(pObj) ) + continue; + Id = Gia_ObjId( p, pObj ); + assert( Gia_ObjIsLut(p, Id) ); + if ( Gia_ObjIsTravIdCurrentId(p, Id) ) + continue; + Gia_ObjSetTravIdCurrentId(p, Id); + Vec_IntPush( vOrder, Id ); + } + Vec_IntForEachEntry( vOrder, Id, i ) + { + Gia_LutForEachFanin( p, Id, iFan, k ) + { + if ( !Gia_ObjIsAnd(Gia_ManObj(p, iFan)) ) + continue; + assert( Gia_ObjIsLut(p, iFan) ); + if ( Gia_ObjIsTravIdCurrentId(p, iFan) ) + continue; + Gia_ObjSetTravIdCurrentId(p, iFan); + Vec_IntPush( vOrder, iFan ); + } + } + assert( Vec_IntCap(vOrder) == 16 || Vec_IntSize(vOrder) == Vec_IntCap(vOrder) ); + Vec_IntReverseOrder( vOrder ); + return vOrder; +} +Vec_Int_t * Gia_ManLutCollect( Gia_Man_t * p ) +{ + Vec_Int_t * vLuts, * vDist, * vOrder; + int i, k, Id, iFan, * pPerm; + // collect LUTs + vLuts = Vec_IntAlloc( Gia_ManAndNum(p) ); + Gia_ManForEachLut( p, Id ) + Vec_IntPush( vLuts, Id ); + // propagate distance + vDist = Vec_IntStart( Gia_ManObjNum(p) ); + Gia_ManForEachCoDriverId( p, Id, i ) + Vec_IntWriteEntry( vDist, Id, 1 ); + Vec_IntForEachEntryReverse( vLuts, Id, i ) + { + int Dist = 1 + Vec_IntEntry(vDist, Id); + Gia_LutForEachFanin( p, Id, iFan, k ) + Vec_IntUpdateEntry( vDist, iFan, Dist ); + } + // sort LUTs by distance + k = 0; + Vec_IntForEachEntry( vLuts, Id, i ) + Vec_IntWriteEntry( vDist, k++, -Vec_IntEntry(vDist, Id) ); + Vec_IntShrink( vDist, k ); + pPerm = Abc_MergeSortCost( Vec_IntArray(vDist), Vec_IntSize(vDist) ); + // collect + vOrder = Vec_IntAlloc( Vec_IntSize(vLuts) ); + for ( i = 0; i < Vec_IntSize(vLuts); i++ ) + Vec_IntPush( vOrder, Vec_IntEntry(vLuts, pPerm[i]) ); + Vec_IntFree( vDist ); + Vec_IntFree( vLuts ); + ABC_FREE( pPerm ); + return vOrder; +} + +/**Function************************************************************* + + Synopsis [LUT packing algorithm.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Gia_ManLutPacking( Gia_Man_t * p, int nBlockSize, int DelayRoute, int DelayDir, int fVerbose ) +{ + int Delays[32], Perm[32]; + Vec_Int_t * vPacking, * vStarts; + Vec_Int_t * vOrder = Gia_ManLutCollect( p ); + Vec_Int_t * vDelay = Vec_IntStart( Gia_ManObjNum(p) ); + Vec_Int_t * vBlock = Vec_IntStart( Gia_ManObjNum(p) ); + Vec_Int_t * vBSize = Vec_IntAlloc( 2 * Vec_IntSize(vOrder) / nBlockSize ); + int i, k, Id, iFan, nSize, iBlock, Delay, DelayMax = 0; + // create blocks + Vec_IntForEachEntry( vOrder, Id, i ) + { + nSize = Gia_ObjLutSize( p, Id ); + assert( nSize <= 32 ); + Gia_LutForEachFanin( p, Id, iFan, k ) + { + Delays[k] = Vec_IntEntry(vDelay, iFan); + Perm[k] = iFan; + } + Vec_IntSelectSortCost2Reverse( Perm, nSize, Delays ); + assert( nSize < 2 || Delays[0] >= Delays[nSize-1] ); + assert( Delays[0] >= 0 && Delays[nSize-1] >= 0 ); + // check if we can reduce delay by adding it to the same bin as the latest one + iBlock = Vec_IntEntry( vBlock, Perm[0] ); + if ( Delays[0] > 0 && Delays[0] > Delays[1] && Vec_IntEntry(vBSize, iBlock) < nBlockSize ) + { + Delay = Delays[0] + DelayDir; + Vec_IntWriteEntry( vBlock, Id, iBlock ); + Vec_IntAddToEntry( vBSize, iBlock, 1 ); + } + else // clean new block + { + Delay = Delays[0] + DelayRoute; + Vec_IntWriteEntry( vBlock, Id, Vec_IntSize(vBSize) ); + Vec_IntPush( vBSize, 1 ); + } + // calculate delay + for ( k = 1; k < nSize; k++ ) + Delay = Abc_MaxInt( Delay, Delays[k] + DelayRoute ); + Vec_IntWriteEntry( vDelay, Id, Delay ); + DelayMax = Abc_MaxInt( DelayMax, Delay ); + } + assert( Vec_IntSum(vBSize) == Vec_IntSize(vOrder) ); + // create packing info + vPacking = Vec_IntAlloc( Vec_IntSize(vBSize) + Vec_IntSize(vOrder) + 1 ); + Vec_IntPush( vPacking, Vec_IntSize(vBSize) ); + // create starting places for each block + vStarts = Vec_IntAlloc( Vec_IntSize(vBSize) ); + Vec_IntForEachEntry( vBSize, nSize, i ) + { + Vec_IntPush( vPacking, nSize ); + Vec_IntPush( vStarts, Vec_IntSize(vPacking) ); + Vec_IntFillExtra( vPacking, Vec_IntSize(vPacking) + nSize, -1 ); + } + assert( Vec_IntCap(vPacking) == 16 || Vec_IntSize(vPacking) == Vec_IntCap(vPacking) ); + // collect LUTs from the block + Vec_IntForEachEntryReverse( vOrder, Id, i ) + { + int Block = Vec_IntEntry( vBlock, Id ); + int Start = Vec_IntEntry( vStarts, Block ); + assert( Vec_IntEntry(vPacking, Start) == -1 ); + Vec_IntWriteEntry( vPacking, Start, Id ); + Vec_IntAddToEntry( vStarts, Block, 1 ); + } + assert( Vec_IntCountEntry(vPacking, -1) == 0 ); + // cleanup + Vec_IntFree( vOrder ); + Vec_IntFree( vDelay ); + Vec_IntFree( vBlock ); + Vec_IntFree( vBSize ); + Vec_IntFree( vStarts ); + Vec_IntFreeP( &p->vPacking ); + p->vPacking = vPacking; + printf( "Global delay = %d.\n", DelayMax ); +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + +ABC_NAMESPACE_IMPL_END + diff --git a/src/aig/gia/module.make b/src/aig/gia/module.make index 07038a09..32359c67 100644 --- a/src/aig/gia/module.make +++ b/src/aig/gia/module.make @@ -47,6 +47,7 @@ SRC += src/aig/gia/giaAig.c \ src/aig/gia/giaMuxes.c \ src/aig/gia/giaNf.c \ src/aig/gia/giaOf.c \ + src/aig/gia/giaPack.c \ src/aig/gia/giaPat.c \ src/aig/gia/giaPf.c \ src/aig/gia/giaQbf.c \ |