/**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.] ******************************************************************************/ #include "ordInt.h" static char rcsid[] UNUSED = "$Id: ordPerm.c,v 1.9 2005/04/16 06:15:25 fabio Exp $"; /*---------------------------------------------------------------------------*/ /* Structure declarations */ /*---------------------------------------------------------------------------*/ typedef struct proc_pair { long proc_no; long var_no; } pair; typedef struct proc_struct { int num_loc_vars; array_t *o_list; /* of pair */ array_t *i_list; /* of pair */ } proc_struct; typedef struct Proc_Com_Graph { int num_vars; int num_proc; int *width_list; proc_struct *proc_list; int *locations; /* Array of length num_proc used as temporary storage by some functions */ int *variables; /* Array of length num_vars used as temporary storage by some functions */ } Proc_Com_Graph; /*---------------------------------------------------------------------------*/ /* Variable declarations */ /*---------------------------------------------------------------------------*/ /**Variable******************************************************************** Synopsis [required] Description [ CHOICE = 0 -->Look-ahead of 2 1 -->Look-ahead of 1 2 -->Touati's heuristic 3 -->Enter permutation manually 4 -->Random ordering] SeeAlso [optional] ******************************************************************************/ static int number_of_calls; /*---------------------------------------------------------------------------*/ /* Macro declarations */ /*---------------------------------------------------------------------------*/ /**AutomaticStart*************************************************************/ /*---------------------------------------------------------------------------*/ /* Static function prototypes */ /*---------------------------------------------------------------------------*/ 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); /**AutomaticEnd***************************************************************/ /*---------------------------------------------------------------------------*/ /* Definition of exported functions */ /*---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------*/ /* Definition of internal functions */ /*---------------------------------------------------------------------------*/ /**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] ******************************************************************************/ lsList OrdNetworkOrderRootsByPerm( Ntk_Network_t *network, int verbose) { 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; } /*---------------------------------------------------------------------------*/ /* Definition of static functions */ /*---------------------------------------------------------------------------*/ /**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] ******************************************************************************/ static lsList NetworkComputeLatchOrder( Ntk_Network_t * network, int verbose) { 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; jproc_list[i].o_list); j++) { cur_pair = array_fetch(pair *, PCG->proc_list[i].o_list, j); FREE(cur_pair); } for (j=0; jproc_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); } /**Function******************************************************************** Synopsis [required] Description [optional] SideEffects [required] SeeAlso [optional] ******************************************************************************/ static int * LatchPermutationCompute( Proc_Com_Graph *PCG, int choice, int verbose) { 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; } /**Function******************************************************************** Synopsis [required] Description [optional] SideEffects [required] SeeAlso [optional] ******************************************************************************/ static double rev_fac( int num_rev_bits) { double result; result = pow( ((double) 2.0),((double) num_rev_bits) ); return result; } /**Function******************************************************************** Synopsis [required] Description [Calculates the cost for a single cut that divides the permutation into 2.] SideEffects [required] SeeAlso [optional] ******************************************************************************/ static double cost_for_cut( Proc_Com_Graph * PCG, int * perm, int end_of_set1) { 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; inum_proc; i++) { PCG->locations[perm[i]]=2; } for (i=0; inum_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; jproc_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; inum_vars; i++) { if (PCG->variables[i] > 0) { ++forw ; } } for (i=0; inum_vars; i++) { PCG->variables[i]=0; } /* Count the # of reverse crossing bits */ /* for (i=end_of_set1+1; inum_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; inum_proc; i++) for (j=0; jproc_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; inum_vars; i++) { if (PCG->variables[i] > 0) { ++rev; } } { double rev_cost = rev_fac(rev); result = ((double) forw) + rev_cost; number_of_calls++; } return result; } /**Function******************************************************************** Synopsis [required] Description [Adds the next best element in the greedy sense as described for init_heur below.] SideEffects [required] SeeAlso [optional] ******************************************************************************/ static void append_best( int * opt_perm, int loc, Proc_Com_Graph * PCG) { 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; inum_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; jproc_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; } /**Function******************************************************************** Synopsis [required] Description [optional] SideEffects [required] SeeAlso [optional] ******************************************************************************/ static double cost_2( int * opt_perm, int loc, Proc_Com_Graph * PCG) { 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; } /**Function******************************************************************** Synopsis [required] Description [optional] SideEffects [required] SeeAlso [optional] ******************************************************************************/ static long int cost_touati_2( int * opt_perm, int loc, Proc_Com_Graph * PCG) { int i, j; long int result; pair *cur_pair; for (i=0; ilocations[opt_perm[i]]=1; } for (i=loc+1; inum_proc; i++) { PCG->locations[opt_perm[i]]=0; } for (i=0; inum_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; jproc_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; inum_vars; i++) { if (PCG->variables[i] != 0) { result++; } } for (i=0; inum_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; jproc_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; inum_vars; i++) { if (PCG->variables[i] != 0) { result++; } } return result; } /**Function******************************************************************** Synopsis [required] Description [optional] SideEffects [required] SeeAlso [optional] ******************************************************************************/ static void swap( int * opt_perm, int i, int j) { int temp; temp = opt_perm[i]; opt_perm[i] = opt_perm[j]; opt_perm[j] = temp; } /**Function******************************************************************** Synopsis [required] Description [optional] SideEffects [required] SeeAlso [optional] ******************************************************************************/ static void append_best_2( int * opt_perm, int loc, Proc_Com_Graph * PCG) { 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; inum_proc; i++) { swap(opt_perm,loc,i); for(j=loc+1; jnum_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]); } /**Function******************************************************************** Synopsis [required] Description [optional] SideEffects [required] SeeAlso [optional] ******************************************************************************/ static void append_touati_2( int * opt_perm, int loc, Proc_Com_Graph * PCG) { 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; inum_proc; i++) { swap(opt_perm,loc,i); for(j=loc+1; jnum_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]); } /**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] ******************************************************************************/ static void init_heur( Proc_Com_Graph * PCG, int * opt_perm) { int i; for(i=0; inum_proc; i++) { opt_perm[i] = i; } /*printf("\nEntering ordering code:\n");*/ for(i=0; inum_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 );*/ } /**Function******************************************************************** Synopsis [required] Description [optional] SideEffects [required] SeeAlso [optional] ******************************************************************************/ static void heur_2( Proc_Com_Graph * PCG, int * opt_perm) { int i; for(i=0; inum_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); } } /**Function******************************************************************** Synopsis [required] Description [optional] SideEffects [required] SeeAlso [optional] ******************************************************************************/ static void heur_touati_la2( Proc_Com_Graph * PCG, int * opt_perm) { int i; for(i=0; inum_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); } } /**Function******************************************************************** Synopsis [required] Description [Returns the ordering of processes that minimizes the bound.] SideEffects [required] SeeAlso [optional] ******************************************************************************/ static int * opt_proc_order( Proc_Com_Graph * PCG) { int *cur_opt; cur_opt = ALLOC(int, PCG->num_proc); heur_2(PCG, cur_opt); /*for (i=0;inum_proc; i++) printf(" %d ",cur_opt[i]+1);*/ return cur_opt; } /**Function******************************************************************** Synopsis [required] Description [Returns the ordering of processes that minimizes the bound.] SideEffects [required] SeeAlso [optional] ******************************************************************************/ static int * opt_touati_order( Proc_Com_Graph * PCG) { 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;inum_proc; i++) printf(" %d ",cur_opt[i]+1);*/ return cur_opt; } /**Function******************************************************************** Synopsis [required] Description [optional] SideEffects [required] SeeAlso [optional] ******************************************************************************/ static double cost_total( Proc_Com_Graph * PCG, int * perm) { int i; double cost=0; for(i=0; inum_proc-1; i++) { cost += cost_for_cut(PCG, perm, i); } return cost; } /**Function******************************************************************** Synopsis [required] Description [optional] SideEffects [required] SeeAlso [optional] ******************************************************************************/ static int * random_permutation( int seed, int n_elts) { 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; }