retLvalue.c File Reference

#include "retInt.h"

Go to the source code of this file.

Enumerations
enum	{ ABC_RET_UPDATE_FAIL, ABC_RET_UPDATE_NO, ABC_RET_UPDATE_YES }
	DECLARATIONS ///. More...

Functions
static Vec_Int_t *	Abc_NtkRetimeGetLags (Abc_Ntk_t *pNtk, int nIterLimit, int fVerbose)
static int	Abc_NtkRetimeSearch_rec (Abc_Ntk_t *pNtk, Vec_Ptr_t *vNodes, Vec_Ptr_t *vLatches, int FiMin, int FiMax, int nMaxIters, int fVerbose)
static int	Abc_NtkRetimeForPeriod (Abc_Ntk_t *pNtk, Vec_Ptr_t *vNodes, Vec_Ptr_t *vLatches, int Fi, int nMaxIters, int fVerbose)
static int	Abc_NtkRetimeUpdateLValue (Abc_Ntk_t *pNtk, Vec_Ptr_t *vNodes, Vec_Ptr_t *vLatches, int Fi)
static int	Abc_NtkRetimePosOverLimit (Abc_Ntk_t *pNtk, int Fi)
static Vec_Ptr_t *	Abc_ManCollectLatches (Abc_Ntk_t *pNtk)
static int	Abc_NtkRetimeUsingLags (Abc_Ntk_t *pNtk, Vec_Int_t *vLags, int fVerbose)
static int	Abc_NodeComputeLag (int LValue, int Fi)
static int	Abc_NodeGetLValue (Abc_Obj_t *pNode)
static void	Abc_NodeSetLValue (Abc_Obj_t *pNode, int Value)
int	Abc_NtkRetimeLValue (Abc_Ntk_t *pNtk, int nIterLimit, int fVerbose)
	FUNCTION DEFINITIONS ///. More...
void	Abc_ManCollectLatches_rec (Abc_Obj_t *pObj, Vec_Ptr_t *vLatches)

Enumeration Type Documentation

anonymous enum

DECLARATIONS ///.

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

FileName [retLvalue.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Retiming package.]

Synopsis [Implementation of Pan's retiming algorithm.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - Oct 31, 2006.]

Revision [

Id:

retLvalue.c,v 1.00 2006/10/31 00:00:00 alanmi Exp

]

Enumerator
ABC_RET_UPDATE_FAIL
ABC_RET_UPDATE_NO
ABC_RET_UPDATE_YES

Definition at line 31 of file retLvalue.c.

{ ABC_RET_UPDATE_FAIL, ABC_RET_UPDATE_NO, ABC_RET_UPDATE_YES };

Function Documentation

Vec_Ptr_t * Abc_ManCollectLatches ( Abc_Ntk_t *  pNtk )

static

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

Synopsis [Collects latches in the topological order.]

Description []

SideEffects []

SeeAlso []

Definition at line 338 of file retLvalue.c.

{
    Vec_Ptr_t * vLatches;
    Abc_Obj_t * pObj;
    int i;
    vLatches = Vec_PtrAlloc( Abc_NtkLatchNum(pNtk) );
    Abc_NtkIncrementTravId( pNtk );
    Abc_NtkForEachLatch( pNtk, pObj, i )
        Abc_ManCollectLatches_rec( pObj, vLatches );
    assert( Vec_PtrSize(vLatches) == Abc_NtkLatchNum(pNtk) );
    return vLatches;
}

void Abc_ManCollectLatches_rec	(	Abc_Obj_t *	pObj,
		Vec_Ptr_t *	vLatches
	)

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

Synopsis [Collects latches in the topological order.]

Description []

SideEffects []

SeeAlso []

Definition at line 309 of file retLvalue.c.

{
    Abc_Obj_t * pDriver;
    if ( !Abc_ObjIsLatch(pObj) )
        return;
    // skip already collected latches
    if ( Abc_NodeIsTravIdCurrent(pObj)  )
        return;
    Abc_NodeSetTravIdCurrent(pObj);
    // get the driver node feeding into the latch
    pDriver = Abc_ObjFanin0(Abc_ObjFanin0(pObj));
    // call recursively if the driver looks like a latch output
    if ( Abc_ObjIsBo(pDriver) )
        Abc_ManCollectLatches_rec( Abc_ObjFanin0(pDriver), vLatches );
    // collect the latch
    Vec_PtrPush( vLatches, pObj );
}

static int Abc_NodeComputeLag ( int  LValue, int  Fi  )

inlinestatic

Definition at line 42 of file retLvalue.c.

{ return (LValue + (1<<16)*Fi)/Fi - (1<<16) - (int)(LValue % Fi == 0);     }

static int Abc_NodeGetLValue ( Abc_Obj_t *  pNode )

inlinestatic

Definition at line 43 of file retLvalue.c.

{ return (int)(ABC_PTRUINT_T)pNode->pCopy;        }

static void Abc_NodeSetLValue ( Abc_Obj_t *  pNode, int  Value  )

inlinestatic

Definition at line 44 of file retLvalue.c.

{ pNode->pCopy = (Abc_Obj_t *)(ABC_PTRUINT_T)Value;    }

int Abc_NtkRetimeForPeriod ( Abc_Ntk_t *  pNtk, Vec_Ptr_t *  vNodes, Vec_Ptr_t *  vLatches, int  Fi, int  nMaxIters, int  fVerbose  )

static

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

Synopsis [Returns 1 if retiming with this clock period is feasible.]

Description []

SideEffects []

SeeAlso []

Definition at line 196 of file retLvalue.c.

{
    Abc_Obj_t * pObj;
    int c, i, fConverged;
    // set l-values of all nodes to be minus infinity, except PIs and constants
    Abc_NtkForEachObj( pNtk, pObj, i )
        if ( Abc_ObjFaninNum(pObj) == 0 )
            Abc_NodeSetLValue( pObj, 0 );
        else
            Abc_NodeSetLValue( pObj, -ABC_INFINITY );
    // update all values iteratively
    fConverged = 0;
    for ( c = 1; c <= nMaxIters; c++ )
    {
        if ( !Abc_NtkRetimeUpdateLValue( pNtk, vNodes, vLatches, Fi ) )
        {
            fConverged = 1;
            break;
        }
        if ( Abc_NtkRetimePosOverLimit(pNtk, Fi) )
            break;
    }
    // report the results
    if ( fVerbose )
    {
        if ( !fConverged )
            printf( "Period = %3d.  Iterations = %3d.    Infeasible %s\n", Fi, c, (c > nMaxIters)? "(timeout)" : "" );
        else
            printf( "Period = %3d.  Iterations = %3d.      Feasible\n",    Fi, c );
    }
/*
    // check if any AND gates have infinite delay
    Counter = 0;
    Abc_NtkForEachNode( pNtk, pObj, i )
        Counter += (Abc_NodeGetLValue(pObj) < -ABC_INFINITY/2);
    if ( Counter > 0 )
        printf( "Warning: %d internal nodes have wrong l-values!\n", Counter );
*/
    return fConverged;
}

Vec_Int_t * Abc_NtkRetimeGetLags ( Abc_Ntk_t *  pNtk, int  nIterLimit, int  fVerbose  )

static

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

Synopsis [Computes the retiming lags.]

Description []

SideEffects []

SeeAlso []

Definition at line 91 of file retLvalue.c.

{
    Vec_Int_t * vLags;
    Vec_Ptr_t * vNodes, * vLatches;
    Abc_Obj_t * pNode;
    int i, FiMax, FiBest, RetValue;
    abctime clk, clkIter;
    char NodeLag;

    // get the upper bound on the clock period
    FiMax = Abc_NtkLevel(pNtk);

    // make sure this clock period is feasible
    vNodes = Abc_NtkDfs( pNtk, 0 );
    vLatches = Abc_ManCollectLatches( pNtk );
    if ( !Abc_NtkRetimeForPeriod( pNtk, vNodes, vLatches, FiMax, nIterLimit, fVerbose ) )
    {
        Vec_PtrFree( vLatches );
        Vec_PtrFree( vNodes );
        printf( "Abc_NtkRetimeGetLags() error: The upper bound on the clock period cannot be computed.\n" );
        return Vec_IntStart( Abc_NtkObjNumMax(pNtk) + 1 );
    }
 
    // search for the optimal clock period between 0 and nLevelMax
clk = Abc_Clock();
    FiBest = Abc_NtkRetimeSearch_rec( pNtk, vNodes, vLatches, 0, FiMax, nIterLimit, fVerbose );
clkIter = Abc_Clock() - clk;

    // recompute the best l-values
    RetValue = Abc_NtkRetimeForPeriod( pNtk, vNodes, vLatches, FiBest, nIterLimit, fVerbose );
    assert( RetValue );

    // fix the problem with non-converged delays
    Abc_NtkForEachNode( pNtk, pNode, i )
        if ( Abc_NodeGetLValue(pNode) < -ABC_INFINITY/2 )
            Abc_NodeSetLValue( pNode, 0 );

    // write the retiming lags
    vLags = Vec_IntStart( Abc_NtkObjNumMax(pNtk) + 1 );
    Abc_NtkForEachNode( pNtk, pNode, i )
    {
        NodeLag = Abc_NodeComputeLag( Abc_NodeGetLValue(pNode), FiBest );
        Vec_IntWriteEntry( vLags, pNode->Id, NodeLag );
    }
/*
    Abc_NtkForEachPo( pNtk, pNode, i )
        printf( "%d ", Abc_NodeGetLValue(Abc_ObjFanin0(pNode)) );
    printf( "\n" );
    Abc_NtkForEachLatch( pNtk, pNode, i )
        printf( "%d/%d ", Abc_NodeGetLValue(Abc_ObjFanout0(pNode)), Abc_NodeGetLValue(Abc_ObjFanout0(pNode)) + FiBest );
    printf( "\n" );
*/

    // print the result
//    if ( fVerbose )
    printf( "The best clock period is %3d. (Currently, network is not modified.)\n", FiBest );
/*
    {
        FILE * pTable;
        pTable = fopen( "iscas/seqmap__stats2.txt", "a+" );
        fprintf( pTable, "%d ", FiBest );
        fprintf( pTable, "\n" );
        fclose( pTable );
    }
*/
    Vec_PtrFree( vNodes );
    Vec_PtrFree( vLatches );
    return vLags;
}

int Abc_NtkRetimeLValue	(	Abc_Ntk_t *	pNtk,
		int	nIterLimit,
		int	fVerbose
	)

FUNCTION DEFINITIONS ///.

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

Synopsis [Implements Pan's retiming algorithm.]

Description []

SideEffects []

SeeAlso []

Definition at line 61 of file retLvalue.c.

{
    Vec_Int_t * vLags;
    int nLatches = Abc_NtkLatchNum(pNtk);
    assert( Abc_NtkIsLogic( pNtk ) );
    // get the lags
    vLags = Abc_NtkRetimeGetLags( pNtk, nIterLimit, fVerbose );
    // compute the retiming
//    Abc_NtkRetimeUsingLags( pNtk, vLags, fVerbose );
    Vec_IntFree( vLags );
    // fix the COs
//    Abc_NtkLogicMakeSimpleCos( pNtk, 0 );
    // check for correctness
    if ( !Abc_NtkCheck( pNtk ) )
        fprintf( stdout, "Abc_NtkRetimeLValue(): Network check has failed.\n" );
    // return the number of latches saved
    return nLatches - Abc_NtkLatchNum(pNtk);
}

int Abc_NtkRetimePosOverLimit ( Abc_Ntk_t *  pNtk, int  Fi  )

static

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

Synopsis [Detects the case when l-values exceeded the limit.]

Description []

SideEffects []

SeeAlso []

Definition at line 288 of file retLvalue.c.

{
    Abc_Obj_t * pObj;
    int i;
    Abc_NtkForEachPo( pNtk, pObj, i )
        if ( Abc_NodeGetLValue(Abc_ObjFanin0(pObj)) > Fi )
            return 1;
    return 0;
}

int Abc_NtkRetimeSearch_rec ( Abc_Ntk_t *  pNtk, Vec_Ptr_t *  vNodes, Vec_Ptr_t *  vLatches, int  FiMin, int  FiMax, int  nMaxIters, int  fVerbose  )

static

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

Synopsis [Performs binary search for the optimal clock period.]

Description [Assumes that FiMin is infeasible while FiMax is feasible.]

SideEffects []

SeeAlso []

Definition at line 172 of file retLvalue.c.

{
    int Median;
    assert( FiMin < FiMax );
    if ( FiMin + 1 == FiMax )
        return FiMax;
    Median = FiMin + (FiMax - FiMin)/2;
    if ( Abc_NtkRetimeForPeriod( pNtk, vNodes, vLatches, Median, nMaxIters, fVerbose ) )
        return Abc_NtkRetimeSearch_rec( pNtk, vNodes, vLatches, FiMin, Median, nMaxIters, fVerbose ); // Median is feasible
    else 
        return Abc_NtkRetimeSearch_rec( pNtk, vNodes, vLatches, Median, FiMax, nMaxIters, fVerbose ); // Median is infeasible
}

int Abc_NtkRetimeUpdateLValue ( Abc_Ntk_t *  pNtk, Vec_Ptr_t *  vNodes, Vec_Ptr_t *  vLatches, int  Fi  )

static

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

Synopsis [Performs one iteration of l-value computation for the nodes.]

Description [Experimentally it was found that checking POs changes is not enough to detect the convergence of l-values in the network.]

SideEffects []

SeeAlso []

Definition at line 249 of file retLvalue.c.

{
    Abc_Obj_t * pObj, * pFanin;
    int i, k, lValueNew, fChange;
    // go through the nodes and detect change
    fChange = 0;
    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
    {
        assert( Abc_ObjIsNode(pObj) );
        lValueNew = -ABC_INFINITY;
        Abc_ObjForEachFanin( pObj, pFanin, k )
        {
            if ( lValueNew < Abc_NodeGetLValue(pFanin) )
                lValueNew = Abc_NodeGetLValue(pFanin);
        }
        lValueNew++;
        if ( Abc_NodeGetLValue(pObj) < lValueNew )
        {
            Abc_NodeSetLValue( pObj, lValueNew );
            fChange = 1;
        }
    }
    // propagate values through the latches
    Vec_PtrForEachEntry( Abc_Obj_t *, vLatches, pObj, i )
        Abc_NodeSetLValue( Abc_ObjFanout0(pObj), Abc_NodeGetLValue(Abc_ObjFanin0(Abc_ObjFanin0(pObj))) - Fi );
    return fChange;
}

int Abc_NtkRetimeUsingLags ( Abc_Ntk_t *  pNtk, Vec_Int_t *  vLags, int  fVerbose  )

static

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

Synopsis [Implements the retiming given as the array of retiming lags.]

Description []

SideEffects []

SeeAlso []

Definition at line 362 of file retLvalue.c.

{
    Abc_Obj_t * pObj;
    int fChanges, fForward, nTotalMoves, Lag, Counter, i;
    // iterate over the nodes
    nTotalMoves = 0;
    do {
        fChanges = 0;
        Abc_NtkForEachNode( pNtk, pObj, i )
        {
            Lag = Vec_IntEntry( vLags, pObj->Id );
            if ( !Lag )
                continue;
            fForward = (Lag < 0);
            if ( Abc_NtkRetimeNodeIsEnabled( pObj, fForward ) )
            {
                Abc_NtkRetimeNode( pObj, fForward, 0 );
                fChanges = 1;
                nTotalMoves++;
                Vec_IntAddToEntry( vLags, pObj->Id, fForward? 1 : -1 );
            }
        }
    } while ( fChanges );
    if ( fVerbose )
        printf( "Total latch moves = %d.\n", nTotalMoves );
    // check if there are remaining lags
    Counter = 0;
    Abc_NtkForEachNode( pNtk, pObj, i )
        Counter += (Vec_IntEntry( vLags, pObj->Id ) != 0);
    if ( Counter )
        printf( "Warning! The number of nodes with unrealized lag = %d.\n", Counter );
    return 1;
}