abc70930: src/base/abci/abcPart.c Source File

00001 
00021 #include "abc.h"
00022 
00026 
00027 typedef struct Supp_Man_t_     Supp_Man_t;
00028 struct Supp_Man_t_
00029 {
00030     int              nChunkSize;    // the size of one chunk of memory (~1 Mb)
00031     int              nStepSize;     // the step size in saving memory (~64 bytes)
00032     char *           pFreeBuf;      // the pointer to free memory
00033     int              nFreeSize;     // the size of remaining free memory
00034     Vec_Ptr_t *      vMemory;       // the memory allocated
00035     Vec_Ptr_t *      vFree;         // the vector of free pieces of memory
00036 };
00037 
00038 typedef struct Supp_One_t_     Supp_One_t;
00039 struct Supp_One_t_
00040 {
00041     int              nRefs;         // the number of references
00042     int              nOuts;         // the number of outputs
00043     int              nOutsAlloc;    // the array size
00044     int              pOuts[0];      // the array of outputs
00045 };
00046 
00047 static inline int    Supp_SizeType( int nSize, int nStepSize )     { return nSize / nStepSize + ((nSize % nStepSize) > 0); }
00048 static inline char * Supp_OneNext( char * pPart )                  { return *((char **)pPart);                             }
00049 static inline void   Supp_OneSetNext( char * pPart, char * pNext ) { *((char **)pPart) = pNext;                            }
00050 
00054 
00066 Supp_Man_t * Supp_ManStart( int nChunkSize, int nStepSize )
00067 {
00068     Supp_Man_t * p;
00069     p = ALLOC( Supp_Man_t, 1 );
00070     memset( p, 0, sizeof(Supp_Man_t) );
00071     p->nChunkSize = nChunkSize;
00072     p->nStepSize  = nStepSize;
00073     p->vMemory    = Vec_PtrAlloc( 1000 );
00074     p->vFree      = Vec_PtrAlloc( 1000 );
00075     return p;
00076 }
00077 
00089 void Supp_ManStop( Supp_Man_t * p )
00090 {
00091     void * pMemory;
00092     int i;
00093     Vec_PtrForEachEntry( p->vMemory, pMemory, i )
00094         free( pMemory );
00095     Vec_PtrFree( p->vMemory );
00096     Vec_PtrFree( p->vFree );
00097     free( p );
00098 }
00099 
00111 char * Supp_ManFetch( Supp_Man_t * p, int nSize )
00112 {
00113     int Type, nSizeReal;
00114     char * pMemory;
00115     assert( nSize > 0 );
00116     Type = Supp_SizeType( nSize, p->nStepSize );
00117     Vec_PtrFillExtra( p->vFree, Type + 1, NULL );
00118     if ( pMemory = Vec_PtrEntry( p->vFree, Type ) )
00119     {
00120         Vec_PtrWriteEntry( p->vFree, Type, Supp_OneNext(pMemory) );
00121         return pMemory;
00122     }
00123     nSizeReal = p->nStepSize * Type;
00124     if ( p->nFreeSize < nSizeReal )
00125     {
00126         p->pFreeBuf = ALLOC( char, p->nChunkSize );
00127         p->nFreeSize = p->nChunkSize;
00128         Vec_PtrPush( p->vMemory, p->pFreeBuf );
00129     }
00130     assert( p->nFreeSize >= nSizeReal );
00131     pMemory = p->pFreeBuf;
00132     p->pFreeBuf  += nSizeReal;
00133     p->nFreeSize -= nSizeReal;
00134     return pMemory;
00135 }
00136 
00148 void Supp_ManRecycle( Supp_Man_t * p, char * pMemory, int nSize )
00149 {
00150     int Type;
00151     Type = Supp_SizeType( nSize, p->nStepSize );
00152     Vec_PtrFillExtra( p->vFree, Type + 1, NULL );
00153     Supp_OneSetNext( pMemory, Vec_PtrEntry(p->vFree, Type) );
00154     Vec_PtrWriteEntry( p->vFree, Type, pMemory );
00155 }
00156 
00168 static inline Supp_One_t * Supp_ManFetchEntry( Supp_Man_t * p, int nWords, int nRefs )
00169 {
00170     Supp_One_t * pPart;
00171     pPart = (Supp_One_t *)Supp_ManFetch( p, sizeof(Supp_One_t) + sizeof(int) * nWords );
00172     pPart->nRefs = nRefs;
00173     pPart->nOuts = 0;
00174     pPart->nOutsAlloc = nWords;
00175     return pPart;
00176 }
00177 
00189 static inline void Supp_ManRecycleEntry( Supp_Man_t * p, Supp_One_t * pEntry )
00190 {
00191     assert( pEntry->nOuts <= pEntry->nOutsAlloc );
00192     assert( pEntry->nOuts >= pEntry->nOutsAlloc/2 );
00193     Supp_ManRecycle( p, (char *)pEntry, sizeof(Supp_One_t) + sizeof(int) * pEntry->nOutsAlloc );
00194 }
00195 
00207 Supp_One_t * Supp_ManMergeEntry( Supp_Man_t * pMan, Supp_One_t * p1, Supp_One_t * p2, int nRefs )
00208 {
00209     Supp_One_t * p = Supp_ManFetchEntry( pMan, p1->nOuts + p2->nOuts, nRefs );
00210     int * pBeg1 = p1->pOuts;
00211     int * pBeg2 = p2->pOuts;
00212     int * pBeg  = p->pOuts;
00213     int * pEnd1 = p1->pOuts + p1->nOuts;
00214     int * pEnd2 = p2->pOuts + p2->nOuts;
00215     while ( pBeg1 < pEnd1 && pBeg2 < pEnd2 )
00216     {
00217         if ( *pBeg1 == *pBeg2 )
00218             *pBeg++ = *pBeg1++, pBeg2++;
00219         else if ( *pBeg1 < *pBeg2 )
00220             *pBeg++ = *pBeg1++;
00221         else 
00222             *pBeg++ = *pBeg2++;
00223     }
00224     while ( pBeg1 < pEnd1 )
00225         *pBeg++ = *pBeg1++;
00226     while ( pBeg2 < pEnd2 )
00227         *pBeg++ = *pBeg2++;
00228     p->nOuts = pBeg - p->pOuts;
00229     assert( p->nOuts <= p->nOutsAlloc );
00230     assert( p->nOuts >= p1->nOuts );
00231     assert( p->nOuts >= p2->nOuts );
00232     return p;
00233 }
00234 
00246 Vec_Int_t * Supp_ManTransferEntry( Supp_One_t * p )
00247 {
00248     Vec_Int_t * vSupp;
00249     int i;
00250     vSupp = Vec_IntAlloc( p->nOuts );
00251     for ( i = 0; i < p->nOuts; i++ )
00252         Vec_IntPush( vSupp, p->pOuts[i] );
00253     return vSupp;
00254 }
00255 
00267 Vec_Ptr_t * Abc_NtkDfsNatural( Abc_Ntk_t * pNtk )
00268 {
00269     Vec_Ptr_t * vNodes;
00270     Abc_Obj_t * pObj, * pNext;
00271     int i, k;
00272     assert( Abc_NtkIsStrash(pNtk) );
00273     vNodes = Vec_PtrAlloc( Abc_NtkObjNum(pNtk) );
00274     Abc_NtkIncrementTravId( pNtk );
00275     // add the constant-1 nodes
00276     pObj = Abc_AigConst1(pNtk);
00277     Abc_NodeSetTravIdCurrent( pObj );
00278     Vec_PtrPush( vNodes, pObj );
00279     // add the CIs/nodes/COs in the topological order
00280     Abc_NtkForEachNode( pNtk, pObj, i )
00281     {
00282         // check the fanins and add CIs
00283         Abc_ObjForEachFanin( pObj, pNext, k )
00284             if ( Abc_ObjIsCi(pNext) && !Abc_NodeIsTravIdCurrent(pNext) )
00285             {
00286                 Abc_NodeSetTravIdCurrent( pNext );
00287                 Vec_PtrPush( vNodes, pNext );
00288             }
00289         // add the node
00290         Vec_PtrPush( vNodes, pObj );
00291         // check the fanouts and add COs
00292         Abc_ObjForEachFanout( pObj, pNext, k )
00293             if ( Abc_ObjIsCo(pNext) && !Abc_NodeIsTravIdCurrent(pNext) )
00294             {
00295                 Abc_NodeSetTravIdCurrent( pNext );
00296                 Vec_PtrPush( vNodes, pNext );
00297             }
00298     }
00299     return vNodes;
00300 }
00301 
00313 Vec_Ptr_t * Abc_NtkComputeSupportsSmart( Abc_Ntk_t * pNtk )
00314 {
00315     Vec_Ptr_t * vSupports;
00316     Vec_Ptr_t * vNodes;
00317     Vec_Int_t * vSupp;
00318     Supp_Man_t * p;
00319     Supp_One_t * pPart0, * pPart1;
00320     Abc_Obj_t * pObj;
00321     int i;
00322     // set the number of PIs/POs
00323     Abc_NtkForEachCi( pNtk, pObj, i )
00324         pObj->pNext = (Abc_Obj_t *)i;
00325     Abc_NtkForEachCo( pNtk, pObj, i )
00326         pObj->pNext = (Abc_Obj_t *)i;
00327     // start the support computation manager
00328     p = Supp_ManStart( 1 << 20, 1 << 6 );
00329     // consider objects in the topological order
00330     vSupports = Vec_PtrAlloc( Abc_NtkCoNum(pNtk) );
00331     Abc_NtkCleanCopy(pNtk);
00332     // order the nodes so that the PIs and POs follow naturally
00333     vNodes = Abc_NtkDfsNatural( pNtk );
00334     Vec_PtrForEachEntry( vNodes, pObj, i )
00335     {
00336         if ( Abc_ObjIsNode(pObj) )
00337         {
00338             pPart0 = (Supp_One_t *)Abc_ObjFanin0(pObj)->pCopy;
00339             pPart1 = (Supp_One_t *)Abc_ObjFanin1(pObj)->pCopy;
00340             pObj->pCopy = (Abc_Obj_t *)Supp_ManMergeEntry( p, pPart0, pPart1, Abc_ObjFanoutNum(pObj) );
00341             assert( pPart0->nRefs > 0 );
00342             if ( --pPart0->nRefs == 0 )
00343                 Supp_ManRecycleEntry( p, pPart0 );
00344             assert( pPart1->nRefs > 0 );
00345             if ( --pPart1->nRefs == 0 )
00346                 Supp_ManRecycleEntry( p, pPart1 );
00347             continue;
00348         }
00349         if ( Abc_ObjIsCo(pObj) )
00350         {
00351             pPart0 = (Supp_One_t *)Abc_ObjFanin0(pObj)->pCopy;
00352             // only save the CO if it is non-trivial
00353             if ( Abc_ObjIsNode(Abc_ObjFanin0(pObj)) )
00354             {
00355                 vSupp = Supp_ManTransferEntry(pPart0);
00356                 Vec_IntPush( vSupp, (int)pObj->pNext );
00357                 Vec_PtrPush( vSupports, vSupp );
00358             }
00359             assert( pPart0->nRefs > 0 );
00360             if ( --pPart0->nRefs == 0 )
00361                 Supp_ManRecycleEntry( p, pPart0 );
00362             continue;
00363         }
00364         if ( Abc_ObjIsCi(pObj) )
00365         {
00366             if ( Abc_ObjFanoutNum(pObj) )
00367             {
00368                 pPart0 = (Supp_One_t *)Supp_ManFetchEntry( p, 1, Abc_ObjFanoutNum(pObj) );
00369                 pPart0->pOuts[ pPart0->nOuts++ ] = (int)pObj->pNext;
00370                 pObj->pCopy = (Abc_Obj_t *)pPart0;
00371             }
00372             continue;
00373         }
00374         if ( pObj == Abc_AigConst1(pNtk) )
00375         {
00376             if ( Abc_ObjFanoutNum(pObj) )
00377                 pObj->pCopy = (Abc_Obj_t *)Supp_ManFetchEntry( p, 0, Abc_ObjFanoutNum(pObj) );
00378             continue;
00379         }
00380         assert( 0 );
00381     }
00382     Vec_PtrFree( vNodes );
00383 //printf( "Memory usage = %d Mb.\n", Vec_PtrSize(p->vMemory) * p->nChunkSize / (1<<20) );
00384     Supp_ManStop( p );
00385     // sort supports by size
00386     Vec_VecSort( (Vec_Vec_t *)vSupports, 1 );
00387     // clear the number of PIs/POs
00388     Abc_NtkForEachCi( pNtk, pObj, i )
00389         pObj->pNext = NULL;
00390     Abc_NtkForEachCo( pNtk, pObj, i )
00391         pObj->pNext = NULL;
00392 /*
00393     Vec_PtrForEachEntry( vSupports, vSupp, i )
00394         printf( "%d ", Vec_IntSize(vSupp) );
00395     printf( "\n" );
00396 */
00397     return vSupports;
00398 }
00399 
00400 
00412 Vec_Ptr_t * Abc_NtkComputeSupportsNaive( Abc_Ntk_t * pNtk )
00413 {
00414     Vec_Ptr_t * vSupp, * vSupports;
00415     Vec_Int_t * vSuppI;
00416     Abc_Obj_t * pObj, * pTemp;
00417     int i, k;
00418     // set the PI numbers
00419     Abc_NtkForEachCi( pNtk, pObj, i )
00420         pObj->pNext = (void *)i;
00421     // save the CI numbers
00422     vSupports = Vec_PtrAlloc( Abc_NtkCoNum(pNtk) );
00423     Abc_NtkForEachCo( pNtk, pObj, i )
00424     {
00425         if ( !Abc_ObjIsNode(Abc_ObjFanin0(pObj)) )
00426             continue;
00427         vSupp = Abc_NtkNodeSupport( pNtk, &pObj, 1 );
00428         vSuppI = (Vec_Int_t *)vSupp;
00429         Vec_PtrForEachEntry( vSupp, pTemp, k )
00430             Vec_IntWriteEntry( vSuppI, k, (int)pTemp->pNext );
00431         Vec_IntSort( vSuppI, 0 );
00432         // append the number of this output
00433         Vec_IntPush( vSuppI, i );
00434         // save the support in the vector
00435         Vec_PtrPush( vSupports, vSuppI );
00436     }
00437     // clean the CI numbers
00438     Abc_NtkForEachCi( pNtk, pObj, i )
00439         pObj->pNext = NULL;
00440     // sort supports by size
00441     Vec_VecSort( (Vec_Vec_t *)vSupports, 1 );
00442 /*
00443     Vec_PtrForEachEntry( vSupports, vSuppI, i )
00444         printf( "%d ", Vec_IntSize(vSuppI) );
00445     printf( "\n" );
00446 */
00447     return vSupports;
00448 }
00449 
00461 unsigned * Abc_NtkSuppCharStart( Vec_Int_t * vOne, int nPis )
00462 {
00463     unsigned * pBuffer;
00464     int i, Entry;
00465     int nWords = Abc_BitWordNum(nPis);
00466     pBuffer = ALLOC( unsigned, nWords );
00467     memset( pBuffer, 0, sizeof(unsigned) * nWords );
00468     Vec_IntForEachEntry( vOne, Entry, i )
00469     {
00470         assert( Entry < nPis );
00471         Abc_InfoSetBit( pBuffer, Entry );
00472     }
00473     return pBuffer;
00474 }
00475 
00487 void Abc_NtkSuppCharAdd( unsigned * pBuffer, Vec_Int_t * vOne, int nPis )
00488 {
00489     int i, Entry;
00490     Vec_IntForEachEntry( vOne, Entry, i )
00491     {
00492         assert( Entry < nPis );
00493         Abc_InfoSetBit( pBuffer, Entry );
00494     }
00495 }
00496 
00508 int Abc_NtkSuppCharCommon( unsigned * pBuffer, Vec_Int_t * vOne )
00509 {
00510     int i, Entry, nCommon = 0;
00511     Vec_IntForEachEntry( vOne, Entry, i )
00512         nCommon += Abc_InfoHasBit(pBuffer, Entry);
00513     return nCommon;
00514 }
00515 
00527 int Abc_NtkPartitionSmartFindPart( Vec_Ptr_t * vPartSuppsAll, Vec_Ptr_t * vPartsAll, Vec_Ptr_t * vPartSuppsChar, int nSuppSizeLimit, Vec_Int_t * vOne )
00528 {
00529 /*
00530     Vec_Int_t * vPartSupp, * vPart;
00531     double Attract, Repulse, Cost, CostBest;
00532     int i, nCommon, iBest;
00533     iBest = -1;
00534     CostBest = 0.0;
00535     Vec_PtrForEachEntry( vPartSuppsAll, vPartSupp, i )
00536     {
00537         vPart = Vec_PtrEntry( vPartsAll, i );
00538         if ( nPartSizeLimit > 0 && Vec_IntSize(vPart) >= nPartSizeLimit )
00539             continue;
00540         nCommon = Vec_IntTwoCountCommon( vPartSupp, vOne );
00541         if ( nCommon == 0 )
00542             continue;
00543         if ( nCommon == Vec_IntSize(vOne) )
00544             return i;
00545         Attract = 1.0 * nCommon / Vec_IntSize(vOne);
00546         if ( Vec_IntSize(vPartSupp) < 100 )
00547             Repulse = 1.0;
00548         else
00549             Repulse = log10( Vec_IntSize(vPartSupp) / 10.0 );
00550         Cost = pow( Attract, pow(Repulse, 5.0) );
00551         if ( CostBest < Cost )
00552         {
00553             CostBest = Cost;
00554             iBest = i;
00555         }
00556     }
00557     if ( CostBest < 0.6 )
00558         return -1;
00559     return iBest;
00560 */
00561 
00562     Vec_Int_t * vPartSupp;//, * vPart;
00563     int Attract, Repulse, Value, ValueBest;
00564     int i, nCommon, iBest;
00565 //    int nCommon2;
00566     iBest = -1;
00567     ValueBest = 0;
00568     Vec_PtrForEachEntry( vPartSuppsAll, vPartSupp, i )
00569     {
00570         // skip partitions with too many outputs
00571 //        vPart = Vec_PtrEntry( vPartsAll, i );
00572 //        if ( nSuppSizeLimit > 0 && Vec_IntSize(vPart) >= nSuppSizeLimit )
00573 //            continue;
00574         // find the number of common variables between this output and the partitions
00575 //        nCommon2 = Vec_IntTwoCountCommon( vPartSupp, vOne );
00576         nCommon = Abc_NtkSuppCharCommon( Vec_PtrEntry(vPartSuppsChar, i), vOne );
00577 //        assert( nCommon2 == nCommon );
00578         // if no common variables, continue searching
00579         if ( nCommon == 0 )
00580             continue;
00581         // if all variables are common, the best partition if found
00582         if ( nCommon == Vec_IntSize(vOne) )
00583             return i;
00584         // skip partitions whose size exceeds the limit
00585         if ( nSuppSizeLimit > 0 && Vec_IntSize(vPartSupp) >= 2 * nSuppSizeLimit )
00586             continue;
00587         // figure out might be the good partition for this one
00588         Attract = 1000 * nCommon / Vec_IntSize(vOne);
00589         if ( Vec_IntSize(vPartSupp) < 100 )
00590             Repulse = 1;
00591         else
00592             Repulse = 1+Extra_Base2Log(Vec_IntSize(vPartSupp)-100);
00593         Value = Attract/Repulse;
00594         if ( ValueBest < Value )
00595         {
00596             ValueBest = Value;
00597             iBest = i;
00598         }
00599     }
00600     if ( ValueBest < 75 )
00601         return -1;
00602     return iBest;
00603 }
00604 
00616 void Abc_NtkPartitionPrint( Abc_Ntk_t * pNtk, Vec_Ptr_t * vPartsAll, Vec_Ptr_t * vPartSuppsAll )
00617 {
00618     Vec_Int_t * vOne;
00619     int i, nOutputs, Counter;
00620 
00621     Counter = 0;
00622     Vec_PtrForEachEntry( vPartSuppsAll, vOne, i )
00623     {
00624         nOutputs = Vec_IntSize(Vec_PtrEntry(vPartsAll, i));
00625         printf( "%d=(%d,%d) ", i, Vec_IntSize(vOne), nOutputs );
00626         Counter += nOutputs;
00627         if ( i == Vec_PtrSize(vPartsAll) - 1 )
00628             break;
00629     }
00630 //    assert( Counter == Abc_NtkCoNum(pNtk) );
00631     printf( "\nTotal = %d. Outputs = %d.\n", Counter, Abc_NtkCoNum(pNtk) );
00632 }
00633 
00645 void Abc_NtkPartitionCompact( Vec_Ptr_t * vPartsAll, Vec_Ptr_t * vPartSuppsAll, int nSuppSizeLimit )
00646 {
00647     Vec_Int_t * vOne, * vPart, * vPartSupp, * vTemp;
00648     int i, iPart;
00649 
00650     if ( nSuppSizeLimit == 0 )
00651         nSuppSizeLimit = 200;
00652 
00653     // pack smaller partitions into larger blocks
00654     iPart = 0;
00655     vPart = vPartSupp = NULL;
00656     Vec_PtrForEachEntry( vPartSuppsAll, vOne, i )
00657     {
00658         if ( Vec_IntSize(vOne) < nSuppSizeLimit )
00659         {
00660             if ( vPartSupp == NULL )
00661             {
00662                 assert( vPart == NULL );
00663                 vPartSupp = Vec_IntDup(vOne);
00664                 vPart = Vec_PtrEntry(vPartsAll, i);
00665             }
00666             else
00667             {
00668                 vPartSupp = Vec_IntTwoMerge( vTemp = vPartSupp, vOne );
00669                 Vec_IntFree( vTemp );
00670                 vPart = Vec_IntTwoMerge( vTemp = vPart, Vec_PtrEntry(vPartsAll, i) );
00671                 Vec_IntFree( vTemp );
00672                 Vec_IntFree( Vec_PtrEntry(vPartsAll, i) );
00673             }
00674             if ( Vec_IntSize(vPartSupp) < nSuppSizeLimit )
00675                 continue;
00676         }
00677         else
00678             vPart = Vec_PtrEntry(vPartsAll, i);
00679         // add the partition 
00680         Vec_PtrWriteEntry( vPartsAll, iPart, vPart );  
00681         vPart = NULL;
00682         if ( vPartSupp ) 
00683         {
00684             Vec_IntFree( Vec_PtrEntry(vPartSuppsAll, iPart) );
00685             Vec_PtrWriteEntry( vPartSuppsAll, iPart, vPartSupp );  
00686             vPartSupp = NULL;
00687         }
00688         iPart++;
00689     }
00690     // add the last one
00691     if ( vPart )
00692     {
00693         Vec_PtrWriteEntry( vPartsAll, iPart, vPart );  
00694         vPart = NULL;
00695 
00696         assert( vPartSupp != NULL );
00697         Vec_IntFree( Vec_PtrEntry(vPartSuppsAll, iPart) );
00698         Vec_PtrWriteEntry( vPartSuppsAll, iPart, vPartSupp );  
00699         vPartSupp = NULL;
00700         iPart++;
00701     }
00702     Vec_PtrShrink( vPartsAll, iPart );
00703     Vec_PtrShrink( vPartsAll, iPart );
00704 }
00705 
00717 Vec_Ptr_t * Abc_NtkPartitionSmart( Abc_Ntk_t * pNtk, int nSuppSizeLimit, int fVerbose )
00718 {
00719     ProgressBar * pProgress;
00720     Vec_Ptr_t * vPartSuppsChar;
00721     Vec_Ptr_t * vSupps, * vPartsAll, * vPartsAll2, * vPartSuppsAll;
00722     Vec_Int_t * vOne, * vPart, * vPartSupp, * vTemp;
00723     int i, iPart, iOut, clk, clk2, timeFind = 0;
00724 
00725     // compute the supports for all outputs
00726 clk = clock();
00727 //    vSupps = Abc_NtkComputeSupportsNaive( pNtk );
00728     vSupps = Abc_NtkComputeSupportsSmart( pNtk );
00729 if ( fVerbose )
00730 {
00731 PRT( "Supps", clock() - clk );
00732 }
00733     // start char-based support representation
00734     vPartSuppsChar = Vec_PtrAlloc( 1000 );
00735 
00736     // create partitions
00737 clk = clock();
00738     vPartsAll = Vec_PtrAlloc( 256 );
00739     vPartSuppsAll = Vec_PtrAlloc( 256 );
00740     pProgress = Extra_ProgressBarStart( stdout, Vec_PtrSize(vSupps) );
00741     Vec_PtrForEachEntry( vSupps, vOne, i )
00742     {
00743         Extra_ProgressBarUpdate( pProgress, i, NULL );
00744 //        if ( i % 1000 == 0 )
00745 //            printf( "CIs = %6d. COs = %6d. Processed = %6d (out of %6d). Parts = %6d.\r", 
00746 //                Abc_NtkCiNum(pNtk), Abc_NtkCoNum(pNtk), i, Vec_PtrSize(vSupps), Vec_PtrSize(vPartsAll) ); 
00747         // get the output number
00748         iOut = Vec_IntPop(vOne);
00749         // find closely matching part
00750 clk2 = clock();
00751         iPart = Abc_NtkPartitionSmartFindPart( vPartSuppsAll, vPartsAll, vPartSuppsChar, nSuppSizeLimit, vOne );
00752 timeFind += clock() - clk2;
00753         if ( iPart == -1 )
00754         {
00755             // create new partition
00756             vPart = Vec_IntAlloc( 32 );
00757             Vec_IntPush( vPart, iOut );
00758             // create new partition support
00759             vPartSupp = Vec_IntDup( vOne );
00760             // add this partition and its support
00761             Vec_PtrPush( vPartsAll, vPart );
00762             Vec_PtrPush( vPartSuppsAll, vPartSupp );
00763 
00764             Vec_PtrPush( vPartSuppsChar, Abc_NtkSuppCharStart(vOne, Abc_NtkCiNum(pNtk)) );
00765         }
00766         else
00767         {
00768             // add output to this partition
00769             vPart = Vec_PtrEntry( vPartsAll, iPart );
00770             Vec_IntPush( vPart, iOut );
00771             // merge supports
00772             vPartSupp = Vec_PtrEntry( vPartSuppsAll, iPart );
00773             vPartSupp = Vec_IntTwoMerge( vTemp = vPartSupp, vOne );
00774             Vec_IntFree( vTemp );
00775             // reinsert new support
00776             Vec_PtrWriteEntry( vPartSuppsAll, iPart, vPartSupp );
00777 
00778             Abc_NtkSuppCharAdd( Vec_PtrEntry(vPartSuppsChar, iPart), vOne, Abc_NtkCiNum(pNtk) );
00779         }
00780     }
00781     Extra_ProgressBarStop( pProgress );
00782 
00783     // stop char-based support representation
00784     Vec_PtrForEachEntry( vPartSuppsChar, vTemp, i )
00785         free( vTemp );
00786     Vec_PtrFree( vPartSuppsChar );
00787 
00788 //printf( "\n" );
00789 if ( fVerbose )
00790 {
00791 PRT( "Parts", clock() - clk );
00792 //PRT( "Find ", timeFind );
00793 }
00794 
00795 clk = clock();
00796     // remember number of supports
00797     Vec_PtrForEachEntry( vPartSuppsAll, vOne, i )
00798         Vec_IntPush( vOne, i );
00799     // sort the supports in the decreasing order
00800     Vec_VecSort( (Vec_Vec_t *)vPartSuppsAll, 1 );
00801     // reproduce partitions
00802     vPartsAll2 = Vec_PtrAlloc( 256 );
00803     Vec_PtrForEachEntry( vPartSuppsAll, vOne, i )
00804         Vec_PtrPush( vPartsAll2, Vec_PtrEntry(vPartsAll, Vec_IntPop(vOne)) );
00805     Vec_PtrFree( vPartsAll );
00806     vPartsAll = vPartsAll2;
00807 
00808     // compact small partitions
00809 //    Abc_NtkPartitionPrint( pNtk, vPartsAll, vPartSuppsAll );
00810     Abc_NtkPartitionCompact( vPartsAll, vPartSuppsAll, nSuppSizeLimit );
00811 
00812 if ( fVerbose )
00813 {
00814 PRT( "Comps", clock() - clk );
00815 }
00816     if ( fVerbose )
00817     printf( "Created %d partitions.\n", Vec_PtrSize(vPartsAll) );
00818 //    Abc_NtkPartitionPrint( pNtk, vPartsAll, vPartSuppsAll );
00819 
00820     // cleanup
00821     Vec_VecFree( (Vec_Vec_t *)vSupps );
00822     Vec_VecFree( (Vec_Vec_t *)vPartSuppsAll );
00823 /*
00824     // converts from intergers to nodes
00825     Vec_PtrForEachEntry( vPartsAll, vPart, iPart )
00826     {
00827         vPartPtr = Vec_PtrAlloc( Vec_IntSize(vPart) );
00828         Vec_IntForEachEntry( vPart, iOut, i )
00829             Vec_PtrPush( vPartPtr, Abc_NtkCo(pNtk, iOut) );
00830         Vec_IntFree( vPart );
00831         Vec_PtrWriteEntry( vPartsAll, iPart, vPartPtr );
00832     }
00833 */
00834     return vPartsAll;
00835 }
00836 
00848 Vec_Ptr_t * Abc_NtkPartitionNaive( Abc_Ntk_t * pNtk, int nPartSize )
00849 {
00850     Vec_Ptr_t * vParts;
00851     Abc_Obj_t * pObj;
00852     int nParts, i;
00853     nParts = (Abc_NtkCoNum(pNtk) / nPartSize) + ((Abc_NtkCoNum(pNtk) % nPartSize) > 0);
00854     vParts = (Vec_Ptr_t *)Vec_VecStart( nParts );
00855     Abc_NtkForEachCo( pNtk, pObj, i )
00856         Vec_IntPush( Vec_PtrEntry(vParts, i / nPartSize), i );
00857     return vParts;
00858 }
00859 
00871 void Abc_NtkConvertCos( Abc_Ntk_t * pNtk, Vec_Int_t * vOuts, Vec_Ptr_t * vOutsPtr )
00872 {
00873     int Out, i;
00874     Vec_PtrClear( vOutsPtr );
00875     Vec_IntForEachEntry( vOuts, Out, i )
00876         Vec_PtrPush( vOutsPtr, Abc_NtkCo(pNtk, Out) );
00877 }
00878 
00890 Abc_Obj_t * Abc_NtkPartStitchFindRepr_rec( Vec_Ptr_t * vEquiv, Abc_Obj_t * pObj )
00891 {
00892     Abc_Obj_t * pRepr;
00893     pRepr = Vec_PtrEntry( vEquiv, pObj->Id );
00894     if ( pRepr == NULL || pRepr == pObj )
00895         return pObj;
00896     return Abc_NtkPartStitchFindRepr_rec( vEquiv, pRepr );
00897 }
00898 
00910 static inline Abc_Obj_t * Abc_NtkPartStitchCopy0( Vec_Ptr_t * vEquiv, Abc_Obj_t * pObj )
00911 {
00912     Abc_Obj_t * pFan = Abc_ObjFanin0( pObj );
00913     Abc_Obj_t * pRepr = Abc_NtkPartStitchFindRepr_rec( vEquiv, pFan );
00914     return Abc_ObjNotCond( pRepr->pCopy, pRepr->fPhase ^ pFan->fPhase ^ Abc_ObjFaninC1(pObj) );
00915 }
00916 static inline Abc_Obj_t * Abc_NtkPartStitchCopy1( Vec_Ptr_t * vEquiv, Abc_Obj_t * pObj )
00917 {
00918     Abc_Obj_t * pFan = Abc_ObjFanin1( pObj );
00919     Abc_Obj_t * pRepr = Abc_NtkPartStitchFindRepr_rec( vEquiv, pFan );
00920     return Abc_ObjNotCond( pRepr->pCopy, pRepr->fPhase ^ pFan->fPhase ^ Abc_ObjFaninC1(pObj) );
00921 }
00922 
00934 static inline Hop_Obj_t * Hop_ObjChild0Next( Abc_Obj_t * pObj ) { return Hop_NotCond( (Hop_Obj_t *)Abc_ObjFanin0(pObj)->pNext, Abc_ObjFaninC0(pObj) ); }
00935 static inline Hop_Obj_t * Hop_ObjChild1Next( Abc_Obj_t * pObj ) { return Hop_NotCond( (Hop_Obj_t *)Abc_ObjFanin1(pObj)->pNext, Abc_ObjFaninC1(pObj) ); }
00936 
00937 
00949 Hop_Man_t * Abc_NtkPartStartHop( Abc_Ntk_t * pNtk )
00950 {
00951     Hop_Man_t * pMan;
00952     Abc_Obj_t * pObj;
00953     int i;
00954     // start the HOP package
00955     pMan = Hop_ManStart();
00956     pMan->vObjs = Vec_PtrAlloc( Abc_NtkObjNumMax(pNtk) + 1  );
00957     Vec_PtrPush( pMan->vObjs, Hop_ManConst1(pMan) );
00958     // map constant node and PIs
00959     Abc_AigConst1(pNtk)->pNext = (Abc_Obj_t *)Hop_ManConst1(pMan);
00960     Abc_NtkForEachCi( pNtk, pObj, i )
00961         pObj->pNext = (Abc_Obj_t *)Hop_ObjCreatePi(pMan);
00962     // map the internal nodes
00963     Abc_AigForEachAnd( pNtk, pObj, i )
00964     {
00965         pObj->pNext = (Abc_Obj_t *)Hop_And( pMan, Hop_ObjChild0Next(pObj), Hop_ObjChild1Next(pObj) );
00966         assert( !Abc_ObjIsComplement(pObj->pNext) );
00967     }
00968     // set the choice nodes
00969     Abc_AigForEachAnd( pNtk, pObj, i )
00970     {
00971         if ( pObj->pCopy )
00972             ((Hop_Obj_t *)pObj->pNext)->pData = pObj->pCopy->pNext;
00973     }
00974     // transfer the POs
00975     Abc_NtkForEachCo( pNtk, pObj, i )
00976         Hop_ObjCreatePo( pMan, Hop_ObjChild0Next(pObj) );
00977     // check the new manager
00978     if ( !Hop_ManCheck(pMan) )
00979         printf( "Abc_NtkPartStartHop: HOP manager check has failed.\n" );
00980     return pMan;
00981 }
00982 
00994 Abc_Ntk_t * Abc_NtkPartStitchChoices( Abc_Ntk_t * pNtk, Vec_Ptr_t * vParts )
00995 {
00996     extern Abc_Ntk_t * Abc_NtkHopRemoveLoops( Abc_Ntk_t * pNtk, Hop_Man_t * pMan );
00997 
00998     Hop_Man_t * pMan;
00999     Vec_Ptr_t * vNodes;
01000     Abc_Ntk_t * pNtkNew, * pNtkTemp;
01001     Abc_Obj_t * pObj, * pFanin;
01002     int i, k, iNodeId;
01003 
01004     // start a new network similar to the original one
01005     assert( Abc_NtkIsStrash(pNtk) );
01006     pNtkNew = Abc_NtkStartFrom( pNtk, ABC_NTK_STRASH, ABC_FUNC_AIG );
01007 
01008     // annotate parts to point to the new network
01009     Vec_PtrForEachEntry( vParts, pNtkTemp, i )
01010     {
01011         assert( Abc_NtkIsStrash(pNtkTemp) );
01012         Abc_NtkCleanCopy( pNtkTemp );
01013 
01014         // map the CI nodes
01015         Abc_AigConst1(pNtkTemp)->pCopy = Abc_AigConst1(pNtkNew);
01016         Abc_NtkForEachCi( pNtkTemp, pObj, k )
01017         {
01018             iNodeId = Nm_ManFindIdByNameTwoTypes( pNtkNew->pManName, Abc_ObjName(pObj), ABC_OBJ_PI, ABC_OBJ_BO );
01019             if ( iNodeId == -1 )
01020             {
01021                 printf( "Cannot find CI node %s in the original network.\n", Abc_ObjName(pObj) );
01022                 return NULL;
01023             }
01024             pObj->pCopy = Abc_NtkObj( pNtkNew, iNodeId );
01025         }
01026 
01027         // add the internal nodes while saving representatives
01028         vNodes = Abc_AigDfs( pNtkTemp, 1, 0 );
01029         Vec_PtrForEachEntry( vNodes, pObj, k )
01030         {
01031             pObj->pCopy = Abc_AigAnd( pNtkNew->pManFunc, Abc_ObjChild0Copy(pObj), Abc_ObjChild1Copy(pObj) );
01032             assert( !Abc_ObjIsComplement(pObj->pCopy) );
01033             if ( Abc_AigNodeIsChoice(pObj) )
01034                 for ( pFanin = pObj->pData; pFanin; pFanin = pFanin->pData )
01035                     pFanin->pCopy->pCopy = pObj->pCopy;
01036         }
01037         Vec_PtrFree( vNodes );
01038 
01039         // map the CO nodes
01040         Abc_NtkForEachCo( pNtkTemp, pObj, k )
01041         {
01042             iNodeId = Nm_ManFindIdByNameTwoTypes( pNtkNew->pManName, Abc_ObjName(pObj), ABC_OBJ_PO, ABC_OBJ_BI );
01043             if ( iNodeId == -1 )
01044             {
01045                 printf( "Cannot find CO node %s in the original network.\n", Abc_ObjName(pObj) );
01046                 return NULL;
01047             }
01048             pObj->pCopy = Abc_NtkObj( pNtkNew, iNodeId );
01049             Abc_ObjAddFanin( pObj->pCopy, Abc_ObjChild0Copy(pObj) );
01050         }
01051     }
01052 
01053     // connect the remaining POs
01054 /*
01055     Abc_AigConst1(pNtk)->pCopy = Abc_AigConst1(pNtkNew);
01056     Abc_NtkForEachCi( pNtk, pObj, i )
01057         pObj->pCopy = Abc_NtkCi( pNtkNew, i );
01058     Abc_NtkForEachCo( pNtk, pObj, i )
01059         pObj->pCopy = Abc_NtkCo( pNtkNew, i );
01060 */
01061     Abc_NtkForEachCo( pNtk, pObj, i )
01062     {
01063         if ( Abc_ObjFaninNum(pObj->pCopy) == 0 )
01064             Abc_ObjAddFanin( pObj->pCopy, Abc_ObjChild0Copy(pObj) );
01065     }
01066 
01067     // transform into the HOP manager
01068     pMan = Abc_NtkPartStartHop( pNtkNew );
01069     pNtkNew = Abc_NtkHopRemoveLoops( pNtkTemp = pNtkNew, pMan );
01070     Abc_NtkDelete( pNtkTemp );
01071 
01072     // check correctness of the new network
01073     if ( !Abc_NtkCheck( pNtkNew ) )
01074     {
01075         printf( "Abc_NtkPartStitchChoices: The network check has failed.\n" );
01076         Abc_NtkDelete( pNtkNew );
01077         return NULL;
01078     }
01079     return pNtkNew;
01080 }
01081 
01093 Abc_Ntk_t * Abc_NtkFraigPartitioned( Vec_Ptr_t * vStore, void * pParams )
01094 {
01095     extern int Cmd_CommandExecute( void * pAbc, char * sCommand );
01096     extern void * Abc_FrameGetGlobalFrame();
01097 
01098     Vec_Ptr_t * vParts, * vFraigs, * vOnePtr;
01099     Vec_Int_t * vOne;
01100     Abc_Ntk_t * pNtk, * pNtk2, * pNtkAig, * pNtkFraig;
01101     int i, k;
01102 
01103     // perform partitioning
01104     pNtk = Vec_PtrEntry( vStore, 0 );
01105     assert( Abc_NtkIsStrash(pNtk) );
01106 //    vParts = Abc_NtkPartitionNaive( pNtk, 20 );
01107     vParts = Abc_NtkPartitionSmart( pNtk, 300, 0 );
01108 
01109     Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "unset progressbar" );
01110 
01111     // fraig each partition
01112     vOnePtr = Vec_PtrAlloc( 1000 );
01113     vFraigs = Vec_PtrAlloc( Vec_PtrSize(vParts) );
01114     Vec_PtrForEachEntry( vParts, vOne, i )
01115     {
01116         // start the partition 
01117         Abc_NtkConvertCos( pNtk, vOne, vOnePtr );
01118         pNtkAig = Abc_NtkCreateConeArray( pNtk, vOnePtr, 0 );
01119         // add nodes to the partition
01120         Vec_PtrForEachEntryStart( vStore, pNtk2, k, 1 )
01121         {
01122             Abc_NtkConvertCos( pNtk2, vOne, vOnePtr );
01123             Abc_NtkAppendToCone( pNtkAig, pNtk2, vOnePtr );
01124         }
01125         printf( "Fraiging part %4d  (out of %4d)  PI = %5d. PO = %5d. And = %6d. Lev = %4d.\r", 
01126             i+1, Vec_PtrSize(vParts), Abc_NtkPiNum(pNtkAig), Abc_NtkPoNum(pNtkAig), 
01127             Abc_NtkNodeNum(pNtkAig), Abc_AigLevel(pNtkAig) );
01128         // fraig the partition
01129         pNtkFraig = Abc_NtkFraig( pNtkAig, pParams, 1, 0 );
01130         Vec_PtrPush( vFraigs, pNtkFraig );
01131         Abc_NtkDelete( pNtkAig );
01132     }
01133     printf( "                                                                                          \r" );
01134     Vec_VecFree( (Vec_Vec_t *)vParts );
01135 
01136     Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "set progressbar" );
01137 
01138     // derive the final network
01139     pNtkFraig = Abc_NtkPartStitchChoices( pNtk, vFraigs );
01140     Vec_PtrForEachEntry( vFraigs, pNtkAig, i )
01141         Abc_NtkDelete( pNtkAig );
01142     Vec_PtrFree( vFraigs );
01143     Vec_PtrFree( vOnePtr );
01144     return pNtkFraig;
01145 }
01146 
01158 void Abc_NtkFraigPartitionedTime( Abc_Ntk_t * pNtk, void * pParams )
01159 {
01160     extern int Cmd_CommandExecute( void * pAbc, char * sCommand );
01161     extern void * Abc_FrameGetGlobalFrame();
01162 
01163     Vec_Ptr_t * vParts, * vFraigs, * vOnePtr;
01164     Vec_Int_t * vOne;
01165     Abc_Ntk_t * pNtkAig, * pNtkFraig;
01166     int i;
01167     int clk = clock();
01168 
01169     // perform partitioning
01170     assert( Abc_NtkIsStrash(pNtk) );
01171 //    vParts = Abc_NtkPartitionNaive( pNtk, 20 );
01172     vParts = Abc_NtkPartitionSmart( pNtk, 300, 0 );
01173 
01174     Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "unset progressbar" );
01175 
01176     // fraig each partition
01177     vOnePtr = Vec_PtrAlloc( 1000 );
01178     vFraigs = Vec_PtrAlloc( Vec_PtrSize(vParts) );
01179     Vec_PtrForEachEntry( vParts, vOne, i )
01180     {
01181         Abc_NtkConvertCos( pNtk, vOne, vOnePtr );
01182         pNtkAig = Abc_NtkCreateConeArray( pNtk, vOnePtr, 0 );
01183         pNtkFraig = Abc_NtkFraig( pNtkAig, pParams, 0, 0 );
01184         Vec_PtrPush( vFraigs, pNtkFraig );
01185         Abc_NtkDelete( pNtkAig );
01186 
01187         printf( "Finished part %5d (out of %5d)\r", i+1, Vec_PtrSize(vParts) );
01188     }
01189     Vec_VecFree( (Vec_Vec_t *)vParts );
01190 
01191     Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "set progressbar" );
01192 
01193     // derive the final network
01194     Vec_PtrForEachEntry( vFraigs, pNtkAig, i )
01195         Abc_NtkDelete( pNtkAig );
01196     Vec_PtrFree( vFraigs );
01197     Vec_PtrFree( vOnePtr );
01198     PRT( "Partitioned fraiging time", clock() - clk );
01199 }
01200 
01204 
01205