llb1Sched.c

Go to the documentation of this file.

/**CFile****************************************************************

  FileName    [llb1Sched.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [BDD based reachability.]

  Synopsis    [Partition scheduling algorithm.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - June 20, 2005.]

  Revision    [$Id: llb1Sched.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]

***********************************************************************/

#include "llbInt.h"

ABC_NAMESPACE_IMPL_START


////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

/**Function*************************************************************

  Synopsis    [Swaps two rows.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Llb_MtrSwapColumns( Llb_Mtr_t * p, int iCol1, int iCol2 )
{
    Llb_Grp_t * pGemp;
    char * pTemp;
    int iTemp;
    assert( iCol1 >= 0 && iCol1 < p->nCols );
    assert( iCol2 >= 0 && iCol2 < p->nCols );
    if ( iCol1 == iCol2 )
        return;
    assert( iCol1 != iCol2 );
    // swap col groups
    pGemp = p->pColGrps[iCol1];
    p->pColGrps[iCol1] = p->pColGrps[iCol2];
    p->pColGrps[iCol2] = pGemp;
    // swap col vectors
    pTemp = p->pMatrix[iCol1];
    p->pMatrix[iCol1] = p->pMatrix[iCol2];
    p->pMatrix[iCol2] = pTemp;
    // swap col sums
    iTemp = p->pColSums[iCol1];
    p->pColSums[iCol1] = p->pColSums[iCol2];
    p->pColSums[iCol2] = iTemp;
}

/**Function*************************************************************

  Synopsis    [Find columns which brings as few vars as possible.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Llb_MtrFindBestColumn( Llb_Mtr_t * p, int iGrpStart )
{
    int Cost, Cost2, CostBest = ABC_INFINITY, Cost2Best = ABC_INFINITY;
    int WeightCur, WeightBest = -ABC_INFINITY, iGrp = -1, iGrpBest = -1;
    int k, c, iVar, Counter;
    // find partition that reduces partial product as much as possible
    for ( iVar = 0; iVar < p->nRows - p->nFfs; iVar++ )
    { 
        if ( p->pRowSums[iVar] < 2 )
            continue;
        // look at present variables that can be quantified
        if ( !(p->pProdVars[iVar] == 1 && p->pProdNums[iVar] == 1) )
            continue;
        // check that it appears in one partition only
        Counter = 0;
        for ( c = iGrpStart; c < p->nCols-1; c++ )
            if ( p->pMatrix[c][iVar] == 1 )
            {
                iGrp = c;
                Counter++;
            }
        assert( Counter == 1 );
        if ( Counter != 1 )
            Abc_Print( -1, "Llb_MtrFindBestColumn() Internal error!\n" );
        // find weight of this column
        WeightCur = 0;
        for ( k = 0; k < p->nRows; k++ )
        {
            // increase weight if variable k will be quantified from partial product
            if ( p->pProdVars[k] == 1 && p->pMatrix[iGrp][k] == 1 && p->pProdNums[k] == 1 ) 
                WeightCur += 2;
            // decrease weight if variable k will be added to partial product
            if ( p->pProdVars[k] == 0 && p->pMatrix[iGrp][k] == 1 )
                WeightCur--;
        }
        if ( WeightCur > 0 && WeightBest < WeightCur )
        {
            WeightBest = WeightCur;
            iGrpBest   = iGrp;
        }
    }
    if ( iGrpBest >= 0 )
        return iGrpBest;
    // could not find the group with any vars to quantify
    // select the group that contains as few extra variables as possible
    // if there is a tie, select variables that appear in less groups than others
    for ( iGrp = iGrpStart; iGrp < p->nCols-1; iGrp++ )
    {
        Cost = Cost2 = 0;
        for ( k = 0; k < p->nRows; k++ )
            if ( p->pProdVars[k] == 0 && p->pMatrix[iGrp][k] == 1 )
            {
                Cost++;
                Cost2 += p->pProdNums[k];
            }
        if ( CostBest >  Cost || 
            (CostBest == Cost && Cost2 > Cost2Best) )
        {
            CostBest  = Cost;
            Cost2Best = Cost2;
            iGrpBest  = iGrp;
        }
    }
    return iGrpBest;
}

/**Function*************************************************************

  Synopsis    [Returns the number of variables that will be saved.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Llb_MtrUseSelectedColumn( Llb_Mtr_t * p, int iCol )
{
    int iVar;
    assert( iCol >= 1 && iCol < p->nCols - 1 );
    for ( iVar = 0; iVar < p->nRows; iVar++ )
    {
        if ( p->pMatrix[iCol][iVar] == 0 )
            continue;
        if ( p->pProdVars[iVar] == 1 && p->pProdNums[iVar] == 1 )
        {
            p->pProdVars[iVar] = 0;
            p->pProdNums[iVar] = 0;
            continue;
        }
        if ( p->pProdVars[iVar] == 0 )
        {
            p->pProdVars[iVar] = 1;
            p->pProdNums[iVar] = p->pRowSums[iVar];
        }
        p->pProdNums[iVar]--;
        assert( p->pProdNums[iVar] >= 0 );
        if ( p->pProdNums[iVar] < 0 )
            Abc_Print( -1, "Llb_MtrUseSelectedColumn() Internal error!\n" );
    }
}

/**Function*************************************************************

  Synopsis    [Verify columns.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Llb_MtrVerifyColumns( Llb_Mtr_t * p, int iGrpStart )
{
    int iVar, iGrp, Counter;
    for ( iVar = 0; iVar < p->nRows; iVar++ )
    {
        if ( p->pProdVars[iVar] == 0 )
            continue;
        Counter = 0;
        for ( iGrp = iGrpStart; iGrp < p->nCols; iGrp++ )
            if ( p->pMatrix[iGrp][iVar] == 1 )
                Counter++;
        assert( Counter == p->pProdNums[iVar] );
        if ( Counter != p->pProdNums[iVar] )
            Abc_Print( -1, "Llb_MtrVerifyColumns(): Internal error.\n" );
    }
}

/**Function*************************************************************

  Synopsis    [Matrix reduce.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Llb_MtrSchedule( Llb_Mtr_t * p )
{
    int iGrp, iGrpBest, i;
    // start partial product
    for ( i = 0; i < p->nRows; i++ )
    {
        if ( i >= p->nPis && i < p->nPis + p->nFfs )
        {
            p->pProdVars[i] = 1;
            p->pProdNums[i] = p->pRowSums[i] - 1;
        }
        else 
        {
            p->pProdVars[i] = 0;
            p->pProdNums[i] = p->pRowSums[i];
        }
    }
    // order the partitions
    Llb_MtrVerifyMatrix( p );
    for ( iGrp = 1; iGrp < p->nCols-1; iGrp++ )
    {
        Llb_MtrVerifyColumns( p, iGrp );
        iGrpBest = Llb_MtrFindBestColumn( p, iGrp );
        Llb_MtrUseSelectedColumn( p, iGrpBest );
        Llb_MtrSwapColumns( p, iGrp, iGrpBest );
    }
    Llb_MtrVerifyMatrix( p );
}

////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


ABC_NAMESPACE_IMPL_END