| /**CFile**************************************************************** |
| |
| FileName [exor.c] |
| |
| SystemName [ABC: Logic synthesis and verification system.] |
| |
| PackageName [Exclusive sum-of-product minimization.] |
| |
| Synopsis [Main procedure.] |
| |
| Author [Alan Mishchenko] |
| |
| Affiliation [UC Berkeley] |
| |
| Date [Ver. 1.0. Started - June 20, 2005.] |
| |
| Revision [$Id: exor.c,v 1.0 2005/06/20 00:00:00 alanmi Exp $] |
| |
| ***********************************************************************/ |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// /// |
| /// Implementation of EXORCISM - 4 /// |
| /// An Exclusive Sum-of-Product Minimizer /// |
| /// Alan Mishchenko <alanmi@ee.pdx.edu> /// |
| /// /// |
| //////////////////////////////////////////////////////////////////////// |
| /// /// |
| /// Main Module /// |
| /// ESOP Minimization Task Coordinator /// |
| /// /// |
| /// 1) interprets command line /// |
| /// 2) calls the approapriate reading procedure /// |
| /// 3) calls the minimization module /// |
| /// /// |
| /// Ver. 1.0. Started - July 18, 2000. Last update - July 20, 2000 /// |
| /// Ver. 1.1. Started - July 24, 2000. Last update - July 29, 2000 /// |
| /// Ver. 1.4. Started - Aug 10, 2000. Last update - Aug 26, 2000 /// |
| /// Ver. 1.6. Started - Sep 11, 2000. Last update - Sep 15, 2000 /// |
| /// Ver. 1.7. Started - Sep 20, 2000. Last update - Sep 23, 2000 /// |
| /// /// |
| //////////////////////////////////////////////////////////////////////// |
| /// This software was tested with the BDD package "CUDD", v.2.3.0 /// |
| /// by Fabio Somenzi /// |
| /// http://vlsi.colorado.edu/~fabio/ /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| #include "exor.h" |
| |
| ABC_NAMESPACE_IMPL_START |
| |
| /////////////////////////////////////////////////////////////////////// |
| /// GLOBAL VARIABLES /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| // information about the cube cover |
| cinfo g_CoverInfo; |
| |
| extern int s_fDecreaseLiterals; |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// EXTERNAL FUNCTIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// FUNCTION main() /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Number of negative literals.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| /* |
| static int QCost[16][16] = |
| { |
| { 1}, // 0 |
| { 1, 2}, // 1 |
| { 5, 5, 6}, // 2 |
| { 14, 14, 16, 18}, // 3 |
| { 20, 20, 20, 22, 24}, // 4 |
| { 32, 32, 32, 34, 36, 38}, // 5 |
| { 44, 44, 44, 44, 46, 48, 50}, // 6 |
| { 56, 56, 56, 56, 58, 60, 62, 64}, // 7 |
| { 0 } |
| }; |
| */ |
| int GetQCost( int nVars, int nNegs ) |
| { |
| int Extra; |
| assert( nVars >= nNegs ); |
| if ( nVars == 0 ) |
| return 1; |
| if ( nVars == 1 ) |
| { |
| if ( nNegs == 0 ) return 1; |
| if ( nNegs == 1 ) return 2; |
| } |
| if ( nVars == 2 ) |
| { |
| if ( nNegs <= 1 ) return 5; |
| if ( nNegs == 2 ) return 6; |
| } |
| if ( nVars == 3 ) |
| { |
| if ( nNegs <= 1 ) return 14; |
| if ( nNegs == 2 ) return 16; |
| if ( nNegs == 3 ) return 18; |
| } |
| Extra = nNegs - nVars/2; |
| return 20 + 12 * (nVars - 4) + (Extra > 0 ? 2 * Extra : 0); |
| |
| } |
| void GetQCostTest() |
| { |
| int i, k, Limit = 10; |
| for ( i = 0; i < Limit; i++ ) |
| { |
| for ( k = 0; k <= i; k++ ) |
| printf( "%4d ", GetQCost(i, k) ); |
| printf( "\n" ); |
| } |
| } |
| int ComputeQCost( Vec_Int_t * vCube ) |
| { |
| int i, Entry, nLitsN = 0; |
| Vec_IntForEachEntry( vCube, Entry, i ) |
| nLitsN += Abc_LitIsCompl(Entry); |
| return GetQCost( Vec_IntSize(vCube), nLitsN ); |
| } |
| int ComputeQCostBits( Cube * p ) |
| { |
| extern varvalue GetVar( Cube* pC, int Var ); |
| int v, nLits = 0, nLitsN = 0; |
| for ( v = 0; v < g_CoverInfo.nVarsIn; v++ ) |
| { |
| int Value = GetVar( p, v ); |
| if ( Value == VAR_NEG ) |
| nLitsN++; |
| else if ( Value == VAR_POS ) |
| nLits++; |
| } |
| nLits += nLitsN; |
| return GetQCost( nLits, nLitsN ); |
| } |
| int ToffoliGateCount( int controls, int lines ) |
| { |
| switch ( controls ) |
| { |
| case 0u: |
| case 1u: |
| return 0; |
| break; |
| case 2u: |
| return 1; |
| break; |
| case 3u: |
| return 4; |
| break; |
| case 4u: |
| return ( ( ( lines + 1 ) / 2 ) >= controls ) ? 8 : 10; |
| break; |
| default: |
| return ( ( ( lines + 1 ) / 2 ) >= controls ) ? 4 * ( controls - 2 ) : 8 * ( controls - 3 ); |
| } |
| } |
| int ComputeQCostTcount( Vec_Int_t * vCube ) |
| { |
| return 7 * ToffoliGateCount( Vec_IntSize( vCube ), g_CoverInfo.nVarsIn + 1 ); |
| } |
| int ComputeQCostTcountBits( Cube * p ) |
| { |
| extern varvalue GetVar( Cube* pC, int Var ); |
| int v, nLits = 0; |
| for ( v = 0; v < g_CoverInfo.nVarsIn; v++ ) |
| if ( GetVar( p, v ) != VAR_ABS ) |
| nLits++; |
| return 7 * ToffoliGateCount( nLits, g_CoverInfo.nVarsIn + 1 ); |
| |
| /* maybe just: 7 * ToffoliGateCount( p->a, g_CoverInfo.nVarsIn + 1 ); */ |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int ReduceEsopCover() |
| { |
| /////////////////////////////////////////////////////////////// |
| // SIMPLIFICATION |
| //////////////////////////////////////////////////////////////////// |
| |
| int nIterWithoutImprovement = 0; |
| int nIterCount = 0; |
| int GainTotal; |
| int z; |
| |
| do |
| { |
| //START: |
| if ( g_CoverInfo.Verbosity == 2 ) |
| printf( "\nITERATION #%d\n\n", ++nIterCount ); |
| else if ( g_CoverInfo.Verbosity == 1 ) |
| printf( "." ); |
| |
| GainTotal = 0; |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| |
| if ( nIterWithoutImprovement > (int)(g_CoverInfo.Quality>0) ) |
| { |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink2( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink2( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink4( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink2( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink4( 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink2( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink2( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink4( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink2( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink4( 1|2|0 ); |
| } |
| |
| if ( GainTotal ) |
| nIterWithoutImprovement = 0; |
| else |
| nIterWithoutImprovement++; |
| |
| // if ( g_CoverInfo.Quality >= 2 && nIterWithoutImprovement == 2 ) |
| // s_fDecreaseLiterals = 1; |
| } |
| while ( nIterWithoutImprovement < 1 + g_CoverInfo.Quality ); |
| |
| |
| // improve the literal count |
| s_fDecreaseLiterals = 1; |
| for ( z = 0; z < 1; z++ ) |
| { |
| if ( g_CoverInfo.Verbosity == 2 ) |
| printf( "\nITERATION #%d\n\n", ++nIterCount ); |
| else if ( g_CoverInfo.Verbosity == 1 ) |
| printf( "." ); |
| |
| GainTotal = 0; |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| |
| // if ( GainTotal ) |
| // { |
| // nIterWithoutImprovement = 0; |
| // goto START; |
| // } |
| } |
| |
| |
| /* //////////////////////////////////////////////////////////////////// |
| // Print statistics |
| printf( "\nShallow simplification time is "; |
| cout << (float)(clk2 - clk1)/(float)(CLOCKS_PER_SEC) << " sec\n" ); |
| printf( "Deep simplification time is "; |
| cout << (float)(Abc_Clock() - clk2)/(float)(CLOCKS_PER_SEC) << " sec\n" ); |
| printf( "Cover after iterative simplification = " << s_nCubesInUse << endl; |
| printf( "Reduced by initial cube writing = " << g_CoverInfo.nCubesBefore-nCubesAfterWriting << endl; |
| printf( "Reduced by shallow simplification = " << nCubesAfterWriting-nCubesAfterShallow << endl; |
| printf( "Reduced by deep simplification = " << nCubesAfterWriting-s_nCubesInUse << endl; |
| |
| // printf( "\nThe total number of cubes created = " << g_CoverInfo.cIDs << endl; |
| // printf( "Total number of places in a queque = " << s_nPosAlloc << endl; |
| // printf( "Minimum free places in queque-2 = " << s_nPosMax[0] << endl; |
| // printf( "Minimum free places in queque-3 = " << s_nPosMax[1] << endl; |
| // printf( "Minimum free places in queque-4 = " << s_nPosMax[2] << endl; |
| */ //////////////////////////////////////////////////////////////////// |
| |
| // write the number of cubes into cover information |
| assert ( g_CoverInfo.nCubesInUse + g_CoverInfo.nCubesFree == g_CoverInfo.nCubesAlloc ); |
| |
| // printf( "\nThe output cover is\n" ); |
| // PrintCoverDebug( cout ); |
| |
| return 0; |
| } |
| |
| ////////////////////////////////////////////////////////////////// |
| // quite a good script |
| ////////////////////////////////////////////////////////////////// |
| /* |
| long clk1 = Abc_Clock(); |
| int nIterWithoutImprovement = 0; |
| do |
| { |
| PrintQuequeStats(); |
| GainTotal = 0; |
| GainTotal += IterativelyApplyExorLink( DIST2, 0|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 0|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|0 ); |
| |
| if ( nIterWithoutImprovement > 2 ) |
| { |
| GainTotal += IterativelyApplyExorLink( DIST2, 0|0|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST4, 0|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST4, 1|2|0 ); |
| } |
| |
| if ( nIterWithoutImprovement > 6 ) |
| { |
| GainTotal += IterativelyApplyExorLink( DIST2, 0|0|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST4, 0|0|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST4, 0|0|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST4, 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST4, 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST4, 1|2|0 ); |
| } |
| |
| if ( GainTotal ) |
| nIterWithoutImprovement = 0; |
| else |
| nIterWithoutImprovement++; |
| } |
| while ( nIterWithoutImprovement < 12 ); |
| |
| nCubesAfterShallow = s_nCubesInUse; |
| |
| */ |
| |
| /* |
| // alu4 - 439 |
| long clk1 = Abc_Clock(); |
| int nIterWithoutImprovement = 0; |
| do |
| { |
| PrintQuequeStats(); |
| GainTotal = 0; |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|0|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|0 ); |
| |
| if ( nIterWithoutImprovement > 2 ) |
| { |
| GainTotal += IterativelyApplyExorLink( DIST2, 0|0|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST4, 0|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST4, 1|2|0 ); |
| } |
| |
| if ( nIterWithoutImprovement > 6 ) |
| { |
| GainTotal += IterativelyApplyExorLink( DIST2, 0|0|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST4, 0|0|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST4, 0|0|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST4, 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST4, 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST4, 1|2|0 ); |
| } |
| |
| if ( GainTotal ) |
| nIterWithoutImprovement = 0; |
| else |
| nIterWithoutImprovement++; |
| } |
| while ( nIterWithoutImprovement < 12 ); |
| */ |
| |
| /* |
| // alu4 - 412 cubes, 700 sec |
| |
| long clk1 = Abc_Clock(); |
| int nIterWithoutImprovement = 0; |
| int nIterCount = 0; |
| do |
| { |
| printf( "\nITERATION #" << ++nIterCount << endl << endl; |
| |
| GainTotal = 0; |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| |
| if ( nIterWithoutImprovement > 3 ) |
| { |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink2( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink4( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink4( 1|2|4 ); |
| } |
| |
| if ( nIterWithoutImprovement > 7 ) |
| { |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink2( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink4( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink4( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink4( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink4( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink4( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink4( 1|2|4 ); |
| } |
| |
| if ( GainTotal ) |
| nIterWithoutImprovement = 0; |
| else |
| nIterWithoutImprovement++; |
| } |
| while ( nIterWithoutImprovement < 12 ); |
| */ |
| |
| /* |
| // pretty good script |
| // alu4 = 424 in 250 sec |
| |
| long clk1 = Abc_Clock(); |
| int nIterWithoutImprovement = 0; |
| int nIterCount = 0; |
| do |
| { |
| printf( "\nITERATION #" << ++nIterCount << " |"; |
| for ( int k = 0; k < nIterWithoutImprovement; k++ ) |
| printf( "*"; |
| for ( ; k < 11; k++ ) |
| printf( "_"; |
| printf( "|" << endl << endl; |
| |
| GainTotal = 0; |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|0 ); |
| |
| if ( nIterWithoutImprovement > 2 ) |
| { |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST4, 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST4, 1|2|4 ); |
| } |
| |
| if ( nIterWithoutImprovement > 4 ) |
| { |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST4, 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST4, 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST4, 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST4, 1|2|4 ); |
| } |
| |
| if ( GainTotal ) |
| nIterWithoutImprovement = 0; |
| else |
| nIterWithoutImprovement++; |
| } |
| while ( nIterWithoutImprovement < 7 ); |
| */ |
| |
| /* |
| alu4 = 435 70 secs |
| |
| long clk1 = Abc_Clock(); |
| int nIterWithoutImprovement = 0; |
| int nIterCount = 0; |
| |
| do |
| { |
| printf( "\nITERATION #" << ++nIterCount << endl << endl; |
| |
| GainTotal = 0; |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|0 ); |
| |
| |
| if ( GainTotal ) |
| nIterWithoutImprovement = 0; |
| else |
| nIterWithoutImprovement++; |
| } |
| while ( nIterWithoutImprovement < 4 ); |
| */ |
| |
| /* |
| // the best previous |
| |
| long clk1 = Abc_Clock(); |
| int nIterWithoutImprovement = 0; |
| int nIterCount = 0; |
| int GainTotal; |
| do |
| { |
| if ( g_CoverInfo.Verbosity == 2 ) |
| printf( "\nITERATION #" << ++nIterCount << endl << endl; |
| else if ( g_CoverInfo.Verbosity == 1 ) |
| cout << '.'; |
| |
| GainTotal = 0; |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|0 ); |
| |
| if ( nIterWithoutImprovement > 1 ) |
| { |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST4, 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST4, 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink( DIST3, 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST4, 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST2, 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink( DIST4, 1|2|0 ); |
| } |
| |
| if ( GainTotal ) |
| nIterWithoutImprovement = 0; |
| else |
| nIterWithoutImprovement++; |
| } |
| // while ( nIterWithoutImprovement < 20 ); |
| // while ( nIterWithoutImprovement < 7 ); |
| while ( nIterWithoutImprovement < 1 + g_CoverInfo.Quality ); |
| |
| */ |
| |
| /* |
| // the last tried |
| |
| long clk1 = Abc_Clock(); |
| int nIterWithoutImprovement = 0; |
| int nIterCount = 0; |
| int GainTotal; |
| do |
| { |
| if ( g_CoverInfo.Verbosity == 2 ) |
| printf( "\nITERATION #" << ++nIterCount << endl << endl; |
| else if ( g_CoverInfo.Verbosity == 1 ) |
| cout << '.'; |
| |
| GainTotal = 0; |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| |
| if ( nIterWithoutImprovement > (int)(g_CoverInfo.Quality>0) ) |
| { |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink2( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink4( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink2( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink4( 1|2|0 ); |
| |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink2( 1|2|0 ); |
| GainTotal += IterativelyApplyExorLink3( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink2( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink4( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink2( 1|2|4 ); |
| GainTotal += IterativelyApplyExorLink4( 1|2|0 ); |
| } |
| |
| if ( GainTotal ) |
| nIterWithoutImprovement = 0; |
| else |
| nIterWithoutImprovement++; |
| } |
| while ( nIterWithoutImprovement < 1 + g_CoverInfo.Quality ); |
| */ |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void AddCubesToStartingCover( Vec_Wec_t * vEsop ) |
| { |
| Vec_Int_t * vCube; |
| Cube * pNew; |
| int * s_Level2Var; |
| int * s_LevelValues; |
| int c, i, k, Lit, Out; |
| |
| s_Level2Var = ABC_ALLOC( int, g_CoverInfo.nVarsIn ); |
| s_LevelValues = ABC_ALLOC( int, g_CoverInfo.nVarsIn ); |
| |
| for ( i = 0; i < g_CoverInfo.nVarsIn; i++ ) |
| s_Level2Var[i] = i; |
| |
| g_CoverInfo.nLiteralsBefore = 0; |
| g_CoverInfo.QCostBefore = 0; |
| Vec_WecForEachLevel( vEsop, vCube, c ) |
| { |
| // get the output of this cube |
| Out = -Vec_IntPop(vCube) - 1; |
| |
| // fill in the cube with blanks |
| for ( i = 0; i < g_CoverInfo.nVarsIn; i++ ) |
| s_LevelValues[i] = VAR_ABS; |
| Vec_IntForEachEntry( vCube, Lit, k ) |
| { |
| if ( Abc_LitIsCompl(Lit) ) |
| s_LevelValues[Abc_Lit2Var(Lit)] = VAR_NEG; |
| else |
| s_LevelValues[Abc_Lit2Var(Lit)] = VAR_POS; |
| } |
| |
| // get the new cube |
| pNew = GetFreeCube(); |
| // consider the need to clear the cube |
| if ( pNew->pCubeDataIn[0] ) // this is a recycled cube |
| { |
| for ( i = 0; i < g_CoverInfo.nWordsIn; i++ ) |
| pNew->pCubeDataIn[i] = 0; |
| for ( i = 0; i < g_CoverInfo.nWordsOut; i++ ) |
| pNew->pCubeDataOut[i] = 0; |
| } |
| |
| InsertVarsWithoutClearing( pNew, s_Level2Var, g_CoverInfo.nVarsIn, s_LevelValues, Out ); |
| // set literal counts |
| pNew->a = Vec_IntSize(vCube); |
| pNew->z = 1; |
| pNew->q = ComputeQCost(vCube); |
| // set the ID |
| pNew->ID = g_CoverInfo.cIDs++; |
| // skip through zero-ID |
| if ( g_CoverInfo.cIDs == 256 ) |
| g_CoverInfo.cIDs = 1; |
| |
| // add this cube to storage |
| CheckForCloseCubes( pNew, 1 ); |
| |
| g_CoverInfo.nLiteralsBefore += Vec_IntSize(vCube); |
| g_CoverInfo.QCostBefore += ComputeQCost(vCube); |
| } |
| ABC_FREE( s_Level2Var ); |
| ABC_FREE( s_LevelValues ); |
| |
| assert ( g_CoverInfo.nCubesInUse + g_CoverInfo.nCubesFree == g_CoverInfo.nCubesAlloc ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Performs heuristic minimization of ESOPs.] |
| |
| Description [Returns 1 on success, 0 on failure.] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Exorcism( Vec_Wec_t * vEsop, int nIns, int nOuts, char * pFileNameOut ) |
| { |
| abctime clk1; |
| int RemainderBits; |
| int TotalWords; |
| int MemTemp, MemTotal; |
| |
| /////////////////////////////////////////////////////////////////////// |
| // STEPS of HEURISTIC ESOP MINIMIZATION |
| /////////////////////////////////////////////////////////////////////// |
| /////////////////////////////////////////////////////////////////////// |
| // STEP 1: determine the size of the starting cover |
| /////////////////////////////////////////////////////////////////////// |
| assert( nIns > 0 ); |
| // inputs |
| RemainderBits = (nIns*2)%(sizeof(unsigned)*8); |
| TotalWords = (nIns*2)/(sizeof(unsigned)*8) + (RemainderBits > 0); |
| g_CoverInfo.nVarsIn = nIns; |
| g_CoverInfo.nWordsIn = TotalWords; |
| // outputs |
| RemainderBits = (nOuts)%(sizeof(unsigned)*8); |
| TotalWords = (nOuts)/(sizeof(unsigned)*8) + (RemainderBits > 0); |
| g_CoverInfo.nVarsOut = nOuts; |
| g_CoverInfo.nWordsOut = TotalWords; |
| g_CoverInfo.cIDs = 1; |
| |
| // cubes |
| clk1 = Abc_Clock(); |
| // g_CoverInfo.nCubesBefore = CountTermsInPseudoKroneckerCover( g_Func.dd, nOuts ); |
| g_CoverInfo.nCubesBefore = Vec_WecSize(vEsop); |
| g_CoverInfo.TimeStart = Abc_Clock() - clk1; |
| |
| if ( g_CoverInfo.Verbosity ) |
| { |
| printf( "Starting cover generation time is %.2f sec\n", TICKS_TO_SECONDS(g_CoverInfo.TimeStart) ); |
| printf( "The number of cubes in the starting cover is %d\n", g_CoverInfo.nCubesBefore ); |
| } |
| |
| if ( g_CoverInfo.nCubesBefore > g_CoverInfo.nCubesMax ) |
| { |
| printf( "\nThe size of the starting cover is more than %d cubes. Quitting...\n", g_CoverInfo.nCubesMax ); |
| return 0; |
| } |
| |
| /////////////////////////////////////////////////////////////////////// |
| // STEP 2: prepare internal data structures |
| /////////////////////////////////////////////////////////////////////// |
| g_CoverInfo.nCubesAlloc = g_CoverInfo.nCubesBefore + ADDITIONAL_CUBES; |
| |
| // allocate cube cover |
| MemTotal = 0; |
| MemTemp = AllocateCover( g_CoverInfo.nCubesAlloc, g_CoverInfo.nWordsIn, g_CoverInfo.nWordsOut ); |
| if ( MemTemp == 0 ) |
| { |
| printf( "Unexpected memory allocation problem. Quitting...\n" ); |
| return 0; |
| } |
| else |
| MemTotal += MemTemp; |
| |
| // allocate cube sets |
| MemTemp = AllocateCubeSets( g_CoverInfo.nVarsIn, g_CoverInfo.nVarsOut ); |
| if ( MemTemp == 0 ) |
| { |
| printf( "Unexpected memory allocation problem. Quitting...\n" ); |
| return 0; |
| } |
| else |
| MemTotal += MemTemp; |
| |
| // allocate adjacency queques |
| MemTemp = AllocateQueques( g_CoverInfo.nCubesAlloc*g_CoverInfo.nCubesAlloc/CUBE_PAIR_FACTOR ); |
| if ( MemTemp == 0 ) |
| { |
| printf( "Unexpected memory allocation problem. Quitting...\n" ); |
| return 0; |
| } |
| else |
| MemTotal += MemTemp; |
| |
| if ( g_CoverInfo.Verbosity ) |
| printf( "Dynamically allocated memory is %dK\n", MemTotal/1000 ); |
| |
| /////////////////////////////////////////////////////////////////////// |
| // STEP 3: write the cube cover into the allocated storage |
| /////////////////////////////////////////////////////////////////////// |
| /////////////////////////////////////////////////////////////////////// |
| clk1 = Abc_Clock(); |
| if ( g_CoverInfo.Verbosity ) |
| printf( "Generating the starting cover...\n" ); |
| AddCubesToStartingCover( vEsop ); |
| /////////////////////////////////////////////////////////////////////// |
| |
| /////////////////////////////////////////////////////////////////////// |
| // STEP 4: iteratively improve the cover |
| /////////////////////////////////////////////////////////////////////// |
| if ( g_CoverInfo.Verbosity ) |
| printf( "Performing minimization...\n" ); |
| clk1 = Abc_Clock(); |
| ReduceEsopCover(); |
| g_CoverInfo.TimeMin = Abc_Clock() - clk1; |
| // g_Func.TimeMin = (float)(Abc_Clock() - clk1)/(float)(CLOCKS_PER_SEC); |
| if ( g_CoverInfo.Verbosity ) |
| { |
| printf( "\nMinimization time is %.2f sec\n", TICKS_TO_SECONDS(g_CoverInfo.TimeMin) ); |
| printf( "\nThe number of cubes after minimization is %d\n", g_CoverInfo.nCubesInUse ); |
| } |
| |
| /////////////////////////////////////////////////////////////////////// |
| // STEP 5: save the cover into file |
| /////////////////////////////////////////////////////////////////////// |
| // if option is MULTI_OUTPUT, the output is written into the output file; |
| // if option is SINGLE_NODE, the output is added to the input file |
| // and written into the output file; in this case, the minimized nodes is |
| // also stored in the temporary file "temp.blif" for verification |
| |
| // create the file name and write the output |
| { |
| char Buffer[1000]; |
| sprintf( Buffer, "%s", pFileNameOut ? pFileNameOut : "temp.esop" ); |
| WriteResultIntoFile( Buffer ); |
| if ( g_CoverInfo.Verbosity ) |
| printf( "Minimized cover has been written into file <%s>\n", Buffer ); |
| } |
| |
| /////////////////////////////////////////////////////////////////////// |
| // STEP 6: delocate memory |
| /////////////////////////////////////////////////////////////////////// |
| DelocateCubeSets(); |
| DelocateCover(); |
| DelocateQueques(); |
| |
| // return success |
| return 1; |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Abc_ExorcismMain( Vec_Wec_t * vEsop, int nIns, int nOuts, char * pFileNameOut, int Quality, int Verbosity, int nCubesMax, int fUseQCost ) |
| { |
| memset( &g_CoverInfo, 0, sizeof(cinfo) ); |
| g_CoverInfo.Quality = Quality; |
| g_CoverInfo.Verbosity = Verbosity; |
| g_CoverInfo.nCubesMax = nCubesMax; |
| g_CoverInfo.fUseQCost = fUseQCost; |
| if ( fUseQCost ) |
| s_fDecreaseLiterals = 1; |
| if ( g_CoverInfo.Verbosity ) |
| { |
| printf( "\nEXORCISM, Ver.4.7: Exclusive Sum-of-Product Minimizer\n" ); |
| printf( "by Alan Mishchenko, Portland State University, July-September 2000\n\n" ); |
| printf( "Incoming ESOP has %d inputs, %d outputs, and %d cubes.\n", nIns, nOuts, Vec_WecSize(vEsop) ); |
| } |
| PrepareBitSetModule(); |
| if ( Exorcism( vEsop, nIns, nOuts, pFileNameOut ) == 0 ) |
| { |
| printf( "Something went wrong when minimizing the cover\n" ); |
| return 0; |
| } |
| return 1; |
| } |
| |
| |
| |
| /////////////////////////////////////////////////////////////////// |
| //////////// End of File ///////////////// |
| /////////////////////////////////////////////////////////////////// |
| |
| |
| ABC_NAMESPACE_IMPL_END |
| |
