Version abc60822

1 files changed, 567 insertions, 0 deletions

diff --git a/src/base/seq/seqMaxMeanCycle.c b/src/base/seq/seqMaxMeanCycle.c
new file mode 100644
index 00000000..46d73cbd
--- /dev/null
+++ b/src/base/seq/seqMaxMeanCycle.c
@@ -0,0 +1,567 @@
+/**CFile****************************************************************
+
+  FileName    [seqMaxMeanCycle.c]
+
+  SystemName  [ABC: Logic synthesis and verification system.]
+
+  PackageName [Construction and manipulation of sequential AIGs.]
+
+  Synopsis    [Efficient computation of maximum mean cycle times.]
+
+  Author      [Aaron P. Hurst]
+  
+  Affiliation [UC Berkeley]
+
+  Date        [Ver. 1.0. Started - May 15, 2006.]
+
+  Revision    [$Id: seqMaxMeanCycle.c,v 1.00 2005/05/15 00:00:00 ahurst Exp $]
+
+***********************************************************************/
+
+#include "seqInt.h"
+#include "hash.h"
+
+////////////////////////////////////////////////////////////////////////
+///                        DECLARATIONS                              ///
+////////////////////////////////////////////////////////////////////////
+
+struct Abc_ManTime_t_
+{
+    Abc_Time_t     tArrDef;
+    Abc_Time_t     tReqDef;
+    Vec_Ptr_t  *   vArrs;
+    Vec_Ptr_t  *   vReqs;
+};
+
+typedef struct Seq_HowardData_t_
+{
+  char   visited;
+  int    mark;
+  int    policy;
+  float  cycle;
+  float  skew;
+  float  delay;
+} Seq_HowardData_t;
+
+// accessing the arrival and required times of a node
+static inline Abc_Time_t * Abc_NodeArrival( Abc_Obj_t * pNode )  {  return pNode->pNtk->pManTime->vArrs->pArray[pNode->Id];  }
+static inline Abc_Time_t * Abc_NodeRequired( Abc_Obj_t * pNode ) {  return pNode->pNtk->pManTime->vReqs->pArray[pNode->Id];  }
+
+Hash_Ptr_t * Seq_NtkPathDelays( Abc_Ntk_t * pNtk, int fVerbose );
+void Seq_NtkMergePios( Abc_Ntk_t * pNtk, Hash_Ptr_t * hFwdDelays, int fVerbose );
+
+void Seq_NtkHowardLoop( Abc_Ntk_t * pNtk, Hash_Ptr_t * hFwdDelays,
+                        Hash_Ptr_t * hNodeData, int node,
+                        int *howardDepth, float *howardDelay, int *howardSink,
+                        float *maxMeanCycle);
+void Abc_NtkDfsReverse_rec2( Abc_Obj_t * pNode, Vec_Ptr_t * vNodes, Vec_Ptr_t * vEndpoints );
+
+#define Seq_NtkGetPathDelay( hFwdDelays, from, to ) \
+  (Hash_PtrExists(hFwdDelays, from)?Hash_FltEntry( ((Hash_Flt_t *)Hash_PtrEntry(hFwdDelays, from, 0)), to, 0):0 )
+
+#define HOWARD_EPSILON 1e-3
+#define ZERO_SLOP      1e-5
+#define REMOVE_ZERO_SLOP( x ) \
+  (x = (x > -ZERO_SLOP && x < ZERO_SLOP)?0:x)
+
+////////////////////////////////////////////////////////////////////////
+///                     FUNCTION DEFINITIONS                         ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+  Synopsis    [Computes maximum mean cycle time.]
+
+  Description [Uses Howard's algorithm.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+float Seq_NtkHoward( Abc_Ntk_t * pNtk, int fVerbose ) {
+
+  Abc_Obj_t *  pObj;
+  Hash_Ptr_t * hFwdDelays;
+  Hash_Flt_t * hOutgoing;
+  Hash_Ptr_Entry_t * pSourceEntry, * pNodeEntry;
+  Hash_Flt_Entry_t * pSinkEntry;
+  int          i, j, iteration = 0;
+  int          source, sink;
+  int          fChanged;
+  int          howardDepth, howardSink = 0;
+  float        delay, howardDelay, t;
+  float        maxMeanCycle = -ABC_INFINITY;
+  Hash_Ptr_t *       hNodeData;
+  Seq_HowardData_t * pNodeData, * pSourceData, * pSinkData;
+
+  // gather timing constraints
+  hFwdDelays = Seq_NtkPathDelays( pNtk, fVerbose );
+  Seq_NtkMergePios( pNtk, hFwdDelays, fVerbose );
+
+  // initialize data, create initial policy
+  hNodeData = Hash_PtrAlloc( hFwdDelays->nSize );
+  Hash_PtrForEachEntry( hFwdDelays, pSourceEntry, i ) {
+    Hash_PtrWriteEntry( hNodeData, pSourceEntry->key, 
+                        (pNodeData = ALLOC(Seq_HowardData_t, 1)) );
+    pNodeData->skew = 0.0;
+    pNodeData->policy = 0;
+    hOutgoing = (Hash_Flt_t *)(pSourceEntry->data);
+    assert(hOutgoing);
+
+    Hash_FltForEachEntry( hOutgoing, pSinkEntry, j ) {
+      sink = pSinkEntry->key;
+      delay = pSinkEntry->data;
+       if (delay > pNodeData->skew) {
+        pNodeData->policy = sink;
+        pNodeData->skew = delay;
+      }
+    }
+  }
+
+  // iteratively refine policy
+  do {
+    iteration++;
+    fChanged = 0;
+    howardDelay = 0.0;
+    howardDepth = 0;
+
+    // reset data
+    Hash_PtrForEachEntry( hNodeData, pNodeEntry, i ) {
+      pNodeData = (Seq_HowardData_t *)pNodeEntry->data;
+      pNodeData->skew = -ABC_INFINITY;
+      pNodeData->cycle = -ABC_INFINITY;
+      pNodeData->mark = 0;
+      pNodeData->visited = 0;
+    }
+
+    // find loops in policy graph
+    Hash_PtrForEachEntry( hNodeData, pNodeEntry, i ) {
+      pNodeData = (Seq_HowardData_t *)(pNodeEntry->data);
+      assert(pNodeData);
+      if (!pNodeData->visited)
+        Seq_NtkHowardLoop( pNtk, hFwdDelays, 
+                           hNodeData, pNodeEntry->key,
+                           &howardDepth, &howardDelay, &howardSink, &maxMeanCycle);
+    }
+
+    if (!howardSink) {
+      return -1;
+    }
+
+    // improve policy by tightening loops
+    Hash_PtrForEachEntry( hFwdDelays, pSourceEntry, i ) {
+      source = pSourceEntry->key;
+      pSourceData = (Seq_HowardData_t *)Hash_PtrEntry( hNodeData, source, 0 );
+      assert(pSourceData);
+      hOutgoing = (Hash_Flt_t *)(pSourceEntry->data);
+      assert(hOutgoing);
+      Hash_FltForEachEntry( hOutgoing, pSinkEntry, j ) {
+        sink = pSinkEntry->key;
+        pSinkData = (Seq_HowardData_t *)Hash_PtrEntry( hNodeData, sink, 0 );
+        assert(pSinkData);
+        delay = pSinkEntry->data;
+        
+        if (pSinkData->cycle > pSourceData->cycle + HOWARD_EPSILON) {
+          fChanged = 1;
+          pSourceData->cycle = pSinkData->cycle;
+          pSourceData->policy = sink;
+        }
+      }
+    }
+
+    // improve policy by correcting skews
+    if (!fChanged) {
+      Hash_PtrForEachEntry( hFwdDelays, pSourceEntry, i ) {
+        source = pSourceEntry->key;
+        pSourceData = (Seq_HowardData_t *)Hash_PtrEntry( hNodeData, source, 0 );
+        assert(pSourceData);
+        hOutgoing = (Hash_Flt_t *)(pSourceEntry->data);
+        assert(hOutgoing);
+        Hash_FltForEachEntry( hOutgoing, pSinkEntry, j ) {
+          sink = pSinkEntry->key;
+          pSinkData = (Seq_HowardData_t *)Hash_PtrEntry( hNodeData, sink, 0 );
+          assert(pSinkData);
+          delay = pSinkEntry->data;
+
+          if (pSinkData->cycle < 0.0 || pSinkData->cycle < pSourceData->cycle)
+            continue;
+
+          t = delay - pSinkData->cycle + pSinkData->skew;
+          if (t > pSourceData->skew + HOWARD_EPSILON) {
+            fChanged = 1;
+            pSourceData->skew = t;
+            pSourceData->policy = sink;
+          }
+        }
+      }
+    }
+
+    if (fVerbose) printf("Iteration %d \t Period = %.2f\n", iteration, maxMeanCycle);
+  } while (fChanged);
+
+  // set global skew, mmct
+  pNodeData = Hash_PtrEntry( hNodeData, -1, 0 );
+  pNtk->globalSkew = -pNodeData->skew;
+  pNtk->maxMeanCycle = maxMeanCycle;
+
+  // set endpoint skews
+  Vec_FltGrow( pNtk->vSkews, Abc_NtkLatchNum( pNtk ) );
+  pNtk->vSkews->nSize =  Abc_NtkLatchNum( pNtk );
+  Abc_NtkForEachLatch( pNtk, pObj, i ) {
+    pNodeData = Hash_PtrEntry( hNodeData, pObj->Id, 0 );
+    // skews are set based on latch # NOT id #
+    Abc_NtkSetLatSkew( pNtk, i, pNodeData->skew );
+  }
+
+  // free node data
+  Hash_PtrForEachEntry( hNodeData, pNodeEntry, i ) {
+    pNodeData = (Seq_HowardData_t *)(pNodeEntry->data);
+    FREE( pNodeData );
+  }
+  Hash_PtrFree(hNodeData);
+
+  // free delay data
+  Hash_PtrForEachEntry( hFwdDelays, pSourceEntry, i ) {
+    Hash_FltFree( (Hash_Flt_t *)(pSourceEntry->data) );
+  }
+  Hash_PtrFree(hFwdDelays);
+
+  return maxMeanCycle;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Computes the mean cycle times of current policy graph.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Seq_NtkHowardLoop( Abc_Ntk_t * pNtk, Hash_Ptr_t * hFwdDelays,
+                        Hash_Ptr_t * hNodeData, int node,
+                        int *howardDepth, float *howardDelay, int *howardSink,
+                        float *maxMeanCycle) {
+  
+  Seq_HowardData_t * pNodeData, *pToData;
+  float delay, t;
+
+  pNodeData = (Seq_HowardData_t *)Hash_PtrEntry( hNodeData, node, 0 );
+  assert(pNodeData);
+  pNodeData->visited = 1;
+  pNodeData->mark = ++(*howardDepth);
+  pNodeData->delay = (*howardDelay);
+  if (pNodeData->policy) {
+    pToData = (Seq_HowardData_t *)Hash_PtrEntry( hNodeData, pNodeData->policy, 0 );
+    assert(pToData);
+    delay = Seq_NtkGetPathDelay( hFwdDelays, node, pNodeData->policy );
+    assert(delay > 0.0);
+    (*howardDelay) += delay;
+    if (pToData->mark) {
+      t = (*howardDelay - pToData->delay) / (*howardDepth - pToData->mark + 1);
+      pNodeData->cycle = t;
+      pNodeData->skew = 0.0;
+      if (*maxMeanCycle < t) {
+        *maxMeanCycle = t;
+        *howardSink = pNodeData->policy;
+      }
+    } else {
+      if(!pToData->visited) {
+        Seq_NtkHowardLoop(pNtk, hFwdDelays, hNodeData, pNodeData->policy,
+                          howardDepth, howardDelay, howardSink, maxMeanCycle);
+      }
+      if(pToData->cycle > 0) {
+        t = delay - pToData->cycle + pToData->skew;
+    pNodeData->skew = t;
+    pNodeData->cycle = pToData->cycle;
+      }
+    }
+  }
+  *howardDelay = pNodeData->delay;
+  pNodeData->mark = 0;
+  --(*howardDepth);
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Computes the register-to-register delays.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Hash_Ptr_t * Seq_NtkPathDelays( Abc_Ntk_t * pNtk, int fVerbose ) {
+
+  Abc_Time_t * pTime, ** ppTimes;
+  Abc_Obj_t * pObj, * pDriver, * pStart, * pFanout;
+  Vec_Ptr_t * vNodes, * vEndpoints;
+  int i, j, nPaths = 0;
+  Hash_Flt_t *  hOutgoing;
+  Hash_Ptr_t *  hFwdDelays;
+  float     nMaxPath = 0, nSumPath = 0;
+
+  extern void Abc_NtkTimePrepare( Abc_Ntk_t * pNtk );
+  extern void Abc_NodeDelayTraceArrival( Abc_Obj_t * pNode );
+
+  if (fVerbose) printf("Gathering path delays...\n");
+
+  hFwdDelays = Hash_PtrAlloc( Abc_NtkCiNum( pNtk ) );
+
+  assert( Abc_NtkIsMappedLogic(pNtk) );
+
+  Abc_NtkTimePrepare( pNtk );
+  ppTimes = (Abc_Time_t **)pNtk->pManTime->vArrs->pArray;
+  vNodes = Vec_PtrAlloc( 100 );
+  vEndpoints = Vec_PtrAlloc( 100 );
+
+  // set the initial times (i.e. ignore all inputs)
+  Abc_NtkForEachObj( pNtk, pObj, i) {
+    pTime = ppTimes[pObj->Id];
+    pTime->Fall = pTime->Rise = pTime->Worst = -ABC_INFINITY;    
+  }
+
+  // starting at each Ci, compute timing forward
+  Abc_NtkForEachCi( pNtk, pStart, j ) {
+    
+    hOutgoing = Hash_FltAlloc( 10 );
+    Hash_PtrWriteEntry( hFwdDelays, pStart->Id, (void *)(hOutgoing) );
+
+    // seed the starting point of interest
+    pTime = ppTimes[pStart->Id];
+    pTime->Fall = pTime->Rise = pTime->Worst = 0.0;
+
+    // find a DFS ordering from the start
+    Abc_NtkIncrementTravId( pNtk );
+    Abc_NodeSetTravIdCurrent( pStart );
+    pObj = Abc_ObjFanout0Ntk(pStart);
+    Abc_ObjForEachFanout( pObj, pFanout, i )
+      Abc_NtkDfsReverse_rec2( pFanout, vNodes, vEndpoints );
+    if ( Abc_ObjIsCo( pStart ) )
+      Vec_PtrPush( vEndpoints, pStart );
+
+    // do timing analysis
+    for ( i = vNodes->nSize-1; i >= 0; --i )
+      Abc_NodeDelayTraceArrival( vNodes->pArray[i] );
+
+    // there is a path to each set of Co endpoints
+    Vec_PtrForEachEntry( vEndpoints, pObj, i )
+    {
+      assert(pObj);
+      assert( Abc_ObjIsCo( pObj ) );
+      pDriver = Abc_ObjFanin0(pObj);
+      pTime   = Abc_NodeArrival(pDriver);
+      if ( pTime->Worst > 0 ) {
+        Hash_FltWriteEntry( hOutgoing, pObj->Id, pTime->Worst );
+        nPaths++;
+        // if (fVerbose) printf("\tpath %d,%d delay = %f\n", pStart->Id, pObj->Id, pTime->Worst);
+        nSumPath += pTime->Worst;
+        if (pTime->Worst > nMaxPath)
+          nMaxPath = pTime->Worst;
+      }
+    }
+
+    // clear the times that were altered
+    for ( i = 0; i < vNodes->nSize; i++ ) {
+      pObj = (Abc_Obj_t *)(vNodes->pArray[i]);
+      pTime = ppTimes[pObj->Id];
+      pTime->Fall = pTime->Rise = pTime->Worst = -ABC_INFINITY;
+    }
+    pTime = ppTimes[pStart->Id];
+    pTime->Fall = pTime->Rise = pTime->Worst = -ABC_INFINITY;
+    
+    Vec_PtrClear( vNodes );
+    Vec_PtrClear( vEndpoints );
+  }
+
+  Vec_PtrFree( vNodes );
+
+  // rezero Cis (note: these should be restored to values if they were nonzero)
+  Abc_NtkForEachCi( pNtk, pObj, i) {
+    pTime = ppTimes[pObj->Id];
+    pTime->Fall = pTime->Rise = pTime->Worst = 0.0;    
+  }
+
+  if (fVerbose) printf("Num. paths = %d\tMax. Path Delay = %.2f\tAvg. Path Delay = %.2f\n", nPaths, nMaxPath, nSumPath / nPaths);
+  return hFwdDelays;
+}
+
+
+/**Function*************************************************************
+
+  Synopsis    [Merges all the Pios together into one ID = -1.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Seq_NtkMergePios( Abc_Ntk_t * pNtk, Hash_Ptr_t * hFwdDelays, 
+                       int fVerbose ) {
+
+  Abc_Obj_t *        pObj;
+  Hash_Flt_Entry_t * pSinkEntry;
+  Hash_Ptr_Entry_t * pSourceEntry;
+  Hash_Flt_t *       hOutgoing, * hPioSource;
+  int                i, j;
+  int                source, sink, nMerges = 0;
+  float              delay = 0, max_delay = 0;
+  Vec_Int_t *        vFreeList;
+
+  vFreeList = Vec_IntAlloc( 10 );
+
+  // create a new "-1" source entry for the Pios
+  hPioSource = Hash_FltAlloc( 100 );
+  Hash_PtrWriteEntry( hFwdDelays, -1, (void *)(hPioSource) );
+
+  // merge all edges with a Pio as a source
+  Abc_NtkForEachPi( pNtk, pObj, i ) {
+    source = pObj->Id;
+    hOutgoing = (Hash_Flt_t *)Hash_PtrEntry( hFwdDelays, source, 0 );
+    if (!hOutgoing) continue;
+
+    Hash_PtrForEachEntry( hOutgoing, pSinkEntry, j ) {
+      nMerges++;
+      sink = pSinkEntry->key;
+      delay = pSinkEntry->data;
+      if (Hash_FltEntry( hPioSource, sink, 1 ) < delay) {
+        Hash_FltWriteEntry( hPioSource, sink, delay );
+      }
+    }
+
+    Hash_FltFree( hOutgoing );
+    Hash_PtrRemove( hFwdDelays, source );
+  }
+
+  // merge all edges with a Pio as a sink
+  Hash_PtrForEachEntry( hFwdDelays, pSourceEntry, i ) {
+    hOutgoing = (Hash_Flt_t *)(pSourceEntry->data);
+    Hash_FltForEachEntry( hOutgoing, pSinkEntry, j ) {
+      sink = pSinkEntry->key;
+      delay = pSinkEntry->data;
+
+      max_delay = -ABC_INFINITY;
+      if (Abc_ObjIsPo( Abc_NtkObj( pNtk, sink ) )) {
+        nMerges++;
+        if (delay > max_delay)
+          max_delay = delay;
+        Vec_IntPush( vFreeList, sink );
+      }
+    }
+    if (max_delay != -ABC_INFINITY)
+      Hash_FltWriteEntry( hOutgoing, -1, delay );
+    // do freeing
+    while( vFreeList->nSize > 0 ) {
+      Hash_FltRemove( hOutgoing, Vec_IntPop( vFreeList ) );
+    }
+  }
+
+  if (fVerbose) printf("Merged %d paths into one Pio node\n", nMerges);
+
+}
+
+/**Function*************************************************************
+
+  Synopsis    [This is a modification of routine from abcDfs.c]
+
+  Description [Recursive DFS from a starting point.  Keeps the endpoints.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Abc_NtkDfsReverse_rec2( Abc_Obj_t * pNode, Vec_Ptr_t * vNodes, Vec_Ptr_t * vEndpoints )
+{
+    Abc_Obj_t * pFanout;
+    int i;
+    assert( !Abc_ObjIsNet(pNode) );
+    // if this node is already visited, skip
+    if ( Abc_NodeIsTravIdCurrent( pNode ) )
+        return;
+    // mark the node as visited
+    Abc_NodeSetTravIdCurrent( pNode );
+    // terminate at the Co
+    if ( Abc_ObjIsCo(pNode) ) {
+      Vec_PtrPush( vEndpoints, pNode );
+      return;
+    }
+    assert( Abc_ObjIsNode( pNode ) );
+    // visit the transitive fanin of the node
+    pNode = Abc_ObjFanout0Ntk(pNode);
+    Abc_ObjForEachFanout( pNode, pFanout, i )
+      Abc_NtkDfsReverse_rec2( pFanout, vNodes, vEndpoints );
+    // add the node after the fanins have been added
+    Vec_PtrPush( vNodes, pNode );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Converts all skews into forward skews 0<skew<T.]
+
+  Description [Can also minimize total skew by changing global skew.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Seq_NtkSkewForward( Abc_Ntk_t * pNtk, float period, int fMinimize ) {
+  
+  Abc_Obj_t * pObj;
+  int         i;
+  float       skew;
+  float       currentSum = 0, bestSum = ABC_INFINITY;
+  float       currentOffset = 0, nextStep, bestOffset = 0;
+  
+  assert( pNtk->vSkews->nSize >= Abc_NtkLatchNum( pNtk )-1 );
+
+  if (fMinimize) {
+    // search all offsets for the one that minimizes sum of skews
+    while(currentOffset < period) {
+      currentSum = 0;
+      nextStep = period;
+      Abc_NtkForEachLatch( pNtk, pObj, i ) {
+        skew = Abc_NtkGetLatSkew( pNtk, i ) + currentOffset;
+        skew = (float)(skew - period*floor(skew/period));
+        currentSum += skew;
+        if (skew > ZERO_SLOP && skew < nextStep) {
+          nextStep = skew;
+        }
+      }
+
+      if (currentSum < bestSum) {
+        bestSum = currentSum;
+        bestOffset = currentOffset;
+      }
+      currentOffset += nextStep;
+    }
+    printf("Offseting all skews by %.2f\n", bestOffset);
+  }
+
+  // convert global skew into forward skew
+  pNtk->globalSkew = pNtk->globalSkew - bestOffset;
+  pNtk->globalSkew = (float)(pNtk->globalSkew - period*floor(pNtk->globalSkew/period));
+  assert(pNtk->globalSkew>= 0 && pNtk->globalSkew < period);
+    
+  // convert endpoint skews into forward skews
+  Abc_NtkForEachLatch( pNtk, pObj, i ) {
+    skew = Abc_NtkGetLatSkew( pNtk, i ) + bestOffset;
+    skew = (float)(skew - period*floor(skew/period));
+    REMOVE_ZERO_SLOP( skew );
+    assert(skew >=0  && skew < period);
+
+    Abc_NtkSetLatSkew( pNtk, i, skew );
+  }
+}
+
+////////////////////////////////////////////////////////////////////////
+///                       END OF FILE                                ///
+////////////////////////////////////////////////////////////////////////