From 33012d9530c40817e1fc5230b3e663f7690b2e94 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sun, 4 Sep 2005 08:01:00 -0700 Subject: Version abc50904 --- src/map/fpga/fpga.h | 2 + src/map/fpga/fpgaCore.c | 41 +++++++---- src/map/fpga/fpgaCreate.c | 2 + src/map/fpga/fpgaCutUtils.c | 103 -------------------------- src/map/fpga/fpgaInt.h | 17 ++--- src/map/fpga/fpgaMatch.c | 2 +- src/map/fpga/fpgaSwitch.c | 176 ++++++++++++++++++++++++++++++++++++++++++++ src/map/fpga/fpgaUtils.c | 37 ---------- src/map/fpga/module.make | 1 + 9 files changed, 214 insertions(+), 167 deletions(-) create mode 100644 src/map/fpga/fpgaSwitch.c (limited to 'src/map/fpga') diff --git a/src/map/fpga/fpga.h b/src/map/fpga/fpga.h index 9dad1670..19241a74 100644 --- a/src/map/fpga/fpga.h +++ b/src/map/fpga/fpga.h @@ -91,6 +91,7 @@ extern void Fpga_ManSetFanoutViolations( Fpga_Man_t * p, int nVio ); extern void Fpga_ManSetChoiceNodeNum( Fpga_Man_t * p, int nChoiceNodes ); extern void Fpga_ManSetChoiceNum( Fpga_Man_t * p, int nChoices ); extern void Fpga_ManSetVerbose( Fpga_Man_t * p, int fVerbose ); +extern void Fpga_ManSetSwitching( Fpga_Man_t * p, int fSwitching ); extern void Fpga_ManSetLatchNum( Fpga_Man_t * p, int nLatches ); extern void Fpga_ManSetName( Fpga_Man_t * p, char * pFileName ); @@ -110,6 +111,7 @@ extern void Fpga_NodeSetData1( Fpga_Node_t * p, Fpga_Node_t * pNode ) extern void Fpga_NodeSetArrival( Fpga_Node_t * p, float Time ); extern void Fpga_NodeSetNextE( Fpga_Node_t * p, Fpga_Node_t * pNextE ); extern void Fpga_NodeSetRepr( Fpga_Node_t * p, Fpga_Node_t * pRepr ); +extern void Fpga_NodeSetSwitching( Fpga_Node_t * p, float Switching ); extern int Fpga_NodeIsConst( Fpga_Node_t * p ); extern int Fpga_NodeIsVar( Fpga_Node_t * p ); diff --git a/src/map/fpga/fpgaCore.c b/src/map/fpga/fpgaCore.c index 0fc90228..95b9ca49 100644 --- a/src/map/fpga/fpgaCore.c +++ b/src/map/fpga/fpgaCore.c @@ -97,22 +97,26 @@ int Fpga_Mapping( Fpga_Man_t * p ) ***********************************************************************/ int Fpga_MappingPostProcess( Fpga_Man_t * p ) { - float aAreaTotalPrev, aAreaTotalCur, aAreaTotalCur2; + int fShowSwitching = 0; + int fRecoverAreaFlow = 1; + int fRecoverArea = 1; + float aAreaTotalCur, aAreaTotalCur2; int Iter, clk; // compute area, set references, and collect nodes used in the mapping + Iter = 1; aAreaTotalCur = Fpga_MappingSetRefsAndArea( p ); if ( p->fVerbose ) { -printf( "Iteration %dD : Area = %11.1f ", 0, aAreaTotalCur ); +printf( "Iteration %dD : Area = %8.1f ", Iter++, aAreaTotalCur ); +if ( fShowSwitching ) +printf( "Switch = %8.1f ", Fpga_MappingGetSwitching(p,p->vMapping) ); PRT( "Time", p->timeMatch ); } - Iter = 1; - do { + if ( fRecoverAreaFlow ) + { clk = clock(); - // save the previous area flow - aAreaTotalPrev = aAreaTotalCur; // compute the required times and the fanouts Fpga_TimeComputeRequiredGlobal( p ); // remap topologically @@ -124,33 +128,38 @@ clk = clock(); // for some reason, this works better on benchmarks if ( p->fVerbose ) { -printf( "Iteration %dF : Area = %11.1f ", Iter++, aAreaTotalCur ); +printf( "Iteration %dF : Area = %8.1f ", Iter++, aAreaTotalCur ); +if ( fShowSwitching ) +printf( "Switch = %8.1f ", Fpga_MappingGetSwitching(p,p->vMapping) ); PRT( "Time", clock() - clk ); } - // quit if this iteration reduced area flow by less than 1% - } while ( aAreaTotalPrev > 1.02 * aAreaTotalCur ); + } // update reference counters aAreaTotalCur2 = Fpga_MappingSetRefsAndArea( p ); assert( aAreaTotalCur == aAreaTotalCur2 ); - do { + if ( fRecoverArea ) + { clk = clock(); - // save the previous area flow - aAreaTotalPrev = aAreaTotalCur; // compute the required times and the fanouts Fpga_TimeComputeRequiredGlobal( p ); // remap topologically - Fpga_MappingMatchesArea( p ); + if ( p->fSwitching ) + Fpga_MappingMatchesSwitch( p ); + else + Fpga_MappingMatchesArea( p ); // get the resulting area aAreaTotalCur = Fpga_MappingSetRefsAndArea( p ); if ( p->fVerbose ) { -printf( "Iteration %dA : Area = %11.1f ", Iter++, aAreaTotalCur ); +printf( "Iteration %d%s : Area = %8.1f ", Iter++, (p->fSwitching?"S":"A"), aAreaTotalCur ); +if ( fShowSwitching ) +printf( "Switch = %8.1f ", Fpga_MappingGetSwitching(p,p->vMapping) ); PRT( "Time", clock() - clk ); } - // quit if this iteration reduced area flow by less than 1% - } while ( aAreaTotalPrev > 1.02 * aAreaTotalCur ); + } + p->fAreaGlo = aAreaTotalCur; return 1; } diff --git a/src/map/fpga/fpgaCreate.c b/src/map/fpga/fpgaCreate.c index f3abbedb..b7bfa3c5 100644 --- a/src/map/fpga/fpgaCreate.c +++ b/src/map/fpga/fpgaCreate.c @@ -65,6 +65,7 @@ void Fpga_ManSetTimeLimit( Fpga_Man_t * p, float TimeLimit ) { p void Fpga_ManSetChoiceNodeNum( Fpga_Man_t * p, int nChoiceNodes ) { p->nChoiceNodes = nChoiceNodes; } void Fpga_ManSetChoiceNum( Fpga_Man_t * p, int nChoices ) { p->nChoices = nChoices; } void Fpga_ManSetVerbose( Fpga_Man_t * p, int fVerbose ) { p->fVerbose = fVerbose; } +void Fpga_ManSetSwitching( Fpga_Man_t * p, int fSwitching ) { p->fSwitching = fSwitching; } void Fpga_ManSetLatchNum( Fpga_Man_t * p, int nLatches ) { p->nLatches = nLatches; } void Fpga_ManSetName( Fpga_Man_t * p, char * pFileName ) { p->pFileName = pFileName; } @@ -104,6 +105,7 @@ void Fpga_NodeSetData0( Fpga_Node_t * p, char * pData ) { p-> void Fpga_NodeSetData1( Fpga_Node_t * p, Fpga_Node_t * pNode ) { p->pLevel = pNode; } void Fpga_NodeSetNextE( Fpga_Node_t * p, Fpga_Node_t * pNextE ) { p->pNextE = pNextE; } void Fpga_NodeSetRepr( Fpga_Node_t * p, Fpga_Node_t * pRepr ) { p->pRepr = pRepr; } +void Fpga_NodeSetSwitching( Fpga_Node_t * p, float Switching ) { p->Switching = Switching; } /**Function************************************************************* diff --git a/src/map/fpga/fpgaCutUtils.c b/src/map/fpga/fpgaCutUtils.c index abe703a2..2419cac4 100644 --- a/src/map/fpga/fpgaCutUtils.c +++ b/src/map/fpga/fpgaCutUtils.c @@ -439,109 +439,6 @@ float Fpga_CutDeref( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, } - -/**function************************************************************* - - synopsis [Computes the exact area associated with the cut.] - - description [] - - sideeffects [] - - seealso [] - -***********************************************************************/ -float Fpga_CutGetSwitchDerefed( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut ) -{ - float aResult, aResult2; - if ( pCut->nLeaves == 1 ) - return 0; - aResult2 = Fpga_CutRefSwitch( pMan, pNode, pCut, 0 ); - aResult = Fpga_CutDerefSwitch( pMan, pNode, pCut, 0 ); -// assert( aResult == aResult2 ); - return aResult; -} - -/**function************************************************************* - - synopsis [References the cut.] - - description [This procedure is similar to the procedure NodeReclaim.] - - sideeffects [] - - seealso [] - -***********************************************************************/ -float Fpga_CutRefSwitch( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts ) -{ - Fpga_Node_t * pNodeChild; - float aArea; - int i; - - // deref the fanouts -// if ( fFanouts ) -// Fpga_CutInsertFanouts( pMan, pNode, pCut ); - - // start the area of this cut - aArea = pNode->SwitchProb; - // go through the children - for ( i = 0; i < pCut->nLeaves; i++ ) - { - pNodeChild = pCut->ppLeaves[i]; - assert( pNodeChild->nRefs >= 0 ); - if ( pNodeChild->nRefs++ > 0 ) - continue; - if ( !Fpga_NodeIsAnd(pNodeChild) ) - { - aArea += pNodeChild->SwitchProb; - continue; - } - aArea += Fpga_CutRefSwitch( pMan, pNodeChild, pNodeChild->pCutBest, fFanouts ); - } - return aArea; -} - -/**function************************************************************* - - synopsis [Dereferences the cut.] - - description [This procedure is similar to the procedure NodeRecusiveDeref.] - - sideeffects [] - - seealso [] - -***********************************************************************/ -float Fpga_CutDerefSwitch( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts ) -{ - Fpga_Node_t * pNodeChild; - float aArea; - int i; - - // deref the fanouts -// if ( fFanouts ) -// Fpga_CutRemoveFanouts( pMan, pNode, pCut ); - - // start the area of this cut - aArea = pNode->SwitchProb; - // go through the children - for ( i = 0; i < pCut->nLeaves; i++ ) - { - pNodeChild = pCut->ppLeaves[i]; - assert( pNodeChild->nRefs > 0 ); - if ( --pNodeChild->nRefs > 0 ) - continue; - if ( !Fpga_NodeIsAnd(pNodeChild) ) - { - aArea += pNodeChild->SwitchProb; - continue; - } - aArea += Fpga_CutDerefSwitch( pMan, pNodeChild, pNodeChild->pCutBest, fFanouts ); - } - return aArea; -} - /**Function************************************************************* Synopsis [Sets the used cuts to be the currently selected ones.] diff --git a/src/map/fpga/fpgaInt.h b/src/map/fpga/fpgaInt.h index 95203378..ec6057a7 100644 --- a/src/map/fpga/fpgaInt.h +++ b/src/map/fpga/fpgaInt.h @@ -120,12 +120,9 @@ struct Fpga_ManStruct_t_ // mapping parameters int nVarsMax; // the max number of variables -// int fTree; // the flag to enable tree mapping -// int fPower; // the flag to enable power optimization int fAreaRecovery; // the flag to use area flow as the first parameter int fVerbose; // the verbosiness flag -// int fRefCount; // enables reference counting -// int fSequential; // use sequential mapping + int fSwitching; // minimize the switching activity (instead of area) int nTravIds; // support of choice nodes @@ -137,7 +134,6 @@ struct Fpga_ManStruct_t_ // the supergate library Fpga_LutLib_t * pLutLib; // the current LUT library -// unsigned uTruths[6][2]; // the elementary truth tables // the memory managers Extra_MmFixed_t * mmNodes; // the memory manager for nodes @@ -215,7 +211,7 @@ struct Fpga_NodeStruct_t_ // the delay information float tRequired; // the best area flow float aEstFanouts; // the fanout estimation - float SwitchProb; // the probability of switching + float Switching; // the probability of switching int LValue; // the l-value of the node short nLatches1; // the number of latches on the first edge short nLatches2; // the number of latches on the second edge @@ -308,9 +304,6 @@ extern float Fpga_CutGetAreaRefed( Fpga_Man_t * pMan, Fpga_Cut_t * p extern float Fpga_CutGetAreaDerefed( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ); extern float Fpga_CutRef( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts ); extern float Fpga_CutDeref( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts ); -extern float Fpga_CutGetSwitchDerefed( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut ); -extern float Fpga_CutRefSwitch( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts ); -extern float Fpga_CutDerefSwitch( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts ); extern float Fpga_CutGetAreaFlow( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ); extern void Fpga_CutGetParameters( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ); /*=== fraigFanout.c =============================================================*/ @@ -329,6 +322,11 @@ extern int Fpga_MappingMatchesSwitch( Fpga_Man_t * p ); /*=== fpgaShow.c =============================================================*/ extern void Fpga_MappingShow( Fpga_Man_t * pMan, char * pFileName ); extern void Fpga_MappingShowNodes( Fpga_Man_t * pMan, Fpga_Node_t ** ppRoots, int nRoots, char * pFileName ); +/*=== fpgaSwitch.c =============================================================*/ +extern float Fpga_CutGetSwitchDerefed( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut ); +extern float Fpga_CutRefSwitch( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts ); +extern float Fpga_CutDerefSwitch( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts ); +extern float Fpga_MappingGetSwitching( Fpga_Man_t * pMan, Fpga_NodeVec_t * vMapping ); /*=== fpgaTime.c ===============================================================*/ extern float Fpga_TimeCutComputeArrival( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ); extern float Fpga_TimeCutComputeArrival_rec( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ); @@ -370,7 +368,6 @@ extern void Fpga_MappingSetupMask( unsigned uMask[], int nVarsMax ) extern void Fpga_MappingSortByLevel( Fpga_Man_t * pMan, Fpga_NodeVec_t * vNodes, int fIncreasing ); extern Fpga_NodeVec_t * Fpga_DfsLim( Fpga_Man_t * pMan, Fpga_Node_t * pNode, int nLevels ); extern Fpga_NodeVec_t * Fpga_MappingLevelize( Fpga_Man_t * pMan, Fpga_NodeVec_t * vNodes ); -extern float Fpga_MappingPrintSwitching( Fpga_Man_t * pMan ); extern int Fpga_MappingMaxLevel( Fpga_Man_t * pMan ); extern void Fpga_ManReportChoices( Fpga_Man_t * pMan ); extern void Fpga_MappingSetChoiceLevels( Fpga_Man_t * pMan ); diff --git a/src/map/fpga/fpgaMatch.c b/src/map/fpga/fpgaMatch.c index 63ee682d..20444209 100644 --- a/src/map/fpga/fpgaMatch.c +++ b/src/map/fpga/fpgaMatch.c @@ -432,7 +432,7 @@ clk = clock(); if ( pNode->nRefs ) { pNode->pCutBest->aFlow = Fpga_CutRefSwitch( p, pNode, pNode->pCutBest, 0 ); - assert( pNode->pCutBest->aFlow <= aAreaCutBest ); + assert( pNode->pCutBest->aFlow <= aAreaCutBest + 0.001 ); // assert( pNode->tRequired < FPGA_FLOAT_LARGE ); } return 1; diff --git a/src/map/fpga/fpgaSwitch.c b/src/map/fpga/fpgaSwitch.c new file mode 100644 index 00000000..0d2ec3fc --- /dev/null +++ b/src/map/fpga/fpgaSwitch.c @@ -0,0 +1,176 @@ +/**CFile**************************************************************** + + FileName [fpgaSwitch.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Generic technology mapping engine.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - September 8, 2003.] + + Revision [$Id: fpgaSwitch.h,v 1.0 2003/09/08 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "fpgaInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static float Fpga_CutGetSwitching( Fpga_Cut_t * pCut ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**function************************************************************* + + synopsis [Computes the exact area associated with the cut.] + + description [] + + sideeffects [] + + seealso [] + +***********************************************************************/ +float Fpga_CutGetSwitchDerefed( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut ) +{ + float aResult, aResult2; + aResult2 = Fpga_CutRefSwitch( pMan, pNode, pCut, 0 ); + aResult = Fpga_CutDerefSwitch( pMan, pNode, pCut, 0 ); +// assert( aResult == aResult2 ); + return aResult; +} + +/**function************************************************************* + + synopsis [References the cut.] + + description [This procedure is similar to the procedure NodeReclaim.] + + sideeffects [] + + seealso [] + +***********************************************************************/ +float Fpga_CutRefSwitch( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts ) +{ + Fpga_Node_t * pNodeChild; + float aArea; + int i; + if ( pCut->nLeaves == 1 ) + return 0; + // start the area of this cut + aArea = Fpga_CutGetSwitching( pCut ); + // go through the children + for ( i = 0; i < pCut->nLeaves; i++ ) + { + pNodeChild = pCut->ppLeaves[i]; + assert( pNodeChild->nRefs >= 0 ); + if ( pNodeChild->nRefs++ > 0 ) + continue; + aArea += Fpga_CutRefSwitch( pMan, pNodeChild, pNodeChild->pCutBest, fFanouts ); + } + return aArea; +} + +/**function************************************************************* + + synopsis [Dereferences the cut.] + + description [This procedure is similar to the procedure NodeRecusiveDeref.] + + sideeffects [] + + seealso [] + +***********************************************************************/ +float Fpga_CutDerefSwitch( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts ) +{ + Fpga_Node_t * pNodeChild; + float aArea; + int i; + if ( pCut->nLeaves == 1 ) + return 0; + // start the area of this cut + aArea = Fpga_CutGetSwitching( pCut ); + // go through the children + for ( i = 0; i < pCut->nLeaves; i++ ) + { + pNodeChild = pCut->ppLeaves[i]; + assert( pNodeChild->nRefs > 0 ); + if ( --pNodeChild->nRefs > 0 ) + continue; + aArea += Fpga_CutDerefSwitch( pMan, pNodeChild, pNodeChild->pCutBest, fFanouts ); + } + return aArea; +} + +/**function************************************************************* + + synopsis [Computes the exact area associated with the cut.] + + description [] + + sideeffects [] + + seealso [] + +***********************************************************************/ +float Fpga_CutGetSwitching( Fpga_Cut_t * pCut ) +{ + float Result; + int i; + Result = 0.0; + for ( i = 0; i < pCut->nLeaves; i++ ) + Result += pCut->ppLeaves[i]->Switching; + return Result; +} + +/**Function************************************************************* + + Synopsis [Computes the array of mapping.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Fpga_MappingGetSwitching( Fpga_Man_t * pMan, Fpga_NodeVec_t * vMapping ) +{ + Fpga_Node_t * pNode; + float Switch; + int i; + Switch = 0.0; + for ( i = 0; i < vMapping->nSize; i++ ) + { + pNode = vMapping->pArray[i]; + if ( !Fpga_NodeIsAnd(pNode) ) + continue; + // at least one phase has the best cut assigned + assert( pNode->pCutBest != NULL ); + // at least one phase is used in the mapping + assert( pNode->nRefs > 0 ); + // compute the array due to the supergate + Switch += pNode->Switching; + } + // add buffer for each CO driven by a CI + for ( i = 0; i < pMan->nOutputs; i++ ) + if ( Fpga_NodeIsVar(pMan->pOutputs[i]) && !Fpga_IsComplement(pMan->pOutputs[i]) ) + Switch += pMan->pOutputs[i]->Switching; + return Switch; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/fpga/fpgaUtils.c b/src/map/fpga/fpgaUtils.c index 89ef13dc..3ea1f2f1 100644 --- a/src/map/fpga/fpgaUtils.c +++ b/src/map/fpga/fpgaUtils.c @@ -779,43 +779,6 @@ Fpga_NodeVec_t * Fpga_MappingLevelize( Fpga_Man_t * pMan, Fpga_NodeVec_t * vNode } return vLevels; } -/**Function************************************************************* - - Synopsis [Prints the switching activity changes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float Fpga_MappingPrintSwitching( Fpga_Man_t * p ) -{ - Fpga_Node_t * pNode; - float SwitchTotal = 0.0; - int nNodes = 0; - int i; - for ( i = 0; i < p->vNodesAll->nSize; i++ ) - { - // skip primary inputs - pNode = p->vNodesAll->pArray[i]; -// if ( !Fpga_NodeIsAnd( pNode ) ) -// continue; - // skip a secondary node - if ( pNode->pRepr ) - continue; - // count the switching nodes - if ( pNode->nRefs > 0 ) - { - SwitchTotal += pNode->SwitchProb; - nNodes++; - } - } - if ( p->fVerbose ) - printf( "Total switching = %10.2f. Average switching = %6.4f.\n", SwitchTotal, SwitchTotal/nNodes ); - return SwitchTotal; -} /**Function************************************************************* diff --git a/src/map/fpga/module.make b/src/map/fpga/module.make index 409e4b54..cc3a6573 100644 --- a/src/map/fpga/module.make +++ b/src/map/fpga/module.make @@ -6,6 +6,7 @@ SRC += src/map/fpga/fpga.c \ src/map/fpga/fpgaFanout.c \ src/map/fpga/fpgaLib.c \ src/map/fpga/fpgaMatch.c \ + src/map/fpga/fpgaSwitch.c \ src/map/fpga/fpgaTime.c \ src/map/fpga/fpgaTruth.c \ src/map/fpga/fpgaUtils.c \ -- cgit v1.2.3