/**CFile*********************************************************************** FileName [partFine.c] PackageName [part] Synopsis [Implements the partition of the network with respect to a list of nodes provided by the user.] Description [The network is composed of an arbitrary set of nodes, each of them implementing some function. This partitioning method will produce a graph representing the network in which the nodes specified in a list will be preserved in the graph structure. Different heuristics will control the structure of the rest of the partition.] SeeAlso [partInOut.c partTotal.c] Author [HoonSang Jin] 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 "partInt.h" static char rcsid[] UNUSED = "$Id: partFine.c,v 1.5 2005/04/30 04:00:38 fabio Exp $"; /*---------------------------------------------------------------------------*/ /* Constant declarations */ /*---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------*/ /* Structure declarations */ /*---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------*/ /* Type declarations */ /*---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------*/ /* Variable declarations */ /*---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------*/ /* Macro declarations */ /*---------------------------------------------------------------------------*/ #define PartVertexReadGeneric(vPtr) ((PartVertexInfo_t *)(vPtr)->user_data)->generic #define PartVertexReadGeneric1(vPtr) ((PartVertexInfo_t *)(vPtr)->user_data)->generic1 #define BASIC_PARTITION_UNIT 15 /**AutomaticStart*************************************************************/ /*---------------------------------------------------------------------------*/ /* Static function prototypes */ /*---------------------------------------------------------------------------*/ static int Part_IsFanoutInverter(Ntk_Node_t *node); /**AutomaticEnd***************************************************************/ /*---------------------------------------------------------------------------*/ /* Definition of exported functions */ /*---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------*/ /* Definition of internal functions */ /*---------------------------------------------------------------------------*/ /**Function******************************************************************** Synopsis [Implements the partition with respect to the given list of nodes.] Description [] SideEffects [] SeeAlso [PartPartitionTotal PartPartitionInputsOutputs] ******************************************************************************/ void PartPartitionFineGrain( Ntk_Network_t *network, graph_t *partition, mdd_t *careSet) { Ntk_Node_t *node; /* Pointer to iterate over nodes */ Mvf_Function_t *mddFunction; /* Pointer to a MDD */ mdd_manager *manager; /* Mdd manager in the partition */ st_table *tableOfLeaves; /* To store the leaves of the graph */ st_table *mddIdToNodeName; /* For quick lookup of node's name */ array_t *arrayOfMvf; /* To store the next state functions */ array_t *arrayOfRoots; /* To store the roots of the graph */ lsList sinkList; /* Vertices representing comb. outputs */ lsGen gen; /* To iterate over lists */ vertex_t *toVertex; /* Will hold the current function vertex */ int i; /* Index for loops */ long mddId; /* Will hold the mddId being processed */ st_table *mddSupport; /* To store the support of the Mvf_Function */ st_generator *stGen; /* To iterate over the MddIds of the support */ vertex_t *fromVertex; /* Will hold the current vertex in the support */ array_t *singletonMvfArray; array_t *singletonArrayOfRoots; array_t *tmpArrayOfMvf; Mvf_Function_t *nodeMvf; lsList sortedListOfNodes; array_t *sortedArrayOfPartitionNodes; array_t *unsortedArrayOfPartitionNodes; st_table *tableOfPartitionNodes; Ntk_Node_t *fanin, *fanout; manager = PartPartitionReadMddManager(partition); /* Make the combinational input nodes into leaves */ tableOfLeaves = st_init_table(st_ptrcmp, st_ptrhash); mddIdToNodeName = st_init_table(st_numcmp, st_numhash); Ntk_NetworkForEachCombInput(network, gen, node) { if(Ntk_NodeReadMddId(node) == NTK_UNASSIGNED_MDD_ID) Ord_NetworkAssignMddIdForNode(network, node); st_insert(tableOfLeaves, (char *)node, (char *) (long) (-1) ); st_insert(mddIdToNodeName, (char *) (long)Ntk_NodeReadMddId(node), Ntk_NodeReadName(node)); } unsortedArrayOfPartitionNodes = array_alloc(Ntk_Node_t *, 0); tableOfPartitionNodes = st_init_table(st_ptrcmp, st_ptrhash); /* Make the target node list for partition */ Ntk_NetworkForEachNode(network, gen, node) { if(Ntk_NodeTestIsShadow(node)) continue; else if(Ntk_NodeTestIsCombInput(node)) continue; else if(Ntk_NodeTestIsCombOutput(node)) continue; else if(Ntk_NodeReadNumFanouts(node) == 1) { fanout = Part_GetFanoutFreeLogic(node); if(Ntk_NodeTestIsCombOutput(fanout)); else if(Ntk_NodeReadNumFanins(node) > 10); else if(Ntk_NodeReadNumFanins(fanout) == 1) continue; else if(!Part_CheckLeafNodeCondition(node, tableOfPartitionNodes, 5, 10)) { if(Ntk_NodeReadNumFanins(node) == 1) { fanin = Part_GetFaninFreeLogic(node); if(!fanin) continue; if(Ntk_NodeTestIsCombInput(fanin)) continue; } continue; } /** if(Part_IsFanoutInverter(node)) continue; if(Ntk_NodeReadNumFanins(node) == 1) continue; **/ } /** else if(Ntk_NodeReadNumFanins(node) == 1) { fanin = Part_GetFaninFreeLogic(node); if(!fanin) continue; if(Ntk_NodeTestIsCombInput(fanin)) continue; } **/ array_insert_last(Ntk_Node_t *, unsortedArrayOfPartitionNodes, node); st_insert(tableOfPartitionNodes, (char *) node, (char *) (long) (-1)); } /* create sorted array of partition nodes */ sortedListOfNodes = Ntk_NetworkComputeTopologicalOrder(network, unsortedArrayOfPartitionNodes, tableOfLeaves); sortedArrayOfPartitionNodes = array_alloc(Ntk_Node_t *, 0); lsForEachItem(sortedListOfNodes, gen, node){ /* sortedListOfNodes includes many internal nodes, need to filter them out */ if(st_is_member(tableOfPartitionNodes, (char *) node)){ array_insert_last(Ntk_Node_t *, sortedArrayOfPartitionNodes, node); if(Ntk_NodeReadMddId(node) == NTK_UNASSIGNED_MDD_ID) Ord_NetworkAssignMddIdForNode(network, node); } } array_free(unsortedArrayOfPartitionNodes); lsDestroy(sortedListOfNodes, (void (*)(lsGeneric))0); st_free_table(tableOfPartitionNodes); tmpArrayOfMvf = array_alloc(Mvf_Function_t *, 0); for(i=0; i < array_n(sortedArrayOfPartitionNodes); i++){ node = array_fetch(Ntk_Node_t *, sortedArrayOfPartitionNodes, i); singletonArrayOfRoots = array_alloc(Ntk_Node_t *, 0); array_insert_last(Ntk_Node_t *, singletonArrayOfRoots, node); singletonMvfArray = Ntm_NetworkBuildMvfs(network, singletonArrayOfRoots, tableOfLeaves, careSet); nodeMvf = array_fetch(Mvf_Function_t *, singletonMvfArray, 0); array_insert_last(Mvf_Function_t *, tmpArrayOfMvf, nodeMvf); array_free(singletonMvfArray); array_free(singletonArrayOfRoots); if(Ntk_NodeReadMddId(node) == NTK_UNASSIGNED_MDD_ID){ Ord_NetworkAssignMddIdForNode(network, node); } st_insert(tableOfLeaves, (char *)node, (char *) (long) (-1) ); st_insert(mddIdToNodeName, (char *) (long)Ntk_NodeReadMddId(node), Ntk_NodeReadName(node)); } arrayOfRoots = array_alloc(Ntk_Node_t *, 0); Ntk_NetworkForEachCombOutput(network, gen, node) { array_insert_last(Ntk_Node_t *, arrayOfRoots, node); } arrayOfMvf = Ntm_NetworkBuildMvfs(network, arrayOfRoots, tableOfLeaves, careSet); array_append(arrayOfRoots, sortedArrayOfPartitionNodes); array_append(arrayOfMvf, tmpArrayOfMvf); array_free(sortedArrayOfPartitionNodes); array_free(tmpArrayOfMvf); /* Create one vertex for every component of arrayOfMvf */ for (i=0; i < array_n(arrayOfRoots); i++) { node = array_fetch(Ntk_Node_t *, arrayOfRoots, i); mddId = Ntk_NodeReadMddId(node); /* obtain the function attached to the node */ mddFunction = array_fetch(Mvf_Function_t *, arrayOfMvf, i); toVertex = g_add_vertex(partition); /* Update the look-up tables in the graph */ st_insert(PartPartitionReadNameToVertex(partition), Ntk_NodeReadName(node), (char *)toVertex); if (mddId != -1) { st_insert(PartPartitionReadMddIdToVertex(partition), (char *)(long) mddId, (char *)toVertex); } toVertex->user_data = (gGeneric)PartVertexInfoCreateSingle(Ntk_NodeReadName(node), mddFunction, mddId); } /* Read the list of vertices on the graph */ sinkList = lsCopy(g_get_vertices(partition), (lsGeneric (*)(lsGeneric))0); /* * For every function on every combinational output, compute the * support and create vertices in the graph when needed */ lsForEachItem(sinkList, gen, toVertex) { mddFunction = PartVertexReadFunction(toVertex); mddSupport = PartCreateFunctionSupportTable(mddFunction); /* * Create one edge (and one vertex if necessary) for every element * in mddSupport */ st_foreach_item(mddSupport, stGen, &mddId, NULL) { char *name; /* Create vertex with the information if needed */ if (st_lookup(PartPartitionReadMddIdToVertex(partition), (char *)(long) mddId, &fromVertex) == 0) { fromVertex = g_add_vertex(partition); st_lookup(mddIdToNodeName, (char *)(long) mddId, &name); /* Update the look-up tables in the graph */ st_insert(PartPartitionReadNameToVertex(partition), name, (char *)fromVertex); st_insert(PartPartitionReadMddIdToVertex(partition), (char *)(long) mddId, (char *)fromVertex); /* Create vertex data */ fromVertex->user_data = (gGeneric)PartVertexInfoCreateSingle(name, Mvf_FunctionCreateFromVariable(manager,mddId), mddId); } /* * Add the edge to the graph. Make sure a self loop is not added. The * self loop may be produced by a mdd that has in its support the same * variables that represent the mddId of the node. */ if (fromVertex != toVertex) { g_add_edge(fromVertex, toVertex); } /* End of if */ } /* End of st_foreach_item */ /* Clean the support table */ st_free_table(mddSupport); } /* End of lsForEachItem */ /* Clean up */ st_free_table(mddIdToNodeName); st_free_table(tableOfLeaves); array_free(arrayOfRoots); lsDestroy(sinkList, (void (*)(lsGeneric))0); /* * The contents of this array (array of mdds) is not deallocated because the * information has been transferred to the partition structure. All the * functions are stored now as part of the vertex information. */ array_free(arrayOfMvf); fprintf(stdout, "NOTICE : current peak memory = %ld\n", bdd_read_peak_memory(manager)); } /* End of PartPartitionCut */ /**Function******************************************************************** Synopsis [Check if the fanout of given node is inverter.] Description [ Check if the fanout of given node is inverter.] SideEffects [] SeeAlso [PartPartitionTotal PartPartitionInputsOutputs] ******************************************************************************/ int Part_IsFanoutInverter(Ntk_Node_t *node) { Ntk_Node_t *fanout; fanout = Part_GetFanoutFreeLogic(node); if(!fanout) return(1); if(Ntk_NodeReadNumFanins(fanout) == 1) return(1); else return(0); } /**Function******************************************************************** Synopsis [Check if the node can be assumed as leaf node based on given threshold.] Description [ This function identify the leaf node for fine grain partition based on threshold.] SideEffects [] SeeAlso [PartPartitionTotal PartPartitionInputsOutputs] ******************************************************************************/ int Part_CheckLeafNodeCondition(Ntk_Node_t *node, st_table *leafTable, int fanoutFreeLimit, int numVariableLimit) { int nVar, nDepth, i; Ntk_Node_t *fanout, *tnode, *tfanin; st_table *ownTable; nVar = Ntk_NodeReadNumFanins(node); nDepth = 0; fanout = node; ownTable = st_init_table(st_ptrcmp, st_ptrhash); while(1) { if(nDepth > fanoutFreeLimit)return(1); if(nVar > numVariableLimit) return(1); if(!st_lookup(leafTable, fanout, &tnode)) { fanout = Part_GetFanoutFreeLogic(fanout); if(fanout == 0) break; if(Ntk_NodeTestIsCombInput(fanout)) break; if(Ntk_NodeTestIsCombOutput(fanout)) break; } else break; nDepth++; if(fanout == 0) break; nVar += Img_CutCalcTransitiveFanin(leafTable, ownTable, fanout, node, numVariableLimit); if(nVar > numVariableLimit) { st_free_table(ownTable); return(1); } } Ntk_NodeForEachFanin(node, i, tfanin) { if(tfanin == 0) continue; if(Ntk_NodeReadNumFanouts(tfanin) != 1) continue; nVar += Img_CutCalcTransitiveFanin(leafTable, ownTable, tfanin, 0, numVariableLimit)-1; if(nVar > numVariableLimit) { st_free_table(ownTable); return(1); } } if(nVar > numVariableLimit) { st_free_table(ownTable); return(1); } /** fanin = node; nDepth = 0; while(1) { if(nDepth > fanoutFreeLimit)return(1); if(nVar > numVariableLimit) return(1); if(!st_lookup(leafTable, (char *)fanin, (char **)&tnode)) { Ntk_NodeForEachFanin(fanin, i, tfanin) { if(tfanin == 0) continue; if(Ntk_NodeReadNumFanouts(tfanin) != 1) continue; nVar += Ntk_NodeReadNumFanins(tfanin) - 1; } if(nVar > numVariableLimit) return(1); fanin = Part_GetFaninFreeLogic(fanin); if(fanin == 0) break; if(Ntk_NodeTestIsCombInput(fanin)) break; if(Ntk_NodeTestIsCombOutput(fanin)) break; } else break; nDepth++; } **/ return(0); } /**Function******************************************************************** Synopsis [Compute the number of support variables of given node.] Description [ Compute the number of support variables of given node.] SideEffects [] SeeAlso [PartPartitionTotal PartPartitionInputsOutputs] ******************************************************************************/ int Img_CutCalcTransitiveFanin(st_table *table, st_table *ownTable, Ntk_Node_t *node, Ntk_Node_t *fanin, int limit) { int i, nVar; Ntk_Node_t *tfanin, *tnode; nVar = 0; Ntk_NodeForEachFanin(node, i, tfanin) { if(tfanin == fanin) continue; if(tfanin == 0) continue; if(Ntk_NodeReadNumFanouts(tfanin) != 1){ if(!st_lookup(ownTable, tfanin, &tnode)) { st_insert(ownTable, tfanin, tfanin); nVar++; } continue; } if(Ntk_NodeTestIsCombInput(tfanin)) { if(!st_lookup(ownTable, tfanin, &tnode)) { st_insert(ownTable, tfanin, tfanin); nVar++; } continue; } if(Ntk_NodeTestIsCombOutput(tfanin)) { if(!st_lookup(ownTable, tfanin, &tnode)) { st_insert(ownTable, tfanin, tfanin); nVar++; } continue; } if(!st_lookup(table, tfanin, &tnode)) { nVar += Img_CutCalcTransitiveFanin(table, ownTable, tfanin, 0, limit); } else nVar++; if(nVar > limit) return(nVar); } return(nVar); } /**Function******************************************************************** Synopsis [Check if the fanin of given node is fanout free.] Description [Check if the fanin of given node is fanout free.] SideEffects [] SeeAlso [PartPartitionTotal PartPartitionInputsOutputs] ******************************************************************************/ Ntk_Node_t * Part_GetFaninFreeLogic(Ntk_Node_t *node) { int i; Ntk_Node_t *fanin; Ntk_NodeForEachFanin(node, i, fanin) { if(Ntk_NodeReadNumFanouts(fanin) != 1) continue; return(fanin); } return(0); } /**Function******************************************************************** Synopsis [Check if the fanout of given node is fanout free.] Description [Check if the fanout of given node is fanout free.] SideEffects [] SeeAlso [PartPartitionTotal PartPartitionInputsOutputs] ******************************************************************************/ Ntk_Node_t * Part_GetFanoutFreeLogic(Ntk_Node_t *node) { int i; Ntk_Node_t *fanout; if(Ntk_NodeReadNumFanouts(node) != 1) return(0); Ntk_NodeForEachFanout(node, i, fanout) { return(fanout); } return(0); }