src/opt/lpk/lpkAbcDec.c File Reference

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

Go to the source code of this file.

Functions

Abc_Obj_t * Lpk_ImplementFun (Lpk_Man_t *pMan, Abc_Ntk_t *pNtk, Vec_Ptr_t *vLeaves, Lpk_Fun_t *p)
Abc_Obj_t * Lpk_Implement_rec (Lpk_Man_t *pMan, Abc_Ntk_t *pNtk, Vec_Ptr_t *vLeaves, Lpk_Fun_t *pFun)
Abc_Obj_t * Lpk_Implement (Lpk_Man_t *pMan, Abc_Ntk_t *pNtk, Vec_Ptr_t *vLeaves, int nLeavesOld)
int Lpk_Decompose_rec (Lpk_Man_t *pMan, Lpk_Fun_t *p)
void Lpk_DecomposeClean (Vec_Ptr_t *vLeaves, int nLeavesOld)
Abc_Obj_t * Lpk_Decompose (Lpk_Man_t *p, Abc_Ntk_t *pNtk, Vec_Ptr_t *vLeaves, unsigned *pTruth, unsigned *puSupps, int nLutK, int AreaLim, int DelayLim)

Function Documentation

Abc_Obj_t* Lpk_Decompose ( Lpk_Man_t *  p,
Abc_Ntk_t *  pNtk,
Vec_Ptr_t *  vLeaves,
unsigned *  pTruth,
unsigned *  puSupps,
int  nLutK,
int  AreaLim,
int  DelayLim 
)

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

Synopsis [Decomposes the function using recursive MUX decomposition.]

Description []

SideEffects []

SeeAlso []

Definition at line 256 of file lpkAbcDec.c.

00257 {
00258     Lpk_Fun_t * pFun;
00259     Abc_Obj_t * pObjNew = NULL;
00260     int nLeaves = Vec_PtrSize( vLeaves );
00261     pFun = Lpk_FunCreate( pNtk, vLeaves, pTruth, nLutK, AreaLim, DelayLim );
00262     if ( puSupps[0] || puSupps[1] )
00263     {
00264 /*
00265         int i;
00266         Lpk_FunComputeCofSupps( pFun );
00267         for ( i = 0; i < nLeaves; i++ )
00268         {
00269             assert( pFun->puSupps[2*i+0] == puSupps[2*i+0] );
00270             assert( pFun->puSupps[2*i+1] == puSupps[2*i+1] );
00271         }
00272 */
00273         memcpy( pFun->puSupps, puSupps, sizeof(unsigned) * 2 * nLeaves );
00274         pFun->fSupports = 1;
00275     }
00276     Lpk_FunSuppMinimize( pFun );
00277     if ( pFun->nVars <= pFun->nLutK )
00278         pObjNew = Lpk_ImplementFun( p, pNtk, vLeaves, pFun );
00279     else if ( Lpk_Decompose_rec(p, pFun) )
00280         pObjNew = Lpk_Implement( p, pNtk, vLeaves, nLeaves );
00281     Lpk_DecomposeClean( vLeaves, nLeaves );
00282     return pObjNew;
00283 }

int Lpk_Decompose_rec ( Lpk_Man_t *  pMan,
Lpk_Fun_t *  p 
)

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

Synopsis [Decomposes the function using recursive MUX decomposition.]

Description [Returns the ID of the top-most decomposition node implementing this function, or 0 if there is no decomposition satisfying the constraints on area and delay.]

SideEffects []

SeeAlso []

Definition at line 144 of file lpkAbcDec.c.

00145 {
00146     static Lpk_Res_t Res0, * pRes0 = &Res0;
00147     Lpk_Res_t * pResMux, * pResDsd;
00148     Lpk_Fun_t * p2;
00149     int clk;
00150 
00151     // is only called for non-trivial blocks
00152     assert( p->nLutK >= 3 && p->nLutK <= 6 );
00153     assert( p->nVars > p->nLutK );
00154     // skip if area bound is exceeded
00155     if ( Lpk_LutNumLuts(p->nVars, p->nLutK) > (int)p->nAreaLim )
00156         return 0;
00157     // skip if delay bound is exceeded
00158     if ( Lpk_SuppDelay(p->uSupp, p->pDelays) > (int)p->nDelayLim )
00159         return 0;
00160 
00161     // compute supports if needed
00162     if ( !p->fSupports )
00163         Lpk_FunComputeCofSupps( p );
00164 
00165     // check DSD decomposition
00166 clk = clock();
00167     pResDsd = Lpk_DsdAnalize( pMan, p, pMan->pPars->nVarsShared );
00168 pMan->timeEvalDsdAn += clock() - clk;
00169     if ( pResDsd && (pResDsd->nBSVars == (int)p->nLutK || pResDsd->nBSVars == (int)p->nLutK - 1) && 
00170           pResDsd->AreaEst <= (int)p->nAreaLim && pResDsd->DelayEst <= (int)p->nDelayLim )
00171     {
00172 clk = clock();
00173         p2 = Lpk_DsdSplit( pMan, p, pResDsd->pCofVars, pResDsd->nCofVars, pResDsd->BSVars );
00174 pMan->timeEvalDsdSp += clock() - clk;
00175         assert( p2->nVars <= (int)p->nLutK );
00176         if ( p->nVars > p->nLutK && !Lpk_Decompose_rec( pMan, p ) )
00177             return 0;
00178         return 1;
00179     }
00180 
00181     // check MUX decomposition
00182 clk = clock();
00183     pResMux = Lpk_MuxAnalize( pMan, p );
00184 pMan->timeEvalMuxAn += clock() - clk;
00185 //    pResMux = NULL;
00186     assert( !pResMux || (pResMux->DelayEst <= (int)p->nDelayLim && pResMux->AreaEst <= (int)p->nAreaLim) );
00187     // accept MUX decomposition if it is "good"
00188     if ( pResMux && pResMux->nSuppSizeS <= (int)p->nLutK && pResMux->nSuppSizeL <= (int)p->nLutK )
00189         pResDsd = NULL;
00190     else if ( pResMux && pResDsd )
00191     {
00192         // compare two decompositions
00193         if ( pResMux->AreaEst < pResDsd->AreaEst || 
00194             (pResMux->AreaEst == pResDsd->AreaEst && pResMux->nSuppSizeL < pResDsd->nSuppSizeL) || 
00195             (pResMux->AreaEst == pResDsd->AreaEst && pResMux->nSuppSizeL == pResDsd->nSuppSizeL && pResMux->DelayEst < pResDsd->DelayEst) )
00196             pResDsd = NULL;
00197         else
00198             pResMux = NULL;
00199     }
00200     assert( pResMux == NULL || pResDsd == NULL );
00201     if ( pResMux )
00202     {
00203 clk = clock();
00204         p2 = Lpk_MuxSplit( pMan, p, pResMux->Variable, pResMux->Polarity );
00205 pMan->timeEvalMuxSp += clock() - clk;
00206         if ( p2->nVars > p->nLutK && !Lpk_Decompose_rec( pMan, p2 ) )
00207             return 0;
00208         if ( p->nVars > p->nLutK && !Lpk_Decompose_rec( pMan, p ) )
00209             return 0;
00210         return 1;
00211     }
00212     if ( pResDsd )
00213     {
00214 clk = clock();
00215         p2 = Lpk_DsdSplit( pMan, p, pResDsd->pCofVars, pResDsd->nCofVars, pResDsd->BSVars );
00216 pMan->timeEvalDsdSp += clock() - clk;
00217         assert( p2->nVars <= (int)p->nLutK );
00218         if ( p->nVars > p->nLutK && !Lpk_Decompose_rec( pMan, p ) )
00219             return 0;
00220         return 1;
00221     }
00222     return 0;
00223 }

void Lpk_DecomposeClean ( Vec_Ptr_t *  vLeaves,
int  nLeavesOld 
)

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

Synopsis [Removes decomposed nodes from the array of fanins.]

Description []

SideEffects []

SeeAlso []

Definition at line 236 of file lpkAbcDec.c.

00237 {
00238     Lpk_Fun_t * pFunc;
00239     int i;
00240     Vec_PtrForEachEntryStart( vLeaves, pFunc, i, nLeavesOld )
00241         Lpk_FunFree( pFunc );
00242     Vec_PtrShrink( vLeaves, nLeavesOld );
00243 }

Abc_Obj_t* Lpk_Implement ( Lpk_Man_t *  pMan,
Abc_Ntk_t *  pNtk,
Vec_Ptr_t *  vLeaves,
int  nLeavesOld 
)

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

Synopsis [Implements the function.]

Description [Returns the node implementing this function.]

SideEffects []

SeeAlso []

Definition at line 117 of file lpkAbcDec.c.

00118 {
00119     Abc_Obj_t * pFanin, * pRes;
00120     int i;
00121     assert( nLeavesOld < Vec_PtrSize(vLeaves) );
00122     // mark implemented nodes
00123     Vec_PtrForEachEntryStop( vLeaves, pFanin, i, nLeavesOld )
00124         Vec_PtrWriteEntry( vLeaves, i, Abc_ObjNot(pFanin) );
00125     // recursively construct starting from the first entry
00126     pRes = Lpk_Implement_rec( pMan, pNtk, vLeaves, Vec_PtrEntry( vLeaves, nLeavesOld ) );
00127     Vec_PtrShrink( vLeaves, nLeavesOld );
00128     return pRes;
00129 }

Abc_Obj_t* Lpk_Implement_rec ( Lpk_Man_t *  pMan,
Abc_Ntk_t *  pNtk,
Vec_Ptr_t *  vLeaves,
Lpk_Fun_t *  pFun 
)

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

Synopsis [Implements the function.]

Description [Returns the node implementing this function.]

SideEffects []

SeeAlso []

Definition at line 85 of file lpkAbcDec.c.

00086 {
00087     Abc_Obj_t * pFanin, * pRes;
00088     int i;
00089     // prepare the leaves of the function
00090     for ( i = 0; i < (int)pFun->nVars; i++ )
00091     {
00092         pFanin = Vec_PtrEntry( vLeaves, pFun->pFanins[i] );
00093         if ( !Abc_ObjIsComplement(pFanin) )
00094             Lpk_Implement_rec( pMan, pNtk, vLeaves, (Lpk_Fun_t *)pFanin );
00095         pFanin = Vec_PtrEntry( vLeaves, pFun->pFanins[i] );
00096         assert( Abc_ObjIsComplement(pFanin) );
00097     }
00098     // construct the function
00099     pRes = Lpk_ImplementFun( pMan, pNtk, vLeaves, pFun );
00100     // replace the function
00101     Vec_PtrWriteEntry( vLeaves, pFun->Id, Abc_ObjNot(pRes) );
00102     Lpk_FunFree( pFun );
00103     return pRes;
00104 }

Abc_Obj_t* Lpk_ImplementFun ( Lpk_Man_t *  pMan,
Abc_Ntk_t *  pNtk,
Vec_Ptr_t *  vLeaves,
Lpk_Fun_t *  p 
)

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

FileName [lpkAbcDec.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Fast Boolean matching for LUT structures.]

Synopsis [The new core procedure.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

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

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

Synopsis [Implements the function.]

Description [Returns the node implementing this function.]

SideEffects []

SeeAlso []

Definition at line 42 of file lpkAbcDec.c.

00043 {
00044     extern Hop_Obj_t * Kit_TruthToHop( Hop_Man_t * pMan, unsigned * pTruth, int nVars, Vec_Int_t * vMemory );
00045     unsigned * pTruth;
00046     Abc_Obj_t * pObjNew;
00047     int i;
00048     if ( p->fMark )
00049         pMan->nMuxes++;
00050     else
00051         pMan->nDsds++;
00052     // create the new node
00053     pObjNew = Abc_NtkCreateNode( pNtk );
00054     for ( i = 0; i < (int)p->nVars; i++ )
00055         Abc_ObjAddFanin( pObjNew, Abc_ObjRegular(Vec_PtrEntry(vLeaves, p->pFanins[i])) );
00056     Abc_ObjSetLevel( pObjNew, Abc_ObjLevelNew(pObjNew) );
00057     // assign the node's function
00058     pTruth = Lpk_FunTruth(p, 0);
00059     if ( p->nVars == 0 )
00060     {
00061         pObjNew->pData = Hop_NotCond( Hop_ManConst1(pNtk->pManFunc), !(pTruth[0] & 1) );
00062         return pObjNew;
00063     }
00064     if ( p->nVars == 1 )
00065     {
00066         pObjNew->pData = Hop_NotCond( Hop_ManPi(pNtk->pManFunc, 0), (pTruth[0] & 1) );
00067         return pObjNew;
00068     }
00069     // create the logic function
00070     pObjNew->pData = Kit_TruthToHop( pNtk->pManFunc, pTruth, p->nVars, NULL );
00071     return pObjNew;
00072 }

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