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/super/module.make | 4 + src/map/super/super.c | 319 ++++++++++ src/map/super/super.h | 51 ++ src/map/super/superAnd.c | 696 ++++++++++++++++++++++ src/map/super/superGENERIC.c | 46 ++ src/map/super/superGate.c | 1324 ++++++++++++++++++++++++++++++++++++++++++ src/map/super/superInt.h | 62 ++ src/map/super/superWrite.c | 76 +++ 8 files changed, 2578 insertions(+) create mode 100644 src/map/super/module.make create mode 100644 src/map/super/super.c create mode 100644 src/map/super/super.h create mode 100644 src/map/super/superAnd.c create mode 100644 src/map/super/superGENERIC.c create mode 100644 src/map/super/superGate.c create mode 100644 src/map/super/superInt.h create mode 100644 src/map/super/superWrite.c (limited to 'src/map/super') diff --git a/src/map/super/module.make b/src/map/super/module.make new file mode 100644 index 00000000..19ce8228 --- /dev/null +++ b/src/map/super/module.make @@ -0,0 +1,4 @@ +SRC += src/map/super/super.c \ + src/map/super/superAnd.c \ + src/map/super/superGate.c \ + src/map/super/superWrite.c diff --git a/src/map/super/super.c b/src/map/super/super.c new file mode 100644 index 00000000..ffb432d5 --- /dev/null +++ b/src/map/super/super.c @@ -0,0 +1,319 @@ +/**CFile**************************************************************** + + FileName [super.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Pre-computation of supergates.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - August 18, 2003.] + + Revision [$Id: super.c,v 1.6 2004/10/30 20:51:11 satrajit Exp $] + +***********************************************************************/ + +#include "superInt.h" +#include "mainInt.h" +#include "mio.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static int Super_CommandSupergates ( Abc_Frame_t * pAbc, int argc, char **argv ); +static int Super_CommandSupergatesAnd( Abc_Frame_t * pAbc, int argc, char **argv ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super_Init( Abc_Frame_t * pAbc ) +{ + Cmd_CommandAdd( pAbc, "SC mapping", "super", Super_CommandSupergates, 0 ); + Cmd_CommandAdd( pAbc, "SC mapping", "super2", Super_CommandSupergatesAnd, 0 ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super_End() +{ +} + + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Super_CommandSupergatesAnd( Abc_Frame_t * pAbc, int argc, char **argv ) +{ + FILE * pOut, * pErr; + int nVarsMax, nLevels; + int fVerbose; + int c; + + pOut = Abc_FrameReadOut(pAbc); + pErr = Abc_FrameReadErr(pAbc); + + // set the defaults + nVarsMax = 4; + nLevels = 3; + fVerbose = 0; + util_getopt_reset(); + while ( (c = util_getopt(argc, argv, "ilvh")) != EOF ) + { + switch (c) + { + case 'i': + nVarsMax = atoi(argv[util_optind]); + util_optind++; + if ( nVarsMax < 0 ) + goto usage; + break; + case 'l': + nLevels = atoi(argv[util_optind]); + util_optind++; + if ( nLevels < 0 ) + goto usage; + break; + case 'v': + fVerbose ^= 1; + break; + case 'h': + goto usage; + break; + default: + goto usage; + } + } + + Super2_Precompute( nVarsMax, nLevels, fVerbose ); + + return 0; + +usage: + fprintf( pErr, "usage: super2 [-i num] [-l num] [-vh]\n"); + fprintf( pErr, "\t precomputes the supergates composed of AND2s and INVs\n" ); + fprintf( pErr, "\t-i num : the max number of inputs to the supergate [default = %d]\n", nVarsMax ); + fprintf( pErr, "\t-l num : the max number of logic levels of gates [default = %d]\n", nLevels ); + fprintf( pErr, "\t-v : enable verbose output\n"); + fprintf( pErr, "\t-h : print the help message\n"); + return 1; /* error exit */ +} + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Super_CommandSupergates( Abc_Frame_t * pAbc, int argc, char **argv ) +{ + FILE * pFile; + FILE * pOut, * pErr; + Mio_Library_t * pLib; + char * FileName, * ExcludeFile; + float DelayLimit; + float AreaLimit; + bool fSkipInvs; + bool fWriteOldFormat; + int nVarsMax, nLevels, TimeLimit; + int fVerbose; + int c; + + pOut = Abc_FrameReadOut(pAbc); + pErr = Abc_FrameReadErr(pAbc); + + // set the defaults + nVarsMax = 5; + nLevels = 3; + DelayLimit = 3.5; + AreaLimit = 9; + TimeLimit = 10; + fSkipInvs = 1; + fVerbose = 0; + fWriteOldFormat = 0; + ExcludeFile = 0; + + util_getopt_reset(); + while ( (c = util_getopt(argc, argv, "eiltdasovh")) != EOF ) + { + switch (c) + { + case 'e': + ExcludeFile = argv[util_optind]; + if ( ExcludeFile == 0 ) + goto usage; + util_optind++; + break; + case 'i': + nVarsMax = atoi(argv[util_optind]); + util_optind++; + if ( nVarsMax < 0 ) + goto usage; + break; + case 'l': + nLevels = atoi(argv[util_optind]); + util_optind++; + if ( nLevels < 0 ) + goto usage; + break; + case 't': + TimeLimit = atoi(argv[util_optind]); + util_optind++; + if ( TimeLimit < 0 ) + goto usage; + break; + case 'd': + DelayLimit = (float)atof(argv[util_optind]); + util_optind++; + if ( DelayLimit <= 0.0 ) + goto usage; + break; + case 'a': + AreaLimit = (float)atof(argv[util_optind]); + util_optind++; + if ( AreaLimit <= 0.0 ) + goto usage; + break; + case 's': + fSkipInvs ^= 1; + break; + case 'o': + fWriteOldFormat ^= 1; + break; + case 'v': + fVerbose ^= 1; + break; + case 'h': + goto usage; + break; + default: + goto usage; + } + } + + + if ( argc != util_optind + 1 ) + { + fprintf( pErr, "The GENLIB library file should be given on the command line.\n" ); + goto usage; + } + + if ( nVarsMax < 2 || nVarsMax > 6 ) + { + fprintf( pErr, "The max number of variables (%d) should be more than 1 and less than 7.\n", nVarsMax ); + goto usage; + } + + // get the input file name + FileName = argv[util_optind]; +// if ( (pFile = Io_FileOpen( FileName, "open_path", "r" )) == NULL ) + 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 = Mio_LibraryRead( pAbc, FileName, ExcludeFile, fVerbose ); + if ( pLib == NULL ) + { + fprintf( pErr, "Reading library has failed.\n" ); + goto usage; + } + + // compute the gates + Super_Precompute( pLib, nVarsMax, nLevels, DelayLimit, AreaLimit, TimeLimit, fSkipInvs, fWriteOldFormat, fVerbose ); + + // delete the library + Mio_LibraryDelete( pLib ); + return 0; + +usage: + fprintf( pErr, "usage: super [-i num] [-l num] [-d float] [-a float] [-t num] [-sovh] \n"); + fprintf( pErr, "\t precomputes the supergates for the given GENLIB library\n" ); + fprintf( pErr, "\t-i num : the max number of supergate inputs [default = %d]\n", nVarsMax ); + fprintf( pErr, "\t-l num : the max number of levels of gates [default = %d]\n", nLevels ); + fprintf( pErr, "\t-d float : the max delay of the supergates [default = %.2f]\n", DelayLimit ); + fprintf( pErr, "\t-a float : the max area of the supergates [default = %.2f]\n", AreaLimit ); + fprintf( pErr, "\t-t num : the approximate runtime limit in seconds [default = %d]\n", TimeLimit ); + fprintf( pErr, "\t-s : toggle the use of inverters at the inputs [default = %s]\n", (fSkipInvs? "no": "yes") ); + fprintf( pErr, "\t-o : toggle dumping the supergate library in old format [default = %s]\n", (fWriteOldFormat? "yes": "no") ); + fprintf( pErr, "\t-e file : file contains list of genlib gates to exclude\n" ); + fprintf( pErr, "\t-v : enable verbose output [default = %s]\n", (fVerbose? "yes" : "no") ); + fprintf( pErr, "\t-h : print the help message\n"); + fprintf( pErr, "\n"); + fprintf( pErr, "\tHere is a piece of advice on precomputing supergate libraries:\n"); + fprintf( pErr, "\t\n"); + fprintf( pErr, "\tStart with the number of inputs equal to 5 (-i 5), the number of \n"); + fprintf( pErr, "\tlevels equal to 3 (-l 3), the delay equal to 2-3 delays of inverter, \n"); + fprintf( pErr, "\tthe area equal to 3-4 areas of two input NAND, and runtime limit equal \n"); + fprintf( pErr, "\tto 10 seconds (-t 10). Run precomputation and learn from the result.\n"); + fprintf( pErr, "\tDetermine what parameter is most constraining and try to increase \n"); + fprintf( pErr, "\tthe value of that parameter. The goal is to have a well-balanced\n"); + fprintf( pErr, "\tset of constraints and the resulting supergate library containing\n"); + fprintf( pErr, "\tapproximately 100K-200K supergates. Typically, it is better to increase\n"); + fprintf( pErr, "\tdelay limit rather than area limit, because having large-area supergates\n"); + fprintf( pErr, "\tmay result in a considerable increase in area.\n"); + fprintf( pErr, "\t\n"); + fprintf( pErr, "\tNote that a good supergate library for experiments typically can be \n"); + fprintf( pErr, "\tprecomputed in 30 sec. Increasing the runtime limit makes sense when\n"); + fprintf( pErr, "\tother parameters are well-balanced and it is needed to enumerate more\n"); + fprintf( pErr, "\tchoices to have a good result. In the end, to compute the final library\n"); + fprintf( pErr, "\tthe runtime can be set to 300 sec to ensure the ultimate quality.\n"); + fprintf( pErr, "\tIn some cases, the runtime has to be reduced if the supergate library\n"); + fprintf( pErr, "\tcontains too many supergates (> 500K).\n"); + fprintf( pErr, "\t\n"); + fprintf( pErr, "\tWhen precomputing libraries of 6 inputs (-i 6), start with even more \n"); + fprintf( pErr, "\trestricted parameters and gradually increase them until the goal is met.\n"); + fprintf( pErr, "\t\n"); + return 1; /* error exit */ +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/super/super.h b/src/map/super/super.h new file mode 100644 index 00000000..ce2b7433 --- /dev/null +++ b/src/map/super/super.h @@ -0,0 +1,51 @@ +/**CFile**************************************************************** + + FileName [super.h] + + PackageName [MVSIS 2.0: Multi-valued logic synthesis system.] + + Synopsis [Pre-computation of supergates (delay-limited gate combinations).] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - September 8, 2003.] + + Revision [$Id: super.h,v 1.3 2004/06/28 14:20:25 alanmi Exp $] + +***********************************************************************/ + +#ifndef __SUPER_H__ +#define __SUPER_H__ + +//////////////////////////////////////////////////////////////////////// +/// INCLUDES /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// PARAMETERS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// STRUCTURE DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// GLOBAL VARIABLES /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// MACRO DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/*=== superCore.c =============================================================*/ + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// +#endif diff --git a/src/map/super/superAnd.c b/src/map/super/superAnd.c new file mode 100644 index 00000000..e90fc76d --- /dev/null +++ b/src/map/super/superAnd.c @@ -0,0 +1,696 @@ +/**CFile**************************************************************** + + FileName [superAnd.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Pre-computation of supergates.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - September 8, 2003.] + + Revision [$Id: superAnd.c,v 1.3 2004/06/28 14:20:25 alanmi Exp $] + +***********************************************************************/ + +#include "superInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +// the bit masks +#define SUPER_MASK(n) ((~((unsigned)0)) >> (32-n)) +#define SUPER_FULL (~((unsigned)0)) + +// data structure for AND2 subgraph precomputation +typedef struct Super2_ManStruct_t_ Super2_Man_t; // manager +typedef struct Super2_LibStruct_t_ Super2_Lib_t; // library +typedef struct Super2_GateStruct_t_ Super2_Gate_t; // supergate + +struct Super2_ManStruct_t_ +{ + Extra_MmFixed_t * pMem; // memory manager for all supergates + stmm_table * tTable; // mapping of truth tables into gates + int nTried; // the total number of tried +}; + +struct Super2_LibStruct_t_ +{ + int i; // used to iterate through the table + int k; // used to iterate through the table + int nInputs; // the number of inputs + int nMints; // the number of minterms + int nLevels; // the number of logic levels + int nGates; // the number of gates in the library + int nGatesAlloc; // the number of allocated places + Super2_Gate_t ** pGates; // the gates themselves + unsigned uMaskBit; // the mask used to determine the compl bit +}; + +struct Super2_GateStruct_t_ +{ + unsigned uTruth; // the truth table of this supergate + Super2_Gate_t * pOne; // the left wing + Super2_Gate_t * pTwo; // the right wing + Super2_Gate_t * pNext; // the next gate in the table +}; + + +// manipulation of complemented attributes +#define Super2_IsComplement(p) (((int)((long) (p) & 01))) +#define Super2_Regular(p) ((Super2_Gate_t *)((unsigned)(p) & ~01)) +#define Super2_Not(p) ((Super2_Gate_t *)((long)(p) ^ 01)) +#define Super2_NotCond(p,c) ((Super2_Gate_t *)((long)(p) ^ (c))) + +// iterating through the gates in the library +#define Super2_LibForEachGate( Lib, Gate ) \ + for ( Lib->i = 0; \ + Lib->i < Lib->nGates && (Gate = Lib->pGates[Lib->i]); \ + Lib->i++ ) +#define Super2_LibForEachGate2( Lib, Gate2 ) \ + for ( Lib->k = 0; \ + Lib->k < Lib->i && (Gate2 = Lib->pGates[Lib->k]); \ + Lib->k++ ) + +// static functions +static Super2_Man_t * Super2_ManStart(); +static void Super2_ManStop( Super2_Man_t * pMan ); +static Super2_Lib_t * Super2_LibStart(); +static Super2_Lib_t * Super2_LibDup( Super2_Lib_t * pLib ); +static void Super2_LibStop( Super2_Lib_t * pLib ); +static void Super2_LibAddGate( Super2_Lib_t * pLib, Super2_Gate_t * pGate ); +static Super2_Lib_t * Super2_LibFirst( Super2_Man_t * pMan, int nInputs ); +static Super2_Lib_t * Super2_LibCompute( Super2_Man_t * pMan, Super2_Lib_t * pLib ); + +static void Super2_LibWrite( Super2_Lib_t * pLib ); +static void Super2_LibWriteGate( FILE * pFile, Super2_Lib_t * pLib, Super2_Gate_t * pGate ); +static char * Super2_LibWriteGate_rec( Super2_Gate_t * pGate, int fInv, int Level ); +static int Super2_LibWriteCompare( char * pStr1, char * pStr2 ); +static int Super2_LibCompareGates( Super2_Gate_t ** ppG1, Super2_Gate_t ** ppG2 ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Precomputes the library of AND2 gates.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super2_Precompute( int nInputs, int nLevels, int fVerbose ) +{ + Super2_Man_t * pMan; + Super2_Lib_t * pLibCur, * pLibNext; + int Level; + int clk; + + assert( nInputs < 6 ); + + // start the manager + pMan = Super2_ManStart(); + + // get the starting supergates + pLibCur = Super2_LibFirst( pMan, nInputs ); + + // perform the computation of supergates +printf( "Computing supergates for %d inputs and %d levels:\n", nInputs, nLevels ); + for ( Level = 1; Level <= nLevels; Level++ ) + { +clk = clock(); + pLibNext = Super2_LibCompute( pMan, pLibCur ); + pLibNext->nLevels = Level; + Super2_LibStop( pLibCur ); + pLibCur = pLibNext; +printf( "Level %d: Tried = %7d. Computed = %7d. ", Level, pMan->nTried, pLibCur->nGates ); +PRT( "Runtime", clock() - clk ); +fflush( stdout ); + } + +printf( "Writing the output file...\n" ); +fflush( stdout ); + // write them into a file + Super2_LibWrite( pLibCur ); + Super2_LibStop( pLibCur ); + + // stop the manager + Super2_ManStop( pMan ); +} + + + + +/**Function************************************************************* + + Synopsis [Starts the manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Super2_Man_t * Super2_ManStart() +{ + Super2_Man_t * pMan; + pMan = ALLOC( Super2_Man_t, 1 ); + memset( pMan, 0, sizeof(Super2_Man_t) ); + pMan->pMem = Extra_MmFixedStart( sizeof(Super2_Gate_t) ); + pMan->tTable = stmm_init_table( st_ptrcmp, st_ptrhash ); + return pMan; +} + +/**Function************************************************************* + + Synopsis [Stops the manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super2_ManStop( Super2_Man_t * pMan ) +{ + Extra_MmFixedStop( pMan->pMem, 0 ); + stmm_free_table( pMan->tTable ); + free( pMan ); +} + +/**Function************************************************************* + + Synopsis [Starts the library.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Super2_Lib_t * Super2_LibStart() +{ + Super2_Lib_t * pLib; + pLib = ALLOC( Super2_Lib_t, 1 ); + memset( pLib, 0, sizeof(Super2_Lib_t) ); + return pLib; +} + +/**Function************************************************************* + + Synopsis [Duplicates the library.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Super2_Lib_t * Super2_LibDup( Super2_Lib_t * pLib ) +{ + Super2_Lib_t * pLibNew; + pLibNew = Super2_LibStart(); + pLibNew->nInputs = pLib->nInputs; + pLibNew->nMints = pLib->nMints; + pLibNew->nLevels = pLib->nLevels; + pLibNew->nGates = pLib->nGates; + pLibNew->uMaskBit = pLib->uMaskBit; + pLibNew->nGatesAlloc = 1000 + pLib->nGatesAlloc; + pLibNew->pGates = ALLOC( Super2_Gate_t *, pLibNew->nGatesAlloc ); + memcpy( pLibNew->pGates, pLib->pGates, pLibNew->nGates * sizeof(Super2_Gate_t *) ); + return pLibNew; +} + +/**Function************************************************************* + + Synopsis [Add gate to the library.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super2_LibAddGate( Super2_Lib_t * pLib, Super2_Gate_t * pGate ) +{ + if ( pLib->nGates == pLib->nGatesAlloc ) + { + pLib->pGates = REALLOC( Super2_Gate_t *, pLib->pGates, 3 * pLib->nGatesAlloc ); + pLib->nGatesAlloc *= 3; + } + pLib->pGates[ pLib->nGates++ ] = pGate; +} + +/**Function************************************************************* + + Synopsis [Stops the library.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super2_LibStop( Super2_Lib_t * pLib ) +{ + free( pLib->pGates ); + free( pLib ); +} + +/**Function************************************************************* + + Synopsis [Derives the starting supergates.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Super2_Lib_t * Super2_LibFirst( Super2_Man_t * pMan, int nInputs ) +{ + Super2_Lib_t * pLib; + int v, m; + + // start the library + pLib = Super2_LibStart(); + + // create the starting supergates + pLib->nInputs = nInputs; + pLib->nMints = (1 << nInputs); + pLib->nLevels = 0; + pLib->nGates = nInputs + 1; + pLib->nGatesAlloc = nInputs + 1; + pLib->uMaskBit = (1 << (pLib->nMints-1)); + pLib->pGates = ALLOC( Super2_Gate_t *, nInputs + 1 ); + // add the constant 0 + pLib->pGates[0] = (Super2_Gate_t *)Extra_MmFixedEntryFetch( pMan->pMem ); + memset( pLib->pGates[0], 0, sizeof(Super2_Gate_t) ); + // add the elementary gates + for ( v = 0; v < nInputs; v++ ) + { + pLib->pGates[v+1] = (Super2_Gate_t *)Extra_MmFixedEntryFetch( pMan->pMem ); + memset( pLib->pGates[v+1], 0, sizeof(Super2_Gate_t) ); + pLib->pGates[v+1]->pTwo = (Super2_Gate_t *)v; + } + + // set up their truth tables + for ( m = 0; m < pLib->nMints; m++ ) + for ( v = 0; v < nInputs; v++ ) + if ( m & (1 << v) ) + pLib->pGates[v+1]->uTruth |= (1 << m); + return pLib; +} + +/**Function************************************************************* + + Synopsis [Precomputes one level of supergates.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Super2_Lib_t * Super2_LibCompute( Super2_Man_t * pMan, Super2_Lib_t * pLib ) +{ + Super2_Lib_t * pLibNew; + Super2_Gate_t * pGate1, * pGate2, * pGateNew; + Super2_Gate_t ** ppGate; + unsigned Mask = SUPER_MASK(pLib->nMints); + unsigned uTruth, uTruthR, uTruth1, uTruth2, uTruth1c, uTruth2c; + + // start the new library + pLibNew = Super2_LibDup( pLib ); + + // reset the hash table + stmm_free_table( pMan->tTable ); + pMan->tTable = stmm_init_table( st_ptrcmp, st_ptrhash ); + // set the starting things into the hash table + Super2_LibForEachGate( pLibNew, pGate1 ) + { + uTruthR = ((pGate1->uTruth & pLibNew->uMaskBit)? Mask & ~pGate1->uTruth : pGate1->uTruth); + + if ( stmm_lookup( pMan->tTable, (char *)uTruthR, (char **)&pGate2 ) ) + { + printf( "New gate:\n" ); + Super2_LibWriteGate( stdout, pLibNew, pGate1 ); + printf( "Gate in the table:\n" ); + Super2_LibWriteGate( stdout, pLibNew, pGate2 ); + assert( 0 ); + } + stmm_insert( pMan->tTable, (char *)uTruthR, (char *)pGate1 ); + } + + + // set the number of gates tried + pMan->nTried = pLibNew->nGates; + + // go through the gate pairs + Super2_LibForEachGate( pLib, pGate1 ) + { + if ( pLib->i && pLib->i % 300 == 0 ) + { + printf( "Tried %5d first gates...\n", pLib->i ); + fflush( stdout ); + } + + Super2_LibForEachGate2( pLib, pGate2 ) + { + uTruth1 = pGate1->uTruth; + uTruth2 = pGate2->uTruth; + uTruth1c = Mask & ~uTruth1; + uTruth2c = Mask & ~uTruth2; + + // none complemented + uTruth = uTruth1 & uTruth2; + uTruthR = ((uTruth & pLibNew->uMaskBit)? Mask & ~uTruth : uTruth); + + if ( !stmm_find_or_add( pMan->tTable, (char *)uTruthR, (char ***)&ppGate ) ) + { + pGateNew = (Super2_Gate_t *)Extra_MmFixedEntryFetch( pMan->pMem ); + pGateNew->pOne = pGate1; + pGateNew->pTwo = pGate2; + pGateNew->uTruth = uTruth; + *ppGate = pGateNew; + Super2_LibAddGate( pLibNew, pGateNew ); + } + + // one complemented + uTruth = uTruth1c & uTruth2; + uTruthR = ((uTruth & pLibNew->uMaskBit)? Mask & ~uTruth : uTruth); + + if ( !stmm_find_or_add( pMan->tTable, (char *)uTruthR, (char ***)&ppGate ) ) + { + pGateNew = (Super2_Gate_t *)Extra_MmFixedEntryFetch( pMan->pMem ); + pGateNew->pOne = Super2_Not(pGate1); + pGateNew->pTwo = pGate2; + pGateNew->uTruth = uTruth; + *ppGate = pGateNew; + Super2_LibAddGate( pLibNew, pGateNew ); + } + + // another complemented + uTruth = uTruth1 & uTruth2c; + uTruthR = ((uTruth & pLibNew->uMaskBit)? Mask & ~uTruth : uTruth); + + if ( !stmm_find_or_add( pMan->tTable, (char *)uTruthR, (char ***)&ppGate ) ) + { + pGateNew = (Super2_Gate_t *)Extra_MmFixedEntryFetch( pMan->pMem ); + pGateNew->pOne = pGate1; + pGateNew->pTwo = Super2_Not(pGate2); + pGateNew->uTruth = uTruth; + *ppGate = pGateNew; + Super2_LibAddGate( pLibNew, pGateNew ); + } + + // both complemented + uTruth = uTruth1c & uTruth2c; + uTruthR = ((uTruth & pLibNew->uMaskBit)? Mask & ~uTruth : uTruth); + + if ( !stmm_find_or_add( pMan->tTable, (char *)uTruthR, (char ***)&ppGate ) ) + { + pGateNew = (Super2_Gate_t *)Extra_MmFixedEntryFetch( pMan->pMem ); + pGateNew->pOne = Super2_Not(pGate1); + pGateNew->pTwo = Super2_Not(pGate2); + pGateNew->uTruth = uTruth; + *ppGate = pGateNew; + Super2_LibAddGate( pLibNew, pGateNew ); + } + + pMan->nTried += 4; + } + } + return pLibNew; +} + + +static unsigned s_uMaskBit; +static unsigned s_uMaskAll; + +/**Function************************************************************* + + Synopsis [Writes the library into the file.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super2_LibWrite( Super2_Lib_t * pLib ) +{ + Super2_Gate_t * pGate; + FILE * pFile; + char FileName[100]; + int clk; + + if ( pLib->nLevels > 5 ) + { + printf( "Cannot write file for %d levels.\n", pLib->nLevels ); + return; + } + +clk = clock(); + // sort the supergates by truth table + s_uMaskBit = pLib->uMaskBit; + s_uMaskAll = SUPER_MASK(pLib->nMints); + qsort( (void *)pLib->pGates, pLib->nGates, sizeof(Super2_Gate_t *), + (int (*)(const void *, const void *)) Super2_LibCompareGates ); + assert( Super2_LibCompareGates( pLib->pGates, pLib->pGates + pLib->nGates - 1 ) < 0 ); +PRT( "Sorting", clock() - clk ); + + + // start the file + sprintf( FileName, "superI%dL%d", pLib->nInputs, pLib->nLevels ); + pFile = fopen( FileName, "w" ); + fprintf( pFile, "# AND2/INV supergates derived on %s.\n", Extra_TimeStamp() ); + fprintf( pFile, "# Command line: \"super2 -i %d -l %d\".\n", pLib->nInputs, pLib->nLevels ); + fprintf( pFile, "# The number of inputs = %6d.\n", pLib->nInputs ); + fprintf( pFile, "# The number of levels = %6d.\n", pLib->nLevels ); + fprintf( pFile, "# The number of supergates = %6d.\n", pLib->nGates ); + fprintf( pFile, "# The total functions = %6d.\n", (1<<(pLib->nMints-1)) ); + fprintf( pFile, "\n" ); + fprintf( pFile, "%6d\n", pLib->nGates ); + + // print the gates + Super2_LibForEachGate( pLib, pGate ) + Super2_LibWriteGate( pFile, pLib, pGate ); + fclose( pFile ); + + printf( "The supergates are written into file \"%s\" ", FileName ); + printf( "(%0.2f Mb).\n", ((double)Extra_FileSize(FileName))/(1<<20) ); +} + +/**Function************************************************************* + + Synopsis [Writes the gate into the file.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Super2_LibCompareGates( Super2_Gate_t ** ppG1, Super2_Gate_t ** ppG2 ) +{ + Super2_Gate_t * pG1 = *ppG1; + Super2_Gate_t * pG2 = *ppG2; + unsigned uTruth1, uTruth2; + + uTruth1 = (pG1->uTruth & s_uMaskBit)? s_uMaskAll & ~pG1->uTruth : pG1->uTruth; + uTruth2 = (pG2->uTruth & s_uMaskBit)? s_uMaskAll & ~pG2->uTruth : pG2->uTruth; + + if ( uTruth1 < uTruth2 ) + return -1; + return 1; +} + +/**Function************************************************************* + + Synopsis [Writes the gate into the file.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super2_LibWriteGate( FILE * pFile, Super2_Lib_t * pLib, Super2_Gate_t * pGate ) +{ +// unsigned uTruthR; + unsigned uTruth; + int fInv; + + // check whether the gate need complementation + fInv = (int)(pGate->uTruth & pLib->uMaskBit); + uTruth = (fInv? ~pGate->uTruth : pGate->uTruth); +/* + // reverse the truth table + uTruthR = 0; + for ( m = 0; m < pLib->nMints; m++ ) + if ( uTruth & (1 << m) ) + uTruthR |= (1 << (pLib->nMints-1-m)); +*/ + // write the truth table + Extra_PrintBinary( pFile, &uTruth, pLib->nMints ); + fprintf( pFile, " " ); + // write the symbolic expression + fprintf( pFile, "%s", Super2_LibWriteGate_rec( pGate, fInv, pLib->nLevels ) ); + fprintf( pFile, "\n" ); +} + + +/**Function************************************************************* + + Synopsis [Recursively writes the gate into the file.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +char * Super2_LibWriteGate_rec( Super2_Gate_t * pGate, int fInv, int Level ) +{ + static char Buff01[ 3], Buff02[ 3]; // Max0 = 1 + static char Buff11[ 6], Buff12[ 6]; // Max1 = 2*Max0 + 2 = 4 + static char Buff21[ 12], Buff22[ 12]; // Max2 = 2*Max1 + 2 = 10 + static char Buff31[ 25], Buff32[ 25]; // Max3 = 2*Max2 + 2 = 22 + static char Buff41[ 50], Buff42[ 50]; // Max4 = 2*Max3 + 2 = 46 + static char Buff51[100], Buff52[100]; // Max5 = 2*Max4 + 2 = 94 + static char * pBuffs1[6] = { Buff01, Buff11, Buff21, Buff31, Buff41, Buff51 }; + static char * pBuffs2[6] = { Buff02, Buff12, Buff22, Buff32, Buff42, Buff52 }; + char * pBranch; + char * pBuffer1 = pBuffs1[Level]; + char * pBuffer2 = pBuffs2[Level]; + Super2_Gate_t * pGateNext1, * pGateNext2; + int fInvNext1, fInvNext2; + int RetValue; + + // consider the last level + assert( Level >= 0 ); + if ( pGate->pOne == NULL ) + { + if ( pGate->uTruth == 0 ) + { + pBuffer1[0] = (fInv? '1': '0'); + pBuffer1[1] = '$'; + pBuffer1[2] = 0; + } + else + { + pBuffer1[0] = (fInv? 'A' + ((int)pGate->pTwo): 'a' + ((int)pGate->pTwo)); + pBuffer1[1] = 0; + } + return pBuffer1; + } + assert( Level > 0 ); + + + // get the left branch + pGateNext1 = Super2_Regular(pGate->pOne); + fInvNext1 = Super2_IsComplement(pGate->pOne); + pBranch = Super2_LibWriteGate_rec(pGateNext1, fInvNext1, Level - 1); + // copy into Buffer1 + strcpy( pBuffer1, pBranch ); + + // get the right branch + pGateNext2 = Super2_Regular(pGate->pTwo); + fInvNext2 = Super2_IsComplement(pGate->pTwo); + pBranch = Super2_LibWriteGate_rec(pGateNext2, fInvNext2, Level - 1); + + // consider the case when comparison is not necessary + if ( fInvNext1 ^ fInvNext2 ) + { + if ( fInvNext1 > fInvNext2 ) + sprintf( pBuffer2, "%c%s%s%c", (fInv? '<': '('), pBuffer1, pBranch, (fInv? '>': ')') ); + else + sprintf( pBuffer2, "%c%s%s%c", (fInv? '<': '('), pBranch, pBuffer1, (fInv? '>': ')') ); + } + else + { + // compare the two branches + RetValue = Super2_LibWriteCompare( pBuffer1, pBranch ); + if ( RetValue == 1 ) + sprintf( pBuffer2, "%c%s%s%c", (fInv? '<': '('), pBuffer1, pBranch, (fInv? '>': ')') ); + else // if ( RetValue == -1 ) + { + sprintf( pBuffer2, "%c%s%s%c", (fInv? '<': '('), pBranch, pBuffer1, (fInv? '>': ')') ); + if ( RetValue == 0 ) + printf( "Strange!\n" ); + } + } + return pBuffer2; +} + +/**Function************************************************************* + + Synopsis [Compares the two branches of the tree.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Super2_LibWriteCompare( char * pStr1, char * pStr2 ) +{ + while ( 1 ) + { + // skip extra symbols + while ( *pStr1 && *pStr1 < 'A' ) + pStr1++; + while ( *pStr2 && *pStr2 < 'A' ) + pStr2++; + + // check if any one is finished + if ( *pStr1 == 0 || *pStr2 == 0 ) + { + if ( *pStr2 ) + return 1; + return -1; + } + + // compare + if ( *pStr1 == *pStr2 ) + { + pStr1++; + pStr2++; + } + else + { + if ( *pStr1 < *pStr2 ) + return 1; + return -1; + } + } + return 0; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/super/superGENERIC.c b/src/map/super/superGENERIC.c new file mode 100644 index 00000000..4c7b67ca --- /dev/null +++ b/src/map/super/superGENERIC.c @@ -0,0 +1,46 @@ +/**CFile**************************************************************** + + FileName [super__.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Pre-computation of supergates.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - September 8, 2003.] + + Revision [$Id: super__.h,v 1.0 2003/09/08 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "superInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/super/superGate.c b/src/map/super/superGate.c new file mode 100644 index 00000000..d0cd0ad7 --- /dev/null +++ b/src/map/super/superGate.c @@ -0,0 +1,1324 @@ +/**CFile**************************************************************** + + FileName [superGate.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Pre-computation of supergates.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - September 8, 2003.] + + Revision [$Id: superGate.c,v 1.7 2004/08/03 00:11:40 satrajit Exp $] + +***********************************************************************/ + +#include "superInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +// the bit masks +#define SUPER_MASK(n) ((~((unsigned)0)) >> (32-(n))) +#define SUPER_FULL (~((unsigned)0)) +#define SUPER_NO_VAR (-9999.0) +#define SUPER_EPSILON (0.001) + +// data structure for supergate precomputation +typedef struct Super_ManStruct_t_ Super_Man_t; // manager +typedef struct Super_GateStruct_t_ Super_Gate_t; // supergate + +struct Super_ManStruct_t_ +{ + // parameters + char * pName; // the original genlib file name + int nVarsMax; // the number of inputs + int nMints; // the number of minterms + int nLevels; // the number of logic levels + float tDelayMax; // the max delay of the supergates in the library + float tAreaMax; // the max area of the supergates in the library + int fSkipInv; // the flag says about skipping inverters + int fWriteOldFormat; // in addition, writes the file in the old format + int fVerbose; + + // supergates + Super_Gate_t * pInputs[10]; // the input supergates + int nGates; // the number of gates in the library + Super_Gate_t ** pGates; // the gates themselves + stmm_table * tTable; // mapping of truth tables into gates + + // memory managers + Extra_MmFixed_t * pMem; // memory manager for the supergates + Extra_MmFlex_t * pMemFlex; // memory manager for the fanin arrays + + // statistics + int nTried; // the total number of tried + int nAdded; // the number of entries added + int nRemoved; // the number of entries removed + int nUnique; // the number of unique gates + int nLookups; // the number of hash table lookups + int nAliases; // the number of hash table lookups thrown away due to aliasing + + // runtime + int Time; // the runtime of the generation procedure + int TimeLimit; // the runtime limit (in seconds) + int TimeSec; // the time passed (in seconds) + int TimeStop; // the time to stop computation (in miliseconds) + int TimePrint; // the time to print message +}; + +struct Super_GateStruct_t_ +{ + Mio_Gate_t * pRoot; // the root gate for this supergate + unsigned fVar : 1; // the flag signaling the elementary variable + unsigned fSuper : 1; // the flag signaling the elementary variable + unsigned nFanins : 6; // the number of fanin gates + unsigned Number : 24; // the number assigned in the process + unsigned uTruth[2]; // the truth table of this supergate + Super_Gate_t * pFanins[6]; // the fanins of the gate + float Area; // the area of this gate + float ptDelays[6]; // the pin-to-pin delays for all inputs + float tDelayMax; // the maximum delay + Super_Gate_t * pNext; // the next gate in the table +}; + + +// iterating through the gates in the library +#define Super_ManForEachGate( GateArray, Limit, Index, Gate ) \ + for ( Index = 0; \ + Index < Limit && (Gate = GateArray[Index]); \ + Index++ ) + +// static functions +static Super_Man_t * Super_ManStart(); +static void Super_ManStop( Super_Man_t * pMan ); + +static void Super_AddGateToTable( Super_Man_t * pMan, Super_Gate_t * pGate ); +static void Super_First( Super_Man_t * pMan, int nVarsMax ); +static Super_Man_t * Super_Compute( Super_Man_t * pMan, Mio_Gate_t ** ppGates, int nGates, bool fSkipInv ); +static Super_Gate_t * Super_CreateGateNew( Super_Man_t * pMan, Mio_Gate_t * pRoot, Super_Gate_t ** pSupers, int nSupers, unsigned uTruth[], float Area, float tPinDelaysRes[], float tDelayMax, int nPins ); +static bool Super_CompareGates( Super_Man_t * pMan, unsigned uTruth[], float Area, float tPinDelaysRes[], int nPins ); +static int Super_DelayCompare( Super_Gate_t ** ppG1, Super_Gate_t ** ppG2 ); +static int Super_AreaCompare( Super_Gate_t ** ppG1, Super_Gate_t ** ppG2 ); +static void Super_TranferGatesToArray( Super_Man_t * pMan ); +static int Super_CheckTimeout( ProgressBar * pPro, Super_Man_t * pMan ); + +static void Super_Write( Super_Man_t * pMan ); +static int Super_WriteCompare( Super_Gate_t ** ppG1, Super_Gate_t ** ppG2 ); +static void Super_WriteFileHeader( Super_Man_t * pMan, FILE * pFile ); + +static void Super_WriteLibrary( Super_Man_t * pMan ); +static void Super_WriteLibraryGate( FILE * pFile, Super_Man_t * pMan, Super_Gate_t * pGate, int Num ); +static char * Super_WriteLibraryGateName( Super_Gate_t * pGate ); +static void Super_WriteLibraryGateName_rec( Super_Gate_t * pGate, char * pBuffer ); + +static void Super_WriteLibraryTree( Super_Man_t * pMan ); +static void Super_WriteLibraryTree_rec( FILE * pFile, Super_Man_t * pMan, Super_Gate_t * pSuper, int * pCounter ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Precomputes the library of supergates.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super_Precompute( Mio_Library_t * pLibGen, int nVarsMax, int nLevels, float tDelayMax, float tAreaMax, int TimeLimit, bool fSkipInv, bool fWriteOldFormat, int fVerbose ) +{ + Super_Man_t * pMan; + Mio_Gate_t ** ppGates; + int nGates, Level, clk, clockStart; + + assert( nVarsMax < 7 ); + + // get the root gates + ppGates = Mio_CollectRoots( pLibGen, nVarsMax, tDelayMax, 0, &nGates ); + + // start the manager + pMan = Super_ManStart(); + pMan->pName = Mio_LibraryReadName(pLibGen); + pMan->fSkipInv = fSkipInv; + pMan->tDelayMax = tDelayMax; + pMan->tAreaMax = tAreaMax; + pMan->TimeLimit = TimeLimit; // in seconds + pMan->TimeStop = TimeLimit * CLOCKS_PER_SEC + clock(); // in CPU ticks + pMan->fWriteOldFormat = fWriteOldFormat; + pMan->fVerbose = fVerbose; + + if ( nGates == 0 ) + { + fprintf( stderr, "Error: No genlib gates satisfy the limits criteria. Stop.\n"); + fprintf( stderr, "Limits: max delay = %.2f, max area = %.2f, time limit = %d sec.\n", + pMan->tDelayMax, pMan->tAreaMax, pMan->TimeLimit ); + + // stop the manager + Super_ManStop( pMan ); + free( ppGates ); + + return; + } + + // get the starting supergates + Super_First( pMan, nVarsMax ); + + // perform the computation of supergates + clockStart = clock(); +if ( fVerbose ) +{ + printf( "Computing supergates with %d inputs and %d levels.\n", + pMan->nVarsMax, nLevels ); + printf( "Limits: max delay = %.2f, max area = %.2f, time limit = %d sec.\n", + pMan->tDelayMax, pMan->tAreaMax, pMan->TimeLimit ); +} + + for ( Level = 1; Level <= nLevels; Level++ ) + { + if ( clock() > pMan->TimeStop ) + break; +clk = clock(); + Super_Compute( pMan, ppGates, nGates, fSkipInv ); + pMan->nLevels = Level; +if ( fVerbose ) +{ + printf( "Lev %d: Try =%12d. Add =%6d. Rem =%5d. Save =%6d. Lookups =%12d. Aliases =%12d. ", + Level, pMan->nTried, pMan->nAdded, pMan->nRemoved, pMan->nAdded - pMan->nRemoved, pMan->nLookups, pMan->nAliases ); +PRT( "Time", clock() - clk ); +fflush( stdout ); +} + } + pMan->Time = clock() - clockStart; + +if ( fVerbose ) +{ +printf( "Writing the output file...\n" ); +fflush( stdout ); +} + // write them into a file + Super_Write( pMan ); + + // stop the manager + Super_ManStop( pMan ); + free( ppGates ); +} + + +/**Function************************************************************* + + Synopsis [Derives the starting supergates.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super_First( Super_Man_t * pMan, int nVarsMax ) +{ + Super_Gate_t * pSuper; + int nMintLimit, nVarLimit; + int v, m; + // set the parameters + pMan->nVarsMax = nVarsMax; + pMan->nMints = (1 << nVarsMax); + pMan->nLevels = 0; + // allocate room for the gates + pMan->nGates = nVarsMax; + pMan->pGates = ALLOC( Super_Gate_t *, nVarsMax + 2 ); + // create the gates corresponding to the elementary variables + for ( v = 0; v < nVarsMax; v++ ) + { + // get a new gate + pSuper = (Super_Gate_t *)Extra_MmFixedEntryFetch( pMan->pMem ); + memset( pSuper, 0, sizeof(Super_Gate_t) ); + // assign the elementary variable, the truth table, and the delays + pSuper->fVar = 1; + pSuper->Number = v; + for ( m = 0; m < nVarsMax; m++ ) + pSuper->ptDelays[m] = SUPER_NO_VAR; + pSuper->ptDelays[v] = 0.0; + // set the gate + pMan->pGates[v] = pSuper; + Super_AddGateToTable( pMan, pSuper ); + pMan->pInputs[v] = pSuper; + } + // set up their truth tables + nVarLimit = (nVarsMax >= 5)? 5 : nVarsMax; + nMintLimit = (1 << nVarLimit); + for ( m = 0; m < nMintLimit; m++ ) + for ( v = 0; v < nVarLimit; v++ ) + if ( m & (1 << v) ) + pMan->pGates[v]->uTruth[0] |= (1 << m); + // make adjustments for the case of 6 variables + if ( nVarsMax == 6 ) + { + for ( v = 0; v < 5; v++ ) + pMan->pGates[v]->uTruth[1] = pMan->pGates[v]->uTruth[0]; + pMan->pGates[5]->uTruth[0] = 0; + pMan->pGates[5]->uTruth[1] = ~((unsigned)0); + } + else + { + for ( v = 0; v < nVarsMax; v++ ) + pMan->pGates[v]->uTruth[1] = 0; + } +} + +/**Function************************************************************* + + Synopsis [Precomputes one level of supergates.] + + Description [This procedure computes the set of supergates that can be + derived from the given set of root gates (from GENLIB library) by composing + the root gates with the currently available supergates. This procedure is + smart in the sense that it tries to avoid useless emuration by imposing + tight bounds by area and delay. Only the supergates and are guaranteed to + have smaller area and delay are enumereated. See comments below for details.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Super_Man_t * Super_Compute( Super_Man_t * pMan, Mio_Gate_t ** ppGates, int nGates, bool fSkipInv ) +{ + Super_Gate_t * pSupers[6], * pGate0, * pGate1, * pGate2, * pGate3, * pGate4, * pGate5, * pGateNew; + float tPinDelaysRes[6], * ptPinDelays[6], tPinDelayMax, tDelayMio; + float Area, Area0, Area1, Area2, Area3, Area4, AreaMio; + unsigned uTruth[2], uTruths[6][2]; + int i0, i1, i2, i3, i4, i5; + Super_Gate_t ** ppGatesLimit; + int nFanins, nGatesLimit, k, s, t; + ProgressBar * pProgress; + int fTimeOut; + int fPrune = 1; // Shall we prune? + int iPruneLimit = 3; // Each of the gates plugged into the root gate will have + // less than these many fanins + int iPruneLimitRoot = 4; // The root gate may have only less than these many fanins + + // put the gates from the unique table into the array + // the gates from the array will be used to compose other gates + // the gates in tbe table are used to check uniqueness of collected gates + Super_TranferGatesToArray( pMan ); + + // sort the gates in the increasing order of maximum delay + if ( pMan->nGates > 10000 ) + { + printf( "Sorting array of %d supergates...\r", pMan->nGates ); + fflush( stdout ); + } + qsort( (void *)pMan->pGates, pMan->nGates, sizeof(Super_Gate_t *), + (int (*)(const void *, const void *)) Super_DelayCompare ); + assert( Super_DelayCompare( pMan->pGates, pMan->pGates + pMan->nGates - 1 ) <= 0 ); + if ( pMan->nGates > 10000 ) + { + printf( " \r" ); + } + + pProgress = Extra_ProgressBarStart( stdout, pMan->TimeLimit ); + pMan->TimePrint = clock() + CLOCKS_PER_SEC; + ppGatesLimit = ALLOC( Super_Gate_t *, pMan->nGates ); + // go through the root gates + // the root gates are sorted in the increasing gelay + fTimeOut = 0; + for ( k = 0; k < nGates; k++ ) + { + if ( fTimeOut ) break; + + if ( fPrune ) + { + if ( pMan->nLevels >= 1 ) // First level gates have been computed + { + if ( Mio_GateReadInputs(ppGates[k]) >= iPruneLimitRoot ) + continue; + } + } + + // select the subset of gates to be considered with this root gate + // all the gates past this point will lead to delay larger than the limit + tDelayMio = (float)Mio_GateReadDelayMax(ppGates[k]); + for ( s = 0, t = 0; s < pMan->nGates; s++ ) + { + if ( fPrune && ( pMan->nLevels >= 1 ) && ( ((int)pMan->pGates[s]->nFanins) >= iPruneLimit )) + continue; + + ppGatesLimit[t] = pMan->pGates[s]; + if ( ppGatesLimit[t++]->tDelayMax + tDelayMio > pMan->tDelayMax ) + break; + } + nGatesLimit = t; + + if ( pMan->fVerbose ) + { + printf ("Trying %d choices for %d inputs\n", t, Mio_GateReadInputs(ppGates[k]) ); + } + + // resort part of this range by area + // now we can prune the search by going up in the list until we reach the limit on area + // all the gates beyond this point can be skipped because their area can be only larger + if ( nGatesLimit > 10000 ) + printf( "Sorting array of %d supergates...\r", nGatesLimit ); + qsort( (void *)ppGatesLimit, nGatesLimit, sizeof(Super_Gate_t *), + (int (*)(const void *, const void *)) Super_AreaCompare ); + assert( Super_AreaCompare( ppGatesLimit, ppGatesLimit + nGatesLimit - 1 ) <= 0 ); + if ( nGatesLimit > 10000 ) + printf( " \r" ); + + // consider the combinations of gates with the root gate on top + AreaMio = (float)Mio_GateReadArea(ppGates[k]); + nFanins = Mio_GateReadInputs(ppGates[k]); + switch ( nFanins ) + { + case 0: // should not happen + assert( 0 ); + break; + case 1: // interter root + Super_ManForEachGate( ppGatesLimit, nGatesLimit, i0, pGate0 ) + { + if ( fTimeOut ) break; + fTimeOut = Super_CheckTimeout( pProgress, pMan ); + // skip the inverter as the root gate before the elementary variable + // as a result, the supergates will not have inverters on the input side + // but inverters still may occur at the output of or inside complex supergates + if ( fSkipInv && pGate0->tDelayMax == 0 ) + continue; + // compute area + Area = AreaMio + pGate0->Area; + if ( Area > pMan->tAreaMax ) + break; + + pSupers[0] = pGate0; uTruths[0][0] = pGate0->uTruth[0]; uTruths[0][1] = pGate0->uTruth[1]; ptPinDelays[0] = pGate0->ptDelays; + Mio_DeriveGateDelays( ppGates[k], ptPinDelays, nFanins, pMan->nVarsMax, SUPER_NO_VAR, tPinDelaysRes, &tPinDelayMax ); + Mio_DeriveTruthTable( ppGates[k], uTruths, nFanins, pMan->nVarsMax, uTruth ); + if ( !Super_CompareGates( pMan, uTruth, Area, tPinDelaysRes, pMan->nVarsMax ) ) + continue; + // create a new gate + pGateNew = Super_CreateGateNew( pMan, ppGates[k], pSupers, nFanins, uTruth, Area, tPinDelaysRes, tPinDelayMax, pMan->nVarsMax ); + Super_AddGateToTable( pMan, pGateNew ); + } + break; + case 2: // two-input root gate + Super_ManForEachGate( ppGatesLimit, nGatesLimit, i0, pGate0 ) + { + Area0 = AreaMio + pGate0->Area; + if ( Area0 > pMan->tAreaMax ) + break; + pSupers[0] = pGate0; uTruths[0][0] = pGate0->uTruth[0]; uTruths[0][1] = pGate0->uTruth[1]; ptPinDelays[0] = pGate0->ptDelays; + Super_ManForEachGate( ppGatesLimit, nGatesLimit, i1, pGate1 ) + if ( i1 != i0 ) + { + if ( fTimeOut ) goto done; + fTimeOut = Super_CheckTimeout( pProgress, pMan ); + // compute area + Area = Area0 + pGate1->Area; + if ( Area > pMan->tAreaMax ) + break; + + pSupers[1] = pGate1; uTruths[1][0] = pGate1->uTruth[0]; uTruths[1][1] = pGate1->uTruth[1]; ptPinDelays[1] = pGate1->ptDelays; + Mio_DeriveGateDelays( ppGates[k], ptPinDelays, nFanins, pMan->nVarsMax, SUPER_NO_VAR, tPinDelaysRes, &tPinDelayMax ); + Mio_DeriveTruthTable( ppGates[k], uTruths, nFanins, pMan->nVarsMax, uTruth ); + if ( !Super_CompareGates( pMan, uTruth, Area, tPinDelaysRes, pMan->nVarsMax ) ) + continue; + // create a new gate + pGateNew = Super_CreateGateNew( pMan, ppGates[k], pSupers, nFanins, uTruth, Area, tPinDelaysRes, tPinDelayMax, pMan->nVarsMax ); + Super_AddGateToTable( pMan, pGateNew ); + } + } + break; + case 3: // three-input root gate + Super_ManForEachGate( ppGatesLimit, nGatesLimit, i0, pGate0 ) + { + Area0 = AreaMio + pGate0->Area; + if ( Area0 > pMan->tAreaMax ) + break; + pSupers[0] = pGate0; uTruths[0][0] = pGate0->uTruth[0]; uTruths[0][1] = pGate0->uTruth[1]; ptPinDelays[0] = pGate0->ptDelays; + + Super_ManForEachGate( ppGatesLimit, nGatesLimit, i1, pGate1 ) + if ( i1 != i0 ) + { + Area1 = Area0 + pGate1->Area; + if ( Area1 > pMan->tAreaMax ) + break; + pSupers[1] = pGate1; uTruths[1][0] = pGate1->uTruth[0]; uTruths[1][1] = pGate1->uTruth[1]; ptPinDelays[1] = pGate1->ptDelays; + + Super_ManForEachGate( ppGatesLimit, nGatesLimit, i2, pGate2 ) + if ( i2 != i0 && i2 != i1 ) + { + if ( fTimeOut ) goto done; + fTimeOut = Super_CheckTimeout( pProgress, pMan ); + // compute area + Area = Area1 + pGate2->Area; + if ( Area > pMan->tAreaMax ) + break; + pSupers[2] = pGate2; uTruths[2][0] = pGate2->uTruth[0]; uTruths[2][1] = pGate2->uTruth[1]; ptPinDelays[2] = pGate2->ptDelays; + + Mio_DeriveGateDelays( ppGates[k], ptPinDelays, nFanins, pMan->nVarsMax, SUPER_NO_VAR, tPinDelaysRes, &tPinDelayMax ); + Mio_DeriveTruthTable( ppGates[k], uTruths, nFanins, pMan->nVarsMax, uTruth ); + if ( !Super_CompareGates( pMan, uTruth, Area, tPinDelaysRes, pMan->nVarsMax ) ) + continue; + // create a new gate + pGateNew = Super_CreateGateNew( pMan, ppGates[k], pSupers, nFanins, uTruth, Area, tPinDelaysRes, tPinDelayMax, pMan->nVarsMax ); + Super_AddGateToTable( pMan, pGateNew ); + } + } + } + break; + case 4: // four-input root gate + Super_ManForEachGate( ppGatesLimit, nGatesLimit, i0, pGate0 ) + { + Area0 = AreaMio + pGate0->Area; + if ( Area0 > pMan->tAreaMax ) + break; + pSupers[0] = pGate0; uTruths[0][0] = pGate0->uTruth[0]; uTruths[0][1] = pGate0->uTruth[1]; ptPinDelays[0] = pGate0->ptDelays; + + Super_ManForEachGate( ppGatesLimit, nGatesLimit, i1, pGate1 ) + if ( i1 != i0 ) + { + Area1 = Area0 + pGate1->Area; + if ( Area1 > pMan->tAreaMax ) + break; + pSupers[1] = pGate1; uTruths[1][0] = pGate1->uTruth[0]; uTruths[1][1] = pGate1->uTruth[1]; ptPinDelays[1] = pGate1->ptDelays; + + Super_ManForEachGate( ppGatesLimit, nGatesLimit, i2, pGate2 ) + if ( i2 != i0 && i2 != i1 ) + { + Area2 = Area1 + pGate2->Area; + if ( Area2 > pMan->tAreaMax ) + break; + pSupers[2] = pGate2; uTruths[2][0] = pGate2->uTruth[0]; uTruths[2][1] = pGate2->uTruth[1]; ptPinDelays[2] = pGate2->ptDelays; + + Super_ManForEachGate( ppGatesLimit, nGatesLimit, i3, pGate3 ) + if ( i3 != i0 && i3 != i1 && i3 != i2 ) + { + if ( fTimeOut ) goto done; + fTimeOut = Super_CheckTimeout( pProgress, pMan ); + // compute area + Area = Area2 + pGate3->Area; + if ( Area > pMan->tAreaMax ) + break; + pSupers[3] = pGate3; uTruths[3][0] = pGate3->uTruth[0]; uTruths[3][1] = pGate3->uTruth[1]; ptPinDelays[3] = pGate3->ptDelays; + + Mio_DeriveGateDelays( ppGates[k], ptPinDelays, nFanins, pMan->nVarsMax, SUPER_NO_VAR, tPinDelaysRes, &tPinDelayMax ); + Mio_DeriveTruthTable( ppGates[k], uTruths, nFanins, pMan->nVarsMax, uTruth ); + if ( !Super_CompareGates( pMan, uTruth, Area, tPinDelaysRes, pMan->nVarsMax ) ) + continue; + // create a new gate + pGateNew = Super_CreateGateNew( pMan, ppGates[k], pSupers, nFanins, uTruth, Area, tPinDelaysRes, tPinDelayMax, pMan->nVarsMax ); + Super_AddGateToTable( pMan, pGateNew ); + } + } + } + } + break; + case 5: // five-input root gate + Super_ManForEachGate( ppGatesLimit, nGatesLimit, i0, pGate0 ) + { + Area0 = AreaMio + pGate0->Area; + if ( Area0 > pMan->tAreaMax ) + break; + pSupers[0] = pGate0; uTruths[0][0] = pGate0->uTruth[0]; uTruths[0][1] = pGate0->uTruth[1]; ptPinDelays[0] = pGate0->ptDelays; + + Super_ManForEachGate( ppGatesLimit, nGatesLimit, i1, pGate1 ) + if ( i1 != i0 ) + { + Area1 = Area0 + pGate1->Area; + if ( Area1 > pMan->tAreaMax ) + break; + pSupers[1] = pGate1; uTruths[1][0] = pGate1->uTruth[0]; uTruths[1][1] = pGate1->uTruth[1]; ptPinDelays[1] = pGate1->ptDelays; + + Super_ManForEachGate( ppGatesLimit, nGatesLimit, i2, pGate2 ) + if ( i2 != i0 && i2 != i1 ) + { + Area2 = Area1 + pGate2->Area; + if ( Area2 > pMan->tAreaMax ) + break; + pSupers[2] = pGate2; uTruths[2][0] = pGate2->uTruth[0]; uTruths[2][1] = pGate2->uTruth[1]; ptPinDelays[2] = pGate2->ptDelays; + + Super_ManForEachGate( ppGatesLimit, nGatesLimit, i3, pGate3 ) + if ( i3 != i0 && i3 != i1 && i3 != i2 ) + { + Area3 = Area2 + pGate3->Area; + if ( Area3 > pMan->tAreaMax ) + break; + pSupers[3] = pGate3; uTruths[3][0] = pGate3->uTruth[0]; uTruths[3][1] = pGate3->uTruth[1]; ptPinDelays[3] = pGate3->ptDelays; + + Super_ManForEachGate( ppGatesLimit, nGatesLimit, i4, pGate4 ) + if ( i4 != i0 && i4 != i1 && i4 != i2 && i4 != i3 ) + { + if ( fTimeOut ) goto done; + fTimeOut = Super_CheckTimeout( pProgress, pMan ); + // compute area + Area = Area3 + pGate4->Area; + if ( Area > pMan->tAreaMax ) + break; + pSupers[4] = pGate4; uTruths[4][0] = pGate4->uTruth[0]; uTruths[4][1] = pGate4->uTruth[1]; ptPinDelays[4] = pGate4->ptDelays; + + Mio_DeriveGateDelays( ppGates[k], ptPinDelays, nFanins, pMan->nVarsMax, SUPER_NO_VAR, tPinDelaysRes, &tPinDelayMax ); + Mio_DeriveTruthTable( ppGates[k], uTruths, nFanins, pMan->nVarsMax, uTruth ); + if ( !Super_CompareGates( pMan, uTruth, Area, tPinDelaysRes, pMan->nVarsMax ) ) + continue; + // create a new gate + pGateNew = Super_CreateGateNew( pMan, ppGates[k], pSupers, nFanins, uTruth, Area, tPinDelaysRes, tPinDelayMax, pMan->nVarsMax ); + Super_AddGateToTable( pMan, pGateNew ); + } + } + } + } + } + break; + case 6: // six-input root gate + Super_ManForEachGate( ppGatesLimit, nGatesLimit, i0, pGate0 ) + { + Area0 = AreaMio + pGate0->Area; + if ( Area0 > pMan->tAreaMax ) + break; + pSupers[0] = pGate0; uTruths[0][0] = pGate0->uTruth[0]; uTruths[0][1] = pGate0->uTruth[1]; ptPinDelays[0] = pGate0->ptDelays; + + Super_ManForEachGate( ppGatesLimit, nGatesLimit, i1, pGate1 ) + if ( i1 != i0 ) + { + Area1 = Area0 + pGate1->Area; + if ( Area1 > pMan->tAreaMax ) + break; + pSupers[1] = pGate1; uTruths[1][0] = pGate1->uTruth[0]; uTruths[1][1] = pGate1->uTruth[1]; ptPinDelays[1] = pGate1->ptDelays; + + Super_ManForEachGate( ppGatesLimit, nGatesLimit, i2, pGate2 ) + if ( i2 != i0 && i2 != i1 ) + { + Area2 = Area1 + pGate2->Area; + if ( Area2 > pMan->tAreaMax ) + break; + pSupers[2] = pGate2; uTruths[2][0] = pGate2->uTruth[0]; uTruths[2][1] = pGate2->uTruth[1]; ptPinDelays[2] = pGate2->ptDelays; + + Super_ManForEachGate( ppGatesLimit, nGatesLimit, i3, pGate3 ) + if ( i3 != i0 && i3 != i1 && i3 != i2 ) + { + Area3 = Area2 + pGate3->Area; + if ( Area3 > pMan->tAreaMax ) + break; + pSupers[3] = pGate3; uTruths[3][0] = pGate3->uTruth[0]; uTruths[3][1] = pGate3->uTruth[1]; ptPinDelays[3] = pGate3->ptDelays; + + Super_ManForEachGate( ppGatesLimit, nGatesLimit, i4, pGate4 ) + if ( i4 != i0 && i4 != i1 && i4 != i2 && i4 != i3 ) + { + if ( fTimeOut ) break; + fTimeOut = Super_CheckTimeout( pProgress, pMan ); + // compute area + Area4 = Area3 + pGate4->Area; + if ( Area > pMan->tAreaMax ) + break; + pSupers[4] = pGate4; uTruths[4][0] = pGate4->uTruth[0]; uTruths[4][1] = pGate4->uTruth[1]; ptPinDelays[4] = pGate4->ptDelays; + + Super_ManForEachGate( ppGatesLimit, nGatesLimit, i5, pGate5 ) + if ( i5 != i0 && i5 != i1 && i5 != i2 && i5 != i3 && i5 != i4 ) + { + if ( fTimeOut ) goto done; + fTimeOut = Super_CheckTimeout( pProgress, pMan ); + // compute area + Area = Area4 + pGate5->Area; + if ( Area > pMan->tAreaMax ) + break; + pSupers[5] = pGate5; uTruths[5][0] = pGate5->uTruth[0]; uTruths[5][1] = pGate5->uTruth[1]; ptPinDelays[5] = pGate5->ptDelays; + + Mio_DeriveGateDelays( ppGates[k], ptPinDelays, nFanins, pMan->nVarsMax, SUPER_NO_VAR, tPinDelaysRes, &tPinDelayMax ); + Mio_DeriveTruthTable( ppGates[k], uTruths, nFanins, pMan->nVarsMax, uTruth ); + if ( !Super_CompareGates( pMan, uTruth, Area, tPinDelaysRes, pMan->nVarsMax ) ) + continue; + // create a new gate + pGateNew = Super_CreateGateNew( pMan, ppGates[k], pSupers, nFanins, uTruth, Area, tPinDelaysRes, tPinDelayMax, pMan->nVarsMax ); + Super_AddGateToTable( pMan, pGateNew ); + } + } + } + } + } + } + break; + default : + assert( 0 ); + break; + } + } +done: + Extra_ProgressBarStop( pProgress ); + free( ppGatesLimit ); + return pMan; +} + +/**Function************************************************************* + + Synopsis [Transfers gates from table into the array.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Super_CheckTimeout( ProgressBar * pPro, Super_Man_t * pMan ) +{ + int TimeNow = clock(); + if ( TimeNow > pMan->TimePrint ) + { + Extra_ProgressBarUpdate( pPro, ++pMan->TimeSec, NULL ); + pMan->TimePrint = clock() + CLOCKS_PER_SEC; + } + if ( TimeNow > pMan->TimeStop ) + { + printf ("Timeout!\n"); + return 1; + } + pMan->nTried++; + return 0; +} + + +/**Function************************************************************* + + Synopsis [Transfers gates from table into the array.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super_TranferGatesToArray( Super_Man_t * pMan ) +{ + stmm_generator * gen; + Super_Gate_t * pGate, * pList; + unsigned Key; + + // put the gates fron the table into the array + free( pMan->pGates ); + pMan->pGates = ALLOC( Super_Gate_t *, pMan->nAdded ); + pMan->nGates = 0; + stmm_foreach_item( pMan->tTable, gen, (char **)&Key, (char **)&pList ) + { + for ( pGate = pList; pGate; pGate = pGate->pNext ) + pMan->pGates[ pMan->nGates++ ] = pGate; + } +// assert( pMan->nGates == pMan->nAdded - pMan->nRemoved ); +} + +/**Function************************************************************* + + Synopsis [Adds one supergate into the unique table.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super_AddGateToTable( Super_Man_t * pMan, Super_Gate_t * pGate ) +{ + Super_Gate_t ** ppList; + unsigned Key; +// Key = pGate->uTruth[0] + 2003 * pGate->uTruth[1]; + Key = pGate->uTruth[0] ^ pGate->uTruth[1]; + if ( !stmm_find_or_add( pMan->tTable, (char *)Key, (char ***)&ppList ) ) + *ppList = NULL; + pGate->pNext = *ppList; + *ppList = pGate; + pMan->nAdded++; +} + +/**Function************************************************************* + + Synopsis [Check the manager's unique table for comparable gates.] + + Description [Returns 0 if the gate is dominated by others. Returns 1 + if the gate is new or is better than the available ones. In this case, + cleans the table by removing the gates that are worse than the given one.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +bool Super_CompareGates( Super_Man_t * pMan, unsigned uTruth[], float Area, float tPinDelaysRes[], int nPins ) +{ + Super_Gate_t ** ppList, * pPrev, * pGate, * pGate2; + int i, fNewIsBetter, fGateIsBetter; + unsigned Key; + + // skip constant functions + if ( pMan->nVarsMax < 6 ) + { + if ( uTruth[0] == 0 || ~uTruth[0] == 0 ) + return 0; + } + else + { + if ( ( uTruth[0] == 0 && uTruth[1] == 0 ) || ( ~uTruth[0] == 0 && ~uTruth[1] == 0 ) ) + return 0; + } + + // get hold of the place where the entry is stored +// Key = uTruth[0] + 2003 * uTruth[1]; + Key = uTruth[0] ^ uTruth[1]; + if ( !stmm_find( pMan->tTable, (char *)Key, (char ***)&ppList ) ) + return 1; + // the entry with this truth table is found + pPrev = NULL; + for ( pGate = *ppList, pGate2 = pGate? pGate->pNext: NULL; pGate; + pGate = pGate2, pGate2 = pGate? pGate->pNext: NULL ) + { + pMan->nLookups++; + if ( pGate->uTruth[0] != uTruth[0] || pGate->uTruth[1] != uTruth[1] ) + { + pMan->nAliases++; + continue; + } + fGateIsBetter = 0; + fNewIsBetter = 0; + if ( pGate->Area + SUPER_EPSILON < Area ) + fGateIsBetter = 1; + else if ( pGate->Area > Area + SUPER_EPSILON ) + fNewIsBetter = 1; + for ( i = 0; i < nPins; i++ ) + { + if ( pGate->ptDelays[i] == SUPER_NO_VAR || tPinDelaysRes[i] == SUPER_NO_VAR ) + continue; + if ( pGate->ptDelays[i] + SUPER_EPSILON < tPinDelaysRes[i] ) + fGateIsBetter = 1; + else if ( pGate->ptDelays[i] > tPinDelaysRes[i] + SUPER_EPSILON ) + fNewIsBetter = 1; + if ( fGateIsBetter && fNewIsBetter ) + break; + } + // consider 4 cases + if ( fGateIsBetter && fNewIsBetter ) // Pareto points; save both + pPrev = pGate; + else if ( fNewIsBetter ) // gate is worse; remove the gate + { + if ( pPrev == NULL ) + *ppList = pGate->pNext; + else + pPrev->pNext = pGate->pNext; + Extra_MmFixedEntryRecycle( pMan->pMem, (char *)pGate ); + pMan->nRemoved++; + } + else if ( fGateIsBetter ) // new is worse, already dominated no need to see others + return 0; + else // if ( !fGateIsBetter && !fNewIsBetter ) // they are identical, no need to see others + return 0; + } + return 1; +} + + +/**Function************************************************************* + + Synopsis [Create a new supergate.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Super_Gate_t * Super_CreateGateNew( Super_Man_t * pMan, Mio_Gate_t * pRoot, Super_Gate_t ** pSupers, int nSupers, + unsigned uTruth[], float Area, float tPinDelaysRes[], float tDelayMax, int nPins ) +{ + Super_Gate_t * pSuper; + pSuper = (Super_Gate_t *)Extra_MmFixedEntryFetch( pMan->pMem ); + memset( pSuper, 0, sizeof(Super_Gate_t) ); + pSuper->pRoot = pRoot; + pSuper->uTruth[0] = uTruth[0]; + pSuper->uTruth[1] = uTruth[1]; + memcpy( pSuper->ptDelays, tPinDelaysRes, sizeof(float) * nPins ); + pSuper->Area = Area; + pSuper->nFanins = nSupers; + memcpy( pSuper->pFanins, pSupers, sizeof(Super_Gate_t *) * nSupers ); + pSuper->pNext = NULL; + pSuper->tDelayMax = tDelayMax; + return pSuper; +} + +/**Function************************************************************* + + Synopsis [Starts the manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Super_Man_t * Super_ManStart() +{ + Super_Man_t * pMan; + pMan = ALLOC( Super_Man_t, 1 ); + memset( pMan, 0, sizeof(Super_Man_t) ); + pMan->pMem = Extra_MmFixedStart( sizeof(Super_Gate_t) ); + pMan->tTable = stmm_init_table( st_ptrcmp, st_ptrhash ); + return pMan; +} + +/**Function************************************************************* + + Synopsis [Stops the manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super_ManStop( Super_Man_t * pMan ) +{ + Extra_MmFixedStop( pMan->pMem, 0 ); + if ( pMan->tTable ) stmm_free_table( pMan->tTable ); + FREE( pMan->pGates ); + free( pMan ); +} + + + + + +/**Function************************************************************* + + Synopsis [Writes the supergate library into the file.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super_Write( Super_Man_t * pMan ) +{ + Super_Gate_t * pGateRoot, * pGate; + stmm_generator * gen; + int fZeroFound, clk, v; + unsigned Key; + + if ( pMan->nGates < 1 ) + { + printf( "The generated library is empty. No output file written.\n" ); + return; + } + + // Filters the supergates by removing those that have fewer inputs than + // the given limit, provided that the inputs are not consequtive. + // For example, NAND2(a,c) is removed, but NAND2(a,b) is left, + // because a and b are consequtive. + FREE( pMan->pGates ); + pMan->pGates = ALLOC( Super_Gate_t *, pMan->nAdded ); + pMan->nGates = 0; + stmm_foreach_item( pMan->tTable, gen, (char **)&Key, (char **)&pGateRoot ) + { + for ( pGate = pGateRoot; pGate; pGate = pGate->pNext ) + { + // skip the elementary variables + if ( pGate->pRoot == NULL ) + continue; + // skip the non-consequtive gates + fZeroFound = 0; + for ( v = 0; v < pMan->nVarsMax; v++ ) + if ( pGate->ptDelays[v] < SUPER_NO_VAR + SUPER_EPSILON ) + fZeroFound = 1; + else if ( fZeroFound ) + break; + if ( v < pMan->nVarsMax ) + continue; + // save the unique gate + pMan->pGates[ pMan->nGates++ ] = pGate; + } + } + +clk = clock(); + // sort the supergates by truth table + qsort( (void *)pMan->pGates, pMan->nGates, sizeof(Super_Gate_t *), + (int (*)(const void *, const void *)) Super_WriteCompare ); + assert( Super_WriteCompare( pMan->pGates, pMan->pGates + pMan->nGates - 1 ) <= 0 ); +if ( pMan->fVerbose ) +{ +PRT( "Sorting", clock() - clk ); +} + + + // write library in the old format +clk = clock(); + if ( pMan->fWriteOldFormat ) + Super_WriteLibrary( pMan ); +if ( pMan->fVerbose ) +{ +PRT( "Writing old format", clock() - clk ); +} + + // write the tree-like structure of supergates +clk = clock(); + Super_WriteLibraryTree( pMan ); +if ( pMan->fVerbose ) +{ +PRT( "Writing new format", clock() - clk ); +} +} + + +/**Function************************************************************* + + Synopsis [Writes the file header.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super_WriteFileHeader( Super_Man_t * pMan, FILE * pFile ) +{ + fprintf( pFile, "#\n" ); + fprintf( pFile, "# Supergate library derived for \"%s\" on %s.\n", pMan->pName, Extra_TimeStamp() ); + fprintf( pFile, "#\n" ); + fprintf( pFile, "# Command line: \"super -i %d -l %d -d %.2f -a %.2f -t %d %s %s\".\n", + pMan->nVarsMax, pMan->nLevels, pMan->tDelayMax, pMan->tAreaMax, pMan->TimeLimit, (pMan->fSkipInv? "" : "-s"), pMan->pName ); + fprintf( pFile, "#\n" ); + fprintf( pFile, "# The number of inputs = %10d.\n", pMan->nVarsMax ); + fprintf( pFile, "# The number of levels = %10d.\n", pMan->nLevels ); + fprintf( pFile, "# The maximum delay = %10.2f.\n", pMan->tDelayMax ); + fprintf( pFile, "# The maximum area = %10.2f.\n", pMan->tAreaMax ); + fprintf( pFile, "# The maximum runtime (sec) = %10d.\n", pMan->TimeLimit ); + fprintf( pFile, "#\n" ); + fprintf( pFile, "# The number of attempts = %10d.\n", pMan->nTried ); + fprintf( pFile, "# The number of supergates = %10d.\n", pMan->nGates ); + fprintf( pFile, "# The number of functions = %10d.\n", pMan->nUnique ); + fprintf( pFile, "# The total functions = %.0f (2^%d).\n", pow(2,pMan->nMints), pMan->nMints ); + fprintf( pFile, "#\n" ); + fprintf( pFile, "# Generation time (sec) = %10.2f.\n", (float)(pMan->Time)/(float)(CLOCKS_PER_SEC) ); + fprintf( pFile, "#\n" ); + fprintf( pFile, "%s\n", pMan->pName ); + fprintf( pFile, "%d\n", pMan->nVarsMax ); + fprintf( pFile, "%d\n", pMan->nGates ); +} + +/**Function************************************************************* + + Synopsis [Compares the truth tables of two gates.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Super_WriteCompare( Super_Gate_t ** ppG1, Super_Gate_t ** ppG2 ) +{ + unsigned * pTruth1 = (*ppG1)->uTruth; + unsigned * pTruth2 = (*ppG2)->uTruth; + if ( pTruth1[1] < pTruth2[1] ) + return -1; + if ( pTruth1[1] > pTruth2[1] ) + return 1; + if ( pTruth1[0] < pTruth2[0] ) + return -1; + if ( pTruth1[0] > pTruth2[0] ) + return 1; + return 0; +} + +/**Function************************************************************* + + Synopsis [Compares the max delay of two gates.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Super_DelayCompare( Super_Gate_t ** ppG1, Super_Gate_t ** ppG2 ) +{ + if ( (*ppG1)->tDelayMax < (*ppG2)->tDelayMax ) + return -1; + if ( (*ppG1)->tDelayMax > (*ppG2)->tDelayMax ) + return 1; + return 0; +} + +/**Function************************************************************* + + Synopsis [Compares the area of two gates.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Super_AreaCompare( Super_Gate_t ** ppG1, Super_Gate_t ** ppG2 ) +{ + if ( (*ppG1)->Area < (*ppG2)->Area ) + return -1; + if ( (*ppG1)->Area > (*ppG2)->Area ) + return 1; + return 0; +} + + + + + + +/**Function************************************************************* + + Synopsis [Writes the gates into the file.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super_WriteLibrary( Super_Man_t * pMan ) +{ + Super_Gate_t * pGate, * pGateNext; + FILE * pFile; + char FileName[100]; + char * pNameGeneric; + int i, Counter; + + // get the file name + pNameGeneric = Extra_FileNameGeneric( pMan->pName ); + sprintf( FileName, "%s.super_old", pNameGeneric ); + free( pNameGeneric ); + + // count the number of unique functions + pMan->nUnique = 1; + Super_ManForEachGate( pMan->pGates, pMan->nGates, i, pGate ) + { + if ( i == pMan->nGates - 1 ) + break; + // print the newline if this gate is different from the following one + pGateNext = pMan->pGates[i+1]; + if ( pGateNext->uTruth[0] != pGate->uTruth[0] || pGateNext->uTruth[1] != pGate->uTruth[1] ) + pMan->nUnique++; + } + + // start the file + pFile = fopen( FileName, "w" ); + Super_WriteFileHeader( pMan, pFile ); + + // print the gates + Counter = 0; + Super_ManForEachGate( pMan->pGates, pMan->nGates, i, pGate ) + { + Super_WriteLibraryGate( pFile, pMan, pGate, ++Counter ); + if ( i == pMan->nGates - 1 ) + break; + // print the newline if this gate is different from the following one + pGateNext = pMan->pGates[i+1]; + if ( pGateNext->uTruth[0] != pGate->uTruth[0] || pGateNext->uTruth[1] != pGate->uTruth[1] ) + fprintf( pFile, "\n" ); + } + assert( Counter == pMan->nGates ); + fclose( pFile ); + +if ( pMan->fVerbose ) +{ + printf( "The supergates are written using old format \"%s\" ", FileName ); + printf( "(%0.3f Mb).\n", ((double)Extra_FileSize(FileName))/(1<<20) ); +} +} + +/**Function************************************************************* + + Synopsis [Writes the supergate into the file.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super_WriteLibraryGate( FILE * pFile, Super_Man_t * pMan, Super_Gate_t * pGate, int Num ) +{ + int i; + fprintf( pFile, "%04d ", Num ); // the number + Extra_PrintBinary( pFile, pGate->uTruth, pMan->nMints ); // the truth table + fprintf( pFile, " %5.2f", pGate->tDelayMax ); // the max delay + fprintf( pFile, " " ); + for ( i = 0; i < pMan->nVarsMax; i++ ) // the pin-to-pin delays + fprintf( pFile, " %5.2f", pGate->ptDelays[i]==SUPER_NO_VAR? 0.0 : pGate->ptDelays[i] ); + fprintf( pFile, " %5.2f", pGate->Area ); // the area + fprintf( pFile, " " ); + fprintf( pFile, "%s", Super_WriteLibraryGateName(pGate) ); // the symbolic expression + fprintf( pFile, "\n" ); +} + +/**Function************************************************************* + + Synopsis [Recursively generates symbolic name of the supergate.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +char * Super_WriteLibraryGateName( Super_Gate_t * pGate ) +{ + static char Buffer[2000]; + Buffer[0] = 0; + Super_WriteLibraryGateName_rec( pGate, Buffer ); + return Buffer; +} + +/**Function************************************************************* + + Synopsis [Recursively generates symbolic name of the supergate.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super_WriteLibraryGateName_rec( Super_Gate_t * pGate, char * pBuffer ) +{ + char Buffer[10]; + int i; + + if ( pGate->pRoot == NULL ) + { + sprintf( Buffer, "%c", 'a' + pGate->Number ); + strcat( pBuffer, Buffer ); + return; + } + strcat( pBuffer, Mio_GateReadName(pGate->pRoot) ); + strcat( pBuffer, "(" ); + for ( i = 0; i < (int)pGate->nFanins; i++ ) + { + if ( i ) + strcat( pBuffer, "," ); + Super_WriteLibraryGateName_rec( pGate->pFanins[i], pBuffer ); + } + strcat( pBuffer, ")" ); +} + + + + + +/**Function************************************************************* + + Synopsis [Recursively writes the gates.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super_WriteLibraryTree( Super_Man_t * pMan ) +{ + Super_Gate_t * pSuper; + FILE * pFile; + char FileName[100]; + char * pNameGeneric; + int i, Counter; + int posStart; + + // get the file name + pNameGeneric = Extra_FileNameGeneric( pMan->pName ); + sprintf( FileName, "%s.super", pNameGeneric ); + free( pNameGeneric ); + + // write the elementary variables + pFile = fopen( FileName, "w" ); + Super_WriteFileHeader( pMan, pFile ); + // write the place holder for the number of lines + posStart = ftell( pFile ); + fprintf( pFile, " \n" ); + // mark the real supergates + Super_ManForEachGate( pMan->pGates, pMan->nGates, i, pSuper ) + pSuper->fSuper = 1; + // write the supergates + Counter = pMan->nVarsMax; + Super_ManForEachGate( pMan->pGates, pMan->nGates, i, pSuper ) + Super_WriteLibraryTree_rec( pFile, pMan, pSuper, &Counter ); + fclose( pFile ); + // write the number of lines + pFile = fopen( FileName, "rb+" ); + fseek( pFile, posStart, SEEK_SET ); + fprintf( pFile, "%d", Counter ); + fclose( pFile ); + +if ( pMan->fVerbose ) +{ + printf( "The supergates are written using new format \"%s\" ", FileName ); + printf( "(%0.3f Mb).\n", ((double)Extra_FileSize(FileName))/(1<<20) ); +} +} + +/**Function************************************************************* + + Synopsis [Recursively writes the gate.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super_WriteLibraryTree_rec( FILE * pFile, Super_Man_t * pMan, Super_Gate_t * pSuper, int * pCounter ) +{ + int nFanins, i; + // skip an elementary variable and a gate that was already written + if ( pSuper->fVar || pSuper->Number > 0 ) + return; + // write the fanins + nFanins = Mio_GateReadInputs(pSuper->pRoot); + for ( i = 0; i < nFanins; i++ ) + Super_WriteLibraryTree_rec( pFile, pMan, pSuper->pFanins[i], pCounter ); + // finally write the gate + pSuper->Number = (*pCounter)++; + fprintf( pFile, "%s", pSuper->fSuper? "* " : "" ); + fprintf( pFile, "%s", Mio_GateReadName(pSuper->pRoot) ); + for ( i = 0; i < nFanins; i++ ) + fprintf( pFile, " %d", pSuper->pFanins[i]->Number ); + // write the formula + // this step is optional, the resulting library will work in any case + // however, it may be helpful to for debugging to compare the same library + // written in the old format and written in the new format with formulas +// fprintf( pFile, " # %s", Super_WriteLibraryGateName( pSuper ) ); + fprintf( pFile, "\n" ); +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + diff --git a/src/map/super/superInt.h b/src/map/super/superInt.h new file mode 100644 index 00000000..686c8739 --- /dev/null +++ b/src/map/super/superInt.h @@ -0,0 +1,62 @@ +/**CFile**************************************************************** + + FileName [superInt.h] + + PackageName [MVSIS 2.0: Multi-valued logic synthesis system.] + + Synopsis [Pre-computation of supergates.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - September 8, 2003.] + + Revision [$Id: superInt.h,v 1.4 2004/07/06 04:55:59 alanmi Exp $] + +***********************************************************************/ + +#ifndef __super_INT_H__ +#define __super_INT_H__ + +//////////////////////////////////////////////////////////////////////// +/// INCLUDES /// +//////////////////////////////////////////////////////////////////////// + +#include "abc.h" +#include "mainInt.h" +#include "mvc.h" +#include "mio.h" +#include "stmm.h" +#include "super.h" + +//////////////////////////////////////////////////////////////////////// +/// PARAMETERS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// STRUCTURE DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// GLOBAL VARIABLES /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// MACRO DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/*=== superAnd.c =============================================================*/ +extern void Super2_Precompute( int nInputs, int nLevels, int fVerbose ); +/*=== superGate.c =============================================================*/ +extern void Super_Precompute( Mio_Library_t * pLibGen, int nInputs, int nLevels, float tDelayMax, float tAreaMax, int TimeLimit, bool fSkipInv, bool fWriteOldFormat, int fVerbose ); + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + +#endif diff --git a/src/map/super/superWrite.c b/src/map/super/superWrite.c new file mode 100644 index 00000000..a0e85604 --- /dev/null +++ b/src/map/super/superWrite.c @@ -0,0 +1,76 @@ +/**CFile**************************************************************** + + FileName [superWrite.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Pre-computation of supergates.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - September 8, 2003.] + + Revision [$Id: superWrite.c,v 1.1 2004/04/03 01:36:45 alanmi Exp $] + +***********************************************************************/ + +#include "superInt.h" + +/* + One record in the supergate library file consists of: + + + + is a zero-based integer + is a string of 2^n bits representing the value of the function for each minterm + is the maximum delay of the gate + is the array of n double values + is a floating point value + is the string representing the gate in the following format: + GATENAME1( GATENAME2( a, c ), GATENAME3( a, d ), ... ) + The gate names (GATENAME1, etc) are the names as they appear in the .genlib library. + The primary inputs of the gates are denoted by lowercase chars 'a', 'b', etc. + The parantheses are mandatory for each gate, except for the wire. + The wire name can be omitted, so that "a" can be used instead of "**wire**( a )". + The spaces are optional in any position of this string. + + + The supergates are generated exhaustively from all gate combinations that + have the max delay lower than the delay given by the user, or until the specified time + limit is reached. + + The supergates are stored in supergate classes by their functionality. + Among the gates with the equivalent functionaly only those are dropped, which are + dominated by at least one other gate in the class in terms of both delay and area. + For the definition of gate dominance see pliGenCheckDominance(). +*/ + + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + -- cgit v1.2.3