src/spfd/spfdUtil.c

Go to the documentation of this file.

#include "spfdInt.h"

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


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


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


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


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


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


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

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

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 */


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 */


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 */


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 */


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 */


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 */


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 */


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 */


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 */


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 */


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

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 */


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 */


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 */


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


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

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                                            */
/*---------------------------------------------------------------------------*/