source: vis_dev/vis-2.3/src/spfd/spfdUtil.c @ 93

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

  FileName    [spfdUtil.c]

  PackageName [spfd]

  Synopsis [Utility routines for the spfd package.]

  Description [Utility routines for the spfd package.]

  SeeAlso     [spfdAPI.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"

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


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


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


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


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


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

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


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


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

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

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

  Synopsis    [Initialize the application data structure of the package.]

  SideEffects [None]

******************************************************************************/
SpfdApplData_t *
SpfdInitializeApplData(
  Ntk_Network_t *network)
{
  SpfdApplData_t *applData;
  SpfdNodeData_t *data;
  st_table *nodeToData;
  lsGen gen;
  Ntk_Node_t *node;
  
  applData = ALLOC(SpfdApplData_t, 1);

  Ntk_NetworkAddApplInfo(network, SPFD_NETWORK_APPL_KEY,
                         (Ntk_ApplInfoFreeFn) SpfdApplFreeCallback,
                         (void *) applData);

  nodeToData = applData->nodeToData = st_init_table(st_ptrcmp, st_ptrhash);
  applData->ddManager = Ntk_NetworkReadMddManager(network);
  applData->currXCube = NIL(bdd_node);
  applData->currRegionNodes = NIL(st_table);
  applData->currBddReq = NIL(st_table);
  applData->currInUseVars = NIL(st_table);
  applData->currPiAltVars = NIL(st_table);
  /* Will be freed when the application quits */
  applData->currWireTable = st_init_table(st_ptrcmp,st_ptrhash);
  applData->currReplaceTable = st_init_table(st_ptrcmp,st_ptrhash);  
  applData->wiresRemoved = st_init_table(st_ptrcmp,st_ptrhash);
  applData->nodesRemoved = st_init_table(st_ptrcmp,st_ptrhash);
  applData->placeData = NIL(SpfdPlaceData_t);

  Ntk_NetworkForEachNode(network,gen,node) {
    data = ALLOC(SpfdNodeData_t,1);
    data->spfd = NIL(bdd_node);
    data->localAlt = NIL(bdd_node);
    data->alternative = NIL(bdd_node);
    data->faninOrder = NIL(array_t);
    data->parameters = NIL(bdd_node *);
    data->numParams = 0;
    data->auxId = -1;
    data->locked = FALSE;
    
    st_insert(nodeToData,(char *)node,(char *)data);
  }

  return applData;

} /* End of SpfdInitializeApplData */


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

  Synopsis [Given a set of 'num' (st_count(SCC)) pairs of functions,
  compute 'num' binary variables and allocate BDD ids to those
  variables such that their level is above all the variables in the
  support of the functions in SCC.]

  SideEffects [None]

******************************************************************************/
bdd_node **
SpfdComputeParameters(
  SpfdApplData_t *applData,
  st_table *SCC)
{
  bdd_manager *ddManager = applData->ddManager;
  st_table *inUseVars = applData->currInUseVars;
  int id,i,minLevel,size,used;
  int index,numIsfs;
  char *dummy;
  st_generator *stGen;
  bdd_node *bdd1,*bdd0;
  bdd_node **parameters;

  minLevel = bdd_num_vars(ddManager);
  /* Find the topmost level among the SCC components SCC(Y,P) */
  st_foreach_item(SCC,stGen,&bdd1,&bdd0) {
    int level1,level0,tempInt;
    level1 = bdd_get_level_from_id(ddManager,bdd_node_read_index(bdd1));
    level0 = bdd_get_level_from_id(ddManager,bdd_node_read_index(bdd0));
    tempInt = (level1 < level0) ? level1 : level0;
    minLevel = (minLevel < tempInt) ? minLevel : tempInt;
  }

  numIsfs = st_count(SCC);
  size = bdd_num_vars(ddManager);
  used = st_count(inUseVars);
  
  /* Allocate required number of new variables above minLevel */
  if (size - used < numIsfs) {
    SpfdMddCreateVariables(ddManager,(numIsfs)-(size-used),minLevel);
  }

  /* Assign the parameters */
  size = bdd_num_vars(ddManager);
  index = numIsfs;
  parameters = ALLOC(bdd_node *,numIsfs);
  /* Assign the parameter variables */
  for (i = 0; i < size; i++) {
    if (index == 0)
      break;
    id = bdd_get_id_from_level(ddManager,i);
    if (!st_lookup(inUseVars,(char *)(long)id,(char **)&dummy)) {
      parameters[numIsfs-index] = bdd_bdd_ith_var(ddManager,id);
      st_insert(inUseVars,(char *)(long)id,(char *)-1);
      index--;
    }
  }

  return parameters;
} /* End of SpfdComputeParameters */


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

  Synopsis    [Allocate num of BDD variables.]

  SideEffects [None]

******************************************************************************/
bdd_node **
SpfdAllocateTemporaryVariables(
  bdd_manager *ddManager,
  st_table *inUseVars,
  int num)
{
  int size,used,i,index,id;
  char *dummy;
  bdd_node **tempVars;

  tempVars = ALLOC(bdd_node *,num);
  size = bdd_num_vars(ddManager);
  used = st_count(inUseVars);
  if (size - used < num) {
    /* Create variables at the end */
    SpfdMddCreateVariables(ddManager,num-(size-used),size);
  }
  size = bdd_num_vars(ddManager);
  index = num;
  /* Assign the temporary variables */
  for (i = size-1; i >= 0; i--) {
    if (index == 0)
      break;
    id = bdd_get_id_from_level(ddManager,i);
    if (!st_lookup(inUseVars,(char *)(long)id,(char **)&dummy)) {
      tempVars[num-index] = bdd_bdd_ith_var(ddManager,id);
      st_insert(inUseVars,(char *)(long)id,(char *)-1);
      index--;
    }
  }

  return tempVars;
} /* End of SpfdAllocateTemporaryVariables */


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

  Synopsis [Recyle existing BDD variables or allocate new ones.]

  SideEffects [The BDD manager is changed accordingly to reflect the
  addition of new variables.]

******************************************************************************/
void
SpfdAllocateOrReuseAuxVariables(
  Ntk_Network_t *network,
  SpfdApplData_t *applData)
{
  st_table *currBddReq = applData->currBddReq;
  bdd_manager *ddManager = applData->ddManager;
  bdd_node *bdd1,*piSupport;
  int numBdds,piSize,regSize,size,newVars;
  int level,regNumVars;
  int numPiAlt,index;
  int *piIds;
  Ntk_Node_t *node;
  st_generator *stGen;
  st_table *inUseVars,*nodeToData,*piAltVars;
  lsGen gen;

  numBdds = st_count(currBddReq);
  
  /* Check if any region nodes are PIs */
  piAltVars = st_init_table(st_numcmp,st_numhash);
  numPiAlt = 0;
  st_foreach_item(currBddReq,stGen,&node,&bdd1) {
    if (Ntk_NodeTestIsPrimaryInput(node)) {
      int id = Ntk_NodeReadMddId(node);
      st_insert(piAltVars,(char *)(long)id,(char *)(long)id);
      numPiAlt++;
    }
  }

  /* Put the variable ids in piSupport in inUseVars */
  inUseVars = st_init_table(st_numcmp,st_numhash);

  /* To be on the safe side we do not reuse PI bdd ids */
  piSize = Ntk_NetworkReadNumPrimaryInputs(network);
  piIds = ALLOC(int,piSize);
  index = 0;
  Ntk_NetworkForEachPrimaryInput(network,gen,node) {
    int id;
    id = Ntk_NodeReadMddId(node);
    st_insert(inUseVars,(char *)(long)id,(char *)-1);
    piIds[index] = id;
    index++;
  }
  bdd_ref(piSupport = bdd_indices_to_cube(ddManager,piIds,piSize));
  FREE(piIds);
  
  if (applData->currXCube) {
    (void) fprintf(vis_stdout,
                   "** spfd warning: Possible memory leak.\n");
  }
  applData->currXCube = piSupport;

  regSize = numBdds;
  size = bdd_num_vars(ddManager);
  regNumVars = 2*regSize+piSize+numPiAlt;
  if (size < regNumVars) {
    newVars = regNumVars - size;
    SpfdMddCreateVariables(ddManager,newVars,0);
  } 
  
  /* Put the BDD ids of regionNodes and their immediate fanin in inUseVars */
  st_foreach_item(currBddReq,stGen,&node,NIL(char *)) {
    st_insert(inUseVars,(char *)(long)Ntk_NodeReadMddId(node),(char *)-1);
  }
   
  /* Assign auxillary ids to region nodes and their immediate fanin.  */
  nodeToData = applData->nodeToData;
  level = 0;
  size = bdd_num_vars(ddManager);
  st_foreach_item(currBddReq,stGen,&node,NIL(char *)) {
    int id;
    while (level < size) {
      id = bdd_get_id_from_level(ddManager,level);
      if (!st_lookup(inUseVars,(char *)(long)id,NIL(char *))) {
        SpfdNodeData_t *nodeData;
        st_lookup(nodeToData,(char *)node,&nodeData);
        nodeData->auxId = id;
        st_insert(inUseVars,(char *)(long)id,(char *)-1);
        level++;
        break;
      }
      level++;
    }
  }

  /* Assign alternate ids (these are in addition to auxIds) to those nodes in
     currBddReq which are PIs */
  st_foreach_item(currBddReq,stGen,&node,NIL(char *)) {
    if (Ntk_NodeTestIsPrimaryInput(node)) {
      int nodeId = Ntk_NodeReadMddId(node);
      while (level < size) {
        int id = bdd_get_id_from_level(ddManager,level);
        if (!st_lookup(inUseVars,(char *)(long)id,NIL(char *))) {
          st_insert(piAltVars,(char *)(long)nodeId,(char *)(long)id);
          st_insert(inUseVars,(char *)(long)id,(char *)-1);
          level++;
          break;
        }
        level++;
      }
    }
  }

  if (applData->currInUseVars) {
    (void) fprintf(vis_stdout,
                   "** spfd warning: Possible memory leak.\n");
  }
  applData->currInUseVars = inUseVars;

  if (applData->currPiAltVars) {
    (void) fprintf(vis_stdout,
                   "** spfd warning: Possible memory leak.\n");
  }
  applData->currPiAltVars = piAltVars;

  return;
  
} /* End of SpfdAllocateOrReuseAuxVariables */


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

  Synopsis [Fanin nodes of each cluster node is ordered according to
  the 'compareFunc'. The fanin nodes need to be ordered during SPFD
  computation.]

  SideEffects        [None]

******************************************************************************/
void
SpfdOrderFaninOfRegionNodes(
  Ntk_Network_t *network,
  SpfdApplData_t *applData,
  int (*compareFunc)(const void *, const void *))
{
  SpfdNodeData_t *nodeData;
  st_table *nodeToData = applData->nodeToData;
  st_table *regionNodes = applData->currRegionNodes;
  st_generator *stGen;
  Ntk_Node_t *regNode,*fanin;
  int i,bound;
  boolean found;
  
  st_foreach_item(regionNodes,stGen,&regNode,NIL(char *)) {
    array_t *tempArray;
    /* Atleast one fanin of regNode should be in regionNodes */
    found = FALSE;
    Ntk_NodeForEachFanin(regNode,i,fanin) {
      if (st_lookup(regionNodes,(char *)fanin,&bound) &&
          !bound &&
          !Ntk_NodeTestIsPrimaryInput(fanin) &&
          !Ntk_NodeTestIsPrimaryOutput(fanin)) {
        found = TRUE;
        break;
      }
    }
    if (found) {
      tempArray = array_dup(Ntk_NodeReadFanins(regNode));
      array_sort(tempArray,compareFunc);
      st_lookup(nodeToData,(char *)regNode,&nodeData);
      if (nodeData->faninOrder) {
        (void) fprintf(vis_stdout,
                       "** spfd warning: Possible memory leak.\n");
      }
      nodeData->faninOrder = tempArray;
    }
  }

  return;
} /* End of SpfdOrderFaninOfRegionNodes */


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

  Synopsis [Compare the convex combination of switched capacitance and
  topological depth of two nodes.]

  SideEffects        [None]

******************************************************************************/
int
SpfdSwitchedCapAndDepthCompare(
  const void *obj1,
  const void *obj2)
{
  SpfdApplData_t *applData;
  st_table *regionNodes;
  Ntk_Node_t *node1,*node2;
  Ntk_Network_t *network;
  float weight1,weight2;
  float switch1,switch2;
  float load1,load2;
  int depth1,depth2;
  int status;
  int dummy;
  
  node1 = *(Ntk_Node_t **)obj1;
  node2 = *(Ntk_Node_t **)obj2;
  assert(Ntk_NodeReadNetwork(node1) == Ntk_NodeReadNetwork(node2));
  network = Ntk_NodeReadNetwork(node1);
  applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
                                                        SPFD_NETWORK_APPL_KEY);
  regionNodes = applData->currRegionNodes;

  status = st_lookup(regionNodes,(char *)node1,&dummy);
  if (!status || dummy ||
      Ntk_NodeTestIsPrimaryOutput(node1) ||
      Ntk_NodeTestIsPrimaryInput(node1)) {
    weight1 = -1.0;
  } else {
    switch1 = Truesim_NetworkReadNodeSwitchingProb(network,node1);
    load1 = Truesim_NetworkReadNodeLoad(network,node1);
    depth1 = Truesim_NetworkReadNodeDepth(network,node1);
    weight1 = spfdAlpha * load1 * switch1 + (1.0-spfdAlpha)*depth1;
  }

  status = st_lookup(regionNodes,(char *)node2,&dummy);
  if (!status || dummy ||
      Ntk_NodeTestIsPrimaryOutput(node2) ||
      Ntk_NodeTestIsPrimaryInput(node2)) {
    weight2 = -1.0;
  } else {
    switch2 = Truesim_NetworkReadNodeSwitchingProb(network,node2);
    load2 = Truesim_NetworkReadNodeLoad(network,node2);
    depth2 = Truesim_NetworkReadNodeDepth(network,node2);
    weight2 = spfdAlpha * load2 * switch2 + (1.0-spfdAlpha)*depth2;
  }
  
  if (weight1 > weight2)
    return -1;
  else if (weight1 == weight2)
    return 0;
  else
    return 1;

} /* End of SpfdSwitchedCapAndDepthCompare */


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

  Synopsis [Compare the convex combination of fanout count and the 
  node's topological depth.]

  SideEffects        [None]

******************************************************************************/
int
SpfdFanoutCountAndDepthCompare(
  const void *obj1,
  const void *obj2)
{
  SpfdApplData_t *applData;
  st_table *regionNodes;
  Ntk_Node_t *node1,*node2;
  Ntk_Network_t *network;
  float weight1,weight2;
  float load1,load2;
  int depth1,depth2;
  int status;
  int dummy;
  
  node1 = *(Ntk_Node_t **)obj1;
  node2 = *(Ntk_Node_t **)obj2;
  assert(Ntk_NodeReadNetwork(node1) == Ntk_NodeReadNetwork(node2));
  network = Ntk_NodeReadNetwork(node1);
  applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network,
                                                        SPFD_NETWORK_APPL_KEY);
  regionNodes = applData->currRegionNodes;

  status = st_lookup(regionNodes,(char *)node1,&dummy);
  if (!status || dummy ||
      Ntk_NodeTestIsPrimaryOutput(node1) ||
      Ntk_NodeTestIsPrimaryInput(node1)) {
    weight1 = -1.0;
  } else {
    load1 = Ntk_NodeReadNumFanouts(node1);
    depth1 = Truesim_NetworkReadNodeDepth(network,node1);
    weight1 = spfdAlpha * load1 + (1.0-spfdAlpha)*depth1;
  }

  status = st_lookup(regionNodes,(char *)node2,&dummy);
  if (!status || dummy ||
      Ntk_NodeTestIsPrimaryOutput(node2) ||
      Ntk_NodeTestIsPrimaryInput(node2)) {
    weight2 = -1.0;
  } else {
    load2 = Ntk_NodeReadNumFanouts(node2);
    depth2 = Truesim_NetworkReadNodeDepth(network,node2);
    weight2 = spfdAlpha * load2 + (1.0-spfdAlpha)*depth2;
  }

  if (weight1 > weight2)
    return -1;
  else if (weight1 == weight2)
    return 0;
  else
    return 1;

} /* End of SpfdFanoutContAndDepthCompare */


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

  Synopsis    [Compare the topological depth of two nodes.]

  SideEffects [None]

******************************************************************************/
int
SpfdDepthCompare(
  const void *obj1,
  const void *obj2)
{
  Ntk_Network_t *network;
  Ntk_Node_t *node1 = *(Ntk_Node_t **)obj1;
  Ntk_Node_t *node2 = *(Ntk_Node_t **)obj2;
  int depth1,depth2;
  
  assert(Ntk_NodeReadNetwork(node1) == Ntk_NodeReadNetwork(node2));
  network = Ntk_NodeReadNetwork(node1);

  depth1 = Truesim_NetworkReadNodeDepth(network,node1);
  depth2 = Truesim_NetworkReadNodeDepth(network,node2);

  if (depth1 < depth2)
    return -1;
  else if (depth1 == depth2)
    return 0;
  else
    return 1;
  
} /* End of SpfdDepthCompare */


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

  Synopsis [Same as SpfdDepthCompare, but the nodes will be sorted in
  descending order when used by qsort.]

  SideEffects [None]

******************************************************************************/
int
SpfdDescendDepthCompare(
  const void *obj1,
  const void *obj2)
{
  Ntk_Network_t *network;
  Ntk_Node_t *node1 = *(Ntk_Node_t **)obj1;
  Ntk_Node_t *node2 = *(Ntk_Node_t **)obj2;
  int depth1,depth2;
  
  assert(Ntk_NodeReadNetwork(node1) == Ntk_NodeReadNetwork(node2));
  network = Ntk_NodeReadNetwork(node1);

  depth1 = Truesim_NetworkReadNodeDepth(network,node1);
  depth2 = Truesim_NetworkReadNodeDepth(network,node2);

  if (depth1 > depth2)
    return -1;
  else if (depth1 == depth2)
    return 0;
  else
    return 1;
  
} /* End of SpfdDescendDepthCompare */


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

  Synopsis [This procedure calls the mdd_create_variables in order to create 
  new variables.]
  
  Description [ This procedure calls the mdd_create_variables in order to
  create new variables. IMPORTANT: The mdd_create_variables
  procedure creates the variables in succession. So if new variables are
  required that are not in succession, those will not be created and hence
  cannot be used. This procedure takes as arguments the DD manager and the
  number of variables that need to be added to the manager.]

  SideEffects [It modifies the manager->hook->mdd field.]

  SeeAlso []

******************************************************************************/
void
SpfdMddCreateVariables(mdd_manager *mgr,     
                   int numVarsToBeAdded,
                   int level)
{
    array_t *mvar_values;
    array_t *mvar_names = NIL(array_t);
    array_t *mvar_strides = NIL(array_t);
    int i,two_values,idBeforeLevel,size;

    if (level > (size = bdd_num_vars(mgr)))
      level = size;
    if (level <= 0)
      idBeforeLevel = bdd_get_id_from_level(mgr,0);
    else
      idBeforeLevel = bdd_get_id_from_level(mgr,level-1);

    if (numVarsToBeAdded <= 0) return;
    
    /* Create 2 mvar values 0,1 */
    mvar_values = array_alloc(int, numVarsToBeAdded);    

    /* Assume we create only Bdd variables here */
    two_values = 2;
    for(i = 0; i < numVarsToBeAdded; i++) {
      array_insert(int, mvar_values, i, two_values);
    }

    /* creates the mdd variables and updates the mvar_list field */
    mdd_create_variables_after(mgr, idBeforeLevel,mvar_values, 
                               mvar_names, mvar_strides);
    
    array_free(mvar_values);

} /* End of SpfdMddCreateVariables */


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

  Synopsis [Returns a BDD containing minterms such that the discriminant for
  those minterms in f is equal to that in g.]

  Description [Returns a BDD containing minterms such that the discriminant for
  those minterms in f is equal to that in g. Used in bdd_add_apply().]

  SideEffects [None]

  SeeAlso     [cuddAddApply.c]

******************************************************************************/
bdd_node *
SpfdAddEqual(
  bdd_manager *ddManager,
  bdd_node **f,
  bdd_node **g)
{
  bdd_node *zero, *one;

  zero = bdd_read_zero(ddManager);
  one = bdd_read_one(ddManager);

  if(*f == *g) {
    return one;
  }

  if(bdd_is_constant(*f) && bdd_is_constant(*g)) {
      return zero;
  }
  return NULL;
}

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

  Synopsis           [Print the network in BLIF format to fileName.]

  SideEffects        [None]

******************************************************************************/
int
SpfdNetworkWriteBlifFile(
  Ntk_Network_t *network,
  char *fileName)
{
  lsGen gen;
  Ntk_Node_t *node;
  FILE *fp;
  int nameLen;
  char *name;
  
  if ((fp = Cmd_FileOpen(fileName,"w",NIL(char *),1)) == NIL(FILE)) {
    (void) fprintf(vis_stderr,
                   "** spfd error: Could not open %s for writing.\n",
                   fileName);
    return 0;
  }

  (void) fprintf(fp,".model %s\n",Ntk_NetworkReadName(network));
  (void) fprintf(fp,".inputs ");
  nameLen = 0;
  Ntk_NetworkForEachPrimaryInput(network,gen,node) {
    name = Ntk_NodeReadName(node);
    (void) fprintf(fp,"%s ",name);
    nameLen += (strlen(name));
    if (nameLen > 65) {
      (void) fprintf(fp,"\\\n");
      nameLen = 0;
    }
  }
  (void) fprintf(fp,"\n");

  nameLen = 0;
  (void) fprintf(fp,".outputs ");
  Ntk_NetworkForEachPrimaryOutput(network,gen,node) {
    name = Ntk_NodeReadName(node);
    (void) fprintf(fp,"%s ",name);
    nameLen += (strlen(name));
    if (nameLen > 65) {
      (void) fprintf(fp,"\\\n");
      nameLen = 0;
    }    
  }
  (void) fprintf(fp,"\n");
  
  Ntk_NetworkForEachNode(network,gen,node) {
    if (!Ntk_NodeTestIsPrimaryInput(node)) {
      if (Ntk_NodeReadNumFanins(node) > 0 ||
          Ntk_NodeReadNumFanouts(node) > 0) {
        Tbl_TableWriteBlifToFile(Ntk_NodeReadTable(node),fp);
      } else if (Ntk_NodeTestIsPrimaryOutput(node)) {
        /* Sometimes output node can be redundant. Very unlikely,
           but output it anyway because we cannot skip primary
           outputs of a network. */
        (void) fprintf(fp,".names %s\n",Ntk_NodeReadName(node));
      }
    }
  }

  (void) fprintf(fp,".end\n");

  fclose(fp);
  
  return 1;
  
} /* End of SpfdNetworkWriteBlifFile */


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

  Synopsis [Compute the relation of the functions specified in either
  nodeBdds and currBddReq. If 'useMddIds' is TRUE use node (from
  nodeArray) MDD ids else use node aux Ids. Return value of 'piSwap' is
  used in the calling function only when 'useMddIds' is TRUE. ]

  SideEffects [None]

  SeeAlso []

******************************************************************************/
bdd_node *
SpfdComputeNodeArrayRelation(
  SpfdApplData_t *applData,
  st_table *currBddReq,
  array_t *nodeBdds,
  array_t *nodeArray,
  boolean useMddIds,
  int *piSwap)
{
  bdd_manager *ddManager = applData->ddManager;
  st_table *piAltVars = applData->currPiAltVars;
  Ntk_Node_t *node;
  array_t *idArray;
  bdd_node *ddTemp,*ddTemp2,*result;
  bdd_node *bdd1,*var;
  int j,id;

  *piSwap = 0;

  if (currBddReq) {
    nodeBdds = array_alloc(bdd_node *,0);
    arrayForEachItem(Ntk_Node_t *,nodeArray,j,node) {
      st_lookup(currBddReq,(char *)node,&bdd1);
      array_insert_last(bdd_node *,nodeBdds,bdd1);
    }
  }
  idArray = array_alloc(int,0);
  if (useMddIds) { /* Use node MDD Ids or alternate Ids for PIs */
    int altId;
    arrayForEachItem(Ntk_Node_t *,nodeArray,j,node) {
      id = Ntk_NodeReadMddId(node);
      if (Ntk_NodeTestIsPrimaryInput(node)) {
        st_lookup(piAltVars,(char *)(long)id,&altId);
        array_insert_last(int,idArray,altId);
        *piSwap = 1;
      } else {
        array_insert_last(int,idArray,id);
      }
    }
  } else { /* Use node Aux Ids */
    arrayForEachItem(Ntk_Node_t *,nodeArray,j,node) {
      array_insert_last(int,idArray,SpfdNodeReadAuxId(applData,node));
    }    
  }
  bdd_ref(result = bdd_not_bdd_node(bdd_read_logic_zero(ddManager)));
  arrayForEachItem(Ntk_Node_t *,nodeArray,j,node) {
    bdd1 = array_fetch(bdd_node *,nodeBdds,j);
    var = bdd_bdd_ith_var(ddManager,array_fetch(int,idArray,j));
    bdd_ref(ddTemp = bdd_bdd_xnor(ddManager,var,bdd1));
    bdd_ref(ddTemp2 = bdd_bdd_and(ddManager,ddTemp,result));
    bdd_recursive_deref(ddManager,result);
    bdd_recursive_deref(ddManager,ddTemp);
    result = ddTemp2;
  }

  if (currBddReq)
    array_free(nodeBdds);
  array_free(idArray);
  
  return result;

} /* End of SpfdComputeNodeArrayRelation */


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

  Synopsis [Swap the BDD variables of primary inputs and it's
  auxillary BDD ids.]

  SideEffects [None]

******************************************************************************/
bdd_node *
SpfdSwapPiAndAltPi(
  SpfdApplData_t *applData,
  bdd_node *fun)
{
  bdd_manager *ddManager = applData->ddManager;
  bdd_node **fromVars;
  bdd_node **toVars;
  bdd_node *ddTemp;
  st_table *piAltVars = applData->currPiAltVars;
  st_generator *stGen;
  int i,num = st_count(piAltVars);
  int id,altId;
      
  fromVars = ALLOC(bdd_node *,num);
  toVars = ALLOC(bdd_node *,num);
  i = 0;
  st_foreach_item_int(piAltVars,stGen,&id,&altId) {
    fromVars[i] = bdd_bdd_ith_var(ddManager,altId);
    toVars[i] = bdd_bdd_ith_var(ddManager,id);
    i++;
  }
  bdd_ref(ddTemp = bdd_bdd_swap_variables(ddManager,fun,fromVars,toVars,num));

  FREE(fromVars);
  FREE(toVars);
  
  return ddTemp;
} /* End of SpfdSwapPiAndAltPi */


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

  Synopsis [The node's BDD is returned as it is without increasing the
  reference count.]

  SideEffects [None]

******************************************************************************/
bdd_node *
SpfdNodeReadLocalBdd(
  Ntk_Network_t *network,
  Ntk_Node_t *node)
{
  vertex_t *vertexPtr;
  Mvf_Function_t *mvf;
  graph_t *partition =
    (graph_t *) Ntk_NetworkReadApplInfo(network,PART_NETWORK_APPL_KEY);
  bdd_node *bdd1;
    
  vertexPtr = Part_PartitionFindVertexByMddId(partition,
                                              Ntk_NodeReadMddId(node));
  mvf = Part_VertexReadFunction(vertexPtr);
  bdd1 = bdd_extract_node_as_is(array_fetch(bdd_t *,mvf,1));

  return bdd1;
}


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

  Synopsis           [Extract 'percent'\% vectors from the patternArray.]

  SideEffects        [None]

******************************************************************************/
array_t *
SpfdFetchInternalPatternArray(
  array_t *patternArray,
  int percent,
  double randomValue)
{
  array_t *returnArray;
  int numVectors,start,end,i;

  /* For internal simulations use 1/10th of the total input pattern vectors */
  numVectors = array_n(patternArray);

  start = (int)(randomValue*(double)numVectors);
  end = start + (int)(numVectors*percent/100); 
  
  returnArray = array_alloc(char *,0);
  if (end == start) {
    array_insert_last(char *,returnArray,
                      array_fetch(char *,patternArray,start));
    return returnArray;
  }

  /* Allocate end - start + 1 size of returnArray */
  for (i = start; i < end; i++) {
    array_insert_last(char *,returnArray,
                      array_fetch(char *,patternArray,i));
  }

  return returnArray;
}

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

  Synopsis [Selects a random node or according to fanout count or
  switched capacitance.]

  Description        [optional]

  SideEffects        [required]

  SeeAlso            [optional]

******************************************************************************/
Ntk_Node_t *
SpfdFindNode(
  Ntk_Network_t *network,
  array_t *nodeArray)
{
  Ntk_Node_t *node1,*maxNode = NIL(Ntk_Node_t);
  int i;

  if (!array_n(nodeArray))
    return maxNode;
  
  if (spfdSortNodes == RANDOM) {
    int index,num;
    float randomValue;
    
    num = array_n(nodeArray);
    if (num < 5) {
      index = 0;
    } else {
      randomValue = ((double)util_random()/(double)(MODULUS1 - 2));
      index = (int) (randomValue * (double)num);
    }
    maxNode = array_fetch(Ntk_Node_t *,nodeArray,index);
  } else if (spfdSortNodes == MAXSWCAP) {
    float swc1,maxSwc;
    float switch1,load1;
    
    maxSwc = 0.0;
    arrayForEachItem(Ntk_Node_t *,nodeArray,i,node1) {
      switch1 = Truesim_NetworkReadNodeSwitchingProb(network,node1);
      load1 = Truesim_NetworkReadNodeLoad(network,node1);
      swc1 = load1 * switch1;
      
      if (swc1 > maxSwc) {
        maxNode = node1;
        maxSwc = swc1;
      }
    }
  } else if (spfdSortNodes == MINSWCAP) {
    float swc1,maxSwc;
    float switch1,load1;
    
    maxSwc = MAXINT;
    arrayForEachItem(Ntk_Node_t *,nodeArray,i,node1) {
      switch1 = Truesim_NetworkReadNodeSwitchingProb(network,node1);
      load1 = Truesim_NetworkReadNodeLoad(network,node1);
      swc1 = load1 * switch1;
      
      if (swc1 < maxSwc) {
        maxNode = node1;
        maxSwc = swc1;
      }
    }
  } else if (spfdSortNodes == MAXFANOUT) {
    int numFanout,maxFanout;
    
    maxFanout = 0;
    arrayForEachItem(Ntk_Node_t *,nodeArray,i,node1) {
      numFanout = Ntk_NodeReadNumFanouts(node1);
      if (numFanout > maxFanout) {
        maxNode = node1;
        maxFanout = numFanout;
      }
    }
  } else if (spfdSortNodes == MINFANOUT) {
    int numFanout,minFanout;
    
    minFanout = MAXINT;
    arrayForEachItem(Ntk_Node_t *,nodeArray,i,node1) {
      numFanout = Ntk_NodeReadNumFanouts(node1);
      if (numFanout < minFanout) {
        maxNode = node1;
        minFanout = numFanout;
      }
    }
  }
  
  return maxNode;
  
} /* End of SpfdFindNode */


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