| /**CFile**************************************************************** |
| |
| FileName [llb1Matrix.c] |
| |
| SystemName [ABC: Logic synthesis and verification system.] |
| |
| PackageName [BDD based reachability.] |
| |
| Synopsis [Partition clustering as a matrix problem.] |
| |
| Author [Alan Mishchenko] |
| |
| Affiliation [UC Berkeley] |
| |
| Date [Ver. 1.0. Started - June 20, 2005.] |
| |
| Revision [$Id: llb1Matrix.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] |
| |
| ***********************************************************************/ |
| |
| #include "llbInt.h" |
| |
| ABC_NAMESPACE_IMPL_START |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// DECLARATIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| // 0123 nCols |
| // +---------------------> |
| // pi 0 | 111 row0 pRowSums[0] |
| // pi 1 | 1 11 row1 pRowSums[1] |
| // pi 2 | 1 11 row2 pRowSums[2] |
| // CS |1 1 |
| // CS |1 111 |
| // CS |111 111 |
| // int | 11111 |
| // int | 111 |
| // int | 111 |
| // int | 111 |
| // NS | 11 11 |
| // NS | 11 1 |
| // NS | 111 |
| // nRows | |
| // v |
| // cccc pColSums[0] |
| // oooo pColSums[1] |
| // llll pColSums[2] |
| // 0123 pColSums[3] |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// FUNCTION DEFINITIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| /**Function************************************************************* |
| |
| Synopsis [Verify columns.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Llb_MtrVerifyRowsAll( Llb_Mtr_t * p ) |
| { |
| int iRow, iCol, Counter; |
| for ( iCol = 0; iCol < p->nCols; iCol++ ) |
| { |
| Counter = 0; |
| for ( iRow = 0; iRow < p->nRows; iRow++ ) |
| if ( p->pMatrix[iCol][iRow] == 1 ) |
| Counter++; |
| assert( Counter == p->pColSums[iCol] ); |
| } |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Verify columns.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Llb_MtrVerifyColumnsAll( Llb_Mtr_t * p ) |
| { |
| int iRow, iCol, Counter; |
| for ( iRow = 0; iRow < p->nRows; iRow++ ) |
| { |
| Counter = 0; |
| for ( iCol = 0; iCol < p->nCols; iCol++ ) |
| if ( p->pMatrix[iCol][iRow] == 1 ) |
| Counter++; |
| assert( Counter == p->pRowSums[iRow] ); |
| } |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Verify columns.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Llb_MtrVerifyMatrix( Llb_Mtr_t * p ) |
| { |
| Llb_MtrVerifyRowsAll( p ); |
| Llb_MtrVerifyColumnsAll( p ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Sort variables in the order of removal.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int * Llb_MtrFindVarOrder( Llb_Mtr_t * p ) |
| { |
| int * pOrder, * pLast; |
| int i, k, fChanges, Temp; |
| pOrder = ABC_CALLOC( int, p->nRows ); |
| pLast = ABC_CALLOC( int, p->nRows ); |
| for ( i = 0; i < p->nRows; i++ ) |
| { |
| pOrder[i] = i; |
| for ( k = p->nCols - 1; k >= 0; k-- ) |
| if ( p->pMatrix[k][i] ) |
| { |
| pLast[i] = k; |
| break; |
| } |
| } |
| do |
| { |
| fChanges = 0; |
| for ( i = 0; i < p->nRows - 1; i++ ) |
| if ( pLast[i] > pLast[i+1] ) |
| { |
| Temp = pOrder[i]; |
| pOrder[i] = pOrder[i+1]; |
| pOrder[i+1] = Temp; |
| |
| Temp = pLast[i]; |
| pLast[i] = pLast[i+1]; |
| pLast[i+1] = Temp; |
| |
| fChanges = 1; |
| } |
| } |
| while ( fChanges ); |
| ABC_FREE( pLast ); |
| return pOrder; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Returns type of a variable.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| char * Llb_MtrVarName( Llb_Mtr_t * p, int iVar ) |
| { |
| static char Buffer[10]; |
| if ( iVar < p->nPis ) |
| strcpy( Buffer, "pi" ); |
| else if ( iVar < p->nPis + p->nFfs ) |
| strcpy( Buffer, "CS" ); |
| else if ( iVar >= p->nRows - p->nFfs ) |
| strcpy( Buffer, "NS" ); |
| else |
| strcpy( Buffer, "int" ); |
| return Buffer; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Creates one column with vars in the array.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Llb_MtrPrint( Llb_Mtr_t * p, int fOrder ) |
| { |
| int * pOrder = NULL; |
| int i, iRow, iCol; |
| if ( fOrder ) |
| pOrder = Llb_MtrFindVarOrder( p ); |
| for ( i = 0; i < p->nRows; i++ ) |
| { |
| iRow = pOrder ? pOrder[i] : i; |
| printf( "%3d : ", iRow ); |
| printf( "%3d ", p->pRowSums[iRow] ); |
| printf( "%3s ", Llb_MtrVarName(p, iRow) ); |
| for ( iCol = 0; iCol < p->nCols; iCol++ ) |
| printf( "%c", p->pMatrix[iCol][iRow] ? '*' : ' ' ); |
| printf( "\n" ); |
| } |
| ABC_FREE( pOrder ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Verify columns.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Llb_MtrPrintMatrixStats( Llb_Mtr_t * p ) |
| { |
| int iVar, iGrp, iGrp1, iGrp2, Span = 0, nCutSize = 0, nCutSizeMax = 0; |
| int * pGrp1 = ABC_CALLOC( int, p->nRows ); |
| int * pGrp2 = ABC_CALLOC( int, p->nRows ); |
| for ( iVar = 0; iVar < p->nRows; iVar++ ) |
| { |
| if ( p->pRowSums[iVar] == 0 ) |
| continue; |
| for ( iGrp1 = 0; iGrp1 < p->nCols; iGrp1++ ) |
| if ( p->pMatrix[iGrp1][iVar] == 1 ) |
| break; |
| for ( iGrp2 = p->nCols - 1; iGrp2 >= 0; iGrp2-- ) |
| if ( p->pMatrix[iGrp2][iVar] == 1 ) |
| break; |
| assert( iGrp1 <= iGrp2 ); |
| pGrp1[iVar] = iGrp1; |
| pGrp2[iVar] = iGrp2; |
| Span += iGrp2 - iGrp1; |
| } |
| // compute span |
| for ( iGrp = 0; iGrp < p->nCols; iGrp++ ) |
| { |
| for ( iVar = 0; iVar < p->nRows; iVar++ ) |
| if ( pGrp1[iVar] == iGrp ) |
| nCutSize++; |
| if ( nCutSizeMax < nCutSize ) |
| nCutSizeMax = nCutSize; |
| for ( iVar = 0; iVar < p->nRows; iVar++ ) |
| if ( pGrp2[iVar] == iGrp ) |
| nCutSize--; |
| } |
| ABC_FREE( pGrp1 ); |
| ABC_FREE( pGrp2 ); |
| printf( "[%4d x %4d] Life-span =%6.2f Max-cut =%5d\n", |
| p->nCols, p->nRows, 1.0*Span/p->nRows, nCutSizeMax ); |
| if ( nCutSize ) |
| Abc_Print( -1, "Cut size is not zero (%d).\n", nCutSize ); |
| } |
| |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Starts the matrix representation.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Llb_Mtr_t * Llb_MtrAlloc( int nPis, int nFfs, int nCols, int nRows ) |
| { |
| Llb_Mtr_t * p; |
| int i; |
| p = ABC_CALLOC( Llb_Mtr_t, 1 ); |
| p->nPis = nPis; |
| p->nFfs = nFfs; |
| p->nRows = nRows; |
| p->nCols = nCols; |
| p->pRowSums = ABC_CALLOC( int, nRows ); |
| p->pColSums = ABC_CALLOC( int, nCols ); |
| p->pColGrps = ABC_CALLOC( Llb_Grp_t *, nCols ); |
| p->pMatrix = ABC_CALLOC( char *, nCols ); |
| for ( i = 0; i < nCols; i++ ) |
| p->pMatrix[i] = ABC_CALLOC( char, nRows ); |
| // partial product |
| p->pProdVars = ABC_CALLOC( char, nRows ); // variables in the partial product |
| p->pProdNums = ABC_CALLOC( int, nRows ); // var counts in the remaining partitions |
| return p; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Stops the matrix representation.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Llb_MtrFree( Llb_Mtr_t * p ) |
| { |
| int i; |
| ABC_FREE( p->pProdVars ); |
| ABC_FREE( p->pProdNums ); |
| for ( i = 0; i < p->nCols; i++ ) |
| ABC_FREE( p->pMatrix[i] ); |
| ABC_FREE( p->pRowSums ); |
| ABC_FREE( p->pColSums ); |
| ABC_FREE( p->pMatrix ); |
| ABC_FREE( p->pColGrps ); |
| ABC_FREE( p ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Creates one column with vars in the array.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Llb_MtrAddColumn( Llb_Mtr_t * p, Llb_Grp_t * pGrp ) |
| { |
| Aig_Obj_t * pVar; |
| int i, iRow, iCol = pGrp->Id; |
| assert( iCol >= 0 && iCol < p->nCols ); |
| p->pColGrps[iCol] = pGrp; |
| Vec_PtrForEachEntry( Aig_Obj_t *, pGrp->vIns, pVar, i ) |
| { |
| iRow = Vec_IntEntry( pGrp->pMan->vObj2Var, Aig_ObjId(pVar) ); |
| assert( iRow >= 0 && iRow < p->nRows ); |
| p->pMatrix[iCol][iRow] = 1; |
| p->pColSums[iCol]++; |
| p->pRowSums[iRow]++; |
| } |
| Vec_PtrForEachEntry( Aig_Obj_t *, pGrp->vOuts, pVar, i ) |
| { |
| iRow = Vec_IntEntry( pGrp->pMan->vObj2Var, Aig_ObjId(pVar) ); |
| assert( iRow >= 0 && iRow < p->nRows ); |
| p->pMatrix[iCol][iRow] = 1; |
| p->pColSums[iCol]++; |
| p->pRowSums[iRow]++; |
| } |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Matrix reduce.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Llb_MtrRemoveSingletonRows( Llb_Mtr_t * p ) |
| { |
| int i, k; |
| for ( i = 0; i < p->nRows; i++ ) |
| if ( p->pRowSums[i] < 2 ) |
| { |
| p->pRowSums[i] = 0; |
| for ( k = 0; k < p->nCols; k++ ) |
| { |
| if ( p->pMatrix[k][i] == 1 ) |
| { |
| p->pMatrix[k][i] = 0; |
| p->pColSums[k]--; |
| } |
| } |
| } |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Matrix reduce.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Llb_Mtr_t * Llb_MtrCreate( Llb_Man_t * p ) |
| { |
| Llb_Mtr_t * pMatrix; |
| Llb_Grp_t * pGroup; |
| int i; |
| pMatrix = Llb_MtrAlloc( Saig_ManPiNum(p->pAig), Saig_ManRegNum(p->pAig), |
| Vec_PtrSize(p->vGroups), Vec_IntSize(p->vVar2Obj) ); |
| Vec_PtrForEachEntry( Llb_Grp_t *, p->vGroups, pGroup, i ) |
| Llb_MtrAddColumn( pMatrix, pGroup ); |
| // Llb_MtrRemoveSingletonRows( pMatrix ); |
| return pMatrix; |
| } |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// END OF FILE /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| ABC_NAMESPACE_IMPL_END |
| |
