src/opt/lpk/lpkAbcMux.c File Reference

#include "lpkInt.h"
Include dependency graph for lpkAbcMux.c:

Go to the source code of this file.

Functions

Lpk_Res_t * Lpk_MuxAnalize (Lpk_Man_t *pMan, Lpk_Fun_t *p)
Lpk_Fun_t * Lpk_MuxSplit (Lpk_Man_t *pMan, Lpk_Fun_t *p, int Var, int Pol)

Function Documentation

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

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

] DECLARATIONS /// 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 42 of file lpkAbcMux.c.

00043 {
00044     static Lpk_Res_t Res, * pRes = &Res;
00045     int nSuppSize0, nSuppSize1, nSuppSizeS, nSuppSizeL;
00046     int Var, Area, Polarity, Delay, Delay0, Delay1, DelayA, DelayB;
00047     memset( pRes, 0, sizeof(Lpk_Res_t) );
00048     assert( p->uSupp == Kit_BitMask(p->nVars) );
00049     assert( p->fSupports );
00050     // derive the delay and area after MUX-decomp with each var - and find the best var
00051     pRes->Variable = -1;
00052     Lpk_SuppForEachVar( p->uSupp, Var )
00053     {
00054         nSuppSize0 = Kit_WordCountOnes(p->puSupps[2*Var+0]);
00055         nSuppSize1 = Kit_WordCountOnes(p->puSupps[2*Var+1]);
00056         assert( nSuppSize0 < (int)p->nVars );
00057         assert( nSuppSize1 < (int)p->nVars );
00058         if ( nSuppSize0 < 1 || nSuppSize1 < 1 )
00059             continue;
00060 //printf( "%d %d    ", nSuppSize0, nSuppSize1 );
00061         if ( nSuppSize0 <= (int)p->nLutK - 2 && nSuppSize1 <= (int)p->nLutK - 2 )
00062         {
00063             // include cof var into 0-block
00064             DelayA = Lpk_SuppDelay( p->puSupps[2*Var+0] | (1<<Var), p->pDelays );
00065             DelayB = Lpk_SuppDelay( p->puSupps[2*Var+1]           , p->pDelays );
00066             Delay0 = ABC_MAX( DelayA, DelayB + 1 );
00067             // include cof var into 1-block
00068             DelayA = Lpk_SuppDelay( p->puSupps[2*Var+1] | (1<<Var), p->pDelays );
00069             DelayB = Lpk_SuppDelay( p->puSupps[2*Var+0]           , p->pDelays );
00070             Delay1 = ABC_MAX( DelayA, DelayB + 1 );
00071             // get the best delay
00072             Delay = ABC_MIN( Delay0, Delay1 );
00073             Area = 2;
00074             Polarity = (int)(Delay == Delay1);
00075         }
00076         else if ( nSuppSize0 <= (int)p->nLutK - 2 )
00077         {
00078             DelayA = Lpk_SuppDelay( p->puSupps[2*Var+0] | (1<<Var), p->pDelays );
00079             DelayB = Lpk_SuppDelay( p->puSupps[2*Var+1]           , p->pDelays );
00080             Delay = ABC_MAX( DelayA, DelayB + 1 );
00081             Area = 1 + Lpk_LutNumLuts( nSuppSize1, p->nLutK );
00082             Polarity = 0;
00083         }
00084         else if ( nSuppSize1 <= (int)p->nLutK - 2 )
00085         {
00086             DelayA = Lpk_SuppDelay( p->puSupps[2*Var+1] | (1<<Var), p->pDelays );
00087             DelayB = Lpk_SuppDelay( p->puSupps[2*Var+0]           , p->pDelays );
00088             Delay = ABC_MAX( DelayA, DelayB + 1 );
00089             Area = 1 + Lpk_LutNumLuts( nSuppSize0, p->nLutK );
00090             Polarity = 1;
00091         }
00092         else if ( nSuppSize0 <= (int)p->nLutK )
00093         {
00094             DelayA = Lpk_SuppDelay( p->puSupps[2*Var+1] | (1<<Var), p->pDelays );
00095             DelayB = Lpk_SuppDelay( p->puSupps[2*Var+0]           , p->pDelays );
00096             Delay = ABC_MAX( DelayA, DelayB + 1 );
00097             Area = 1 + Lpk_LutNumLuts( nSuppSize1+2, p->nLutK );
00098             Polarity = 1;
00099         }
00100         else if ( nSuppSize1 <= (int)p->nLutK )
00101         {
00102             DelayA = Lpk_SuppDelay( p->puSupps[2*Var+0] | (1<<Var), p->pDelays );
00103             DelayB = Lpk_SuppDelay( p->puSupps[2*Var+1]           , p->pDelays );
00104             Delay = ABC_MAX( DelayA, DelayB + 1 );
00105             Area = 1 + Lpk_LutNumLuts( nSuppSize0+2, p->nLutK );
00106             Polarity = 0;
00107         }
00108         else
00109         {
00110             // include cof var into 0-block
00111             DelayA = Lpk_SuppDelay( p->puSupps[2*Var+0] | (1<<Var), p->pDelays );
00112             DelayB = Lpk_SuppDelay( p->puSupps[2*Var+1]           , p->pDelays );
00113             Delay0 = ABC_MAX( DelayA, DelayB + 1 );
00114             // include cof var into 1-block
00115             DelayA = Lpk_SuppDelay( p->puSupps[2*Var+1] | (1<<Var), p->pDelays );
00116             DelayB = Lpk_SuppDelay( p->puSupps[2*Var+0]           , p->pDelays );
00117             Delay1 = ABC_MAX( DelayA, DelayB + 1 );
00118             // get the best delay
00119             Delay = ABC_MIN( Delay0, Delay1 );
00120             if ( Delay == Delay0 )
00121                 Area = Lpk_LutNumLuts( nSuppSize0+2, p->nLutK ) + Lpk_LutNumLuts( nSuppSize1, p->nLutK );
00122             else
00123                 Area = Lpk_LutNumLuts( nSuppSize1+2, p->nLutK ) + Lpk_LutNumLuts( nSuppSize0, p->nLutK );
00124             Polarity = (int)(Delay == Delay1);
00125         }
00126         // find the best variable
00127         if ( Delay > (int)p->nDelayLim )
00128             continue;
00129         if ( Area > (int)p->nAreaLim )
00130             continue;
00131         nSuppSizeS = ABC_MIN( nSuppSize0 + 2 *!Polarity, nSuppSize1 + 2 * Polarity );
00132         nSuppSizeL = ABC_MAX( nSuppSize0 + 2 *!Polarity, nSuppSize1 + 2 * Polarity );
00133         if ( nSuppSizeL > (int)p->nVars )
00134             continue;
00135         if ( pRes->Variable == -1 || pRes->AreaEst > Area || 
00136             (pRes->AreaEst == Area && pRes->nSuppSizeS + pRes->nSuppSizeL > nSuppSizeS + nSuppSizeL) || 
00137             (pRes->AreaEst == Area && pRes->nSuppSizeS + pRes->nSuppSizeL == nSuppSizeS + nSuppSizeL && pRes->DelayEst > Delay) )
00138         {
00139             pRes->Variable = Var;
00140             pRes->Polarity = Polarity;
00141             pRes->AreaEst  = Area;
00142             pRes->DelayEst = Delay;
00143             pRes->nSuppSizeS = nSuppSizeS;
00144             pRes->nSuppSizeL = nSuppSizeL;
00145         }
00146     }
00147     return pRes->Variable == -1 ? NULL : pRes;
00148 }

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 161 of file lpkAbcMux.c.

00162 {
00163     Lpk_Fun_t * pNew;
00164     unsigned * pTruth  = Lpk_FunTruth( p, 0 );
00165     unsigned * pTruth0 = Lpk_FunTruth( p, 1 );
00166     unsigned * pTruth1 = Lpk_FunTruth( p, 2 );
00167 //    unsigned uSupp;
00168     int iVarVac; 
00169     assert( Var >= 0 && Var < (int)p->nVars );
00170     assert( p->nAreaLim >= 2 );
00171     assert( p->uSupp == Kit_BitMask(p->nVars) );
00172     Kit_TruthCofactor0New( pTruth0, pTruth, p->nVars, Var );
00173     Kit_TruthCofactor1New( pTruth1, pTruth, p->nVars, Var );
00174 /*
00175 uSupp = Kit_TruthSupport( pTruth, p->nVars );
00176 Extra_PrintBinary( stdout, &uSupp, 16 ); printf( "\n" );
00177 uSupp = Kit_TruthSupport( pTruth0, p->nVars );
00178 Extra_PrintBinary( stdout, &uSupp, 16 ); printf( "\n" );
00179 uSupp = Kit_TruthSupport( pTruth1, p->nVars );
00180 Extra_PrintBinary( stdout, &uSupp, 16 ); printf( "\n\n" );
00181 */
00182     // derive the new component
00183     pNew = Lpk_FunDup( p, Pol ? pTruth0 : pTruth1 );
00184     // update the support of the old component
00185     p->uSupp  = Kit_TruthSupport( Pol ? pTruth1 : pTruth0, p->nVars );
00186     p->uSupp |= (1 << Var);
00187     // update the truth table of the old component
00188     iVarVac = Kit_WordFindFirstBit( ~p->uSupp );
00189     assert( iVarVac < (int)p->nVars );
00190     p->uSupp |= (1 << iVarVac);
00191     Kit_TruthIthVar( pTruth, p->nVars, iVarVac );
00192     if ( Pol )
00193         Kit_TruthMuxVar( pTruth, pTruth, pTruth1, p->nVars, Var );
00194     else
00195         Kit_TruthMuxVar( pTruth, pTruth0, pTruth, p->nVars, Var );
00196     assert( p->uSupp == Kit_TruthSupport(pTruth, p->nVars) );
00197     // set the decomposed variable
00198     p->pFanins[iVarVac] = pNew->Id;
00199     p->pDelays[iVarVac] = p->nDelayLim - 1;
00200     // support minimize both
00201     p->fSupports = 0;
00202     Lpk_FunSuppMinimize( p );
00203     Lpk_FunSuppMinimize( pNew );
00204     // update delay and area requirements
00205     pNew->nDelayLim = p->nDelayLim - 1;
00206     if ( pNew->nVars <= pNew->nLutK )
00207     {
00208         pNew->nAreaLim = 1;
00209         p->nAreaLim = p->nAreaLim - 1;
00210     }
00211     else if ( p->nVars <= p->nLutK )
00212     {
00213         pNew->nAreaLim = p->nAreaLim - 1;
00214         p->nAreaLim = 1;
00215     }
00216     else if ( p->nVars < pNew->nVars )
00217     {
00218         pNew->nAreaLim = p->nAreaLim / 2 + p->nAreaLim % 2;
00219         p->nAreaLim = p->nAreaLim / 2 - p->nAreaLim % 2;
00220     }
00221     else // if ( pNew->nVars < p->nVars )
00222     {
00223         pNew->nAreaLim = p->nAreaLim / 2 - p->nAreaLim % 2;
00224         p->nAreaLim = p->nAreaLim / 2 + p->nAreaLim % 2;
00225     }
00226     pNew->fMark = 1;
00227     return pNew;
00228 }

Generated on Tue Jan 5 12:19:28 2010 for abc70930 by  doxygen 1.6.1