Experiments with simulation.

6 files changed, 357 insertions, 6 deletions

diff --git a/abclib.dsp b/abclib.dsp
index 436a22a6..481af325 100644
--- a/abclib.dsp
+++ b/abclib.dsp
@@ -2359,6 +2359,10 @@ SOURCE=.\src\map\if\ifSeq.c
 # End Source File
 # Begin Source File
 
+SOURCE=.\src\map\if\ifTest.c
+# End Source File
+# Begin Source File
+
 SOURCE=.\src\map\if\ifTime.c
 # End Source File
 # Begin Source File
diff --git a/src/aig/gia/gia.h b/src/aig/gia/gia.h
index f8668224..a5858ca6 100644
--- a/src/aig/gia/gia.h
+++ b/src/aig/gia/gia.h
@@ -859,15 +859,19 @@ static inline void        Gia_ClassUndoPair( Gia_Man_t * p, int i )          { a
     for ( assert(Gia_ObjIsHead(p, i)), iObj = Gia_ObjNext(p, i); iObj; iObj = Gia_ObjNext(p, iObj) )
 
 
-static inline int         Gia_ObjFoffset( Gia_Man_t * p, Gia_Obj_t * pObj )        { return Vec_IntEntry( p->vFanout, Gia_ObjId(p, pObj) );                 }
-static inline int         Gia_ObjFanoutNum( Gia_Man_t * p, Gia_Obj_t * pObj )      { return Vec_IntEntry( p->vFanoutNums, Gia_ObjId(p, pObj) );             }
-static inline int         Gia_ObjFanoutId( Gia_Man_t * p, Gia_Obj_t * pObj, int i ){ return Vec_IntEntry( p->vFanout, Gia_ObjFoffset(p, pObj) + i );        }
-static inline Gia_Obj_t * Gia_ObjFanout0( Gia_Man_t * p, Gia_Obj_t * pObj )        { return Gia_ManObj( p, Gia_ObjFanoutId(p, pObj, 0) );                   }
-static inline Gia_Obj_t * Gia_ObjFanout( Gia_Man_t * p, Gia_Obj_t * pObj, int i )  { return Gia_ManObj( p, Gia_ObjFanoutId(p, pObj, i) );                   }
+static inline int         Gia_ObjFoffsetId( Gia_Man_t * p, int Id )                { return Vec_IntEntry( p->vFanout, Id );                                 }
+static inline int         Gia_ObjFoffset( Gia_Man_t * p, Gia_Obj_t * pObj )        { return Gia_ObjFoffsetId( p, Gia_ObjId(p, pObj) );                      }
+static inline int         Gia_ObjFanoutNumId( Gia_Man_t * p, int Id )              { return Vec_IntEntry( p->vFanoutNums, Id );                             }
+static inline int         Gia_ObjFanoutNum( Gia_Man_t * p, Gia_Obj_t * pObj )      { return Gia_ObjFanoutNumId( p, Gia_ObjId(p, pObj) );                    }
+static inline int         Gia_ObjFanoutId( Gia_Man_t * p, int Id, int i )          { return Vec_IntEntry( p->vFanout, Gia_ObjFoffsetId(p, Id) + i );        }
+static inline Gia_Obj_t * Gia_ObjFanout0( Gia_Man_t * p, Gia_Obj_t * pObj )        { return Gia_ManObj( p, Gia_ObjFanoutId(p, Gia_ObjId(p, pObj), 0) );     }
+static inline Gia_Obj_t * Gia_ObjFanout( Gia_Man_t * p, Gia_Obj_t * pObj, int i )  { return Gia_ManObj( p, Gia_ObjFanoutId(p, Gia_ObjId(p, pObj), i) );     }
 static inline void        Gia_ObjSetFanout( Gia_Man_t * p, Gia_Obj_t * pObj, int i, Gia_Obj_t * pFan )   { Vec_IntWriteEntry( p->vFanout, Gia_ObjFoffset(p, pObj) + i, Gia_ObjId(p, pFan) ); }
 
 #define Gia_ObjForEachFanoutStatic( p, pObj, pFanout, i )      \
     for ( i = 0; (i < Gia_ObjFanoutNum(p, pObj))   && (((pFanout) = Gia_ObjFanout(p, pObj, i)), 1); i++ )
+#define Gia_ObjForEachFanoutStaticId( p, Id, FanId, i )      \
+    for ( i = 0; (i < Gia_ObjFanoutNumId(p, Id))   && (((FanId) = Gia_ObjFanoutId(p, Id, i)), 1); i++ )
 
 static inline int         Gia_ManHasMapping( Gia_Man_t * p )                { return p->vMapping != NULL;                }
 static inline int         Gia_ObjIsLut( Gia_Man_t * p, int Id )             { return Vec_IntEntry(p->vMapping, Id) != 0; }
@@ -908,6 +912,8 @@ static inline int         Gia_ObjLutFanin( Gia_Man_t * p, int Id, int i )   { re
     for ( i = 0; (i < p->nObjs) && ((pObj) = Gia_ManObj(p, i)); i++ )      if ( !Gia_ObjIsMuxId(p, i) ) {} else
 #define Gia_ManForEachCi( p, pObj, i )                                  \
     for ( i = 0; (i < Vec_IntSize(p->vCis)) && ((pObj) = Gia_ManCi(p, i)); i++ )
+#define Gia_ManForEachCiReverse( p, pObj, i )                           \
+    for ( i = Vec_IntSize(p->vCis) - 1; (i >= 0) && ((pObj) = Gia_ManCi(p, i)); i-- )
 #define Gia_ManForEachCo( p, pObj, i )                                  \
     for ( i = 0; (i < Vec_IntSize(p->vCos)) && ((pObj) = Gia_ManCo(p, i)); i++ )
 #define Gia_ManForEachCoReverse( p, pObj, i )                           \
@@ -1223,6 +1229,7 @@ extern word *              Gia_ObjComputeTruthTableCut( Gia_Man_t * p, Gia_Obj_t
 extern Gia_Man_t *         Gia_ManReduceConst( Gia_Man_t * pAig, int fVerbose );
 /*=== giaUtil.c ===========================================================*/
 extern unsigned            Gia_ManRandom( int fReset );
+extern word                Gia_ManRandomW( int fReset );
 extern void                Gia_ManRandomInfo( Vec_Ptr_t * vInfo, int iInputStart, int iWordStart, int iWordStop );
 extern char *              Gia_TimeStamp();
 extern char *              Gia_FileNameGenericAppend( char * pBase, char * pSuffix );
diff --git a/src/aig/gia/giaUtil.c b/src/aig/gia/giaUtil.c
index 34bda9bb..56aa2468 100644
--- a/src/aig/gia/giaUtil.c
+++ b/src/aig/gia/giaUtil.c
@@ -59,6 +59,11 @@ unsigned Gia_ManRandom( int fReset )
     m_w = 18000 * (m_w & 65535) + (m_w >> 16);
     return (m_z << 16) + m_w;
 }
+word Gia_ManRandomW( int fReset )
+{ 
+    return ((word)Gia_ManRandom(fReset) << 32) | ((word)Gia_ManRandom(fReset) << 0);
+}
+
 
 
 /**Function*************************************************************
diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c
index 03875daa..8f7dfb43 100644
--- a/src/base/abci/abc.c
+++ b/src/base/abci/abc.c
@@ -34030,6 +34030,8 @@ int Abc_CommandAbc9Test( Abc_Frame_t * pAbc, int argc, char ** argv )
     int c, fVerbose = 0;
     int nFrames = 0;
     int fSwitch = 0;
+    int nWords = 1000;
+    int nProcs = 2;
 //    extern Gia_Man_t * Gia_VtaTest( Gia_Man_t * p );
 //    extern int Gia_ManSuppSizeTest( Gia_Man_t * p );
 //    extern void Gia_VtaTest( Gia_Man_t * p, int nFramesStart, int nFramesMax, int nConfMax, int nTimeMax, int fVerbose );
@@ -34051,12 +34053,35 @@ int Abc_CommandAbc9Test( Abc_Frame_t * pAbc, int argc, char ** argv )
 //    extern Gia_Man_t * Unm_ManTest( Gia_Man_t * pGia );
 //    extern void Agi_ManTest( Gia_Man_t * pGia );
 //    extern void Gia_ManCheckFalseTest( Gia_Man_t * p, int nSlackMax );
+    extern void Gia_ParTest( Gia_Man_t * p, int nWords, int nProcs );
 
     Extra_UtilGetoptReset();
-    while ( ( c = Extra_UtilGetopt( argc, argv, "Fsvh" ) ) != EOF )
+    while ( ( c = Extra_UtilGetopt( argc, argv, "WPFsvh" ) ) != EOF )
     {
         switch ( c )
         {
+        case 'W':
+            if ( globalUtilOptind >= argc )
+            {
+                Abc_Print( -1, "Command line switch \"-W\" should be followed by an integer.\n" );
+                goto usage;
+            }
+            nWords = atoi(argv[globalUtilOptind]);
+            globalUtilOptind++;
+            if ( nWords < 0 )
+                goto usage;
+            break;
+        case 'P':
+            if ( globalUtilOptind >= argc )
+            {
+                Abc_Print( -1, "Command line switch \"-P\" should be followed by an integer.\n" );
+                goto usage;
+            }
+            nProcs = atoi(argv[globalUtilOptind]);
+            globalUtilOptind++;
+            if ( nProcs < 0 )
+                goto usage;
+            break;
         case 'F':
             if ( globalUtilOptind >= argc )
             {
@@ -34131,6 +34156,7 @@ int Abc_CommandAbc9Test( Abc_Frame_t * pAbc, int argc, char ** argv )
 //    Gia_ManResubTest( pAbc->pGia );
 //    Jf_ManTestCnf( pAbc->pGia );
 //    Gia_ManCheckFalseTest( pAbc->pGia, nFrames );
+    Gia_ParTest( pAbc->pGia, nWords, nProcs );
     return 0;
 usage:
     Abc_Print( -2, "usage: &test [-F num] [-svh]\n" );
diff --git a/src/map/if/ifTest.c b/src/map/if/ifTest.c
new file mode 100644
index 00000000..efca2e10
--- /dev/null
+++ b/src/map/if/ifTest.c
@@ -0,0 +1,308 @@
+/**CFile****************************************************************
+
+  FileName    [ifTest.c]
+
+  SystemName  [ABC: Logic synthesis and verification system.]
+
+  PackageName [FPGA mapping based on priority cuts.]
+
+  Synopsis    []
+
+  Author      [Alan Mishchenko]
+  
+  Affiliation [UC Berkeley]
+
+  Date        [Ver. 1.0. Started - November 21, 2006.]
+
+  Revision    [$Id: ifTest.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "if.h"
+#include "aig/gia/gia.h"
+
+//#ifdef ABC_USE_PTHREADS
+
+#ifdef _WIN32
+#include "../lib/pthread.h"
+#else
+#include <pthread.h>
+#include <unistd.h>
+#endif
+
+//#endif
+
+ABC_NAMESPACE_IMPL_START
+
+////////////////////////////////////////////////////////////////////////
+///                        DECLARATIONS                              ///
+////////////////////////////////////////////////////////////////////////
+
+static inline word * Gia_ParTestObj( Gia_Man_t * p, int Id )         { return (word *)p->pData + Id * p->iData; }
+static inline void   Gia_ParTestAlloc( Gia_Man_t * p, int nWords )   { assert( !p->pData ); p->pData = (unsigned *)ABC_ALLOC(word, Gia_ManObjNum(p) * nWords); p->iData = nWords; }
+static inline void   Gia_ParTestFree( Gia_Man_t * p )                { ABC_FREE( p->pData ); p->iData = 0; }
+
+////////////////////////////////////////////////////////////////////////
+///                     FUNCTION DEFINITIONS                         ///
+////////////////////////////////////////////////////////////////////////
+ 
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Gia_ParTestSimulateObj( Gia_Man_t * p, int Id )
+{
+    Gia_Obj_t * pObj = Gia_ManObj( p, Id );
+    word * pData, * pData0, * pData1;
+    int i;
+    if ( Gia_ObjIsAnd(pObj) )
+    {
+        pData  = Gia_ParTestObj( p, Id );
+        pData0 = Gia_ParTestObj( p, Gia_ObjFaninId0(pObj, Id) );
+        pData1 = Gia_ParTestObj( p, Gia_ObjFaninId1(pObj, Id) );
+        if ( Gia_ObjFaninC0(pObj) )
+        {
+            if ( Gia_ObjFaninC1(pObj) )
+                for ( i = 0; i < p->iData; i++ )
+                    pData[i] = ~(pData0[i] | pData1[i]);
+            else 
+                for ( i = 0; i < p->iData; i++ )
+                    pData[i] = ~pData0[i] & pData1[i];
+        }
+        else 
+        {
+            if ( Gia_ObjFaninC1(pObj) )
+                for ( i = 0; i < p->iData; i++ )
+                    pData[i] = pData0[i] & ~pData1[i];
+            else 
+                for ( i = 0; i < p->iData; i++ )
+                    pData[i] = pData0[i] & pData1[i];
+        }
+    }
+    else if ( Gia_ObjIsCo(pObj) )
+    {
+        pData  = Gia_ParTestObj( p, Id );
+        pData0 = Gia_ParTestObj( p, Gia_ObjFaninId0(pObj, Id) );
+        if ( Gia_ObjFaninC0(pObj) )
+            for ( i = 0; i < p->iData; i++ )
+                pData[i] = ~pData0[i];
+        else 
+            for ( i = 0; i < p->iData; i++ )
+                pData[i] = pData0[i];
+    }
+    else if ( Gia_ObjIsCi(pObj) )
+    {
+        pData = Gia_ParTestObj( p, Id );
+        for ( i = 0; i < p->iData; i++ )
+            pData[i] = Gia_ManRandomW( 0 );
+    }
+    else if ( Gia_ObjIsConst0(pObj) )
+    {
+        pData = Gia_ParTestObj( p, Id );
+        for ( i = 0; i < p->iData; i++ )
+            pData[i] = 0;
+    }
+    else assert( 0 );
+}
+void Gia_ParTestSimulate( Gia_Man_t * p, int nWords )
+{
+    Gia_Obj_t * pObj;
+    int i;
+    Gia_ManRandom( 1 );
+    Gia_ParTestAlloc( p, nWords );
+    Gia_ManForEachObj( p, pObj, i )
+        Gia_ParTestSimulateObj( p, i );
+    Gia_ParTestFree( p );
+}
+  
+
+/**Function*************************************************************
+
+  Synopsis    [Assigns references.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Vec_Int_t * Gia_ManCreateFaninCounts( Gia_Man_t * p )  
+{
+    Vec_Int_t * vCounts;
+    Gia_Obj_t * pObj; int i;
+    vCounts = Vec_IntAlloc( Gia_ManObjNum(p) );
+    Gia_ManForEachObj( p, pObj, i )
+    {
+        if ( Gia_ObjIsAnd(pObj) )
+            Vec_IntPush( vCounts, 2 );
+        else if ( Gia_ObjIsCo(pObj) )
+            Vec_IntPush( vCounts, 1 );
+        else
+            Vec_IntPush( vCounts, 0 );
+    }
+    assert( Vec_IntSize(vCounts) == Gia_ManObjNum(p) );
+    return vCounts;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+#define PAR_THR_MAX 100
+typedef struct Par_ThData_t_
+{
+    Gia_Man_t * p;
+    int         Id;
+    int         Status;
+} Par_ThData_t;
+//pthread_mutex_t g_mutex = PTHREAD_MUTEX_INITIALIZER;
+void * Gia_ParWorkerThread( void * pArg )
+{
+    Par_ThData_t * pThData = (Par_ThData_t *)pArg;
+    unsigned Counter = 0;
+    while ( 1 )
+    {
+        while ( pThData->Status == 0 )
+            printf( "" );
+        assert( pThData->Status == 1 );
+        if ( pThData->Id == -1 )
+        {
+//            printf( "Stopped\n" ); fflush( stdout );
+            pthread_exit( NULL );
+            assert( 0 );
+            return NULL;
+        }
+        assert( pThData->Id >= 0 );
+        Gia_ParTestSimulateObj( pThData->p, pThData->Id );
+//        printf( "Simulated %d \n", pThData->Id ); fflush( stdout );
+        pThData->Status = 0;
+    }
+    assert( Counter != 0 );
+    assert( 0 );
+    return (void *)Counter;
+}
+void Gia_ParTestSimulate2( Gia_Man_t * p, int nWords, int nProcs )
+{
+    pthread_t WorkerThread[PAR_THR_MAX];
+    Par_ThData_t ThData[PAR_THR_MAX];
+    Vec_Int_t * vStack, * vFanins;
+    int i, k, iFan, status, nCountFanins;
+    Gia_ManRandom( 1 );
+    Gia_ParTestAlloc( p, nWords );
+    // start the stack
+    vStack = Vec_IntAlloc( 1000 );
+    for ( i = Vec_IntSize(p->vCis) - 1; i >= 0; i-- )
+        Vec_IntPush( vStack, Vec_IntEntry(p->vCis, i) );
+    Vec_IntPush( vStack, 0 );
+    Gia_ManStaticFanoutStart( p );
+    vFanins = Gia_ManCreateFaninCounts( p );
+    nCountFanins = Vec_IntSum(vFanins);
+    // start the threads
+    assert( nProcs <= PAR_THR_MAX );
+    for ( i = 0; i < nProcs; i++ )
+    {
+        ThData[i].p = p;
+        ThData[i].Id = -1;
+        ThData[i].Status = 0;
+        status = pthread_create( WorkerThread + i, NULL, Gia_ParWorkerThread, (void *)(ThData + i) );  assert( status == 0 );
+//        printf( "Started %d\n", i ); fflush( stdout );
+    }
+    while ( nCountFanins > 0 )
+    {
+        for ( i = 0; i < nProcs; i++ )
+        {
+            if ( ThData[i].Status )
+                continue;
+            assert( ThData[i].Status == 0 );
+            if ( ThData[i].Id >= 0 )
+            {
+                Gia_ObjForEachFanoutStaticId( p, ThData[i].Id, iFan, k )
+                {
+                    assert( Vec_IntEntry(vFanins, iFan) > 0 );
+                    if ( Vec_IntAddToEntry(vFanins, iFan, -1) == 0 )
+                        Vec_IntPush( vStack, iFan );
+                    assert( nCountFanins > 0 );
+                    nCountFanins--;
+                }
+            }
+            if ( Vec_IntSize(vStack) > 0 )
+            {
+                ThData[i].Id = Vec_IntPop( vStack );
+                ThData[i].Status = 1;
+            }
+        }
+    }
+    Vec_IntForEachEntry( vFanins, iFan, k )
+        if ( iFan != 0 )
+        {
+            printf( "%d -> %d    ", k, iFan );
+            Gia_ObjPrint( p, Gia_ManObj(p, k) );
+        }
+//    assert( Vec_IntSum(vFanins) == 0 );
+    // stop the threads
+    while ( 1 )
+    {
+        for ( i = 0; i < nProcs; i++ )
+            if ( ThData[i].Status )
+                break;
+        if ( i == nProcs )
+            break;
+    }
+    for ( i = 0; i < nProcs; i++ )
+    {
+//        printf( "Stopping %d\n", i ); fflush( stdout );
+        ThData[i].Id = -1;
+        ThData[i].Status = 1;
+    }
+    Gia_ManStaticFanoutStop( p );
+    Vec_IntFree( vStack );
+    Vec_IntFree( vFanins );
+    Gia_ParTestFree( p );
+}
+
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Gia_ParTest( Gia_Man_t * p, int nWords, int nProcs )
+{
+    abctime clk = Abc_Clock();
+    printf( "Trying with %d words and %d procs.\n", nWords, nProcs );
+    printf( "Memory usage = %.2f MB\n", (8.0*nWords*Gia_ManObjNum(p))/(1<<20) );
+    Gia_ParTestSimulate( p, nWords );
+    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
+    clk = Abc_Clock();
+    Gia_ParTestSimulate2( p, nWords, nProcs );
+    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
+}
+
+////////////////////////////////////////////////////////////////////////
+///                       END OF FILE                                ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
diff --git a/src/map/if/module.make b/src/map/if/module.make
index f6eb65ae..5311fb5f 100644
--- a/src/map/if/module.make
+++ b/src/map/if/module.make
@@ -15,6 +15,7 @@ SRC +=  src/map/if/ifCom.c \
     src/map/if/ifSat.c \
     src/map/if/ifSelect.c \
     src/map/if/ifSeq.c \
+    src/map/if/ifTest.c \
     src/map/if/ifTime.c \
     src/map/if/ifTruth.c \
     src/map/if/ifTune.c \