Naive LUT packing algorithm (command &pack).

3 files changed, 307 insertions, 0 deletions

diff --git a/src/aig/gia/giaPack.c b/src/aig/gia/giaPack.c
new file mode 100644
index 00000000..0cbf96d8
--- /dev/null
+++ b/src/aig/gia/giaPack.c
@@ -0,0 +1,207 @@
+/**CFile****************************************************************
+
+  FileName    [giaPack.c]
+
+  SystemName  [ABC: Logic synthesis and verification system.]
+
+  PackageName [Scalable AIG package.]
+
+  Synopsis    [LUT packing.]
+
+  Author      [Alan Mishchenko]
+  
+  Affiliation [UC Berkeley]
+
+  Date        [Ver. 1.0. Started - June 20, 2005.]
+
+  Revision    [$Id: giaPack.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "gia.h"
+
+ABC_NAMESPACE_IMPL_START
+
+
+////////////////////////////////////////////////////////////////////////
+///                        DECLARATIONS                              ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+///                     FUNCTION DEFINITIONS                         ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+  Synopsis    [Collects LUT nodes in the increasing order of distance from COs.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Vec_Int_t * Gia_ManLutCollect2( Gia_Man_t * p )
+{
+    Gia_Obj_t * pObj;
+    Vec_Int_t * vOrder;
+    int i, k, Id, iFan;
+    vOrder = Vec_IntAlloc( Gia_ManLutNum(p) );
+    Gia_ManIncrementTravId( p );
+    Gia_ManForEachCoDriver( p, pObj, i )
+    {
+        if ( !Gia_ObjIsAnd(pObj) )
+            continue;
+        Id = Gia_ObjId( p, pObj );
+        assert( Gia_ObjIsLut(p, Id) );
+        if ( Gia_ObjIsTravIdCurrentId(p, Id) )
+            continue;
+        Gia_ObjSetTravIdCurrentId(p, Id);
+        Vec_IntPush( vOrder, Id );
+    }
+    Vec_IntForEachEntry( vOrder, Id, i )
+    {
+        Gia_LutForEachFanin( p, Id, iFan, k )
+        {
+            if ( !Gia_ObjIsAnd(Gia_ManObj(p, iFan)) )
+                continue;
+            assert( Gia_ObjIsLut(p, iFan) );
+            if ( Gia_ObjIsTravIdCurrentId(p, iFan) )
+                continue;
+            Gia_ObjSetTravIdCurrentId(p, iFan);
+            Vec_IntPush( vOrder, iFan );
+        }
+    }
+    assert( Vec_IntCap(vOrder) == 16 || Vec_IntSize(vOrder) == Vec_IntCap(vOrder) );
+    Vec_IntReverseOrder( vOrder );
+    return vOrder;
+}
+Vec_Int_t * Gia_ManLutCollect( Gia_Man_t * p )
+{
+    Vec_Int_t * vLuts, * vDist, * vOrder;
+    int i, k, Id, iFan, * pPerm;
+    // collect LUTs
+    vLuts = Vec_IntAlloc( Gia_ManAndNum(p) );
+    Gia_ManForEachLut( p, Id )
+        Vec_IntPush( vLuts, Id );
+    // propagate distance
+    vDist = Vec_IntStart( Gia_ManObjNum(p) );
+    Gia_ManForEachCoDriverId( p, Id, i )
+        Vec_IntWriteEntry( vDist, Id, 1 );
+    Vec_IntForEachEntryReverse( vLuts, Id, i )
+    {
+        int Dist = 1 + Vec_IntEntry(vDist, Id);
+        Gia_LutForEachFanin( p, Id, iFan, k )
+            Vec_IntUpdateEntry( vDist, iFan, Dist );
+    }
+    // sort LUTs by distance
+    k = 0;
+    Vec_IntForEachEntry( vLuts, Id, i )
+        Vec_IntWriteEntry( vDist, k++, -Vec_IntEntry(vDist, Id) );
+    Vec_IntShrink( vDist, k );
+    pPerm = Abc_MergeSortCost( Vec_IntArray(vDist), Vec_IntSize(vDist) );
+    // collect
+    vOrder = Vec_IntAlloc( Vec_IntSize(vLuts) );
+    for ( i = 0; i < Vec_IntSize(vLuts); i++ )
+        Vec_IntPush( vOrder, Vec_IntEntry(vLuts, pPerm[i]) );
+    Vec_IntFree( vDist );
+    Vec_IntFree( vLuts );
+    ABC_FREE( pPerm );
+    return vOrder;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [LUT packing algorithm.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Gia_ManLutPacking( Gia_Man_t * p, int nBlockSize, int DelayRoute, int DelayDir, int fVerbose )
+{
+    int Delays[32], Perm[32];
+    Vec_Int_t * vPacking, * vStarts;
+    Vec_Int_t * vOrder = Gia_ManLutCollect( p );
+    Vec_Int_t * vDelay = Vec_IntStart( Gia_ManObjNum(p) );
+    Vec_Int_t * vBlock = Vec_IntStart( Gia_ManObjNum(p) );
+    Vec_Int_t * vBSize = Vec_IntAlloc( 2 * Vec_IntSize(vOrder) / nBlockSize );
+    int i, k, Id, iFan, nSize, iBlock, Delay, DelayMax = 0;
+    // create blocks
+    Vec_IntForEachEntry( vOrder, Id, i )
+    {
+        nSize = Gia_ObjLutSize( p, Id );
+        assert( nSize <= 32 );
+        Gia_LutForEachFanin( p, Id, iFan, k )
+        {
+            Delays[k] = Vec_IntEntry(vDelay, iFan);
+            Perm[k] = iFan;
+        }
+        Vec_IntSelectSortCost2Reverse( Perm, nSize, Delays );
+        assert( nSize < 2 || Delays[0] >= Delays[nSize-1] );
+        assert( Delays[0] >= 0 && Delays[nSize-1] >= 0 );
+        // check if we can reduce delay by adding it to the same bin as the latest one
+        iBlock = Vec_IntEntry( vBlock, Perm[0] );
+        if ( Delays[0] > 0 && Delays[0] > Delays[1] && Vec_IntEntry(vBSize, iBlock) < nBlockSize )
+        {
+            Delay = Delays[0] + DelayDir;
+            Vec_IntWriteEntry( vBlock, Id, iBlock );
+            Vec_IntAddToEntry( vBSize, iBlock, 1 );
+        }
+        else // clean new block
+        {
+            Delay = Delays[0] + DelayRoute;
+            Vec_IntWriteEntry( vBlock, Id, Vec_IntSize(vBSize) );
+            Vec_IntPush( vBSize, 1 );
+        }
+        // calculate delay
+        for ( k = 1; k < nSize; k++ )
+            Delay = Abc_MaxInt( Delay, Delays[k] + DelayRoute );
+        Vec_IntWriteEntry( vDelay, Id, Delay );
+        DelayMax = Abc_MaxInt( DelayMax, Delay );
+    }
+    assert( Vec_IntSum(vBSize) == Vec_IntSize(vOrder) );
+    // create packing info
+    vPacking = Vec_IntAlloc( Vec_IntSize(vBSize) + Vec_IntSize(vOrder) + 1 );
+    Vec_IntPush( vPacking, Vec_IntSize(vBSize) );
+    // create starting places for each block
+    vStarts = Vec_IntAlloc( Vec_IntSize(vBSize) );
+    Vec_IntForEachEntry( vBSize, nSize, i )
+    {
+        Vec_IntPush( vPacking, nSize );
+        Vec_IntPush( vStarts, Vec_IntSize(vPacking) );
+        Vec_IntFillExtra( vPacking, Vec_IntSize(vPacking) + nSize, -1 );
+    }
+    assert( Vec_IntCap(vPacking) == 16 || Vec_IntSize(vPacking) == Vec_IntCap(vPacking) );
+    // collect LUTs from the block
+    Vec_IntForEachEntryReverse( vOrder, Id, i )
+    {
+        int Block = Vec_IntEntry( vBlock, Id );
+        int Start = Vec_IntEntry( vStarts, Block );
+        assert( Vec_IntEntry(vPacking, Start) == -1 );
+        Vec_IntWriteEntry( vPacking, Start, Id );
+        Vec_IntAddToEntry( vStarts, Block, 1 );
+    }
+    assert( Vec_IntCountEntry(vPacking, -1) == 0 );
+    // cleanup
+    Vec_IntFree( vOrder );
+    Vec_IntFree( vDelay );
+    Vec_IntFree( vBlock );
+    Vec_IntFree( vBSize );
+    Vec_IntFree( vStarts );
+    Vec_IntFreeP( &p->vPacking );
+    p->vPacking = vPacking;
+    printf( "Global delay = %d.\n", DelayMax );
+}
+
+////////////////////////////////////////////////////////////////////////
+///                       END OF FILE                                ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
diff --git a/src/aig/gia/module.make b/src/aig/gia/module.make
index 07038a09..32359c67 100644
--- a/src/aig/gia/module.make
+++ b/src/aig/gia/module.make
@@ -47,6 +47,7 @@ SRC +=    src/aig/gia/giaAig.c \
     src/aig/gia/giaMuxes.c \
     src/aig/gia/giaNf.c \
     src/aig/gia/giaOf.c \
+    src/aig/gia/giaPack.c \
     src/aig/gia/giaPat.c \
     src/aig/gia/giaPf.c \
     src/aig/gia/giaQbf.c \
diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c
index 2fa26c71..d1c86e62 100644
--- a/src/base/abci/abc.c
+++ b/src/base/abci/abc.c
@@ -414,6 +414,7 @@ static int Abc_CommandAbc9Lf                 ( Abc_Frame_t * pAbc, int argc, cha
 static int Abc_CommandAbc9Mf                 ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandAbc9Nf                 ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandAbc9Of                 ( Abc_Frame_t * pAbc, int argc, char ** argv );
+static int Abc_CommandAbc9Pack               ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandAbc9Unmap              ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandAbc9Struct             ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandAbc9Trace              ( Abc_Frame_t * pAbc, int argc, char ** argv );
@@ -1034,6 +1035,7 @@ void Abc_Init( Abc_Frame_t * pAbc )
     Cmd_CommandAdd( pAbc, "ABC9",         "&mf",           Abc_CommandAbc9Mf,           0 );
     Cmd_CommandAdd( pAbc, "ABC9",         "&nf",           Abc_CommandAbc9Nf,           0 );
     Cmd_CommandAdd( pAbc, "ABC9",         "&of",           Abc_CommandAbc9Of,           0 );
+    Cmd_CommandAdd( pAbc, "ABC9",         "&pack",         Abc_CommandAbc9Pack,         0 );
     Cmd_CommandAdd( pAbc, "ABC9",         "&unmap",        Abc_CommandAbc9Unmap,        0 );
     Cmd_CommandAdd( pAbc, "ABC9",         "&struct",       Abc_CommandAbc9Struct,       0 );
     Cmd_CommandAdd( pAbc, "ABC9",         "&trace",        Abc_CommandAbc9Trace,        0 );
@@ -34257,6 +34259,103 @@ usage:
   SeeAlso     []
 
 ***********************************************************************/
+int Abc_CommandAbc9Pack( Abc_Frame_t * pAbc, int argc, char ** argv )
+{
+    extern void Gia_ManLutPacking( Gia_Man_t * p, int nBlock, int DelayRoute, int DelayDir, int fVerbose );
+    int c, nBlock = 2, DelayRoute = 10, DelayDir = 2, fVerbose = 0;
+    Extra_UtilGetoptReset();
+    while ( ( c = Extra_UtilGetopt( argc, argv, "NRDvh" ) ) != EOF )
+    {
+        switch ( c )
+        {
+        case 'N':
+            if ( globalUtilOptind >= argc )
+            {
+                Abc_Print( -1, "Command line switch \"-N\" should be followed by a positive integer.\n" );
+                goto usage;
+            }
+            nBlock = atoi(argv[globalUtilOptind]);
+            globalUtilOptind++;
+            if ( nBlock < 2 )
+            {
+                Abc_Print( -1, "LUT block size (%d) should be more than 1.\n", nBlock );
+                goto usage;
+            }
+            break;
+        case 'R':
+            if ( globalUtilOptind >= argc )
+            {
+                Abc_Print( -1, "Command line switch \"-N\" should be followed by a positive integer.\n" );
+                goto usage;
+            }
+            DelayRoute = atoi(argv[globalUtilOptind]);
+            globalUtilOptind++;
+            if ( DelayRoute <= 0 )
+            {
+                Abc_Print( -1, "Rounting delay (%d) should be more than 0.\n", DelayRoute);
+                goto usage;
+            }
+            break;
+        case 'D':
+            if ( globalUtilOptind >= argc )
+            {
+                Abc_Print( -1, "Command line switch \"-D\" should be followed by a positive integer.\n" );
+                goto usage;
+            }
+            DelayDir = atoi(argv[globalUtilOptind]);
+            globalUtilOptind++;
+            if ( DelayDir <= 0 )
+            {
+                Abc_Print( -1, "Direct delay (%d) should be more than 0.\n", DelayRoute);
+                goto usage;
+            }
+            break;
+        case 'v':
+            fVerbose ^= 1;
+            break;
+        case 'h':
+        default:
+            goto usage;
+        }
+    }
+
+    if ( pAbc->pGia == NULL )
+    {
+        Abc_Print( -1, "Empty GIA network.\n" );
+        return 1;
+    }
+    if ( !Gia_ManHasMapping(pAbc->pGia) )
+    {
+        Abc_Print( -1, "Current AIG has no mapping. Run \"&if\".\n" );
+        return 1;
+    }
+    if ( Gia_ManLutSizeMax(pAbc->pGia) > 6 )
+        Abc_Print( 0, "Current AIG has mapping into %d-LUTs.\n", Gia_ManLutSizeMax(pAbc->pGia) );
+    Gia_ManLutPacking( pAbc->pGia, nBlock, DelayRoute, DelayDir, fVerbose );
+    return 0;
+
+usage:
+    Abc_Print( -2, "usage: &pack [-NRD num] [-vh]\n" );
+    Abc_Print( -2, "\t           performs packing for the LUT mapped network\n" );
+    Abc_Print( -2, "\t-N num   : the number of LUTs in the block [default = %d]\n", nBlock );
+    Abc_Print( -2, "\t-R num   : the routable delay of a LUT [default = %d]\n", DelayRoute );
+    Abc_Print( -2, "\t-D num   : the direct (non-routable) delay of a LUT [default = %d]\n", DelayDir );
+    Abc_Print( -2, "\t-v       : toggles verbose output [default = %s]\n", fVerbose? "yes": "no" );
+    Abc_Print( -2, "\t-h       : prints the command usage\n");
+    return 1;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
 int Abc_CommandAbc9Unmap( Abc_Frame_t * pAbc, int argc, char ** argv )
 {
     extern void Gia_ManTestStruct( Gia_Man_t * p );