source: vis_dev/vis-2.3/src/spfd/spfdCmd.c @ 104

/**CFile***********************************************************************

  FileName    [spfdCmd.c]

  PackageName [spfd]

  Synopsis [Interface functions for commands spfd_pilo and spfd_pdlo.]

  Description [Interface functions for commands spfd_pilo and spfd_pdlo.]

  SeeAlso     [spfdOpt.c]

  Author      [Balakrishna Kumthekar]

  Copyright [This file was created at the University of Colorado at Boulder.
  The University of Colorado at Boulder makes no warranty about the suitability
  of this software for any purpose.  It is presented on an AS IS basis.]

******************************************************************************/

#include "spfdInt.h"

static char rcsid[] UNUSED = "$Id: spfdCmd.c,v 1.28 2002/09/09 01:04:28 fabio Exp $";

/*---------------------------------------------------------------------------*/
/* Constant declarations                                                     */
/*---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*/
/* Type declarations                                                         */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Structure declarations                                                    */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Variable declarations                                                     */
/*---------------------------------------------------------------------------*/

static jmp_buf timeOutEnv; /* time out */
int spfdCreatedPart; /* Whether network BDDs were created in the package */
int spfdVerbose; /* verbosity */
float spfdAlpha; /* spfdAlpha * load + (1-spfdAlpha) * topDepth, is used to order
                fanin nodes during SPFD computation */
boolean spfdPerfSim; /* Perform simulation */
boolean spfdNtkChanged; /* TRUE if network changes structurally or functionally */
boolean spfdReprogNoWire; /* If TRUE, no functional changes are performed
                         unless required by structural changes */
int spfdWiresAdded, spfdNumWiresRem; /* Number of wires added and removed */
int spfdSortNodes; /* Method to sort nodes */
int spfdMethod; /* Optimization method */

/*---------------------------------------------------------------------------*/
/* Macro declarations                                                        */
/*---------------------------------------------------------------------------*/


/**AutomaticStart*************************************************************/

/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/

static int CommandSpfdNetworkOptimize(Hrc_Manager_t **hmgr, int argc, char **argv);
static int CommandSpfdPlaceOptimize(Hrc_Manager_t **hmgr, int argc, char **argv);
static void TimeOutHandle(void);
static int TestIsNetworkMultipleValued(Ntk_Network_t *network);
static int SpfdSimultaneousPlacementAndLogicOpt(Ntk_Network_t *network, char *netFile, char *archFile, char *placeFile, char *routeFile, char *netOutFile, int regionDepth);

/**AutomaticEnd***************************************************************/


/*---------------------------------------------------------------------------*/
/* Definition of exported functions                                          */
/*---------------------------------------------------------------------------*/

/**Function********************************************************************

  Synopsis    [This function initializes the spfd package.]

  SideEffects [None]

  SeeAlso     [Spfd_End]

******************************************************************************/
void
Spfd_Init(void)
{
  Cmd_CommandAdd("spfd_pilo", CommandSpfdNetworkOptimize, 1);
  Cmd_CommandAdd("spfd_pdlo", CommandSpfdPlaceOptimize, 1);

} /* End of Spfd_Init */

/**Function********************************************************************

  Synopsis    [This function ends the spfd package.]

  SideEffects [None]

  SeeAlso     [Spfd_Init]

******************************************************************************/
void
Spfd_End(void)
{

} /* End of Spfd_End */

/*---------------------------------------------------------------------------*/
/* Definition of internal functions                                          */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Definition of static functions                                            */
/*---------------------------------------------------------------------------*/
/**Function********************************************************************

   Synopsis [Implements SPFD-based placement independent logic
   optimization command, spfd_pilo, for combinational circuits mapped
   to LUT-based FPGAs.]

   CommandName [spfd_pilo]

   CommandSynopsis [Perform SPFD-based placement independent logic
   optimization.]

   CommandArguments [\[-a <\[0,1\]>\] \[-D <depth>\] \[-f
   <file>\] \[-h\] \[-i <freq>\] \[-p <percent>\]
   \[-r\] \[-S <n>\] \[-t <sec>\] \[-v <n>\]
   \[-w <file>\] ]

   CommandDescription [This command performs SPFD-based wire
   removal/replacement and reprogramming of combinational circuits
   mapped to LUT-based FPGAs to reduce the number of wires and nodes
   in the circuit. The flexibilities in the circuit are represented by
   SPFDs. The following references explain in detail the theory behind
   SPFDs.

   <p>S. Yamashita, H. Sawada, and A. Nagoya. A new method to express
   functional permissibilities for LUT based FPGAs and its
   applications. In International Conference on Computer Aided Design,
   pages 254-261, 1996.

   <p>Subarnarekha Sinha and Robert K. Brayton. Implementation and use of
   SPFDs in optimizaing Boolean networks. In International Conference
   on Computer Aided Design, 1998.

   <p> Instead of computing the flexibilities for every node in the
   network at once, the algorithm computes the flexibilities for one
   cluster at a time. Working with clusters allows us to avoid the BDD
   explosion problem and hence, handle large circuits. The SPFDs are
   computed for the cluster and the cluster nodes are reprogrammed
   based on the flexibility derived. Switching activity is used to
   drive the choice of alternate function to be implemented at the
   node. In the absence of switching activity information, the
   function that can reduce support of the node can be chosen (not
   implemented). Currently, an arbitrary choice is made from the
   flexibilities provided by SPFDs. (-S 0, -S 2, and -S 4)

   <p>
   Before calling this command a network should be created for the
   design (use flatten_hierarchy) and MDD ids for every node in the
   network should be created (static_order -o all -n append, for
   example). Dynamic variable ordering (dvo -e sift) can be enabled 
   to reduce BDD sizes.

   <p>Command options:<p>

   <dl>

   <dt> -a &lt;alpha&gt;
   <dd> A convex combination of switched
   capacitance (switching activity * fanout count, SWC) and topological
   depth is used to sort the fanin nodes during SPFD computation. alpha
   is between 0 and 1.0. The cost function is alpha*SWC +
   (1.0-alpha)*topDepth. The default value is 0.5. <p>

   <dt> -D &lt;depth&gt;
   <dd> A cluster is computed which includes nodes within the specified
   'depth'. The default value is 1.<p>

   <dt> -f &lt;file&gt;
   <dd> File with simulation vectors.  The file
   format is as below. The format is simple but strict and hence, few
   checks are made.
   <p> .i <code>c n d o e p f q g r h s i t j u k a l b m</code><br>
    .s <br>
    0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 ; <br>
    0 1 1 0 0 0 0 1 0 1 1 0 1 1 1 1 0 0 0 0 1 ; <br>
    0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 ; <br>
    0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 0 1 ; <br>

   <p>The .i statement specifies the primary inputs of the network. The
   patterns start after .s key word. Each vector is a space separated list of
   bits and ends in a semi-colon. The length of any vector should be equal 
   to the number of signals specified in the .i statement. A line starting 
   with # is a comment.  <p>

   <dt> -h
   <dd> Print usage. <p>

   <dt> -i &lt;freq&gt;
   <dd> Number of iterations after which to update node switching
   activity. This is valid only if patterns are provided in a file 
   using -f option. The default value is every 5 iterations. <p>

   <dt> -m &lt;n&gt;
   <dd> Heuristics to optimize a selected node. <br>
   <code>0</code>: Reduce the selected node's support. <br>
   <code>1</code>: Reprogram the selected node.<br>
   <code>2</code>: Reprogram the selected node's fanin nodes.
   (default)<br>
   <code>3</code>: Reduce the selected node's fanout wires. <p>
   
   <dt> -p &lt;percent&gt;
   <dd> The percentage of vectors, specified via <code>-f</code>
   option, used to perform simulation (to update switching activity)
   during logic optimization. The default value is 10%. <p>

   <dt> -r
   <dd> Do not reprogram LUTs if no structural changes have been
   performed with in the cluster, i.e., if no nodes or wires have been
   removed do not change the local implementation of LUTs even if
   alternate implementations are availabe from SPFD information. The
   default is to reprogram. <p>

   <dt> -S &lt;n&gt;
   <dd> Method used to sort nodes. The nodes are then optimized in
   that order.<br>
   <code>0</code>: Random node is chosen. (default) <br>
   <code>1</code>: If switching activity is available, node with
   maximum SWC is chosen.  <br>
   <code>2</code>: Node with maximum fanout is chosen. <br>
   <code>3</code>: If switching activity is available, node with
   minimum SWC is chosen. <br>
   <code>4</code>: Node with minimum fanout is chosen. <p>

   <dt> -t &lt;sec&gt;
   <dd> Time in seconds allowed to complete the command. If the
   computation time goes above that limit, the process is aborted.
   The default is no limit.<p>
   
   <dt> -v &lt;n&gt;
   <dd> Verbosity level. Default value is 0.<p>

   <dt> -w &lt;file&gt;
   <dd> File to output final optimized circuit. <p> ]
   </dl>
  
   <p> <b>Relevant flags to be set by the set command:</b> <p>
   <dl>
   <dt> <b>spfd_repl_rem</b>
   <dd> If <b>no</b>, the logic optimization performs only wire
   removal. If <b>yes</b>, both wire replacement and removal are performed.
   </dl>
  
   SideEffects [The network is changed to reflect the wires/nodes
   removed or replaced. The internal function of the nodes is also
   changed. The partition attached to the network is changed
   accordingly.]

******************************************************************************/
static int
CommandSpfdNetworkOptimize(
  Hrc_Manager_t **hmgr,
  int argc,
  char **argv)
{

  Ntk_Network_t *network = NIL(Ntk_Network_t);
  graph_t *simPart;
  int status,percent,frequency,regionDepth;
  int c;
  long timeOutPeriod,initialTime,finalTime;
  char *simFile,*writeFile;
  char endPtr[128];
  FILE *fp = NIL(FILE);
  
  /* These are the default values. */
  spfdCreatedPart = 0; /* Do not create a new partition */
  timeOutPeriod   = 0;  
  simFile = NIL(char);  /* File containing simulation vectors */
  spfdVerbose = 0; /* verbosity */
  regionDepth = 1; /* Depth of cluster */
  percent = 10; /* Percent of total vectors to be simulated during opt. */
  frequency = 5; /* Perform simulation every frequency iterations */
  spfdSortNodes = RANDOM; /* Choose a random node for optimization */
  spfdMethod = 2;
  spfdAlpha = 0.5; 
  writeFile = NIL(char); /* File to output final optimized ckt. */
  spfdNtkChanged = FALSE; 
  spfdReprogNoWire = TRUE;
  spfdWiresAdded = 0;
  spfdNumWiresRem = 0;
  spfdPerfSim = FALSE; /* Default */
  
  if (bdd_get_package_name() != CUDD) {
    (void) fprintf(vis_stderr,
                   "** spfd error: The spfd package can be used "
                   "only with CUDD package\n");
    (void) fprintf(vis_stderr,
                   "** spfd error: Please link with CUDD package\n");
    return 0;
  }
        
  util_getopt_reset();

  while((c = util_getopt(argc, argv, "a:D:f:hi:m:p:rS:t:v:w:")) != EOF) {
    switch(c) {
    case 'a':
      spfdAlpha = (float) strtod(util_optarg,(char **)&endPtr);
      if (!strcmp(util_optarg,endPtr)) {
        (void) fprintf(vis_stdout,
                       "** spfd warning: Invalid value <%s> specified for -a\n",
                       util_optarg);
        (void) fprintf(vis_stdout,"** spfd warning: Assuming 0.5.\n");
        spfdAlpha = 0.5;
      } else if (spfdAlpha > 1.0 || spfdAlpha < 0.0) {
        (void) fprintf(vis_stdout,
                       "** spfd warning: Value for -a <%f> not in [0,1]\n",
                       spfdAlpha);
        (void) fprintf(vis_stdout,"** spfd warning: Assuming 0.5.\n");
        spfdAlpha = 0.5;
      }
      break;
    case 'D':
      regionDepth = atoi(util_optarg);
      break;
    case 'f': 
      if (!util_optarg) {
        (void) fprintf(vis_stderr,
                       "** spfd error: Simulation file not specified.\n");
        goto usage;
      } else {
        simFile = util_strsav(util_optarg);
        if ((fp = Cmd_FileOpen(simFile,"r",NIL(char *),1)) == NIL(FILE)) {
          (void) fprintf(vis_stderr,
                         "** spfd error: Could not open %s for reading.\n",
                         simFile);
          goto endgame;
        } else {
          fclose(fp);
        }
        spfdPerfSim = TRUE;
      }
      break;
    case 'h':
      goto usage;
    case 'i':
      frequency = atoi(util_optarg);
      break;
    case 'm':
      spfdMethod = atoi(util_optarg);
      if (spfdMethod > 3 || spfdMethod < 0) {
        (void) fprintf(vis_stderr, "** spfd warning: -m has invalid argument\n");
        (void) fprintf(vis_stderr, "** spfd warning: Using 2 instead.\n");
      }
      break;
    case 'p':
      percent = atoi(util_optarg);
      if (percent > 100 || percent < 0) {
        (void) fprintf(vis_stderr,
                       "** spfd warning: -p <%d> has invalid argument.\n",
                       percent);
        (void) fprintf(vis_stderr,
                       "** spfd warning: Using 10%% instead.\n");
      }
      break;
    case 'r':
      spfdReprogNoWire = FALSE;
      break;
    case 'S':
      spfdSortNodes = atoi(util_optarg);
      if (spfdSortNodes > 4 || spfdSortNodes < 0) {
        (void) fprintf(vis_stderr,
                       "** spfd warning: -S <%d> has invalid argument.\n",
                       spfdSortNodes);
        (void) fprintf(vis_stderr,
                       "** spfd warning: Using 0 (random) instead.\n");
      }
      break;
    case 't':
      timeOutPeriod = atoi(util_optarg);
      break;
    case 'v':
      spfdVerbose = atoi(util_optarg);
      break;
    case 'w':
      writeFile = util_strsav(util_optarg);
      if ((fp = Cmd_FileOpen(writeFile,"w",NIL(char *),1)) == NIL(FILE)) {
        (void) fprintf(vis_stderr,
                       "** spfd error: Could not open %s for writing.\n",
                       writeFile);
        goto endgame;
      } else {
        fclose(fp);
      }
      break;
    default:
      goto usage;
    }
  }

  if(Hrc_ManagerReadCurrentNode(*hmgr) == NIL(Hrc_Node_t)) {
    (void) fprintf(vis_stderr,"** spfd error: The hierarchy manager is empty."
                   " Read in design.\n");
    goto endgame;
  }

  network = (Ntk_Network_t *) 
    Hrc_NodeReadApplInfo(Hrc_ManagerReadCurrentNode(*hmgr), 
                         NTK_HRC_NODE_APPL_KEY);

  if(network == NIL(Ntk_Network_t)) {
    (void) fprintf(vis_stderr,"** spfd error: There is no network. ");
    (void) fprintf(vis_stderr,"Use flatten_hierarchy.\n");
    goto endgame;
  }
    
  /* Check if the current network has signals with multiple values. */
  if (TestIsNetworkMultipleValued(network)) {
    (void) fprintf(vis_stderr,"** spfd error: Circuit has multiple "
                   "valued variables.\n");
    (void) fprintf(vis_stderr,"** spfd error: The algorithm currently "
                   "supports only Boolean valued variables.\n");
    goto endgame;
  }

  if(Ntk_NetworkReadNumPrimaryInputs(network) !=
     Ntk_NetworkReadNumInputs(network)) {
    (void) fprintf(vis_stderr,"** spfd error: Pseudo inputs present "
                   "in the network.\n");
    (void) fprintf(vis_stderr,"** spfd error: The algorithm does not apply.\n");
    goto endgame;
  }

  if(Ntk_NetworkReadNumLatches(network) > 0) {
    (void) fprintf(vis_stderr,"** spfd error: Sequential circuit.\n");
    (void) fprintf(vis_stderr,"** spfd error: The command is only for combinational circuits.\n");
    goto endgame;
  }
  
  /* Access a 'total' partition */
  simPart = (graph_t *) Ntk_NetworkReadApplInfo(network,PART_NETWORK_APPL_KEY);
  if (simPart == NIL(graph_t) || 
      (Part_PartitionReadMethod(simPart) != Part_Total_c)) {
    simPart = Part_NetworkCreatePartition(network, 
                                          NIL(Hrc_Node_t),
                                          "dummy", (lsList) 0, 
                                          (lsList) 0, NIL(mdd_t),
                                          Part_Total_c,
                                          (lsList) 0, 
                                          FALSE, FALSE, TRUE);
    if (simPart == NIL(graph_t)) {
      (void) fprintf(vis_stderr,"** spfd error: Could not create partition.\n");
      goto endgame;
    }
    Ntk_NetworkAddApplInfo(network,PART_NETWORK_APPL_KEY,
                           (Ntk_ApplInfoFreeFn)Part_PartitionFreeCallback,
                           (void *)simPart);
    spfdCreatedPart = 1; /* Using new partition */
    (void) fprintf(vis_stdout,
                   "** spfd info: A new partition created.\n");
  }

  /* Start the timer.*/
  if (timeOutPeriod > 0){
    (void) signal(SIGALRM, (void(*)(int))TimeOutHandle);
    (void) alarm(timeOutPeriod);
    if (setjmp(timeOutEnv) > 0) {
      (void) fprintf(vis_stderr, "** spfd warning: Timeout occurred after ");
      (void) fprintf(vis_stderr, "%ld seconds.\n", timeOutPeriod);
      alarm(0);
      goto endgame;
    }
  }

  initialTime = util_cpu_time();

  if (!spfdPerfSim) {
    (void) fprintf(vis_stdout,
                   "** spfd info: Simulation vectors not specified.\n");
    if (spfdSortNodes == MAXSWCAP) {
      (void) fprintf(vis_stdout,
                     "** spfd info: Using method -S 2 instead of -S 1\n");
      spfdSortNodes = MAXFANOUT;
    } else if (spfdSortNodes == MINSWCAP) {
      (void) fprintf(vis_stdout,
                     "** spfd info: Using method -S 4 instead of -S 3\n");      
      spfdSortNodes = MINFANOUT;
    }
  }
  status = SpfdNetworkOptimize(network,simFile,percent,frequency,regionDepth);

  finalTime = util_cpu_time();
  if(status) {
    (void) fprintf(vis_stdout, "%-20s%10ld\n", "** spfd info: analysis time =",
                   (finalTime-initialTime)/1000);
  }
  else {
    (void) fprintf(vis_stdout, "** spfd error: Optimization failed.\n");
  }

  if (writeFile) {
    SpfdNetworkWriteBlifFile(network,writeFile);
    FREE(writeFile);
  }

  if (simFile)
    FREE(simFile);

  if (spfdCreatedPart)
    Ntk_NetworkFreeApplInfo(network,PART_NETWORK_APPL_KEY);
  
  alarm(0);
  return 0;  /* normal exit */

endgame:
  /* Clean up */
  if (simFile)
    FREE(simFile);

  if (writeFile)
    FREE(writeFile);

  if (spfdCreatedPart)
    Ntk_NetworkFreeApplInfo(network,PART_NETWORK_APPL_KEY);
  
  return 1; /* Error exit */

usage:

  (void) fprintf(vis_stderr, "\nusage: Also see \'help spfd_pilo\' for more details.\n\n");
  (void) fprintf(vis_stderr, "    -a <alpha>\t\t<alpha> should be between 0.0 and 1.0\n");
  (void) fprintf(vis_stderr, "             \t\talpha*(SA*numFanout) + (1.0-alpha)*top_depth is used\n");
  (void) fprintf(vis_stderr, "             \t\tto order nodes during SPFD computation.\n");
  (void) fprintf(vis_stderr, "             \t\tSA is the switching activity of the node.\n");
  (void) fprintf(vis_stderr, "             \t\tThe default value is 0.5.\n\n");
  (void) fprintf(vis_stderr, "    -D <depth>\t\tCollect nodes that are within the specified depth.\n");
  (void) fprintf(vis_stderr, "            \t\tfrom the node being optimized.\n");
  (void) fprintf(vis_stderr, "            \t\tThe default is 1.\n\n");
  (void) fprintf(vis_stderr, "    -f <filename>\tFile containing simulation vectors.\n");
  (void) fprintf(vis_stderr, "               \t\tSee help for the format.\n\n"); 
  (void) fprintf(vis_stderr, "    -h      \t\tCommand usage.\n\n");
  (void) fprintf(vis_stderr, "    -i <freq> \t\tPerform internal simulations after \n");
  (void) fprintf(vis_stderr, "            \t\tevery <freq> iterations.\n");
  (void) fprintf(vis_stderr, "            \t\tDefault is 5.\n\n");
  (void) fprintf(vis_stderr, "    -m <n> \t\tHeuristics to optimize a selected node:\n");
  (void) fprintf(vis_stderr, "           \t\t0: Reduce the selected node's support.\n");
  (void) fprintf(vis_stderr, "           \t\t1: Reprogram the selected node.\n");
  (void) fprintf(vis_stderr, "           \t\t2: Reprogram the selected node's fanin nodes. (default)\n");
  (void) fprintf(vis_stderr, "           \t\t3: Reduce the selected node's fanout wires.\n\n");
  (void) fprintf(vis_stderr, "    -p <percent>\tPercent of total pattern vectors that\n");
  (void) fprintf(vis_stderr, "            \t\tshould be used during internal simulations.\n");
  (void) fprintf(vis_stderr, "            \t\tDefault is 10%%.\n\n");
  (void) fprintf(vis_stderr, "    -r      \t\tDo not reprogram internal nodes if the network\n");
  (void) fprintf(vis_stderr, "            \t\thas not changed structurally.\n");
  (void) fprintf(vis_stderr, "            \t\tBy default, reprogram.\n\n");
  (void) fprintf(vis_stderr, "    -S <value> \t\tHeuristic to select nodes for optimization.\n");
  (void) fprintf(vis_stderr, "            \t\t0. Random node. (default) \n");
  (void) fprintf(vis_stderr, "            \t\t1. Node with max. SA*numFanout.\n");
  (void) fprintf(vis_stderr, "            \t\t2. Node with max. fanout.\n");
  (void) fprintf(vis_stderr, "            \t\t3. Node with min. SA*numFanout.\n");
  (void) fprintf(vis_stderr, "            \t\t4. Node with min. fanout.\n\n");
  (void) fprintf(vis_stderr, "    -t <N>  \t\tTime (s) limit for the command.\n\n");
  (void) fprintf(vis_stderr, "    -v <N>  \t\tVerbosity level.\n\n");  
  (void) fprintf(vis_stderr, "    -w <filename>\tFile to output final optimized circuit.\n\n");
  (void) fprintf(vis_stderr, "set options: \n");
  (void) fprintf(vis_stderr, "\tspfd_repl_rem <yes|no>\n");
  (void) fprintf(vis_stderr, "\t\tReplace and remove wires simultaneously?\n");
  return 1;    /* error exit */

} /* End of CommandSpfdNetworkOptimize */


/**Function********************************************************************

   Synopsis [Implements SPFD-based simultaneous placement and logic
   optimization command, spfd_pdlo, for combinational circuits mapped
   to LUT-based FPGAs.]

   CommandName [spfd_pdlo]

   CommandSynopsis [Perform SPFD-based simultaneous placement and
   logic optimization.]

   CommandArguments [\[-D &lt;depth&gt;\] \[-h\] \[-n &lt;file&gt;\]
   \[-r\] \[-t &lt;sec&gt;\] \[-v &lt;n&gt;\] \[-w &lt;file&gt;\]
   net_file arch_file place_file route_file]

   CommandDescription [This command performs SPFD-based combined logic
   and placement optimization of combinational circuits mapped to
   LUT-based FPGAs to improve circuit area and speed. The
   flexibilities in the circuit are represented by SPFDs. The
   following references explain in detail the theory behind SPFDs.

   <p>S. Yamashita, H. Sawada, and A. Nagoya. A new method to express
   functional permissibilities for LUT based FPGAs and its
   applications. In International Conference on Computer Aided Design,
   pages 254-261, 1996.

   <p>Subarnarekha Sinha and Robert K. Brayton. Implementation and use of
   SPFDs in optimizaing Boolean networks. In International Conference
   on Computer Aided Design, 1998.

   <p>The command implements a technique that tightly links the logic
   and placement optimization steps. The algorithm is based on
   simulated annealing. Two types of moves, directed towards global
   reduction in the cost function (total wire length), are accepted by
   the simulated annealing algorithm: (1) wire removal/replacement,
   and (2) swapping of a pair of blocks in the FPGA. Feedback from
   placement is valuable in making an informed choice of a target wire
   during logic optimization moves. The logic optimization steps
   performed are similar to those of spfd_pilo, except that the
   placement information is now used instead of the fanout count.
   More information on this technique can be found in :

   <p>Balakrishna Kumthekar and Fabio Somenzi. Power and delay reduction
   via simultaneous logic and placement optimization in FPGAs.  In Design,
   Automation and Test in Europe, 2000.

   <p>The command produces a placement file which is used by VPR for
   routing.
  
   <p>This command can be used only if VIS is linked with VPR 4.22
   (Versatile Place and Route), the FPGA place and route tool <a
   href="http://www.eecg.toronto.edu/~vaughn/vpr/vpr.html"> VPR</a>,
   from the University of Toronto.  Please follow the instructions
   provided in the release notes to use VPR with VIS.  You can also
   contact kumtheka@avanticorp.com if you need more help.

   <p>Before calling this command a network should be created for the
   design (use flatten_hierarchy) and MDD ids for every node in the
   network should be created (static_order -o all -n append). Dynamic
   variable ordering (dvo -e sift) can be enabled to reduce BDD sizes.
   
   <p>Command options:<p>

   <dl>

   <dt> -D &lt;depth&gt;
   <dd> A cluster is computed which includes nodes within the specified
   'depth'. The default value is 1.<p>

   <dt> -n &lt;file&gt;
   <dd> File to output the optimized circuit in VPR's .net format.<p>

   <dt> -r
   <dd> Do not reprogram LUTs if no structural changes have been
   performed with in the cluster, i.e., if no nodes or wires have been
   removed do not change the local implementation of LUTs even if
   alternate implementations are availabe from SPFD information. The
   default is to reprogram. <p>

   <dt> -t &lt;sec&gt;
   <dd> Time in seconds allowed to complete the command. If the
   computation time goes above that limit, the process is is aborted.
   The default is no limit.<p>
   
   <dt> -v &lt;n&gt;
   <dd> Verbosity level.<p>

   <dt> -w &lt;file&gt;
   <dd> File to output final optimized circuit. <p>
   </dl>
  
   <p> <b>The following is needed by VPR:</b> <p>
   <dl>
   <dt> <b>net_file</b>
   <dd> The description of the circuit in the .net format. Logic
   optimization uses the circuit described in .BLIF format whereas VPR
   needs the same circuit described in .net format. VPack (which comes
   with VPR) converts a .BLIF format into a .net format. <p>

   <dt> <b>arch_file</b>
   <dd> Architecture description file for FPGAs. More information can be
   found in VPR's manual. <p>

   <dt> <b>place_file</b>
   <dd> File to dump placement information. <p>

   <dt> <b>route_file</b>
   <dd> File to dump routing information. <p>

   <p> <b>Relevant flags to be set by the set command:</b> <p>
   <dl>
   <dt> <b>spfd_pdlo_logic_move_freq</b> "r1 m1 r2 m2 ..."
   <dd> Perform m1 logic moves whenever the rate of acceptance during
   simulated annealing is greater than or equal to r1, and so on. r1,
   r2, r3 ... should be monotonically decreasing, else the results would
   be unpredictable. 0 <= ri <= 1.0. For example:

   <p> <code>set spfd_pdlo_logic_move_freq "0.8 0 0.5 5 0.2 10"</code><p>

   In the above logic schedule, zero logic moves per temperature will
   be performed when the rate of acceptance is above 0.8, 5 logic
   moves between 0.8 and 0.5, 10 moves between 0.5 and 0.2. As no
   value is specified for acceptance rate close to 0.0, by default, 1
   logic move per temperature will be performed. In this example it
   will be 1 logic move between 0.2 and 0.0.
   The quotes around the schedule are necessary.<p>

   <dt> <b>spfd_repl_rem</b>
   <dd> If <b>no</b>, the logic optimization performs only wire
   removal. If <b>yes</b>, both wire replacement and removal are performed. <p>

   <dt> <b>spfd_pdlo_timing</b>
   <dd> If set, use timing driven method to remove or replace wires on the
   critical path. If not set, use bounding box of the wires as the
   cost function.<p>

   <dt> <b>spfd_pdlo_timing_nodeorwire</b>
   <dd> Remove/replace all the wires belonging to the most critical
   net. If not set, attempt to remove/replace only the most critical
   wire. <p>

   <dt> <b>spfd_pdlo_out_crit_nets_first</b>
   <dd> Output the circuit in VPR's .net format with the nets
   appearing in the increasing order of their slack. If not set, the
   initial net order specified in the original circuit's .net file is
   used. The file is specified with <code>-n</code> option. This
   variable is valid only if <b>spfd_pdlo_timing</b> is set. <p>

   <dt> <b>spfd_pdlo_remap_clb_array</b>
   <dd> During logic optimization, due to the removal of nodes in the
   network, the current size of FPGA might be bigger than it is
   necessary. In such cases, if this variable is set, the size of the
   FPGA is reduced to fit the current logic network. <p>

   </dl>

   <p> <b>Relevant flags that are options to VPR:</b>
   <p> For detailed information on the following options please refer to
   the manual that accompanies VPR source distribution.
   <p>
   <dl>
   <dt><b> vpr_nodisp</b>
   <dt><b>vpr_fix_pins</b>
   <dt><b>vpr_nx</b>
   <dt><b>vpr_ny</b>
   <dt><b>vpr_fast</b>
   <dt><b>vpr_init_t</b>
   <dt><b>vpr_alpha_t</b>
   <dt><b>vpr_exit_t</b>
   <dt><b>vpr_inner_num</b>
   <dt><b>vpr_seet</b>
   <dt><b>vpr_place_cost_exp</b>
   <dt><b>vpr_place_chan_width</b>
   </dl> ]

   SideEffects [The network is changed to reflect the wires/nodes
   removed or replaced. The internal function of the nodes is also
   changed. The partition attached to the network is changed
   accordingly.]
   
******************************************************************************/
static int
CommandSpfdPlaceOptimize(
  Hrc_Manager_t **hmgr,
  int argc,
  char **argv)
{

#ifndef USE_VPR
  (void) fprintf(vis_stdout,"** spfd info: This command requires VPR "
                 "(Versatile Place and Route)\n");
  (void) fprintf(vis_stdout,"** spfd info: See \'help spfd_pdlo\' for more "
                 "information\n");
  (void) fprintf(vis_stdout,"** spfd info: on how to compile VIS with VPR.\n");
  (void) fprintf(vis_stdout,"** spfd info: Exiting calmly ...\n");
  return 0;
#else
  
  Ntk_Network_t *network;
  graph_t *simPart;
  int status,regionDepth;
  int c;
  long timeOutPeriod,initialTime,finalTime;
  char *writeFile;
  char *netFile,*archFile,*placeFile,*routeFile;
  char *netOutFile;
  FILE *fp = NIL(FILE);


  /* These are the default values. */
  spfdCreatedPart = 0; /* Do not create a new partition */
  timeOutPeriod   = 0;  
  spfdVerbose = 0; /* verbosity */
  regionDepth = 1; /* Depth of cluster */
  writeFile = NIL(char); /* File to output final optimized ckt. */
  spfdNtkChanged = FALSE;
  spfdReprogNoWire = TRUE;
  netFile = archFile = NIL(char); /* Circuit specified in VPR's .net
                                     format and FPGA architecture file */
  placeFile = routeFile = NIL(char); /* File to store placement and
                                        routing information */
  spfdWiresAdded = 0;
  spfdNumWiresRem = 0;
  netOutFile = NIL(char); /* File to output the optimized circuit in
                             .net format */
  status = FALSE;
  
  if (bdd_get_package_name() != CUDD) {
    (void) fprintf(vis_stderr,
                   "** spfd error: The spfd package can be used "
                   "only with CUDD package\n");
    (void) fprintf(vis_stderr,
                   "** spfd error: Please link with CUDD package\n");
    return 0;
  }

  util_getopt_reset();
  while((c = util_getopt(argc, argv, "D:hn:rt:v:w:")) != EOF) {
    switch(c) {
    case 'D':
      regionDepth = atoi(util_optarg);
      break;
    case 'h':
      goto usage;
    case 'n':
      netOutFile = util_strsav(util_optarg);
      break;      
    case 'r':
      spfdReprogNoWire = FALSE;
      break;
    case 't':
      timeOutPeriod = atoi(util_optarg);
      break;
    case 'v':
      spfdVerbose = atoi(util_optarg);
      break;
    case 'w':
      writeFile = util_strsav(util_optarg);
      if ((fp = Cmd_FileOpen(writeFile,"w",NIL(char *),1)) == NIL(FILE)) {
        (void) fprintf(vis_stderr,
                       "** spfd error: Could not open %s for writing.\n",
                       writeFile);
        goto endgame;
      } else {
        fclose(fp);
      }
      break;
    default:
      goto usage;
    }
  }

  /* netFile, archFile, and placeFile are essential. The user can
     specify /dev/null for routeFile if they don't want to store the
     routing information */
  if (argc < 5 || argc < util_optind+4)
    goto usage;

  /* Get the net, architecture, place and route file names */
  netFile = argv[util_optind];
  archFile = argv[util_optind+1];
  placeFile = argv[util_optind+2];
  routeFile = argv[util_optind+3];

  if(Hrc_ManagerReadCurrentNode(*hmgr) == NIL(Hrc_Node_t)) {
    (void) fprintf(vis_stderr,"** spfd error: The hierarchy manager is empty. "
                   "Read in design.\n");
    goto endgame;
  }

  network = (Ntk_Network_t *) 
    Hrc_NodeReadApplInfo(Hrc_ManagerReadCurrentNode(*hmgr), 
                         NTK_HRC_NODE_APPL_KEY);

  if(network == NIL(Ntk_Network_t)) {
    (void) fprintf(vis_stderr,"** spfd error: There is no network. ");
    (void) fprintf(vis_stderr,"Use flatten_hierarchy.\n");
    goto endgame;
  }

  /* Check if the current network has signals with multiple values. */
  if (TestIsNetworkMultipleValued(network)) {
    (void) fprintf(vis_stderr,"** spfd error: Circuit has multiple "
                   "valued variables.\n");
    (void) fprintf(vis_stderr,"** spfd error: The algorithm applies "
                   "to Boolean variables only.\n");
    goto endgame;
  }

  if(Ntk_NetworkReadNumPrimaryInputs(network) !=
     Ntk_NetworkReadNumInputs(network)) {
    (void) fprintf(vis_stderr,"** spfd error: Pseudo inputs present "
                   "in the network.\n");
    (void) fprintf(vis_stderr,"** spfd error: The algorithm does not apply.\n");
    goto endgame;
  }

  /* Access a 'total' partition */
  simPart = (graph_t *) Ntk_NetworkReadApplInfo(network, 
                                                PART_NETWORK_APPL_KEY);
  if (simPart == NIL(graph_t) || 
      (Part_PartitionReadMethod(simPart) != Part_Total_c)) {
    simPart = Part_NetworkCreatePartition(network, 
                                          NIL(Hrc_Node_t),
                                          "dummy", (lsList) 0, 
                                          (lsList) 0, NIL(mdd_t),
                                          Part_Total_c,
                                          (lsList) 0, 
                                          FALSE, FALSE, TRUE);
    if (simPart == NIL(graph_t)) {
      (void) fprintf(vis_stderr,"** spfd error: Could not create partition.\n");
      goto endgame;
    }
    Ntk_NetworkAddApplInfo(network,PART_NETWORK_APPL_KEY,
                           (Ntk_ApplInfoFreeFn)Part_PartitionFreeCallback,
                           (void *)simPart);
    spfdCreatedPart = 1; /* Using new partition */
    (void) fprintf(vis_stdout,
                   "** spfd info: A new partition created.\n");
  }

  /* Start the timer.*/
  if (timeOutPeriod > 0){
    (void) signal(SIGALRM, (void(*)(int))TimeOutHandle);
    (void) alarm(timeOutPeriod);
    if (setjmp(timeOutEnv) > 0) {
      (void) fprintf(vis_stderr, "** spfd warning: Timeout occurred after ");
      (void) fprintf(vis_stderr, "%ld seconds.\n", timeOutPeriod);
      alarm(0);
      goto endgame;
    }
  }

  initialTime = util_cpu_time();

  /* Call the optimization routine. */
  status = SpfdSimultaneousPlacementAndLogicOpt(network,netFile,archFile,
                                                placeFile,routeFile,netOutFile,
                                                regionDepth);
  
  finalTime = util_cpu_time();
  if(status) {
    (void) fprintf(vis_stdout, "%-20s%10ld\n", "** spfd info: analysis time =",
                   (finalTime-initialTime)/1000);
  }
  else {
    (void) fprintf(vis_stdout, "** spfd error: Optimization failed.\n");
  }

  if (writeFile) {
    SpfdNetworkWriteBlifFile(network,writeFile);
    FREE(writeFile);
  }

  if (netOutFile) {
    FREE(netOutFile);
  }

  if (spfdCreatedPart)
    Ntk_NetworkFreeApplInfo(network,PART_NETWORK_APPL_KEY);
  
  alarm(0);
  return 0;  /* normal exit */

endgame:
  /* Clean up */
  if (writeFile)
    FREE(writeFile);

  if (netOutFile) {
    FREE(netOutFile);
  }
  
  if (spfdCreatedPart)
    Ntk_NetworkFreeApplInfo(network,PART_NETWORK_APPL_KEY);
  
  return 1; /* Error exit */

usage:

  (void) fprintf(vis_stderr, "\nusage: Also see \'help spfd_pdlo\' for more details.\n\n");
  (void) fprintf(vis_stderr, "spfd_pdlo [options] net_file arch_file place_file route_file\n\n");
  (void) fprintf(vis_stderr, "    -D <depth>\t\tConsider region upto <depth>.\n\n");
  (void) fprintf(vis_stderr, "    -h      \t\tCommand usage.\n\n");
  (void) fprintf(vis_stderr, "    -n <filename>\tFile to output optimized\n");
  (void) fprintf(vis_stderr, "            \t\tcircuit in .net format.\n\n");
  (void) fprintf(vis_stderr, "    -r      \t\tDo not reprogram internal nodes if there are no\n");
  (void) fprintf(vis_stderr, "            \t\tstructural changes in the network.\n\n");
  (void) fprintf(vis_stderr, "    -t <N>  \t\tTime (s) limit for the command.\n\n");  
  (void) fprintf(vis_stderr, "    -v <N>  \t\tVerbosity level.\n\n");
  (void) fprintf(vis_stderr, "    -w <filename>\tFile to output final optimized circuit.\n\n");
  (void) fprintf(vis_stderr, "set options: \n");
  (void) fprintf(vis_stderr, "\tspfd_pdlo_logic_move_freq \"r1 m1 r2 m2 ...\"\n");
  (void) fprintf(vis_stderr, "\t\tPerform m1 logic moves per temperature whenever the rate\n");
  (void) fprintf(vis_stderr, "\t\tof acceptance during simulated annealing is greater than\n");
  (void) fprintf(vis_stderr, "\t\tor equal to r1, and so on. r1 > r2 > r3 ... \n");
  (void) fprintf(vis_stderr, "\t\tand 0 <= ri <= 1.0.\n\n");
  (void) fprintf(vis_stderr, "\tspfd_repl_rem <yes|no>\n");
  (void) fprintf(vis_stderr, "\t\tPerform both wire replacement and removal?\n\n");
  (void) fprintf(vis_stderr, "\tspfd_pdlo_timing\n");
  (void) fprintf(vis_stderr, "\t\tUse timing driven method.\n");
  (void) fprintf(vis_stderr, "\t\tIf not set, Bounding box method is used.\n\n");
  (void) fprintf(vis_stderr, "\tspfd_pdlo_timing_nodeorwire\n");
  (void) fprintf(vis_stderr, "\t\tProcess the fanouts of the most tcritical node. If not set,\n");
  (void) fprintf(vis_stderr, "\t\tprocess only the wires on the critical path.\n\n");
  (void) fprintf(vis_stderr, "\tspfd_pdlo_out_crit_nets_first\n");
  (void) fprintf(vis_stderr, "\t\tOutput the circuit in VPR\'s .net format with\n");
  (void) fprintf(vis_stderr, "\t\tnets appearing in the increasing order of their slack.\n");
  (void) fprintf(vis_stderr, "\t\tIf not set, the initial net order specified in the original\n");
  (void) fprintf(vis_stderr, "\t\tcircuit\'s .net file is used. The file specified in -n option\n");
  (void) fprintf(vis_stderr, "\t\tis used. This option is valid only if spfd_pdlo_timing is set.\n\n");
  (void) fprintf(vis_stderr, "\tspfd_pdlo_remap_clb_array\n");
  (void) fprintf(vis_stderr, "\t\tReduce the size of FPGA if necessary during\n");
  (void) fprintf(vis_stderr, "\t\tlogic optimization.\n\n");
  (void) fprintf(vis_stderr, "set options for VPR: Please see VPR's manual for more information.\n");
  (void) fprintf(vis_stderr, "    vpr_nodisp\n");
  (void) fprintf(vis_stderr, "    vpr_fix_pins\n");
  (void) fprintf(vis_stderr, "    vpr_nx\n");
  (void) fprintf(vis_stderr, "    vpr_ny\n");
  (void) fprintf(vis_stderr, "    vpr_fast\n");
  (void) fprintf(vis_stderr, "    vpr_init_t\n");
  (void) fprintf(vis_stderr, "    vpr_alpha_t \n");
  (void) fprintf(vis_stderr, "    vpr_exit_t\n");
  (void) fprintf(vis_stderr, "    vpr_inner_num\n");
  (void) fprintf(vis_stderr, "    vpr_seed\n");
  (void) fprintf(vis_stderr, "    vpr_place_cost_exp\n");
  (void) fprintf(vis_stderr, "    vpr_place_chan_width\n");
  return 1;    /* error exit */
#endif /* ifdef USE_VPR */

} /* End of CommandSpfdPlaceOptimize */


/**Function********************************************************************

  Synopsis    [Handle function for timeout.]

  Description [This function is called when the time out occurs.]

  SideEffects []

******************************************************************************/
static void
TimeOutHandle(void)
{
  longjmp(timeOutEnv, 1);
}

/**Function********************************************************************

  Synopsis    [Checks whether the network has multiple valued signals.]

  Description [Checks whether the network has multiple valued
  signals. Returns 1 if true, else 0.]

  SideEffects [None]

  SeeAlso []

******************************************************************************/
static int
TestIsNetworkMultipleValued(Ntk_Network_t *network)
{
  Ntk_Node_t *node;
  lsGen gen;
  Var_Variable_t *var;
  int numValues;

  Ntk_NetworkForEachNode(network,gen,node) {
    var = Ntk_NodeReadVariable(node);
    numValues = Var_VariableReadNumValues(var);
    if (numValues > 2)
      return 1;
  }
  return 0;
}

#ifndef USE_VPR
/**Function********************************************************************
 
  Synopsis [Dummy function]

  SideEffects [None]

******************************************************************************/
static int 
SpfdSimultaneousPlacementAndLogicOpt(
  Ntk_Network_t *network,
  char *netFile,
  char *archFile,
  char *placeFile,
  char *routeFile,
  char *netOutFile,
  int regionDepth)
{
  return 0;
}
#endif