diff options
Diffstat (limited to 'src/map/fpga/fpgaMatch.c')
| -rw-r--r-- | src/map/fpga/fpgaMatch.c | 729 |
1 files changed, 729 insertions, 0 deletions
diff --git a/src/map/fpga/fpgaMatch.c b/src/map/fpga/fpgaMatch.c new file mode 100644 index 00000000..8668ce4b --- /dev/null +++ b/src/map/fpga/fpgaMatch.c @@ -0,0 +1,729 @@ +/**CFile**************************************************************** + + FileName [fpgaMatch.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Technology mapping for variable-size-LUT FPGAs.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 2.0. Started - August 18, 2004.] + + Revision [$Id: fpgaMatch.c,v 1.7 2004/09/30 21:18:10 satrajit Exp $] + +***********************************************************************/ + +#include "fpgaInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static int Fpga_MatchNode( Fpga_Man_t * p, Fpga_Node_t * pNode, int fDelayOriented ); +static int Fpga_MatchNodeArea( Fpga_Man_t * p, Fpga_Node_t * pNode ); +static int Fpga_MatchNodeSwitch( Fpga_Man_t * p, Fpga_Node_t * pNode ); + +static Fpga_Cut_t * Fpga_MappingAreaWithoutNode( Fpga_Man_t * p, Fpga_Node_t * pFanout, Fpga_Node_t * pNodeNo ); +static int Fpga_MappingMatchesAreaArray( Fpga_Man_t * p, Fpga_NodeVec_t * vNodes ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Finds the best delay assignment of LUTs.] + + Description [This procedure iterates through all the nodes + of the object graph reachable from the POs and assigns the best + match to each of them. If the flag fDelayOriented is set to 1, it + tries to minimize the arrival time and uses the area flow as a + tie-breaker. If the flag is set to 0, it considers all the cuts, + whose arrival times matches the required time at the node, and + minimizes the area flow using the arrival time as a tie-breaker. + + Before this procedure is called, the required times should be set + and the fanout counts should be computed. In the first iteration, + the required times are set to very large number (by NodeCreate) + and the fanout counts are set to the number of fanouts in the AIG. + In the following iterations, the required times are set by the + backward traversal, while the fanouts are estimated approximately. + + If the arrival times of the PI nodes are given, they should be + assigned to the PIs after the cuts are computed and before this + procedure is called for the first time.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_MappingMatches( Fpga_Man_t * p, int fDelayOriented ) +{ + ProgressBar * pProgress; + Fpga_Node_t * pNode; + int i, nNodes; + + // assign the arrival times of the PIs + for ( i = 0; i < p->nInputs; i++ ) + p->pInputs[i]->pCutBest->tArrival = p->pInputArrivals[i]; + + // match LUTs with nodes in the topological order + nNodes = p->vAnds->nSize; + pProgress = Extra_ProgressBarStart( stdout, nNodes ); + for ( i = 0; i < nNodes; i++ ) + { + pNode = p->vAnds->pArray[i]; + if ( !Fpga_NodeIsAnd( pNode ) ) + continue; + // skip a secondary node + if ( pNode->pRepr ) + continue; + // match the node + Fpga_MatchNode( p, pNode, fDelayOriented ); + Extra_ProgressBarUpdate( pProgress, i, "Matches ..." ); + } + Extra_ProgressBarStop( pProgress ); + return 1; +} + +/**Function************************************************************* + + Synopsis [Computes the best matching for one node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_MatchNode( Fpga_Man_t * p, Fpga_Node_t * pNode, int fDelayOriented ) +{ + Fpga_Cut_t * pCut, * pCutBestOld; + int clk; + // make sure that at least one cut other than the trivial is present + if ( pNode->pCuts->pNext == NULL ) + { + printf( "\nError: A node in the mapping graph does not have feasible cuts.\n" ); + return 0; + } + + // estimate the fanouts of the node + if ( pNode->aEstFanouts < 0 ) + pNode->aEstFanouts = (float)pNode->nRefs; + else + pNode->aEstFanouts = (float)((2.0 * pNode->aEstFanouts + pNode->nRefs) / 3.0); +// pNode->aEstFanouts = (float)pNode->nRefs; + + pCutBestOld = pNode->pCutBest; + pNode->pCutBest = NULL; + for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext ) + { + // compute the arrival time of the cut and its area flow +clk = clock(); + Fpga_CutGetParameters( p, pCut ); +//p->time2 += clock() - clk; + // drop the cut if it does not meet the required times + if ( pCut->tArrival > pNode->tRequired ) + continue; + // if no cut is assigned, use the current one + if ( pNode->pCutBest == NULL ) + { + pNode->pCutBest = pCut; + continue; + } + // choose the best cut using one of the two criteria: + // (1) delay oriented mapping (first traversal), delay first, area-flow as a tie-breaker + // (2) area recovery (subsequent traversals), area-flow first, delay as a tie-breaker + if ( (fDelayOriented && + (pNode->pCutBest->tArrival > pCut->tArrival || + pNode->pCutBest->tArrival == pCut->tArrival && pNode->pCutBest->aFlow > pCut->aFlow)) || + (!fDelayOriented && + (pNode->pCutBest->aFlow > pCut->aFlow || + pNode->pCutBest->aFlow == pCut->aFlow && pNode->pCutBest->tArrival > pCut->tArrival)) ) + { + pNode->pCutBest = pCut; + } + } + + // make sure the match is found + if ( pNode->pCutBest == NULL ) + { + if ( pCutBestOld == NULL ) + { +// printf( "\nError: Could not match a node in the object graph.\n" ); + return 0; + } + pNode->pCutBest = pCutBestOld; + } + return 1; +} + + + + + +/**Function************************************************************* + + Synopsis [Finds the best area assignment of LUTs.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_MappingMatchesArea( Fpga_Man_t * p ) +{ + ProgressBar * pProgress; + Fpga_Node_t * pNode; + int i, nNodes; + + // assign the arrival times of the PIs + for ( i = 0; i < p->nInputs; i++ ) + p->pInputs[i]->pCutBest->tArrival = p->pInputArrivals[i]; + + // match LUTs with nodes in the topological order + nNodes = p->vAnds->nSize; + pProgress = Extra_ProgressBarStart( stdout, nNodes ); + for ( i = 0; i < nNodes; i++ ) + { + pNode = p->vAnds->pArray[i]; + if ( !Fpga_NodeIsAnd( pNode ) ) + continue; + // skip a secondary node + if ( pNode->pRepr ) + continue; + // match the node + Fpga_MatchNodeArea( p, pNode ); + Extra_ProgressBarUpdate( pProgress, i, "Matches ..." ); + } + Extra_ProgressBarStop( pProgress ); + return 1; +} + +/**Function************************************************************* + + Synopsis [Finds the best area assignment of LUTs.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_MappingMatchesAreaArray( Fpga_Man_t * p, Fpga_NodeVec_t * vNodes ) +{ + Fpga_Node_t * pNode; + int i; + + // match LUTs with nodes in the topological order + for ( i = 0; i < vNodes->nSize; i++ ) + { + pNode = vNodes->pArray[i]; + if ( !Fpga_NodeIsAnd( pNode ) ) + continue; + // skip a secondary node + if ( pNode->pRepr ) + continue; + // match the node + if ( !Fpga_MatchNodeArea( p, pNode ) ) + return 0; + } + return 1; +} + +/**Function************************************************************* + + Synopsis [Computes the best matching for one node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_MatchNodeArea( Fpga_Man_t * p, Fpga_Node_t * pNode ) +{ + Fpga_Cut_t * pCut, * pCutBestOld; + float aAreaCutBest; + int clk; + // make sure that at least one cut other than the trivial is present + if ( pNode->pCuts->pNext == NULL ) + { + printf( "\nError: A node in the mapping graph does not have feasible cuts.\n" ); + return 0; + } + + // remember the old cut + pCutBestOld = pNode->pCutBest; + // deref the old cut + if ( pNode->nRefs ) + aAreaCutBest = Fpga_CutDeref( p, pNode, pNode->pCutBest, 0 ); + + // search for a better cut + pNode->pCutBest = NULL; + for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext ) + { + // compute the arrival time of the cut and its area flow +clk = clock(); + pCut->tArrival = Fpga_TimeCutComputeArrival( p, pCut ); +//p->time2 += clock() - clk; + // drop the cut if it does not meet the required times + if ( pCut->tArrival > pNode->tRequired ) + continue; + // get the area of this cut + pCut->aFlow = Fpga_CutGetAreaDerefed( p, pCut ); + // if no cut is assigned, use the current one + if ( pNode->pCutBest == NULL ) + { + pNode->pCutBest = pCut; + continue; + } + // choose the best cut as follows: exact area first, delay as a tie-breaker + if ( pNode->pCutBest->aFlow > pCut->aFlow || + pNode->pCutBest->aFlow == pCut->aFlow && pNode->pCutBest->tArrival > pCut->tArrival ) + { + pNode->pCutBest = pCut; + } + } + + // make sure the match is found + if ( pNode->pCutBest == NULL ) + { + pNode->pCutBest = pCutBestOld; + // insert the new cut + if ( pNode->nRefs ) + pNode->pCutBest->aFlow = Fpga_CutRef( p, pNode, pNode->pCutBest, 0 ); +// printf( "\nError: Could not match a node in the object graph.\n" ); + return 0; + } + + // insert the new cut + // make sure the area selected is not worse then the original area + if ( pNode->nRefs ) + { + pNode->pCutBest->aFlow = Fpga_CutRef( p, pNode, pNode->pCutBest, 0 ); + assert( pNode->pCutBest->aFlow <= aAreaCutBest ); +// assert( pNode->tRequired < FPGA_FLOAT_LARGE ); + } + return 1; +} + + + + +/**Function************************************************************* + + Synopsis [Finds the best area assignment of LUTs.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_MappingMatchesSwitch( Fpga_Man_t * p ) +{ + ProgressBar * pProgress; + Fpga_Node_t * pNode; + int i, nNodes; + + // assign the arrival times of the PIs + for ( i = 0; i < p->nInputs; i++ ) + p->pInputs[i]->pCutBest->tArrival = p->pInputArrivals[i]; + + // match LUTs with nodes in the topological order + nNodes = p->vAnds->nSize; + pProgress = Extra_ProgressBarStart( stdout, nNodes ); + for ( i = 0; i < nNodes; i++ ) + { + pNode = p->vAnds->pArray[i]; + if ( !Fpga_NodeIsAnd( pNode ) ) + continue; + // skip a secondary node + if ( pNode->pRepr ) + continue; + // match the node + Fpga_MatchNodeSwitch( p, pNode ); + Extra_ProgressBarUpdate( pProgress, i, "Matches ..." ); + } + Extra_ProgressBarStop( pProgress ); + return 1; +} + +/**Function************************************************************* + + Synopsis [Computes the best matching for one node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_MatchNodeSwitch( Fpga_Man_t * p, Fpga_Node_t * pNode ) +{ + Fpga_Cut_t * pCut, * pCutBestOld; + float aAreaCutBest; + int clk; + // make sure that at least one cut other than the trivial is present + if ( pNode->pCuts->pNext == NULL ) + { + printf( "\nError: A node in the mapping graph does not have feasible cuts.\n" ); + return 0; + } + + // remember the old cut + pCutBestOld = pNode->pCutBest; + // deref the old cut + if ( pNode->nRefs ) + aAreaCutBest = Fpga_CutDerefSwitch( p, pNode, pNode->pCutBest, 0 ); + + // search for a better cut + pNode->pCutBest = NULL; + for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext ) + { + // compute the arrival time of the cut and its area flow +clk = clock(); + pCut->tArrival = Fpga_TimeCutComputeArrival( p, pCut ); +//p->time2 += clock() - clk; + // drop the cut if it does not meet the required times + if ( pCut->tArrival > pNode->tRequired ) + continue; + // get the area of this cut + pCut->aFlow = Fpga_CutGetSwitchDerefed( p, pNode, pCut ); + // if no cut is assigned, use the current one + if ( pNode->pCutBest == NULL ) + { + pNode->pCutBest = pCut; + continue; + } + // choose the best cut as follows: exact area first, delay as a tie-breaker + if ( pNode->pCutBest->aFlow > pCut->aFlow || + pNode->pCutBest->aFlow == pCut->aFlow && pNode->pCutBest->tArrival > pCut->tArrival ) + { + pNode->pCutBest = pCut; + } + } + + // make sure the match is found + if ( pNode->pCutBest == NULL ) + { + pNode->pCutBest = pCutBestOld; + // insert the new cut + if ( pNode->nRefs ) + pNode->pCutBest->aFlow = Fpga_CutRefSwitch( p, pNode, pNode->pCutBest, 0 ); +// printf( "\nError: Could not match a node in the object graph.\n" ); + return 0; + } + + // insert the new cut + // make sure the area selected is not worse then the original area + if ( pNode->nRefs ) + { + pNode->pCutBest->aFlow = Fpga_CutRefSwitch( p, pNode, pNode->pCutBest, 0 ); + assert( pNode->pCutBest->aFlow <= aAreaCutBest ); +// assert( pNode->tRequired < FPGA_FLOAT_LARGE ); + } + return 1; +} + + +#if 0 +/**function************************************************************* + + synopsis [References the cut.] + + description [This procedure is similar to the procedure NodeReclaim.] + + sideeffects [] + + seealso [] + +***********************************************************************/ +void Fpga_Experiment( Fpga_Man_t * p ) +{ + int Counter[10] = {0}; + Fpga_Node_t * pNode; + int i; + + for ( i = 0; i < p->nOutputs; i++ ) + { + pNode = Fpga_Regular(p->pOutputs[i]); + pNode->vFanouts = NULL; + } + + for ( i = 0; i < p->vAnds->nSize; i++ ) + { + pNode = p->vAnds->pArray[i]; + if ( !Fpga_NodeIsAnd( pNode ) ) + continue; + if ( pNode->vFanouts == NULL ) + continue; + if ( pNode->vFanouts->nSize >= 10 ) + continue; + Counter[pNode->vFanouts->nSize]++; + } + + printf( "Fanout stats: " ); + for ( i = 0; i < 10; i++ ) + printf( " %d=%d", i, Counter[i] ); + printf( "\n" ); + printf( "Area before = %4.2f.\n", Fpga_MappingArea(p) ); + + for ( i = 0; i < p->vAnds->nSize; i++ ) + { + Fpga_NodeVec_t * vNodesTfo; + float AreaBefore; + + pNode = p->vAnds->pArray[i]; + if ( !Fpga_NodeIsAnd( pNode ) ) + continue; + if ( pNode->vFanouts == NULL ) + continue; + if ( pNode->vFanouts->nSize != 1 && pNode->vFanouts->nSize != 2 && pNode->vFanouts->nSize != 3 ) + continue; + +// assert( pNode->nRefs > 0 ); + if ( pNode->nRefs == 0 ) + continue; + + AreaBefore = pNode->pCutBest->aFlow; + pNode->pCutBest->aFlow = FPGA_FLOAT_LARGE; + + Fpga_TimeComputeRequiredGlobal( p ); + + vNodesTfo = Fpga_CollectNodeTfo( p, pNode ); + if ( Fpga_MappingMatchesAreaArray( p, vNodesTfo ) == 0 ) + printf( "attempt failed\n" ); + else + printf( "attempt succeeded\n" ); + Fpga_NodeVecFree( vNodesTfo ); + + pNode->pCutBest->aFlow = AreaBefore; +// break; + } + printf( "Area after = %4.2f.\n", Fpga_MappingArea(p) ); +// printf( "AREA GAIN = %4.2f (%.2f %%)\n", GainTotal, 100.0 * GainTotal / Fpga_MappingArea(p) ); +} + + + +/**function************************************************************* + + synopsis [References the cut.] + + description [This procedure is similar to the procedure NodeReclaim.] + + sideeffects [] + + seealso [] + +***********************************************************************/ +void Fpga_Experiment2( Fpga_Man_t * p ) +{ + int Counter[10] = {0}; + Fpga_Cut_t * ppCutsNew[10]; + Fpga_Cut_t * ppCutsOld[10]; + Fpga_Node_t * pFanout, * pNode; + float Gain, Loss, GainTotal, Area1, Area2; + int i, k; + + for ( i = 0; i < p->nOutputs; i++ ) + { + pNode = Fpga_Regular(p->pOutputs[i]); + pNode->vFanouts = NULL; + } + + for ( i = 0; i < p->vAnds->nSize; i++ ) + { + pNode = p->vAnds->pArray[i]; + if ( !Fpga_NodeIsAnd( pNode ) ) + continue; + if ( pNode->vFanouts == NULL ) + continue; + if ( pNode->vFanouts->nSize >= 10 ) + continue; + Counter[pNode->vFanouts->nSize]++; + } + + printf( "Fanout stats: " ); + for ( i = 0; i < 10; i++ ) + printf( " %d=%d", i, Counter[i] ); + printf( "\n" ); + printf( "Area before = %4.2f.\n", Fpga_MappingArea(p) ); + + GainTotal = 0; + for ( i = 0; i < p->vAnds->nSize; i++ ) + { + pNode = p->vAnds->pArray[i]; + if ( !Fpga_NodeIsAnd( pNode ) ) + continue; + if ( pNode->vFanouts == NULL ) + continue; + if ( pNode->vFanouts->nSize != 2 )//&& pNode->vFanouts->nSize != 2 && pNode->vFanouts->nSize != 3 ) + continue; + + assert( pNode->nRefs > 0 ); + + // for all fanouts, find the best cut without this node + for ( k = 0; k < pNode->vFanouts->nSize; k++ ) + { + pFanout = pNode->vFanouts->pArray[k]; + ppCutsOld[k] = pFanout->pCutBest; + ppCutsNew[k] = Fpga_MappingAreaWithoutNode( p, pFanout, pNode ); + if ( ppCutsNew[k] == NULL ) + break; + } + if ( k != pNode->vFanouts->nSize ) + { + printf( "Node %4d: Skipped.\n", pNode->Num ); + continue; + } + + + // compute the area after replacing all the cuts + Gain = 0; + for ( k = 0; k < pNode->vFanouts->nSize; k++ ) + { + pFanout = pNode->vFanouts->pArray[k]; + // deref old cut + Area1 = Fpga_MatchAreaDeref( p, ppCutsOld[k] ); + // assign new cut + pFanout->pCutBest = ppCutsNew[k]; + // ref new cut + Area2 = Fpga_MatchAreaRef( p, ppCutsNew[k] ); + // compute the gain + Gain += Area1 - Area2; + } + + printf( "%d ", pNode->nRefs ); + + // undo the whole thing + Loss = 0; + for ( k = 0; k < pNode->vFanouts->nSize; k++ ) + { + pFanout = pNode->vFanouts->pArray[k]; + // deref old cut + Area1 = Fpga_MatchAreaDeref( p, ppCutsNew[k] ); + // assign new cut + pFanout->pCutBest = ppCutsOld[k]; + // ref new cut + Area2 = Fpga_MatchAreaRef( p, ppCutsOld[k] ); + // compute the gain + Loss += Area2 - Area1; + } + assert( Gain == Loss ); + + + printf( "Node %4d: Fanouts = %d. Cut area = %4.2f. Gain = %4.2f.\n", + pNode->Num, pNode->nRefs, pNode->pCutBest->aFlow, Gain ); + + if ( Gain > 0 ) + GainTotal += Gain; + } + printf( "Area after = %4.2f.\n", Fpga_MappingArea(p) ); + printf( "AREA GAIN = %4.2f (%.2f %%)\n", GainTotal, 100.0 * GainTotal / Fpga_MappingArea(p) ); +} + + +/**function************************************************************* + + synopsis [Computes the loss of area when node is not allowed.] + + description [Returning FPGA_FLOAT_LARGE means it does not exist.] + + sideeffects [] + + seealso [] + +***********************************************************************/ +Fpga_Cut_t * Fpga_MappingAreaWithoutNode( Fpga_Man_t * p, Fpga_Node_t * pNode, Fpga_Node_t * pNodeNo ) +{ + Fpga_Cut_t * pCut, * pCutBestOld, * pCutRes; + float aAreaCutBest; + int i, clk; + // make sure that at least one cut other than the trivial is present + if ( pNode->pCuts->pNext == NULL ) + { + printf( "\nError: A node in the mapping graph does not have feasible cuts.\n" ); + return 0; + } + + assert( pNode->nRefs > 0 ); + + // remember the old cut + pCutBestOld = pNode->pCutBest; + // deref the old cut + aAreaCutBest = Fpga_MatchAreaDeref( p, pNode->pCutBest ); + + // search for a better cut + pNode->pCutBest = NULL; + for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext ) + { + // compute the arrival time of the cut and its area flow +clk = clock(); + Fpga_MatchCutGetArrTime( p, pCut ); +//p->time2 += clock() - clk; + // drop the cut if it does not meet the required times + if ( pCut->tArrival > pNode->tRequired ) + continue; + + // skip the cut if it contains the no-node + for ( i = 0; i < pCut->nLeaves; i++ ) + if ( pCut->ppLeaves[i] == pNodeNo ) + break; + if ( i != pCut->nLeaves ) + continue; + + // get the area of this cut + pCut->aFlow = Fpga_MatchAreaCount( p, pCut ); + // if no cut is assigned, use the current one + if ( pNode->pCutBest == NULL ) + { + pNode->pCutBest = pCut; + continue; + } + // choose the best cut as follows: exact area first, delay as a tie-breaker + if ( pNode->pCutBest->aFlow > pCut->aFlow || + pNode->pCutBest->aFlow == pCut->aFlow && pNode->pCutBest->tArrival > pCut->tArrival ) + { + pNode->pCutBest = pCut; + } + } + + // make sure the match is found + if ( pNode->pCutBest == NULL ) + { + pNode->pCutBest = pCutBestOld; + // insert the new cut + pNode->pCutBest->aFlow = Fpga_MatchAreaRef( p, pNode->pCutBest ); + return NULL; + } + + pCutRes = pNode->pCutBest; + pNode->pCutBest = pCutBestOld; + + // insert the new cut + pNode->pCutBest->aFlow = Fpga_MatchAreaRef( p, pNode->pCutBest ); + + // make sure the area selected is not worse then the original area + assert( pNode->pCutBest->aFlow == aAreaCutBest ); + assert( pNode->tRequired < FPGA_FLOAT_LARGE ); + return pCutRes; +} + +#endif +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// |