source: vis_dev/vis-2.3/src/ord/ordPerm.c @ 36

Last change on this file since 36 was 14, checked in by cecile, 13 years ago

vis2.3

File size: 28.4 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [ordPerm.c]
4
5  PackageName [ord]
6
7  Synopsis    [Routines to find permutation on latches to minimize MDD size.]
8
9  Author      [Serdar Tasiran, Tom Shiple]
10
11  Copyright   [Copyright (c) 1994-1996 The Regents of the Univ. of California.
12  All rights reserved.
13
14  Permission is hereby granted, without written agreement and without license
15  or royalty fees, to use, copy, modify, and distribute this software and its
16  documentation for any purpose, provided that the above copyright notice and
17  the following two paragraphs appear in all copies of this software.
18
19  IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
20  DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
21  OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
22  CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
23
24  THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
25  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
26  FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN
27  "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE
28  MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]
29
30******************************************************************************/
31
32#include "ordInt.h"
33
34static char rcsid[] UNUSED = "$Id: ordPerm.c,v 1.9 2005/04/16 06:15:25 fabio Exp $";
35
36/*---------------------------------------------------------------------------*/
37/* Structure declarations                                                     */
38/*---------------------------------------------------------------------------*/
39
40typedef struct proc_pair {
41    long proc_no;
42    long var_no;
43} pair;
44
45typedef struct proc_struct {
46  int num_loc_vars;
47  array_t *o_list; /* of pair */
48  array_t *i_list; /* of pair */
49} proc_struct; 
50
51typedef struct Proc_Com_Graph {
52    int          num_vars;
53    int          num_proc;
54    int         *width_list;
55    proc_struct *proc_list;
56    int         *locations;      /* Array of length num_proc used as temporary storage by some
57                                    functions */
58    int         *variables;      /* Array of length num_vars used as temporary storage by some
59                                    functions */
60   
61} Proc_Com_Graph;
62
63
64/*---------------------------------------------------------------------------*/
65/* Variable declarations                                                     */
66/*---------------------------------------------------------------------------*/
67/**Variable********************************************************************
68
69  Synopsis    [required]
70
71  Description [
72  CHOICE = 0 -->Look-ahead of 2
73           1 -->Look-ahead of 1
74           2 -->Touati's heuristic
75           3 -->Enter permutation manually
76           4 -->Random ordering]
77
78  SeeAlso     [optional]
79
80******************************************************************************/
81static int number_of_calls;
82
83
84/*---------------------------------------------------------------------------*/
85/* Macro declarations                                                        */
86/*---------------------------------------------------------------------------*/
87
88
89/**AutomaticStart*************************************************************/
90
91/*---------------------------------------------------------------------------*/
92/* Static function prototypes                                                */
93/*---------------------------------------------------------------------------*/
94
95static lsList NetworkComputeLatchOrder(Ntk_Network_t * network, int verbose);
96static int * LatchPermutationCompute(Proc_Com_Graph *PCG, int choice, int verbose);
97static double rev_fac(int num_rev_bits);
98static double cost_for_cut(Proc_Com_Graph * PCG, int * perm, int end_of_set1);
99static void append_best(int * opt_perm, int loc, Proc_Com_Graph * PCG);
100static double cost_2(int * opt_perm, int loc, Proc_Com_Graph * PCG);
101static long int cost_touati_2(int * opt_perm, int loc, Proc_Com_Graph * PCG);
102static void swap(int * opt_perm, int i, int j);
103static void append_best_2(int * opt_perm, int loc, Proc_Com_Graph * PCG);
104static void append_touati_2(int * opt_perm, int loc, Proc_Com_Graph * PCG);
105static void init_heur(Proc_Com_Graph * PCG, int * opt_perm);
106static void heur_2(Proc_Com_Graph * PCG, int * opt_perm);
107static void heur_touati_la2(Proc_Com_Graph * PCG, int * opt_perm);
108static int * opt_proc_order(Proc_Com_Graph * PCG);
109static int * opt_touati_order(Proc_Com_Graph * PCG);
110static double cost_total(Proc_Com_Graph * PCG, int * perm);
111static int * random_permutation(int seed, int n_elts);
112
113/**AutomaticEnd***************************************************************/
114
115
116/*---------------------------------------------------------------------------*/
117/* Definition of exported functions                                          */
118/*---------------------------------------------------------------------------*/
119
120
121/*---------------------------------------------------------------------------*/
122/* Definition of internal functions                                          */
123/*---------------------------------------------------------------------------*/
124
125/**Function********************************************************************
126
127  Synopsis [Computes a total ordering on the combinational outputs of a
128  network.]
129
130  Description [Computes a total ordering on the combinational outputs of a
131  network. First, the algorithm orders the data inputs using the permutation
132  algorithm (Aziz et al, "BDD Variable Ordering for Interacting FSMs", DAC
133  1994, p. 283).  Then, it orders the remaining combinational outputs in order
134  of decreasing depth.  Finally, the second list is appended to the first.]
135
136  SideEffects []
137
138  SeeAlso     [OrdNetworkComputeNodeDepths]
139
140******************************************************************************/
141lsList
142OrdNetworkOrderRootsByPerm(
143  Ntk_Network_t *network,
144  int verbose)
145{
146  lsGen gen;
147  Ntk_Node_t *node;
148  lsList dataInputs;
149  st_table *processedTable = st_init_table(st_ptrcmp, st_ptrhash);
150  lsList otherCombOuts = lsCreate();
151
152  /*
153   * Create a list of all combinational outputs that are not data inputs to
154   * latches. A node can drive more than one latch data input, latch initial
155   * input, or primary output. Use a hash table to ensure that no node appears
156   * twice in the list.
157   */
158  Ntk_NetworkForEachCombOutput(network, gen, node) {
159    if (!Ntk_NodeTestIsLatchDataInput(node)) {
160      OrdNodeAddToList(otherCombOuts, processedTable, node);
161    }
162  }
163  st_free_table(processedTable);
164
165  /* Compute depth of all roots in otherCombOuts. */
166  OrdNetworkComputeNodeDepths(network, otherCombOuts);
167
168  /* Sort otherCombOuts based on depth. */
169  lsSort(otherCombOuts, OrdNodesFromListCompareDepth);
170
171  /* Compute order on dataInputs roots using the permutation method. */
172  dataInputs = NetworkComputeLatchOrder(network, verbose);
173
174  /* Add the otherCombOuts list to the end of the dataInputs list. */
175  Ord_ListAppendList(dataInputs, otherCombOuts);
176  (void) lsDestroy(otherCombOuts, (void (*) (lsGeneric)) NULL);
177 
178  return dataInputs;
179}
180
181
182/*---------------------------------------------------------------------------*/
183/* Definition of static functions                                            */
184/*---------------------------------------------------------------------------*/
185
186/**Function********************************************************************
187
188  Synopsis    [Computes an ordering on the latches.]
189
190  Description [Computes an ordering on the latches, to be used for variable
191  ordering.  Returns a list of the corresponding latch data inputs (Ntk_Node_t
192  *) giving the ordering.  Implements the algorithm given in Aziz et al, "BDD
193  Variable Ordering for Interacting FSMs", DAC 1994, p. 283.]
194
195  SideEffects [Creates a file in /tmp.]
196
197  SeeAlso     [NetworkOrderNodes]
198
199******************************************************************************/
200static lsList
201NetworkComputeLatchOrder(
202  Ntk_Network_t * network,
203  int verbose)
204{
205  int           i, j;
206  lsGen         listGen;
207  st_generator *stGen;
208  Ntk_Node_t   *latch;
209  lsList        tfoLatchList;
210  int          *latchOrderArray;
211  long          count             = 0L;
212  st_table     *idToLatch         = st_init_table(st_numcmp, st_numhash);
213  int           numLatches        = Ntk_NetworkReadNumLatches(network);
214  st_table     *latchDependencies = Ntk_NetworkComputeLatchDependencies(network);
215  lsList        latchOrderList    = lsCreate();
216  int           latchOrderingMode = 1;  /* FIX: make an option */
217  double        convConstant      = log10(2.0);
218  Proc_Com_Graph *PCG;
219  pair         *cur_pair;
220 
221  /*
222   * Assign unique integer between 0 and numLatches-1 to each latch.  Store
223   * this correspondance in the idToLatch hash table.
224   * (NOTE: may be sensitive to ordering in memory.)
225   */
226  Ntk_NetworkForEachLatch(network, listGen, latch) {
227    Ntk_NodeSetUndef(latch, (void *) count);
228    st_insert(idToLatch, (char *) count, (char *) latch);
229    count++;
230  }
231
232  /* Create a Proc_Com_Graph and write the communications
233   * structure of the network into it
234   */
235 
236  PCG = ALLOC(Proc_Com_Graph, 1);
237  PCG->num_proc = numLatches; /*  SER (void) fprintf(pcgFile, "%d\n", numLatches);  */
238  PCG->num_vars = numLatches; /*  SER (void) fprintf(pcgFile, "%d\n", numLatches);  */
239
240  PCG->proc_list = ALLOC(proc_struct, PCG->num_proc);
241  PCG->width_list= ALLOC(int, PCG->num_vars);
242  PCG->locations = ALLOC(int, PCG->num_proc); 
243  PCG->variables = ALLOC(int, PCG->num_vars);
244
245  for(i=0;i< PCG->num_proc ; i++) {
246      PCG->proc_list[i].o_list= array_alloc(pair *, 0);
247      PCG->proc_list[i].i_list= array_alloc(pair *, 0);
248  };
249
250  /*
251   * For each latch/tfoLatchList pair, write information about the latch, and
252   * write the latches to which the latch fanouts. Finish the entry with "%%".
253   * Here is the general format for a process:
254   * process # list of local vars to process #
255   *     fanout-latch : local-var-fanning-to  width-of-local-var /
256   *       ....
257   *     fanout-latch : local-var-fanning-to  width-of-local-var / %%
258   *
259   * When this format is specialized to case where each process is a single
260   * latch, then the format looks like:
261   * latch # latch #
262   *     fanout-latch : latch  width-of-latch /
263   *       ....
264   *     fanout-latch : latch  width-of-latch / %%
265   */
266  st_foreach_item(latchDependencies, stGen, &latch, &tfoLatchList) {
267    Ntk_Node_t *tfoLatch;
268    int         varWidth;
269    long        var_no, fr_no, to_no;
270   
271
272    /*
273     * Write the latch id and the cardinality of the latch variable
274     * domain.
275     */
276    fr_no =  (long) Ntk_NodeReadUndef(latch);
277    PCG->proc_list[fr_no].num_loc_vars = 1;
278   
279   
280    /*
281     * For each transitive fanout latch, write the tfoLatch id, the latch
282     * id, and the width of the latch variable (assumes minimum
283     * encoding). Width is ceiling(log2(number of values in domain)).
284     */
285    varWidth = (int) ceil(log10
286             ((double)Var_VariableReadNumValues(Ntk_NodeReadVariable(latch)))
287                          / convConstant);
288    lsForEachItem(tfoLatchList, listGen, tfoLatch) {
289        to_no = (long) Ntk_NodeReadUndef(tfoLatch);
290        var_no = (long) Ntk_NodeReadUndef(latch);
291
292        cur_pair = ALLOC(pair,1);
293        cur_pair->proc_no = to_no;
294        cur_pair->var_no = var_no;
295        array_insert_last(pair *, PCG->proc_list[fr_no].o_list, cur_pair);
296
297        cur_pair = ALLOC(pair,1);
298        cur_pair->proc_no = fr_no;
299        cur_pair->var_no = var_no;         
300        array_insert_last(pair *, PCG->proc_list[to_no].i_list, cur_pair);
301       
302        PCG->width_list[var_no] = varWidth;
303    }
304  }
305
306  /*
307   * We don't need the latchDependencies table anymore.  Free the list stored
308   * at each value, and then free the table itself.
309   */
310  st_foreach_item(latchDependencies, stGen, &latch, &tfoLatchList) {
311    (void) lsDestroy(tfoLatchList, (void (*) (lsGeneric)) NULL);
312  }
313  st_free_table(latchDependencies);
314
315  /*
316   * Compute the order on the latches. This is returned as an array of
317   * integers, where the latch whose id is latchOrderArray[i] is ordered in
318   * the ith position of latchOrderList. Note that the returned list actually
319   * contains the latch data inputs, not the latches themselves.
320   */
321  latchOrderArray = LatchPermutationCompute(PCG, latchOrderingMode, verbose);
322 
323  for (i=0; i < PCG->num_proc; i++) {
324      for (j=0; j<array_n(PCG->proc_list[i].o_list); j++) {
325              cur_pair = array_fetch(pair *, PCG->proc_list[i].o_list, j);
326              FREE(cur_pair);
327      }
328
329      for (j=0; j<array_n(PCG->proc_list[i].i_list); j++) {
330              cur_pair = array_fetch(pair *, PCG->proc_list[i].i_list, j);
331              FREE(cur_pair);
332      }
333     
334      array_free(PCG->proc_list[i].o_list);
335      array_free(PCG->proc_list[i].i_list);
336  }
337
338  FREE(PCG->proc_list);
339  FREE(PCG->width_list);
340  FREE(PCG->variables);
341  FREE(PCG->locations);
342  FREE(PCG);
343 
344  for (i = 0; i < numLatches; i++) {
345    int status UNUSED = st_lookup(idToLatch,
346                                  (char *) (long) (latchOrderArray[i]),
347                                  &latch);
348    assert(status);
349    (void) lsNewEnd(latchOrderList, (lsGeneric) Ntk_LatchReadDataInput(latch), LS_NH);
350  }
351
352  /*
353   * We are done with idToLatch and latchOrderArray.
354   */
355  st_free_table(idToLatch);
356  FREE(latchOrderArray); 
357 
358  return (latchOrderList);
359}
360
361
362/**Function********************************************************************
363
364  Synopsis    [required]
365
366  Description [optional]
367
368  SideEffects [required]
369
370  SeeAlso     [optional]
371
372******************************************************************************/
373static int *
374LatchPermutationCompute(
375  Proc_Com_Graph *PCG,
376  int choice,
377  int verbose)
378{
379  int *opt_perm;
380
381  if (choice == 0) {     
382      opt_perm = opt_proc_order(PCG);
383  }
384  else if (choice == 1) {
385    opt_perm = ALLOC(int, PCG->num_proc);
386    init_heur(PCG, opt_perm);
387  }
388  else if (choice == 2) {
389    opt_perm = opt_touati_order(PCG);
390  }
391  else if (choice == 3) {
392    opt_perm = random_permutation(7,PCG->num_vars);
393  }
394  else {
395    fail("Unknown Option for Computing Latch Permutation");
396  }
397
398  if (verbose > 1) {
399    (void) fprintf(vis_stdout, "TOTAL COST= %e \n",cost_total(PCG,opt_perm));
400  }
401 
402  return opt_perm;
403}
404
405
406/**Function********************************************************************
407
408  Synopsis    [required]
409
410  Description [optional]
411
412  SideEffects [required]
413
414  SeeAlso     [optional]
415
416******************************************************************************/
417static double
418rev_fac(
419  int  num_rev_bits)
420{
421  double result;
422 
423  result  = pow( ((double) 2.0),((double) num_rev_bits) );
424 
425  return result; 
426}
427
428
429/**Function********************************************************************
430
431  Synopsis    [required]
432
433  Description [Calculates the cost for a single cut that divides the
434  permutation into 2.]
435
436  SideEffects [required]
437
438  SeeAlso     [optional]
439
440******************************************************************************/
441static double
442cost_for_cut(
443  Proc_Com_Graph * PCG,
444  int * perm,
445  int  end_of_set1)
446{
447  int i, j;
448  double result; 
449  int forw  = 0,  rev = 0; 
450  pair *cur_pair;
451 
452  for (i=0; i<=end_of_set1; i++) {
453    PCG->locations[perm[i]]=1;
454  }
455       
456  for (i=end_of_set1+1; i<PCG->num_proc; i++) {
457    PCG->locations[perm[i]]=2;
458  }
459
460  for (i=0; i<PCG->num_vars; i++) {
461    PCG->variables[i]=0;
462  }
463       
464  /* Count the # of   forward crossing  bits   */
465/*  for (i=0; i<=end_of_set1; i++) {
466    st_foreach_item(PCG->proc_list[perm[i]].o_list,
467                    gen,(char **)&bit_no,(char **)&to_proc) { 
468      if (PCG->locations[to_proc] ==2)  {
469        PCG->variables[bit_no]++ ;
470      }
471    }
472  }
473*/
474  for (i=0; i<=end_of_set1; i++) 
475      for (j=0; j<array_n(PCG->proc_list[perm[i]].o_list); j++) {
476          cur_pair = array_fetch(pair *, PCG->proc_list[perm[i]].o_list, j);
477          if (PCG->locations[cur_pair->proc_no] ==2)  {
478              PCG->variables[cur_pair->var_no]++ ;
479          }     
480      }
481 
482 
483  for (i=0; i<PCG->num_vars; i++) {
484    if (PCG->variables[i] > 0) {
485      ++forw ;
486    }
487  }
488
489  for (i=0; i<PCG->num_vars; i++) {
490    PCG->variables[i]=0;
491  }
492
493  /* Count the # of   reverse crossing  bits   */
494/*  for (i=end_of_set1+1; i<PCG->num_proc; i++) {
495    st_foreach_item(PCG->proc_list[perm[i]].o_list,
496                    gen,(char **)&bit_no,(char **)&to_proc) { 
497      if (PCG->locations[to_proc] ==1)  {
498        PCG->variables[bit_no]++;
499      }
500    }
501  }
502  */
503  for (i=end_of_set1+1; i<PCG->num_proc; i++) 
504      for (j=0; j<array_n(PCG->proc_list[perm[i]].o_list); j++) {
505          cur_pair = array_fetch(pair *, PCG->proc_list[perm[i]].o_list, j);
506          if (PCG->locations[cur_pair->proc_no] ==1)  {
507              PCG->variables[cur_pair->var_no]++ ;
508          }     
509      }
510
511     
512  for (i=0; i<PCG->num_vars; i++) {
513    if (PCG->variables[i] > 0) {
514      ++rev;
515    }
516  }
517
518  {
519    double rev_cost = rev_fac(rev);
520    result =  ((double) forw) + rev_cost;
521    number_of_calls++;
522  }
523  return result; 
524}
525
526
527/**Function********************************************************************
528
529  Synopsis    [required]
530
531  Description [Adds the next best element in the greedy sense as described for
532  init_heur below.]
533
534  SideEffects [required]
535
536  SeeAlso     [optional]
537
538******************************************************************************/
539static void
540append_best(
541  int * opt_perm,
542  int  loc,
543  Proc_Com_Graph * PCG)
544{
545  int i,  temp, bestswap, cur_fanout, best_fanout; 
546  double cur_cost, best_cost;
547  int j;
548  pair *cur_pair;
549   
550  best_cost = cost_for_cut(PCG, opt_perm, loc);
551  cur_cost = best_cost;
552  bestswap = loc;
553
554  best_fanout = 100000;
555  for(i=loc+1; i<PCG->num_proc;  i++) {
556      temp = opt_perm[loc];
557      opt_perm[loc] = opt_perm[i];
558      opt_perm[i] = temp;
559     
560      cur_cost = cost_for_cut(PCG, opt_perm, loc);
561     
562      if ( cur_cost == best_cost ) {
563          cur_fanout = 0;
564         
565          for ( j = 0 ; j <= loc ; j++ ) {
566              PCG->locations[opt_perm[j]] = 1;
567          }
568                       
569          for ( j = loc + 1 ; j < PCG->num_proc ; j++ ) {
570              PCG->locations[opt_perm[j]] = 2;
571          }
572     
573/*          st_foreach_item( PCG->proc_list[opt_perm[i]].o_list,
574                           stgen, ( char ** ) &bit_no, ( char ** )  &to_proc ) {
575              if ( PCG->locations[to_proc] == 2 ) {
576                  cur_fanout++;
577              }
578          }
579*/         
580          for (j=0; j<array_n(PCG->proc_list[opt_perm[i]].o_list); j++) {
581              cur_pair = array_fetch(pair *, PCG->proc_list[opt_perm[i]].o_list, j);
582              if (PCG->locations[cur_pair->proc_no] ==2)
583                  cur_fanout++;
584          }
585         
586         
587         
588         
589          if ( cur_fanout < best_fanout ) {
590              best_fanout = cur_fanout;
591              bestswap = i;
592          }
593      }
594     
595      if (cur_cost < best_cost) {
596          best_cost = cur_cost;
597          bestswap = i;
598      }
599
600      temp = opt_perm[loc];
601      opt_perm[loc] = opt_perm[i];
602      opt_perm[i] = temp;
603  }
604
605  temp = opt_perm[loc];
606  opt_perm[loc] = opt_perm[bestswap];
607  opt_perm[bestswap] = temp;
608}
609
610
611/**Function********************************************************************
612
613  Synopsis    [required]
614
615  Description [optional]
616
617  SideEffects [required]
618
619  SeeAlso     [optional]
620
621******************************************************************************/
622static double
623cost_2(
624  int * opt_perm,
625  int  loc,
626  Proc_Com_Graph * PCG)
627{
628   
629  double cost_0 = cost_for_cut(PCG, opt_perm, loc);
630  double cost_1 = cost_for_cut(PCG, opt_perm, loc+1);
631  double result = cost_0 + cost_1;
632 
633  return result;
634   
635}
636
637
638/**Function********************************************************************
639
640  Synopsis    [required]
641
642  Description [optional]
643
644  SideEffects [required]
645
646  SeeAlso     [optional]
647
648******************************************************************************/
649static long int
650cost_touati_2(
651  int * opt_perm,
652  int  loc,
653  Proc_Com_Graph * PCG)
654{
655  int i, j;
656  long int result;
657  pair *cur_pair;
658
659
660  for (i=0; i<loc; i++) {
661      PCG->locations[opt_perm[i]]=1;
662  }
663
664  for (i=loc+1; i<PCG->num_proc; i++) {
665      PCG->locations[opt_perm[i]]=0;
666  }
667
668  for (i=0; i<PCG->num_vars; i++)
669      PCG->variables[i]=0;
670 
671/*  st_foreach_item(PCG->proc_list[opt_perm[loc]].i_list,
672                  gen,(char **)&bit_no,(char **)&from_proc) { 
673    if (PCG->locations[from_proc] == 0)  {
674      PCG->variables[bit_no]++ ;
675    }
676  }
677*/
678 
679  for (j=0; j<array_n(PCG->proc_list[opt_perm[loc]].i_list); j++) {
680      cur_pair = array_fetch(pair *, PCG->proc_list[opt_perm[loc]].i_list, j);
681      if (PCG->locations[cur_pair->proc_no] ==0)  {
682          PCG->variables[cur_pair->var_no]++ ;
683      }     
684  }
685
686  result = 0;
687  for (i=0; i<PCG->num_vars; i++)  {
688    if (PCG->variables[i] != 0) {
689      result++;
690    }
691  }
692                                                             
693  for (i=0; i<PCG->num_vars; i++)
694      PCG->variables[i]=0;
695
696/*  st_foreach_item(PCG->proc_list[opt_perm[loc+1]].i_list,
697                  gen,(char **)&bit_no,(char **)&from_proc) { 
698    if (PCG->locations[from_proc] == 0)  {
699      PCG->variables[bit_no]++ ;
700    }
701  }
702  */
703
704  for (j=0; j<array_n(PCG->proc_list[opt_perm[loc+1]].i_list); j++) {
705      cur_pair = array_fetch(pair *, PCG->proc_list[opt_perm[loc+1]].i_list, j);
706      if (PCG->locations[cur_pair->proc_no] ==0)  {
707          PCG->variables[cur_pair->var_no]++ ;
708      }     
709  }
710 
711  for (i=0; i<PCG->num_vars; i++)  {
712    if (PCG->variables[i] != 0) {
713      result++;
714    }
715  }
716
717  return result;
718}
719
720
721/**Function********************************************************************
722
723  Synopsis    [required]
724
725  Description [optional]
726
727  SideEffects [required]
728
729  SeeAlso     [optional]
730
731******************************************************************************/
732static void
733swap(
734  int * opt_perm,
735  int  i,
736  int  j)
737{
738  int temp;
739
740  temp = opt_perm[i];
741  opt_perm[i] = opt_perm[j];
742  opt_perm[j] = temp;
743}
744
745
746/**Function********************************************************************
747
748  Synopsis    [required]
749
750  Description [optional]
751
752  SideEffects [required]
753
754  SeeAlso     [optional]
755
756******************************************************************************/
757static void
758append_best_2(
759  int * opt_perm,
760  int  loc,
761  Proc_Com_Graph * PCG)
762{
763  double best_cost, cur_cost;
764  int i,j;
765  int best[2];
766
767
768  best_cost = cost_2(opt_perm, loc, PCG); 
769  cur_cost =  best_cost;
770  best[0] = loc;
771  best[1] = loc+1;
772
773  for(i=loc; i<PCG->num_proc;  i++) {
774    swap(opt_perm,loc,i);
775    for(j=loc+1; j<PCG->num_proc;  j++) {
776      swap(opt_perm,loc+1,j);
777      cur_cost = cost_2(opt_perm, loc, PCG);
778      if (cur_cost < best_cost) {
779        best_cost = cur_cost;
780        best[0] = i;
781        best[1] = j;
782      };
783      swap(opt_perm,loc+1,j);
784    }
785    swap(opt_perm,loc,i);
786  };
787
788  swap(opt_perm,loc,best[0]);
789  swap(opt_perm,loc+1,best[1]);
790}
791
792
793/**Function********************************************************************
794
795  Synopsis    [required]
796
797  Description [optional]
798
799  SideEffects [required]
800
801  SeeAlso     [optional]
802
803******************************************************************************/
804static void
805append_touati_2(
806  int * opt_perm,
807  int  loc,
808  Proc_Com_Graph * PCG)
809{
810  long int best_cost, cur_cost;
811  int i,j;
812  int best[2];
813
814  /*
815   * FIX: this is the same function as append_best_2, except that
816   * cost_touati_2 is used rather than cost_2; just pass the cost function in
817   * as a parameter.
818   */
819
820  best_cost = cost_touati_2(opt_perm, loc, PCG); 
821  cur_cost =  best_cost;
822  best[0] = loc;
823  best[1] = loc+1;
824
825  for(i=loc; i<PCG->num_proc;  i++) {
826    swap(opt_perm,loc,i);
827    for(j=loc+1; j<PCG->num_proc;  j++) {
828      swap(opt_perm,loc+1,j);
829      cur_cost = cost_touati_2(opt_perm, loc, PCG);
830      if (cur_cost < best_cost) {
831        best_cost = cur_cost;
832        best[0] = i;
833        best[1] = j;
834      };
835      swap(opt_perm,loc+1,j);
836    }
837    swap(opt_perm,loc,i);
838  };
839
840  swap(opt_perm,loc,best[0]);
841  swap(opt_perm,loc+1,best[1]);
842}
843
844
845/**Function********************************************************************
846
847  Synopsis    [required]
848
849  Description [Returns an initial guess for the optimum permutation by forming
850  it one element at a time at each step choosing the element that minimizes
851  cost_for_cut for the set obtained by adding it to the first part of the
852  permutation, writes the permutation to opt_perm.]
853
854  SideEffects [required]
855
856  SeeAlso     [optional]
857
858******************************************************************************/
859static void
860init_heur(
861  Proc_Com_Graph * PCG,
862  int * opt_perm)
863{
864  int i; 
865     
866  for(i=0; i<PCG->num_proc; i++) {
867    opt_perm[i]  = i;
868  }
869
870 
871 
872  /*printf("\nEntering ordering code:\n");*/
873  for(i=0; i<PCG->num_proc; i++)  {
874    /*printf("Iteration\t:\t%d(%d)\n", i, PCG->num_proc );*/
875    append_best(opt_perm,  i,  PCG); 
876  }
877  /*printf("\n\t--- Total number of calls = %d ---\n",  number_of_calls );*/
878}
879
880
881/**Function********************************************************************
882
883  Synopsis    [required]
884
885  Description [optional]
886
887  SideEffects [required]
888
889  SeeAlso     [optional]
890
891******************************************************************************/
892static void
893heur_2(
894  Proc_Com_Graph * PCG,
895  int * opt_perm)
896{
897
898  int i;
899
900  for(i=0; i<PCG->num_proc; i++) {
901    opt_perm[i]  = i;
902  }
903
904  for(i=0; i<(2*floor(((double)PCG->num_proc) / 2.0 )); i = i+2) { 
905    /*printf("Iteration\t:\t%d(%d)\n", i, PCG->num_proc );*/
906    append_best_2(opt_perm,i,PCG);
907  }
908}
909
910
911/**Function********************************************************************
912
913  Synopsis    [required]
914
915  Description [optional]
916
917  SideEffects [required]
918
919  SeeAlso     [optional]
920
921******************************************************************************/
922static void
923heur_touati_la2(
924  Proc_Com_Graph * PCG,
925  int * opt_perm)
926{
927  int i;
928
929  for(i=0; i<PCG->num_proc; i++) {
930    opt_perm[i]  = i;
931  }
932
933  for(i=0; i<(2*floor(((double)PCG->num_proc) / 2.0 )); i = i+2) {
934                                /*printf("Iteration\t:\t%d(%d)\n", i, PCG->num_proc );*/
935    append_touati_2(opt_perm,i,PCG);
936  }
937}
938
939
940/**Function********************************************************************
941
942  Synopsis    [required]
943
944  Description [Returns the ordering of processes that minimizes the bound.]
945
946  SideEffects [required]
947
948  SeeAlso     [optional]
949
950******************************************************************************/
951static int *
952opt_proc_order(
953  Proc_Com_Graph * PCG)
954{
955  int *cur_opt;
956
957       
958  cur_opt = ALLOC(int, PCG->num_proc);
959  heur_2(PCG, cur_opt);
960   
961  /*for (i=0;i<PCG->num_proc; i++) printf(" %d ",cur_opt[i]+1);*/
962
963  return  cur_opt;
964}
965
966
967/**Function********************************************************************
968
969  Synopsis    [required]
970
971  Description [Returns the ordering of processes that minimizes the bound.]
972
973  SideEffects [required]
974
975  SeeAlso     [optional]
976
977******************************************************************************/
978static int *
979opt_touati_order(
980  Proc_Com_Graph * PCG)
981{
982  int *cur_opt;
983
984
985  /*
986   * FIX: same function as opt_proc_order except for heuristic call.
987   */
988 
989  cur_opt = ALLOC(int, PCG->num_proc);
990  heur_touati_la2(PCG, cur_opt);
991   
992  /*for (i=0;i<PCG->num_proc; i++) printf(" %d ",cur_opt[i]+1);*/
993
994  return  cur_opt;
995}
996 
997/**Function********************************************************************
998
999  Synopsis    [required]
1000
1001  Description [optional]
1002
1003  SideEffects [required]
1004
1005  SeeAlso     [optional]
1006
1007******************************************************************************/
1008static double
1009cost_total(
1010  Proc_Com_Graph * PCG,
1011  int * perm)
1012{
1013  int i;
1014
1015  double cost=0;
1016
1017  for(i=0; i<PCG->num_proc-1; i++) {
1018    cost += cost_for_cut(PCG, perm, i);
1019  }
1020       
1021  return  cost;
1022}
1023
1024
1025/**Function********************************************************************
1026
1027  Synopsis    [required]
1028
1029  Description [optional]
1030
1031  SideEffects [required]
1032
1033  SeeAlso     [optional]
1034
1035******************************************************************************/
1036static int *
1037random_permutation(
1038  int  seed,
1039  int  n_elts)
1040{
1041  int i, j;
1042  int *permutation;
1043  int *remaining;
1044  int next_entry;
1045  int next_value;
1046  int n_entries;
1047
1048  if (n_elts <= 0) {
1049    return NIL(int);
1050  }
1051
1052  n_entries = n_elts;
1053  permutation = ALLOC(int, n_entries);
1054  remaining = ALLOC(int, n_entries);
1055  for (i = 0; i < n_entries; i++) {
1056    remaining[i] = i;
1057  }
1058
1059  util_srandom((long) seed);
1060
1061  next_entry = 0;
1062  for (; n_entries > 0; n_entries--) {
1063    next_value = util_random() % n_entries;
1064    permutation[next_entry++] = remaining[next_value];
1065    for (j = next_value; j < n_entries - 1; j++) {
1066      remaining[j] = remaining[j + 1];
1067    }
1068  }
1069  FREE(remaining);
1070  return permutation;
1071}
Note: See TracBrowser for help on using the repository browser.