src/aig/aig/aigPart.c File Reference

#include "aig.h"
Include dependency graph for aigPart.c:

Go to the source code of this file.

Data Structures

struct  Part_Man_t_
struct  Part_One_t_

Typedefs

typedef struct Part_Man_t_ Part_Man_t
typedef struct Part_One_t_ Part_One_t

Functions

static int Part_SizeType (int nSize, int nStepSize)
static char * Part_OneNext (char *pPart)
static void Part_OneSetNext (char *pPart, char *pNext)
Part_Man_t * Part_ManStart (int nChunkSize, int nStepSize)
void Part_ManStop (Part_Man_t *p)
char * Part_ManFetch (Part_Man_t *p, int nSize)
void Part_ManRecycle (Part_Man_t *p, char *pMemory, int nSize)
static Part_One_t * Part_ManFetchEntry (Part_Man_t *p, int nWords, int nRefs)
static void Part_ManRecycleEntry (Part_Man_t *p, Part_One_t *pEntry)
Part_One_t * Part_ManMergeEntry (Part_Man_t *pMan, Part_One_t *p1, Part_One_t *p2, int nRefs)
Vec_Int_t * Part_ManTransferEntry (Part_One_t *p)
Vec_Ptr_t * Aig_ManSupports (Aig_Man_t *pMan)
unsigned * Aig_ManSuppCharStart (Vec_Int_t *vOne, int nPis)
void Aig_ManSuppCharAdd (unsigned *pBuffer, Vec_Int_t *vOne, int nPis)
int Aig_ManSuppCharCommon (unsigned *pBuffer, Vec_Int_t *vOne)
int Aig_ManPartitionSmartFindPart (Vec_Ptr_t *vPartSuppsAll, Vec_Ptr_t *vPartsAll, Vec_Ptr_t *vPartSuppsBit, int nSuppSizeLimit, Vec_Int_t *vOne)
void Aig_ManPartitionPrint (Aig_Man_t *p, Vec_Ptr_t *vPartsAll, Vec_Ptr_t *vPartSuppsAll)
void Aig_ManPartitionCompact (Vec_Ptr_t *vPartsAll, Vec_Ptr_t *vPartSuppsAll, int nSuppSizeLimit)
Vec_Ptr_t * Aig_ManPartitionSmart (Aig_Man_t *p, int nSuppSizeLimit, int fVerbose, Vec_Ptr_t **pvPartSupps)
Vec_Ptr_t * Aig_ManPartitionNaive (Aig_Man_t *p, int nPartSize)
Aig_Obj_t * Aig_ManDupPart_rec (Aig_Man_t *pNew, Aig_Man_t *pOld, Aig_Obj_t *pObj, Vec_Int_t *vSuppMap)
Vec_Ptr_t * Aig_ManDupPart (Aig_Man_t *pNew, Aig_Man_t *pOld, Vec_Int_t *vPart, Vec_Int_t *vSuppMap, int fInverse)
Vec_Ptr_t * Aig_ManMiterPartitioned (Aig_Man_t *p1, Aig_Man_t *p2, int nPartSize)
Aig_Man_t * Aig_ManChoicePartitioned (Vec_Ptr_t *vAigs, int nPartSize)

Typedef Documentation

typedef struct Part_Man_t_ Part_Man_t

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

FileName [aigPart.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [AIG package.]

Synopsis [AIG partitioning package.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

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

] DECLARATIONS ///

Definition at line 27 of file aigPart.c.

typedef struct Part_One_t_ Part_One_t

Definition at line 38 of file aigPart.c.

Function Documentation

Aig_Man_t* Aig_ManChoicePartitioned ( Vec_Ptr_t *  vAigs,
int  nPartSize 
)

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

Synopsis [Performs partitioned choice computation.]

Description [Assumes that each output in the second AIG cannot have more supp vars than the same output in the first AIG.]

SideEffects []

SeeAlso []

Definition at line 872 of file aigPart.c.

00873 {
00874     extern int Cmd_CommandExecute( void * pAbc, char * sCommand );
00875     extern void * Abc_FrameGetGlobalFrame();
00876     extern Aig_Man_t * Fra_FraigChoice( Aig_Man_t * pManAig, int nConfMax );
00877 
00878     Vec_Ptr_t * vOutsTotal, * vOuts;
00879     Aig_Man_t * pAigTotal, * pAigPart, * pAig;
00880     Vec_Int_t * vPart, * vPartSupp;
00881     Vec_Ptr_t * vParts;
00882     Aig_Obj_t * pObj;
00883     void ** ppData;
00884     int i, k, m;
00885 
00886     // partition the first AIG in the array
00887     assert( Vec_PtrSize(vAigs) > 1 );
00888     pAig = Vec_PtrEntry( vAigs, 0 );
00889     vParts = Aig_ManPartitionSmart( pAig, nPartSize, 0, NULL );
00890 
00891     // start the total fraiged AIG
00892     pAigTotal = Aig_ManStartFrom( pAig );
00893     Aig_ManReprStart( pAigTotal, Vec_PtrSize(vAigs) * Aig_ManObjNumMax(pAig) + 10000 );
00894     vOutsTotal = Vec_PtrStart( Aig_ManPoNum(pAig) );
00895 
00896     // set the PI numbers
00897     Vec_PtrForEachEntry( vAigs, pAig, i )
00898         Aig_ManForEachPi( pAig, pObj, k )
00899             pObj->pNext = (Aig_Obj_t *)(long)k;
00900 
00901     Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "unset progressbar" );
00902 
00903     // create the total fraiged AIG
00904     vPartSupp = Vec_IntAlloc( 100 ); // maps part PI num into total PI num
00905     Vec_PtrForEachEntry( vParts, vPart, i )
00906     {
00907         // derive the partition AIG
00908         pAigPart = Aig_ManStart( 5000 );
00909 //        pAigPart->pName = Extra_UtilStrsav( pAigPart->pName );
00910         Vec_IntClear( vPartSupp );
00911         Vec_PtrForEachEntry( vAigs, pAig, k )
00912         {
00913             vOuts = Aig_ManDupPart( pAigPart, pAig, vPart, vPartSupp, 0 );
00914             if ( k == 0 )
00915             {
00916                 Vec_PtrForEachEntry( vOuts, pObj, m )
00917                     Aig_ObjCreatePo( pAigPart, pObj );
00918             }
00919             Vec_PtrFree( vOuts );
00920         }
00921         // derive the total AIG from the partitioned AIG
00922         vOuts = Aig_ManDupPart( pAigTotal, pAigPart, vPart, vPartSupp, 1 );
00923         // add to the outputs
00924         Vec_PtrForEachEntry( vOuts, pObj, k )
00925         {
00926             assert( Vec_PtrEntry( vOutsTotal, Vec_IntEntry(vPart,k) ) == NULL );
00927             Vec_PtrWriteEntry( vOutsTotal, Vec_IntEntry(vPart,k), pObj );
00928         }
00929         Vec_PtrFree( vOuts );
00930         // store contents of pData pointers
00931         ppData = ALLOC( void *, Aig_ManObjNumMax(pAigPart) );
00932         Aig_ManForEachObj( pAigPart, pObj, k )
00933             ppData[k] = pObj->pData;
00934         // report the process
00935         printf( "Part %4d  (out of %4d)  PI = %5d. PO = %5d. And = %6d. Lev = %4d.\r", 
00936             i+1, Vec_PtrSize(vParts), Aig_ManPiNum(pAigPart), Aig_ManPoNum(pAigPart), 
00937             Aig_ManNodeNum(pAigPart), Aig_ManLevelNum(pAigPart) );
00938         // compute equivalence classes (to be stored in pNew->pReprs)
00939         pAig = Fra_FraigChoice( pAigPart, 1000 );
00940         Aig_ManStop( pAig );
00941         // reset the pData pointers
00942         Aig_ManForEachObj( pAigPart, pObj, k )
00943             pObj->pData = ppData[k];
00944         free( ppData );
00945         // transfer representatives to the total AIG
00946         if ( pAigPart->pReprs )
00947             Aig_ManTransferRepr( pAigTotal, pAigPart );
00948         Aig_ManStop( pAigPart );
00949     }
00950     printf( "                                                                                          \r" );
00951     Vec_VecFree( (Vec_Vec_t *)vParts );
00952     Vec_IntFree( vPartSupp );
00953 
00954     Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "set progressbar" );
00955 
00956     // clear the PI numbers
00957     Vec_PtrForEachEntry( vAigs, pAig, i )
00958         Aig_ManForEachPi( pAig, pObj, k )
00959             pObj->pNext = NULL;
00960 /*
00961     // collect the missing outputs (outputs whose driver is not a node)
00962     pAig = Vec_PtrEntry( vAigs, 0 );
00963     Aig_ManConst1(pAig)->pData = Aig_ManConst1(pAigTotal);
00964     Aig_ManForEachPi( pAig, pObj, i )
00965         pAig->pData = Aig_ManPi( pAigTotal, i );
00966     Aig_ManForEachPo( pAig, pObj, i )
00967         if ( !Aig_ObjIsNode(Aig_ObjFanin0(pObj)) )
00968         {
00969             assert( Vec_PtrEntry( vOutsTotal, i ) == NULL );
00970             Vec_PtrWriteEntry( vOutsTotal, i, Aig_ObjChild0Copy(pObj) );
00971         }
00972 */
00973     // add the outputs in the same order
00974     Vec_PtrForEachEntry( vOutsTotal, pObj, i )
00975         Aig_ObjCreatePo( pAigTotal, pObj );
00976     Vec_PtrFree( vOutsTotal );
00977 
00978     // derive the result of choicing
00979     pAig = Aig_ManRehash( pAigTotal );
00980     // create the equivalent nodes lists
00981     Aig_ManMarkValidChoices( pAig );
00982     return pAig;
00983 }

Vec_Ptr_t* Aig_ManDupPart ( Aig_Man_t *  pNew,
Aig_Man_t *  pOld,
Vec_Int_t *  vPart,
Vec_Int_t *  vSuppMap,
int  fInverse 
)

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

Synopsis [Adds internal nodes in the topological order.]

Description [Returns the array of new outputs.]

SideEffects []

SeeAlso []

Definition at line 751 of file aigPart.c.

00752 {
00753     Vec_Ptr_t * vOutsTotal;
00754     Aig_Obj_t * pObj;
00755     int Entry, i;
00756     // create the PIs
00757     Aig_ManIncrementTravId( pOld );
00758     Aig_ManConst1(pOld)->pData = Aig_ManConst1(pNew);
00759     Aig_ObjSetTravIdCurrent( pOld, Aig_ManConst1(pOld) );
00760     if ( !fInverse )
00761     {
00762         Vec_IntForEachEntry( vSuppMap, Entry, i )
00763         {
00764             pObj = Aig_ManPi( pOld, Entry );
00765             pObj->pData = Aig_ManPi( pNew, i );
00766             Aig_ObjSetTravIdCurrent( pOld, pObj );
00767         }
00768     }
00769     else
00770     {
00771         Vec_IntForEachEntry( vSuppMap, Entry, i )
00772         {
00773             pObj = Aig_ManPi( pOld, i );
00774             pObj->pData = Aig_ManPi( pNew, Entry );
00775             Aig_ObjSetTravIdCurrent( pOld, pObj );
00776         }
00777         vSuppMap = NULL; // should not be useful
00778     }
00779     // create the internal nodes
00780     vOutsTotal = Vec_PtrAlloc( Vec_IntSize(vPart) );
00781     if ( !fInverse )
00782     {
00783         Vec_IntForEachEntry( vPart, Entry, i )
00784         {
00785             pObj = Aig_ManPo( pOld, Entry );
00786             Aig_ManDupPart_rec( pNew, pOld, Aig_ObjFanin0(pObj), vSuppMap );
00787             Vec_PtrPush( vOutsTotal, Aig_ObjChild0Copy(pObj) );
00788         }
00789     }
00790     else
00791     {
00792         Aig_ManForEachObj( pOld, pObj, i )
00793         {
00794             if ( Aig_ObjIsPo(pObj) )
00795             {
00796                 Aig_ManDupPart_rec( pNew, pOld, Aig_ObjFanin0(pObj), vSuppMap );
00797                 Vec_PtrPush( vOutsTotal, Aig_ObjChild0Copy(pObj) );
00798             }
00799             else if ( Aig_ObjIsNode(pObj) && pObj->nRefs == 0 )
00800                 Aig_ManDupPart_rec( pNew, pOld, pObj, vSuppMap );
00801             
00802         }
00803     }
00804     return vOutsTotal; 
00805 }

Aig_Obj_t* Aig_ManDupPart_rec ( Aig_Man_t *  pNew,
Aig_Man_t *  pOld,
Aig_Obj_t *  pObj,
Vec_Int_t *  vSuppMap 
)

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

Synopsis [Adds internal nodes in the topological order.]

Description []

SideEffects []

SeeAlso []

Definition at line 722 of file aigPart.c.

00723 {
00724     assert( !Aig_IsComplement(pObj) );
00725     if ( Aig_ObjIsTravIdCurrent(pOld, pObj) )
00726         return pObj->pData;
00727     Aig_ObjSetTravIdCurrent(pOld, pObj);
00728     if ( Aig_ObjIsPi(pObj) )
00729     {
00730         assert( Vec_IntSize(vSuppMap) == Aig_ManPiNum(pNew) );
00731         Vec_IntPush( vSuppMap, (int)(long)pObj->pNext );
00732         return pObj->pData = Aig_ObjCreatePi(pNew);
00733     }
00734     assert( Aig_ObjIsNode(pObj) );
00735     Aig_ManDupPart_rec( pNew, pOld, Aig_ObjFanin0(pObj), vSuppMap );
00736     Aig_ManDupPart_rec( pNew, pOld, Aig_ObjFanin1(pObj), vSuppMap );
00737     return pObj->pData = Aig_And( pNew, Aig_ObjChild0Copy(pObj), Aig_ObjChild1Copy(pObj) );
00738 }

Vec_Ptr_t* Aig_ManMiterPartitioned ( Aig_Man_t *  p1,
Aig_Man_t *  p2,
int  nPartSize 
)

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

Synopsis [Create partitioned miter of the two AIGs.]

Description [Assumes that each output in the second AIG cannot have more supp vars than the same output in the first AIG.]

SideEffects []

SeeAlso []

Definition at line 819 of file aigPart.c.

00820 {
00821     Aig_Man_t * pNew;
00822     Aig_Obj_t * pMiter;
00823     Vec_Ptr_t * vMiters, * vNodes1, * vNodes2;
00824     Vec_Ptr_t * vParts, * vPartSupps;
00825     Vec_Int_t * vPart, * vPartSupp;
00826     int i, k;
00827     // partition the first manager
00828     vParts = Aig_ManPartitionSmart( p1, nPartSize, 0, &vPartSupps );
00829     // derive miters
00830     vMiters = Vec_PtrAlloc( Vec_PtrSize(vParts) );
00831     for ( i = 0; i < Vec_PtrSize(vParts); i++ )
00832     {
00833         // get partitions and their support
00834         vPart     = Vec_PtrEntry( vParts, i );
00835         vPartSupp = Vec_PtrEntry( vPartSupps, i );
00836         // create the new miter
00837         pNew = Aig_ManStart( 1000 );
00838 //        pNew->pName = Extra_UtilStrsav( p1->pName );
00839         // create the PIs
00840         for ( k = 0; k < Vec_IntSize(vPartSupp); k++ )
00841             Aig_ObjCreatePi( pNew );
00842         // copy the components
00843         vNodes1 = Aig_ManDupPart( pNew, p1, vPart, vPartSupp, 0 );
00844         vNodes2 = Aig_ManDupPart( pNew, p2, vPart, vPartSupp, 0 );
00845         // create the miter
00846         pMiter = Aig_MiterTwo( pNew, vNodes1, vNodes2 );
00847         Vec_PtrFree( vNodes1 );
00848         Vec_PtrFree( vNodes2 );
00849         // create the output
00850         Aig_ObjCreatePo( pNew, pMiter );
00851         // clean up
00852         Aig_ManCleanup( pNew );
00853         Vec_PtrPush( vMiters, pNew );
00854     }
00855     Vec_VecFree( (Vec_Vec_t *)vParts );
00856     Vec_VecFree( (Vec_Vec_t *)vPartSupps );
00857     return vMiters;
00858 }

void Aig_ManPartitionCompact ( Vec_Ptr_t *  vPartsAll,
Vec_Ptr_t *  vPartSuppsAll,
int  nSuppSizeLimit 
)

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

Synopsis [Perform the smart partitioning.]

Description []

SideEffects []

SeeAlso []

Definition at line 501 of file aigPart.c.

00502 {
00503     Vec_Int_t * vOne, * vPart, * vPartSupp, * vTemp;
00504     int i, iPart;
00505 
00506     if ( nSuppSizeLimit == 0 )
00507         nSuppSizeLimit = 200;
00508 
00509     // pack smaller partitions into larger blocks
00510     iPart = 0;
00511     vPart = vPartSupp = NULL;
00512     Vec_PtrForEachEntry( vPartSuppsAll, vOne, i )
00513     {
00514         if ( Vec_IntSize(vOne) < nSuppSizeLimit )
00515         {
00516             if ( vPartSupp == NULL )
00517             {
00518                 assert( vPart == NULL );
00519                 vPartSupp = Vec_IntDup(vOne);
00520                 vPart = Vec_PtrEntry(vPartsAll, i);
00521             }
00522             else
00523             {
00524                 vPartSupp = Vec_IntTwoMerge( vTemp = vPartSupp, vOne );
00525                 Vec_IntFree( vTemp );
00526                 vPart = Vec_IntTwoMerge( vTemp = vPart, Vec_PtrEntry(vPartsAll, i) );
00527                 Vec_IntFree( vTemp );
00528                 Vec_IntFree( Vec_PtrEntry(vPartsAll, i) );
00529             }
00530             if ( Vec_IntSize(vPartSupp) < nSuppSizeLimit )
00531                 continue;
00532         }
00533         else
00534             vPart = Vec_PtrEntry(vPartsAll, i);
00535         // add the partition 
00536         Vec_PtrWriteEntry( vPartsAll, iPart, vPart );  
00537         vPart = NULL;
00538         if ( vPartSupp ) 
00539         {
00540             Vec_IntFree( Vec_PtrEntry(vPartSuppsAll, iPart) );
00541             Vec_PtrWriteEntry( vPartSuppsAll, iPart, vPartSupp );  
00542             vPartSupp = NULL;
00543         }
00544         iPart++;
00545     }
00546     // add the last one
00547     if ( vPart )
00548     {
00549         Vec_PtrWriteEntry( vPartsAll, iPart, vPart );  
00550         vPart = NULL;
00551 
00552         assert( vPartSupp != NULL );
00553         Vec_IntFree( Vec_PtrEntry(vPartSuppsAll, iPart) );
00554         Vec_PtrWriteEntry( vPartSuppsAll, iPart, vPartSupp );  
00555         vPartSupp = NULL;
00556         iPart++;
00557     }
00558     Vec_PtrShrink( vPartsAll, iPart );
00559     Vec_PtrShrink( vPartsAll, iPart );
00560 }

Vec_Ptr_t* Aig_ManPartitionNaive ( Aig_Man_t *  p,
int  nPartSize 
)

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

Synopsis [Perform the naive partitioning.]

Description []

SideEffects []

SeeAlso []

Definition at line 697 of file aigPart.c.

00698 {
00699     Vec_Ptr_t * vParts;
00700     Aig_Obj_t * pObj;
00701     int nParts, i;
00702     nParts = (Aig_ManPoNum(p) / nPartSize) + ((Aig_ManPoNum(p) % nPartSize) > 0);
00703     vParts = (Vec_Ptr_t *)Vec_VecStart( nParts );
00704     Aig_ManForEachPo( p, pObj, i )
00705         Vec_IntPush( Vec_PtrEntry(vParts, i / nPartSize), i );
00706     return vParts;
00707 }

void Aig_ManPartitionPrint ( Aig_Man_t *  p,
Vec_Ptr_t *  vPartsAll,
Vec_Ptr_t *  vPartSuppsAll 
)

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

Synopsis [Perform the smart partitioning.]

Description []

SideEffects []

SeeAlso []

Definition at line 472 of file aigPart.c.

00473 {
00474     Vec_Int_t * vOne;
00475     int i, nOutputs, Counter;
00476 
00477     Counter = 0;
00478     Vec_PtrForEachEntry( vPartSuppsAll, vOne, i )
00479     {
00480         nOutputs = Vec_IntSize(Vec_PtrEntry(vPartsAll, i));
00481         printf( "%d=(%d,%d) ", i, Vec_IntSize(vOne), nOutputs );
00482         Counter += nOutputs;
00483         if ( i == Vec_PtrSize(vPartsAll) - 1 )
00484             break;
00485     }
00486     assert( Counter == Aig_ManPoNum(p) );
00487 //    printf( "\nTotal = %d. Outputs = %d.\n", Counter, Aig_ManPoNum(p) );
00488 }

Vec_Ptr_t* Aig_ManPartitionSmart ( Aig_Man_t *  p,
int  nSuppSizeLimit,
int  fVerbose,
Vec_Ptr_t **  pvPartSupps 
)

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

Synopsis [Perform the smart partitioning.]

Description []

SideEffects []

SeeAlso []

Definition at line 573 of file aigPart.c.

00574 {
00575     Vec_Ptr_t * vPartSuppsBit;
00576     Vec_Ptr_t * vSupports, * vPartsAll, * vPartsAll2, * vPartSuppsAll;//, * vPartPtr;
00577     Vec_Int_t * vOne, * vPart, * vPartSupp, * vTemp;
00578     int i, iPart, iOut, clk;
00579 
00580     // compute the supports for all outputs
00581 clk = clock();
00582     vSupports = Aig_ManSupports( p );
00583 if ( fVerbose )
00584 {
00585 PRT( "Supps", clock() - clk );
00586 }
00587     // start char-based support representation
00588     vPartSuppsBit = Vec_PtrAlloc( 1000 );
00589 
00590     // create partitions
00591 clk = clock();
00592     vPartsAll = Vec_PtrAlloc( 256 );
00593     vPartSuppsAll = Vec_PtrAlloc( 256 );
00594     Vec_PtrForEachEntry( vSupports, vOne, i )
00595     {
00596         // get the output number
00597         iOut = Vec_IntPop(vOne);
00598         // find closely matching part
00599         iPart = Aig_ManPartitionSmartFindPart( vPartSuppsAll, vPartsAll, vPartSuppsBit, nSuppSizeLimit, vOne );
00600         if ( iPart == -1 )
00601         {
00602             // create new partition
00603             vPart = Vec_IntAlloc( 32 );
00604             Vec_IntPush( vPart, iOut );
00605             // create new partition support
00606             vPartSupp = Vec_IntDup( vOne );
00607             // add this partition and its support
00608             Vec_PtrPush( vPartsAll, vPart );
00609             Vec_PtrPush( vPartSuppsAll, vPartSupp );
00610 
00611             Vec_PtrPush( vPartSuppsBit, Aig_ManSuppCharStart(vOne, Aig_ManPiNum(p)) );
00612         }
00613         else
00614         {
00615             // add output to this partition
00616             vPart = Vec_PtrEntry( vPartsAll, iPart );
00617             Vec_IntPush( vPart, iOut );
00618             // merge supports
00619             vPartSupp = Vec_PtrEntry( vPartSuppsAll, iPart );
00620             vPartSupp = Vec_IntTwoMerge( vTemp = vPartSupp, vOne );
00621             Vec_IntFree( vTemp );
00622             // reinsert new support
00623             Vec_PtrWriteEntry( vPartSuppsAll, iPart, vPartSupp );
00624 
00625             Aig_ManSuppCharAdd( Vec_PtrEntry(vPartSuppsBit, iPart), vOne, Aig_ManPiNum(p) );
00626         }
00627     }
00628 
00629     // stop char-based support representation
00630     Vec_PtrForEachEntry( vPartSuppsBit, vTemp, i )
00631         free( vTemp );
00632     Vec_PtrFree( vPartSuppsBit );
00633 
00634 //printf( "\n" );
00635 if ( fVerbose )
00636 {
00637 PRT( "Parts", clock() - clk );
00638 }
00639 
00640 clk = clock();
00641     // reorder partitions in the decreasing order of support sizes
00642     // remember partition number in each partition support
00643     Vec_PtrForEachEntry( vPartSuppsAll, vOne, i )
00644         Vec_IntPush( vOne, i );
00645     // sort the supports in the decreasing order
00646     Vec_VecSort( (Vec_Vec_t *)vPartSuppsAll, 1 );
00647     // reproduce partitions
00648     vPartsAll2 = Vec_PtrAlloc( 256 );
00649     Vec_PtrForEachEntry( vPartSuppsAll, vOne, i )
00650         Vec_PtrPush( vPartsAll2, Vec_PtrEntry(vPartsAll, Vec_IntPop(vOne)) );
00651     Vec_PtrFree( vPartsAll );
00652     vPartsAll = vPartsAll2;
00653 
00654     // compact small partitions
00655 //    Aig_ManPartitionPrint( p, vPartsAll, vPartSuppsAll );
00656     Aig_ManPartitionCompact( vPartsAll, vPartSuppsAll, nSuppSizeLimit );
00657     if ( fVerbose )
00658 //    Aig_ManPartitionPrint( p, vPartsAll, vPartSuppsAll );
00659     printf( "Created %d partitions.\n", Vec_PtrSize(vPartsAll) );
00660 
00661 if ( fVerbose )
00662 {
00663 //PRT( "Comps", clock() - clk );
00664 }
00665 
00666     // cleanup
00667     Vec_VecFree( (Vec_Vec_t *)vSupports );
00668     if ( pvPartSupps == NULL )
00669         Vec_VecFree( (Vec_Vec_t *)vPartSuppsAll );
00670     else
00671         *pvPartSupps = vPartSuppsAll;
00672 /*
00673     // converts from intergers to nodes
00674     Vec_PtrForEachEntry( vPartsAll, vPart, iPart )
00675     {
00676         vPartPtr = Vec_PtrAlloc( Vec_IntSize(vPart) );
00677         Vec_IntForEachEntry( vPart, iOut, i )
00678             Vec_PtrPush( vPartPtr, Aig_ManPo(p, iOut) );
00679         Vec_IntFree( vPart );
00680         Vec_PtrWriteEntry( vPartsAll, iPart, vPartPtr );
00681     }
00682 */
00683     return vPartsAll;
00684 }

int Aig_ManPartitionSmartFindPart ( Vec_Ptr_t *  vPartSuppsAll,
Vec_Ptr_t *  vPartsAll,
Vec_Ptr_t *  vPartSuppsBit,
int  nSuppSizeLimit,
Vec_Int_t *  vOne 
)

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

Synopsis [Find the best partition.]

Description []

SideEffects []

SeeAlso []

Definition at line 423 of file aigPart.c.

00424 {
00425     Vec_Int_t * vPartSupp;//, * vPart;
00426     int Attract, Repulse, Value, ValueBest;
00427     int i, nCommon, iBest;
00428     iBest = -1;
00429     ValueBest = 0;
00430     Vec_PtrForEachEntry( vPartSuppsAll, vPartSupp, i )
00431     {
00432 //        vPart = Vec_PtrEntry( vPartsAll, i );
00433 //        if ( nSuppSizeLimit > 0 && Vec_IntSize(vPart) >= nSuppSizeLimit )
00434 //            continue;
00435 //        nCommon = Vec_IntTwoCountCommon( vPartSupp, vOne );
00436         nCommon = Aig_ManSuppCharCommon( Vec_PtrEntry(vPartSuppsBit, i), vOne );
00437         if ( nCommon == 0 )
00438             continue;
00439         if ( nCommon == Vec_IntSize(vOne) )
00440             return i;
00441         // skip partitions whose size exceeds the limit
00442         if ( nSuppSizeLimit > 0 && Vec_IntSize(vPartSupp) >= 2 * nSuppSizeLimit )
00443             continue;
00444         Attract = 1000 * nCommon / Vec_IntSize(vOne);
00445         if ( Vec_IntSize(vPartSupp) < 100 )
00446             Repulse = 1;
00447         else
00448             Repulse = 1+Aig_Base2Log(Vec_IntSize(vPartSupp)-100);
00449         Value = Attract/Repulse;
00450         if ( ValueBest < Value )
00451         {
00452             ValueBest = Value;
00453             iBest = i;
00454         }
00455     }
00456     if ( ValueBest < 75 )
00457         return -1;
00458     return iBest;
00459 }

void Aig_ManSuppCharAdd ( unsigned *  pBuffer,
Vec_Int_t *  vOne,
int  nPis 
)

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

Synopsis [Add to char-bases support representation.]

Description []

SideEffects []

SeeAlso []

Definition at line 383 of file aigPart.c.

00384 {
00385     int i, Entry;
00386     Vec_IntForEachEntry( vOne, Entry, i )
00387     {
00388         assert( Entry < nPis );
00389         Aig_InfoSetBit( pBuffer, Entry );
00390     }
00391 }

int Aig_ManSuppCharCommon ( unsigned *  pBuffer,
Vec_Int_t *  vOne 
)

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

Synopsis [Find the common variables using char-bases support representation.]

Description []

SideEffects []

SeeAlso []

Definition at line 404 of file aigPart.c.

00405 {
00406     int i, Entry, nCommon = 0;
00407     Vec_IntForEachEntry( vOne, Entry, i )
00408         nCommon += Aig_InfoHasBit(pBuffer, Entry);
00409     return nCommon;
00410 }

unsigned* Aig_ManSuppCharStart ( Vec_Int_t *  vOne,
int  nPis 
)

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

Synopsis [Start char-bases support representation.]

Description []

SideEffects []

SeeAlso []

Definition at line 357 of file aigPart.c.

00358 {
00359     unsigned * pBuffer;
00360     int i, Entry;
00361     int nWords = Aig_BitWordNum(nPis);
00362     pBuffer = ALLOC( unsigned, nWords );
00363     memset( pBuffer, 0, sizeof(unsigned) * nWords );
00364     Vec_IntForEachEntry( vOne, Entry, i )
00365     {
00366         assert( Entry < nPis );
00367         Aig_InfoSetBit( pBuffer, Entry );
00368     }
00369     return pBuffer;
00370 }

Vec_Ptr_t* Aig_ManSupports ( Aig_Man_t *  pMan  ) 

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

Synopsis [Computes supports of the POs in the multi-output AIG.]

Description []

SideEffects []

SeeAlso []

Definition at line 267 of file aigPart.c.

00268 {
00269     Vec_Ptr_t * vSupports;
00270     Vec_Int_t * vSupp;
00271     Part_Man_t * p;
00272     Part_One_t * pPart0, * pPart1;
00273     Aig_Obj_t * pObj;
00274     int i;
00275     // set the number of PIs/POs
00276     Aig_ManForEachPi( pMan, pObj, i )
00277         pObj->pNext = (Aig_Obj_t *)(long)i;
00278     Aig_ManForEachPo( pMan, pObj, i )
00279         pObj->pNext = (Aig_Obj_t *)(long)i;
00280     // start the support computation manager
00281     p = Part_ManStart( 1 << 20, 1 << 6 );
00282     // consider objects in the topological order
00283     vSupports = Vec_PtrAlloc( Aig_ManPoNum(pMan) );
00284     Aig_ManCleanData(pMan);
00285     Aig_ManForEachObj( pMan, pObj, i )
00286     {
00287         if ( Aig_ObjIsNode(pObj) )
00288         {
00289             pPart0 = Aig_ObjFanin0(pObj)->pData;
00290             pPart1 = Aig_ObjFanin1(pObj)->pData;
00291             pObj->pData = Part_ManMergeEntry( p, pPart0, pPart1, pObj->nRefs );
00292             assert( pPart0->nRefs > 0 );
00293             if ( --pPart0->nRefs == 0 )
00294                 Part_ManRecycleEntry( p, pPart0 );
00295             assert( pPart1->nRefs > 0 );
00296             if ( --pPart1->nRefs == 0 )
00297                 Part_ManRecycleEntry( p, pPart1 );
00298             continue;
00299         }
00300         if ( Aig_ObjIsPo(pObj) )
00301         {
00302             pPart0 = Aig_ObjFanin0(pObj)->pData;
00303             vSupp = Part_ManTransferEntry(pPart0);
00304             Vec_IntPush( vSupp, (int)(long)pObj->pNext );
00305             Vec_PtrPush( vSupports, vSupp );
00306             assert( pPart0->nRefs > 0 );
00307             if ( --pPart0->nRefs == 0 )
00308                 Part_ManRecycleEntry( p, pPart0 );
00309             continue;
00310         }
00311         if ( Aig_ObjIsPi(pObj) )
00312         {
00313             if ( pObj->nRefs )
00314             {
00315                 pPart0 = Part_ManFetchEntry( p, 1, pObj->nRefs );
00316                 pPart0->pOuts[ pPart0->nOuts++ ] = (int)(long)pObj->pNext;
00317                 pObj->pData = pPart0;
00318             }
00319             continue;
00320         }
00321         if ( Aig_ObjIsConst1(pObj) )
00322         {
00323             if ( pObj->nRefs )
00324                 pObj->pData = Part_ManFetchEntry( p, 0, pObj->nRefs );
00325             continue;
00326         }
00327         assert( 0 );
00328     }
00329 //printf( "Memory usage = %d Mb.\n", Vec_PtrSize(p->vMemory) * p->nChunkSize / (1<<20) );
00330     Part_ManStop( p );
00331     // sort supports by size
00332     Vec_VecSort( (Vec_Vec_t *)vSupports, 1 );
00333     // clear the number of PIs/POs
00334     Aig_ManForEachPi( pMan, pObj, i )
00335         pObj->pNext = NULL;
00336     Aig_ManForEachPo( pMan, pObj, i )
00337         pObj->pNext = NULL;
00338 /*
00339     Aig_ManForEachPo( pMan, pObj, i )
00340         printf( "%d ", Vec_IntSize( (Vec_Int_t *)Vec_VecEntry(vSupports, i) ) );
00341     printf( "\n" );
00342 */
00343     return vSupports;
00344 }

char* Part_ManFetch ( Part_Man_t *  p,
int  nSize 
)

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

Synopsis [Fetches the memory entry of the given size.]

Description []

SideEffects []

SeeAlso []

Definition at line 111 of file aigPart.c.

00112 {
00113     int Type, nSizeReal;
00114     char * pMemory;
00115     assert( nSize > 0 );
00116     Type = Part_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, Part_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 }

static Part_One_t* Part_ManFetchEntry ( Part_Man_t *  p,
int  nWords,
int  nRefs 
) [inline, static]

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

Synopsis [Fetches the memory entry of the given size.]

Description []

SideEffects []

SeeAlso []

Definition at line 168 of file aigPart.c.

00169 {
00170     Part_One_t * pPart;
00171     pPart = (Part_One_t *)Part_ManFetch( p, sizeof(Part_One_t) + sizeof(int) * nWords );
00172     pPart->nRefs = nRefs;
00173     pPart->nOuts = 0;
00174     pPart->nOutsAlloc = nWords;
00175     return pPart;
00176 }

Part_One_t* Part_ManMergeEntry ( Part_Man_t *  pMan,
Part_One_t *  p1,
Part_One_t *  p2,
int  nRefs 
)

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

Synopsis [Merges two entries.]

Description []

SideEffects []

SeeAlso []

Definition at line 207 of file aigPart.c.

00208 {
00209     Part_One_t * p = Part_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 }

void Part_ManRecycle ( Part_Man_t *  p,
char *  pMemory,
int  nSize 
)

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

Synopsis [Recycles the memory entry of the given size.]

Description []

SideEffects []

SeeAlso []

Definition at line 148 of file aigPart.c.

00149 {
00150     int Type;
00151     Type = Part_SizeType( nSize, p->nStepSize );
00152     Vec_PtrFillExtra( p->vFree, Type + 1, NULL );
00153     Part_OneSetNext( pMemory, Vec_PtrEntry(p->vFree, Type) );
00154     Vec_PtrWriteEntry( p->vFree, Type, pMemory );
00155 }

static void Part_ManRecycleEntry ( Part_Man_t *  p,
Part_One_t *  pEntry 
) [inline, static]

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

Synopsis [Recycles the memory entry of the given size.]

Description []

SideEffects []

SeeAlso []

Definition at line 189 of file aigPart.c.

00190 {
00191     assert( pEntry->nOuts <= pEntry->nOutsAlloc );
00192     assert( pEntry->nOuts >= pEntry->nOutsAlloc/2 );
00193     Part_ManRecycle( p, (char *)pEntry, sizeof(Part_One_t) + sizeof(int) * pEntry->nOutsAlloc );
00194 }

Part_Man_t* Part_ManStart ( int  nChunkSize,
int  nStepSize 
)

FUNCTION DEFINITIONS ///Function*************************************************************

Synopsis [Start the memory manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 66 of file aigPart.c.

00067 {
00068     Part_Man_t * p;
00069     p = ALLOC( Part_Man_t, 1 );
00070     memset( p, 0, sizeof(Part_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 }

void Part_ManStop ( Part_Man_t *  p  ) 

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

Synopsis [Stops the memory manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 89 of file aigPart.c.

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 }

Vec_Int_t* Part_ManTransferEntry ( Part_One_t *  p  ) 

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

Synopsis [Tranfers the entry.]

Description []

SideEffects []

SeeAlso []

Definition at line 246 of file aigPart.c.

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 }

static char* Part_OneNext ( char *  pPart  )  [inline, static]

Definition at line 48 of file aigPart.c.

00048 { return *((char **)pPart);                             }

static void Part_OneSetNext ( char *  pPart,
char *  pNext 
) [inline, static]

Definition at line 49 of file aigPart.c.

00049 { *((char **)pPart) = pNext;                            }

static int Part_SizeType ( int  nSize,
int  nStepSize 
) [inline, static]

Definition at line 47 of file aigPart.c.

00047 { return nSize / nStepSize + ((nSize % nStepSize) > 0); }

Generated on Tue Jan 5 12:18:11 2010 for abc70930 by  doxygen 1.6.1