From 44d220d28fa2ee56cb539e03684f021731814f17 Mon Sep 17 00:00:00 2001
From: Alan Mishchenko <alanmi@berkeley.edu>
Date: Tue, 28 Nov 2006 08:01:00 -0800
Subject: Version abc61128
---
src/map/fpga/fpga.c | 4 +-
src/map/fpga/fpgaCore.c | 19 ++-
src/map/fpga/fpgaCut.c | 4 +-
src/map/fpga/fpgaMatch.c | 12 ++
src/map/if/if.h | 17 ++-
src/map/if/ifCore.c | 68 +++++++++
src/map/if/ifMan.c | 8 +-
src/map/if/ifMap.c | 334 +++++++++++++++++++++++++++++++++++----------
src/map/mapper/mapperCut.c | 3 +-
9 files changed, 384 insertions(+), 85 deletions(-)
(limited to 'src/map')
diff --git a/src/map/fpga/fpga.c b/src/map/fpga/fpga.c
index d04c9910..d7a128b0 100644
--- a/src/map/fpga/fpga.c
+++ b/src/map/fpga/fpga.c
@@ -57,8 +57,8 @@ void Fpga_Init( Abc_Frame_t * pAbc )
{
// set the default library
//Fpga_LutLib_t s_LutLib = { "lutlib", 6, {0,1,2,4,8,16,32}, {0,1,2,3,4,5,6} };
-// Fpga_LutLib_t s_LutLib = { "lutlib", 5, {0,1,1,1,1,1}, {0,1,1,1,1,1} };
- Fpga_LutLib_t s_LutLib = { "lutlib", 4, {0,1,1,1,1}, {0,1,1,1,1} };
+ Fpga_LutLib_t s_LutLib = { "lutlib", 5, {0,1,1,1,1,1}, {0,1,1,1,1,1} };
+// Fpga_LutLib_t s_LutLib = { "lutlib", 4, {0,1,1,1,1}, {0,1,1,1,1} };
//Fpga_LutLib_t s_LutLib = { "lutlib", 3, {0,1,1,1}, {0,1,1,1} };
Abc_FrameSetLibLut( Fpga_LutLibDup(&s_LutLib) );
diff --git a/src/map/fpga/fpgaCore.c b/src/map/fpga/fpgaCore.c
index 56facf20..634a8eb1 100644
--- a/src/map/fpga/fpgaCore.c
+++ b/src/map/fpga/fpgaCore.c
@@ -79,8 +79,12 @@ int Fpga_Mapping( Fpga_Man_t * p )
// print the AI-graph used for mapping
//Fpga_ManShow( p, "test" );
+// if ( p->fVerbose )
+// Fpga_MappingPrintOutputArrivals( p );
if ( p->fVerbose )
- Fpga_MappingPrintOutputArrivals( p );
+ {
+ PRT( "Total time", clock() - clkTotal );
+ }
return 1;
}
@@ -101,14 +105,14 @@ int Fpga_Mapping( Fpga_Man_t * p )
***********************************************************************/
int Fpga_MappingPostProcess( Fpga_Man_t * p )
{
- int fShowSwitching = 1;
+ int fShowSwitching = 0;
int fRecoverAreaFlow = 1;
int fRecoverArea = 1;
float aAreaTotalCur, aAreaTotalCur2;
int Iter, clk;
-if ( p->fVerbose )
- printf( "Best clock period = %5.2f\n", Fpga_TimeComputeArrivalMax(p) );
+//if ( p->fVerbose )
+// printf( "Best clock period = %5.2f\n", Fpga_TimeComputeArrivalMax(p) );
// compute area, set references, and collect nodes used in the mapping
Iter = 1;
@@ -118,6 +122,9 @@ if ( p->fVerbose )
printf( "Iteration %dD : Area = %8.1f ", Iter++, aAreaTotalCur );
if ( fShowSwitching )
printf( "Switch = %8.1f ", Fpga_MappingGetSwitching(p,p->vMapping) );
+else
+printf( "Delay = %5.2f ", Fpga_TimeComputeArrivalMax(p) );
+
PRT( "Time", p->timeMatch );
}
@@ -141,6 +148,8 @@ if ( p->fVerbose )
printf( "Iteration %dF : Area = %8.1f ", Iter++, aAreaTotalCur );
if ( fShowSwitching )
printf( "Switch = %8.1f ", Fpga_MappingGetSwitching(p,p->vMapping) );
+else
+printf( "Delay = %5.2f ", Fpga_TimeComputeArrivalMax(p) );
PRT( "Time", clock() - clk );
}
}
@@ -166,6 +175,8 @@ if ( p->fVerbose )
printf( "Iteration %d%s : Area = %8.1f ", Iter++, (p->fSwitching?"S":"A"), aAreaTotalCur );
if ( fShowSwitching )
printf( "Switch = %8.1f ", Fpga_MappingGetSwitching(p,p->vMapping) );
+else
+printf( "Delay = %5.2f ", Fpga_TimeComputeArrivalMax(p) );
PRT( "Time", clock() - clk );
}
}
diff --git a/src/map/fpga/fpgaCut.c b/src/map/fpga/fpgaCut.c
index c2aba4a3..a5505e72 100644
--- a/src/map/fpga/fpgaCut.c
+++ b/src/map/fpga/fpgaCut.c
@@ -130,6 +130,7 @@ void Fpga_MappingCuts( Fpga_Man_t * p )
Fpga_CutTable_t * pTable;
Fpga_Node_t * pNode;
int nCuts, nNodes, i;
+ int clk = clock();
// set the elementary cuts for the PI variables
assert( p->nVarsMax > 1 && p->nVarsMax < 11 );
@@ -154,8 +155,9 @@ void Fpga_MappingCuts( Fpga_Man_t * p )
if ( p->fVerbose )
{
nCuts = Fpga_CutCountAll(p);
- printf( "Nodes = %6d. Total %d-feasible cuts = %d. Cuts per node = %.1f.\n",
+ printf( "Nodes = %6d. Total %d-cuts = %d. Cuts per node = %.1f. ",
p->nNodes, p->nVarsMax, nCuts, ((float)nCuts)/p->nNodes );
+ PRT( "Time", clock() - clk );
}
// print the cuts for the first primary output
diff --git a/src/map/fpga/fpgaMatch.c b/src/map/fpga/fpgaMatch.c
index 736d38b2..d413a067 100644
--- a/src/map/fpga/fpgaMatch.c
+++ b/src/map/fpga/fpgaMatch.c
@@ -87,6 +87,18 @@ int Fpga_MappingMatches( Fpga_Man_t * p, int fDelayOriented )
Extra_ProgressBarUpdate( pProgress, i, "Matches ..." );
}
Extra_ProgressBarStop( pProgress );
+/*
+ if ( !fDelayOriented )
+ {
+ float Area = 0.0;
+ for ( i = 0; i < p->nOutputs; i++ )
+ {
+ printf( "%5.2f ", Fpga_Regular(p->pOutputs[i])->pCutBest->aFlow );
+ Area += Fpga_Regular(p->pOutputs[i])->pCutBest->aFlow;
+ }
+ printf( "\nTotal = %5.2f\n", Area );
+ }
+*/
return 1;
}
diff --git a/src/map/if/if.h b/src/map/if/if.h
index 04e1541e..a1d2d41b 100644
--- a/src/map/if/if.h
+++ b/src/map/if/if.h
@@ -75,8 +75,10 @@ struct If_Par_t_
If_Lib_t * pLutLib; // the LUT library
int nCutsMax; // the max number of cuts
int fVerbose; // the verbosity flag
- int fSeq; // sequential mapping
+ int fArea; // area-oriented mapping
+ int fFancy; // a fancy feature
int fLatchPaths; // reset timing on latch paths
+ int fSeq; // sequential mapping
int nLatches; // the number of latches
float DelayTarget; // delay target
float * pTimesArr; // arrival times
@@ -110,6 +112,9 @@ struct If_Man_t_
float fEpsilon; // epsilon used for comparison
float RequiredGlo; // global required times
float AreaGlo; // global area
+ int nCutsUsed; // the number of cuts currently used
+ int nCutsMerged; // the total number of cuts merged
+ int nCutsMax; // the maximum number of cuts at a node
// memory management
Mem_Fixed_t * pMem; // memory manager
int nEntrySize; // the size of the entry
@@ -123,7 +128,6 @@ struct If_Man_t_
struct If_Cut_t_
{
float Delay; // the delay of the cut
- float Flow; // the area flow of the cut
float Area; // the area of the cut
If_Cut_t * pOne; // the parent cut
If_Cut_t * pTwo; // the parent cut
@@ -162,6 +166,10 @@ static inline If_Obj_t * If_ManPo( If_Man_t * p, int i ) { r
static inline If_Obj_t * If_ManObj( If_Man_t * p, int i ) { return (If_Obj_t *)Vec_PtrEntry( p->vObjs, i ); }
static inline If_Cut_t * If_ManCut( If_Man_t * p, int i ) { return p->ppCuts[i]; }
+static inline int If_ManPiNum( If_Man_t * p ) { return p->nObjs[IF_PI]; }
+static inline int If_ManPoNum( If_Man_t * p ) { return p->nObjs[IF_PO]; }
+static inline int If_ManAndNum( If_Man_t * p ) { return p->nObjs[IF_AND]; }
+
static inline int If_ObjIsConst1( If_Obj_t * pObj ) { return pObj->Type == IF_CONST1; }
static inline int If_ObjIsPi( If_Obj_t * pObj ) { return pObj->Type == IF_PI; }
static inline int If_ObjIsPo( If_Obj_t * pObj ) { return pObj->Type == IF_PO; }
@@ -229,6 +237,8 @@ static inline float If_CutLutArea( If_Man_t * p, If_Cut_t * pCut ) { r
/// FUNCTION DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
+/*=== ifCore.c ==========================================================*/
+extern int If_ManPerformMapping( If_Man_t * p );
/*=== ifMan.c ==========================================================*/
extern If_Man_t * If_ManStart( If_Par_t * pPars );
extern void If_ManStop( If_Man_t * p );
@@ -236,11 +246,12 @@ extern If_Obj_t * If_ManCreatePi( If_Man_t * p );
extern If_Obj_t * If_ManCreatePo( If_Man_t * p, If_Obj_t * pDriver, int fCompl0 );
extern If_Obj_t * If_ManCreateAnd( If_Man_t * p, If_Obj_t * pFan0, int fCompl0, If_Obj_t * pFan1, int fCompl1 );
/*=== ifMap.c ==========================================================*/
-extern int If_ManPerformMapping( If_Man_t * p );
+extern void If_ObjPerformMapping( If_Man_t * p, If_Obj_t * pObj, int Mode );
/*=== ifUtil.c ==========================================================*/
extern float If_ManDelayMax( If_Man_t * p );
extern void If_ManCleanNodeCopy( If_Man_t * p );
extern void If_ManCleanCutData( If_Man_t * p );
+extern void If_ManComputeRequired( If_Man_t * p, int fFirstTime );
extern float If_ManScanMapping( If_Man_t * p );
#ifdef __cplusplus
diff --git a/src/map/if/ifCore.c b/src/map/if/ifCore.c
index 4d7e92d0..37a22d8b 100644
--- a/src/map/if/ifCore.c
+++ b/src/map/if/ifCore.c
@@ -24,6 +24,8 @@
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
+static int If_ManPerformMappingRound( If_Man_t * p, int nCutsUsed, int Mode );
+
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
@@ -39,6 +41,72 @@
SeeAlso []
***********************************************************************/
+int If_ManPerformMapping( If_Man_t * p )
+{
+ If_Obj_t * pObj;
+ int nItersFlow = 2;
+ int nItersArea = 1;
+ int clkTotal = clock();
+ int i;
+ // set arrival times and trivial cuts at const 1 and PIs
+ If_ManConst1(p)->Cuts[0].Delay = 0.0;
+ If_ManForEachPi( p, pObj, i )
+ pObj->Cuts[0].Delay = p->pPars->pTimesArr[i];
+ // set the fanout estimates of the PIs
+ If_ManForEachPi( p, pObj, i )
+ pObj->EstRefs = (float)1.0;
+ // delay oriented mapping
+ If_ManPerformMappingRound( p, p->pPars->nCutsMax, 0 );
+ // area flow oriented mapping
+ for ( i = 0; i < nItersFlow; i++ )
+ If_ManPerformMappingRound( p, p->pPars->nCutsMax, 1 );
+ // area oriented mapping
+ for ( i = 0; i < nItersArea; i++ )
+ If_ManPerformMappingRound( p, p->pPars->nCutsMax, 2 );
+ if ( p->pPars->fVerbose )
+ {
+ PRT( "Total time", clock() - clkTotal );
+ }
+ return 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManPerformMappingRound( If_Man_t * p, int nCutsUsed, int Mode )
+{
+ If_Obj_t * pObj;
+ int i, clk = clock();
+ assert( Mode >= 0 && Mode <= 2 );
+ // set the cut number
+ p->nCutsUsed = nCutsUsed;
+ p->nCutsMerged = 0;
+ p->nCutsMax = 0;
+ // map the internal nodes
+ If_ManForEachNode( p, pObj, i )
+ If_ObjPerformMapping( p, pObj, Mode );
+ // compute required times and stats
+ If_ManComputeRequired( p, Mode==0 );
+ if ( p->pPars->fVerbose )
+ {
+ char Symb = (Mode == 0)? 'D' : ((Mode == 1)? 'F' : 'A');
+ printf( "%c: Del = %6.2f. Area = %8.2f. Cuts = %6d. Lim = %2d. Ave = %5.2f. ",
+ Symb, p->RequiredGlo, p->AreaGlo, p->nCutsMerged, p->nCutsUsed, 1.0 * p->nCutsMerged / If_ManAndNum(p) );
+ PRT( "T", clock() - clk );
+// printf( "Max number of cuts = %d. Average number of cuts = %5.2f.\n",
+// p->nCutsMax, 1.0 * p->nCutsMerged / If_ManAndNum(p) );
+ }
+ return 1;
+}
+
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
diff --git a/src/map/if/ifMan.c b/src/map/if/ifMan.c
index 616c5cf6..bc13c6f0 100644
--- a/src/map/if/ifMan.c
+++ b/src/map/if/ifMan.c
@@ -97,7 +97,7 @@ void If_ManStop( If_Man_t * p )
FREE( p->pPars->pTimesReq );
// free temporary cut memory
pTemp = p->ppCuts[0];
- for ( i = 1; i < p->pPars->nCutsMax * p->pPars->nCutsMax; i++ )
+ for ( i = 1; i < 1 + p->pPars->nCutsMax * p->pPars->nCutsMax; i++ )
if ( pTemp > p->ppCuts[i] )
pTemp = p->ppCuts[i];
free( pTemp );
@@ -228,14 +228,18 @@ If_Cut_t ** If_ManSetupCuts( If_Man_t * p )
{
If_Cut_t ** pCutStore;
int * pArrays, nCutSize, nCutsTotal, i;
- nCutsTotal = p->pPars->nCutsMax * p->pPars->nCutsMax;
+ // decide how many cuts to alloc
+ nCutsTotal = 1 + p->pPars->nCutsMax * p->pPars->nCutsMax;
+ // figure out the cut size
nCutSize = sizeof(If_Cut_t) + sizeof(int) * p->pPars->nLutSize;
+ // allocate and clean space for cuts
pCutStore = (If_Cut_t **)ALLOC( If_Cut_t *, (nCutsTotal + 1) );
memset( pCutStore, 0, sizeof(If_Cut_t *) * (nCutsTotal + 1) );
pCutStore[0] = (If_Cut_t *)ALLOC( char, nCutSize * nCutsTotal );
memset( pCutStore[0], 0, nCutSize * nCutsTotal );
for ( i = 1; i < nCutsTotal; i++ )
pCutStore[i] = (If_Cut_t *)((char *)pCutStore[0] + sizeof(If_Cut_t) * i);
+ // assign room for cut leaves
pArrays = (int *)((char *)pCutStore[0] + sizeof(If_Cut_t) * nCutsTotal);
for ( i = 0; i < nCutsTotal; i++ )
pCutStore[i]->pLeaves = pArrays + i * p->pPars->nLutSize;
diff --git a/src/map/if/ifMap.c b/src/map/if/ifMap.c
index 5f2c4133..0b505062 100644
--- a/src/map/if/ifMap.c
+++ b/src/map/if/ifMap.c
@@ -24,13 +24,69 @@
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
+/*
+ Ideas to try:
+ - reverse order of area recovery
+ - ordering of the outputs by size
+ - merging Delay, Delay2, and Area
+ - expand/reduce area recovery
+
+*/
+
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
- Synopsis [Prepares the object for FPGA mapping.]
+ Synopsis [Returns 1 if pDom is contained in pCut.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline int If_CutCheckDominance( If_Cut_t * pDom, If_Cut_t * pCut )
+{
+ int i, k;
+ for ( i = 0; i < (int)pDom->nLeaves; i++ )
+ {
+ for ( k = 0; k < (int)pCut->nLeaves; k++ )
+ if ( pDom->pLeaves[i] == pCut->pLeaves[k] )
+ break;
+ if ( k == (int)pCut->nLeaves ) // node i in pDom is not contained in pCut
+ return 0;
+ }
+ // every node in pDom is contained in pCut
+ return 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Returns 1 if pDom is equal to pCut.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline int If_CutCheckEquality( If_Cut_t * pDom, If_Cut_t * pCut )
+{
+ int i;
+ if ( (int)pDom->nLeaves != (int)pCut->nLeaves )
+ return 0;
+ for ( i = 0; i < (int)pDom->nLeaves; i++ )
+ if ( pDom->pLeaves[i] != pCut->pLeaves[i] )
+ return 0;
+ return 1;
+}
+/**Function*************************************************************
+
+ Synopsis [Returns 1 if the cut is contained.]
Description []
@@ -39,8 +95,39 @@
SeeAlso []
***********************************************************************/
-int If_CutMerge( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC, int nLimit )
+int If_CutFilter( If_Man_t * p, If_Cut_t * pCut )
{
+ If_Cut_t * pTemp;
+ int i;
+ for ( i = 0; i < p->nCuts; i++ )
+ {
+ pTemp = p->ppCuts[i];
+ if ( pTemp->nLeaves > pCut->nLeaves )
+ continue;
+ // skip the non-contained cuts
+// if ( (pTemp->uSign & pCut->uSign) != pTemp->uSign )
+// continue;
+ // check containment seriously
+ if ( If_CutCheckDominance( pTemp, pCut ) )
+// if ( If_CutCheckEquality( pTemp, pCut ) )
+ return 1;
+ }
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prepares the object for FPGA mapping.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_CutMergeOrdered( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC, int nLimit )
+{
int i, k, c;
assert( pC0->nLeaves >= pC1->nLeaves );
// the case of the largest cut sizes
@@ -114,6 +201,33 @@ int If_CutMerge( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC, int nLimit )
return 1;
}
+/**Function*************************************************************
+
+ Synopsis [Prepares the object for FPGA mapping.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline int If_CutMerge( If_Cut_t * pCut0, If_Cut_t * pCut1, If_Cut_t * pCut, int nLimit )
+{
+ // merge the nodes
+ if ( pCut0->nLeaves < pCut1->nLeaves )
+ {
+ if ( !If_CutMergeOrdered( pCut1, pCut0, pCut, nLimit ) )
+ return 0;
+ }
+ else
+ {
+ if ( !If_CutMergeOrdered( pCut0, pCut1, pCut, nLimit ) )
+ return 0;
+ }
+ return 1;
+}
+
/**Function*************************************************************
Synopsis [Prepares the object for FPGA mapping.]
@@ -137,9 +251,39 @@ int If_CutCompareDelay( If_Cut_t ** ppC0, If_Cut_t ** ppC1 )
return -1;
if ( pC0->nLeaves > pC1->nLeaves )
return 1;
- if ( pC0->Flow < pC1->Flow )
+ if ( pC0->Area < pC1->Area )
return -1;
- if ( pC0->Flow > pC1->Flow )
+ if ( pC0->Area > pC1->Area )
+ return 1;
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prepares the object for FPGA mapping.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_CutCompareDelayOld( If_Cut_t ** ppC0, If_Cut_t ** ppC1 )
+{
+ If_Cut_t * pC0 = *ppC0;
+ If_Cut_t * pC1 = *ppC1;
+ if ( pC0->Delay < pC1->Delay )
+ return -1;
+ if ( pC0->Delay > pC1->Delay )
+ return 1;
+ if ( pC0->Area < pC1->Area )
+ return -1;
+ if ( pC0->Area > pC1->Area )
+ return 1;
+ if ( pC0->nLeaves < pC1->nLeaves )
+ return -1;
+ if ( pC0->nLeaves > pC1->nLeaves )
return 1;
return 0;
}
@@ -159,9 +303,9 @@ int If_CutCompareArea( If_Cut_t ** ppC0, If_Cut_t ** ppC1 )
{
If_Cut_t * pC0 = *ppC0;
If_Cut_t * pC1 = *ppC1;
- if ( pC0->Flow < pC1->Flow )
+ if ( pC0->Area < pC1->Area )
return -1;
- if ( pC0->Flow > pC1->Flow )
+ if ( pC0->Area > pC1->Area )
return 1;
if ( pC0->nLeaves < pC1->nLeaves )
return -1;
@@ -174,6 +318,28 @@ int If_CutCompareArea( If_Cut_t ** ppC0, If_Cut_t ** ppC1 )
return 0;
}
+/**Function*************************************************************
+
+ Synopsis [Sorts the cuts.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManSortCuts( If_Man_t * p, int Mode )
+{
+ // sort the cuts
+ if ( Mode || p->pPars->fArea ) // area
+ qsort( p->ppCuts, p->nCuts, sizeof(If_Cut_t *), (int (*)(const void *, const void *))If_CutCompareArea );
+ else if ( p->pPars->fFancy )
+ qsort( p->ppCuts, p->nCuts, sizeof(If_Cut_t *), (int (*)(const void *, const void *))If_CutCompareDelayOld );
+ else
+ qsort( p->ppCuts, p->nCuts, sizeof(If_Cut_t *), (int (*)(const void *, const void *))If_CutCompareDelay );
+}
+
/**Function*************************************************************
Synopsis [Computes delay.]
@@ -190,6 +356,7 @@ float If_CutDelay( If_Man_t * p, If_Cut_t * pCut )
If_Obj_t * pLeaf;
float Delay;
int i;
+ assert( pCut->nLeaves > 1 );
Delay = -IF_FLOAT_LARGE;
If_CutForEachLeaf( p, pCut, pLeaf, i )
Delay = IF_MAX( Delay, If_ObjCutBest(pLeaf)->Delay );
@@ -212,9 +379,18 @@ float If_CutFlow( If_Man_t * p, If_Cut_t * pCut )
If_Obj_t * pLeaf;
float Flow;
int i;
+ assert( pCut->nLeaves > 1 );
Flow = If_CutLutArea(p, pCut);
If_CutForEachLeaf( p, pCut, pLeaf, i )
- Flow += If_ObjCutBest(pLeaf)->Flow / pLeaf->EstRefs;
+ {
+ if ( pLeaf->nRefs == 0 )
+ Flow += If_ObjCutBest(pLeaf)->Area;
+ else
+ {
+ assert( pLeaf->EstRefs > p->fEpsilon );
+ Flow += If_ObjCutBest(pLeaf)->Area / pLeaf->EstRefs;
+ }
+ }
return Flow;
}
@@ -229,15 +405,19 @@ float If_CutFlow( If_Man_t * p, If_Cut_t * pCut )
SeeAlso []
***********************************************************************/
-float If_CutArea1( If_Man_t * p, If_Cut_t * pCut )
+float If_CutRef( If_Man_t * p, If_Cut_t * pCut, int nLevels )
{
If_Obj_t * pLeaf;
float Area;
int i;
Area = If_CutLutArea(p, pCut);
If_CutForEachLeaf( p, pCut, pLeaf, i )
- if ( pLeaf->nRefs == 0 )
- Area += If_CutLutArea(p, If_ObjCutBest(pLeaf));
+ {
+ assert( pLeaf->nRefs >= 0 );
+ if ( pLeaf->nRefs++ > 0 || !If_ObjIsAnd(pLeaf) || nLevels == 1 )
+ continue;
+ Area += If_CutRef( p, If_ObjCutBest(pLeaf), nLevels - 1 );
+ }
return Area;
}
@@ -252,12 +432,20 @@ float If_CutArea1( If_Man_t * p, If_Cut_t * pCut )
SeeAlso []
***********************************************************************/
-void If_CutRef1( If_Man_t * p, If_Cut_t * pCut )
+float If_CutDeref( If_Man_t * p, If_Cut_t * pCut, int nLevels )
{
If_Obj_t * pLeaf;
+ float Area;
int i;
+ Area = If_CutLutArea(p, pCut);
If_CutForEachLeaf( p, pCut, pLeaf, i )
- pLeaf->nRefs++;
+ {
+ assert( pLeaf->nRefs > 0 );
+ if ( --pLeaf->nRefs > 0 || !If_ObjIsAnd(pLeaf) || nLevels == 1 )
+ continue;
+ Area += If_CutDeref( p, If_ObjCutBest(pLeaf), nLevels - 1 );
+ }
+ return Area;
}
/**Function*************************************************************
@@ -271,12 +459,14 @@ void If_CutRef1( If_Man_t * p, If_Cut_t * pCut )
SeeAlso []
***********************************************************************/
-void If_CutDeref1( If_Man_t * p, If_Cut_t * pCut )
+float If_CutArea( If_Man_t * p, If_Cut_t * pCut, int nLevels )
{
- If_Obj_t * pLeaf;
- int i;
- If_CutForEachLeaf( p, pCut, pLeaf, i )
- pLeaf->nRefs--;
+ float aResult, aResult2;
+ assert( pCut->nLeaves > 1 );
+ aResult2 = If_CutRef( p, pCut, nLevels );
+ aResult = If_CutDeref( p, pCut, nLevels );
+ assert( aResult == aResult2 );
+ return aResult;
}
/**Function*************************************************************
@@ -303,85 +493,85 @@ void If_CutCopy( If_Cut_t * pCutDest, If_Cut_t * pCutSrc )
Synopsis [Finds the best cut.]
- Description []
+ Description [Mapping modes: delay (0), area flow (1), area (2).]
SideEffects []
SeeAlso []
***********************************************************************/
-void If_ObjPerformMapping( If_Man_t * p, If_Obj_t * pObj )
+void If_ObjPerformMapping( If_Man_t * p, If_Obj_t * pObj, int Mode )
{
If_Cut_t * pCut0, * pCut1, * pCut;
int i, k;
- // create cross-product of the cuts
+
+ // prepare
+ if ( Mode == 0 )
+ pObj->EstRefs = (float)pObj->nRefs;
+ else if ( Mode == 1 )
+ pObj->EstRefs = (float)((2.0 * pObj->EstRefs + pObj->nRefs) / 3.0);
+ else if ( Mode == 2 && pObj->nRefs > 0 )
+ If_CutDeref( p, If_ObjCutBest(pObj), 100 );
+
+ // recompute the parameters of the best cut
p->nCuts = 0;
- pCut = p->ppCuts[0];
+ p->nCutsMerged++;
+ if ( Mode )
+ {
+ pCut = If_ObjCutBest(pObj);
+ pCut->Delay = If_CutDelay( p, pCut );
+ assert( pCut->Delay <= pObj->Required + p->fEpsilon );
+ pCut->Area = (Mode == 2)? If_CutArea( p, pCut, 100 ) : If_CutFlow( p, pCut );
+ // save the best cut from the previous iteration
+ If_CutCopy( p->ppCuts[p->nCuts++], pCut );
+ p->nCutsMerged++;
+ }
+
+ // generate cuts
+ pCut = p->ppCuts[p->nCuts];
If_ObjForEachCut( pObj->pFanin0, pCut0, i )
If_ObjForEachCut( pObj->pFanin1, pCut1, k )
{
- if ( pCut0->nLeaves < pCut1->nLeaves )
- {
- if ( !If_CutMerge( pCut1, pCut0, pCut, p->pPars->nLutSize ) )
- continue;
- }
- else
- {
- if ( !If_CutMerge( pCut0, pCut1, pCut, p->pPars->nLutSize ) )
- continue;
- }
+ // prefilter using arrival times
+ if ( Mode && (pCut0->Delay > pObj->Required + p->fEpsilon || pCut1->Delay > pObj->Required + p->fEpsilon) )
+ continue;
+ // merge the nodes
+ if ( !If_CutMerge( pCut0, pCut1, pCut, p->pPars->nLutSize ) )
+ continue;
+ // check if this cut is contained in any of the available cuts
+ if ( If_CutFilter( p, pCut ) )
+ continue;
+ // check if the cut satisfies the required times
+ pCut->Delay = If_CutDelay( p, pCut );
+ if ( Mode && pCut->Delay > pObj->Required + p->fEpsilon )
+ continue;
// the cuts have been successfully merged
pCut->pOne = pCut0; pCut->fCompl0 = pObj->fCompl0;
pCut->pTwo = pCut1; pCut->fCompl1 = pObj->fCompl1;
// pCut->Phase = ...
- pCut->Delay = If_CutDelay( p, pCut );
- pCut->Flow = If_CutFlow( p, pCut );
+ pCut->Area = (Mode == 2)? If_CutArea( p, pCut, 100 ) : If_CutFlow( p, pCut );
+ p->nCutsMerged++;
// prepare room for the next cut
pCut = p->ppCuts[++p->nCuts];
}
- // sort the cuts
- if ( p->pPars->Mode == 1 ) // delay
- qsort( p->ppCuts, p->nCuts, sizeof(If_Cut_t *), (int (*)(const void *, const void *))If_CutCompareDelay );
- else
- qsort( p->ppCuts, p->nCuts, sizeof(If_Cut_t *), (int (*)(const void *, const void *))If_CutCompareArea );
+ assert( p->nCuts > 0 );
+ If_ManSortCuts( p, Mode );
// take the first
- pObj->nCuts = IF_MIN( p->nCuts + 1, p->pPars->nCutsMax );
+ pObj->nCuts = IF_MIN( p->nCuts + 1, p->nCutsUsed );
If_ObjForEachCutStart( pObj, pCut, i, 1 )
If_CutCopy( pCut, p->ppCuts[i-1] );
pObj->iCut = 1;
-}
-
-/**Function*************************************************************
-
- Synopsis [Maps the nodes for delay.]
-
- Description []
-
- SideEffects []
-
- SeeAlso []
-
-***********************************************************************/
-int If_ManPerformMapping( If_Man_t * p )
-{
- If_Obj_t * pObj;
- float DelayBest;
- int i, clk = clock();
- // set arrival times and trivial cuts at const 1 and PIs
- If_ManConst1(p)->Cuts[0].Delay = 0.0;
- If_ManForEachPi( p, pObj, i )
- pObj->Cuts[0].Delay = p->pPars->pTimesArr[i];
- // set the initial fanout estimates
- If_ManForEachObj( p, pObj, i )
- pObj->EstRefs = (float)pObj->nRefs;
- // map the internal nodes
- If_ManForEachNode( p, pObj, i )
- If_ObjPerformMapping( p, pObj );
- // get the best arrival time of the POs
- DelayBest = If_ManDelayMax(p);
- printf( "Best delay = %d. ", (int)DelayBest );
- PRT( "Time", clock() - clk );
- return 1;
+ assert( If_ObjCutBest(pObj)->nLeaves > 1 );
+ // assign delay of the trivial cut
+ If_ObjCutTriv(pObj)->Delay = If_ObjCutBest(pObj)->Delay;
+//printf( "%d %d ", pObj->Id, (int)If_ObjCutBest(pObj)->Delay );
+//printf( "%d %d ", pObj->Id, pObj->nCuts );
+ // ref the selected cut
+ if ( Mode == 2 && pObj->nRefs > 0 )
+ If_CutRef( p, If_ObjCutBest(pObj), 100 );
+ // find the largest cut
+ if ( p->nCutsMax < pObj->nCuts )
+ p->nCutsMax = pObj->nCuts;
}
////////////////////////////////////////////////////////////////////////
diff --git a/src/map/mapper/mapperCut.c b/src/map/mapper/mapperCut.c
index 9dad07d0..91ef6562 100644
--- a/src/map/mapper/mapperCut.c
+++ b/src/map/mapper/mapperCut.c
@@ -612,7 +612,8 @@ int Map_CutMergeTwo( Map_Cut_t * pCut1, Map_Cut_t * pCut2, Map_Node_t * ppNodes[
{
min = i;
for ( k = i+1; k < nTotal; k++ )
- if ( ppNodes[k] < ppNodes[min] )
+// if ( ppNodes[k] < ppNodes[min] ) // reported bug fix (non-determinism!)
+ if ( ppNodes[k]->Num < ppNodes[min]->Num )
min = k;
pNodeTemp = ppNodes[i];
ppNodes[i] = ppNodes[min];
--
cgit v1.2.3