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

/**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; 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);
}


/**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; 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; 
}


/**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; 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;
}


/**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; 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;
}


/**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; 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]);
}


/**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; 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]);
}


/**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; 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 );*/
}


/**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; 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);
  }
}


/**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; 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);
  }
}


/**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;i<PCG->num_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;i<PCG->num_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; i<PCG->num_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;
}