From 888e5bed5d7f56a5d86d91a6e8e88f3e5a3454dc Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Fri, 29 Jul 2005 08:01:00 -0700 Subject: Version abc50729 --- src/map/fpga/fpga.c | 239 ++++++++ src/map/fpga/fpga.h | 158 ++++++ src/map/fpga/fpgaCore.c | 241 ++++++++ src/map/fpga/fpgaCreate.c | 585 ++++++++++++++++++++ src/map/fpga/fpgaCut.c | 1150 ++++++++++++++++++++++++++++++++++++++ src/map/fpga/fpgaCutUtils.c | 571 +++++++++++++++++++ src/map/fpga/fpgaFanout.c | 139 +++++ src/map/fpga/fpgaGENERIC.c | 46 ++ src/map/fpga/fpgaInt.h | 395 +++++++++++++ src/map/fpga/fpgaLib.c | 183 ++++++ src/map/fpga/fpgaMatch.c | 729 ++++++++++++++++++++++++ src/map/fpga/fpgaTime.c | 189 +++++++ src/map/fpga/fpgaTruth.c | 107 ++++ src/map/fpga/fpgaUtils.c | 1289 +++++++++++++++++++++++++++++++++++++++++++ src/map/fpga/fpgaVec.c | 408 ++++++++++++++ src/map/fpga/module.make | 12 + 16 files changed, 6441 insertions(+) create mode 100644 src/map/fpga/fpga.c create mode 100644 src/map/fpga/fpga.h create mode 100644 src/map/fpga/fpgaCore.c create mode 100644 src/map/fpga/fpgaCreate.c create mode 100644 src/map/fpga/fpgaCut.c create mode 100644 src/map/fpga/fpgaCutUtils.c create mode 100644 src/map/fpga/fpgaFanout.c create mode 100644 src/map/fpga/fpgaGENERIC.c create mode 100644 src/map/fpga/fpgaInt.h create mode 100644 src/map/fpga/fpgaLib.c create mode 100644 src/map/fpga/fpgaMatch.c create mode 100644 src/map/fpga/fpgaTime.c create mode 100644 src/map/fpga/fpgaTruth.c create mode 100644 src/map/fpga/fpgaUtils.c create mode 100644 src/map/fpga/fpgaVec.c create mode 100644 src/map/fpga/module.make (limited to 'src/map/fpga') diff --git a/src/map/fpga/fpga.c b/src/map/fpga/fpga.c new file mode 100644 index 00000000..6b107498 --- /dev/null +++ b/src/map/fpga/fpga.c @@ -0,0 +1,239 @@ +/**CFile**************************************************************** + + FileName [fpga.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Command file for the FPGA package.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 2.0. Started - August 18, 2004.] + + Revision [$Id: fpga.c,v 1.4 2004/10/28 17:36:07 alanmi Exp $] + +***********************************************************************/ + +#include "fpgaInt.h" +#include "main.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static int Fpga_CommandReadLibrary( Abc_Frame_t * pAbc, int argc, char **argv ); +static int Fpga_CommandPrintLibrary( Abc_Frame_t * pAbc, int argc, char **argv ); + +// the library file format should be as follows: +/* +# The area/delay of k-variable LUTs: +# k area delay +1 1 1 +2 2 2 +3 4 3 +4 8 4 +5 16 5 +6 32 6 +*/ + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Package initialization procedure.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +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} }; + Abc_FrameSetLibLut( pAbc, Fpga_LutLibDup(&s_LutLib) ); + + Cmd_CommandAdd( pAbc, "FPGA mapping", "read_lut", Fpga_CommandReadLibrary, 0 ); + Cmd_CommandAdd( pAbc, "FPGA mapping", "print_lut", Fpga_CommandPrintLibrary, 0 ); +} + +/**Function************************************************************* + + Synopsis [Package ending procedure.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_End() +{ + Fpga_LutLibFree( Abc_FrameReadLibLut(Abc_FrameGetGlobalFrame()) ); +} + + +/**Function************************************************************* + + Synopsis [Command procedure to read LUT libraries.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_CommandReadLibrary( Abc_Frame_t * pAbc, int argc, char **argv ) +{ + FILE * pFile; + FILE * pOut, * pErr; + Fpga_LutLib_t * pLib; + Abc_Ntk_t * pNet; + char * FileName; + int fVerbose; + int c; + + pNet = Abc_FrameReadNet(pAbc); + pOut = Abc_FrameReadOut(pAbc); + pErr = Abc_FrameReadErr(pAbc); + + // set the defaults + fVerbose = 1; + util_getopt_reset(); + while ( (c = util_getopt(argc, argv, "vh")) != EOF ) + { + switch (c) + { + case 'v': + fVerbose ^= 1; + break; + case 'h': + goto usage; + break; + default: + goto usage; + } + } + + + if ( argc != util_optind + 1 ) + { + goto usage; + } + + // get the input file name + FileName = argv[util_optind]; + if ( (pFile = fopen( FileName, "r" )) == NULL ) + { + fprintf( pErr, "Cannot open input file \"%s\". ", FileName ); + if ( FileName = Extra_FileGetSimilarName( FileName, ".genlib", ".lib", ".gen", ".g", NULL ) ) + fprintf( pErr, "Did you mean \"%s\"?", FileName ); + fprintf( pErr, "\n" ); + return 1; + } + fclose( pFile ); + + // set the new network + pLib = Fpga_LutLibCreate( FileName, fVerbose ); + if ( pLib == NULL ) + { + fprintf( pErr, "Reading LUT library has failed.\n" ); + goto usage; + } + // replace the current library + Fpga_LutLibFree( Abc_FrameReadLibLut(Abc_FrameGetGlobalFrame()) ); + Abc_FrameSetLibLut( Abc_FrameGetGlobalFrame(), pLib ); + return 0; + +usage: + fprintf( pErr, "\nusage: read_lut [-vh]\n"); + fprintf( pErr, "\t read the LUT library from the file\n" ); + fprintf( pErr, "\t-v : toggles enabling of verbose output [default = %s]\n", (fVerbose? "yes" : "no") ); + fprintf( pErr, "\t-h : print the command usage\n"); + fprintf( pErr, "\t \n"); + fprintf( pErr, "\t File format for a LUT library:\n"); + fprintf( pErr, "\t (the default library is shown)\n"); + fprintf( pErr, "\t \n"); + fprintf( pErr, "\t # The area/delay of k-variable LUTs:\n"); + fprintf( pErr, "\t # k area delay\n"); + fprintf( pErr, "\t 1 1 1\n"); + fprintf( pErr, "\t 2 2 2\n"); + fprintf( pErr, "\t 3 4 3\n"); + fprintf( pErr, "\t 4 8 4\n"); + fprintf( pErr, "\t 5 16 5\n"); + fprintf( pErr, "\t 6 32 6\n"); + return 1; /* error exit */ +} + +/**Function************************************************************* + + Synopsis [Command procedure to read LUT libraries.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_CommandPrintLibrary( Abc_Frame_t * pAbc, int argc, char **argv ) +{ + FILE * pOut, * pErr; + Abc_Ntk_t * pNet; + int fVerbose; + int c; + + pNet = Abc_FrameReadNet(pAbc); + pOut = Abc_FrameReadOut(pAbc); + pErr = Abc_FrameReadErr(pAbc); + + // set the defaults + fVerbose = 1; + util_getopt_reset(); + while ( (c = util_getopt(argc, argv, "vh")) != EOF ) + { + switch (c) + { + case 'v': + fVerbose ^= 1; + break; + case 'h': + goto usage; + break; + default: + goto usage; + } + } + + + if ( argc != util_optind ) + { + goto usage; + } + + // set the new network + Fpga_LutLibPrint( Abc_FrameReadLibLut(Abc_FrameGetGlobalFrame()) ); + return 0; + +usage: + fprintf( pErr, "\nusage: read_print [-vh]\n"); + fprintf( pErr, "\t print the current LUT library\n" ); + fprintf( pErr, "\t-v : toggles enabling of verbose output [default = %s]\n", (fVerbose? "yes" : "no") ); + fprintf( pErr, "\t-h : print the command usage\n"); + return 1; /* error exit */ +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/fpga/fpga.h b/src/map/fpga/fpga.h new file mode 100644 index 00000000..62a93a75 --- /dev/null +++ b/src/map/fpga/fpga.h @@ -0,0 +1,158 @@ +/**CFile**************************************************************** + + FileName [fpga.h] + + PackageName [MVSIS 2.0: 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: fpga.h,v 1.7 2004/09/30 21:18:09 satrajit Exp $] + +***********************************************************************/ + +#ifndef __FPGA_H__ +#define __FPGA_H__ + +//////////////////////////////////////////////////////////////////////// +/// INCLUDES /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// PARAMETERS /// +//////////////////////////////////////////////////////////////////////// + +// the maximum size of LUTs used for mapping +#define FPGA_MAX_LUTSIZE 10 + +//////////////////////////////////////////////////////////////////////// +/// STRUCTURE DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +typedef struct Fpga_ManStruct_t_ Fpga_Man_t; +typedef struct Fpga_NodeStruct_t_ Fpga_Node_t; +typedef struct Fpga_NodeVecStruct_t_ Fpga_NodeVec_t; +typedef struct Fpga_CutStruct_t_ Fpga_Cut_t; +typedef struct Fpga_LutLibStruct_t_ Fpga_LutLib_t; + +//////////////////////////////////////////////////////////////////////// +/// GLOBAL VARIABLES /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// MACRO DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +#define Fpga_IsComplement(p) (((int)((long) (p) & 01))) +#define Fpga_Regular(p) ((Fpga_Node_t *)((unsigned)(p) & ~01)) +#define Fpga_Not(p) ((Fpga_Node_t *)((long)(p) ^ 01)) +#define Fpga_NotCond(p,c) ((Fpga_Node_t *)((long)(p) ^ (c))) + +#define Fpga_Ref(p) +#define Fpga_Deref(p) +#define Fpga_RecursiveDeref(p,c) + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/*=== fpgaCreate.c =============================================================*/ +extern Fpga_Man_t * Fpga_ManCreate( int nInputs, int nOutputs, int fVerbose ); +extern Fpga_Node_t * Fpga_NodeCreate( Fpga_Man_t * p, Fpga_Node_t * p1, Fpga_Node_t * p2 ); +extern void Fpga_ManFree( Fpga_Man_t * pMan ); +extern void Fpga_ManPrintTimeStats( Fpga_Man_t * p ); + +extern int Fpga_ManReadInputNum( Fpga_Man_t * p ); +extern int Fpga_ManReadOutputNum( Fpga_Man_t * p ); +extern Fpga_Node_t ** Fpga_ManReadInputs ( Fpga_Man_t * p ); +extern Fpga_Node_t ** Fpga_ManReadOutputs( Fpga_Man_t * p ); +extern Fpga_Node_t * Fpga_ManReadConst1 ( Fpga_Man_t * p ); +extern float * Fpga_ManReadInputArrivals( Fpga_Man_t * p ); +extern int Fpga_ManReadVerbose( Fpga_Man_t * p ); +extern float * Fpga_ManReadLutAreas( Fpga_Man_t * p ); +extern void Fpga_ManSetTimeToMap( Fpga_Man_t * p, int Time ); +extern void Fpga_ManSetTimeToNet( Fpga_Man_t * p, int Time ); +extern void Fpga_ManSetTimeTotal( Fpga_Man_t * p, int Time ); +extern void Fpga_ManSetOutputNames( Fpga_Man_t * p, char ** ppNames ); +extern void Fpga_ManSetInputArrivals( Fpga_Man_t * p, float * pArrivals ); +extern void Fpga_ManSetTree( Fpga_Man_t * p, int fTree ); +extern void Fpga_ManSetPower( Fpga_Man_t * p, int fPower ); +extern void Fpga_ManSetAreaRecovery( Fpga_Man_t * p, int fAreaRecovery ); +extern void Fpga_ManSetResyn( Fpga_Man_t * p, int fResynthesis ); +extern void Fpga_ManSetDelayLimit( Fpga_Man_t * p, float DelayLimit ); +extern void Fpga_ManSetAreaLimit( Fpga_Man_t * p, float AreaLimit ); +extern void Fpga_ManSetTimeLimit( Fpga_Man_t * p, float TimeLimit ); +extern void Fpga_ManSetObeyFanoutLimits( Fpga_Man_t * p, int fObeyFanoutLimits ); +extern void Fpga_ManSetNumIterations( Fpga_Man_t * p, int nNumIterations ); +extern int Fpga_ManReadFanoutViolations( Fpga_Man_t * p ); +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_ManSetLatchNum( Fpga_Man_t * p, int nLatches ); +extern void Fpga_ManSetSequential( Fpga_Man_t * p, int fSequential ); +extern void Fpga_ManSetName( Fpga_Man_t * p, char * pFileName ); + +extern int Fpga_LibReadLutMax( Fpga_LutLib_t * pLib ); + +extern char * Fpga_NodeReadData0( Fpga_Node_t * p ); +extern Fpga_Node_t * Fpga_NodeReadData1( Fpga_Node_t * p ); +extern int Fpga_NodeReadNum( Fpga_Node_t * p ); +extern int Fpga_NodeReadLevel( Fpga_Node_t * p ); +extern Fpga_Cut_t * Fpga_NodeReadCuts( Fpga_Node_t * p ); +extern Fpga_Cut_t * Fpga_NodeReadCutBest( Fpga_Node_t * p ); +extern Fpga_Node_t * Fpga_NodeReadOne( Fpga_Node_t * p ); +extern Fpga_Node_t * Fpga_NodeReadTwo( Fpga_Node_t * p ); +extern void Fpga_NodeSetLevel( Fpga_Node_t * p, Fpga_Node_t * pNode ); +extern void Fpga_NodeSetData0( Fpga_Node_t * p, char * pData ); +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 int Fpga_NodeIsConst( Fpga_Node_t * p ); +extern int Fpga_NodeIsVar( Fpga_Node_t * p ); +extern int Fpga_NodeIsAnd( Fpga_Node_t * p ); +extern int Fpga_NodeComparePhase( Fpga_Node_t * p1, Fpga_Node_t * p2 ); + +extern int Fpga_CutReadLeavesNum( Fpga_Cut_t * p ); +extern Fpga_Node_t ** Fpga_CutReadLeaves( Fpga_Cut_t * p ); + +extern Fpga_Node_t * Fpga_NodeAnd( Fpga_Man_t * p, Fpga_Node_t * p1, Fpga_Node_t * p2 ); +extern Fpga_Node_t * Fpga_NodeOr( Fpga_Man_t * p, Fpga_Node_t * p1, Fpga_Node_t * p2 ); +extern Fpga_Node_t * Fpga_NodeExor( Fpga_Man_t * p, Fpga_Node_t * p1, Fpga_Node_t * p2 ); +extern Fpga_Node_t * Fpga_NodeMux( Fpga_Man_t * p, Fpga_Node_t * pNode, Fpga_Node_t * pNodeT, Fpga_Node_t * pNodeE ); +extern void Fpga_NodeSetChoice( Fpga_Man_t * pMan, Fpga_Node_t * pNodeOld, Fpga_Node_t * pNodeNew ); + +extern void Fpga_ManStats( Fpga_Man_t * p ); + +/*=== fpgaCore.c =============================================================*/ +extern int Fpga_Mapping( Fpga_Man_t * p ); +/*=== fpgaCut.c ===============================================================*/ +extern void Fpga_MappingCreatePiCuts( Fpga_Man_t * p ); +extern void Fpga_CutsCleanSign( Fpga_Man_t * pMan ); +/*=== fpgaCutUtils.c =============================================================*/ +extern void Fpga_CutCreateFromNode( Fpga_Man_t * p, int iRoot, int * pLeaves, int nLeaves ); +extern void Fpga_MappingSetUsedCuts( Fpga_Man_t * p ); +/*=== fpgaFraig.c =============================================================*/ +extern Fpga_Man_t * Fpga_ManDupFraig( Fraig_Man_t * pManFraig ); +extern Fpga_Man_t * Fpga_ManBalanceFraig( Fraig_Man_t * pManFraig, int * pInputArrivals ); +/*=== fpgaLib.c =============================================================*/ +extern Fpga_LutLib_t * Fpga_LutLibDup( Fpga_LutLib_t * p ); +/*=== fpgaTruth.c =============================================================*/ +extern void * Fpga_TruthsCutBdd( void * dd, Fpga_Cut_t * pCut ); +/*=== fpgaUtil.c =============================================================*/ +extern int Fpga_ManCheckConsistency( Fpga_Man_t * p ); +extern void Fpga_ManCleanData0( Fpga_Man_t * pMan ); +extern Fpga_NodeVec_t * Fpga_CollectNodeTfo( Fpga_Man_t * pMan, Fpga_Node_t * pNode ); + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// +#endif diff --git a/src/map/fpga/fpgaCore.c b/src/map/fpga/fpgaCore.c new file mode 100644 index 00000000..37726542 --- /dev/null +++ b/src/map/fpga/fpgaCore.c @@ -0,0 +1,241 @@ +/**CFile**************************************************************** + + FileName [fpgaCore.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: fpgaCore.c,v 1.7 2004/10/01 23:41:04 satrajit Exp $] + +***********************************************************************/ + +#include "fpgaInt.h" +//#include "res.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static int Fpga_MappingPostProcess( Fpga_Man_t * p ); + +extern void Fpga_Experiment( Fpga_Man_t * p ); +extern void Fpga_MappingCutsSeq( Fpga_Man_t * p ); +extern void Fpga_MappingLValues( Fpga_Man_t * pMan, int fVerbose ); + + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Performs technology mapping for the given object graph.] + + Description [The object graph is stored in the mapping manager. + First, all the AND-nodes, which fanout into the POs, are collected + in the DFS fashion. Next, three steps are performed: the k-feasible + cuts are computed for each node, the truth tables are computed for + each cut, and the delay-optimal matches are assigned for each node.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_Mapping( Fpga_Man_t * p ) +{ + int clk; + + // collect the nodes reachable from POs in the DFS order (including the choices) + p->vAnds = Fpga_MappingDfs( p, 1 ); + Fpga_ManReportChoices( p ); // recomputes levels + Fpga_MappingSetChoiceLevels( p ); + + if ( p->fSequential ) + { +// Fpga_MappingCutsSeq( p ); + Fpga_MappingCuts( p ); +//clk = clock(); +// Fpga_MappingLValues( p, p->fVerbose ); +//PRT( "Time", clock() - clk ); + return 0; + } + + // compute the cuts of nodes in the DFS order + clk = clock(); + Fpga_MappingCuts( p ); + p->timeCuts = clock() - clk; + +// Fpga_MappingSortByLevel( p, p->vAnds, 1 ); + + // derive the truth tables + clk = clock(); +// Fpga_MappingTruths( p ); + p->timeTruth = clock() - clk; + + // match the truth tables to the supergates + clk = clock(); + if ( !Fpga_MappingMatches( p, 1 ) ) + return 0; + p->timeMatch = clock() - clk; + + // perform area recovery + if ( p->fAreaRecovery ) + { + clk = clock(); + if ( !Fpga_MappingPostProcess( p ) ) + return 0; + p->timeRecover = clock() - clk; + } + + // perform resynthesis +// if ( p->fResynthesis ) +// Res_Resynthesize( p, p->DelayLimit, p->AreaLimit, p->TimeLimit, 1 ); + + // print the AI-graph used for mapping + //Fpga_ManShow( p, "test" ); + if ( p->fVerbose ) + Fpga_MappingPrintOutputArrivals( p ); + return 1; +} + +/**Function************************************************************* + + Synopsis [Postprocesses the mapped network for area recovery.] + + Description [This procedure assumes that the mapping is assigned. + It iterates the loop, in which the required times are computed and + the mapping is updated. It is conceptually similar to the paper: + V. Manohararajah, S. D. Brown, Z. G. Vranesic, Heuristics for area + minimization in LUT-based FGPA technology mapping. Proc. IWLS '04.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_MappingPostProcess( Fpga_Man_t * p ) +{ + float aAreaTotalPrev, aAreaTotalCur, aAreaTotalCur2; + float aSwitchTotalPrev, aSwitchTotalCur; + int Iter, clk; + +if ( p->fVerbose ) +{ +printf( "Iteration %dD : Area = %11.1f ", 0, Fpga_MappingArea( p ) ); +PRT( "Time", p->timeMatch ); +} + +// aAreaTotalCur = FPGA_FLOAT_LARGE; + aAreaTotalCur = Fpga_MappingSetRefsAndArea( p ); + + Iter = 1; + do { +clk = clock(); + // save the previous area flow + aAreaTotalPrev = aAreaTotalCur; + + // compute the required times and the fanouts + Fpga_TimeComputeRequiredGlobal( p ); + // remap topologically + Fpga_MappingMatches( p, 0 ); + // get the resulting area + aAreaTotalCur = Fpga_MappingArea( p ); +if ( p->fVerbose ) +{ +printf( "Iteration %dF : Area = %11.1f ", Iter++, aAreaTotalCur ); +PRT( "Time", clock() - clk ); +} + if ( p->fPower ) + aSwitchTotalCur = Fpga_MappingPrintSwitching( p ); + // quit if this iteration reduced area flow by less than 1% + } while ( aAreaTotalPrev > 1.02 * aAreaTotalCur ); + + +/* + // compute the area of each cut + aAreaTotalCur = Fpga_MappingSetRefsAndArea( p ); + // compute the required times and the fanouts + Fpga_TimeComputeRequiredGlobal( p ); + // perform experiment + Fpga_Experiment( p ); +*/ + + + // compute the area of each cut + aAreaTotalCur = Fpga_MappingSetRefsAndArea( p ); + aAreaTotalCur2 = Fpga_MappingComputeCutAreas( p ); + assert( aAreaTotalCur == aAreaTotalCur2 ); + + +// aAreaTotalCur = FPGA_FLOAT_LARGE; +// Iter = 1; + do { +clk = clock(); + // save the previous area flow + aAreaTotalPrev = aAreaTotalCur; + + // compute the required times and the fanouts + Fpga_TimeComputeRequiredGlobal( p ); + // remap topologically + Fpga_MappingMatchesArea( p ); + // get the resulting area + aAreaTotalCur = Fpga_MappingArea( p ); +if ( p->fVerbose ) +{ +printf( "Iteration %dA : Area = %11.1f ", Iter++, aAreaTotalCur ); +PRT( "Time", clock() - clk ); +} + if ( p->fPower ) + { + aSwitchTotalPrev = aSwitchTotalCur; + aSwitchTotalCur = Fpga_MappingPrintSwitching( p ); + } + // quit if this iteration reduced area flow by less than 1% + } while ( aAreaTotalPrev > 1.02 * aAreaTotalCur ); + + + if ( p->fPower ) + { + do { +clk = clock(); + // save the previous area flow + aAreaTotalPrev = aAreaTotalCur; + + // compute the required times and the fanouts + Fpga_TimeComputeRequiredGlobal( p ); + // remap topologically + Fpga_MappingMatchesSwitch( p ); + // get the resulting area + aAreaTotalCur = Fpga_MappingArea( p ); +if ( p->fVerbose ) +{ +printf( "Iteration %dS : Area = %11.1f ", Iter++, aAreaTotalCur ); +PRT( "Time", clock() - clk ); +} + aSwitchTotalPrev = aSwitchTotalCur; + aSwitchTotalCur = Fpga_MappingPrintSwitching( p ); + // quit if this iteration reduced area flow by less than 1% + } while ( aSwitchTotalPrev > 1.01 * aSwitchTotalCur ); + } + +/* + // compute the area of each cut + aAreaTotalCur = Fpga_MappingSetRefsAndArea( p ); + // compute the required times and the fanouts + Fpga_TimeComputeRequiredGlobal( p ); + // perform experiment + Fpga_Experiment( p ); +*/ + p->fAreaGlo = aAreaTotalCur; + return 1; +} + + diff --git a/src/map/fpga/fpgaCreate.c b/src/map/fpga/fpgaCreate.c new file mode 100644 index 00000000..fc6577fa --- /dev/null +++ b/src/map/fpga/fpgaCreate.c @@ -0,0 +1,585 @@ +/**CFile**************************************************************** + + FileName [fpgaCreate.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: fpgaCreate.c,v 1.8 2004/09/30 21:18:09 satrajit Exp $] + +***********************************************************************/ + +#include "fpgaInt.h" +#include "main.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static void Fpga_TableCreate( Fpga_Man_t * p ); +static void Fpga_TableResize( Fpga_Man_t * p ); +static Fpga_Node_t * Fpga_TableLookup( Fpga_Man_t * p, Fpga_Node_t * p1, Fpga_Node_t * p2 ); + +// hash key for the structural hash table +static inline unsigned Fpga_HashKey2( Fpga_Node_t * p0, Fpga_Node_t * p1, int TableSize ) { return ((unsigned)(p0) + (unsigned)(p1) * 12582917) % TableSize; } + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Reads parameters of the mapping manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_ManReadInputNum( Fpga_Man_t * p ) { return p->nInputs; } +int Fpga_ManReadOutputNum( Fpga_Man_t * p ) { return p->nOutputs; } +Fpga_Node_t ** Fpga_ManReadInputs ( Fpga_Man_t * p ) { return p->pInputs; } +Fpga_Node_t ** Fpga_ManReadOutputs( Fpga_Man_t * p ) { return p->pOutputs; } +Fpga_Node_t * Fpga_ManReadConst1 ( Fpga_Man_t * p ) { return p->pConst1; } +float * Fpga_ManReadInputArrivals( Fpga_Man_t * p ) { return p->pInputArrivals;} +int Fpga_ManReadVerbose( Fpga_Man_t * p ) { return p->fVerbose; } +float * Fpga_ManReadLutAreas( Fpga_Man_t * p ) { return p->pLutLib->pLutAreas; } +void Fpga_ManSetTimeToMap( Fpga_Man_t * p, int Time ) { p->timeToMap = Time; } +void Fpga_ManSetTimeToNet( Fpga_Man_t * p, int Time ) { p->timeToNet = Time; } +void Fpga_ManSetTimeTotal( Fpga_Man_t * p, int Time ) { p->timeTotal = Time; } +void Fpga_ManSetOutputNames( Fpga_Man_t * p, char ** ppNames ) { p->ppOutputNames = ppNames; } +void Fpga_ManSetInputArrivals( Fpga_Man_t * p, float * pArrivals ) { p->pInputArrivals = pArrivals; } +void Fpga_ManSetTree( Fpga_Man_t * p, int fTree ) { p->fTree = fTree; } +void Fpga_ManSetPower( Fpga_Man_t * p, int fPower ) { p->fPower = fPower; } +void Fpga_ManSetAreaRecovery( Fpga_Man_t * p, int fAreaRecovery ) { p->fAreaRecovery = fAreaRecovery;} +void Fpga_ManSetResyn( Fpga_Man_t * p, int fResynthesis ) { p->fResynthesis = fResynthesis; } +void Fpga_ManSetDelayLimit( Fpga_Man_t * p, float DelayLimit ) { p->DelayLimit = DelayLimit; } +void Fpga_ManSetAreaLimit( Fpga_Man_t * p, float AreaLimit ) { p->AreaLimit = AreaLimit; } +void Fpga_ManSetTimeLimit( Fpga_Man_t * p, float TimeLimit ) { p->TimeLimit = TimeLimit; } +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_ManSetLatchNum( Fpga_Man_t * p, int nLatches ) { p->nLatches = nLatches; } +void Fpga_ManSetSequential( Fpga_Man_t * p, int fSequential ) { p->fSequential = fSequential; } +void Fpga_ManSetName( Fpga_Man_t * p, char * pFileName ) { p->pFileName = pFileName; } + +/**Function************************************************************* + + Synopsis [Reads the parameters of the LUT library.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_LibReadLutMax( Fpga_LutLib_t * pLib ) { return pLib->LutMax; } + +/**Function************************************************************* + + Synopsis [Reads parameters of the mapping node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +char * Fpga_NodeReadData0( Fpga_Node_t * p ) { return p->pData0; } +Fpga_Node_t * Fpga_NodeReadData1( Fpga_Node_t * p ) { return p->pLevel; } +int Fpga_NodeReadNum( Fpga_Node_t * p ) { return p->Num; } +int Fpga_NodeReadLevel( Fpga_Node_t * p ) { return Fpga_Regular(p)->Level; } +Fpga_Cut_t * Fpga_NodeReadCuts( Fpga_Node_t * p ) { return p->pCuts; } +Fpga_Cut_t * Fpga_NodeReadCutBest( Fpga_Node_t * p ) { return p->pCutBest; } +Fpga_Node_t * Fpga_NodeReadOne( Fpga_Node_t * p ) { return p->p1; } +Fpga_Node_t * Fpga_NodeReadTwo( Fpga_Node_t * p ) { return p->p2; } +void Fpga_NodeSetData0( Fpga_Node_t * p, char * pData ) { p->pData0 = pData; } +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; } + +/**Function************************************************************* + + Synopsis [Checks the type of the node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_NodeIsConst( Fpga_Node_t * p ) { return (Fpga_Regular(p))->Num == -1; } +int Fpga_NodeIsVar( Fpga_Node_t * p ) { return (Fpga_Regular(p))->p1 == NULL && (Fpga_Regular(p))->Num >= 0; } +int Fpga_NodeIsAnd( Fpga_Node_t * p ) { return (Fpga_Regular(p))->p1 != NULL; } +int Fpga_NodeComparePhase( Fpga_Node_t * p1, Fpga_Node_t * p2 ) { assert( !Fpga_IsComplement(p1) ); assert( !Fpga_IsComplement(p2) ); return p1->fInv ^ p2->fInv; } + +/**Function************************************************************* + + Synopsis [Reads parameters from the cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_CutReadLeavesNum( Fpga_Cut_t * p ) { return p->nLeaves; } +Fpga_Node_t ** Fpga_CutReadLeaves( Fpga_Cut_t * p ) { return p->ppLeaves; } + + +/**Function************************************************************* + + Synopsis [Create the mapping manager.] + + Description [The number of inputs and outputs is assumed to be + known is advance. It is much simpler to have them fixed upfront. + When it comes to representing the object graph in the form of + AIG, the resulting manager is similar to the regular AIG manager, + except that it does not use reference counting (and therefore + does not have garbage collections). It does have table resizing. + The data structure is more flexible to represent additional + information needed for mapping.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Man_t * Fpga_ManCreate( int nInputs, int nOutputs, int fVerbose ) +{ + Fpga_Man_t * p; + int i; + + // start the manager + p = ALLOC( Fpga_Man_t, 1 ); + memset( p, 0, sizeof(Fpga_Man_t) ); + p->pLutLib = Abc_FrameReadLibLut(Abc_FrameGetGlobalFrame()); + p->nVarsMax = p->pLutLib->LutMax; + p->fVerbose = fVerbose; + p->fAreaRecovery = 1; + p->fTree = 0; + p->fRefCount = 1; + p->fEpsilon = (float)0.00001; + + Fpga_TableCreate( p ); +//if ( p->fVerbose ) +// printf( "Node = %d (%d) bytes. Cut = %d bytes.\n", sizeof(Fpga_Node_t), FPGA_NUM_BYTES(sizeof(Fpga_Node_t)), sizeof(Fpga_Cut_t) ); + p->mmNodes = Extra_MmFixedStart( FPGA_NUM_BYTES(sizeof(Fpga_Node_t)) ); + p->mmCuts = Extra_MmFixedStart( sizeof(Fpga_Cut_t) ); + + assert( p->nVarsMax > 0 ); + Fpga_MappingSetupTruthTables( p->uTruths ); + + // make sure the constant node will get index -1 + p->nNodes = -1; + // create the constant node + p->pConst1 = Fpga_NodeCreate( p, NULL, NULL ); + p->vNodesAll = Fpga_NodeVecAlloc( 100 ); + + // create the PI nodes + p->nInputs = nInputs; + p->pInputs = ALLOC( Fpga_Node_t *, nInputs ); + for ( i = 0; i < nInputs; i++ ) + p->pInputs[i] = Fpga_NodeCreate( p, NULL, NULL ); + + // create the place for the output nodes + p->nOutputs = nOutputs; + p->pOutputs = ALLOC( Fpga_Node_t *, nOutputs ); + memset( p->pOutputs, 0, sizeof(Fpga_Node_t *) * nOutputs ); + return p; +} + +/**Function************************************************************* + + Synopsis [Deallocates the mapping manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_ManFree( Fpga_Man_t * p ) +{ +// Fpga_ManStats( p ); + +// int i; +// for ( i = 0; i < p->vNodesAll->nSize; i++ ) +// Fpga_NodeVecFree( p->vNodesAll->pArray[i]->vFanouts ); +// Fpga_NodeVecFree( p->pConst1->vFanouts ); + if ( p->vAnds ) + Fpga_NodeVecFree( p->vAnds ); + if ( p->vNodesAll ) + Fpga_NodeVecFree( p->vNodesAll ); + Extra_MmFixedStop( p->mmNodes, 0 ); + Extra_MmFixedStop( p->mmCuts, 0 ); + FREE( p->pInputArrivals ); + FREE( p->pInputs ); + FREE( p->pOutputs ); + FREE( p->pBins ); +// FREE( p->ppOutputNames ); + if ( p->pSimInfo ) + { + FREE( p->pSimInfo[0] ); + FREE( p->pSimInfo ); + } + FREE( p ); +} + + +/**Function************************************************************* + + Synopsis [Prints runtime statistics of the mapping manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_ManPrintTimeStats( Fpga_Man_t * p ) +{ + extern char * pNetName; + extern int TotalLuts; +// FILE * pTable; + + +/* + pTable = fopen( "stats.txt", "a+" ); + fprintf( pTable, "%s ", pNetName ); + fprintf( pTable, "%.0f ", p->fRequiredGlo ); +// fprintf( pTable, "%.0f ", p->fAreaGlo );//+ (float)nOutputInvs ); + fprintf( pTable, "%.0f ", (float)TotalLuts ); + fprintf( pTable, "%4.2f\n", (float)(p->timeTotal-p->timeToMap)/(float)(CLOCKS_PER_SEC) ); + fclose( pTable ); +*/ + +// printf( "N-canonical = %d. Matchings = %d. ", p->nCanons, p->nMatches ); +// printf( "Choice nodes = %d. Choices = %d.\n", p->nChoiceNodes, p->nChoices ); + PRT( "ToMap", p->timeToMap ); + PRT( "Cuts ", p->timeCuts ); + PRT( "Match", p->timeMatch ); + PRT( "Area ", p->timeRecover ); + PRT( "ToNet", p->timeToNet ); + PRT( "TOTAL", p->timeTotal ); + if ( p->time1 ) { PRT( "time1", p->time1 ); } + if ( p->time2 ) { PRT( "time2", p->time2 ); } +} + +/**Function************************************************************* + + Synopsis [Creates a new node.] + + Description [This procedure should be called to create the constant + node and the PI nodes first.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Node_t * Fpga_NodeCreate( Fpga_Man_t * p, Fpga_Node_t * p1, Fpga_Node_t * p2 ) +{ + Fpga_Node_t * pNode; + // create the node + pNode = (Fpga_Node_t *)Extra_MmFixedEntryFetch( p->mmNodes ); + memset( pNode, 0, sizeof(Fpga_Node_t) ); + // set very large required time + pNode->tRequired = FPGA_FLOAT_LARGE; + pNode->aEstFanouts = -1; + pNode->p1 = p1; + pNode->p2 = p2; + // set the number of this node + pNode->Num = p->nNodes++; + // place to store the fanouts +// pNode->vFanouts = Fpga_NodeVecAlloc( 5 ); + // store this node in the internal array + if ( pNode->Num >= 0 ) + Fpga_NodeVecPush( p->vNodesAll, pNode ); + else + pNode->fInv = 1; + // set the level of this node + if ( p1 ) + { + // create the fanout info + Fpga_NodeAddFaninFanout( Fpga_Regular(p1), pNode ); + Fpga_NodeAddFaninFanout( Fpga_Regular(p2), pNode ); + // compute the level + pNode->Level = 1 + FPGA_MAX(Fpga_Regular(p1)->Level, Fpga_Regular(p2)->Level); + pNode->fInv = Fpga_NodeIsSimComplement(p1) & Fpga_NodeIsSimComplement(p2); + } + // reference the inputs (will be used to compute the number of fanouts) + if ( p->fRefCount ) + { + if ( p1 ) Fpga_NodeRef(p1); + if ( p2 ) Fpga_NodeRef(p2); + } + return pNode; +} + +/**Function************************************************************* + + Synopsis [Create the unique table of AND gates.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_TableCreate( Fpga_Man_t * pMan ) +{ + assert( pMan->pBins == NULL ); + pMan->nBins = Cudd_Prime(50000); + pMan->pBins = ALLOC( Fpga_Node_t *, pMan->nBins ); + memset( pMan->pBins, 0, sizeof(Fpga_Node_t *) * pMan->nBins ); + pMan->nNodes = 0; +} + +/**Function************************************************************* + + Synopsis [Looks up the AND2 node in the unique table.] + + Description [This procedure implements one-level hashing. All the nodes + are hashed by their children. If the node with the same children was already + created, it is returned by the call to this procedure. If it does not exist, + this procedure creates a new node with these children. ] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Node_t * Fpga_TableLookup( Fpga_Man_t * pMan, Fpga_Node_t * p1, Fpga_Node_t * p2 ) +{ + Fpga_Node_t * pEnt; + unsigned Key; + + if ( p1 == p2 ) + return p1; + if ( p1 == Fpga_Not(p2) ) + return Fpga_Not(pMan->pConst1); + if ( Fpga_NodeIsConst(p1) ) + { + if ( p1 == pMan->pConst1 ) + return p2; + return Fpga_Not(pMan->pConst1); + } + if ( Fpga_NodeIsConst(p2) ) + { + if ( p2 == pMan->pConst1 ) + return p1; + return Fpga_Not(pMan->pConst1); + } + + if ( Fpga_Regular(p1)->Num > Fpga_Regular(p2)->Num ) + pEnt = p1, p1 = p2, p2 = pEnt; + + Key = Fpga_HashKey2( p1, p2, pMan->nBins ); + for ( pEnt = pMan->pBins[Key]; pEnt; pEnt = pEnt->pNext ) + if ( pEnt->p1 == p1 && pEnt->p2 == p2 ) + return pEnt; + // resize the table + if ( pMan->nNodes >= 2 * pMan->nBins ) + { + Fpga_TableResize( pMan ); + Key = Fpga_HashKey2( p1, p2, pMan->nBins ); + } + // create the new node + pEnt = Fpga_NodeCreate( pMan, p1, p2 ); + // add the node to the corresponding linked list in the table + pEnt->pNext = pMan->pBins[Key]; + pMan->pBins[Key] = pEnt; + return pEnt; +} + + +/**Function************************************************************* + + Synopsis [Resizes the table.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_TableResize( Fpga_Man_t * pMan ) +{ + Fpga_Node_t ** pBinsNew; + Fpga_Node_t * pEnt, * pEnt2; + int nBinsNew, Counter, i, clk; + unsigned Key; + +clk = clock(); + // get the new table size + nBinsNew = Cudd_Prime(2 * pMan->nBins); + // allocate a new array + pBinsNew = ALLOC( Fpga_Node_t *, nBinsNew ); + memset( pBinsNew, 0, sizeof(Fpga_Node_t *) * nBinsNew ); + // rehash the entries from the old table + Counter = 0; + for ( i = 0; i < pMan->nBins; i++ ) + for ( pEnt = pMan->pBins[i], pEnt2 = pEnt? pEnt->pNext: NULL; pEnt; + pEnt = pEnt2, pEnt2 = pEnt? pEnt->pNext: NULL ) + { + Key = Fpga_HashKey2( pEnt->p1, pEnt->p2, nBinsNew ); + pEnt->pNext = pBinsNew[Key]; + pBinsNew[Key] = pEnt; + Counter++; + } + assert( Counter == pMan->nNodes - pMan->nInputs ); + if ( pMan->fVerbose ) + { +// printf( "Increasing the unique table size from %6d to %6d. ", pMan->nBins, nBinsNew ); +// PRT( "Time", clock() - clk ); + } + // replace the table and the parameters + free( pMan->pBins ); + pMan->pBins = pBinsNew; + pMan->nBins = nBinsNew; +} + + + +/**Function************************************************************* + + Synopsis [Elementary AND operation on the AIG.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Node_t * Fpga_NodeAnd( Fpga_Man_t * p, Fpga_Node_t * p1, Fpga_Node_t * p2 ) +{ + Fpga_Node_t * pNode; + pNode = Fpga_TableLookup( p, p1, p2 ); + return pNode; +} + +/**Function************************************************************* + + Synopsis [Elementary OR operation on the AIG.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Node_t * Fpga_NodeOr( Fpga_Man_t * p, Fpga_Node_t * p1, Fpga_Node_t * p2 ) +{ + Fpga_Node_t * pNode; + pNode = Fpga_Not( Fpga_TableLookup( p, Fpga_Not(p1), Fpga_Not(p2) ) ); + return pNode; +} + +/**Function************************************************************* + + Synopsis [Elementary EXOR operation on the AIG.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Node_t * Fpga_NodeExor( Fpga_Man_t * p, Fpga_Node_t * p1, Fpga_Node_t * p2 ) +{ + return Fpga_NodeMux( p, p1, Fpga_Not(p2), p2 ); +} + +/**Function************************************************************* + + Synopsis [Elementary MUX operation on the AIG.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Node_t * Fpga_NodeMux( Fpga_Man_t * p, Fpga_Node_t * pC, Fpga_Node_t * pT, Fpga_Node_t * pE ) +{ + Fpga_Node_t * pAnd1, * pAnd2, * pRes; + pAnd1 = Fpga_TableLookup( p, pC, pT ); + pAnd2 = Fpga_TableLookup( p, Fpga_Not(pC), pE ); + pRes = Fpga_NodeOr( p, pAnd1, pAnd2 ); + return pRes; +} + + +/**Function************************************************************* + + Synopsis [Sets the node to be equivalent to the given one.] + + Description [This procedure is a work-around for the equivalence check. + Does not verify the equivalence. Use at the user's risk.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_NodeSetChoice( Fpga_Man_t * pMan, Fpga_Node_t * pNodeOld, Fpga_Node_t * pNodeNew ) +{ + pNodeNew->pNextE = pNodeOld->pNextE; + pNodeOld->pNextE = pNodeNew; + pNodeNew->pRepr = pNodeOld; +} + + + +/**Function************************************************************* + + Synopsis [Prints some interesting stats.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_ManStats( Fpga_Man_t * p ) +{ + FILE * pTable; + pTable = fopen( "stats.txt", "a+" ); + fprintf( pTable, "%s ", p->pFileName ); + fprintf( pTable, "%4d ", p->nInputs - p->nLatches ); + fprintf( pTable, "%4d ", p->nOutputs - p->nLatches ); + fprintf( pTable, "%4d ", p->nLatches ); + fprintf( pTable, "%7d ", p->vAnds->nSize ); + fprintf( pTable, "%7d ", Fpga_CutCountAll(p) ); + fprintf( pTable, "%2d\n", (int)p->fRequiredGlo ); + fclose( pTable ); +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + diff --git a/src/map/fpga/fpgaCut.c b/src/map/fpga/fpgaCut.c new file mode 100644 index 00000000..27079953 --- /dev/null +++ b/src/map/fpga/fpgaCut.c @@ -0,0 +1,1150 @@ +/**CFile**************************************************************** + + FileName [fpgaCut.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Generic technology mapping engine.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 2.0. Started - August 18, 2004.] + + Revision [$Id: fpgaCut.c,v 1.3 2004/07/06 04:55:57 alanmi Exp $] + +***********************************************************************/ + +#include "fpgaInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +typedef struct Fpga_CutTableStrutct_t Fpga_CutTable_t; +struct Fpga_CutTableStrutct_t +{ + Fpga_Cut_t ** pBins; // the table used for linear probing + int nBins; // the size of the table + int * pCuts; // the array of cuts currently stored + int nCuts; // the number of cuts currently stored + Fpga_Cut_t ** pArray; // the temporary array of cuts + Fpga_Cut_t ** pCuts1; // the temporary array of cuts + Fpga_Cut_t ** pCuts2; // the temporary array of cuts +}; + +// the largest number of cuts considered +#define FPGA_CUTS_MAX_COMPUTE 500 +// the largest number of cuts used +#define FPGA_CUTS_MAX_USE 200 + +// primes used to compute the hash key +static int s_HashPrimes[10] = { 109, 499, 557, 619, 631, 709, 797, 881, 907, 991 }; + +static int bit_count[256] = { + 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5, + 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, + 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, + 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, + 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, + 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, + 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, + 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8 +}; + +#define FPGA_COUNT_ONES(u) (bit_count[(u)&255]+bit_count[((u)>>8)&255]+bit_count[((u)>>16)&255]+bit_count[(u)>>24]) + +static Fpga_Cut_t * Fpga_CutCompute( Fpga_Man_t * p, Fpga_CutTable_t * pTable, Fpga_Node_t * pNode ); +static void Fpga_CutFilter( Fpga_Man_t * p, Fpga_Node_t * pNode ); +static Fpga_Cut_t * Fpga_CutMergeLists( Fpga_Man_t * p, Fpga_CutTable_t * pTable, Fpga_Cut_t * pList1, Fpga_Cut_t * pList2, int fComp1, int fComp2, int fPivot1, int fPivot2 ); +static int Fpga_CutMergeTwo( Fpga_Cut_t * pCut1, Fpga_Cut_t * pCut2, Fpga_Node_t * ppNodes[], int nNodesMax ); +static Fpga_Cut_t * Fpga_CutUnionLists( Fpga_Cut_t * pList1, Fpga_Cut_t * pList2 ); +static int Fpga_CutBelongsToList( Fpga_Cut_t * pList, Fpga_Node_t * ppNodes[], int nNodes ); +extern Fpga_Cut_t * Fpga_CutAlloc( Fpga_Man_t * p ); +extern int Fpga_CutCountAll( Fpga_Man_t * pMan ); + +static void Fpga_CutListPrint( Fpga_Man_t * pMan, Fpga_Node_t * pRoot ); +static void Fpga_CutListPrint2( Fpga_Man_t * pMan, Fpga_Node_t * pRoot ); +static void Fpga_CutPrint_( Fpga_Man_t * pMan, Fpga_Cut_t * pCut, Fpga_Node_t * pRoot ); + +static Fpga_CutTable_t * Fpga_CutTableStart( Fpga_Man_t * pMan ); +static void Fpga_CutTableStop( Fpga_CutTable_t * p ); +static unsigned Fpga_CutTableHash( Fpga_Node_t * ppNodes[], int nNodes ); +static int Fpga_CutTableLookup( Fpga_CutTable_t * p, Fpga_Node_t * ppNodes[], int nNodes ); +static Fpga_Cut_t * Fpga_CutTableConsider( Fpga_Man_t * pMan, Fpga_CutTable_t * p, Fpga_Node_t * ppNodes[], int nNodes ); +static void Fpga_CutTableRestart( Fpga_CutTable_t * p ); + +static int Fpga_CutSortCutsCompare( Fpga_Cut_t ** pC1, Fpga_Cut_t ** pC2 ); +static Fpga_Cut_t * Fpga_CutSortCuts( Fpga_Man_t * pMan, Fpga_CutTable_t * p, Fpga_Cut_t * pList ); +static int Fpga_CutList2Array( Fpga_Cut_t ** pArray, Fpga_Cut_t * pList ); +static Fpga_Cut_t * Fpga_CutArray2List( Fpga_Cut_t ** pArray, int nCuts ); + + +// iterator through all the cuts of the list +#define Fpga_ListForEachCut( pList, pCut ) \ + for ( pCut = pList; \ + pCut; \ + pCut = pCut->pNext ) +#define Fpga_ListForEachCutSafe( pList, pCut, pCut2 ) \ + for ( pCut = pList, \ + pCut2 = pCut? pCut->pNext: NULL; \ + pCut; \ + pCut = pCut2, \ + pCut2 = pCut? pCut->pNext: NULL ) + + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Computes the cuts for each node in the object graph.] + + Description [The cuts are computed in one sweep over the mapping graph. + First, the elementary cuts, which include the node itself, are assigned + to the PI nodes. The internal nodes are considered in the DFS order. + Each node is two-input AND-gate. So to compute the cuts at a node, we + need to merge the sets of cuts of its two predecessors. The merged set + contains only unique cuts with the number of inputs equal to k or less. + Finally, the elementary cut, composed of the node itself, is added to + the set of cuts for the node. + + This procedure is pretty fast for 5-feasible cuts, but it dramatically + slows down on some "dense" networks when computing 6-feasible cuts. + The problem is that there are too many cuts in this case. We should + think how to heuristically trim the number of cuts in such cases, + to have reasonable runtime.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_MappingCuts( Fpga_Man_t * p ) +{ + ProgressBar * pProgress; + Fpga_CutTable_t * pTable; + Fpga_Node_t * pNode; + int nCuts, nNodes, i; + + // set the elementary cuts for the PI variables + assert( p->nVarsMax > 1 && p->nVarsMax < 7 ); + Fpga_MappingCreatePiCuts( p ); + + // compute the cuts for the internal nodes + nNodes = p->vAnds->nSize; + pProgress = Extra_ProgressBarStart( stdout, nNodes ); + pTable = Fpga_CutTableStart( p ); + for ( i = 0; i < nNodes; i++ ) + { + Extra_ProgressBarUpdate( pProgress, i, "Cuts ..." ); + pNode = p->vAnds->pArray[i]; + if ( !Fpga_NodeIsAnd( pNode ) ) + continue; + Fpga_CutCompute( p, pTable, pNode ); + } + Extra_ProgressBarStop( pProgress ); + Fpga_CutTableStop( pTable ); + + // report the stats + if ( p->fVerbose ) + { + nCuts = Fpga_CutCountAll(p); + printf( "Nodes = %6d. Total %d-feasible cuts = %d. Cuts per node = %.1f.\n", + p->nNodes, p->nVarsMax, nCuts, ((float)nCuts)/p->nNodes ); + } + + // print the cuts for the first primary output +// Fpga_CutListPrint( p, Fpga_Regular(p->pOutputs[0]) ); +} + +/**Function************************************************************* + + Synopsis [Performs technology mapping for variable-size-LUTs.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_MappingCreatePiCuts( Fpga_Man_t * p ) +{ + Fpga_Cut_t * pCut; + int i; + + // set the elementary cuts for the PI variables + for ( i = 0; i < p->nInputs; i++ ) + { + pCut = Fpga_CutAlloc( p ); + pCut->nLeaves = 1; + pCut->ppLeaves[0] = p->pInputs[i]; + pCut->uSign = (1 << (i%31)); + p->pInputs[i]->pCuts = pCut; + p->pInputs[i]->pCutBest = pCut; + // set the input arrival times +// p->pInputs[i]->pCut[1]->tArrival = p->pInputArrivals[i]; + } +} + +/**Function************************************************************* + + Synopsis [Computes the cuts for one node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Cut_t * Fpga_CutCompute( Fpga_Man_t * p, Fpga_CutTable_t * pTable, Fpga_Node_t * pNode ) +{ + Fpga_Node_t * pTemp; + Fpga_Cut_t * pList, * pList1, * pList2; + Fpga_Cut_t * pCut; + int fPivot1 = p->fTree && (Fpga_NodeReadRef(pNode->p1)>2); + int fPivot2 = p->fTree && (Fpga_NodeReadRef(pNode->p2)>2); + + // if the cuts are computed return them + if ( pNode->pCuts ) + return pNode->pCuts; + + // compute the cuts for the children + pList1 = Fpga_Regular(pNode->p1)->pCuts; + pList2 = Fpga_Regular(pNode->p2)->pCuts; + // merge the lists + pList = Fpga_CutMergeLists( p, pTable, pList1, pList2, + Fpga_IsComplement(pNode->p1), Fpga_IsComplement(pNode->p2), + fPivot1, fPivot2 ); + // if there are functionally equivalent nodes, union them with this list + assert( pList ); + // only add to the list of cuts if the node is a representative one + if ( pNode->pRepr == NULL ) + { + for ( pTemp = pNode->pNextE; pTemp; pTemp = pTemp->pNextE ) + { + assert( pTemp->pCuts ); + pList = Fpga_CutUnionLists( pList, pTemp->pCuts ); + assert( pTemp->pCuts ); + pList = Fpga_CutSortCuts( p, pTable, pList ); + } + } + // add the new cut + pCut = Fpga_CutAlloc( p ); + pCut->nLeaves = 1; + pCut->ppLeaves[0] = pNode; + pCut->uSign = (1 << (pNode->Num%31)); + pCut->fLevel = (float)pCut->ppLeaves[0]->Level; + // append (it is important that the elementary cut is appended first) + pCut->pNext = pList; + // set at the node + pNode->pCuts = pCut; + // remove the dominated cuts + Fpga_CutFilter( p, pNode ); + // set the phase correctly + if ( pNode->pRepr && Fpga_NodeComparePhase(pNode, pNode->pRepr) ) + { + Fpga_ListForEachCut( pNode->pCuts, pCut ) + pCut->Phase = 1; + } + + +/* + { + Fpga_Cut_t * pPrev; + int i, Counter = 0; + for ( pCut = pNode->pCuts->pNext, pPrev = pNode->pCuts; pCut; pCut = pCut->pNext ) + { + for ( i = 0; i < pCut->nLeaves; i++ ) + if ( pCut->ppLeaves[i]->Level >= pNode->Level ) + break; + if ( i != pCut->nLeaves ) + pPrev->pNext = pCut->pNext; + else + pPrev = pCut; + } + } + { + int i, Counter = 0;; + for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext ) + for ( i = 0; i < pCut->nLeaves; i++ ) + Counter += (pCut->ppLeaves[i]->Level >= pNode->Level); + if ( Counter ) + printf( " %d", Counter ); + } +*/ + + return pCut; +} + +/**Function************************************************************* + + Synopsis [Filter the cuts using dominance.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_CutFilter( Fpga_Man_t * p, Fpga_Node_t * pNode ) +{ + Fpga_Cut_t * pTemp, * pPrev, * pCut, * pCut2; + int i, k, Counter; + + Counter = 0; + pPrev = pNode->pCuts; + Fpga_ListForEachCutSafe( pNode->pCuts->pNext, pCut, pCut2 ) + { + // go through all the previous cuts up to pCut + for ( pTemp = pNode->pCuts->pNext; pTemp != pCut; pTemp = pTemp->pNext ) + { + // check if every node in pTemp is contained in pCut + for ( i = 0; i < pTemp->nLeaves; i++ ) + { + for ( k = 0; k < pCut->nLeaves; k++ ) + if ( pTemp->ppLeaves[i] == pCut->ppLeaves[k] ) + break; + if ( k == pCut->nLeaves ) // node i in pTemp is not contained in pCut + break; + } + if ( i == pTemp->nLeaves ) // every node in pTemp is contained in pCut + { + Counter++; + break; + } + } + if ( pTemp != pCut ) // pTemp contain pCut + { + pPrev->pNext = pCut->pNext; // skip pCut + // recycle pCut + Fpga_CutFree( p, pCut ); + } + else + pPrev = pCut; + } +// printf( "Dominated = %3d. \n", Counter ); +} + + +/**Function************************************************************* + + Synopsis [Merges two lists of cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Cut_t * Fpga_CutMergeLists( Fpga_Man_t * p, Fpga_CutTable_t * pTable, + Fpga_Cut_t * pList1, Fpga_Cut_t * pList2, int fComp1, int fComp2, int fPivot1, int fPivot2 ) +{ + Fpga_Node_t * ppNodes[6]; + Fpga_Cut_t * pListNew, ** ppListNew, * pLists[7] = { NULL }; + Fpga_Cut_t * pCut, * pPrev, * pTemp1, * pTemp2; + int nNodes, Counter, i; + Fpga_Cut_t ** ppArray1, ** ppArray2, ** ppArray3; + int nCuts1, nCuts2, nCuts3, k, fComp3; + + ppArray1 = pTable->pCuts1; + ppArray2 = pTable->pCuts2; + nCuts1 = Fpga_CutList2Array( ppArray1, pList1 ); + nCuts2 = Fpga_CutList2Array( ppArray2, pList2 ); + if ( fPivot1 ) + nCuts1 = 1; + if ( fPivot2 ) + nCuts2 = 1; + // swap the lists based on their length + if ( nCuts1 > nCuts2 ) + { + ppArray3 = ppArray1; + ppArray1 = ppArray2; + ppArray2 = ppArray3; + + nCuts3 = nCuts1; + nCuts1 = nCuts2; + nCuts2 = nCuts3; + + fComp3 = fComp1; + fComp1 = fComp2; + fComp2 = fComp3; + } + // pList1 is shorter or equal length compared to pList2 + + // prepare the manager for the cut computation + Fpga_CutTableRestart( pTable ); + // go through the cut pairs + Counter = 0; +// for ( pTemp1 = pList1; pTemp1; pTemp1 = fPivot1? NULL: pTemp1->pNext ) +// for ( pTemp2 = pList2; pTemp2; pTemp2 = fPivot2? NULL: pTemp2->pNext ) + for ( i = 0; i < nCuts1; i++ ) + { + for ( k = 0; k <= i; k++ ) + { + pTemp1 = ppArray1[i]; + pTemp2 = ppArray2[k]; + + if ( pTemp1->nLeaves == p->nVarsMax && pTemp2->nLeaves == p->nVarsMax ) + { + if ( pTemp1->ppLeaves[0] != pTemp2->ppLeaves[0] ) + continue; + if ( pTemp1->ppLeaves[1] != pTemp2->ppLeaves[1] ) + continue; + } + + // check if k-feasible cut exists + nNodes = Fpga_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax ); + if ( nNodes == 0 ) + continue; + // consider the cut for possible addition to the set of new cuts + pCut = Fpga_CutTableConsider( p, pTable, ppNodes, nNodes ); + if ( pCut == NULL ) + continue; + // add data to the cut + pCut->pOne = Fpga_CutNotCond( pTemp1, fComp1 ); + pCut->pTwo = Fpga_CutNotCond( pTemp2, fComp2 ); + // create the signature + pCut->uSign = pTemp1->uSign | pTemp2->uSign; + // add it to the corresponding list + pCut->pNext = pLists[pCut->nLeaves]; + pLists[pCut->nLeaves] = pCut; + // count this cut and quit if limit is reached + Counter++; + if ( Counter == FPGA_CUTS_MAX_COMPUTE ) + goto QUITS; + } + for ( k = 0; k < i; k++ ) + { + pTemp1 = ppArray1[k]; + pTemp2 = ppArray2[i]; + + if ( pTemp1->nLeaves == p->nVarsMax && pTemp2->nLeaves == p->nVarsMax ) + { + if ( pTemp1->ppLeaves[0] != pTemp2->ppLeaves[0] ) + continue; + if ( pTemp1->ppLeaves[1] != pTemp2->ppLeaves[1] ) + continue; + } + + + // check if k-feasible cut exists + nNodes = Fpga_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax ); + if ( nNodes == 0 ) + continue; + // consider the cut for possible addition to the set of new cuts + pCut = Fpga_CutTableConsider( p, pTable, ppNodes, nNodes ); + if ( pCut == NULL ) + continue; + // add data to the cut + pCut->pOne = Fpga_CutNotCond( pTemp1, fComp1 ); + pCut->pTwo = Fpga_CutNotCond( pTemp2, fComp2 ); + // create the signature + pCut->uSign = pTemp1->uSign | pTemp2->uSign; + // add it to the corresponding list + pCut->pNext = pLists[pCut->nLeaves]; + pLists[pCut->nLeaves] = pCut; + // count this cut and quit if limit is reached + Counter++; + if ( Counter == FPGA_CUTS_MAX_COMPUTE ) + goto QUITS; + } + } + // consider the rest of them + for ( i = nCuts1; i < nCuts2; i++ ) + for ( k = 0; k < nCuts1; k++ ) + { + pTemp1 = ppArray1[k]; + pTemp2 = ppArray2[i]; + + if ( pTemp1->nLeaves == p->nVarsMax && pTemp2->nLeaves == p->nVarsMax ) + { + if ( pTemp1->ppLeaves[0] != pTemp2->ppLeaves[0] ) + continue; + if ( pTemp1->ppLeaves[1] != pTemp2->ppLeaves[1] ) + continue; + if ( pTemp1->ppLeaves[2] != pTemp2->ppLeaves[2] ) + continue; + } + + + // check if k-feasible cut exists + nNodes = Fpga_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax ); + if ( nNodes == 0 ) + continue; + // consider the cut for possible addition to the set of new cuts + pCut = Fpga_CutTableConsider( p, pTable, ppNodes, nNodes ); + if ( pCut == NULL ) + continue; + // add data to the cut + pCut->pOne = Fpga_CutNotCond( pTemp1, fComp1 ); + pCut->pTwo = Fpga_CutNotCond( pTemp2, fComp2 ); + // create the signature + pCut->uSign = pTemp1->uSign | pTemp2->uSign; + // add it to the corresponding list + pCut->pNext = pLists[pCut->nLeaves]; + pLists[pCut->nLeaves] = pCut; + // count this cut and quit if limit is reached + Counter++; + if ( Counter == FPGA_CUTS_MAX_COMPUTE ) + goto QUITS; + } +QUITS : + // combine all the lists into one + pListNew = NULL; + ppListNew = &pListNew; + for ( i = 1; i <= p->nVarsMax; i++ ) + { + if ( pLists[i] == NULL ) + continue; + // find the last entry + for ( pPrev = pLists[i], pCut = pPrev->pNext; pCut; + pPrev = pCut, pCut = pCut->pNext ); + // connect these lists + *ppListNew = pLists[i]; + ppListNew = &pPrev->pNext; + } + *ppListNew = NULL; + // sort the cuts by arrival times and use only the first FPGA_CUTS_MAX_USE + pListNew = Fpga_CutSortCuts( p, pTable, pListNew ); + return pListNew; +} + + +/**Function************************************************************* + + Synopsis [Merges two lists of cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Cut_t * Fpga_CutMergeLists2( Fpga_Man_t * p, Fpga_CutTable_t * pTable, + Fpga_Cut_t * pList1, Fpga_Cut_t * pList2, int fComp1, int fComp2, int fPivot1, int fPivot2 ) +{ + Fpga_Node_t * ppNodes[6]; + Fpga_Cut_t * pListNew, ** ppListNew, * pLists[7] = { NULL }; + Fpga_Cut_t * pCut, * pPrev, * pTemp1, * pTemp2; + int nNodes, Counter, i; + + // prepare the manager for the cut computation + Fpga_CutTableRestart( pTable ); + // go through the cut pairs + Counter = 0; + for ( pTemp1 = pList1; pTemp1; pTemp1 = fPivot1? NULL: pTemp1->pNext ) + for ( pTemp2 = pList2; pTemp2; pTemp2 = fPivot2? NULL: pTemp2->pNext ) + { + // check if k-feasible cut exists + nNodes = Fpga_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax ); + if ( nNodes == 0 ) + continue; + // consider the cut for possible addition to the set of new cuts + pCut = Fpga_CutTableConsider( p, pTable, ppNodes, nNodes ); + if ( pCut == NULL ) + continue; + // add data to the cut + pCut->pOne = Fpga_CutNotCond( pTemp1, fComp1 ); + pCut->pTwo = Fpga_CutNotCond( pTemp2, fComp2 ); + // add it to the corresponding list + pCut->pNext = pLists[pCut->nLeaves]; + pLists[pCut->nLeaves] = pCut; + // count this cut and quit if limit is reached + Counter++; + if ( Counter == FPGA_CUTS_MAX_COMPUTE ) + goto QUITS; + } +QUITS : + // combine all the lists into one + pListNew = NULL; + ppListNew = &pListNew; + for ( i = 1; i <= p->nVarsMax; i++ ) + { + if ( pLists[i] == NULL ) + continue; + // find the last entry + for ( pPrev = pLists[i], pCut = pPrev->pNext; pCut; + pPrev = pCut, pCut = pCut->pNext ); + // connect these lists + *ppListNew = pLists[i]; + ppListNew = &pPrev->pNext; + } + *ppListNew = NULL; + // sort the cuts by arrival times and use only the first FPGA_CUTS_MAX_USE + pListNew = Fpga_CutSortCuts( p, pTable, pListNew ); + return pListNew; +} + +/**Function************************************************************* + + Synopsis [Merges two cuts.] + + Description [Returns the number of nodes in the resulting cut, or 0 if the + cut is infeasible. Returns the resulting nodes in the array ppNodes[].] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_CutMergeTwo( Fpga_Cut_t * pCut1, Fpga_Cut_t * pCut2, Fpga_Node_t * ppNodes[], int nNodesMax ) +{ + Fpga_Node_t * pNodeTemp; + int nTotal, i, k, min, Counter; + unsigned uSign; + + // use quick prefiltering + uSign = pCut1->uSign | pCut2->uSign; + Counter = FPGA_COUNT_ONES(uSign); + if ( Counter > nNodesMax ) + return 0; +/* + // check the special case when at least of the cuts is the largest + if ( pCut1->nLeaves == nNodesMax ) + { + if ( pCut2->nLeaves == nNodesMax ) + { + // return 0 if the cuts are different + for ( i = 0; i < nNodesMax; i++ ) + if ( pCut1->ppLeaves[i] != pCut2->ppLeaves[i] ) + return 0; + // return nNodesMax if they are the same + for ( i = 0; i < nNodesMax; i++ ) + ppNodes[i] = pCut1->ppLeaves[i]; + return nNodesMax; + } + else if ( pCut2->nLeaves == nNodesMax - 1 ) + { + // return 0 if the cuts are different + fMismatch = 0; + for ( i = 0; i < nNodesMax; i++ ) + if ( pCut1->ppLeaves[i] != pCut2->ppLeaves[i - fMismatch] ) + { + if ( fMismatch == 1 ) + return 0; + fMismatch = 1; + } + // return nNodesMax if they are the same + for ( i = 0; i < nNodesMax; i++ ) + ppNodes[i] = pCut1->ppLeaves[i]; + return nNodesMax; + } + } + else if ( pCut1->nLeaves == nNodesMax - 1 && pCut2->nLeaves == nNodesMax ) + { + // return 0 if the cuts are different + fMismatch = 0; + for ( i = 0; i < nNodesMax; i++ ) + if ( pCut1->ppLeaves[i - fMismatch] != pCut2->ppLeaves[i] ) + { + if ( fMismatch == 1 ) + return 0; + fMismatch = 1; + } + // return nNodesMax if they are the same + for ( i = 0; i < nNodesMax; i++ ) + ppNodes[i] = pCut2->ppLeaves[i]; + return nNodesMax; + } +*/ + // count the number of unique entries in pCut2 + nTotal = pCut1->nLeaves; + for ( i = 0; i < pCut2->nLeaves; i++ ) + { + // try to find this entry among the leaves of pCut1 + for ( k = 0; k < pCut1->nLeaves; k++ ) + if ( pCut2->ppLeaves[i] == pCut1->ppLeaves[k] ) + break; + if ( k < pCut1->nLeaves ) // found + continue; + // we found a new entry to add + if ( nTotal == nNodesMax ) + return 0; + ppNodes[nTotal++] = pCut2->ppLeaves[i]; + } + // we know that the feasible cut exists + + // add the starting entries + for ( k = 0; k < pCut1->nLeaves; k++ ) + ppNodes[k] = pCut1->ppLeaves[k]; + + // selection-sort the entries + for ( i = 0; i < nTotal - 1; i++ ) + { + min = i; + for ( k = i+1; k < nTotal; k++ ) + if ( ppNodes[k] < ppNodes[min] ) + min = k; + pNodeTemp = ppNodes[i]; + ppNodes[i] = ppNodes[min]; + ppNodes[min] = pNodeTemp; + } + + return nTotal; +} + +/**Function************************************************************* + + Synopsis [Computes the union of the two lists of cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Cut_t * Fpga_CutUnionLists( Fpga_Cut_t * pList1, Fpga_Cut_t * pList2 ) +{ + Fpga_Cut_t * pTemp, * pRoot; + // find the last cut in the first list + pRoot = pList1; + Fpga_ListForEachCut( pList1, pTemp ) + pRoot = pTemp; + // attach the non-trival part of the second cut to the end of the first + assert( pRoot->pNext == NULL ); + pRoot->pNext = pList2->pNext; + pList2->pNext = NULL; + return pList1; +} + + +/**Function************************************************************* + + Synopsis [Checks whether the given cut belongs to the list.] + + Description [This procedure takes most of the runtime in the cut + computation.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_CutBelongsToList( Fpga_Cut_t * pList, Fpga_Node_t * ppNodes[], int nNodes ) +{ + Fpga_Cut_t * pTemp; + int i; + for ( pTemp = pList; pTemp; pTemp = pTemp->pNext ) + { + for ( i = 0; i < nNodes; i++ ) + if ( pTemp->ppLeaves[i] != ppNodes[i] ) + break; + if ( i == nNodes ) + return 1; + } + return 0; +} + +/**Function************************************************************* + + Synopsis [Counts all the cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_CutCountAll( Fpga_Man_t * pMan ) +{ + Fpga_Node_t * pNode; + Fpga_Cut_t * pCut; + int i, nCuts; + // go through all the nodes in the unique table of the manager + nCuts = 0; + for ( i = 0; i < pMan->nBins; i++ ) + for ( pNode = pMan->pBins[i]; pNode; pNode = pNode->pNext ) + for ( pCut = pNode->pCuts; pCut; pCut = pCut->pNext ) + if ( pCut->nLeaves > 1 ) // skip the elementary cuts + nCuts++; + return nCuts; +} + + +/**Function************************************************************* + + Synopsis [Clean the signatures.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_CutsCleanSign( Fpga_Man_t * pMan ) +{ + Fpga_Node_t * pNode; + Fpga_Cut_t * pCut; + int i; + for ( i = 0; i < pMan->nBins; i++ ) + for ( pNode = pMan->pBins[i]; pNode; pNode = pNode->pNext ) + for ( pCut = pNode->pCuts; pCut; pCut = pCut->pNext ) + pCut->uSign = 0; +} + + + +/**Function************************************************************* + + Synopsis [Prints the cuts in the list.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_CutListPrint( Fpga_Man_t * pMan, Fpga_Node_t * pRoot ) +{ + Fpga_Cut_t * pTemp; + int Counter; + for ( Counter = 0, pTemp = pRoot->pCuts; pTemp; pTemp = pTemp->pNext, Counter++ ) + { + printf( "%2d : ", Counter + 1 ); + Fpga_CutPrint_( pMan, pTemp, pRoot ); + } +} + +/**Function************************************************************* + + Synopsis [Prints the cuts in the list.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_CutListPrint2( Fpga_Man_t * pMan, Fpga_Node_t * pRoot ) +{ + Fpga_Cut_t * pTemp; + int Counter; + for ( Counter = 0, pTemp = pRoot->pCuts; pTemp; pTemp = pTemp->pNext, Counter++ ) + { + printf( "%2d : ", Counter + 1 ); + Fpga_CutPrint_( pMan, pTemp, pRoot ); + } +} + +/**Function************************************************************* + + Synopsis [Prints the cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_CutPrint_( Fpga_Man_t * pMan, Fpga_Cut_t * pCut, Fpga_Node_t * pRoot ) +{ + int i; + printf( "(%3d) {", pRoot->Num ); + for ( i = 0; i < pMan->nVarsMax; i++ ) + if ( pCut->ppLeaves[i] ) + printf( " %3d", pCut->ppLeaves[i]->Num ); + printf( " }\n" ); +} + + + + + + + + +/**Function************************************************************* + + Synopsis [Starts the hash table to canonicize cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_CutTable_t * Fpga_CutTableStart( Fpga_Man_t * pMan ) +{ + Fpga_CutTable_t * p; + // allocate the table + p = ALLOC( Fpga_CutTable_t, 1 ); + memset( p, 0, sizeof(Fpga_CutTable_t) ); + p->nBins = Cudd_Prime( 10 * FPGA_CUTS_MAX_COMPUTE ); + p->pBins = ALLOC( Fpga_Cut_t *, p->nBins ); + memset( p->pBins, 0, sizeof(Fpga_Cut_t *) * p->nBins ); + p->pCuts = ALLOC( int, 2 * FPGA_CUTS_MAX_COMPUTE ); + p->pArray = ALLOC( Fpga_Cut_t *, 2 * FPGA_CUTS_MAX_COMPUTE ); + p->pCuts1 = ALLOC( Fpga_Cut_t *, 2 * FPGA_CUTS_MAX_COMPUTE ); + p->pCuts2 = ALLOC( Fpga_Cut_t *, 2 * FPGA_CUTS_MAX_COMPUTE ); + return p; +} + +/**Function************************************************************* + + Synopsis [Stops the hash table.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_CutTableStop( Fpga_CutTable_t * p ) +{ + free( p->pCuts1 ); + free( p->pCuts2 ); + free( p->pArray ); + free( p->pBins ); + free( p->pCuts ); + free( p ); +} + +/**Function************************************************************* + + Synopsis [Computes the hash value of the cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +unsigned Fpga_CutTableHash( Fpga_Node_t * ppNodes[], int nNodes ) +{ + unsigned uRes; + int i; + uRes = 0; + for ( i = 0; i < nNodes; i++ ) + uRes += s_HashPrimes[i] * ppNodes[i]->Num; + return uRes; +} + +/**Function************************************************************* + + Synopsis [Looks up the table for the available cut.] + + Description [Returns -1 if the same cut is found. Returns the index + of the cell where the cut should be added, if it does not exist.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_CutTableLookup( Fpga_CutTable_t * p, Fpga_Node_t * ppNodes[], int nNodes ) +{ + Fpga_Cut_t * pCut; + unsigned Key; + int b, i; + + Key = Fpga_CutTableHash(ppNodes, nNodes) % p->nBins; + for ( b = Key; p->pBins[b]; b = (b+1) % p->nBins ) + { + pCut = p->pBins[b]; + if ( pCut->nLeaves != nNodes ) + continue; + for ( i = 0; i < nNodes; i++ ) + if ( pCut->ppLeaves[i] != ppNodes[i] ) + break; + if ( i == nNodes ) + return -1; + } + return b; +} + + +/**Function************************************************************* + + Synopsis [Starts the hash table to canonicize cuts.] + + Description [Considers addition of the cut to the hash table.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Cut_t * Fpga_CutTableConsider( Fpga_Man_t * pMan, Fpga_CutTable_t * p, Fpga_Node_t * ppNodes[], int nNodes ) +{ + Fpga_Cut_t * pCut; + int Place, i; + // check the cut + Place = Fpga_CutTableLookup( p, ppNodes, nNodes ); + if ( Place == -1 ) + return NULL; + assert( nNodes > 0 ); + // create the new cut + pCut = Fpga_CutAlloc( pMan ); + pCut->nLeaves = nNodes; + pCut->fLevel = 0.0; + for ( i = 0; i < nNodes; i++ ) + { + pCut->ppLeaves[i] = ppNodes[i]; + pCut->fLevel += ppNodes[i]->Level; + } + pCut->fLevel /= nNodes; + // add the cut to the table + assert( p->pBins[Place] == NULL ); + p->pBins[Place] = pCut; + // add the cut to the new list + p->pCuts[ p->nCuts++ ] = Place; + return pCut; +} + +/**Function************************************************************* + + Synopsis [Prepares the table to be used with other cuts.] + + Description [Restarts the table by cleaning the info about cuts stored + when the previous node was considered.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_CutTableRestart( Fpga_CutTable_t * p ) +{ + int i; + for ( i = 0; i < p->nCuts; i++ ) + { + assert( p->pBins[ p->pCuts[i] ] ); + p->pBins[ p->pCuts[i] ] = NULL; + } + p->nCuts = 0; +} + + + +/**Function************************************************************* + + Synopsis [Compares the cuts by the number of leaves and then by delay.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_CutSortCutsCompare( Fpga_Cut_t ** pC1, Fpga_Cut_t ** pC2 ) +{ + if ( (*pC1)->nLeaves < (*pC2)->nLeaves ) + return -1; + if ( (*pC1)->nLeaves > (*pC2)->nLeaves ) + return 1; +/* + if ( (*pC1)->fLevel > (*pC2)->fLevel ) + return -1; + if ( (*pC1)->fLevel < (*pC2)->fLevel ) + return 1; +*/ + return 0; +} + +/**Function************************************************************* + + Synopsis [Sorts the cuts by average arrival time.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Cut_t * Fpga_CutSortCuts( Fpga_Man_t * pMan, Fpga_CutTable_t * p, Fpga_Cut_t * pList ) +{ + Fpga_Cut_t * pListNew; + int nCuts, i; + // move the cuts from the list into the array + nCuts = Fpga_CutList2Array( p->pCuts1, pList ); + assert( nCuts <= FPGA_CUTS_MAX_COMPUTE ); + // sort the cuts + qsort( (void *)p->pCuts1, nCuts, sizeof(Fpga_Cut_t *), + (int (*)(const void *, const void *)) Fpga_CutSortCutsCompare ); + // move them back into the list + if ( nCuts > FPGA_CUTS_MAX_USE - 1 ) + { +// printf( "*" ); + // free the remaining cuts + for ( i = FPGA_CUTS_MAX_USE - 1; i < nCuts; i++ ) + Extra_MmFixedEntryRecycle( pMan->mmCuts, (char *)p->pCuts1[i] ); + // update the number of cuts + nCuts = FPGA_CUTS_MAX_USE - 1; + } + pListNew = Fpga_CutArray2List( p->pCuts1, nCuts ); + return pListNew; +} + +/**Function************************************************************* + + Synopsis [Moves the nodes from the list into the array.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_CutList2Array( Fpga_Cut_t ** pArray, Fpga_Cut_t * pList ) +{ + int i; + for ( i = 0; pList; pList = pList->pNext, i++ ) + pArray[i] = pList; + return i; +} + +/**Function************************************************************* + + Synopsis [Moves the nodes from the array into the list.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Cut_t * Fpga_CutArray2List( Fpga_Cut_t ** pArray, int nCuts ) +{ + Fpga_Cut_t * pListNew, ** ppListNew; + int i; + pListNew = NULL; + ppListNew = &pListNew; + for ( i = 0; i < nCuts; i++ ) + { + // connect these lists + *ppListNew = pArray[i]; + ppListNew = &pArray[i]->pNext; +//printf( " %d(%.2f)", pArray[i]->nLeaves, pArray[i]->fLevel ); + } +//printf( "\n" ); + + *ppListNew = NULL; + return pListNew; +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + diff --git a/src/map/fpga/fpgaCutUtils.c b/src/map/fpga/fpgaCutUtils.c new file mode 100644 index 00000000..abe703a2 --- /dev/null +++ b/src/map/fpga/fpgaCutUtils.c @@ -0,0 +1,571 @@ +/**CFile**************************************************************** + + FileName [fpgaCutUtils.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Generic technology mapping engine.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 2.0. Started - August 18, 2004.] + + Revision [$Id: fpgaCutUtils.h,v 1.0 2003/09/08 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "fpgaInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Allocates the cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Cut_t * Fpga_CutAlloc( Fpga_Man_t * p ) +{ + Fpga_Cut_t * pCut; + pCut = (Fpga_Cut_t *)Extra_MmFixedEntryFetch( p->mmCuts ); + memset( pCut, 0, sizeof(Fpga_Cut_t) ); + return pCut; +} + +/**Function************************************************************* + + Synopsis [Duplicates the cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Cut_t * Fpga_CutDup( Fpga_Man_t * p, Fpga_Cut_t * pCutOld ) +{ + Fpga_Cut_t * pCutNew; + int i; + pCutNew = Fpga_CutAlloc( p ); + pCutNew->pRoot = pCutOld->pRoot; + pCutNew->nLeaves = pCutOld->nLeaves; + for ( i = 0; i < pCutOld->nLeaves; i++ ) + pCutNew->ppLeaves[i] = pCutOld->ppLeaves[i]; + return pCutNew; +} + +/**Function************************************************************* + + Synopsis [Deallocates the cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_CutFree( Fpga_Man_t * p, Fpga_Cut_t * pCut ) +{ + if ( pCut ) + Extra_MmFixedEntryRecycle( p->mmCuts, (char *)pCut ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_CutPrint( Fpga_Man_t * p, Fpga_Node_t * pRoot, Fpga_Cut_t * pCut ) +{ + int i; + printf( "CUT: Delay = %4.2f. Area = %4.2f. Nodes = %d -> {", + pCut->tArrival, pCut->aFlow, pRoot->Num ); + for ( i = 0; i < pCut->nLeaves; i++ ) + printf( " %d", pCut->ppLeaves[i]->Num ); + printf( " } \n" ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Cut_t * Fpga_CutCreateSimple( Fpga_Man_t * p, Fpga_Node_t * pNode ) +{ + Fpga_Cut_t * pCut; + pCut = Fpga_CutAlloc( p ); + pCut->pRoot = pNode; + pCut->nLeaves = 1; + pCut->ppLeaves[0] = pNode; + pCut->uSign = FPGA_SEQ_SIGN(pCut->ppLeaves[0]); + return pCut; +} + + +/**function************************************************************* + + synopsis [Computes the exact area associated with the cut.] + + description [] + + sideeffects [] + + seealso [] + +***********************************************************************/ +float Fpga_CutGetRootArea( Fpga_Man_t * p, Fpga_Cut_t * pCut ) +{ + return p->pLutLib->pLutAreas[pCut->nLeaves]; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Cut_t * Fpga_CutListAppend( Fpga_Cut_t * pSetAll, Fpga_Cut_t * pSets ) +{ + Fpga_Cut_t * pPrev, * pTemp; + if ( pSetAll == NULL ) + return pSets; + if ( pSets == NULL ) + return pSetAll; + // find the last one + for ( pTemp = pSets; pTemp; pTemp = pTemp->pNext ) + pPrev = pTemp; + // append all the end of the current set + assert( pPrev->pNext == NULL ); + pPrev->pNext = pSetAll; + return pSets; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_CutListRecycle( Fpga_Man_t * p, Fpga_Cut_t * pSetList, Fpga_Cut_t * pSave ) +{ + Fpga_Cut_t * pNext, * pTemp; + for ( pTemp = pSetList, pNext = pTemp? pTemp->pNext : NULL; + pTemp; + pTemp = pNext, pNext = pNext? pNext->pNext : NULL ) + if ( pTemp != pSave ) + Extra_MmFixedEntryRecycle( p->mmCuts, (char *)pTemp ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_CutListCount( Fpga_Cut_t * pSets ) +{ + Fpga_Cut_t * pTemp; + int i; + for ( i = 0, pTemp = pSets; pTemp; pTemp = pTemp->pNext, i++ ); + return i; +} + +#if 0 + +/**function************************************************************* + + synopsis [Removes the fanouts of the cut.] + + description [] + + sideeffects [] + + seealso [] + +***********************************************************************/ +void Fpga_CutRemoveFanouts( Fpga_Man_t * p, Fpga_Node_t * pNode, Fpga_Cut_t * pCut ) +{ + Fpga_NodeVec_t * vFanouts; + int i, k; + for ( i = 0; i < pCut->nLeaves; i++ ) + { + vFanouts = pCut->ppLeaves[i]->vFanouts; + for ( k = 0; k < vFanouts->nSize; k++ ) + if ( vFanouts->pArray[k] == pNode ) + break; + assert( k != vFanouts->nSize ); + for ( k++; k < vFanouts->nSize; k++ ) + vFanouts->pArray[k-1] = vFanouts->pArray[k]; + vFanouts->nSize--; + } +} + +/**function************************************************************* + + synopsis [Removes the fanouts of the cut.] + + description [] + + sideeffects [] + + seealso [] + +***********************************************************************/ +void Fpga_CutInsertFanouts( Fpga_Man_t * p, Fpga_Node_t * pNode, Fpga_Cut_t * pCut ) +{ + int i; + for ( i = 0; i < pCut->nLeaves; i++ ) + Fpga_NodeVecPush( pCut->ppLeaves[i]->vFanouts, pNode ); +} +#endif + +/**Function************************************************************* + + Synopsis [Computes the arrival time and the area flow of the cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_CutGetParameters( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ) +{ + Fpga_Cut_t * pFaninCut; + int i; + pCut->tArrival = -FPGA_FLOAT_LARGE; + pCut->aFlow = pMan->pLutLib->pLutAreas[pCut->nLeaves]; + for ( i = 0; i < pCut->nLeaves; i++ ) + { + pFaninCut = pCut->ppLeaves[i]->pCutBest; + if ( pCut->tArrival < pFaninCut->tArrival ) + pCut->tArrival = pFaninCut->tArrival; + // if the fanout count is not set, assume it to be 1 + if ( pCut->ppLeaves[i]->nRefs == 0 ) + pCut->aFlow += pFaninCut->aFlow; + else +// pCut->aFlow += pFaninCut->aFlow / pCut->ppLeaves[i]->nRefs; + pCut->aFlow += pFaninCut->aFlow / pCut->ppLeaves[i]->aEstFanouts; + } + pCut->tArrival += pMan->pLutLib->pLutDelays[pCut->nLeaves]; +} + + +/**function************************************************************* + + synopsis [Computes the area flow of the cut.] + + description [] + + sideeffects [] + + seealso [] + +***********************************************************************/ +float Fpga_CutGetAreaFlow( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ) +{ + Fpga_Cut_t * pCutFanin; + int i; + pCut->aFlow = pMan->pLutLib->pLutAreas[pCut->nLeaves]; + for ( i = 0; i < pCut->nLeaves; i++ ) + { + // get the cut implementing this phase of the fanin + pCutFanin = pCut->ppLeaves[i]->pCutBest; + assert( pCutFanin ); + pCut->aFlow += pCutFanin->aFlow / pCut->ppLeaves[i]->nRefs; + } + return pCut->aFlow; +} + +/**function************************************************************* + + synopsis [Computes the exact area associated with the cut.] + + description [] + + sideeffects [] + + seealso [] + +***********************************************************************/ +float Fpga_CutGetAreaRefed( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ) +{ + float aResult, aResult2; + if ( pCut->nLeaves == 1 ) + return 0; + aResult = Fpga_CutDeref( pMan, NULL, pCut, 0 ); + aResult2 = Fpga_CutRef( pMan, NULL, pCut, 0 ); + assert( aResult == aResult2 ); + return aResult; +} + +/**function************************************************************* + + synopsis [Computes the exact area associated with the cut.] + + description [] + + sideeffects [] + + seealso [] + +***********************************************************************/ +float Fpga_CutGetAreaDerefed( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ) +{ + float aResult, aResult2; + if ( pCut->nLeaves == 1 ) + return 0; + aResult2 = Fpga_CutRef( pMan, NULL, pCut, 0 ); + aResult = Fpga_CutDeref( pMan, NULL, 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_CutRef( 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 = pMan->pLutLib->pLutAreas[pCut->nLeaves]; + // 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) ) + continue; + aArea += Fpga_CutRef( 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_CutDeref( 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 = pMan->pLutLib->pLutAreas[pCut->nLeaves]; + // 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) ) + continue; + aArea += Fpga_CutDeref( pMan, pNodeChild, pNodeChild->pCutBest, fFanouts ); + } + return aArea; +} + + + +/**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.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_MappingSetUsedCuts( Fpga_Man_t * pMan ) +{ + int i; + for ( i = 0; i < pMan->vNodesAll->nSize; i++ ) + if ( pMan->vNodesAll->pArray[i]->pCutOld ) + { + pMan->vNodesAll->pArray[i]->pCutBest = pMan->vNodesAll->pArray[i]->pCutOld; + pMan->vNodesAll->pArray[i]->pCutOld = NULL; + } +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/fpga/fpgaFanout.c b/src/map/fpga/fpgaFanout.c new file mode 100644 index 00000000..50809f65 --- /dev/null +++ b/src/map/fpga/fpgaFanout.c @@ -0,0 +1,139 @@ +/**CFile**************************************************************** + + FileName [fpgaFanout.c] + + PackageName [FRAIG: Functionally reduced AND-INV graphs.] + + Synopsis [Procedures to manipulate fanouts of the FRAIG nodes.] + + Author [Alan Mishchenko ] + + Affiliation [UC Berkeley] + + Date [Ver. 2.0. Started - August 18, 2004.] + + Revision [$Id: fpgaFanout.c,v 1.1 2005/01/23 06:59:41 alanmi Exp $] + +***********************************************************************/ + +#include "fpgaInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + + +/**Function************************************************************* + + Synopsis [Add the fanout to the node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_NodeAddFaninFanout( Fpga_Node_t * pFanin, Fpga_Node_t * pFanout ) +{ + Fpga_Node_t * pPivot; + + // pFanins is a fanin of pFanout + assert( !Fpga_IsComplement(pFanin) ); + assert( !Fpga_IsComplement(pFanout) ); + assert( Fpga_Regular(pFanout->p1) == pFanin || Fpga_Regular(pFanout->p2) == pFanin ); + + pPivot = pFanin->pFanPivot; + if ( pPivot == NULL ) + { + pFanin->pFanPivot = pFanout; + return; + } + + if ( Fpga_Regular(pPivot->p1) == pFanin ) + { + if ( Fpga_Regular(pFanout->p1) == pFanin ) + { + pFanout->pFanFanin1 = pPivot->pFanFanin1; + pPivot->pFanFanin1 = pFanout; + } + else // if ( Fpga_Regular(pFanout->p2) == pFanin ) + { + pFanout->pFanFanin2 = pPivot->pFanFanin1; + pPivot->pFanFanin1 = pFanout; + } + } + else // if ( Fpga_Regular(pPivot->p2) == pFanin ) + { + assert( Fpga_Regular(pPivot->p2) == pFanin ); + if ( Fpga_Regular(pFanout->p1) == pFanin ) + { + pFanout->pFanFanin1 = pPivot->pFanFanin2; + pPivot->pFanFanin2 = pFanout; + } + else // if ( Fpga_Regular(pFanout->p2) == pFanin ) + { + pFanout->pFanFanin2 = pPivot->pFanFanin2; + pPivot->pFanFanin2 = pFanout; + } + } +} + +/**Function************************************************************* + + Synopsis [Add the fanout to the node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_NodeRemoveFaninFanout( Fpga_Node_t * pFanin, Fpga_Node_t * pFanoutToRemove ) +{ + Fpga_Node_t * pFanout, * pFanout2, ** ppFanList; + // start the linked list of fanouts + ppFanList = &pFanin->pFanPivot; + // go through the fanouts + Fpga_NodeForEachFanoutSafe( pFanin, pFanout, pFanout2 ) + { + // skip the fanout-to-remove + if ( pFanout == pFanoutToRemove ) + continue; + // add useful fanouts to the list + *ppFanList = pFanout; + ppFanList = Fpga_NodeReadNextFanoutPlace( pFanin, pFanout ); + } + *ppFanList = NULL; +} + +/**Function************************************************************* + + Synopsis [Returns the number of fanouts of a node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_NodeGetFanoutNum( Fpga_Node_t * pNode ) +{ + Fpga_Node_t * pFanout; + int Counter = 0; + Fpga_NodeForEachFanout( pNode, pFanout ) + Counter++; + return Counter; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/fpga/fpgaGENERIC.c b/src/map/fpga/fpgaGENERIC.c new file mode 100644 index 00000000..f272c1b8 --- /dev/null +++ b/src/map/fpga/fpgaGENERIC.c @@ -0,0 +1,46 @@ +/**CFile**************************************************************** + + FileName [fpga__.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: fpga__.h,v 1.0 2003/09/08 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "fpgaInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/fpga/fpgaInt.h b/src/map/fpga/fpgaInt.h new file mode 100644 index 00000000..0fea9ec8 --- /dev/null +++ b/src/map/fpga/fpgaInt.h @@ -0,0 +1,395 @@ +/**CFile**************************************************************** + + FileName [fpgaInt.h] + + PackageName [MVSIS 2.0: 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: fpgaInt.h,v 1.8 2004/09/30 21:18:10 satrajit Exp $] + +***********************************************************************/ + +#ifndef __FPGA_INT_H__ +#define __FPGA_INT_H__ + +//////////////////////////////////////////////////////////////////////// +/// INCLUDES /// +//////////////////////////////////////////////////////////////////////// + +//#include "leaks.h" +#include +#include +#include +#include "extra.h" +#include "fraig.h" +#include "fpga.h" + +//////////////////////////////////////////////////////////////////////// +/// PARAMETERS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// MACRO DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +#ifdef _WIN32 +#define inline __inline // compatible with MS VS 6.0 +#endif + +// the maximum number of cut leaves (currently does not work for 7) +#define FPGA_MAX_LEAVES 6 + +// the bit masks +#define FPGA_MASK(n) ((~((unsigned)0)) >> (32-(n))) +#define FPGA_FULL (~((unsigned)0)) +#define FPGA_NO_VAR (-9999.0) +#define FPGA_NUM_BYTES(n) (((n)/16 + (((n)%16) > 0))*16) + +// maximum/minimum operators +#define FPGA_MIN(a,b) (((a) < (b))? (a) : (b)) +#define FPGA_MAX(a,b) (((a) > (b))? (a) : (b)) + +// the small and large numbers (min/max float are 1.17e-38/3.40e+38) +#define FPGA_FLOAT_LARGE ((float)1.0e+20) +#define FPGA_FLOAT_SMALL ((float)1.0e-20) +#define FPGA_INT_LARGE (10000000) + +// the macro to compute the signature +#define FPGA_SEQ_SIGN(p) (1 << (((unsigned)p)%31)); + +// internal macros to work with cuts +#define Fpga_CutIsComplement(p) (((int)((long) (p) & 01))) +#define Fpga_CutRegular(p) ((Fpga_Cut_t *)((unsigned)(p) & ~01)) +#define Fpga_CutNot(p) ((Fpga_Cut_t *)((long)(p) ^ 01)) +#define Fpga_CutNotCond(p,c) ((Fpga_Cut_t *)((long)(p) ^ (c))) + +// the cut nodes +#define Fpga_SeqIsComplement( p ) (((int)((long) (p) & 01))) +#define Fpga_SeqRegular( p ) ((Fpga_Node_t *)((unsigned)(p) & ~015)) +#define Fpga_SeqIndex( p ) ((((unsigned)(p)) >> 1) & 07) +#define Fpga_SeqIndexCreate( p, Ind ) (((unsigned)(p)) | (1 << (((unsigned)(Ind)) & 07))) + +// internal macros for referencing of nodes +#define Fpga_NodeReadRef(p) ((Fpga_Regular(p))->nRefs) +#define Fpga_NodeRef(p) ((Fpga_Regular(p))->nRefs++) + +// returns the complemented attribute of the node +#define Fpga_NodeIsSimComplement(p) (Fpga_IsComplement(p)? !(Fpga_Regular(p)->fInv) : (p)->fInv) + +// generating random unsigned (#define RAND_MAX 0x7fff) +#define FPGA_RANDOM_UNSIGNED ((((unsigned)rand()) << 24) ^ (((unsigned)rand()) << 12) ^ ((unsigned)rand())) + +// outputs the runtime in seconds +#define PRT(a,t) printf("%s = ", (a)); printf("%6.2f sec\n", (float)(t)/(float)(CLOCKS_PER_SEC)) + +//////////////////////////////////////////////////////////////////////// +/// STRUCTURE DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +// the mapping manager +struct Fpga_ManStruct_t_ +{ + // the mapping graph + Fpga_Node_t ** pBins; // the table of nodes hashed by their children + int nBins; // the size of the table + Fpga_Node_t ** pInputs; // the array of inputs + int nInputs; // the number of inputs + Fpga_Node_t ** pOutputs; // the array of outputs + int nOutputs; // the number of outputs + int nNodes; // the total number of nodes + Fpga_Node_t * pConst1; // the constant 1 node + Fpga_NodeVec_t * vAnds; // the array of pointer to nodes by number + Fpga_NodeVec_t * vNodesAll; // the array of pointer to nodes by number + int nLatches; // the number of latches in the circuit + + // info about the original circuit + char * pFileName; // the file name + char ** ppOutputNames; // the primary output names + float * pInputArrivals;// the PI arrival times + + // 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 nTravIds; + + // support of choice nodes + int nChoiceNodes; // the number of choice nodes + int nChoices; // the number of all choices + + int nCanons; + int nMatches; + + // 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 + Extra_MmFixed_t * mmCuts; // the memory manager for cuts + + // simulation info from the FRAIG manager + int nSimRounds; // the number of words in the simulation info + unsigned ** pSimInfo; // the simulation info for each PI + + // resynthesis parameters + int fResynthesis; // the resynthesis flag + float fRequiredGlo; // the global required times + float fRequiredShift;// the shift of the required times + float fRequiredStart;// the starting global required times + float fRequiredGain; // the reduction in delay + float fAreaGlo; // the total area + float fAreaGain; // the reduction in area + float fEpsilon; // the epsilon used to compare floats + float fDelayWindow; // the delay window for delay-oriented resynthesis + float DelayLimit; // for resynthesis + float AreaLimit; // for resynthesis + float TimeLimit; // for resynthesis + + // runtime statistics + int timeToMap; // time to transfer to the mapping structure + int timeCuts; // time to compute k-feasible cuts + int timeTruth; // time to compute the truth table for each cut + int timeMatch; // time to perform matching for each node + int timeRecover; // time to perform area recovery + int timeToNet; // time to transfer back to the network + int timeTotal; // the total mapping time + int time1; // time to transfer to the mapping structure + int time2; // time to transfer to the mapping structure +}; + +// the LUT library +struct Fpga_LutLibStruct_t_ +{ + char * pName; // the name of the LUT library + int LutMax; // the maximum LUT size + float pLutAreas[FPGA_MAX_LUTSIZE+1]; // the areas of LUTs + float pLutDelays[FPGA_MAX_LUTSIZE+1];// the delays of LUTs +}; + +// the mapping node +struct Fpga_NodeStruct_t_ +{ + // general information about the node + Fpga_Node_t * pNext; // the next node in the hash table + Fpga_Node_t * pLevel; // the next node in the linked list by level + int Num; // the unique number of this node + int NumA; // the unique number of this node + short Num2; // the temporary number of this node + short nRefs; // the number of references (fanouts) of the given node + unsigned fMark0 : 1; // the mark used for traversals + unsigned fMark1 : 1; // the mark used for traversals + unsigned fInv : 1; // the complemented attribute for the equivalent nodes + unsigned Value : 2; // the value of the nodes + unsigned fUsed : 1; // the flag indicating that the node is used in the mapping + unsigned fTemp : 1; // unused + unsigned Level :11; // the level of the given node + unsigned uData :14; // used to mark the fanins, for which resynthesis was tried + int TravId; + + // the successors of this node + Fpga_Node_t * p1; // the first child + Fpga_Node_t * p2; // the second child + Fpga_Node_t * pNextE; // the next functionally equivalent node + Fpga_Node_t * pRepr; // the representative of the functionally equivalent class +// Fpga_NodeVec_t * vFanouts; // the array of fanouts of the node + + // representation of node's fanouts + Fpga_Node_t * pFanPivot; // the first fanout of this node + Fpga_Node_t * pFanFanin1; // the next fanout of p1 + Fpga_Node_t * pFanFanin2; // the next fanout of p2 + + // the delay information + float tRequired; // the best area flow + float aEstFanouts; // the fanout estimation + float SwitchProb; // 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 + + // cut information + Fpga_Cut_t * pCutBest; // the best mapping + Fpga_Cut_t * pCutOld; // the old mapping + Fpga_Cut_t * pCuts; // mapping choices for the node (elementary comes first) + Fpga_Cut_t * pCutsN; // mapping choices for the node (elementary comes first) + + // misc information + char * pData0; // temporary storage for the corresponding network node +}; + +// the cuts used for matching +struct Fpga_CutStruct_t_ +{ + Fpga_Cut_t * pOne; // the father of this cut + Fpga_Cut_t * pTwo; // the mother of this cut + Fpga_Node_t * pRoot; // the root of the cut + Fpga_Node_t * ppLeaves[FPGA_MAX_LEAVES+1]; // the leaves of this cut + float fLevel; // the average level of the fanins + unsigned uSign; // signature for quick comparison + char fMark; // the mark to denote visited cut + char Phase; // the mark to denote complemented cut + char nLeaves; // the number of leaves of this cut + char nVolume; // the volume of this cut + float tArrival; // the arrival time + float aFlow; // the area flow of the cut + Fpga_Cut_t * pNext; // the pointer to the next cut in the list +}; + +// the vector of nodes +struct Fpga_NodeVecStruct_t_ +{ + Fpga_Node_t ** pArray; // the array of nodes + int nSize; // the number of entries in the array + int nCap; // the number of allocated entries +}; + +// getting hold of the next fanout of the node +#define Fpga_NodeReadNextFanout( pNode, pFanout ) \ + ( ( pFanout == NULL )? NULL : \ + ((Fpga_Regular((pFanout)->p1) == (pNode))? \ + (pFanout)->pFanFanin1 : (pFanout)->pFanFanin2) ) + +// getting hold of the place where the next fanout will be attached +#define Fpga_NodeReadNextFanoutPlace( pNode, pFanout ) \ + ( (Fpga_Regular((pFanout)->p1) == (pNode))? \ + &(pFanout)->pFanFanin1 : &(pFanout)->pFanFanin2 ) + +// iterator through the fanouts of the node +#define Fpga_NodeForEachFanout( pNode, pFanout ) \ + for ( pFanout = (pNode)->pFanPivot; pFanout; \ + pFanout = Fpga_NodeReadNextFanout(pNode, pFanout) ) + +// safe iterator through the fanouts of the node +#define Fpga_NodeForEachFanoutSafe( pNode, pFanout, pFanout2 ) \ + for ( pFanout = (pNode)->pFanPivot, \ + pFanout2 = Fpga_NodeReadNextFanout(pNode, pFanout); \ + pFanout; \ + pFanout = pFanout2, \ + pFanout2 = Fpga_NodeReadNextFanout(pNode, pFanout) ) + +//////////////////////////////////////////////////////////////////////// +/// GLOBAL VARIABLES /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/*=== fpgaCut.c ===============================================================*/ +extern void Fpga_MappingCuts( Fpga_Man_t * p ); +extern void Fpga_MappingCreatePiCuts( Fpga_Man_t * p ); +extern int Fpga_CutCountAll( Fpga_Man_t * pMan ); +/*=== fpgaCutUtils.c ===============================================================*/ +extern Fpga_Cut_t * Fpga_CutAlloc( Fpga_Man_t * p ); +extern Fpga_Cut_t * Fpga_CutDup( Fpga_Man_t * p, Fpga_Cut_t * pCutOld ); +extern void Fpga_CutFree( Fpga_Man_t * p, Fpga_Cut_t * pCut ); +extern void Fpga_CutPrint( Fpga_Man_t * p, Fpga_Node_t * pRoot, Fpga_Cut_t * pCut ); +extern Fpga_Cut_t * Fpga_CutCreateSimple( Fpga_Man_t * p, Fpga_Node_t * pNode ); +extern float Fpga_CutGetRootArea( Fpga_Man_t * p, Fpga_Cut_t * pCut ); +extern Fpga_Cut_t * Fpga_CutListAppend( Fpga_Cut_t * pSetAll, Fpga_Cut_t * pSets ); +extern void Fpga_CutListRecycle( Fpga_Man_t * p, Fpga_Cut_t * pSetList, Fpga_Cut_t * pSave ); +extern int Fpga_CutListCount( Fpga_Cut_t * pSets ); +extern void Fpga_CutRemoveFanouts( Fpga_Man_t * p, Fpga_Node_t * pNode, Fpga_Cut_t * pCut ); +extern void Fpga_CutInsertFanouts( Fpga_Man_t * p, Fpga_Node_t * pNode, Fpga_Cut_t * pCut ); +extern float Fpga_CutGetAreaRefed( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ); +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 =============================================================*/ +extern void Fpga_NodeAddFaninFanout( Fpga_Node_t * pFanin, Fpga_Node_t * pFanout ); +extern void Fpga_NodeRemoveFaninFanout( Fpga_Node_t * pFanin, Fpga_Node_t * pFanoutToRemove ); +extern int Fpga_NodeGetFanoutNum( Fpga_Node_t * pNode ); +/*=== fpgaLib.c ============================================================*/ +extern Fpga_LutLib_t * Fpga_LutLibCreate( char * FileName, int fVerbose ); +extern void Fpga_LutLibFree( Fpga_LutLib_t * p ); +extern void Fpga_LutLibPrint( Fpga_LutLib_t * pLutLib ); +extern int Fpga_LutLibDelaysAreDiscrete( Fpga_LutLib_t * pLutLib ); +/*=== fpgaMatch.c ===============================================================*/ +extern int Fpga_MappingMatches( Fpga_Man_t * p, int fDelayOriented ); +extern int Fpga_MappingMatchesArea( Fpga_Man_t * p ); +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 ); +/*=== 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 ); +extern float Fpga_TimeComputeArrivalMax( Fpga_Man_t * p ); +extern void Fpga_TimeComputeRequiredGlobal( Fpga_Man_t * p ); +extern void Fpga_TimeComputeRequired( Fpga_Man_t * p, float fRequired ); +extern void Fpga_TimePropagateRequired( Fpga_Man_t * p, Fpga_NodeVec_t * vNodes ); +/*=== fpgaTruth.c ===============================================================*/ +extern void Fpga_MappingTruths( Fpga_Man_t * pMan ); +/*=== fpgaVec.c =============================================================*/ +extern Fpga_NodeVec_t * Fpga_NodeVecAlloc( int nCap ); +extern void Fpga_NodeVecFree( Fpga_NodeVec_t * p ); +extern Fpga_Node_t ** Fpga_NodeVecReadArray( Fpga_NodeVec_t * p ); +extern int Fpga_NodeVecReadSize( Fpga_NodeVec_t * p ); +extern void Fpga_NodeVecGrow( Fpga_NodeVec_t * p, int nCapMin ); +extern void Fpga_NodeVecShrink( Fpga_NodeVec_t * p, int nSizeNew ); +extern void Fpga_NodeVecClear( Fpga_NodeVec_t * p ); +extern void Fpga_NodeVecPush( Fpga_NodeVec_t * p, Fpga_Node_t * Entry ); +extern int Fpga_NodeVecPushUnique( Fpga_NodeVec_t * p, Fpga_Node_t * Entry ); +extern Fpga_Node_t * Fpga_NodeVecPop( Fpga_NodeVec_t * p ); +extern void Fpga_NodeVecWriteEntry( Fpga_NodeVec_t * p, int i, Fpga_Node_t * Entry ); +extern Fpga_Node_t * Fpga_NodeVecReadEntry( Fpga_NodeVec_t * p, int i ); +extern void Fpga_NodeVecSortByLevel( Fpga_NodeVec_t * p ); +extern void Fpga_SortNodesByArrivalTimes( Fpga_NodeVec_t * p ); +extern void Fpga_NodeVecUnion( Fpga_NodeVec_t * p, Fpga_NodeVec_t * p1, Fpga_NodeVec_t * p2 ); +extern void Fpga_NodeVecPushOrder( Fpga_NodeVec_t * vNodes, Fpga_Node_t * pNode, int fIncreasing ); +extern void Fpga_NodeVecReverse( Fpga_NodeVec_t * vNodes ); + +/*=== fpgaUtils.c ===============================================================*/ +extern Fpga_NodeVec_t * Fpga_MappingDfs( Fpga_Man_t * pMan, int fCollectEquiv ); +extern Fpga_NodeVec_t * Fpga_MappingDfsNodes( Fpga_Man_t * pMan, Fpga_Node_t ** ppNodes, int nNodes, int fEquiv ); +extern Fpga_NodeVec_t * Fpga_MappingDfsCutsNode( Fpga_Man_t * pMan, Fpga_Node_t * pNode ); +//extern Sat_IntVec_t * Fpga_MappingDfsNodesSat( Fpga_Man_t * pMan, Fpga_Node_t ** ppNodes, int nNodes ); +extern Fpga_NodeVec_t * Fpga_MappingDfsCuts( Fpga_Man_t * pMan ); +extern int Fpga_CountLevels( Fpga_Man_t * pMan ); +extern int Fpga_CountLevelsNodes( Fpga_Man_t * pMan, Fpga_Node_t ** ppRoots, int nRoots ); +extern void Fpga_MappingMarkUsed( Fpga_Man_t * pMan ); +extern float Fpga_MappingGetAreaFlow( Fpga_Man_t * p ); +extern float Fpga_MappingArea( Fpga_Man_t * pMan ); +extern float Fpga_MappingComputeCutAreas( Fpga_Man_t * pMan ); +extern float Fpga_MappingSetRefsAndArea( Fpga_Man_t * pMan ); +extern int Fpga_MappingCountLevels( Fpga_Man_t * pMan ); +extern void Fpga_MappingUnmark( Fpga_Man_t * pMan ); +extern void Fpga_MappingUnmark_rec( Fpga_Node_t * pNode ); +extern void Fpga_MappingMark_rec( Fpga_Node_t * pNode ); +extern void Fpga_MappedMark_rec( Fpga_Node_t * pNode ); +extern void Fpga_MappedUnmark_rec( Fpga_Node_t * pNode ); +extern void Fpga_MappingPrintOutputArrivals( Fpga_Man_t * p ); +extern void Fpga_MappingSetupTruthTables( unsigned uTruths[][2] ); +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_GetMaxLevel( Fpga_Man_t * pMan ); +extern void Fpga_ManReportChoices( Fpga_Man_t * pMan ); +extern void Fpga_MappingSetChoiceLevels( Fpga_Man_t * pMan ); + +/*=== CUDD package.c ===============================================================*/ +extern unsigned int Cudd_Prime( unsigned int p ); + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + +#endif diff --git a/src/map/fpga/fpgaLib.c b/src/map/fpga/fpgaLib.c new file mode 100644 index 00000000..9fd8e281 --- /dev/null +++ b/src/map/fpga/fpgaLib.c @@ -0,0 +1,183 @@ +/**CFile**************************************************************** + + FileName [fpgaLib.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: fpgaLib.c,v 1.4 2005/01/23 06:59:41 alanmi Exp $] + +***********************************************************************/ + +#include "fpgaInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Reads the description of LUTs from the LUT library file.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_LutLib_t * Fpga_LutLibCreate( char * FileName, int fVerbose ) +{ + char pBuffer[1000], * pToken; + Fpga_LutLib_t * p; + FILE * pFile; + int i; + + pFile = fopen( FileName, "r" ); + if ( pFile == NULL ) + { + printf( "Cannot open LUT library file \"%s\".\n", FileName ); + return NULL; + } + + p = ALLOC( Fpga_LutLib_t, 1 ); + memset( p, 0, sizeof(Fpga_LutLib_t) ); + p->pName = util_strsav( FileName ); + + i = 1; + while ( fgets( pBuffer, 1000, pFile ) != NULL ) + { + pToken = strtok( pBuffer, " \t\n" ); + if ( pToken == NULL ) + continue; + if ( pToken[0] == '#' ) + continue; + if ( i != atoi(pToken) ) + { + printf( "Error in the LUT library file \"%s\".\n", FileName ); + free( p ); + return NULL; + } + + pToken = strtok( NULL, " \t\n" ); + p->pLutAreas[i] = (float)atof(pToken); + + pToken = strtok( NULL, " \t\n" ); + p->pLutDelays[i] = (float)atof(pToken); + + if ( i == FPGA_MAX_LUTSIZE ) + { + printf( "Skipping LUTs of size more than %d.\n", i ); + break; + } + i++; + } + p->LutMax = i-1; + if ( p->LutMax > FPGA_MAX_LEAVES ) + { + p->LutMax = FPGA_MAX_LEAVES; + printf( "Warning: LUTs with more than %d input will not be used.\n", FPGA_MAX_LEAVES ); + } + return p; +} + +/**Function************************************************************* + + Synopsis [Duplicates the LUT library.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_LutLib_t * Fpga_LutLibDup( Fpga_LutLib_t * p ) +{ + Fpga_LutLib_t * pNew; + pNew = ALLOC( Fpga_LutLib_t, 1 ); + *pNew = *p; + pNew->pName = util_strsav( pNew->pName ); + return pNew; +} + +/**Function************************************************************* + + Synopsis [Frees the LUT library.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_LutLibFree( Fpga_LutLib_t * pLutLib ) +{ + if ( pLutLib == NULL ) + return; + FREE( pLutLib->pName ); + FREE( pLutLib ); +} + + +/**Function************************************************************* + + Synopsis [Prints the LUT library.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_LutLibPrint( Fpga_LutLib_t * pLutLib ) +{ + int i; + printf( "# The area/delay of k-variable LUTs:\n" ); + printf( "# k area delay\n" ); + for ( i = 1; i <= pLutLib->LutMax; i++ ) + printf( "%d %7.2f %7.2f\n", i, pLutLib->pLutAreas[i], pLutLib->pLutDelays[i] ); +} + +/**Function************************************************************* + + Synopsis [Returns 1 if the delays are discrete.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_LutLibDelaysAreDiscrete( Fpga_LutLib_t * pLutLib ) +{ + float Delay; + int i; + for ( i = 1; i <= pLutLib->LutMax; i++ ) + { + Delay = pLutLib->pLutDelays[i]; + if ( ((float)((int)Delay)) != Delay ) + return 0; + } + return 1; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + 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 /// +//////////////////////////////////////////////////////////////////////// diff --git a/src/map/fpga/fpgaTime.c b/src/map/fpga/fpgaTime.c new file mode 100644 index 00000000..df98faa1 --- /dev/null +++ b/src/map/fpga/fpgaTime.c @@ -0,0 +1,189 @@ +/**CFile**************************************************************** + + FileName [fpgaTime.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: fpgaTime.c,v 1.1 2005/01/23 06:59:42 alanmi Exp $] + +***********************************************************************/ + +#include "fpgaInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Computes the arrival times of the cut.] + + Description [Computes the maximum arrival time of the cut leaves and + adds the delay of the LUT.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Fpga_TimeCutComputeArrival( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ) +{ + int i; + float tArrival; + tArrival = -FPGA_FLOAT_LARGE; + for ( i = 0; i < pCut->nLeaves; i++ ) + if ( tArrival < pCut->ppLeaves[i]->pCutBest->tArrival ) + tArrival = pCut->ppLeaves[i]->pCutBest->tArrival; + tArrival += pMan->pLutLib->pLutDelays[pCut->nLeaves]; + return tArrival; +} + +/**Function************************************************************* + + Synopsis [Computes the arrival times of the cut recursively.] + + Description [When computing the arrival time for the previously unused + cuts, their arrival time may be incorrect because their fanins have + incorrect arrival time. This procedure is called to fix this problem.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Fpga_TimeCutComputeArrival_rec( Fpga_Man_t * pMan, Fpga_Cut_t * pCut ) +{ + int i; + for ( i = 0; i < pCut->nLeaves; i++ ) + if ( pCut->ppLeaves[i]->nRefs == 0 ) + Fpga_TimeCutComputeArrival_rec( pMan, pCut->ppLeaves[i]->pCutBest ); + return Fpga_TimeCutComputeArrival( pMan, pCut ); +} + +/**Function************************************************************* + + Synopsis [Computes the maximum arrival times.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Fpga_TimeComputeArrivalMax( Fpga_Man_t * p ) +{ + float fRequired; + int i; + // get the critical PO arrival time + fRequired = -FPGA_FLOAT_LARGE; + for ( i = 0; i < p->nOutputs; i++ ) + { + if ( Fpga_NodeIsConst(p->pOutputs[i]) ) + continue; + fRequired = FPGA_MAX( fRequired, Fpga_Regular(p->pOutputs[i])->pCutBest->tArrival ); + } + return fRequired; +} + +/**Function************************************************************* + + Synopsis [Computes the required times of all nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_TimeComputeRequiredGlobal( Fpga_Man_t * p ) +{ + p->fRequiredGlo = Fpga_TimeComputeArrivalMax( p ); + Fpga_TimeComputeRequired( p, p->fRequiredGlo ); +} + +/**Function************************************************************* + + Synopsis [Computes the required times of all nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_TimeComputeRequired( Fpga_Man_t * p, float fRequired ) +{ + Fpga_NodeVec_t * vNodes; + int i; + + // clean the required times and the fanout counts for all nodes + for ( i = 0; i < p->vAnds->nSize; i++ ) + p->vAnds->pArray[i]->tRequired = FPGA_FLOAT_LARGE; + + // set the required times for the POs + for ( i = 0; i < p->nOutputs; i++ ) + Fpga_Regular(p->pOutputs[i])->tRequired = fRequired; + + // collect nodes reachable from POs in the DFS order through the best cuts + vNodes = Fpga_MappingDfsCuts( p ); + Fpga_TimePropagateRequired( p, vNodes ); + Fpga_NodeVecFree( vNodes ); +} + +/**Function************************************************************* + + Synopsis [Computes the required times of the given nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_TimePropagateRequired( Fpga_Man_t * p, Fpga_NodeVec_t * vNodes ) +{ + Fpga_Node_t * pNode, * pChild; + float fRequired; + int i, k; + + // sorts the nodes in the decreasing order of levels + Fpga_MappingSortByLevel( p, vNodes, 0 ); + // go through the nodes in the reverse topological order + for ( k = 0; k < vNodes->nSize; k++ ) + { + pNode = vNodes->pArray[k]; + if ( !Fpga_NodeIsAnd(pNode) ) + continue; + // get the required time for children + fRequired = pNode->tRequired - p->pLutLib->pLutDelays[pNode->pCutBest->nLeaves]; + // update the required time of the children + for ( i = 0; i < pNode->pCutBest->nLeaves; i++ ) + { + pChild = pNode->pCutBest->ppLeaves[i]; + pChild->tRequired = FPGA_MIN( pChild->tRequired, fRequired ); + } + } +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/fpga/fpgaTruth.c b/src/map/fpga/fpgaTruth.c new file mode 100644 index 00000000..17c6385c --- /dev/null +++ b/src/map/fpga/fpgaTruth.c @@ -0,0 +1,107 @@ +/**CFile**************************************************************** + + FileName [fpgaTruth.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: fpgaTruth.c,v 1.4 2005/01/23 06:59:42 alanmi Exp $] + +***********************************************************************/ + +#include "fpgaInt.h" +#include "cudd.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Recursively derives the truth table for the cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +DdNode * Fpga_TruthsCutBdd_rec( DdManager * dd, Fpga_Cut_t * pCut, Fpga_NodeVec_t * vVisited ) +{ + DdNode * bFunc, * bFunc0, * bFunc1; + assert( !Fpga_IsComplement(pCut) ); + // if the cut is visited, return the result + if ( pCut->uSign ) + return (DdNode *)pCut->uSign; + // compute the functions of the children + bFunc0 = Fpga_TruthsCutBdd_rec( dd, Fpga_CutRegular(pCut->pOne), vVisited ); Cudd_Ref( bFunc0 ); + bFunc0 = Cudd_NotCond( bFunc0, Fpga_CutIsComplement(pCut->pOne) ); + bFunc1 = Fpga_TruthsCutBdd_rec( dd, Fpga_CutRegular(pCut->pTwo), vVisited ); Cudd_Ref( bFunc1 ); + bFunc1 = Cudd_NotCond( bFunc1, Fpga_CutIsComplement(pCut->pTwo) ); + // get the function of the cut + bFunc = Cudd_bddAnd( dd, bFunc0, bFunc1 ); Cudd_Ref( bFunc ); + bFunc = Cudd_NotCond( bFunc, pCut->Phase ); + Cudd_RecursiveDeref( dd, bFunc0 ); + Cudd_RecursiveDeref( dd, bFunc1 ); + assert( pCut->uSign == 0 ); + pCut->uSign = (unsigned)bFunc; + // add this cut to the visited list + Fpga_NodeVecPush( vVisited, (Fpga_Node_t *)pCut ); + return bFunc; +} + +/**Function************************************************************* + + Synopsis [Derives the truth table for one cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void * Fpga_TruthsCutBdd( void * dd, Fpga_Cut_t * pCut ) +{ + Fpga_NodeVec_t * vVisited; + DdNode * bFunc; + int i; + assert( pCut->nLeaves > 1 ); + // set the leaf variables + for ( i = 0; i < pCut->nLeaves; i++ ) + pCut->ppLeaves[i]->pCuts->uSign = (unsigned)Cudd_bddIthVar( dd, i ); + // recursively compute the function + vVisited = Fpga_NodeVecAlloc( 10 ); + bFunc = Fpga_TruthsCutBdd_rec( dd, pCut, vVisited ); Cudd_Ref( bFunc ); + // clean the intermediate BDDs + for ( i = 0; i < pCut->nLeaves; i++ ) + pCut->ppLeaves[i]->pCuts->uSign = 0; + for ( i = 0; i < vVisited->nSize; i++ ) + { + pCut = (Fpga_Cut_t *)vVisited->pArray[i]; + Cudd_RecursiveDeref( dd, (DdNode*)pCut->uSign ); + pCut->uSign = 0; + } + Fpga_NodeVecFree( vVisited ); + Cudd_Deref( bFunc ); + return bFunc; +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/fpga/fpgaUtils.c b/src/map/fpga/fpgaUtils.c new file mode 100644 index 00000000..a5b2cb32 --- /dev/null +++ b/src/map/fpga/fpgaUtils.c @@ -0,0 +1,1289 @@ +/**CFile**************************************************************** + + FileName [fpgaUtils.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: fpgaUtils.c,v 1.3 2004/07/06 04:55:58 alanmi Exp $] + +***********************************************************************/ + +#include "fpgaInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static void Fpga_MappingDfs_rec( Fpga_Node_t * pNode, Fpga_NodeVec_t * vNodes, int fCollectEquiv ); +static void Fpga_MappingDfsCuts_rec( Fpga_Node_t * pNode, Fpga_NodeVec_t * vNodes ); +static float Fpga_MappingArea_rec( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_NodeVec_t * vNodes ); +static int Fpga_MappingCountLevels_rec( Fpga_Node_t * pNode ); +static void Fpga_MappingMarkUsed_rec( Fpga_Node_t * pNode ); +static int Fpga_MappingCompareOutputDelay( int * pOut1, int * pOut2 ); +static float Fpga_MappingSetRefsAndArea_rec( Fpga_Man_t * pMan, Fpga_Node_t * pNode ); +static Fpga_Man_t * s_pMan = NULL; + +static void Fpga_DfsLim_rec( Fpga_Node_t * pNode, int Level, Fpga_NodeVec_t * vNodes ); +static int Fpga_CollectNodeTfo_rec( Fpga_Node_t * pNode, Fpga_Node_t * pPivot, Fpga_NodeVec_t * vVisited, Fpga_NodeVec_t * vTfo ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + + +/**Function************************************************************* + + Synopsis [Computes the DFS ordering of the nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_NodeVec_t * Fpga_MappingDfs( Fpga_Man_t * pMan, int fCollectEquiv ) +{ + Fpga_NodeVec_t * vNodes; + Fpga_Node_t * pNode; + int i; + // start the array + vNodes = Fpga_NodeVecAlloc( 100 ); + // collect the PIs + for ( i = 0; i < pMan->nInputs; i++ ) + { + pNode = pMan->pInputs[i]; + Fpga_NodeVecPush( vNodes, pNode ); + pNode->fMark0 = 1; + } + // perform the traversal + for ( i = 0; i < pMan->nOutputs; i++ ) + Fpga_MappingDfs_rec( Fpga_Regular(pMan->pOutputs[i]), vNodes, fCollectEquiv ); + for ( i = 0; i < vNodes->nSize; i++ ) + vNodes->pArray[i]->fMark0 = 0; +// for ( i = 0; i < pMan->nOutputs; i++ ) +// Fpga_MappingUnmark_rec( Fpga_Regular(pMan->pOutputs[i]) ); + return vNodes; +} + +/**Function************************************************************* + + Synopsis [Recursively computes the DFS ordering of the nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_MappingDfs_rec( Fpga_Node_t * pNode, Fpga_NodeVec_t * vNodes, int fCollectEquiv ) +{ + assert( !Fpga_IsComplement(pNode) ); + if ( pNode->fMark0 ) + return; + // visit the transitive fanin + if ( Fpga_NodeIsAnd(pNode) ) + { + Fpga_MappingDfs_rec( Fpga_Regular(pNode->p1), vNodes, fCollectEquiv ); + Fpga_MappingDfs_rec( Fpga_Regular(pNode->p2), vNodes, fCollectEquiv ); + } + // visit the equivalent nodes + if ( fCollectEquiv && pNode->pNextE ) + Fpga_MappingDfs_rec( pNode->pNextE, vNodes, fCollectEquiv ); + // make sure the node is not visited through the equivalent nodes + assert( pNode->fMark0 == 0 ); + // mark the node as visited + pNode->fMark0 = 1; + // add the node to the list + Fpga_NodeVecPush( vNodes, pNode ); +} + +/**Function************************************************************* + + Synopsis [Computes the DFS ordering of the nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_NodeVec_t * Fpga_MappingDfsNodes( Fpga_Man_t * pMan, Fpga_Node_t ** ppNodes, int nNodes, int fEquiv ) +{ + Fpga_NodeVec_t * vNodes; + int i; + // perform the traversal + vNodes = Fpga_NodeVecAlloc( 200 ); + for ( i = 0; i < nNodes; i++ ) + Fpga_MappingDfs_rec( ppNodes[i], vNodes, fEquiv ); + for ( i = 0; i < vNodes->nSize; i++ ) + vNodes->pArray[i]->fMark0 = 0; + return vNodes; +} + + +/**Function************************************************************* + + Synopsis [Computes the number of logic levels not counting PIs/POs.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_CountLevels( Fpga_Man_t * pMan ) +{ + int i, LevelsMax, LevelsCur; + // perform the traversal + LevelsMax = -1; + for ( i = 0; i < pMan->nOutputs; i++ ) + { + LevelsCur = Fpga_Regular(pMan->pOutputs[i])->Level; + if ( LevelsMax < LevelsCur ) + LevelsMax = LevelsCur; + } + return LevelsMax; +} + +/**Function************************************************************* + + Synopsis [Computes the number of logic levels not counting PIs/POs.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_CountLevelsNodes( Fpga_Man_t * pMan, Fpga_Node_t ** ppRoots, int nRoots ) +{ + int i, LevelsMax, LevelsCur; + // perform the traversal + LevelsMax = -1; + for ( i = 0; i < nRoots; i++ ) + { + LevelsCur = Fpga_Regular(ppRoots[i])->Level; + if ( LevelsMax < LevelsCur ) + LevelsMax = LevelsCur; + } + return LevelsMax; +} + +/**Function************************************************************* + + Synopsis [Computes the DFS ordering of the nodes visible in current mapping.] + + Description [The node is visible if it appears as a root of one of the best + cuts (that is cuts selected for the current mapping).] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_NodeVec_t * Fpga_MappingDfsCuts( Fpga_Man_t * pMan ) +{ + Fpga_NodeVec_t * vNodes; + int i; + // perform the traversal + vNodes = Fpga_NodeVecAlloc( 100 ); + for ( i = 0; i < pMan->nOutputs; i++ ) + Fpga_MappingDfsCuts_rec( Fpga_Regular(pMan->pOutputs[i]), vNodes ); + for ( i = 0; i < vNodes->nSize; i++ ) + vNodes->pArray[i]->fMark0 = 0; + return vNodes; +} + +/**Function************************************************************* + + Synopsis [Computes the DFS ordering of the nodes visible in current mapping.] + + Description [The node is visible if it appears as a root of one of the best + cuts (that is cuts selected for the current mapping).] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_NodeVec_t * Fpga_MappingDfsCutsNode( Fpga_Man_t * pMan, Fpga_Node_t * pNode ) +{ + Fpga_NodeVec_t * vNodes; + int i; + // perform the traversal + vNodes = Fpga_NodeVecAlloc( 100 ); + Fpga_MappingDfsCuts_rec( pNode, vNodes ); + for ( i = 0; i < vNodes->nSize; i++ ) + vNodes->pArray[i]->fMark0 = 0; + return vNodes; +} + +/**Function************************************************************* + + Synopsis [Recursively computes the DFS ordering of the nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_MappingDfsCuts_rec( Fpga_Node_t * pNode, Fpga_NodeVec_t * vNodes ) +{ + int i; + assert( !Fpga_IsComplement(pNode) ); + if ( !Fpga_NodeIsAnd(pNode) ) + return; + if ( pNode->fMark0 ) + return; + assert( pNode->pCutBest != NULL ); + // visit the transitive fanin of the selected cut + for ( i = 0; i < pNode->pCutBest->nLeaves; i++ ) + Fpga_MappingDfsCuts_rec( pNode->pCutBest->ppLeaves[i], vNodes ); + // make sure the node is not visited through the fanin nodes + assert( pNode->fMark0 == 0 ); + // mark the node as visited + pNode->fMark0 = 1; + // add the node to the list + Fpga_NodeVecPush( vNodes, pNode ); +} + + +/**Function************************************************************* + + Synopsis [Marks the nodes used in the mapping.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_MappingMarkUsed( Fpga_Man_t * pMan ) +{ + int i; + for ( i = 0; i < pMan->nOutputs; i++ ) + Fpga_MappingMarkUsed_rec( Fpga_Regular(pMan->pOutputs[i]) ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_MappingMarkUsed_rec( Fpga_Node_t * pNode ) +{ + int i; + assert( !Fpga_IsComplement(pNode) ); + if ( pNode->fUsed ) + return; + pNode->fUsed = 1; + if ( !Fpga_NodeIsAnd(pNode) ) + return; + assert( pNode->pCutBest != NULL ); + // visit the transitive fanin of the selected cut + for ( i = 0; i < pNode->pCutBest->nLeaves; i++ ) + Fpga_MappingMarkUsed_rec( pNode->pCutBest->ppLeaves[i] ); +} + + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Fpga_MappingGetAreaFlow( Fpga_Man_t * p ) +{ + float aFlowFlowTotal = 0; + int i; + for ( i = 0; i < p->nOutputs; i++ ) + { + if ( Fpga_NodeIsConst(p->pOutputs[i]) ) + continue; + aFlowFlowTotal += Fpga_Regular(p->pOutputs[i])->pCutBest->aFlow; + } + return aFlowFlowTotal; +} + +/**Function************************************************************* + + Synopsis [Computes the area of the current mapping.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Fpga_MappingArea( Fpga_Man_t * pMan ) +{ + Fpga_NodeVec_t * vNodes; + float aTotal; + int i; + // perform the traversal + aTotal = 0; + vNodes = Fpga_NodeVecAlloc( 100 ); + for ( i = 0; i < pMan->nOutputs; i++ ) + { + aTotal += Fpga_MappingArea_rec( pMan, Fpga_Regular(pMan->pOutputs[i]), vNodes ); + // add the area for single-input nodes (if any) at the POs +// if ( Fpga_NodeIsVar(pMan->pOutputs[i]) || Fpga_IsComplement(pMan->pOutputs[i]) ) +// aTotal += pMan->pLutLib->pLutAreas[1]; + } + for ( i = 0; i < vNodes->nSize; i++ ) + vNodes->pArray[i]->fMark0 = 0; + Fpga_NodeVecFree( vNodes ); + return aTotal; +} + +/**Function************************************************************* + + Synopsis [Recursively computes the DFS ordering of the nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Fpga_MappingArea_rec( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_NodeVec_t * vNodes ) +{ + float aArea; + int i; + assert( !Fpga_IsComplement(pNode) ); + if ( !Fpga_NodeIsAnd(pNode) ) + return 0; + if ( pNode->fMark0 ) + return 0; + assert( pNode->pCutBest != NULL ); + // visit the transitive fanin of the selected cut + aArea = 0; + for ( i = 0; i < pNode->pCutBest->nLeaves; i++ ) + aArea += Fpga_MappingArea_rec( pMan, pNode->pCutBest->ppLeaves[i], vNodes ); + // make sure the node is not visited through the fanin nodes + assert( pNode->fMark0 == 0 ); + // mark the node as visited + pNode->fMark0 = 1; + // add the node to the list + aArea += pMan->pLutLib->pLutAreas[pNode->pCutBest->nLeaves]; + // add the node to the list + Fpga_NodeVecPush( vNodes, pNode ); + return aArea; +} + + +/**Function************************************************************* + + Synopsis [Sets the correct reference counts for the mapping.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Fpga_MappingComputeCutAreas( Fpga_Man_t * pMan ) +{ + Fpga_NodeVec_t * vNodes; + Fpga_Node_t * pNode; + float Area = 0; + int i; + // collect nodes reachable from POs in the DFS order through the best cuts + vNodes = Fpga_MappingDfsCuts( pMan ); + for ( i = 0; i < vNodes->nSize; i++ ) + { + pNode = vNodes->pArray[i]; + pNode->pCutBest->aFlow = Fpga_CutGetAreaRefed( pMan, pNode->pCutBest ); + Area += pMan->pLutLib->pLutAreas[pNode->pCutBest->nLeaves]; + } + Fpga_NodeVecFree( vNodes ); + return Area; +} + +/**Function************************************************************* + + Synopsis [Sets the correct reference counts for the mapping.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Fpga_MappingSetRefsAndArea( Fpga_Man_t * pMan ) +{ + Fpga_Node_t * pNode; + float aArea; + int i; + // clean all references + for ( i = 0; i < pMan->vNodesAll->nSize; i++ ) + pMan->vNodesAll->pArray[i]->nRefs = 0; + // collect nodes reachable from POs in the DFS order through the best cuts + aArea = 0; + for ( i = 0; i < pMan->nOutputs; i++ ) + { + pNode = Fpga_Regular(pMan->pOutputs[i]); + if ( pNode == pMan->pConst1 ) + continue; + aArea += Fpga_MappingSetRefsAndArea_rec( pMan, pNode ); + pNode->nRefs++; + } + return aArea; +} + +/**Function************************************************************* + + Synopsis [Recursively computes the DFS ordering of the nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Fpga_MappingSetRefsAndArea_rec( Fpga_Man_t * pMan, Fpga_Node_t * pNode ) +{ + float aArea; + int i; + assert( !Fpga_IsComplement(pNode) ); + if ( pNode->nRefs++ ) + return 0; + if ( !Fpga_NodeIsAnd(pNode) ) + return 0; + assert( pNode->pCutBest != NULL ); + // visit the transitive fanin of the selected cut + aArea = pMan->pLutLib->pLutAreas[pNode->pCutBest->nLeaves]; + for ( i = 0; i < pNode->pCutBest->nLeaves; i++ ) + aArea += Fpga_MappingSetRefsAndArea_rec( pMan, pNode->pCutBest->ppLeaves[i] ); + return aArea; +} + +/**Function************************************************************* + + Synopsis [Computes the number of logic levels not counting PIs/POs.] + + Description [] + + SideEffects [Note that this procedure will reassign the levels assigned + originally by NodeCreate() because it counts the number of levels with + choices differently!] + + SeeAlso [] + +***********************************************************************/ +int Fpga_MappingCountLevels( Fpga_Man_t * pMan ) +{ + int i, LevelsMax, LevelsCur; + // perform the traversal + LevelsMax = -1; + for ( i = 0; i < pMan->nOutputs; i++ ) + { + LevelsCur = Fpga_MappingCountLevels_rec( Fpga_Regular(pMan->pOutputs[i]) ); + if ( LevelsMax < LevelsCur ) + LevelsMax = LevelsCur; + } + for ( i = 0; i < pMan->nOutputs; i++ ) + Fpga_MappingUnmark_rec( Fpga_Regular(pMan->pOutputs[i]) ); + return LevelsMax; +} + +/**Function************************************************************* + + Synopsis [Recursively computes the number of logic levels.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_MappingCountLevels_rec( Fpga_Node_t * pNode ) +{ + int Level1, Level2; + assert( !Fpga_IsComplement(pNode) ); + if ( !Fpga_NodeIsAnd(pNode) ) + { + pNode->Level = 0; + return 0; + } + if ( pNode->fMark0 ) + return pNode->Level; + pNode->fMark0 = 1; + // visit the transitive fanin + Level1 = Fpga_MappingCountLevels_rec( Fpga_Regular(pNode->p1) ); + Level2 = Fpga_MappingCountLevels_rec( Fpga_Regular(pNode->p2) ); + // set the number of levels + pNode->Level = 1 + ((Level1>Level2)? Level1: Level2); + return pNode->Level; +} + +/**Function************************************************************* + + Synopsis [Unmarks the nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_MappingUnmark( Fpga_Man_t * pMan ) +{ + int i; + for ( i = 0; i < pMan->nOutputs; i++ ) + Fpga_MappingUnmark_rec( Fpga_Regular(pMan->pOutputs[i]) ); +} + +/**Function************************************************************* + + Synopsis [Recursively unmarks the nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_MappingUnmark_rec( Fpga_Node_t * pNode ) +{ + assert( !Fpga_IsComplement(pNode) ); + if ( pNode->fMark0 == 0 ) + return; + pNode->fMark0 = 0; + if ( !Fpga_NodeIsAnd(pNode) ) + return; + Fpga_MappingUnmark_rec( Fpga_Regular(pNode->p1) ); + Fpga_MappingUnmark_rec( Fpga_Regular(pNode->p2) ); + // visit the equivalent nodes + if ( pNode->pNextE ) + Fpga_MappingUnmark_rec( pNode->pNextE ); +} + +/**Function************************************************************* + + Synopsis [Recursively unmarks the nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_MappingMark_rec( Fpga_Node_t * pNode ) +{ + assert( !Fpga_IsComplement(pNode) ); + if ( pNode->fMark0 == 1 ) + return; + pNode->fMark0 = 1; + if ( !Fpga_NodeIsAnd(pNode) ) + return; + Fpga_MappingMark_rec( Fpga_Regular(pNode->p1) ); + Fpga_MappingMark_rec( Fpga_Regular(pNode->p2) ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_MappedMark_rec( Fpga_Node_t * pNode ) +{ + int i; + assert( !Fpga_IsComplement(pNode) ); + if ( pNode->fMark0 == 1 ) + return; + pNode->fMark0 = 1; + if ( !Fpga_NodeIsAnd(pNode) ) + return; + assert( pNode->pCutBest != NULL ); + // visit the transitive fanin of the selected cut + for ( i = 0; i < pNode->pCutBest->nLeaves; i++ ) + Fpga_MappedMark_rec( pNode->pCutBest->ppLeaves[i] ); +} + +/**Function************************************************************* + + Synopsis [Recursively unmarks the nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_MappedUnmark_rec( Fpga_Node_t * pNode ) +{ + int i; + assert( !Fpga_IsComplement(pNode) ); + if ( pNode->fMark0 == 0 ) + return; + pNode->fMark0 = 0; + if ( !Fpga_NodeIsAnd(pNode) ) + return; + assert( pNode->pCutBest != NULL ); + // visit the transitive fanin of the selected cut + for ( i = 0; i < pNode->pCutBest->nLeaves; i++ ) + Fpga_MappedUnmark_rec( pNode->pCutBest->ppLeaves[i] ); +} + +/**Function************************************************************* + + Synopsis [Prints a bunch of latest arriving outputs.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_MappingPrintOutputArrivals( Fpga_Man_t * p ) +{ + Fpga_Node_t * pNode; + int fCompl, Limit, i; + int * pSorted; + + // sort outputs by arrival time + s_pMan = p; + pSorted = ALLOC( int, p->nOutputs ); + for ( i = 0; i < p->nOutputs; i++ ) + pSorted[i] = i; + qsort( (void *)pSorted, p->nOutputs, sizeof(int), + (int (*)(const void *, const void *)) Fpga_MappingCompareOutputDelay ); + assert( Fpga_MappingCompareOutputDelay( pSorted, pSorted + p->nOutputs - 1 ) <= 0 ); + s_pMan = NULL; + + // print the latest outputs + Limit = (p->nOutputs > 5)? 5 : p->nOutputs; + for ( i = 0; i < Limit; i++ ) + { + // get the i-th latest output + pNode = Fpga_Regular(p->pOutputs[pSorted[i]]); + fCompl = Fpga_IsComplement(p->pOutputs[pSorted[i]]); + // print out the best arrival time + printf( "Output %20s : ", p->ppOutputNames[pSorted[i]] ); + printf( "Delay = %8.2f ", (double)pNode->pCutBest->tArrival ); + if ( fCompl ) + printf( "NEG" ); + else + printf( "POS" ); + printf( "\n" ); + } + free( pSorted ); +} + +/**Function************************************************************* + + Synopsis [Compares the outputs by their arrival times.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_MappingCompareOutputDelay( int * pOut1, int * pOut2 ) +{ + Fpga_Node_t * pNode1 = Fpga_Regular(s_pMan->pOutputs[*pOut1]); + Fpga_Node_t * pNode2 = Fpga_Regular(s_pMan->pOutputs[*pOut2]); + float pTime1 = pNode1->pCutBest? pNode1->pCutBest->tArrival : 0; + float pTime2 = pNode2->pCutBest? pNode2->pCutBest->tArrival : 0; + if ( pTime1 > pTime2 ) + return -1; + if ( pTime1 < pTime2 ) + return 1; + return 0; +} + +/**Function************************************************************* + + Synopsis [Sets up the truth tables.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_MappingSetupTruthTables( unsigned uTruths[][2] ) +{ + int m, v; + // set up the truth tables + for ( m = 0; m < 32; m++ ) + for ( v = 0; v < 5; v++ ) + if ( m & (1 << v) ) + uTruths[v][0] |= (1 << m); + // make adjustments for the case of 6 variables + for ( v = 0; v < 5; v++ ) + uTruths[v][1] = uTruths[v][0]; + uTruths[5][0] = 0; + uTruths[5][1] = FPGA_FULL; +} + +/**Function************************************************************* + + Synopsis [Sets up the mask.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_MappingSetupMask( unsigned uMask[], int nVarsMax ) +{ + if ( nVarsMax == 6 ) + uMask[0] = uMask[1] = FPGA_FULL; + else + { + uMask[0] = FPGA_MASK(1 << nVarsMax); + uMask[1] = 0; + } +} + +/**Function************************************************************* + + Synopsis [Verify one useful property.] + + Description [This procedure verifies one useful property. After + the FRAIG construction with choice nodes is over, each primary node + should have fanins that are primary nodes. The primary nodes is the + one that does not have pNode->pRepr set to point to another node.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_ManCheckConsistency( Fpga_Man_t * p ) +{ + Fpga_Node_t * pNode; + Fpga_NodeVec_t * pVec; + int i; + pVec = Fpga_MappingDfs( p, 0 ); + for ( i = 0; i < pVec->nSize; i++ ) + { + pNode = pVec->pArray[i]; + if ( Fpga_NodeIsVar(pNode) ) + { + if ( pNode->pRepr ) + printf( "Primary input %d is a secondary node.\n", pNode->Num ); + } + else if ( Fpga_NodeIsConst(pNode) ) + { + if ( pNode->pRepr ) + printf( "Constant 1 %d is a secondary node.\n", pNode->Num ); + } + else + { + if ( pNode->pRepr ) + printf( "Internal node %d is a secondary node.\n", pNode->Num ); + if ( Fpga_Regular(pNode->p1)->pRepr ) + printf( "Internal node %d has first fanin that is a secondary node.\n", pNode->Num ); + if ( Fpga_Regular(pNode->p2)->pRepr ) + printf( "Internal node %d has second fanin that is a secondary node.\n", pNode->Num ); + } + } + Fpga_NodeVecFree( pVec ); + return 1; +} + +/**Function************************************************************* + + Synopsis [Compares the supergates by their level.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_CompareNodesByLevelDecreasing( Fpga_Node_t ** ppS1, Fpga_Node_t ** ppS2 ) +{ + if ( Fpga_Regular(*ppS1)->Level > Fpga_Regular(*ppS2)->Level ) + return -1; + if ( Fpga_Regular(*ppS1)->Level < Fpga_Regular(*ppS2)->Level ) + return 1; + return 0; +} + +/**Function************************************************************* + + Synopsis [Compares the supergates by their level.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_CompareNodesByLevelIncreasing( Fpga_Node_t ** ppS1, Fpga_Node_t ** ppS2 ) +{ + if ( Fpga_Regular(*ppS1)->Level < Fpga_Regular(*ppS2)->Level ) + return -1; + if ( Fpga_Regular(*ppS1)->Level > Fpga_Regular(*ppS2)->Level ) + return 1; + return 0; +} + +/**Function************************************************************* + + Synopsis [Orders the nodes in the decreasing order of levels.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_MappingSortByLevel( Fpga_Man_t * pMan, Fpga_NodeVec_t * vNodes, int fIncreasing ) +{ + if ( fIncreasing ) + qsort( (void *)vNodes->pArray, vNodes->nSize, sizeof(Fpga_Node_t *), + (int (*)(const void *, const void *)) Fpga_CompareNodesByLevelIncreasing ); + else + qsort( (void *)vNodes->pArray, vNodes->nSize, sizeof(Fpga_Node_t *), + (int (*)(const void *, const void *)) Fpga_CompareNodesByLevelDecreasing ); +// assert( Fpga_CompareNodesByLevel( vNodes->pArray, vNodes->pArray + vNodes->nSize - 1 ) <= 0 ); +} + +/**Function************************************************************* + + Synopsis [Computes the limited DFS ordering for one node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_NodeVec_t * Fpga_DfsLim( Fpga_Man_t * pMan, Fpga_Node_t * pNode, int nLevels ) +{ + Fpga_NodeVec_t * vNodes; + int i; + // perform the traversal + vNodes = Fpga_NodeVecAlloc( 100 ); + Fpga_DfsLim_rec( pNode, nLevels, vNodes ); + for ( i = 0; i < vNodes->nSize; i++ ) + vNodes->pArray[i]->fMark0 = 0; + return vNodes; +} + +/**Function************************************************************* + + Synopsis [Recursively computes the DFS ordering of the nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_DfsLim_rec( Fpga_Node_t * pNode, int Level, Fpga_NodeVec_t * vNodes ) +{ + assert( !Fpga_IsComplement(pNode) ); + if ( pNode->fMark0 ) + return; + pNode->fMark0 = 1; + // visit the transitive fanin + Level--; + if ( Level > 0 && Fpga_NodeIsAnd(pNode) ) + { + Fpga_DfsLim_rec( Fpga_Regular(pNode->p1), Level, vNodes ); + Fpga_DfsLim_rec( Fpga_Regular(pNode->p2), Level, vNodes ); + } + // add the node to the list + Fpga_NodeVecPush( vNodes, pNode ); +} + +/**Function************************************************************* + + Synopsis [Computes the limited DFS ordering for one node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_ManCleanData0( Fpga_Man_t * pMan ) +{ + int i; + for ( i = 0; i < pMan->vNodesAll->nSize; i++ ) + pMan->vNodesAll->pArray[i]->pData0 = 0; +} + +/**Function************************************************************* + + Synopsis [Collects the TFO of the node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_NodeVec_t * Fpga_CollectNodeTfo( Fpga_Man_t * pMan, Fpga_Node_t * pNode ) +{ + Fpga_NodeVec_t * vVisited, * vTfo; + int i; + // perform the traversal + vVisited = Fpga_NodeVecAlloc( 100 ); + vTfo = Fpga_NodeVecAlloc( 100 ); + for ( i = 0; i < pMan->nOutputs; i++ ) + Fpga_CollectNodeTfo_rec( Fpga_Regular(pMan->pOutputs[i]), pNode, vVisited, vTfo ); + for ( i = 0; i < vVisited->nSize; i++ ) + vVisited->pArray[i]->fMark0 = vVisited->pArray[i]->fMark1 = 0; + Fpga_NodeVecFree( vVisited ); + return vTfo; +} + +/**Function************************************************************* + + Synopsis [Collects the TFO of the node.] + + Description [Returns 1 if the node should be collected.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_CollectNodeTfo_rec( Fpga_Node_t * pNode, Fpga_Node_t * pPivot, Fpga_NodeVec_t * vVisited, Fpga_NodeVec_t * vTfo ) +{ + int Ret1, Ret2; + assert( !Fpga_IsComplement(pNode) ); + // skip visited nodes + if ( pNode->fMark0 ) + return pNode->fMark1; + pNode->fMark0 = 1; + Fpga_NodeVecPush( vVisited, pNode ); + + // return the pivot node + if ( pNode == pPivot ) + { + pNode->fMark1 = 1; + return 1; + } + if ( pNode->Level < pPivot->Level ) + { + pNode->fMark1 = 0; + return 0; + } + // visit the transitive fanin + assert( Fpga_NodeIsAnd(pNode) ); + Ret1 = Fpga_CollectNodeTfo_rec( Fpga_Regular(pNode->p1), pPivot, vVisited, vTfo ); + Ret2 = Fpga_CollectNodeTfo_rec( Fpga_Regular(pNode->p2), pPivot, vVisited, vTfo ); + if ( Ret1 || Ret2 ) + { + pNode->fMark1 = 1; + Fpga_NodeVecPush( vTfo, pNode ); + } + else + pNode->fMark1 = 0; + return pNode->fMark1; +} + +/**Function************************************************************* + + Synopsis [Levelizes the nodes accessible from the POs.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_NodeVec_t * Fpga_MappingLevelize( Fpga_Man_t * pMan, Fpga_NodeVec_t * vNodes ) +{ + Fpga_NodeVec_t * vLevels; + Fpga_Node_t ** ppNodes; + Fpga_Node_t * pNode; + int nNodes, nLevelsMax, i; + + // reassign the levels (this may be necessary for networks which choices) + ppNodes = vNodes->pArray; + nNodes = vNodes->nSize; + for ( i = 0; i < nNodes; i++ ) + { + pNode = ppNodes[i]; + if ( !Fpga_NodeIsAnd(pNode) ) + { + pNode->Level = 0; + continue; + } + pNode->Level = 1 + FPGA_MAX( Fpga_Regular(pNode->p1)->Level, Fpga_Regular(pNode->p2)->Level ); + } + + // get the max levels + nLevelsMax = 0; + for ( i = 0; i < pMan->nOutputs; i++ ) + nLevelsMax = FPGA_MAX( nLevelsMax, (int)Fpga_Regular(pMan->pOutputs[i])->Level ); + nLevelsMax++; + + // allocate storage for levels + vLevels = Fpga_NodeVecAlloc( nLevelsMax ); + for ( i = 0; i < nLevelsMax; i++ ) + Fpga_NodeVecPush( vLevels, NULL ); + + // go through the nodes and add them to the levels + for ( i = 0; i < nNodes; i++ ) + { + pNode = ppNodes[i]; + pNode->pLevel = NULL; + if ( !Fpga_NodeIsAnd(pNode) ) + continue; + // attach the node to this level + pNode->pLevel = Fpga_NodeVecReadEntry( vLevels, pNode->Level ); + Fpga_NodeVecWriteEntry( vLevels, pNode->Level, pNode ); + } + 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************************************************************* + + Synopsis [Sets up the mask.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_GetMaxLevel( Fpga_Man_t * pMan ) +{ + int nLevelMax, i; + nLevelMax = 0; + for ( i = 0; i < pMan->nOutputs; i++ ) + nLevelMax = nLevelMax > (int)Fpga_Regular(pMan->pOutputs[i])->Level? + nLevelMax : (int)Fpga_Regular(pMan->pOutputs[i])->Level; + return nLevelMax; +} + + +/**Function************************************************************* + + Synopsis [Analyses choice nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_MappingUpdateLevel_rec( Fpga_Man_t * pMan, Fpga_Node_t * pNode, int fMaximum ) +{ + Fpga_Node_t * pTemp; + int Level1, Level2, LevelE; + assert( !Fpga_IsComplement(pNode) ); + if ( !Fpga_NodeIsAnd(pNode) ) + return pNode->Level; + // skip the visited node + if ( pNode->TravId == pMan->nTravIds ) + return pNode->Level; + pNode->TravId = pMan->nTravIds; + // compute levels of the children nodes + Level1 = Fpga_MappingUpdateLevel_rec( pMan, Fpga_Regular(pNode->p1), fMaximum ); + Level2 = Fpga_MappingUpdateLevel_rec( pMan, Fpga_Regular(pNode->p2), fMaximum ); + pNode->Level = 1 + FPGA_MAX( Level1, Level2 ); + if ( pNode->pNextE ) + { + LevelE = Fpga_MappingUpdateLevel_rec( pMan, pNode->pNextE, fMaximum ); + if ( fMaximum ) + { + if ( pNode->Level < (unsigned)LevelE ) + pNode->Level = LevelE; + } + else + { + if ( pNode->Level > (unsigned)LevelE ) + pNode->Level = LevelE; + } + // set the level of all equivalent nodes to be the same minimum + if ( pNode->pRepr == NULL ) // the primary node + for ( pTemp = pNode->pNextE; pTemp; pTemp = pTemp->pNextE ) + pTemp->Level = pNode->Level; + } + return pNode->Level; +} + +/**Function************************************************************* + + Synopsis [Resets the levels of the nodes in the choice graph.] + + Description [Makes the level of the choice nodes to be equal to the + maximum of the level of the nodes in the equivalence class. This way + sorting by level leads to the reverse topological order, which is + needed for the required time computation.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_MappingSetChoiceLevels( Fpga_Man_t * pMan ) +{ + int i; + pMan->nTravIds++; + for ( i = 0; i < pMan->nOutputs; i++ ) + Fpga_MappingUpdateLevel_rec( pMan, Fpga_Regular(pMan->pOutputs[i]), 1 ); +} + +/**Function************************************************************* + + Synopsis [Reports statistics on choice nodes.] + + Description [The number of choice nodes is the number of primary nodes, + which has pNextE set to a pointer. The number of choices is the number + of entries in the equivalent-node lists of the primary nodes.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_ManReportChoices( Fpga_Man_t * pMan ) +{ + Fpga_Node_t * pNode, * pTemp; + int nChoiceNodes, nChoices; + int i, LevelMax1, LevelMax2; + + // report the number of levels + LevelMax1 = Fpga_GetMaxLevel( pMan ); + pMan->nTravIds++; + for ( i = 0; i < pMan->nOutputs; i++ ) + Fpga_MappingUpdateLevel_rec( pMan, Fpga_Regular(pMan->pOutputs[i]), 0 ); + LevelMax2 = Fpga_GetMaxLevel( pMan ); + + // report statistics about choices + nChoiceNodes = nChoices = 0; + for ( i = 0; i < pMan->vAnds->nSize; i++ ) + { + pNode = pMan->vAnds->pArray[i]; + if ( pNode->pRepr == NULL && pNode->pNextE != NULL ) + { // this is a choice node = the primary node that has equivalent nodes + nChoiceNodes++; + for ( pTemp = pNode; pTemp; pTemp = pTemp->pNextE ) + nChoices++; + } + } + if ( pMan->fVerbose ) + { + printf( "Maximum level: Original = %d. Reduced due to choices = %d.\n", LevelMax1, LevelMax2 ); + printf( "Choice stats: Choice nodes = %d. Total choices = %d.\n", nChoiceNodes, nChoices ); + } +/* + { + FILE * pTable; + pTable = fopen( "stats_choice.txt", "a+" ); + fprintf( pTable, "%s ", pMan->pFileName ); + fprintf( pTable, "%4d ", LevelMax1 ); + fprintf( pTable, "%4d ", pMan->vAnds->nSize - pMan->nInputs ); + fprintf( pTable, "%4d ", LevelMax2 ); + fprintf( pTable, "%7d ", nChoiceNodes ); + fprintf( pTable, "%7d ", nChoices + nChoiceNodes ); + fprintf( pTable, "\n" ); + fclose( pTable ); + } +*/ +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/fpga/fpgaVec.c b/src/map/fpga/fpgaVec.c new file mode 100644 index 00000000..a8c6b983 --- /dev/null +++ b/src/map/fpga/fpgaVec.c @@ -0,0 +1,408 @@ +/**CFile**************************************************************** + + FileName [fpgaVec.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: fpgaVec.c,v 1.3 2005/01/23 06:59:42 alanmi Exp $] + +***********************************************************************/ + +#include "fpgaInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static int Fpga_NodeVecCompareLevels( Fpga_Node_t ** pp1, Fpga_Node_t ** pp2 ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Allocates a vector with the given capacity.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_NodeVec_t * Fpga_NodeVecAlloc( int nCap ) +{ + Fpga_NodeVec_t * p; + p = ALLOC( Fpga_NodeVec_t, 1 ); + if ( nCap > 0 && nCap < 16 ) + nCap = 16; + p->nSize = 0; + p->nCap = nCap; + p->pArray = p->nCap? ALLOC( Fpga_Node_t *, p->nCap ) : NULL; + return p; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_NodeVecFree( Fpga_NodeVec_t * p ) +{ + FREE( p->pArray ); + FREE( p ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Node_t ** Fpga_NodeVecReadArray( Fpga_NodeVec_t * p ) +{ + return p->pArray; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_NodeVecReadSize( Fpga_NodeVec_t * p ) +{ + return p->nSize; +} + +/**Function************************************************************* + + Synopsis [Resizes the vector to the given capacity.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_NodeVecGrow( Fpga_NodeVec_t * p, int nCapMin ) +{ + if ( p->nCap >= nCapMin ) + return; + p->pArray = REALLOC( Fpga_Node_t *, p->pArray, nCapMin ); + p->nCap = nCapMin; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_NodeVecShrink( Fpga_NodeVec_t * p, int nSizeNew ) +{ + assert( p->nSize >= nSizeNew ); + p->nSize = nSizeNew; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_NodeVecClear( Fpga_NodeVec_t * p ) +{ + p->nSize = 0; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_NodeVecPush( Fpga_NodeVec_t * p, Fpga_Node_t * Entry ) +{ + if ( p->nSize == p->nCap ) + { + if ( p->nCap < 16 ) + Fpga_NodeVecGrow( p, 16 ); + else + Fpga_NodeVecGrow( p, 2 * p->nCap ); + } + p->pArray[p->nSize++] = Entry; +} + +/**Function************************************************************* + + Synopsis [Add the element while ensuring uniqueness.] + + Description [Returns 1 if the element was found, and 0 if it was new. ] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_NodeVecPushUnique( Fpga_NodeVec_t * p, Fpga_Node_t * Entry ) +{ + int i; + for ( i = 0; i < p->nSize; i++ ) + if ( p->pArray[i] == Entry ) + return 1; + Fpga_NodeVecPush( p, Entry ); + return 0; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Node_t * Fpga_NodeVecPop( Fpga_NodeVec_t * p ) +{ + return p->pArray[--p->nSize]; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_NodeVecWriteEntry( Fpga_NodeVec_t * p, int i, Fpga_Node_t * Entry ) +{ + assert( i >= 0 && i < p->nSize ); + p->pArray[i] = Entry; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fpga_Node_t * Fpga_NodeVecReadEntry( Fpga_NodeVec_t * p, int i ) +{ + assert( i >= 0 && i < p->nSize ); + return p->pArray[i]; +} + +/**Function************************************************************* + + Synopsis [Comparison procedure for two nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_NodeVecCompareLevels( Fpga_Node_t ** pp1, Fpga_Node_t ** pp2 ) +{ + int Level1 = Fpga_Regular(*pp1)->Level; + int Level2 = Fpga_Regular(*pp2)->Level; + if ( Level1 < Level2 ) + return -1; + if ( Level1 > Level2 ) + return 1; + if ( Fpga_Regular(*pp1)->Num < Fpga_Regular(*pp2)->Num ) + return -1; + if ( Fpga_Regular(*pp1)->Num > Fpga_Regular(*pp2)->Num ) + return 1; + return 0; +} + +/**Function************************************************************* + + Synopsis [Sorting the entries by their integer value.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_NodeVecSortByLevel( Fpga_NodeVec_t * p ) +{ + qsort( (void *)p->pArray, p->nSize, sizeof(Fpga_Node_t *), + (int (*)(const void *, const void *)) Fpga_NodeVecCompareLevels ); +} + +/**Function************************************************************* + + Synopsis [Compares the arrival times.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fpga_NodeVecCompareArrivals( Fpga_Node_t ** ppS1, Fpga_Node_t ** ppS2 ) +{ + if ( (*ppS1)->pCutBest->tArrival < (*ppS2)->pCutBest->tArrival ) + return -1; + if ( (*ppS1)->pCutBest->tArrival > (*ppS2)->pCutBest->tArrival ) + return 1; + return 0; +} + +/**Function************************************************************* + + Synopsis [Orders the nodes in the increasing order of the arrival times.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_SortNodesByArrivalTimes( Fpga_NodeVec_t * p ) +{ + qsort( (void *)p->pArray, p->nSize, sizeof(Fpga_Node_t *), + (int (*)(const void *, const void *)) Fpga_NodeVecCompareArrivals ); +// assert( Fpga_CompareNodesByLevel( p->pArray, p->pArray + p->nSize - 1 ) <= 0 ); +} + + +/**Function************************************************************* + + Synopsis [Computes the union of nodes in two arrays.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_NodeVecUnion( Fpga_NodeVec_t * p, Fpga_NodeVec_t * p1, Fpga_NodeVec_t * p2 ) +{ + int i; + Fpga_NodeVecClear( p ); + for ( i = 0; i < p1->nSize; i++ ) + Fpga_NodeVecPush( p, p1->pArray[i] ); + for ( i = 0; i < p2->nSize; i++ ) + Fpga_NodeVecPush( p, p2->pArray[i] ); +} + +/**Function************************************************************* + + Synopsis [Inserts a new node in the order by arrival times.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_NodeVecPushOrder( Fpga_NodeVec_t * vNodes, Fpga_Node_t * pNode, int fIncreasing ) +{ + Fpga_Node_t * pNode1, * pNode2; + int i; + Fpga_NodeVecPush( vNodes, pNode ); + // find the place of the node + for ( i = vNodes->nSize-1; i > 0; i-- ) + { + pNode1 = vNodes->pArray[i ]; + pNode2 = vNodes->pArray[i-1]; + if ( fIncreasing && pNode1->pCutBest->tArrival >= pNode2->pCutBest->tArrival || + !fIncreasing && pNode1->pCutBest->tArrival <= pNode2->pCutBest->tArrival ) + break; + vNodes->pArray[i ] = pNode2; + vNodes->pArray[i-1] = pNode1; + } +} + +/**Function************************************************************* + + Synopsis [Inserts a new node in the order by arrival times.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fpga_NodeVecReverse( Fpga_NodeVec_t * vNodes ) +{ + Fpga_Node_t * pNode1, * pNode2; + int i; + for ( i = 0; i < vNodes->nSize/2; i++ ) + { + pNode1 = vNodes->pArray[i]; + pNode2 = vNodes->pArray[vNodes->nSize-1-i]; + vNodes->pArray[i] = pNode2; + vNodes->pArray[vNodes->nSize-1-i] = pNode1; + } +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + diff --git a/src/map/fpga/module.make b/src/map/fpga/module.make new file mode 100644 index 00000000..409e4b54 --- /dev/null +++ b/src/map/fpga/module.make @@ -0,0 +1,12 @@ +SRC += src/map/fpga/fpga.c \ + src/map/fpga/fpgaCore.c \ + src/map/fpga/fpgaCreate.c \ + src/map/fpga/fpgaCut.c \ + src/map/fpga/fpgaCutUtils.c \ + src/map/fpga/fpgaFanout.c \ + src/map/fpga/fpgaLib.c \ + src/map/fpga/fpgaMatch.c \ + src/map/fpga/fpgaTime.c \ + src/map/fpga/fpgaTruth.c \ + src/map/fpga/fpgaUtils.c \ + src/map/fpga/fpgaVec.c -- cgit v1.2.3