/**CFile*********************************************************************** FileName [spfdOpt.c] PackageName [spfd] Synopsis [Routines that implement spfd_pilo.] Description [Routines that implement spfd_pilo.] SeeAlso [spfdCmd.c spfdReg.c spfdProg.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 */ /*---------------------------------------------------------------------------*/ static int CompareConvexFanoutCountAndDepth(const void *obj1, const void *obj2); static int CompareConvexSwitchedCapAndDepth(const void *obj1, const void *obj2); /**AutomaticEnd***************************************************************/ /*---------------------------------------------------------------------------*/ /* Definition of exported functions */ /*---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------*/ /* Definition of internal functions */ /*---------------------------------------------------------------------------*/ /**Function******************************************************************** Synopsis [Optimize the network by performing wire/node removal, wire replacement and LUT reprogramming to reduce the number of wires and nodes and the overall switching activity of the circuit.] Description [Optimize the network by performing wire/node removal, wire replacement and LUT reprogramming to reduce the number of wires and nodes and the overall switching activity of the circuit. The algorithm iteratively selects a node, 'maxNode', (based on the heuristic selected) and examines all the fanout/fanin wires to determine if any one them can be removed or replaced by another wire. For each wire selected, fanout cluster if computed up to a depth 'regionDepth'. SPFD are computed only for these cluster nodes. Any wire, internal to the cluster, that has an empty SPFD is removed. Cluster nodes are then reprogrammed by choosing an alternative implementation derived from the node SPFD. After the cluster nodes are optimized, 'maxNode' is locked and is not optimized in future iterations. The algorithm ends when there are no more nodes to be optimized. The argument 'simFile' (if not NULL) specifies the vectors used to simulate the circuit in order to compute circuit node switching activity. Vector simulations are performed every 'frequency' iterations. 'regionDepth' specifies the depth of the cluster from the 'maxNode'.] SideEffects [None] ******************************************************************************/ int SpfdNetworkOptimize( Ntk_Network_t *network, char *simFile, int percent, int frequency, int regionDepth) { SpfdApplData_t *applData; Ntk_Node_t *node,*maxNode; int stop,iter,status; float randomValue; array_t *nodeArray; lsGen gen; st_generator *stGen; char *dummy; boolean replRem; array_t *inputArray,*patternArray,*intPatternArray; char *optName; /* To keep the compiler happy */ inputArray = patternArray = intPatternArray = NIL(array_t); /* Check if both wire removal and replacement are to be done */ optName = Cmd_FlagReadByName("spfd_repl_rem"); if (optName && (strcmp(optName,"yes") == 0)) { replRem = TRUE; } else { replRem = FALSE; } /* First initialize the simulation package. This will also levelize the nodes in the network. The level info is stored in local data structure of 'truesim' package'. This is needed even if we do not perform vector simulation. */ Truesim_InitializeSimulation(network,NIL(char),0,-1,0,NIL(st_table)); if (spfdPerfSim) { /* Perform simulation? */ /* Array of primary input nodes */ inputArray = array_alloc(Ntk_Node_t *,0); /* Array of simulation vectors */ patternArray = array_alloc(char *,0); status = Truesim_ReadSimulationVectors(network,simFile, inputArray,patternArray); /* Error while reading simulation vectors */ if (!status) { array_free(inputArray); array_free(patternArray); (void) fprintf(vis_stdout, "** spfd error: Error reading simulation" " vector file. \n"); return 0; } Truesim_ZeroDelayPatternSimulate(network,inputArray,patternArray); /* Select a random start for the set of internal simulation vectors. We simulate only a portion of vectors (during optimization iterations) to get a coarse estimate of circuit node switching activities. */ randomValue = ((double)util_random()/(double)(MODULUS1 - 2)); if (randomValue > (double) (1.0 - ((double)percent)/((double)100))) randomValue = (1.0 - ((double)percent)/((double)100))/2.0; /* Partial set of simulation vectors */ intPatternArray = SpfdFetchInternalPatternArray(patternArray,percent, randomValue); } /* Initialize the package application data structure */ applData = SpfdInitializeApplData(network); iter = 1; do { if (spfdVerbose > 2) { (void) fprintf(vis_stdout, "** spfd info: Iteration %d\n",iter); } nodeArray = array_alloc(Ntk_Node_t *,0); /* Collect circuit nodes, later needed to be sorted. Only the internal nodes will be sorted.*/ switch (spfdMethod) { case REDUCE_FANIN_WIRES: case OPTIMIZE_MAX_NODE: Ntk_NetworkForEachNode(network,gen,node) { if (!Ntk_NodeTestIsPrimaryOutput(node) && !Ntk_NodeTestIsPrimaryInput(node) && !SpfdNodeReadLocked(applData,node)) array_insert_last(Ntk_Node_t *,nodeArray,node); } break; case OPTIMIZE_FANIN_NODES: Ntk_NetworkForEachNode(network,gen,node) { if (!Ntk_NodeTestIsPrimaryInput(node) && !SpfdNodeReadLocked(applData,node)) array_insert_last(Ntk_Node_t *,nodeArray,node); } break; case REDUCE_FANOUT_WIRES: Ntk_NetworkForEachNode(network,gen,node) { if (!SpfdNodeReadLocked(applData,node)) array_insert_last(Ntk_Node_t *,nodeArray,node); } break; } /* Find the node with max. fanout/switched cap., or a random node */ maxNode = SpfdFindNode(network,nodeArray); if (!maxNode) stop = 1; else stop = 0; array_free(nodeArray); /* Optimize. */ if (!stop) { switch (spfdMethod) { case REDUCE_FANIN_WIRES: SpfdOptimizeFaninWires(network,maxNode,regionDepth,replRem); break; case OPTIMIZE_MAX_NODE: SpfdOptimizeNode(network,maxNode,regionDepth); break; case OPTIMIZE_FANIN_NODES: SpfdOptimizeFaninNodes(network,maxNode,regionDepth); break; case REDUCE_FANOUT_WIRES: SpfdOptimizeFanoutWires(network,maxNode,regionDepth,replRem); break; } /* If the network has changed (structurally), update the depth information to reflect the change in the network.*/ if (spfdNtkChanged) { Truesim_NetworkUpdateNodeTopologicalDepth(network); spfdNtkChanged = FALSE; } if (spfdPerfSim && (iter % frequency == 0)) { Truesim_ZeroDelayPatternSimulate(network,inputArray,intPatternArray); } } iter++; } while (!stop); if (spfdPerfSim) { /* End simulation; free memory */ Truesim_QuitSimulation(network); array_free(inputArray); array_free(patternArray); } /* Print the number of wires removed and delete the sinkTable. */ fprintf(vis_stdout,"** spfd info: # of wires removed = %d\n", spfdNumWiresRem - spfdWiresAdded); fprintf(vis_stdout,"** spfd info: # of nodes removed = %d\n", st_count(applData->nodesRemoved)); /* Free the memory for each node */ st_foreach_item(applData->nodesRemoved,stGen,&node,&dummy) { if (node) Ntk_NodeFree(node); } return 1; } /* End of SpfdNetworkOptimize */ #if 0 /**Function******************************************************************** Synopsis [Optimize the cluster of nodes in the fanout of each fanout wire of maxNode. The cluster is formed of those nodes that are within 'regionDepth' of the fanout wire. Both wire removal and replacement are performed if 'replRem' is true.] SideEffects [None] ******************************************************************************/ void SpfdProcessFanoutWires( Ntk_Network_t *network, Ntk_Node_t *maxNode, int regionDepth, boolean replRem) { SpfdApplData_t *applData; array_t *fanoutArray,*replArray; st_table *wiresRemoved,*sinkTable; st_generator *stGen; Ntk_Node_t *ntkNode,*tempNode,*replNode; int i,num; /* Package application data structure */ applData = Ntk_NetworkReadApplInfo(network,SPFD_NETWORK_APPL_KEY); fanoutArray = array_dup(Ntk_NodeReadFanouts(maxNode)); for (i = array_n(fanoutArray) - 1; i >=0; i--) { ntkNode = array_fetch(Ntk_Node_t *,fanoutArray,i); /* Skip POs */ if (Ntk_NodeTestIsPrimaryOutput(ntkNode)) continue; /* Could be removed during an earlier iteration */ if (!st_lookup(applData->nodesRemoved,(char *)ntkNode,NIL(char *))) { array_t *regionArray; /* regionArray is an array of nodes sorted according to their depth. */ regionArray = SpfdNodeComputeFanoutRegion(applData,ntkNode,regionDepth); /* Analyze region's BDD requirements */ SpfdComputeRequiredGlobalBdds(network,applData); /* Analyze auxilarry BDD ID requirements */ SpfdAllocateOrReuseAuxVariables(network,applData); /* Order the fanin of internal and boundary nodes */ if (spfdPerfSim) { SpfdOrderFaninOfRegionNodes(network,applData, SpfdSwitchedCapAndDepthCompare); } else { SpfdOrderFaninOfRegionNodes(network,applData, SpfdFanoutCountAndDepthCompare); } /* Set the spfds for nodes in the region. The spfds are reduced to a single pair and the localAlt is set to one of the components of the single pair SPFD. */ SpfdRegionComputeSinglePairSpfd(network,applData,regionArray); /* Now check if the spfd of wire maxNode --> ntkNode is empty. Remove the spfd of ntkNode as it was not deleted in SpfdRegionComputeSinglePairSpfd */ /* Compute array of potential candidates for replacement */ if (replRem) replArray = SpfdNodeComputeTFIUntilDepth(ntkNode,regionDepth); else replArray = NIL(array_t); replNode = SpfdCheckIfWireIsRedundantOrReplaceable(network,applData, maxNode,ntkNode, replArray); /* No longer needed. */ SpfdNodeDeleteSpfd(applData,ntkNode); if (replArray) array_free(replArray); /* Check to see if wires have been found to be redundant/replaceable. If no wires are to be removed/replaced, then decide whether or not to reprogram. */ if (st_count(applData->currWireTable) == 0 && st_count(applData->currReplaceTable) == 0 && !spfdReprogNoWire) { /* In this case just clean up currBddReq, localAlt and globalAlt. */ st_table *currBddReq; st_generator *stGen; Ntk_Node_t *regNode; bdd_node *bdd1; bdd_manager *ddManager; int j; ddManager = applData->ddManager; currBddReq = applData->currBddReq; /* Clean up currBddReq */ st_foreach_item(currBddReq,stGen,(char **)®Node,(char **)&bdd1) { bdd_recursive_deref(ddManager,bdd1); } st_free_table(currBddReq); applData->currBddReq = NIL(st_table); /* Clean up localAlt and globalAlt of region nodes */ arrayForEachItem(Ntk_Node_t *,regionArray,j,regNode) { SpfdNodeDeleteGlobalAlternative(applData,regNode); SpfdNodeDeleteLocalAlt(applData,regNode); } } else { /* Now reprogram the nodes in the region. */ SpfdReprogramRegionNodes(network,applData,regionArray); } /* In this subroutine we have only a single wire replaced. Delete just that data */ if (replNode) { SpfdNodeDeleteGlobalAlternative(applData,replNode); SpfdNodeSetAuxId(applData,replNode,-1); st_delete(applData->currReplaceTable,(char **)&ntkNode, (char **)&sinkTable); st_free_table(sinkTable); /* A small caveat: sometimes a wire added can be later removed. Check if the replNode --> ntkNode still exists. If not set replNode to NULL. */ wiresRemoved = applData->wiresRemoved; if (st_lookup(wiresRemoved,(char *)replNode,(char **)&sinkTable) && st_lookup(sinkTable,(char *)ntkNode,NIL(char *))) { /* Reduce the number of wires added and delete replNode->ntkNode from wiresRemoved table */ spfdWiresAdded--; st_delete(sinkTable,(char **)&ntkNode,NIL(char *)); if (st_count(sinkTable) < 1) { st_delete(wiresRemoved,(char **)&replNode,(char **)&sinkTable); st_free_table(sinkTable); } replNode = NIL(Ntk_Node_t); } } /* Clean up auxIds and piAltVars*/ SpfdCleanUpAuxIds(applData); /* Free stuff used only for the current iteration */ if (applData->currXCube) { bdd_recursive_deref(applData->ddManager,applData->currXCube); applData->currXCube = NIL(bdd_node); } if (applData->currRegionNodes) { st_free_table(applData->currRegionNodes); applData->currRegionNodes = NIL(st_table); } if (applData->currInUseVars) { st_free_table(applData->currInUseVars); applData->currInUseVars = NIL(st_table); } num = st_count(applData->currWireTable); assert(num == 0); num = st_count(applData->currReplaceTable); assert(num == 0); /* Update the total number of wires removed */ wiresRemoved = applData->wiresRemoved; if (st_count(wiresRemoved) > 0) { st_foreach_item(wiresRemoved,stGen,(char **)&tempNode, (char **)&sinkTable){ spfdNumWiresRem += st_count(sinkTable); } /* free the wiresRemoved contents */ st_foreach(wiresRemoved,SpfdStTableClean,NIL(char)); } /* Free regionArray (cluster) */ array_free(regionArray); } } array_free(fanoutArray); /* Lock the node */ SpfdNodeSetLocked(applData,maxNode,TRUE); } /* End of SpfdProcessFanoutWires */ #endif /**Function******************************************************************** Synopsis [Checks if the SPFD for 'from' --> 'to' is empty. If yes, the wire is removed. If not, nodes in 'replaceArray' are examined to check for replacability. If a node is found, that node is returned.] SideEffects [None] ******************************************************************************/ Ntk_Node_t * SpfdCheckIfWireIsRedundantOrReplaceable( Ntk_Network_t *network, SpfdApplData_t *applData, Ntk_Node_t *from, Ntk_Node_t *to, array_t *replaceArray) { bdd_manager *ddManager = applData->ddManager; bdd_node *result,*ddTemp,*ddTemp2,*var,*varAux; bdd_node *toSpfd,*wireSpfd,*logicZero; int i,index; Ntk_Node_t *fanin,*tempNode,*replNode; st_table *wireTable = applData->currWireTable; st_table *wiresRemoved = applData->wiresRemoved; st_table *sinkTable; /* Possible replacement node */ replNode = NIL(Ntk_Node_t); logicZero = bdd_read_logic_zero(ddManager); /* Check if this wire has already been removed. */ if (!(st_lookup(wiresRemoved,(char *)from,&sinkTable) && st_lookup(sinkTable,(char *)to,&tempNode))) { bdd_ref(result = bdd_read_one(ddManager)); /* Compute the characteristic function of pairs of minterms cannot be distinguished any fanin of 'to'. Let f_i be the ith fanin of 'to'. We compute result = \prod f_i == f'_i, where f_i != from */ Ntk_NodeForEachFanin(to,i,fanin) { var = bdd_bdd_ith_var(ddManager,Ntk_NodeReadMddId(fanin)); index = SpfdNodeReadAuxId(applData,fanin); varAux = bdd_bdd_ith_var(ddManager,index); if (fanin != from) { bdd_ref(ddTemp = bdd_bdd_xnor(ddManager,var,varAux)); /* XNOR */ bdd_ref(ddTemp2 = bdd_bdd_and(ddManager,result,ddTemp)); bdd_recursive_deref(ddManager,result); bdd_recursive_deref(ddManager,ddTemp); result = ddTemp2; } } /* Finally put in f_i == f_i', where f_i = from) */ var = bdd_bdd_ith_var(ddManager,Ntk_NodeReadMddId(from)); index = SpfdNodeReadAuxId(applData,from); varAux = bdd_bdd_ith_var(ddManager,index); bdd_ref(ddTemp = bdd_bdd_xor(ddManager,var,varAux)); bdd_ref(ddTemp2 = bdd_bdd_and(ddManager,result,ddTemp)); bdd_recursive_deref(ddManager,result); bdd_recursive_deref(ddManager,ddTemp); result = ddTemp2; /* Compute AND of result and the SPFD of 'to'. */ toSpfd = SpfdNodeReadSpfd(applData,to); if (toSpfd == NIL(bdd_node)) { (void) fprintf(vis_stderr, "** spfd error: Spfd expected but not found.\n"); exit(0); } bdd_ref(wireSpfd = bdd_bdd_and(ddManager,toSpfd,result)); bdd_recursive_deref(ddManager,result); if (wireSpfd == logicZero) { /* Can the wire be removed? */ if (spfdVerbose > 1) (void) fprintf(vis_stdout, "** spfd info: Target wire %s --> %s has empty spfd.\n", Ntk_NodeReadName(from),Ntk_NodeReadName(to)); /* Insert the wire into wireTable */ if (st_lookup(wireTable,(char *)from,&sinkTable)) { st_insert(sinkTable,(char *)to,(char *)to); } else { sinkTable = st_init_table(st_ptrcmp,st_ptrhash); st_insert(sinkTable,(char *)to,(char *)to); st_insert(wireTable,(char *)from,(char *)sinkTable); } bdd_recursive_deref(ddManager,wireSpfd); } else if (replaceArray != NIL(array_t)) { /* Try for replacement. Exit after finding the first one. Here the assumption is that the nodes are sorted according to some criterion. */ replNode = SpfdTestIfNodeGlobalFuncSatisfiesWireSpfd(network,replaceArray, from,to,wireSpfd); bdd_recursive_deref(ddManager,wireSpfd); } else { bdd_recursive_deref(ddManager,wireSpfd); } } return replNode; } /* End of SpfdCheckIfWireIsRedundantOrReplaceable */ /**Function******************************************************************** Synopsis [Checks if the global functions implemented by nodes in 'replaceArray' satisfy the SPFD, 'wireSpfd' of 'from' --> 'to'.] SideEffects [None] ******************************************************************************/ Ntk_Node_t * SpfdTestIfNodeGlobalFuncSatisfiesWireSpfd( Ntk_Network_t *network, array_t *replaceArray, Ntk_Node_t *from, Ntk_Node_t *to, bdd_node *wireSpfd) { SpfdApplData_t *applData; bdd_manager *ddManager; st_table *leavesTable,*inUseVars,*replaceTable; st_table *sinkTable,*currBddReq; bdd_t *mddOne; lsGen gen; Ntk_Node_t *fanin,*node,*replNode; Ntk_Node_t *foundNode; array_t *nodeMvfs,*nodeBdds; bdd_node *bdd1,*xCube,*yVar; bdd_node **tempVars,**firstCompose,**secondCompose; bdd_node *step1,*step2,*step3,*step4,*step5; bdd_node *logicZero; int i,j,size,replId,id,auxId; applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network, SPFD_NETWORK_APPL_KEY); ddManager = applData->ddManager; inUseVars = applData->currInUseVars; replaceTable = applData->currReplaceTable; currBddReq = applData->currBddReq; mddOne = bdd_one(ddManager); logicZero = bdd_read_logic_zero(ddManager); /* Collect the leaf nodes of the network. */ leavesTable = st_init_table(st_ptrcmp, st_ptrhash); Ntk_NetworkForEachCombInput(network,gen,node) { st_insert(leavesTable,(char *)node,(char *) -1); } /* Compute the global MVFs of the nodes in replaceArray */ nodeMvfs = Ntm_NetworkBuildMvfs(network,replaceArray,leavesTable,mddOne); bdd_free(mddOne); st_free_table(leavesTable); /* Collect node global Bdds */ nodeBdds = array_alloc(bdd_node *,0); arrayForEachItem(Ntk_Node_t *,replaceArray,i,node) { Mvf_Function_t *mvf; mvf = array_fetch(Mvf_Function_t *,nodeMvfs,i); bdd1 = bdd_extract_node_as_is(array_fetch(bdd_t *,mvf,1)); bdd_ref(bdd1); array_insert_last(bdd_node *,nodeBdds,bdd1); } Mvf_FunctionArrayFree(nodeMvfs); /* Now check one at a time if global function satisfies wireSpfd */ foundNode = NIL(Ntk_Node_t); xCube = applData->currXCube; arrayForEachItem(Ntk_Node_t *,nodeBdds,i,bdd1) { int idAllocated; idAllocated = 0; replNode = array_fetch(Ntk_Node_t *,replaceArray,i); replId = Ntk_NodeReadMddId(replNode); /* Check if replId is already in use. This is possible is outside the cluster. */ if (st_lookup(inUseVars,(char *)(long)replId,NIL(char *))) { /* Allocate yVar and yAuxVar for replNode */ tempVars = SpfdAllocateTemporaryVariables(ddManager,inUseVars,1); yVar = tempVars[0]; idAllocated = 1; FREE(tempVars); } else { /* replId not in use */ yVar = bdd_bdd_ith_var(ddManager,replId); } /* Now perform the following steps, using two compositions. */ /* 1. step1 = yVar == bdd1 2. step2 = wireSpfd(Y,Y') --> wireSpfd(x,Y') 3. step3 = \exists_x step1 * step2 4. step4 = step3(yVar,Y') --> step3(yVar,x) 5. step5 = \exists_x step1 * step4 If step5 == logicZero, then replNode is a candidate */ /* Prepare compose arrays for the above steps */ size = bdd_num_vars(ddManager); firstCompose = ALLOC(bdd_node *,size); secondCompose = ALLOC(bdd_node *,size); for (j = 0; j < size; j++) { firstCompose[j] = bdd_bdd_ith_var(ddManager,j); secondCompose[j] = bdd_bdd_ith_var(ddManager,j); } Ntk_NodeForEachFanin(to,j,fanin) { id = Ntk_NodeReadMddId(fanin); auxId = SpfdNodeReadAuxId(applData,fanin); st_lookup(currBddReq,(char *)fanin,(char **)&firstCompose[id]); secondCompose[auxId] = firstCompose[id]; } bdd_ref(step1 = bdd_bdd_xnor(ddManager,yVar,bdd1)); bdd_ref(step2 = bdd_bdd_vector_compose(ddManager,wireSpfd,firstCompose)); FREE(firstCompose); bdd_ref(step3 = bdd_bdd_and_abstract(ddManager,step1,step2,xCube)); bdd_recursive_deref(ddManager,step2); bdd_ref(step4 = bdd_bdd_vector_compose(ddManager,step3,secondCompose)); bdd_recursive_deref(ddManager,step3); FREE(secondCompose); bdd_ref(step5 = bdd_bdd_and_abstract(ddManager,step1,step4,xCube)); bdd_recursive_deref(ddManager,step4); bdd_recursive_deref(ddManager,step1); /* Now if step5 is zero, then return replNode as the candidate. I will use the globalAlt field of the node to store the global BDD. This way I don't have to recompute the global BDD later. */ if (step5 == logicZero) { bdd_recursive_deref(ddManager,step5); bdd_ref(bdd1); SpfdNodeSetGlobalAlternative(applData,replNode,bdd1); /* Allocate an auxId for this node. It will be needed during reprogramming. */ if (idAllocated) { auxId = bdd_node_read_index(yVar); } else { tempVars = SpfdAllocateTemporaryVariables(ddManager,inUseVars,1); auxId = bdd_node_read_index(tempVars[0]); FREE(tempVars); } SpfdNodeSetAuxId(applData,replNode,auxId); st_insert(inUseVars,(char *)(long)replId,(char *)-1); st_insert(inUseVars,(char *)(long)auxId,(char *)-1); /* Insert information in replaceTable */ if (st_lookup(replaceTable,(char *)to,&sinkTable)) { st_insert(sinkTable,(char *)from,(char *)replNode); } else { sinkTable = st_init_table(st_ptrcmp,st_ptrhash); st_insert(sinkTable,(char *)from,(char *)replNode); st_insert(replaceTable,(char *)to,(char *)sinkTable); } foundNode = replNode; break; } else { bdd_recursive_deref(ddManager,step5); /* release the id */ if (idAllocated) { id = bdd_node_read_index(yVar); st_delete(inUseVars, &id, NIL(char *)); } } } /* Free the nodeBdds */ arrayForEachItem(bdd_node *,nodeBdds,i,bdd1) { bdd_recursive_deref(ddManager,bdd1); } array_free(nodeBdds); return foundNode; } /* End of SpfdTestIfNodeGlobalFuncSatisfiesWireSpfd */ /**Function******************************************************************** Synopsis [Try to remove/replace the fanin wires of maxNode.] SideEffects [None] SeeAlso [SpfdOptimizeFanoutWires] ******************************************************************************/ void SpfdOptimizeFaninWires( Ntk_Network_t *network, Ntk_Node_t *maxNode, int regionDepth, boolean replRem) { SpfdApplData_t *applData; array_t *faninArray; Ntk_Node_t *ntkNode,*fanout; char *dummy; int i,j; applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network, SPFD_NETWORK_APPL_KEY); /* replace/remove the fanin wire of maxNode one at a time. The fanin node with higher switched capacitance will be optimized first. */ faninArray = array_dup(Ntk_NodeReadFanins(maxNode)); if (spfdPerfSim) array_sort(faninArray,CompareConvexSwitchedCapAndDepth); else array_sort(faninArray,CompareConvexFanoutCountAndDepth); for (i = array_n(faninArray) - 1; i >=0; i--) { boolean skip; ntkNode = array_fetch(Ntk_Node_t *,faninArray,i); if (!st_lookup(applData->nodesRemoved,(char *)ntkNode,(char **)&dummy)) { skip = TRUE; /* Check if the current fanin node is still in the support of maxNode. */ Ntk_NodeForEachFanout(ntkNode,j,fanout) { if (fanout == maxNode) { skip = FALSE; break; } } } else { skip = TRUE; } if (!skip) SpfdOptimizeWire(network,ntkNode,maxNode,regionDepth,replRem); } array_free(faninArray); /* Lock the node */ SpfdNodeSetLocked(applData,maxNode,TRUE); return ; } /* End of SpfdOptimizeFaninWires */ /**Function******************************************************************** Synopsis [Try to remove/replace the fanout wires of maxNode.] SideEffects [None] SeeAlso [SpfdOptimizeFaninWires] ******************************************************************************/ void SpfdOptimizeFanoutWires( Ntk_Network_t *network, Ntk_Node_t *maxNode, int regionDepth, boolean replRem) { SpfdApplData_t *applData; array_t *fanoutArray; Ntk_Node_t *ntkNode,*fanout; int i,j; applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network, SPFD_NETWORK_APPL_KEY); /* replace/remove the fanout wires of maxNode one at a time. The fanout node with higher switched capacitance will be optimized first. */ fanoutArray = array_dup(Ntk_NodeReadFanouts(maxNode)); if (spfdPerfSim) array_sort(fanoutArray,CompareConvexSwitchedCapAndDepth); else array_sort(fanoutArray,CompareConvexFanoutCountAndDepth); for (i = array_n(fanoutArray) - 1; i >=0; i--) { boolean skip; ntkNode = array_fetch(Ntk_Node_t *,fanoutArray,i); skip = TRUE; /* Check if the maxNode is still in the support of fanout. */ Ntk_NodeForEachFanout(maxNode,j,fanout) { if (fanout == ntkNode) { skip = FALSE; break; } } if (!skip) SpfdOptimizeWire(network,maxNode,ntkNode,regionDepth,replRem); } array_free(fanoutArray); /* Lock the node */ SpfdNodeSetLocked(applData,maxNode,TRUE); return ; } /* End of SpfdOptimizeFanoutWires */ /**Function******************************************************************** Synopsis [Optimize all the fanin nodes of maxNode.] SideEffects [None] ******************************************************************************/ void SpfdOptimizeFaninNodes( Ntk_Network_t *network, Ntk_Node_t *maxNode, int regionDepth) { SpfdApplData_t *applData; array_t *faninArray; Ntk_Node_t *ntkNode; char *dummy; int i; applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network, SPFD_NETWORK_APPL_KEY); /* Optimize fanin nodes one at a time. The fanin node with higher switched capacitance will be optimized first. */ faninArray = array_dup(Ntk_NodeReadFanins(maxNode)); if (spfdPerfSim) array_sort(faninArray,CompareConvexSwitchedCapAndDepth); else array_sort(faninArray,CompareConvexFanoutCountAndDepth); for (i = array_n(faninArray) - 1; i >=0; i--) { boolean skip = FALSE; ntkNode = array_fetch(Ntk_Node_t *,faninArray,i); if (st_lookup(applData->nodesRemoved,(char *)ntkNode,(char **)&dummy)) { skip = TRUE; } if (!skip) SpfdOptimizeNode(network,ntkNode,regionDepth); } array_free(faninArray); /* Lock the node */ SpfdNodeSetLocked(applData,maxNode,TRUE); return ; } /* End of SpfdOptimizeFaninNodes */ /**Function******************************************************************** Synopsis [Optimize the cluster of nodes in the fanout the wire maxNode --> ntkNode. The cluster is formed of those nodes that are within 'regionDepth' of this wire. Both wire removal and replacement are performed if 'replRem' is true.] SideEffects [None] ******************************************************************************/ void SpfdOptimizeWire( Ntk_Network_t *network, Ntk_Node_t *maxNode, Ntk_Node_t *ntkNode, int regionDepth, boolean replRem) { SpfdApplData_t *applData; array_t *replArray; st_table *wiresRemoved,*sinkTable; st_generator *stGen; Ntk_Node_t *tempNode,*replNode; array_t *regionArray; int num; /* Package application data structure */ applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network, SPFD_NETWORK_APPL_KEY); /* Skip POs */ if (Ntk_NodeTestIsPrimaryOutput(ntkNode)) return; /* regionArray is an array of nodes sorted according to their depth. */ regionArray = SpfdNodeComputeFanoutRegion(applData,ntkNode,regionDepth); /* Analyze region's BDD requirements */ SpfdComputeRequiredGlobalBdds(network,applData); /* Analyze auxilarry BDD ID requirements */ SpfdAllocateOrReuseAuxVariables(network,applData); /* Order the fanin of internal and boundary nodes */ if (spfdPerfSim) { SpfdOrderFaninOfRegionNodes(network,applData, SpfdSwitchedCapAndDepthCompare); } else { SpfdOrderFaninOfRegionNodes(network,applData, SpfdFanoutCountAndDepthCompare); } /* Set the spfds for nodes in the region. The spfds are reduced to a single pair and the localAlt is set to one of the components of the single pair SPFD. */ SpfdRegionComputeSinglePairSpfd(network,applData,regionArray); /* Now check if the spfd of wire maxNode --> ntkNode is empty. Remove the spfd of ntkNode as it was not deleted in SpfdRegionComputeSinglePairSpfd */ /* Compute array of potential candidates for replacement */ if (replRem) replArray = SpfdNodeComputeTFIUntilDepth(ntkNode,regionDepth); else replArray = NIL(array_t); replNode = SpfdCheckIfWireIsRedundantOrReplaceable(network,applData, maxNode,ntkNode, replArray); /* SPFD of ntkNode is no longer needed. */ SpfdNodeDeleteSpfd(applData,ntkNode); if (replArray) array_free(replArray); /* Check to see if wires have been found to be redundant/replaceable. If no wires are to be removed/replaced, then decide whether or not to reprogram. */ if (st_count(applData->currWireTable) == 0 && st_count(applData->currReplaceTable) == 0 && !spfdReprogNoWire) { /* In this case just clean up currBddReq, localAlt and globalAlt. */ st_table *currBddReq; st_generator *stGen; Ntk_Node_t *regNode; bdd_node *bdd1; bdd_manager *ddManager; int j; ddManager = applData->ddManager; currBddReq = applData->currBddReq; /* Clean up currBddReq */ st_foreach_item(currBddReq,stGen,®Node,&bdd1) { bdd_recursive_deref(ddManager,bdd1); } st_free_table(currBddReq); applData->currBddReq = NIL(st_table); /* Clean up localAlt and globalAlt of region nodes */ arrayForEachItem(Ntk_Node_t *,regionArray,j,regNode) { SpfdNodeDeleteGlobalAlternative(applData,regNode); SpfdNodeDeleteLocalAlt(applData,regNode); } } else { /* Now reprogram the nodes in the region. */ SpfdReprogramRegionNodes(network,applData,regionArray); } /* In this subroutine we have only a single wire replaced. Delete just that data */ if (replNode) { SpfdNodeDeleteGlobalAlternative(applData,replNode); SpfdNodeSetAuxId(applData,replNode,-1); st_delete(applData->currReplaceTable,&ntkNode, &sinkTable); st_free_table(sinkTable); /* A small caveat: sometimes a wire added can be later removed. Check if the replNode --> ntkNode still exists. If not set replNode to NULL. */ wiresRemoved = applData->wiresRemoved; if (st_lookup(wiresRemoved,(char *)replNode,&sinkTable) && st_lookup(sinkTable,(char *)ntkNode,NIL(char *))) { /* Reduce the number of wires added and delete replNode->ntkNode from wiresRemoved table */ spfdWiresAdded--; st_delete(sinkTable,&ntkNode,NIL(char *)); if (st_count(sinkTable) < 1) { st_delete(wiresRemoved,&replNode,&sinkTable); st_free_table(sinkTable); } replNode = NIL(Ntk_Node_t); } } /* Clean up auxIds and piAltVars*/ SpfdCleanUpAuxIds(applData); /* Free stuff used only for the current wire */ if (applData->currXCube) { bdd_recursive_deref(applData->ddManager,applData->currXCube); applData->currXCube = NIL(bdd_node); } if (applData->currRegionNodes) { st_free_table(applData->currRegionNodes); applData->currRegionNodes = NIL(st_table); } if (applData->currInUseVars) { st_free_table(applData->currInUseVars); applData->currInUseVars = NIL(st_table); } num = st_count(applData->currWireTable); assert(num == 0); num = st_count(applData->currReplaceTable); assert(num == 0); /* Update the total number of wires removed. */ wiresRemoved = applData->wiresRemoved; if (st_count(wiresRemoved) > 0) { st_foreach_item(wiresRemoved,stGen,&tempNode, &sinkTable){ spfdNumWiresRem += st_count(sinkTable); } /* free the wiresRemoved contents */ st_foreach(wiresRemoved,SpfdStTableClean,NIL(char)); } /* Free regionArray (cluster) */ array_free(regionArray); return ; } /* End of SpfdOptimizeWire */ /**Function******************************************************************** Synopsis [Optimize the ntkNode. This is done by computing its SPFD derived from the output cluster. The cluster is formed of those nodes that are within 'regionDepth' in the fanout of ntkNode. Both wire removal and replacement are performed if 'replRem' is true.] SideEffects [None] ******************************************************************************/ void SpfdOptimizeNode( Ntk_Network_t *network, Ntk_Node_t *ntkNode, int regionDepth) { SpfdApplData_t *applData; st_table *wiresRemoved,*sinkTable; st_generator *stGen; Ntk_Node_t *tempNode; array_t *regionArray; int num; /* Package application data structure */ applData = (SpfdApplData_t *) Ntk_NetworkReadApplInfo(network, SPFD_NETWORK_APPL_KEY); /* Skip POs */ if (Ntk_NodeTestIsPrimaryOutput(ntkNode)) return; /* regionArray is an array of nodes sorted according to their depth. */ regionArray = SpfdNodeComputeFanoutRegion(applData,ntkNode,regionDepth); /* Analyze region's BDD requirements */ SpfdComputeRequiredGlobalBdds(network,applData); /* Analyze auxilarry BDD ID requirements */ SpfdAllocateOrReuseAuxVariables(network,applData); /* Order the fanin of internal and boundary nodes */ if (spfdPerfSim) { SpfdOrderFaninOfRegionNodes(network,applData, SpfdSwitchedCapAndDepthCompare); } else { SpfdOrderFaninOfRegionNodes(network,applData, SpfdFanoutCountAndDepthCompare); } /* Set the spfds for nodes in the region. The spfds are reduced to a single pair and the localAlt is set to one of the components of the single pair SPFD. */ SpfdRegionComputeSinglePairSpfd(network,applData,regionArray); /* Remove the spfd of ntkNode as it was not deleted in SpfdRegionComputeSinglePairSpfd */ /* SPFD of ntkNode is no longer needed. */ SpfdNodeDeleteSpfd(applData,ntkNode); /* Check to see if wires have been found to be redundant/replaceable. If no wires are to be removed/replaced, then decide whether or not to reprogram. */ if (st_count(applData->currWireTable) == 0 && !spfdReprogNoWire) { /* In this case just clean up currBddReq, localAlt and globalAlt. */ st_table *currBddReq; st_generator *stGen; Ntk_Node_t *regNode; bdd_node *bdd1; bdd_manager *ddManager; int j; ddManager = applData->ddManager; currBddReq = applData->currBddReq; /* Clean up currBddReq */ st_foreach_item(currBddReq,stGen,®Node,&bdd1) { bdd_recursive_deref(ddManager,bdd1); } st_free_table(currBddReq); applData->currBddReq = NIL(st_table); /* Clean up localAlt and globalAlt of region nodes */ arrayForEachItem(Ntk_Node_t *,regionArray,j,regNode) { SpfdNodeDeleteGlobalAlternative(applData,regNode); SpfdNodeDeleteLocalAlt(applData,regNode); } } else { /* Now reprogram the nodes in the region. */ SpfdReprogramRegionNodes(network,applData,regionArray); } /* Clean up auxIds and piAltVars*/ SpfdCleanUpAuxIds(applData); /* Free stuff used only for the current wire */ if (applData->currXCube) { bdd_recursive_deref(applData->ddManager,applData->currXCube); applData->currXCube = NIL(bdd_node); } if (applData->currRegionNodes) { st_free_table(applData->currRegionNodes); applData->currRegionNodes = NIL(st_table); } if (applData->currInUseVars) { st_free_table(applData->currInUseVars); applData->currInUseVars = NIL(st_table); } num = st_count(applData->currWireTable); assert(num == 0); num = st_count(applData->currReplaceTable); assert(num == 0); /* Update the total number of wires removed */ wiresRemoved = applData->wiresRemoved; if (st_count(wiresRemoved) > 0) { st_foreach_item(wiresRemoved,stGen,&tempNode, &sinkTable){ spfdNumWiresRem += st_count(sinkTable); } /* free the wiresRemoved contents */ st_foreach(wiresRemoved,SpfdStTableClean,NIL(char)); } /* Free regionArray (cluster) */ array_free(regionArray); /* Lock the node */ SpfdNodeSetLocked(applData,ntkNode,TRUE); return ; } /* End of SpfdOptimizeNode */ /*---------------------------------------------------------------------------*/ /* Definition of static functions */ /*---------------------------------------------------------------------------*/ /**Function******************************************************************** Synopsis [Compare the convex combination of fanout count and the node's topological depth.] SideEffects [None] ******************************************************************************/ static int CompareConvexFanoutCountAndDepth( const void *obj1, const void *obj2) { Ntk_Node_t *node1,*node2; Ntk_Network_t *network; float weight1,weight2; float load1,load2; int depth1,depth2; node1 = *(Ntk_Node_t **)obj1; node2 = *(Ntk_Node_t **)obj2; assert(Ntk_NodeReadNetwork(node1) == Ntk_NodeReadNetwork(node2)); network = Ntk_NodeReadNetwork(node1); if (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; } if (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 CompareConvexFanoutCountAndDepth */ /**Function******************************************************************** Synopsis [Compare the convex combination of switched capacitance and topological depth of two nodes.] SideEffects [None] ******************************************************************************/ static int CompareConvexSwitchedCapAndDepth( const void *obj1, const void *obj2) { Ntk_Node_t *node1,*node2; Ntk_Network_t *network; float weight1,weight2; float switch1,switch2; float load1,load2; int depth1,depth2; node1 = *(Ntk_Node_t **)obj1; node2 = *(Ntk_Node_t **)obj2; assert(Ntk_NodeReadNetwork(node1) == Ntk_NodeReadNetwork(node2)); network = Ntk_NodeReadNetwork(node1); if (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; } if (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 CompareConvexSwitchedCapAndDepth */