diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2006-06-11 08:01:00 -0700 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2006-06-11 08:01:00 -0700 |
commit | 3db1557f45b03875a0a0b8adddcc15c4565895d2 (patch) | |
tree | 2896d20ddcb85ae4aa7245ca28bc585f567fea54 /src/temp/ivy/ivyMulti.c | |
parent | 7d0921330b1f4e789901b4c2450920e7c412f95f (diff) | |
download | abc-3db1557f45b03875a0a0b8adddcc15c4565895d2.tar.gz abc-3db1557f45b03875a0a0b8adddcc15c4565895d2.tar.bz2 abc-3db1557f45b03875a0a0b8adddcc15c4565895d2.zip |
Version abc60611
Diffstat (limited to 'src/temp/ivy/ivyMulti.c')
-rw-r--r-- | src/temp/ivy/ivyMulti.c | 427 |
1 files changed, 427 insertions, 0 deletions
diff --git a/src/temp/ivy/ivyMulti.c b/src/temp/ivy/ivyMulti.c new file mode 100644 index 00000000..059d1500 --- /dev/null +++ b/src/temp/ivy/ivyMulti.c @@ -0,0 +1,427 @@ +/**CFile**************************************************************** + + FileName [ivyMulti.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [And-Inverter Graph package.] + + Synopsis [Constructing multi-input AND/EXOR gates.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - May 11, 2006.] + + Revision [$Id: ivyMulti.c,v 1.00 2006/05/11 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "ivy.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +typedef struct Ivy_Eval_t_ Ivy_Eval_t; +struct Ivy_Eval_t_ +{ + unsigned Mask : 5; // the mask of covered nodes + unsigned Weight : 3; // the number of covered nodes + unsigned Cost : 4; // the number of overlapping nodes + unsigned Level : 12; // the level of this node + unsigned Fan0 : 4; // the first fanin + unsigned Fan1 : 4; // the second fanin +}; + +static Ivy_Obj_t * Ivy_MultiBuild_rec( Ivy_Eval_t * pEvals, int iNum, Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type ); +static void Ivy_MultiSort( Ivy_Obj_t ** pArgs, int nArgs ); +static int Ivy_MultiPushUniqueOrderByLevel( Ivy_Obj_t ** pArray, int nArgs, Ivy_Obj_t * pNode ); +static Ivy_Obj_t * Ivy_MultiEval( Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type ); + + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Constructs the well-balanced tree of gates.] + + Description [Disregards levels and possible logic sharing.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Ivy_Obj_t * Ivy_Multi_rec( Ivy_Obj_t ** ppObjs, int nObjs, Ivy_Type_t Type ) +{ + Ivy_Obj_t * pObj1, * pObj2; + if ( nObjs == 1 ) + return ppObjs[0]; + pObj1 = Ivy_Multi_rec( ppObjs, nObjs/2, Type ); + pObj2 = Ivy_Multi_rec( ppObjs + nObjs/2, nObjs - nObjs/2, Type ); + return Ivy_Oper( pObj1, pObj2, Type ); +} + +/**Function************************************************************* + + Synopsis [Constructs a balanced tree while taking sharing into account.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Ivy_Obj_t * Ivy_Multi( Ivy_Obj_t ** pArgsInit, int nArgs, Ivy_Type_t Type ) +{ + static char NumBits[32] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5}; + static Ivy_Eval_t pEvals[15+15*14/2]; + static Ivy_Obj_t * pArgs[16]; + Ivy_Eval_t * pEva, * pEvaBest; + int nArgsNew, nEvals, i, k; + Ivy_Obj_t * pTemp; + + // consider the case of one argument + assert( nArgs > 0 ); + if ( nArgs == 1 ) + return pArgsInit[0]; + // consider the case of two arguments + if ( nArgs == 2 ) + return Ivy_Oper( pArgsInit[0], pArgsInit[1], Type ); + +//Ivy_MultiEval( pArgsInit, nArgs, Type ); printf( "\n" ); + + // set the initial ones + for ( i = 0; i < nArgs; i++ ) + { + pArgs[i] = pArgsInit[i]; + pEva = pEvals + i; + pEva->Mask = (1 << i); + pEva->Weight = 1; + pEva->Cost = 0; + pEva->Level = Ivy_Regular(pArgs[i])->Level; + pEva->Fan0 = 0; + pEva->Fan1 = 0; + } + + // find the available nodes + pEvaBest = pEvals; + nArgsNew = nArgs; + for ( i = 1; i < nArgsNew; i++ ) + for ( k = 0; k < i; k++ ) + if ( pTemp = Ivy_TableLookup(Ivy_ObjCreateGhost(pArgs[k], pArgs[i], Type, IVY_INIT_NONE)) ) + { + pEva = pEvals + nArgsNew; + pEva->Mask = pEvals[k].Mask | pEvals[i].Mask; + pEva->Weight = NumBits[pEva->Mask]; + pEva->Cost = pEvals[k].Cost + pEvals[i].Cost + NumBits[pEvals[k].Mask & pEvals[i].Mask]; + pEva->Level = 1 + IVY_MAX(pEvals[k].Level, pEvals[i].Level); + pEva->Fan0 = k; + pEva->Fan1 = i; +// assert( pEva->Level == (unsigned)Ivy_ObjLevel(pTemp) ); + // compare + if ( pEvaBest->Weight < pEva->Weight || + pEvaBest->Weight == pEva->Weight && pEvaBest->Cost > pEva->Cost || + pEvaBest->Weight == pEva->Weight && pEvaBest->Cost == pEva->Cost && pEvaBest->Level > pEva->Level ) + pEvaBest = pEva; + // save the argument + pArgs[nArgsNew++] = pTemp; + if ( nArgsNew == 15 ) + goto Outside; + } +Outside: + +// printf( "Best = %d.\n", pEvaBest - pEvals ); + + // the case of no common nodes + if ( nArgsNew == nArgs ) + { + Ivy_MultiSort( pArgs, nArgs ); + return Ivy_MultiBalance_rec( pArgs, nArgs, Type ); + } + // the case of one common node + if ( nArgsNew == nArgs + 1 ) + { + assert( pEvaBest - pEvals == nArgs ); + k = 0; + for ( i = 0; i < nArgs; i++ ) + if ( i != (int)pEvaBest->Fan0 && i != (int)pEvaBest->Fan1 ) + pArgs[k++] = pArgs[i]; + pArgs[k++] = pArgs[nArgs]; + assert( k == nArgs - 1 ); + nArgs = k; + Ivy_MultiSort( pArgs, nArgs ); + return Ivy_MultiBalance_rec( pArgs, nArgs, Type ); + } + // the case when there is a node that covers everything + if ( (int)pEvaBest->Mask == ((1 << nArgs) - 1) ) + return Ivy_MultiBuild_rec( pEvals, pEvaBest - pEvals, pArgs, nArgsNew, Type ); + + // evaluate node pairs + nEvals = nArgsNew; + for ( i = 1; i < nArgsNew; i++ ) + for ( k = 0; k < i; k++ ) + { + pEva = pEvals + nEvals; + pEva->Mask = pEvals[k].Mask | pEvals[i].Mask; + pEva->Weight = NumBits[pEva->Mask]; + pEva->Cost = pEvals[k].Cost + pEvals[i].Cost + NumBits[pEvals[k].Mask & pEvals[i].Mask]; + pEva->Level = 1 + IVY_MAX(pEvals[k].Level, pEvals[i].Level); + pEva->Fan0 = k; + pEva->Fan1 = i; + // compare + if ( pEvaBest->Weight < pEva->Weight || + pEvaBest->Weight == pEva->Weight && pEvaBest->Cost > pEva->Cost || + pEvaBest->Weight == pEva->Weight && pEvaBest->Cost == pEva->Cost && pEvaBest->Level > pEva->Level ) + pEvaBest = pEva; + // save the argument + nEvals++; + } + assert( pEvaBest - pEvals >= nArgsNew ); + +// printf( "Used (%d, %d).\n", pEvaBest->Fan0, pEvaBest->Fan1 ); + + // get the best implementation + pTemp = Ivy_MultiBuild_rec( pEvals, pEvaBest - pEvals, pArgs, nArgsNew, Type ); + + // collect those not covered by EvaBest + k = 0; + for ( i = 0; i < nArgs; i++ ) + if ( (pEvaBest->Mask & (1 << i)) == 0 ) + pArgs[k++] = pArgs[i]; + pArgs[k++] = pTemp; + assert( k == nArgs - (int)pEvaBest->Weight + 1 ); + nArgs = k; + Ivy_MultiSort( pArgs, nArgs ); + return Ivy_MultiBalance_rec( pArgs, nArgs, Type ); +} + +/**Function************************************************************* + + Synopsis [Implements multi-input AND/EXOR operation.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Ivy_Obj_t * Ivy_MultiBuild_rec( Ivy_Eval_t * pEvals, int iNum, Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type ) +{ + Ivy_Obj_t * pNode0, * pNode1; + if ( iNum < nArgs ) + return pArgs[iNum]; + pNode0 = Ivy_MultiBuild_rec( pEvals, pEvals[iNum].Fan0, pArgs, nArgs, Type ); + pNode1 = Ivy_MultiBuild_rec( pEvals, pEvals[iNum].Fan1, pArgs, nArgs, Type ); + return Ivy_Oper( pNode0, pNode1, Type ); +} + +/**Function************************************************************* + + Synopsis [Selection-sorts the nodes in the decreasing over of level.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Ivy_MultiSort( Ivy_Obj_t ** pArgs, int nArgs ) +{ + Ivy_Obj_t * pTemp; + int i, j, iBest; + + for ( i = 0; i < nArgs-1; i++ ) + { + iBest = i; + for ( j = i+1; j < nArgs; j++ ) + if ( Ivy_Regular(pArgs[j])->Level > Ivy_Regular(pArgs[iBest])->Level ) + iBest = j; + pTemp = pArgs[i]; + pArgs[i] = pArgs[iBest]; + pArgs[iBest] = pTemp; + } +} + +/**Function************************************************************* + + Synopsis [Inserts a new node in the order by levels.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Ivy_MultiPushUniqueOrderByLevel( Ivy_Obj_t ** pArray, int nArgs, Ivy_Obj_t * pNode ) +{ + Ivy_Obj_t * pNode1, * pNode2; + int i; + // try to find the node in the array + for ( i = 0; i < nArgs; i++ ) + if ( pArray[i] == pNode ) + return nArgs; + // put the node last + pArray[nArgs++] = pNode; + // find the place to put the new node + for ( i = nArgs-1; i > 0; i-- ) + { + pNode1 = pArray[i ]; + pNode2 = pArray[i-1]; + if ( Ivy_Regular(pNode1)->Level <= Ivy_Regular(pNode2)->Level ) + break; + pArray[i ] = pNode2; + pArray[i-1] = pNode1; + } + return nArgs; +} + +/**Function************************************************************* + + Synopsis [Balances the array recursively.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Ivy_Obj_t * Ivy_MultiBalance_rec( Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type ) +{ + Ivy_Obj_t * pNodeNew; + // consider the case of one argument + assert( nArgs > 0 ); + if ( nArgs == 1 ) + return pArgs[0]; + // consider the case of two arguments + if ( nArgs == 2 ) + return Ivy_Oper( pArgs[0], pArgs[1], Type ); + // get the last two nodes + pNodeNew = Ivy_Oper( pArgs[nArgs-1], pArgs[nArgs-2], Type ); + // add the new node + nArgs = Ivy_MultiPushUniqueOrderByLevel( pArgs, nArgs - 2, pNodeNew ); + return Ivy_MultiBalance_rec( pArgs, nArgs, Type ); +} + +/**Function************************************************************* + + Synopsis [Implements multi-input AND/EXOR operation.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Ivy_Obj_t * Ivy_MultiEval( Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type ) +{ + Ivy_Obj_t * pTemp; + int i, k; + int nArgsOld = nArgs; + for ( i = 0; i < nArgs; i++ ) + printf( "%d[%d] ", i, Ivy_Regular(pArgs[i])->Level ); + for ( i = 1; i < nArgs; i++ ) + for ( k = 0; k < i; k++ ) + { + pTemp = Ivy_TableLookup(Ivy_ObjCreateGhost(pArgs[k], pArgs[i], Type, IVY_INIT_NONE)); + if ( pTemp != NULL ) + { + printf( "%d[%d]=(%d,%d) ", nArgs, Ivy_Regular(pTemp)->Level, k, i ); + pArgs[nArgs++] = pTemp; + } + } + printf( " ((%d/%d)) ", nArgsOld, nArgs-nArgsOld ); + return NULL; +} + + + +/**Function************************************************************* + + Synopsis [Old code.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Ivy_Obj_t * Ivy_Multi1( Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type ) +{ + Ivy_Obj_t * pArgsRef[5], * pTemp; + int i, k, m, nArgsNew, Counter = 0; + + +//Ivy_MultiEval( pArgs, nArgs, Type ); printf( "\n" ); + + + assert( Type == IVY_AND || Type == IVY_EXOR ); + assert( nArgs > 0 ); + if ( nArgs == 1 ) + return pArgs[0]; + + // find the nodes with more than one fanout + nArgsNew = 0; + for ( i = 0; i < nArgs; i++ ) + if ( Ivy_ObjRefs( Ivy_Regular(pArgs[i]) ) > 0 ) + pArgsRef[nArgsNew++] = pArgs[i]; + + // go through pairs + if ( nArgsNew >= 2 ) + for ( i = 0; i < nArgsNew; i++ ) + for ( k = i + 1; k < nArgsNew; k++ ) + if ( pTemp = Ivy_TableLookup(Ivy_ObjCreateGhost(pArgsRef[i], pArgsRef[k], Type, IVY_INIT_NONE)) ) + Counter++; +// printf( "%d", Counter ); + + // go through pairs + if ( nArgsNew >= 2 ) + for ( i = 0; i < nArgsNew; i++ ) + for ( k = i + 1; k < nArgsNew; k++ ) + if ( pTemp = Ivy_TableLookup(Ivy_ObjCreateGhost(pArgsRef[i], pArgsRef[k], Type, IVY_INIT_NONE)) ) + { + nArgsNew = 0; + for ( m = 0; m < nArgs; m++ ) + if ( pArgs[m] != pArgsRef[i] && pArgs[m] != pArgsRef[k] ) + pArgs[nArgsNew++] = pArgs[m]; + pArgs[nArgsNew++] = pTemp; + assert( nArgsNew == nArgs - 1 ); + return Ivy_Multi1( pArgs, nArgsNew, Type ); + } + return Ivy_Multi_rec( pArgs, nArgs, Type ); +} + +/**Function************************************************************* + + Synopsis [Old code.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Ivy_Obj_t * Ivy_Multi2( Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type ) +{ + assert( Type == IVY_AND || Type == IVY_EXOR ); + assert( nArgs > 0 ); + return Ivy_Multi_rec( pArgs, nArgs, Type ); +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + |