ABC: A System for Sequential Synthesis and Verification
 
Loading...
Searching...
No Matches
Functions
lpkAbcMux.c File Reference
#include "lpkInt.h"
Include dependency graph for lpkAbcMux.c:

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 ///.
 
Lpk_Fun_t * Lpk_MuxSplit (Lpk_Man_t *pMan, Lpk_Fun_t *p, int Var, int Pol)
 

Function Documentation

◆ Lpk_MuxAnalize()

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}
p
Cube * p
Definition exorList.c:222
Var
int Var
Definition exorList.c:228
Lpk_SuppDelay
int Lpk_SuppDelay(unsigned uSupp, int *pDelays)
Definition lpkAbcUtil.c:215
Lpk_SuppForEachVar
#define Lpk_SuppForEachVar(Supp, Var)
Definition lpkInt.h:196
Lpk_Res_t
struct Lpk_Res_t_ Lpk_Res_t
Definition lpkInt.h:163
Lpk_Res_t_::nSuppSizeS
int nSuppSizeS
Definition lpkInt.h:170
Lpk_Res_t_::Variable
int Variable
Definition lpkInt.h:174
Lpk_Res_t_::Polarity
int Polarity
Definition lpkInt.h:175
Lpk_Res_t_::DelayEst
int DelayEst
Definition lpkInt.h:172
Lpk_Res_t_::AreaEst
int AreaEst
Definition lpkInt.h:173
Lpk_Res_t_::nSuppSizeL
int nSuppSizeL
Definition lpkInt.h:171
assert
#define assert(ex)
Definition util_old.h:213
memset
char * memset()
Here is the call graph for this function:
Here is the caller graph for this function:

◆ Lpk_MuxSplit()

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/*
178uSupp = Kit_TruthSupport( pTruth, p->nVars );
179Extra_PrintBinary( stdout, &uSupp, 16 ); printf( "\n" );
180uSupp = Kit_TruthSupport( pTruth0, p->nVars );
181Extra_PrintBinary( stdout, &uSupp, 16 ); printf( "\n" );
182uSupp = Kit_TruthSupport( pTruth1, p->nVars );
183Extra_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}
Kit_TruthSupport
unsigned Kit_TruthSupport(unsigned *pTruth, int nVars)
Definition kitTruth.c:346
Kit_TruthMuxVar
void Kit_TruthMuxVar(unsigned *pOut, unsigned *pCof0, unsigned *pCof1, int nVars, int iVar)
Definition kitTruth.c:1069
Kit_TruthCofactor1New
void Kit_TruthCofactor1New(unsigned *pOut, unsigned *pIn, int nVars, int iVar)
Definition kitTruth.c:573
Kit_TruthCofactor0New
void Kit_TruthCofactor0New(unsigned *pOut, unsigned *pIn, int nVars, int iVar)
Definition kitTruth.c:521
Lpk_FunDup
Lpk_Fun_t * Lpk_FunDup(Lpk_Fun_t *p, unsigned *pTruth)
Definition lpkAbcUtil.c:114
Lpk_FunSuppMinimize
int Lpk_FunSuppMinimize(Lpk_Fun_t *p)
Definition lpkAbcUtil.c:143
Lpk_Fun_t
struct Lpk_Fun_t_ Lpk_Fun_t
Definition lpkInt.h:144
Lpk_Fun_t_::nAreaLim
unsigned nAreaLim
Definition lpkInt.h:151
Lpk_Fun_t_::nLutK
unsigned nLutK
Definition lpkInt.h:150
Lpk_Fun_t_::nDelayLim
unsigned nDelayLim
Definition lpkInt.h:156
Lpk_Fun_t_::nVars
unsigned nVars
Definition lpkInt.h:149
Lpk_Fun_t_::Id
unsigned Id
Definition lpkInt.h:148
Lpk_Fun_t_::fMark
unsigned fMark
Definition lpkInt.h:153
Here is the call graph for this function:
Here is the caller graph for this function: