abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Functions
lpkAbcMux.c File Reference
#include "lpkInt.h"

Go to the source code of this file.

Functions

ABC_NAMESPACE_IMPL_START
Lpk_Res_t * 		Lpk_MuxAnalize (Lpk_Man_t *pMan, Lpk_Fun_t *p)
 DECLARATIONS ///. More...
 
Lpk_Fun_t * Lpk_MuxSplit (Lpk_Man_t *pMan, Lpk_Fun_t *p, int Var, int Pol)
 

Function Documentation

ABC_NAMESPACE_IMPL_START Lpk_Res_t* Lpk_MuxAnalize ( Lpk_Man_t *  pMan,
Lpk_Fun_t *  p 
)

DECLARATIONS ///.

CFile****************************************************************

FileName [lpkAbcMux.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Fast Boolean matching for LUT structures.]

Synopsis [LUT-decomposition based on recursive MUX decomposition.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - April 28, 2007.]

Revision [

Id:
lpkAbcMux.c,v 1.00 2007/04/28 00:00:00 alanmi Exp

]FUNCTION DEFINITIONS /// Function*************************************************************

Synopsis [Checks the possibility of MUX decomposition.]

Description [Returns the best variable to use for MUX decomposition.]

SideEffects []

SeeAlso []

Definition at line 45 of file lpkAbcMux.c.

46 {
47  static Lpk_Res_t Res, * pRes = &Res;
48  int nSuppSize0, nSuppSize1, nSuppSizeS, nSuppSizeL;
49  int Var, Area, Polarity, Delay, Delay0, Delay1, DelayA, DelayB;
50  memset( pRes, 0, sizeof(Lpk_Res_t) );
51  assert( p->uSupp == Kit_BitMask(p->nVars) );
52  assert( p->fSupports );
53  // derive the delay and area after MUX-decomp with each var - and find the best var
54  pRes->Variable = -1;
55  Lpk_SuppForEachVar( p->uSupp, Var )
56  {
57  nSuppSize0 = Kit_WordCountOnes(p->puSupps[2*Var+0]);
58  nSuppSize1 = Kit_WordCountOnes(p->puSupps[2*Var+1]);
59  assert( nSuppSize0 < (int)p->nVars );
60  assert( nSuppSize1 < (int)p->nVars );
61  if ( nSuppSize0 < 1 || nSuppSize1 < 1 )
62  continue;
63 //printf( "%d %d ", nSuppSize0, nSuppSize1 );
64  if ( nSuppSize0 <= (int)p->nLutK - 2 && nSuppSize1 <= (int)p->nLutK - 2 )
65  {
66  // include cof var into 0-block
67  DelayA = Lpk_SuppDelay( p->puSupps[2*Var+0] | (1<<Var), p->pDelays );
68  DelayB = Lpk_SuppDelay( p->puSupps[2*Var+1] , p->pDelays );
69  Delay0 = Abc_MaxInt( DelayA, DelayB + 1 );
70  // include cof var into 1-block
71  DelayA = Lpk_SuppDelay( p->puSupps[2*Var+1] | (1<<Var), p->pDelays );
72  DelayB = Lpk_SuppDelay( p->puSupps[2*Var+0] , p->pDelays );
73  Delay1 = Abc_MaxInt( DelayA, DelayB + 1 );
74  // get the best delay
75  Delay = Abc_MinInt( Delay0, Delay1 );
76  Area = 2;
77  Polarity = (int)(Delay == Delay1);
78  }
79  else if ( nSuppSize0 <= (int)p->nLutK - 2 )
80  {
81  DelayA = Lpk_SuppDelay( p->puSupps[2*Var+0] | (1<<Var), p->pDelays );
82  DelayB = Lpk_SuppDelay( p->puSupps[2*Var+1] , p->pDelays );
83  Delay = Abc_MaxInt( DelayA, DelayB + 1 );
84  Area = 1 + Lpk_LutNumLuts( nSuppSize1, p->nLutK );
85  Polarity = 0;
86  }
87  else if ( nSuppSize1 <= (int)p->nLutK - 2 )
88  {
89  DelayA = Lpk_SuppDelay( p->puSupps[2*Var+1] | (1<<Var), p->pDelays );
90  DelayB = Lpk_SuppDelay( p->puSupps[2*Var+0] , p->pDelays );
91  Delay = Abc_MaxInt( DelayA, DelayB + 1 );
92  Area = 1 + Lpk_LutNumLuts( nSuppSize0, p->nLutK );
93  Polarity = 1;
94  }
95  else if ( nSuppSize0 <= (int)p->nLutK )
96  {
97  DelayA = Lpk_SuppDelay( p->puSupps[2*Var+1] | (1<<Var), p->pDelays );
98  DelayB = Lpk_SuppDelay( p->puSupps[2*Var+0] , p->pDelays );
99  Delay = Abc_MaxInt( DelayA, DelayB + 1 );
100  Area = 1 + Lpk_LutNumLuts( nSuppSize1+2, p->nLutK );
101  Polarity = 1;
102  }
103  else if ( nSuppSize1 <= (int)p->nLutK )
104  {
105  DelayA = Lpk_SuppDelay( p->puSupps[2*Var+0] | (1<<Var), p->pDelays );
106  DelayB = Lpk_SuppDelay( p->puSupps[2*Var+1] , p->pDelays );
107  Delay = Abc_MaxInt( DelayA, DelayB + 1 );
108  Area = 1 + Lpk_LutNumLuts( nSuppSize0+2, p->nLutK );
109  Polarity = 0;
110  }
111  else
112  {
113  // include cof var into 0-block
114  DelayA = Lpk_SuppDelay( p->puSupps[2*Var+0] | (1<<Var), p->pDelays );
115  DelayB = Lpk_SuppDelay( p->puSupps[2*Var+1] , p->pDelays );
116  Delay0 = Abc_MaxInt( DelayA, DelayB + 1 );
117  // include cof var into 1-block
118  DelayA = Lpk_SuppDelay( p->puSupps[2*Var+1] | (1<<Var), p->pDelays );
119  DelayB = Lpk_SuppDelay( p->puSupps[2*Var+0] , p->pDelays );
120  Delay1 = Abc_MaxInt( DelayA, DelayB + 1 );
121  // get the best delay
122  Delay = Abc_MinInt( Delay0, Delay1 );
123  if ( Delay == Delay0 )
124  Area = Lpk_LutNumLuts( nSuppSize0+2, p->nLutK ) + Lpk_LutNumLuts( nSuppSize1, p->nLutK );
125  else
126  Area = Lpk_LutNumLuts( nSuppSize1+2, p->nLutK ) + Lpk_LutNumLuts( nSuppSize0, p->nLutK );
127  Polarity = (int)(Delay == Delay1);
128  }
129  // find the best variable
130  if ( Delay > (int)p->nDelayLim )
131  continue;
132  if ( Area > (int)p->nAreaLim )
133  continue;
134  nSuppSizeS = Abc_MinInt( nSuppSize0 + 2 *!Polarity, nSuppSize1 + 2 * Polarity );
135  nSuppSizeL = Abc_MaxInt( nSuppSize0 + 2 *!Polarity, nSuppSize1 + 2 * Polarity );
136  if ( nSuppSizeL > (int)p->nVars )
137  continue;
138  if ( pRes->Variable == -1 || pRes->AreaEst > Area ||
139  (pRes->AreaEst == Area && pRes->nSuppSizeS + pRes->nSuppSizeL > nSuppSizeS + nSuppSizeL) ||
140  (pRes->AreaEst == Area && pRes->nSuppSizeS + pRes->nSuppSizeL == nSuppSizeS + nSuppSizeL && pRes->DelayEst > Delay) )
141  {
142  pRes->Variable = Var;
143  pRes->Polarity = Polarity;
144  pRes->AreaEst = Area;
145  pRes->DelayEst = Delay;
146  pRes->nSuppSizeS = nSuppSizeS;
147  pRes->nSuppSizeL = nSuppSizeL;
148  }
149  }
150  return pRes->Variable == -1 ? NULL : pRes;
151 }
memset
char * memset()
Lpk_Fun_t_::nAreaLim
unsigned nAreaLim
Definition: lpkInt.h:150
Lpk_Fun_t_::nVars
unsigned nVars
Definition: lpkInt.h:148
Lpk_Res_t_::Variable
int Variable
Definition: lpkInt.h:173
Lpk_SuppDelay
int Lpk_SuppDelay(unsigned uSupp, char *pDelays)
Definition: lpkAbcUtil.c:215
Lpk_Fun_t_::nLutK
unsigned nLutK
Definition: lpkInt.h:149
Lpk_Res_t_::AreaEst
int AreaEst
Definition: lpkInt.h:172
Lpk_Fun_t_::uSupp
unsigned uSupp
Definition: lpkInt.h:154
Lpk_Fun_t_::fSupports
unsigned fSupports
Definition: lpkInt.h:152
Lpk_Res_t_
Definition: lpkInt.h:163
Abc_MaxInt
static int Abc_MaxInt(int a, int b)
Definition: abc_global.h:238
Abc_MinInt
static int Abc_MinInt(int a, int b)
Definition: abc_global.h:239
Lpk_Res_t_::DelayEst
int DelayEst
Definition: lpkInt.h:171
Lpk_Res_t_::nSuppSizeS
int nSuppSizeS
Definition: lpkInt.h:169
Lpk_Fun_t_::pDelays
char pDelays[16]
Definition: lpkInt.h:156
Lpk_Res_t_::Polarity
int Polarity
Definition: lpkInt.h:174
Minisat::Var
int Var
Definition: SolverTypes.h:42
Lpk_LutNumLuts
static int Lpk_LutNumLuts(int nVarsMax, int nLutK)
Definition: lpkInt.h:178
assert
#define assert(ex)
Definition: util_old.h:213
Kit_WordCountOnes
static int Kit_WordCountOnes(unsigned uWord)
Definition: kit.h:243
Lpk_SuppForEachVar
#define Lpk_SuppForEachVar(Supp, Var)
Definition: lpkInt.h:195
Lpk_Fun_t_::puSupps
unsigned puSupps[32]
Definition: lpkInt.h:155
Kit_BitMask
static unsigned Kit_BitMask(int nBits)
Definition: kit.h:225
Lpk_Res_t_::nSuppSizeL
int nSuppSizeL
Definition: lpkInt.h:170
Lpk_Fun_t_::nDelayLim
unsigned nDelayLim
Definition: lpkInt.h:151
Lpk_Fun_t* Lpk_MuxSplit ( Lpk_Man_t *  pMan,
Lpk_Fun_t *  p,
int  Var,
int  Pol 
)

Function*************************************************************

Synopsis [Transforms the function decomposed by the MUX decomposition.]

Description [Returns the best variable to use for MUX decomposition.]

SideEffects []

SeeAlso []

Definition at line 164 of file lpkAbcMux.c.

165 {
166  Lpk_Fun_t * pNew;
167  unsigned * pTruth = Lpk_FunTruth( p, 0 );
168  unsigned * pTruth0 = Lpk_FunTruth( p, 1 );
169  unsigned * pTruth1 = Lpk_FunTruth( p, 2 );
170 // unsigned uSupp;
171  int iVarVac;
172  assert( Var >= 0 && Var < (int)p->nVars );
173  assert( p->nAreaLim >= 2 );
174  assert( p->uSupp == Kit_BitMask(p->nVars) );
175  Kit_TruthCofactor0New( pTruth0, pTruth, p->nVars, Var );
176  Kit_TruthCofactor1New( pTruth1, pTruth, p->nVars, Var );
177 /*
178 uSupp = Kit_TruthSupport( pTruth, p->nVars );
179 Extra_PrintBinary( stdout, &uSupp, 16 ); printf( "\n" );
180 uSupp = Kit_TruthSupport( pTruth0, p->nVars );
181 Extra_PrintBinary( stdout, &uSupp, 16 ); printf( "\n" );
182 uSupp = Kit_TruthSupport( pTruth1, p->nVars );
183 Extra_PrintBinary( stdout, &uSupp, 16 ); printf( "\n\n" );
184 */
185  // derive the new component
186  pNew = Lpk_FunDup( p, Pol ? pTruth0 : pTruth1 );
187  // update the support of the old component
188  p->uSupp = Kit_TruthSupport( Pol ? pTruth1 : pTruth0, p->nVars );
189  p->uSupp |= (1 << Var);
190  // update the truth table of the old component
191  iVarVac = Kit_WordFindFirstBit( ~p->uSupp );
192  assert( iVarVac < (int)p->nVars );
193  p->uSupp |= (1 << iVarVac);
194  Kit_TruthIthVar( pTruth, p->nVars, iVarVac );
195  if ( Pol )
196  Kit_TruthMuxVar( pTruth, pTruth, pTruth1, p->nVars, Var );
197  else
198  Kit_TruthMuxVar( pTruth, pTruth0, pTruth, p->nVars, Var );
199  assert( p->uSupp == Kit_TruthSupport(pTruth, p->nVars) );
200  // set the decomposed variable
201  p->pFanins[iVarVac] = pNew->Id;
202  p->pDelays[iVarVac] = p->nDelayLim - 1;
203  // support minimize both
204  p->fSupports = 0;
205  Lpk_FunSuppMinimize( p );
206  Lpk_FunSuppMinimize( pNew );
207  // update delay and area requirements
208  pNew->nDelayLim = p->nDelayLim - 1;
209  if ( pNew->nVars <= pNew->nLutK )
210  {
211  pNew->nAreaLim = 1;
212  p->nAreaLim = p->nAreaLim - 1;
213  }
214  else if ( p->nVars <= p->nLutK )
215  {
216  pNew->nAreaLim = p->nAreaLim - 1;
217  p->nAreaLim = 1;
218  }
219  else if ( p->nVars < pNew->nVars )
220  {
221  pNew->nAreaLim = p->nAreaLim / 2 + p->nAreaLim % 2;
222  p->nAreaLim = p->nAreaLim / 2 - p->nAreaLim % 2;
223  }
224  else // if ( pNew->nVars < p->nVars )
225  {
226  pNew->nAreaLim = p->nAreaLim / 2 - p->nAreaLim % 2;
227  p->nAreaLim = p->nAreaLim / 2 + p->nAreaLim % 2;
228  }
229  pNew->fMark = 1;
230  return pNew;
231 }
Lpk_Fun_t_::nAreaLim
unsigned nAreaLim
Definition: lpkInt.h:150
Lpk_Fun_t_::nVars
unsigned nVars
Definition: lpkInt.h:148
Lpk_Fun_t_::nLutK
unsigned nLutK
Definition: lpkInt.h:149
Lpk_Fun_t_::uSupp
unsigned uSupp
Definition: lpkInt.h:154
Lpk_Fun_t_::fSupports
unsigned fSupports
Definition: lpkInt.h:152
Kit_TruthMuxVar
void Kit_TruthMuxVar(unsigned *pOut, unsigned *pCof0, unsigned *pCof1, int nVars, int iVar)
Definition: kitTruth.c:1069
Lpk_Fun_t_::Id
unsigned Id
Definition: lpkInt.h:147
Lpk_FunTruth
static unsigned * Lpk_FunTruth(Lpk_Fun_t *p, int Num)
Definition: lpkInt.h:179
Kit_TruthCofactor0New
void Kit_TruthCofactor0New(unsigned *pOut, unsigned *pIn, int nVars, int iVar)
Definition: kitTruth.c:521
Kit_TruthCofactor1New
void Kit_TruthCofactor1New(unsigned *pOut, unsigned *pIn, int nVars, int iVar)
Definition: kitTruth.c:573
Lpk_FunSuppMinimize
int Lpk_FunSuppMinimize(Lpk_Fun_t *p)
Definition: lpkAbcUtil.c:143
Lpk_Fun_t_::fMark
unsigned fMark
Definition: lpkInt.h:153
Kit_TruthIthVar
static void Kit_TruthIthVar(unsigned *pTruth, int nVars, int iVar)
Definition: kit.h:473
Lpk_Fun_t_
Definition: lpkInt.h:144
Kit_WordFindFirstBit
static int Kit_WordFindFirstBit(unsigned uWord)
Definition: kit.h:231
Lpk_Fun_t_::pDelays
char pDelays[16]
Definition: lpkInt.h:156
Lpk_FunDup
Lpk_Fun_t * Lpk_FunDup(Lpk_Fun_t *p, unsigned *pTruth)
Definition: lpkAbcUtil.c:114
Kit_TruthSupport
unsigned Kit_TruthSupport(unsigned *pTruth, int nVars)
Definition: kitTruth.c:346
Minisat::Var
int Var
Definition: SolverTypes.h:42
Lpk_Fun_t_::pFanins
char pFanins[16]
Definition: lpkInt.h:157
assert
#define assert(ex)
Definition: util_old.h:213
Kit_BitMask
static unsigned Kit_BitMask(int nBits)
Definition: kit.h:225
Lpk_Fun_t_::nDelayLim
unsigned nDelayLim
Definition: lpkInt.h:151