src/map/fpga/fpgaMatch.c

Go to the documentation of this file.

#include "fpgaInt.h"


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 )
{
    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 );
/*
    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;
}

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 ( Fpga_FloatMoreThan(p, 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 && 
               (Fpga_FloatMoreThan(p, pNode->pCutBest->tArrival, pCut->tArrival) || 
                Fpga_FloatEqual(p, pNode->pCutBest->tArrival, pCut->tArrival) && Fpga_FloatMoreThan(p, pNode->pCutBest->aFlow, pCut->aFlow) )) ||
             (!fDelayOriented && 
               (Fpga_FloatMoreThan(p, pNode->pCutBest->aFlow, pCut->aFlow) || 
                Fpga_FloatEqual(p, pNode->pCutBest->aFlow, pCut->aFlow) && Fpga_FloatMoreThan(p, 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;
}





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;
}

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;
}

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 ( Fpga_FloatMoreThan( p, 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 ( Fpga_FloatMoreThan(p, pNode->pCutBest->aFlow, pCut->aFlow) || 
             Fpga_FloatEqual(p, pNode->pCutBest->aFlow, pCut->aFlow) && Fpga_FloatMoreThan(p, 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;
}




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;
}

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 ( Fpga_FloatMoreThan( p, 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 ( Fpga_FloatMoreThan(p, pNode->pCutBest->aFlow, pCut->aFlow) || 
             Fpga_FloatEqual(p, pNode->pCutBest->aFlow, pCut->aFlow) && Fpga_FloatMoreThan(p, 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 + 0.001 );
//        assert( pNode->tRequired < FPGA_FLOAT_LARGE );
    }
    return 1;
}


#if 0

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, 0 );

        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) );
}



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) );
}


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


float Fpga_FindBestNode( Fpga_Man_t * p, Fpga_NodeVec_t * vNodes, Fpga_Node_t ** ppNode, Fpga_Cut_t ** ppCutBest )
{
    Fpga_Node_t * pNode;
    Fpga_Cut_t * pCut;
    float Gain, CutArea1, CutArea2, CutArea3;
    int i;

    Gain = 0;
    for ( i = 0; i < vNodes->nSize; i++ )
    {
        pNode = vNodes->pArray[i];
        // deref the current cut
        CutArea1 = Fpga_CutDeref( p, pNode, pNode->pCutBest, 0 );

        // ref all the cuts
        for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext )
        {
            if ( pCut == pNode->pCutBest )
                continue;
            if ( pCut->tArrival > pNode->tRequired )
                continue;

            CutArea2 = Fpga_CutGetAreaDerefed( p, pCut );
            if ( Gain < CutArea1 - CutArea2 )
            {
                *ppNode = pNode;
                *ppCutBest = pCut;
                Gain = CutArea1 - CutArea2;
            }
        }
        // ref the old cut
        CutArea3 = Fpga_CutRef( p, pNode, pNode->pCutBest, 0 );
        assert( CutArea1 == CutArea3 );
    }
    if ( Gain == 0 )
        printf( "Returning no gain.\n" );

    return Gain;
}

---