abc70930: src/opt/lpk/lpkInt.h Source File

00001 
00021 #ifndef __LPK_INT_H__
00022 #define __LPK_INT_H__
00023 
00024 #ifdef __cplusplus
00025 extern "C" {
00026 #endif 
00027 
00031 
00032 #include "abc.h"
00033 #include "kit.h"
00034 #include "if.h"
00035 #include "lpk.h"
00036 
00040 
00044 
00045 #define LPK_SIZE_MAX             24     // the largest size of the function
00046 #define LPK_CUTS_MAX            512     // the largest number of cuts considered
00047 
00048 typedef struct Lpk_Man_t_ Lpk_Man_t;
00049 typedef struct Lpk_Cut_t_ Lpk_Cut_t;
00050 
00051 struct Lpk_Cut_t_
00052 {
00053     unsigned     nLeaves       : 6;     // (L) the number of leaves
00054     unsigned     nNodes        : 6;     // (M) the number of nodes
00055     unsigned     nNodesDup     : 6;     // (Q) nodes outside of MFFC
00056     unsigned     nLuts         : 6;     // (N) the number of LUTs to try
00057     unsigned     unused        : 6;     // unused
00058     unsigned     fHasDsd       : 1;     // set to 1 if the cut has structural DSD (and so cannot be used)
00059     unsigned     fMark         : 1;     // multipurpose mark
00060     unsigned     uSign[2];              // the signature
00061     float        Weight;                // the weight of the cut: (M - Q)/N(V)   (the larger the better)
00062     int          Gain;                  // the gain achieved using this cut
00063     int          pLeaves[LPK_SIZE_MAX]; // the leaves of the cut
00064     int          pNodes[LPK_SIZE_MAX];  // the nodes of the cut
00065 };
00066 
00067 struct Lpk_Man_t_
00068 {
00069     // parameters
00070     Lpk_Par_t *  pPars;                 // the set of parameters
00071     // current representation
00072     Abc_Ntk_t *  pNtk;                  // the network
00073     Abc_Obj_t *  pObj;                  // the node to resynthesize 
00074     // cut representation
00075     int          nMffc;                 // the size of MFFC of the node
00076     int          nCuts;                 // the total number of cuts    
00077     int          nCutsMax;              // the largest possible number of cuts
00078     int          nEvals;                // the number of good cuts
00079     Lpk_Cut_t    pCuts[LPK_CUTS_MAX];   // the storage for cuts
00080     int          pEvals[LPK_CUTS_MAX];  // the good cuts
00081     // visited nodes 
00082     Vec_Vec_t *  vVisited;
00083     // mapping manager
00084     If_Man_t *   pIfMan;
00085     Vec_Int_t *  vCover; 
00086     Vec_Vec_t *  vLevels;
00087     // temporary variables
00088     int          fCofactoring;          // working in the cofactoring mode
00089     int          fCalledOnce;           // limits the depth of MUX cofactoring
00090     int          nCalledSRed;           // the number of called to SRed
00091     int          pRefs[LPK_SIZE_MAX];   // fanin reference counters 
00092     int          pCands[LPK_SIZE_MAX];  // internal nodes pointing only to the leaves
00093     Vec_Ptr_t *  vLeaves;
00094     // truth table representation
00095     Vec_Ptr_t *  vTtElems;              // elementary truth tables
00096     Vec_Ptr_t *  vTtNodes;              // storage for temporary truth tables of the nodes 
00097     Vec_Int_t *  vMemory;
00098     Vec_Int_t *  vBddDir;
00099     Vec_Int_t *  vBddInv;
00100     unsigned     puSupps[32];           // the supports of the cofactors
00101     unsigned *   ppTruths[5][16];
00102     // variable sets
00103     Vec_Int_t *  vSets[8];
00104     Kit_DsdMan_t* pDsdMan;
00105     // statistics
00106     int          nNodesTotal;           // total number of nodes
00107     int          nNodesOver;            // nodes with cuts over the limit 
00108     int          nCutsTotal;            // total number of cuts
00109     int          nCutsUseful;           // useful cuts 
00110     int          nGainTotal;            // the gain in LUTs
00111     int          nChanges;              // the number of changed nodes
00112     int          nBenefited;            // the number of gainful that benefited from decomposition
00113     int          nMuxes;
00114     int          nDsds;
00115     int          nTotalNets;
00116     int          nTotalNets2;
00117     int          nTotalNodes;
00118     int          nTotalNodes2;
00119     // counter of non-DSD blocks
00120     int          nBlocks[17];
00121     // runtime
00122     int          timeCuts;
00123     int          timeTruth;
00124     int          timeSupps;
00125     int          timeTruth2;
00126     int          timeTruth3;
00127     int          timeEval;
00128     int          timeMap;
00129     int          timeOther;
00130     int          timeTotal;
00131     // runtime of eval
00132     int          timeEvalMuxAn;
00133     int          timeEvalMuxSp;
00134     int          timeEvalDsdAn;
00135     int          timeEvalDsdSp;
00136  
00137 };
00138 
00139 
00140 // internal representation of the function to be decomposed
00141 typedef struct Lpk_Fun_t_ Lpk_Fun_t;
00142 struct Lpk_Fun_t_
00143 {
00144     Vec_Ptr_t *  vNodes;           // the array of leaves and decomposition nodes
00145     unsigned     Id         :  7;  // the ID of this node
00146     unsigned     nVars      :  5;  // the number of variables
00147     unsigned     nLutK      :  4;  // the number of LUT inputs
00148     unsigned     nAreaLim   :  5;  // the area limit (the largest allowed)
00149     unsigned     nDelayLim  :  9;  // the delay limit (the largest allowed)
00150     unsigned     fSupports  :  1;  // supports of cofactors were precomputed
00151     unsigned     fMark      :  1;  // marks the MUX-based dec
00152     unsigned     uSupp;            // the support of this component
00153     unsigned     puSupps[32];      // the supports of the cofactors
00154     char         pDelays[16];      // the delays of the inputs
00155     char         pFanins[16];      // the fanins of this function
00156     unsigned     pTruth[0];        // the truth table (contains room for three truth tables)    
00157 };
00158 
00159 // preliminary decomposition result
00160 typedef struct Lpk_Res_t_ Lpk_Res_t;
00161 struct Lpk_Res_t_
00162 {
00163     int          nBSVars;          // the number of bound set variables
00164     unsigned     BSVars;           // the bound set
00165     int          nCofVars;         // the number of cofactoring variables
00166     char         pCofVars[4];      // the cofactoring variables
00167     int          nSuppSizeS;       // support size of the smaller (decomposed) function 
00168     int          nSuppSizeL;       // support size of the larger (composition) function
00169     int          DelayEst;         // estimated delay of the decomposition
00170     int          AreaEst;          // estimated area of the decomposition
00171     int          Variable;         // variable in MUX decomposition
00172     int          Polarity;         // polarity in MUX decomposition
00173 };
00174 
00175 static inline int        Lpk_LutNumVars( int nLutsLim, int nLutK ) { return  nLutsLim * (nLutK - 1) + 1;                                            }
00176 static inline int        Lpk_LutNumLuts( int nVarsMax, int nLutK ) { return (nVarsMax - 1) / (nLutK - 1) + (int)((nVarsMax - 1) % (nLutK - 1) > 0); }
00177 static inline unsigned * Lpk_FunTruth( Lpk_Fun_t * p, int Num )    { assert( Num < 3 ); return p->pTruth + Kit_TruthWordNum(p->nVars) * Num;        }
00178 
00182 
00186 
00187 #define Lpk_CutForEachLeaf( pNtk, pCut, pObj, i )                                        \
00188     for ( i = 0; (i < (int)(pCut)->nLeaves) && (((pObj) = Abc_NtkObj(pNtk, (pCut)->pLeaves[i])), 1); i++ )
00189 #define Lpk_CutForEachNode( pNtk, pCut, pObj, i )                                        \
00190     for ( i = 0; (i < (int)(pCut)->nNodes) && (((pObj) = Abc_NtkObj(pNtk, (pCut)->pNodes[i])), 1); i++ )
00191 #define Lpk_CutForEachNodeReverse( pNtk, pCut, pObj, i )                                 \
00192     for ( i = (int)(pCut)->nNodes - 1; (i >= 0) && (((pObj) = Abc_NtkObj(pNtk, (pCut)->pNodes[i])), 1); i-- )
00193 #define Lpk_SuppForEachVar( Supp, Var )\
00194     for ( Var = 0; Var < 16; Var++ )\
00195         if ( !(Supp & (1<<Var)) ) {} else
00196 
00200 
00201 /*=== lpkAbcDec.c ============================================================*/
00202 extern Abc_Obj_t *    Lpk_Decompose( Lpk_Man_t * pMan, Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, unsigned * pTruth, unsigned * puSupps, int nLutK, int AreaLim, int DelayLim );
00203 /*=== lpkAbcDsd.c ============================================================*/
00204 extern Lpk_Res_t *    Lpk_DsdAnalize( Lpk_Man_t * pMan, Lpk_Fun_t * p, int nShared );
00205 extern Lpk_Fun_t *    Lpk_DsdSplit( Lpk_Man_t * pMan, Lpk_Fun_t * p, char * pCofVars, int nCofVars, unsigned uBoundSet );
00206 /*=== lpkAbcMux.c ============================================================*/
00207 extern Lpk_Res_t *    Lpk_MuxAnalize( Lpk_Man_t * pMan, Lpk_Fun_t * p );
00208 extern Lpk_Fun_t *    Lpk_MuxSplit( Lpk_Man_t * pMan, Lpk_Fun_t * p, int Var, int Pol );
00209 /*=== lpkAbcUtil.c ============================================================*/
00210 extern Lpk_Fun_t *    Lpk_FunAlloc( int nVars );
00211 extern void           Lpk_FunFree( Lpk_Fun_t * p );
00212 extern Lpk_Fun_t *    Lpk_FunCreate( Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, unsigned * pTruth, int nLutK, int AreaLim, int DelayLim );
00213 extern Lpk_Fun_t *    Lpk_FunDup( Lpk_Fun_t * p, unsigned * pTruth );
00214 extern int            Lpk_FunSuppMinimize( Lpk_Fun_t * p );
00215 extern void           Lpk_FunComputeCofSupps( Lpk_Fun_t * p );
00216 extern int            Lpk_SuppDelay( unsigned uSupp, char * pDelays );
00217 extern int            Lpk_SuppToVars( unsigned uBoundSet, char * pVars );
00218 
00219 
00220 /*=== lpkCut.c =========================================================*/
00221 extern unsigned *     Lpk_CutTruth( Lpk_Man_t * p, Lpk_Cut_t * pCut, int fInv );
00222 extern int            Lpk_NodeCuts( Lpk_Man_t * p );
00223 /*=== lpkMap.c =========================================================*/
00224 extern Lpk_Man_t *    Lpk_ManStart( Lpk_Par_t * pPars );
00225 extern void           Lpk_ManStop( Lpk_Man_t * p );
00226 /*=== lpkMap.c =========================================================*/
00227 extern If_Obj_t *     Lpk_MapPrime( Lpk_Man_t * p, unsigned * pTruth, int nVars, If_Obj_t ** ppLeaves );
00228 extern If_Obj_t *     Lpk_MapTree_rec( Lpk_Man_t * p, Kit_DsdNtk_t * pNtk, If_Obj_t ** ppLeaves, int iLit, If_Obj_t * pResult );
00229 /*=== lpkMulti.c =======================================================*/
00230 extern If_Obj_t *     Lpk_MapTreeMulti( Lpk_Man_t * p, unsigned * pTruth, int nLeaves, If_Obj_t ** ppLeaves );
00231 /*=== lpkMux.c =========================================================*/
00232 extern If_Obj_t *     Lpk_MapTreeMux_rec( Lpk_Man_t * p, unsigned * pTruth, int nVars, If_Obj_t ** ppLeaves );
00233 extern If_Obj_t *     Lpk_MapSuppRedDec_rec( Lpk_Man_t * p, unsigned * pTruth, int nVars, If_Obj_t ** ppLeaves );
00234 /*=== lpkSets.c =========================================================*/
00235 extern unsigned       Lpk_MapSuppRedDecSelect( Lpk_Man_t * p, unsigned * pTruth, int nVars, int * piVar, int * piVarReused );
00236 
00237 #ifdef __cplusplus
00238 }
00239 #endif
00240 
00241 #endif
00242 
00246