src/map/fpga/fpgaMatch.c File Reference

#include "fpgaInt.h"
Include dependency graph for fpgaMatch.c:

Go to the source code of this file.

Functions

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)
int Fpga_MappingMatches (Fpga_Man_t *p, int fDelayOriented)
int Fpga_MappingMatchesArea (Fpga_Man_t *p)
int Fpga_MappingMatchesSwitch (Fpga_Man_t *p)
float Fpga_FindBestNode (Fpga_Man_t *p, Fpga_NodeVec_t *vNodes, Fpga_Node_t **ppNode, Fpga_Cut_t **ppCutBest)

Function Documentation

float Fpga_FindBestNode ( Fpga_Man_t *  p,
Fpga_NodeVec_t *  vNodes,
Fpga_Node_t **  ppNode,
Fpga_Cut_t **  ppCutBest 
)

function*************************************************************

synopsis [Performs area minimization using a heuristic algorithm.]

description []

sideeffects []

seealso []

Definition at line 752 of file fpgaMatch.c.

00753 {
00754     Fpga_Node_t * pNode;
00755     Fpga_Cut_t * pCut;
00756     float Gain, CutArea1, CutArea2, CutArea3;
00757     int i;
00758 
00759     Gain = 0;
00760     for ( i = 0; i < vNodes->nSize; i++ )
00761     {
00762         pNode = vNodes->pArray[i];
00763         // deref the current cut
00764         CutArea1 = Fpga_CutDeref( p, pNode, pNode->pCutBest, 0 );
00765 
00766         // ref all the cuts
00767         for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext )
00768         {
00769             if ( pCut == pNode->pCutBest )
00770                 continue;
00771             if ( pCut->tArrival > pNode->tRequired )
00772                 continue;
00773 
00774             CutArea2 = Fpga_CutGetAreaDerefed( p, pCut );
00775             if ( Gain < CutArea1 - CutArea2 )
00776             {
00777                 *ppNode = pNode;
00778                 *ppCutBest = pCut;
00779                 Gain = CutArea1 - CutArea2;
00780             }
00781         }
00782         // ref the old cut
00783         CutArea3 = Fpga_CutRef( p, pNode, pNode->pCutBest, 0 );
00784         assert( CutArea1 == CutArea3 );
00785     }
00786     if ( Gain == 0 )
00787         printf( "Returning no gain.\n" );
00788 
00789     return Gain;
00790 }

static Fpga_Cut_t* Fpga_MappingAreaWithoutNode ( Fpga_Man_t *  p,
Fpga_Node_t *  pFanout,
Fpga_Node_t *  pNodeNo 
) [static]
int Fpga_MappingMatches ( Fpga_Man_t *  p,
int  fDelayOriented 
)

FUNCTION DEFINITIONS ///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 []

Definition at line 64 of file fpgaMatch.c.

00065 {
00066     ProgressBar * pProgress;
00067     Fpga_Node_t * pNode;
00068     int i, nNodes;
00069     
00070     // assign the arrival times of the PIs
00071     for ( i = 0; i < p->nInputs; i++ )
00072         p->pInputs[i]->pCutBest->tArrival = p->pInputArrivals[i];
00073 
00074     // match LUTs with nodes in the topological order
00075     nNodes = p->vAnds->nSize;
00076     pProgress = Extra_ProgressBarStart( stdout, nNodes );
00077     for ( i = 0; i < nNodes; i++ )
00078     {
00079         pNode = p->vAnds->pArray[i];
00080         if ( !Fpga_NodeIsAnd( pNode ) )
00081             continue;
00082         // skip a secondary node
00083         if ( pNode->pRepr )
00084             continue;
00085         // match the node
00086         Fpga_MatchNode( p, pNode, fDelayOriented );
00087         Extra_ProgressBarUpdate( pProgress, i, "Matches ..." );
00088     }
00089     Extra_ProgressBarStop( pProgress );
00090 /*
00091     if ( !fDelayOriented )
00092     {
00093         float Area = 0.0;
00094         for ( i = 0; i < p->nOutputs; i++ )
00095         {
00096             printf( "%5.2f ", Fpga_Regular(p->pOutputs[i])->pCutBest->aFlow );
00097             Area += Fpga_Regular(p->pOutputs[i])->pCutBest->aFlow;
00098         }
00099         printf( "\nTotal = %5.2f\n", Area );
00100     }
00101 */
00102     return 1;
00103 }

int Fpga_MappingMatchesArea ( Fpga_Man_t *  p  ) 

Function*************************************************************

Synopsis [Finds the best area assignment of LUTs.]

Description []

SideEffects []

SeeAlso []

Definition at line 193 of file fpgaMatch.c.

00194 {
00195     ProgressBar * pProgress;
00196     Fpga_Node_t * pNode;
00197     int i, nNodes;
00198     
00199     // assign the arrival times of the PIs
00200     for ( i = 0; i < p->nInputs; i++ )
00201         p->pInputs[i]->pCutBest->tArrival = p->pInputArrivals[i];
00202 
00203     // match LUTs with nodes in the topological order
00204     nNodes = p->vAnds->nSize;
00205     pProgress = Extra_ProgressBarStart( stdout, nNodes );
00206     for ( i = 0; i < nNodes; i++ )
00207     {
00208         pNode = p->vAnds->pArray[i];
00209         if ( !Fpga_NodeIsAnd( pNode ) )
00210             continue;
00211         // skip a secondary node
00212         if ( pNode->pRepr )
00213             continue;
00214         // match the node
00215         Fpga_MatchNodeArea( p, pNode );
00216         Extra_ProgressBarUpdate( pProgress, i, "Matches ..." );
00217     }
00218     Extra_ProgressBarStop( pProgress );
00219     return 1;
00220 }

int Fpga_MappingMatchesAreaArray ( Fpga_Man_t *  p,
Fpga_NodeVec_t *  vNodes 
) [static]

Function*************************************************************

Synopsis [Finds the best area assignment of LUTs.]

Description []

SideEffects []

SeeAlso []

Definition at line 233 of file fpgaMatch.c.

00234 {
00235     Fpga_Node_t * pNode;
00236     int i;
00237 
00238     // match LUTs with nodes in the topological order
00239     for ( i = 0; i < vNodes->nSize; i++ )
00240     {
00241         pNode = vNodes->pArray[i];
00242         if ( !Fpga_NodeIsAnd( pNode ) )
00243             continue;
00244         // skip a secondary node
00245         if ( pNode->pRepr )
00246             continue;
00247         // match the node
00248         if ( !Fpga_MatchNodeArea( p, pNode ) )
00249             return 0;
00250     }
00251     return 1;
00252 }

int Fpga_MappingMatchesSwitch ( Fpga_Man_t *  p  ) 

Function*************************************************************

Synopsis [Finds the best area assignment of LUTs.]

Description []

SideEffects []

SeeAlso []

Definition at line 346 of file fpgaMatch.c.

00347 {
00348     ProgressBar * pProgress;
00349     Fpga_Node_t * pNode;
00350     int i, nNodes;
00351     
00352     // assign the arrival times of the PIs
00353     for ( i = 0; i < p->nInputs; i++ )
00354         p->pInputs[i]->pCutBest->tArrival = p->pInputArrivals[i];
00355 
00356     // match LUTs with nodes in the topological order
00357     nNodes = p->vAnds->nSize;
00358     pProgress = Extra_ProgressBarStart( stdout, nNodes );
00359     for ( i = 0; i < nNodes; i++ )
00360     {
00361         pNode = p->vAnds->pArray[i];
00362         if ( !Fpga_NodeIsAnd( pNode ) )
00363             continue;
00364         // skip a secondary node
00365         if ( pNode->pRepr )
00366             continue;
00367         // match the node
00368         Fpga_MatchNodeSwitch( p, pNode );
00369         Extra_ProgressBarUpdate( pProgress, i, "Matches ..." );
00370     }
00371     Extra_ProgressBarStop( pProgress );
00372     return 1;
00373 }

int Fpga_MatchNode ( Fpga_Man_t *  p,
Fpga_Node_t *  pNode,
int  fDelayOriented 
) [static]

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

] DECLARATIONS ///

Function*************************************************************

Synopsis [Computes the best matching for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 116 of file fpgaMatch.c.

00117 {
00118     Fpga_Cut_t * pCut, * pCutBestOld;
00119     int clk;
00120     // make sure that at least one cut other than the trivial is present
00121     if ( pNode->pCuts->pNext == NULL )
00122     {
00123         printf( "\nError: A node in the mapping graph does not have feasible cuts.\n" );
00124         return 0;
00125     }
00126 
00127     // estimate the fanouts of the node
00128     if ( pNode->aEstFanouts < 0 )
00129         pNode->aEstFanouts = (float)pNode->nRefs;
00130     else
00131         pNode->aEstFanouts = (float)((2.0 * pNode->aEstFanouts + pNode->nRefs) / 3.0);
00132 //        pNode->aEstFanouts = (float)pNode->nRefs;
00133 
00134     pCutBestOld = pNode->pCutBest;
00135     pNode->pCutBest = NULL;
00136     for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext )
00137     {
00138         // compute the arrival time of the cut and its area flow
00139 clk = clock();
00140         Fpga_CutGetParameters( p, pCut );
00141 //p->time2 += clock() - clk;
00142         // drop the cut if it does not meet the required times
00143         if ( Fpga_FloatMoreThan(p, pCut->tArrival, pNode->tRequired) )
00144             continue;
00145         // if no cut is assigned, use the current one
00146         if ( pNode->pCutBest == NULL )
00147         {
00148             pNode->pCutBest = pCut;
00149             continue;
00150         }
00151         // choose the best cut using one of the two criteria:
00152         // (1) delay oriented mapping (first traversal), delay first, area-flow as a tie-breaker
00153         // (2) area recovery (subsequent traversals), area-flow first, delay as a tie-breaker
00154         if ( (fDelayOriented && 
00155                (Fpga_FloatMoreThan(p, pNode->pCutBest->tArrival, pCut->tArrival) || 
00156                 Fpga_FloatEqual(p, pNode->pCutBest->tArrival, pCut->tArrival) && Fpga_FloatMoreThan(p, pNode->pCutBest->aFlow, pCut->aFlow) )) ||
00157              (!fDelayOriented && 
00158                (Fpga_FloatMoreThan(p, pNode->pCutBest->aFlow, pCut->aFlow) || 
00159                 Fpga_FloatEqual(p, pNode->pCutBest->aFlow, pCut->aFlow) && Fpga_FloatMoreThan(p, pNode->pCutBest->tArrival, pCut->tArrival)))  )
00160         {
00161             pNode->pCutBest = pCut;
00162         }
00163     }
00164 
00165     // make sure the match is found
00166     if ( pNode->pCutBest == NULL )
00167     {
00168         if ( pCutBestOld == NULL )
00169         {
00170 //            printf( "\nError: Could not match a node in the object graph.\n" );
00171             return 0;
00172         }
00173         pNode->pCutBest = pCutBestOld;
00174     }
00175     return 1;
00176 }

int Fpga_MatchNodeArea ( Fpga_Man_t *  p,
Fpga_Node_t *  pNode 
) [static]

Function*************************************************************

Synopsis [Computes the best matching for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 265 of file fpgaMatch.c.

00266 {
00267     Fpga_Cut_t * pCut, * pCutBestOld;
00268     float aAreaCutBest;
00269     int clk;
00270     // make sure that at least one cut other than the trivial is present
00271     if ( pNode->pCuts->pNext == NULL )
00272     {
00273         printf( "\nError: A node in the mapping graph does not have feasible cuts.\n" );
00274         return 0;
00275     }
00276 
00277     // remember the old cut
00278     pCutBestOld = pNode->pCutBest;
00279     // deref the old cut
00280     if ( pNode->nRefs ) 
00281         aAreaCutBest = Fpga_CutDeref( p, pNode, pNode->pCutBest, 0 );
00282 
00283     // search for a better cut
00284     pNode->pCutBest = NULL;
00285     for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext )
00286     {
00287         // compute the arrival time of the cut and its area flow
00288 clk = clock();
00289         pCut->tArrival = Fpga_TimeCutComputeArrival( p, pCut );
00290 //p->time2 += clock() - clk;
00291         // drop the cut if it does not meet the required times
00292         if ( Fpga_FloatMoreThan( p, pCut->tArrival, pNode->tRequired ) )
00293             continue;
00294         // get the area of this cut
00295         pCut->aFlow = Fpga_CutGetAreaDerefed( p, pCut );
00296         // if no cut is assigned, use the current one
00297         if ( pNode->pCutBest == NULL )
00298         {
00299             pNode->pCutBest = pCut;
00300             continue;
00301         }
00302         // choose the best cut as follows: exact area first, delay as a tie-breaker
00303         if ( Fpga_FloatMoreThan(p, pNode->pCutBest->aFlow, pCut->aFlow) || 
00304              Fpga_FloatEqual(p, pNode->pCutBest->aFlow, pCut->aFlow) && Fpga_FloatMoreThan(p, pNode->pCutBest->tArrival, pCut->tArrival) )
00305         {
00306             pNode->pCutBest = pCut;
00307         }
00308     }
00309 
00310     // make sure the match is found
00311     if ( pNode->pCutBest == NULL )
00312     {
00313         pNode->pCutBest = pCutBestOld; 
00314         // insert the new cut
00315         if ( pNode->nRefs ) 
00316             pNode->pCutBest->aFlow = Fpga_CutRef( p, pNode, pNode->pCutBest, 0 );
00317 //        printf( "\nError: Could not match a node in the object graph.\n" );
00318         return 0;
00319     }
00320 
00321     // insert the new cut
00322     // make sure the area selected is not worse then the original area
00323     if ( pNode->nRefs ) 
00324     {
00325         pNode->pCutBest->aFlow = Fpga_CutRef( p, pNode, pNode->pCutBest, 0 );
00326 //        assert( pNode->pCutBest->aFlow <= aAreaCutBest );
00327 //        assert( pNode->tRequired < FPGA_FLOAT_LARGE );
00328     }
00329     return 1;
00330 }

int Fpga_MatchNodeSwitch ( Fpga_Man_t *  p,
Fpga_Node_t *  pNode 
) [static]

Function*************************************************************

Synopsis [Computes the best matching for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 386 of file fpgaMatch.c.

00387 {
00388     Fpga_Cut_t * pCut, * pCutBestOld;
00389     float aAreaCutBest;
00390     int clk;
00391     // make sure that at least one cut other than the trivial is present
00392     if ( pNode->pCuts->pNext == NULL )
00393     {
00394         printf( "\nError: A node in the mapping graph does not have feasible cuts.\n" );
00395         return 0;
00396     }
00397 
00398     // remember the old cut
00399     pCutBestOld = pNode->pCutBest;
00400     // deref the old cut
00401     if ( pNode->nRefs ) 
00402         aAreaCutBest = Fpga_CutDerefSwitch( p, pNode, pNode->pCutBest, 0 );
00403 
00404     // search for a better cut
00405     pNode->pCutBest = NULL;
00406     for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext )
00407     {
00408         // compute the arrival time of the cut and its area flow
00409 clk = clock();
00410         pCut->tArrival = Fpga_TimeCutComputeArrival( p, pCut );
00411 //p->time2 += clock() - clk;
00412         // drop the cut if it does not meet the required times
00413         if ( Fpga_FloatMoreThan( p, pCut->tArrival, pNode->tRequired ) )
00414             continue;
00415         // get the area of this cut
00416         pCut->aFlow = Fpga_CutGetSwitchDerefed( p, pNode, pCut );
00417         // if no cut is assigned, use the current one
00418         if ( pNode->pCutBest == NULL )
00419         {
00420             pNode->pCutBest = pCut;
00421             continue;
00422         }
00423         // choose the best cut as follows: exact area first, delay as a tie-breaker
00424         if ( Fpga_FloatMoreThan(p, pNode->pCutBest->aFlow, pCut->aFlow) || 
00425              Fpga_FloatEqual(p, pNode->pCutBest->aFlow, pCut->aFlow) && Fpga_FloatMoreThan(p, pNode->pCutBest->tArrival, pCut->tArrival) )
00426         {
00427             pNode->pCutBest = pCut;
00428         }
00429     }
00430 
00431     // make sure the match is found
00432     if ( pNode->pCutBest == NULL )
00433     {
00434         pNode->pCutBest = pCutBestOld; 
00435         // insert the new cut
00436         if ( pNode->nRefs ) 
00437             pNode->pCutBest->aFlow = Fpga_CutRefSwitch( p, pNode, pNode->pCutBest, 0 );
00438 //        printf( "\nError: Could not match a node in the object graph.\n" );
00439         return 0;
00440     }
00441 
00442     // insert the new cut
00443     // make sure the area selected is not worse then the original area
00444     if ( pNode->nRefs ) 
00445     {
00446         pNode->pCutBest->aFlow = Fpga_CutRefSwitch( p, pNode, pNode->pCutBest, 0 );
00447         assert( pNode->pCutBest->aFlow <= aAreaCutBest + 0.001 );
00448 //        assert( pNode->tRequired < FPGA_FLOAT_LARGE );
00449     }
00450     return 1;
00451 }

Generated on Tue Jan 5 12:19:03 2010 for abc70930 by  doxygen 1.6.1