src/opt/lpk/lpkMux.c File Reference

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

Go to the source code of this file.

Functions

int Lpk_MapTreeBestCofVar (Lpk_Man_t *p, unsigned *pTruth, int nVars, unsigned *pCof0, unsigned *pCof1)
If_Obj_t * Lpk_MapTreeMux_rec (Lpk_Man_t *p, unsigned *pTruth, int nVars, If_Obj_t **ppLeaves)
If_Obj_t * Lpk_MapSuppRedDec_rec (Lpk_Man_t *p, unsigned *pTruth, int nVars, If_Obj_t **ppLeaves)

Function Documentation

If_Obj_t* Lpk_MapSuppRedDec_rec ( Lpk_Man_t *  p,
unsigned *  pTruth,
int  nVars,
If_Obj_t **  ppLeaves 
)

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

Synopsis [Implements support-reducing decomposition.]

Description []

SideEffects []

SeeAlso []

Definition at line 130 of file lpkMux.c.

00131 {
00132     Kit_DsdNtk_t * pNtkDec, * pNtkComp, * ppNtks[2], * pTemp;
00133     If_Obj_t * pObjNew;
00134     unsigned * pCof0 = Vec_PtrEntry( p->vTtNodes,  0 );
00135     unsigned * pCof1 = Vec_PtrEntry( p->vTtNodes,  1 );
00136     unsigned * pDec0 = Vec_PtrEntry( p->vTtNodes,  2 );
00137     unsigned * pDec1 = Vec_PtrEntry( p->vTtNodes,  3 );
00138     unsigned * pDec  = Vec_PtrEntry( p->vTtNodes,  4 );
00139     unsigned * pCo00 = Vec_PtrEntry( p->vTtNodes,  5 );
00140     unsigned * pCo01 = Vec_PtrEntry( p->vTtNodes,  6 );
00141     unsigned * pCo10 = Vec_PtrEntry( p->vTtNodes,  7 );
00142     unsigned * pCo11 = Vec_PtrEntry( p->vTtNodes,  8 );
00143     unsigned * pCo0  = Vec_PtrEntry( p->vTtNodes,  9 );
00144     unsigned * pCo1  = Vec_PtrEntry( p->vTtNodes, 10 );
00145     unsigned * pCo   = Vec_PtrEntry( p->vTtNodes, 11 );
00146     int TrueMint0, TrueMint1, FalseMint0, FalseMint1;
00147     int uSubsets, uSubset0, uSubset1, iVar, iVarReused, i;
00148 
00149     // determine if supp-red decomposition exists
00150     uSubsets = Lpk_MapSuppRedDecSelect( p, pTruth, nVars, &iVar, &iVarReused );
00151     if ( uSubsets == 0 )
00152         return NULL;
00153     p->nCalledSRed++;
00154 
00155     // get the cofactors
00156     Kit_TruthCofactor0New( pCof0, pTruth, nVars, iVar );
00157     Kit_TruthCofactor1New( pCof1, pTruth, nVars, iVar );
00158 
00159     // get the bound sets
00160     uSubset0 = uSubsets & 0xFFFF;
00161     uSubset1 = uSubsets >> 16;
00162 
00163     // compute the decomposed functions
00164     ppNtks[0] = Kit_DsdDecompose( pCof0, nVars );
00165     ppNtks[1] = Kit_DsdDecompose( pCof1, nVars );
00166     ppNtks[0] = Kit_DsdExpand( pTemp = ppNtks[0] );      Kit_DsdNtkFree( pTemp );
00167     ppNtks[1] = Kit_DsdExpand( pTemp = ppNtks[1] );      Kit_DsdNtkFree( pTemp );
00168     Kit_DsdTruthPartial( p->pDsdMan, ppNtks[0], pDec0, uSubset0 );
00169     Kit_DsdTruthPartial( p->pDsdMan, ppNtks[1], pDec1, uSubset1 );
00170 //    Kit_DsdTruthPartialTwo( p->pDsdMan, ppNtks[0], uSubset0, iVarReused, pCo0, pDec0 );
00171 //    Kit_DsdTruthPartialTwo( p->pDsdMan, ppNtks[1], uSubset1, iVarReused, pCo1, pDec1 );
00172     Kit_DsdNtkFree( ppNtks[0] );
00173     Kit_DsdNtkFree( ppNtks[1] );
00174 //Kit_DsdPrintFromTruth( pDec0, nVars );
00175 //Kit_DsdPrintFromTruth( pDec1, nVars );
00176     // get the decomposed function
00177     Kit_TruthMuxVar( pDec, pDec0, pDec1, nVars, iVar );
00178 
00179     // find any true assignments of the decomposed functions
00180     TrueMint0 = Kit_TruthFindFirstBit( pDec0, nVars );
00181     TrueMint1 = Kit_TruthFindFirstBit( pDec1, nVars );
00182     assert( TrueMint0 >= 0 && TrueMint1 >= 0 );
00183     // find any false assignments of the decomposed functions
00184     FalseMint0 = Kit_TruthFindFirstZero( pDec0, nVars );
00185     FalseMint1 = Kit_TruthFindFirstZero( pDec1, nVars );
00186     assert( FalseMint0 >= 0 && FalseMint1 >= 0 );
00187 
00188     // cofactor the cofactors according to these minterms
00189     Kit_TruthCopy( pCo00, pCof0, nVars );
00190     Kit_TruthCopy( pCo01, pCof0, nVars );
00191     for ( i = 0; i < nVars; i++ )
00192         if ( uSubset0 & (1 << i) )
00193         {
00194             if ( FalseMint0 & (1 << i) )
00195                 Kit_TruthCofactor1( pCo00, nVars, i );
00196             else
00197                 Kit_TruthCofactor0( pCo00, nVars, i );
00198             if ( TrueMint0 & (1 << i) )
00199                 Kit_TruthCofactor1( pCo01, nVars, i );
00200             else
00201                 Kit_TruthCofactor0( pCo01, nVars, i );
00202         }
00203     Kit_TruthCopy( pCo10, pCof1, nVars );
00204     Kit_TruthCopy( pCo11, pCof1, nVars );
00205     for ( i = 0; i < nVars; i++ )
00206         if ( uSubset1 & (1 << i) )
00207         {
00208             if ( FalseMint1 & (1 << i) )
00209                 Kit_TruthCofactor1( pCo10, nVars, i );
00210             else
00211                 Kit_TruthCofactor0( pCo10, nVars, i );
00212             if ( TrueMint1 & (1 << i) )
00213                 Kit_TruthCofactor1( pCo11, nVars, i );
00214             else
00215                 Kit_TruthCofactor0( pCo11, nVars, i );
00216         }
00217 
00218     // derive the functions by composing them with the new variable (iVarReused)
00219     Kit_TruthMuxVar( pCo0, pCo00, pCo01, nVars, iVarReused );
00220     Kit_TruthMuxVar( pCo1, pCo10, pCo11, nVars, iVarReused );
00221 //Kit_DsdPrintFromTruth( pCo0, nVars );
00222 //Kit_DsdPrintFromTruth( pCo1, nVars );
00223 
00224     // derive the composition function
00225     Kit_TruthMuxVar( pCo , pCo0 , pCo1 , nVars, iVar );
00226 
00227     // process the decomposed function
00228     pNtkDec = Kit_DsdDecompose( pDec, nVars );
00229     pNtkComp = Kit_DsdDecompose( pCo, nVars );
00230 //Kit_DsdPrint( stdout, pNtkDec );
00231 //Kit_DsdPrint( stdout, pNtkComp );
00232 //printf( "cofactored variable %c\n", 'a' + iVar );
00233 //printf( "reused variable %c\n", 'a' + iVarReused );
00234 
00235     ppLeaves[iVarReused] = Lpk_MapTree_rec( p, pNtkDec, ppLeaves, pNtkDec->Root, NULL );
00236     pObjNew = Lpk_MapTree_rec( p, pNtkComp, ppLeaves, pNtkComp->Root, NULL );
00237 
00238     Kit_DsdNtkFree( pNtkDec );
00239     Kit_DsdNtkFree( pNtkComp );
00240     return pObjNew;
00241 }

int Lpk_MapTreeBestCofVar ( Lpk_Man_t *  p,
unsigned *  pTruth,
int  nVars,
unsigned *  pCof0,
unsigned *  pCof1 
)

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

FileName [lpkMux.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Fast Boolean matching for LUT structures.]

Synopsis []

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

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

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

Synopsis [Find the best cofactoring variable.]

Description []

SideEffects []

SeeAlso []

Definition at line 42 of file lpkMux.c.

00043 {
00044     int i, iBestVar, nSuppSizeCur0, nSuppSizeCur1, nSuppSizeCur, nSuppSizeMin;
00045     // iterate through variables
00046     iBestVar = -1;
00047     nSuppSizeMin = KIT_INFINITY;
00048     for ( i = 0; i < nVars; i++ )
00049     {
00050         // cofactor the functiona and get support sizes
00051         Kit_TruthCofactor0New( pCof0, pTruth, nVars, i );
00052         Kit_TruthCofactor1New( pCof1, pTruth, nVars, i );
00053         nSuppSizeCur0 = Kit_TruthSupportSize( pCof0, nVars );
00054         nSuppSizeCur1 = Kit_TruthSupportSize( pCof1, nVars );
00055         nSuppSizeCur  = nSuppSizeCur0 + nSuppSizeCur1;
00056         // skip cofactoring that goes above the limit
00057         if ( nSuppSizeCur0 > p->pPars->nLutSize || nSuppSizeCur1 > p->pPars->nLutSize )
00058             continue;
00059         // compare this variable with other variables
00060         if ( nSuppSizeMin > nSuppSizeCur ) 
00061         {
00062             nSuppSizeMin = nSuppSizeCur;
00063             iBestVar = i;
00064         }
00065     }
00066     // cofactor w.r.t. this variable
00067     if ( iBestVar != -1 )
00068     {
00069         Kit_TruthCofactor0New( pCof0, pTruth, nVars, iBestVar );
00070         Kit_TruthCofactor1New( pCof1, pTruth, nVars, iBestVar );
00071     }
00072     return iBestVar;
00073 }

If_Obj_t* Lpk_MapTreeMux_rec ( Lpk_Man_t *  p,
unsigned *  pTruth,
int  nVars,
If_Obj_t **  ppLeaves 
)

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

Synopsis [Maps the function by the best cofactoring.]

Description []

SideEffects []

SeeAlso []

Definition at line 86 of file lpkMux.c.

00087 {
00088     unsigned * pCof0 = Vec_PtrEntry( p->vTtNodes, 0 );
00089     unsigned * pCof1 = Vec_PtrEntry( p->vTtNodes, 1 );
00090     If_Obj_t * pObj0, * pObj1;
00091     Kit_DsdNtk_t * ppNtks[2];
00092     int iBestVar;
00093     assert( nVars > 3 );
00094     p->fCalledOnce = 1;
00095     // cofactor w.r.t. the best variable
00096     iBestVar = Lpk_MapTreeBestCofVar( p, pTruth, nVars, pCof0, pCof1 );
00097     if ( iBestVar == -1 )
00098         return NULL;
00099     // decompose the functions
00100     ppNtks[0] = Kit_DsdDecompose( pCof0, nVars );
00101     ppNtks[1] = Kit_DsdDecompose( pCof1, nVars );
00102     if ( p->pPars->fVeryVerbose )
00103     {
00104         printf( "Cofactoring w.r.t. var %c (%d -> %d+%d supp vars):\n", 
00105             'a'+iBestVar, nVars, Kit_TruthSupportSize(pCof0, nVars), Kit_TruthSupportSize(pCof1, nVars) );
00106         Kit_DsdPrintExpanded( ppNtks[0] );
00107         Kit_DsdPrintExpanded( ppNtks[1] );
00108     }
00109     // map the DSD structures
00110     pObj0 = Lpk_MapTree_rec( p, ppNtks[0], ppLeaves, ppNtks[0]->Root, NULL );
00111     pObj1 = Lpk_MapTree_rec( p, ppNtks[1], ppLeaves, ppNtks[1]->Root, NULL );
00112     Kit_DsdNtkFree( ppNtks[0] );
00113     Kit_DsdNtkFree( ppNtks[1] );
00114     return If_ManCreateMux( p->pIfMan, pObj0, pObj1, ppLeaves[iBestVar] );
00115 }

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