src/ord/ordPerm.c File Reference
#include "ordInt.h"
Include dependency graph for ordPerm.c:
Go to the source code of this file.
Data Structures | |
| struct | proc_pair |
| struct | proc_struct |
| struct | Proc_Com_Graph |
Typedefs | |
| typedef struct proc_pair | pair |
| typedef struct proc_struct | proc_struct |
| typedef struct Proc_Com_Graph | Proc_Com_Graph |
Functions | |
| static lsList | NetworkComputeLatchOrder (Ntk_Network_t *network, int verbose) |
| static int * | LatchPermutationCompute (Proc_Com_Graph *PCG, int choice, int verbose) |
| static double | rev_fac (int num_rev_bits) |
| static double | cost_for_cut (Proc_Com_Graph *PCG, int *perm, int end_of_set1) |
| static void | append_best (int *opt_perm, int loc, Proc_Com_Graph *PCG) |
| static double | cost_2 (int *opt_perm, int loc, Proc_Com_Graph *PCG) |
| static long int | cost_touati_2 (int *opt_perm, int loc, Proc_Com_Graph *PCG) |
| static void | swap (int *opt_perm, int i, int j) |
| static void | append_best_2 (int *opt_perm, int loc, Proc_Com_Graph *PCG) |
| static void | append_touati_2 (int *opt_perm, int loc, Proc_Com_Graph *PCG) |
| static void | init_heur (Proc_Com_Graph *PCG, int *opt_perm) |
| static void | heur_2 (Proc_Com_Graph *PCG, int *opt_perm) |
| static void | heur_touati_la2 (Proc_Com_Graph *PCG, int *opt_perm) |
| static int * | opt_proc_order (Proc_Com_Graph *PCG) |
| static int * | opt_touati_order (Proc_Com_Graph *PCG) |
| static double | cost_total (Proc_Com_Graph *PCG, int *perm) |
| static int * | random_permutation (int seed, int n_elts) |
| lsList | OrdNetworkOrderRootsByPerm (Ntk_Network_t *network, int verbose) |
Variables | |
| static char rcsid[] | UNUSED = "$Id: ordPerm.c,v 1.9 2005/04/16 06:15:25 fabio Exp $" |
| static int | number_of_calls |
Typedef Documentation
| typedef struct Proc_Com_Graph Proc_Com_Graph |
| typedef struct proc_struct proc_struct |
Function Documentation
| static void append_best | ( | int * | opt_perm, |
| int | loc, | ||
| Proc_Com_Graph * | PCG | ||
| ) | [static] |
Function********************************************************************
Synopsis [required]
Description [Adds the next best element in the greedy sense as described for init_heur below.]
SideEffects [required]
SeeAlso [optional]
Definition at line 540 of file ordPerm.c.
{
int i, temp, bestswap, cur_fanout, best_fanout;
double cur_cost, best_cost;
int j;
pair *cur_pair;
best_cost = cost_for_cut(PCG, opt_perm, loc);
cur_cost = best_cost;
bestswap = loc;
best_fanout = 100000;
for(i=loc+1; i<PCG->num_proc; i++) {
temp = opt_perm[loc];
opt_perm[loc] = opt_perm[i];
opt_perm[i] = temp;
cur_cost = cost_for_cut(PCG, opt_perm, loc);
if ( cur_cost == best_cost ) {
cur_fanout = 0;
for ( j = 0 ; j <= loc ; j++ ) {
PCG->locations[opt_perm[j]] = 1;
}
for ( j = loc + 1 ; j < PCG->num_proc ; j++ ) {
PCG->locations[opt_perm[j]] = 2;
}
/* st_foreach_item( PCG->proc_list[opt_perm[i]].o_list,
stgen, ( char ** ) &bit_no, ( char ** ) &to_proc ) {
if ( PCG->locations[to_proc] == 2 ) {
cur_fanout++;
}
}
*/
for (j=0; j<array_n(PCG->proc_list[opt_perm[i]].o_list); j++) {
cur_pair = array_fetch(pair *, PCG->proc_list[opt_perm[i]].o_list, j);
if (PCG->locations[cur_pair->proc_no] ==2)
cur_fanout++;
}
if ( cur_fanout < best_fanout ) {
best_fanout = cur_fanout;
bestswap = i;
}
}
if (cur_cost < best_cost) {
best_cost = cur_cost;
bestswap = i;
}
temp = opt_perm[loc];
opt_perm[loc] = opt_perm[i];
opt_perm[i] = temp;
}
temp = opt_perm[loc];
opt_perm[loc] = opt_perm[bestswap];
opt_perm[bestswap] = temp;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static void append_best_2 | ( | int * | opt_perm, |
| int | loc, | ||
| Proc_Com_Graph * | PCG | ||
| ) | [static] |
Function********************************************************************
Synopsis [required]
Description [optional]
SideEffects [required]
SeeAlso [optional]
Definition at line 758 of file ordPerm.c.
{
double best_cost, cur_cost;
int i,j;
int best[2];
best_cost = cost_2(opt_perm, loc, PCG);
cur_cost = best_cost;
best[0] = loc;
best[1] = loc+1;
for(i=loc; i<PCG->num_proc; i++) {
swap(opt_perm,loc,i);
for(j=loc+1; j<PCG->num_proc; j++) {
swap(opt_perm,loc+1,j);
cur_cost = cost_2(opt_perm, loc, PCG);
if (cur_cost < best_cost) {
best_cost = cur_cost;
best[0] = i;
best[1] = j;
};
swap(opt_perm,loc+1,j);
}
swap(opt_perm,loc,i);
};
swap(opt_perm,loc,best[0]);
swap(opt_perm,loc+1,best[1]);
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static void append_touati_2 | ( | int * | opt_perm, |
| int | loc, | ||
| Proc_Com_Graph * | PCG | ||
| ) | [static] |
Function********************************************************************
Synopsis [required]
Description [optional]
SideEffects [required]
SeeAlso [optional]
Definition at line 805 of file ordPerm.c.
{
long int best_cost, cur_cost;
int i,j;
int best[2];
/*
* FIX: this is the same function as append_best_2, except that
* cost_touati_2 is used rather than cost_2; just pass the cost function in
* as a parameter.
*/
best_cost = cost_touati_2(opt_perm, loc, PCG);
cur_cost = best_cost;
best[0] = loc;
best[1] = loc+1;
for(i=loc; i<PCG->num_proc; i++) {
swap(opt_perm,loc,i);
for(j=loc+1; j<PCG->num_proc; j++) {
swap(opt_perm,loc+1,j);
cur_cost = cost_touati_2(opt_perm, loc, PCG);
if (cur_cost < best_cost) {
best_cost = cur_cost;
best[0] = i;
best[1] = j;
};
swap(opt_perm,loc+1,j);
}
swap(opt_perm,loc,i);
};
swap(opt_perm,loc,best[0]);
swap(opt_perm,loc+1,best[1]);
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static double cost_2 | ( | int * | opt_perm, |
| int | loc, | ||
| Proc_Com_Graph * | PCG | ||
| ) | [static] |
Function********************************************************************
Synopsis [required]
Description [optional]
SideEffects [required]
SeeAlso [optional]
Definition at line 623 of file ordPerm.c.
{
double cost_0 = cost_for_cut(PCG, opt_perm, loc);
double cost_1 = cost_for_cut(PCG, opt_perm, loc+1);
double result = cost_0 + cost_1;
return result;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static double cost_for_cut | ( | Proc_Com_Graph * | PCG, |
| int * | perm, | ||
| int | end_of_set1 | ||
| ) | [static] |
Function********************************************************************
Synopsis [required]
Description [Calculates the cost for a single cut that divides the permutation into 2.]
SideEffects [required]
SeeAlso [optional]
Definition at line 442 of file ordPerm.c.
{
int i, j;
double result;
int forw = 0, rev = 0;
pair *cur_pair;
for (i=0; i<=end_of_set1; i++) {
PCG->locations[perm[i]]=1;
}
for (i=end_of_set1+1; i<PCG->num_proc; i++) {
PCG->locations[perm[i]]=2;
}
for (i=0; i<PCG->num_vars; i++) {
PCG->variables[i]=0;
}
/* Count the # of forward crossing bits */
/* for (i=0; i<=end_of_set1; i++) {
st_foreach_item(PCG->proc_list[perm[i]].o_list,
gen,(char **)&bit_no,(char **)&to_proc) {
if (PCG->locations[to_proc] ==2) {
PCG->variables[bit_no]++ ;
}
}
}
*/
for (i=0; i<=end_of_set1; i++)
for (j=0; j<array_n(PCG->proc_list[perm[i]].o_list); j++) {
cur_pair = array_fetch(pair *, PCG->proc_list[perm[i]].o_list, j);
if (PCG->locations[cur_pair->proc_no] ==2) {
PCG->variables[cur_pair->var_no]++ ;
}
}
for (i=0; i<PCG->num_vars; i++) {
if (PCG->variables[i] > 0) {
++forw ;
}
}
for (i=0; i<PCG->num_vars; i++) {
PCG->variables[i]=0;
}
/* Count the # of reverse crossing bits */
/* for (i=end_of_set1+1; i<PCG->num_proc; i++) {
st_foreach_item(PCG->proc_list[perm[i]].o_list,
gen,(char **)&bit_no,(char **)&to_proc) {
if (PCG->locations[to_proc] ==1) {
PCG->variables[bit_no]++;
}
}
}
*/
for (i=end_of_set1+1; i<PCG->num_proc; i++)
for (j=0; j<array_n(PCG->proc_list[perm[i]].o_list); j++) {
cur_pair = array_fetch(pair *, PCG->proc_list[perm[i]].o_list, j);
if (PCG->locations[cur_pair->proc_no] ==1) {
PCG->variables[cur_pair->var_no]++ ;
}
}
for (i=0; i<PCG->num_vars; i++) {
if (PCG->variables[i] > 0) {
++rev;
}
}
{
double rev_cost = rev_fac(rev);
result = ((double) forw) + rev_cost;
number_of_calls++;
}
return result;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static double cost_total | ( | Proc_Com_Graph * | PCG, |
| int * | perm | ||
| ) | [static] |
Function********************************************************************
Synopsis [required]
Description [optional]
SideEffects [required]
SeeAlso [optional]
Definition at line 1009 of file ordPerm.c.
{
int i;
double cost=0;
for(i=0; i<PCG->num_proc-1; i++) {
cost += cost_for_cut(PCG, perm, i);
}
return cost;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static long int cost_touati_2 | ( | int * | opt_perm, |
| int | loc, | ||
| Proc_Com_Graph * | PCG | ||
| ) | [static] |
Function********************************************************************
Synopsis [required]
Description [optional]
SideEffects [required]
SeeAlso [optional]
Definition at line 650 of file ordPerm.c.
{
int i, j;
long int result;
pair *cur_pair;
for (i=0; i<loc; i++) {
PCG->locations[opt_perm[i]]=1;
}
for (i=loc+1; i<PCG->num_proc; i++) {
PCG->locations[opt_perm[i]]=0;
}
for (i=0; i<PCG->num_vars; i++)
PCG->variables[i]=0;
/* st_foreach_item(PCG->proc_list[opt_perm[loc]].i_list,
gen,(char **)&bit_no,(char **)&from_proc) {
if (PCG->locations[from_proc] == 0) {
PCG->variables[bit_no]++ ;
}
}
*/
for (j=0; j<array_n(PCG->proc_list[opt_perm[loc]].i_list); j++) {
cur_pair = array_fetch(pair *, PCG->proc_list[opt_perm[loc]].i_list, j);
if (PCG->locations[cur_pair->proc_no] ==0) {
PCG->variables[cur_pair->var_no]++ ;
}
}
result = 0;
for (i=0; i<PCG->num_vars; i++) {
if (PCG->variables[i] != 0) {
result++;
}
}
for (i=0; i<PCG->num_vars; i++)
PCG->variables[i]=0;
/* st_foreach_item(PCG->proc_list[opt_perm[loc+1]].i_list,
gen,(char **)&bit_no,(char **)&from_proc) {
if (PCG->locations[from_proc] == 0) {
PCG->variables[bit_no]++ ;
}
}
*/
for (j=0; j<array_n(PCG->proc_list[opt_perm[loc+1]].i_list); j++) {
cur_pair = array_fetch(pair *, PCG->proc_list[opt_perm[loc+1]].i_list, j);
if (PCG->locations[cur_pair->proc_no] ==0) {
PCG->variables[cur_pair->var_no]++ ;
}
}
for (i=0; i<PCG->num_vars; i++) {
if (PCG->variables[i] != 0) {
result++;
}
}
return result;
}
Here is the caller graph for this function:
| static void heur_2 | ( | Proc_Com_Graph * | PCG, |
| int * | opt_perm | ||
| ) | [static] |
Function********************************************************************
Synopsis [required]
Description [optional]
SideEffects [required]
SeeAlso [optional]
Definition at line 893 of file ordPerm.c.
{
int i;
for(i=0; i<PCG->num_proc; i++) {
opt_perm[i] = i;
}
for(i=0; i<(2*floor(((double)PCG->num_proc) / 2.0 )); i = i+2) {
/*printf("Iteration\t:\t%d(%d)\n", i, PCG->num_proc );*/
append_best_2(opt_perm,i,PCG);
}
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static void heur_touati_la2 | ( | Proc_Com_Graph * | PCG, |
| int * | opt_perm | ||
| ) | [static] |
Function********************************************************************
Synopsis [required]
Description [optional]
SideEffects [required]
SeeAlso [optional]
Definition at line 923 of file ordPerm.c.
{
int i;
for(i=0; i<PCG->num_proc; i++) {
opt_perm[i] = i;
}
for(i=0; i<(2*floor(((double)PCG->num_proc) / 2.0 )); i = i+2) {
/*printf("Iteration\t:\t%d(%d)\n", i, PCG->num_proc );*/
append_touati_2(opt_perm,i,PCG);
}
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static void init_heur | ( | Proc_Com_Graph * | PCG, |
| int * | opt_perm | ||
| ) | [static] |
Function********************************************************************
Synopsis [required]
Description [Returns an initial guess for the optimum permutation by forming it one element at a time at each step choosing the element that minimizes cost_for_cut for the set obtained by adding it to the first part of the permutation, writes the permutation to opt_perm.]
SideEffects [required]
SeeAlso [optional]
Definition at line 860 of file ordPerm.c.
{
int i;
for(i=0; i<PCG->num_proc; i++) {
opt_perm[i] = i;
}
/*printf("\nEntering ordering code:\n");*/
for(i=0; i<PCG->num_proc; i++) {
/*printf("Iteration\t:\t%d(%d)\n", i, PCG->num_proc );*/
append_best(opt_perm, i, PCG);
}
/*printf("\n\t--- Total number of calls = %d ---\n", number_of_calls );*/
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static int * LatchPermutationCompute | ( | Proc_Com_Graph * | PCG, |
| int | choice, | ||
| int | verbose | ||
| ) | [static] |
Function********************************************************************
Synopsis [required]
Description [optional]
SideEffects [required]
SeeAlso [optional]
Definition at line 374 of file ordPerm.c.
{
int *opt_perm;
if (choice == 0) {
opt_perm = opt_proc_order(PCG);
}
else if (choice == 1) {
opt_perm = ALLOC(int, PCG->num_proc);
init_heur(PCG, opt_perm);
}
else if (choice == 2) {
opt_perm = opt_touati_order(PCG);
}
else if (choice == 3) {
opt_perm = random_permutation(7,PCG->num_vars);
}
else {
fail("Unknown Option for Computing Latch Permutation");
}
if (verbose > 1) {
(void) fprintf(vis_stdout, "TOTAL COST= %e \n",cost_total(PCG,opt_perm));
}
return opt_perm;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static lsList NetworkComputeLatchOrder | ( | Ntk_Network_t * | network, |
| int | verbose | ||
| ) | [static] |
AutomaticStart
Function********************************************************************
Synopsis [Computes an ordering on the latches.]
Description [Computes an ordering on the latches, to be used for variable ordering. Returns a list of the corresponding latch data inputs (Ntk_Node_t ) giving the ordering. Implements the algorithm given in Aziz et al, "BDD Variable Ordering for Interacting FSMs", DAC 1994, p. 283.]
SideEffects [Creates a file in /tmp.]
SeeAlso [NetworkOrderNodes]
Definition at line 201 of file ordPerm.c.
{
int i, j;
lsGen listGen;
st_generator *stGen;
Ntk_Node_t *latch;
lsList tfoLatchList;
int *latchOrderArray;
long count = 0L;
st_table *idToLatch = st_init_table(st_numcmp, st_numhash);
int numLatches = Ntk_NetworkReadNumLatches(network);
st_table *latchDependencies = Ntk_NetworkComputeLatchDependencies(network);
lsList latchOrderList = lsCreate();
int latchOrderingMode = 1; /* FIX: make an option */
double convConstant = log10(2.0);
Proc_Com_Graph *PCG;
pair *cur_pair;
/*
* Assign unique integer between 0 and numLatches-1 to each latch. Store
* this correspondance in the idToLatch hash table.
* (NOTE: may be sensitive to ordering in memory.)
*/
Ntk_NetworkForEachLatch(network, listGen, latch) {
Ntk_NodeSetUndef(latch, (void *) count);
st_insert(idToLatch, (char *) count, (char *) latch);
count++;
}
/* Create a Proc_Com_Graph and write the communications
* structure of the network into it
*/
PCG = ALLOC(Proc_Com_Graph, 1);
PCG->num_proc = numLatches; /* SER (void) fprintf(pcgFile, "%d\n", numLatches); */
PCG->num_vars = numLatches; /* SER (void) fprintf(pcgFile, "%d\n", numLatches); */
PCG->proc_list = ALLOC(proc_struct, PCG->num_proc);
PCG->width_list= ALLOC(int, PCG->num_vars);
PCG->locations = ALLOC(int, PCG->num_proc);
PCG->variables = ALLOC(int, PCG->num_vars);
for(i=0;i< PCG->num_proc ; i++) {
PCG->proc_list[i].o_list= array_alloc(pair *, 0);
PCG->proc_list[i].i_list= array_alloc(pair *, 0);
};
/*
* For each latch/tfoLatchList pair, write information about the latch, and
* write the latches to which the latch fanouts. Finish the entry with "%%".
* Here is the general format for a process:
* process # list of local vars to process #
* fanout-latch : local-var-fanning-to width-of-local-var /
* ....
* fanout-latch : local-var-fanning-to width-of-local-var / %%
*
* When this format is specialized to case where each process is a single
* latch, then the format looks like:
* latch # latch #
* fanout-latch : latch width-of-latch /
* ....
* fanout-latch : latch width-of-latch / %%
*/
st_foreach_item(latchDependencies, stGen, &latch, &tfoLatchList) {
Ntk_Node_t *tfoLatch;
int varWidth;
long var_no, fr_no, to_no;
/*
* Write the latch id and the cardinality of the latch variable
* domain.
*/
fr_no = (long) Ntk_NodeReadUndef(latch);
PCG->proc_list[fr_no].num_loc_vars = 1;
/*
* For each transitive fanout latch, write the tfoLatch id, the latch
* id, and the width of the latch variable (assumes minimum
* encoding). Width is ceiling(log2(number of values in domain)).
*/
varWidth = (int) ceil(log10
((double)Var_VariableReadNumValues(Ntk_NodeReadVariable(latch)))
/ convConstant);
lsForEachItem(tfoLatchList, listGen, tfoLatch) {
to_no = (long) Ntk_NodeReadUndef(tfoLatch);
var_no = (long) Ntk_NodeReadUndef(latch);
cur_pair = ALLOC(pair,1);
cur_pair->proc_no = to_no;
cur_pair->var_no = var_no;
array_insert_last(pair *, PCG->proc_list[fr_no].o_list, cur_pair);
cur_pair = ALLOC(pair,1);
cur_pair->proc_no = fr_no;
cur_pair->var_no = var_no;
array_insert_last(pair *, PCG->proc_list[to_no].i_list, cur_pair);
PCG->width_list[var_no] = varWidth;
}
}
/*
* We don't need the latchDependencies table anymore. Free the list stored
* at each value, and then free the table itself.
*/
st_foreach_item(latchDependencies, stGen, &latch, &tfoLatchList) {
(void) lsDestroy(tfoLatchList, (void (*) (lsGeneric)) NULL);
}
st_free_table(latchDependencies);
/*
* Compute the order on the latches. This is returned as an array of
* integers, where the latch whose id is latchOrderArray[i] is ordered in
* the ith position of latchOrderList. Note that the returned list actually
* contains the latch data inputs, not the latches themselves.
*/
latchOrderArray = LatchPermutationCompute(PCG, latchOrderingMode, verbose);
for (i=0; i < PCG->num_proc; i++) {
for (j=0; j<array_n(PCG->proc_list[i].o_list); j++) {
cur_pair = array_fetch(pair *, PCG->proc_list[i].o_list, j);
FREE(cur_pair);
}
for (j=0; j<array_n(PCG->proc_list[i].i_list); j++) {
cur_pair = array_fetch(pair *, PCG->proc_list[i].i_list, j);
FREE(cur_pair);
}
array_free(PCG->proc_list[i].o_list);
array_free(PCG->proc_list[i].i_list);
}
FREE(PCG->proc_list);
FREE(PCG->width_list);
FREE(PCG->variables);
FREE(PCG->locations);
FREE(PCG);
for (i = 0; i < numLatches; i++) {
int status UNUSED = st_lookup(idToLatch,
(char *) (long) (latchOrderArray[i]),
&latch);
assert(status);
(void) lsNewEnd(latchOrderList, (lsGeneric) Ntk_LatchReadDataInput(latch), LS_NH);
}
/*
* We are done with idToLatch and latchOrderArray.
*/
st_free_table(idToLatch);
FREE(latchOrderArray);
return (latchOrderList);
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static int * opt_proc_order | ( | Proc_Com_Graph * | PCG | ) | [static] |
Function********************************************************************
Synopsis [required]
Description [Returns the ordering of processes that minimizes the bound.]
SideEffects [required]
SeeAlso [optional]
Definition at line 952 of file ordPerm.c.
{
int *cur_opt;
cur_opt = ALLOC(int, PCG->num_proc);
heur_2(PCG, cur_opt);
/*for (i=0;i<PCG->num_proc; i++) printf(" %d ",cur_opt[i]+1);*/
return cur_opt;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static int * opt_touati_order | ( | Proc_Com_Graph * | PCG | ) | [static] |
Function********************************************************************
Synopsis [required]
Description [Returns the ordering of processes that minimizes the bound.]
SideEffects [required]
SeeAlso [optional]
Definition at line 979 of file ordPerm.c.
{
int *cur_opt;
/*
* FIX: same function as opt_proc_order except for heuristic call.
*/
cur_opt = ALLOC(int, PCG->num_proc);
heur_touati_la2(PCG, cur_opt);
/*for (i=0;i<PCG->num_proc; i++) printf(" %d ",cur_opt[i]+1);*/
return cur_opt;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| lsList OrdNetworkOrderRootsByPerm | ( | Ntk_Network_t * | network, |
| int | verbose | ||
| ) |
AutomaticEnd Function********************************************************************
Synopsis [Computes a total ordering on the combinational outputs of a network.]
Description [Computes a total ordering on the combinational outputs of a network. First, the algorithm orders the data inputs using the permutation algorithm (Aziz et al, "BDD Variable Ordering for Interacting FSMs", DAC 1994, p. 283). Then, it orders the remaining combinational outputs in order of decreasing depth. Finally, the second list is appended to the first.]
SideEffects []
SeeAlso [OrdNetworkComputeNodeDepths]
Definition at line 142 of file ordPerm.c.
{
lsGen gen;
Ntk_Node_t *node;
lsList dataInputs;
st_table *processedTable = st_init_table(st_ptrcmp, st_ptrhash);
lsList otherCombOuts = lsCreate();
/*
* Create a list of all combinational outputs that are not data inputs to
* latches. A node can drive more than one latch data input, latch initial
* input, or primary output. Use a hash table to ensure that no node appears
* twice in the list.
*/
Ntk_NetworkForEachCombOutput(network, gen, node) {
if (!Ntk_NodeTestIsLatchDataInput(node)) {
OrdNodeAddToList(otherCombOuts, processedTable, node);
}
}
st_free_table(processedTable);
/* Compute depth of all roots in otherCombOuts. */
OrdNetworkComputeNodeDepths(network, otherCombOuts);
/* Sort otherCombOuts based on depth. */
lsSort(otherCombOuts, OrdNodesFromListCompareDepth);
/* Compute order on dataInputs roots using the permutation method. */
dataInputs = NetworkComputeLatchOrder(network, verbose);
/* Add the otherCombOuts list to the end of the dataInputs list. */
Ord_ListAppendList(dataInputs, otherCombOuts);
(void) lsDestroy(otherCombOuts, (void (*) (lsGeneric)) NULL);
return dataInputs;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| static int * random_permutation | ( | int | seed, |
| int | n_elts | ||
| ) | [static] |
Function********************************************************************
Synopsis [required]
Description [optional]
SideEffects [required]
SeeAlso [optional]
Definition at line 1037 of file ordPerm.c.
{
int i, j;
int *permutation;
int *remaining;
int next_entry;
int next_value;
int n_entries;
if (n_elts <= 0) {
return NIL(int);
}
n_entries = n_elts;
permutation = ALLOC(int, n_entries);
remaining = ALLOC(int, n_entries);
for (i = 0; i < n_entries; i++) {
remaining[i] = i;
}
util_srandom((long) seed);
next_entry = 0;
for (; n_entries > 0; n_entries--) {
next_value = util_random() % n_entries;
permutation[next_entry++] = remaining[next_value];
for (j = next_value; j < n_entries - 1; j++) {
remaining[j] = remaining[j + 1];
}
}
FREE(remaining);
return permutation;
}
Here is the caller graph for this function:
| static double rev_fac | ( | int | num_rev_bits | ) | [static] |
Function********************************************************************
Synopsis [required]
Description [optional]
SideEffects [required]
SeeAlso [optional]
Definition at line 418 of file ordPerm.c.
{
double result;
result = pow( ((double) 2.0),((double) num_rev_bits) );
return result;
}
Here is the caller graph for this function:
| static void swap | ( | int * | opt_perm, |
| int | i, | ||
| int | j | ||
| ) | [static] |
Function********************************************************************
Synopsis [required]
Description [optional]
SideEffects [required]
SeeAlso [optional]
Definition at line 733 of file ordPerm.c.
{
int temp;
temp = opt_perm[i];
opt_perm[i] = opt_perm[j];
opt_perm[j] = temp;
}
Here is the caller graph for this function:
Variable Documentation
int number_of_calls [static] |
char rcsid [] UNUSED = "$Id: ordPerm.c,v 1.9 2005/04/16 06:15:25 fabio Exp $" [static] |
CFile***********************************************************************
FileName [ordPerm.c]
PackageName [ord]
Synopsis [Routines to find permutation on latches to minimize MDD size.]
Author [Serdar Tasiran, Tom Shiple]
Copyright [Copyright (c) 1994-1996 The Regents of the Univ. of California. All rights reserved.
Permission is hereby granted, without written agreement and without license or royalty fees, to use, copy, modify, and distribute this software and its documentation for any purpose, provided that the above copyright notice and the following two paragraphs appear in all copies of this software.
IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]
