src/spfd/spfdUtil.c File Reference

#include "spfdInt.h"

Include dependency graph for spfdUtil.c:

Go to the source code of this file.

Functions
SpfdApplData_t *	SpfdInitializeApplData (Ntk_Network_t *network)
bdd_node **	SpfdComputeParameters (SpfdApplData_t *applData, st_table *SCC)
bdd_node **	SpfdAllocateTemporaryVariables (bdd_manager *ddManager, st_table *inUseVars, int num)
void	SpfdAllocateOrReuseAuxVariables (Ntk_Network_t *network, SpfdApplData_t *applData)
void	SpfdOrderFaninOfRegionNodes (Ntk_Network_t *network, SpfdApplData_t *applData, int(*compareFunc)(const void *, const void *))
int	SpfdSwitchedCapAndDepthCompare (const void *obj1, const void *obj2)
int	SpfdFanoutCountAndDepthCompare (const void *obj1, const void *obj2)
int	SpfdDepthCompare (const void *obj1, const void *obj2)
int	SpfdDescendDepthCompare (const void *obj1, const void *obj2)
void	SpfdMddCreateVariables (mdd_manager *mgr, int numVarsToBeAdded, int level)
bdd_node *	SpfdAddEqual (bdd_manager *ddManager, bdd_node **f, bdd_node **g)
int	SpfdNetworkWriteBlifFile (Ntk_Network_t *network, char *fileName)
bdd_node *	SpfdComputeNodeArrayRelation (SpfdApplData_t *applData, st_table *currBddReq, array_t *nodeBdds, array_t *nodeArray, boolean useMddIds, int *piSwap)
bdd_node *	SpfdSwapPiAndAltPi (SpfdApplData_t *applData, bdd_node *fun)
bdd_node *	SpfdNodeReadLocalBdd (Ntk_Network_t *network, Ntk_Node_t *node)
array_t *	SpfdFetchInternalPatternArray (array_t *patternArray, int percent, double randomValue)
Ntk_Node_t *	SpfdFindNode (Ntk_Network_t *network, array_t *nodeArray)

---

Function Documentation

bdd_node* SpfdAddEqual	(	bdd_manager *	ddManager,
		bdd_node **	f,
		bdd_node **	g
	)

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]

Definition at line 672 of file spfdUtil.c.

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

Here is the caller graph for this function:

void SpfdAllocateOrReuseAuxVariables	(	Ntk_Network_t *	network,
		SpfdApplData_t *	applData
	)

Function********************************************************************

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

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

Definition at line 236 of file spfdUtil.c.

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

Here is the call graph for this function:

Here is the caller graph for this function:

bdd_node** SpfdAllocateTemporaryVariables	(	bdd_manager *	ddManager,
		st_table *	inUseVars,
		int	num
	)

Function********************************************************************

Synopsis [Allocate num of BDD variables.]

SideEffects [None]

Definition at line 193 of file spfdUtil.c.

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

Here is the call graph for this function:

Here is the caller graph for this function:

bdd_node* SpfdComputeNodeArrayRelation	(	SpfdApplData_t *	applData,
		st_table *	currBddReq,
		array_t *	nodeBdds,
		array_t *	nodeArray,
		boolean	useMddIds,
		int *	piSwap
	)

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 []

Definition at line 780 of file spfdUtil.c.

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

Here is the call graph for this function:

Here is the caller graph for this function:

bdd_node** SpfdComputeParameters	(	SpfdApplData_t *	applData,
		st_table *	SCC
	)

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]

Definition at line 133 of file spfdUtil.c.

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

Here is the call graph for this function:

Here is the caller graph for this function:

int SpfdDepthCompare	(	const void *	obj1,
		const void *	obj2
	)

Function********************************************************************

Synopsis [Compare the topological depth of two nodes.]

SideEffects [None]

Definition at line 545 of file spfdUtil.c.

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

Here is the call graph for this function:

Here is the caller graph for this function:

int SpfdDescendDepthCompare	(	const void *	obj1,
		const void *	obj2
	)

Function********************************************************************

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

SideEffects [None]

Definition at line 579 of file spfdUtil.c.

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

Here is the call graph for this function:

int SpfdFanoutCountAndDepthCompare	(	const void *	obj1,
		const void *	obj2
	)

Function********************************************************************

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

SideEffects [None]

Definition at line 483 of file spfdUtil.c.

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

Here is the call graph for this function:

Here is the caller graph for this function:

array_t* SpfdFetchInternalPatternArray	(	array_t *	patternArray,
		int	percent,
		double	randomValue
	)

Function********************************************************************

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

SideEffects [None]

Definition at line 918 of file spfdUtil.c.

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

Here is the caller graph for this function:

Ntk_Node_t* SpfdFindNode	(	Ntk_Network_t *	network,
		array_t *	nodeArray
	)

Function********************************************************************

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

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 961 of file spfdUtil.c.

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

Here is the call graph for this function:

Here is the caller graph for this function:

SpfdApplData_t* SpfdInitializeApplData

(

Ntk_Network_t *

network

)

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.]AutomaticStart AutomaticEnd Function********************************************************************

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

SideEffects [None]

Definition at line 74 of file spfdUtil.c.

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

Here is the call graph for this function:

Here is the caller graph for this function:

void SpfdMddCreateVariables	(	mdd_manager *	mgr,
		int	numVarsToBeAdded,
		int	level
	)

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 []

Definition at line 622 of file spfdUtil.c.

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

Here is the caller graph for this function:

int SpfdNetworkWriteBlifFile	(	Ntk_Network_t *	network,
		char *	fileName
	)

Function********************************************************************

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

SideEffects [None]

Definition at line 700 of file spfdUtil.c.

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

Here is the call graph for this function:

Here is the caller graph for this function:

bdd_node* SpfdNodeReadLocalBdd	(	Ntk_Network_t *	network,
		Ntk_Node_t *	node
	)

Function********************************************************************

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

SideEffects [None]

Definition at line 891 of file spfdUtil.c.

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

Here is the call graph for this function:

Here is the caller graph for this function:

void SpfdOrderFaninOfRegionNodes	(	Ntk_Network_t *	network,
		SpfdApplData_t *	applData,
		int(*)(const void *, const void *)	compareFunc
	)

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]

Definition at line 366 of file spfdUtil.c.

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

Here is the call graph for this function:

Here is the caller graph for this function:

bdd_node* SpfdSwapPiAndAltPi	(	SpfdApplData_t *	applData,
		bdd_node *	fun
	)

Function********************************************************************

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

SideEffects [None]

Definition at line 852 of file spfdUtil.c.

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

Here is the caller graph for this function:

int SpfdSwitchedCapAndDepthCompare	(	const void *	obj1,
		const void *	obj2
	)

Function********************************************************************

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

SideEffects [None]

Definition at line 417 of file spfdUtil.c.

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

Here is the call graph for this function:

Here is the caller graph for this function: