src/ord/ordPerm.c

Go to the documentation of this file.

#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                                                     */
/*---------------------------------------------------------------------------*/
static int number_of_calls;


/*---------------------------------------------------------------------------*/
/* Macro declarations                                                        */
/*---------------------------------------------------------------------------*/


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

/*---------------------------------------------------------------------------*/
/* Definition of exported functions                                          */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Definition of internal functions                                          */
/*---------------------------------------------------------------------------*/

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

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


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


static double
rev_fac(
  int  num_rev_bits)
{
  double result;
  
  result  = pow( ((double) 2.0),((double) num_rev_bits) );
 
  return result; 
}


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


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


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


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


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


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


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


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


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


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


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


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


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