// compute the utilization of each link in the ring at iteration
// step "iteration". Z is the congestion computed at the current step.
// The algorithm is different for each bias factor, but all of them
// adjust the utilization of the shortcut links in the same way.

*operation* void compute_utilization(Ring* ring, double Z, int iteration)
*traverse*
  *from* UtilAlg
  *to* {Factor0, Factor1, Factor2, Factor3, Factor4}
*wrapper* UtilAlg
  *suffix*
  (@
     ring->compute_shortcut_utilization();
   @)
*wrapper* Factor0
  (@
     ring->compute_utilization_bf0(Z);
  @)
*wrapper* Factor1
  (@
     ring->compute_utilization_bf1(Z);
  @)
*wrapper* Factor2
  (@
     ring->compute_utilization_bf2(Z, iteration);
   @)
*wrapper* Factor3
  (@
     ring->compute_utilization_bf3(Z);
   @)
*wrapper* Factor4
  (@
     ring->compute_utilization_bf4(Z);
  @)


// Bias factor 0.

*operation* void compute_utilization_bf0(double Z)
*traverse*
  *from* Ring
  *through* -> *, jumps, *   // ignore shortcuts at this stage
  *to* VirtualNeighbor
*wrapper* VirtualAdjacency
  (@
     double total_flow = *get_next_total_flow();
     get_next_util()->set_val(total_flow/Z);
  @)
*wrapper* VirtualNeighbor
  (@
     double total_flow = *get_total_flow();
     get_util()->set_val(total_flow/Z);
  @)     


// Bias factor 1

*operation* void compute_utilization_bf1(double Z)
*traverse*
  *from* Ring
  *through* -> *, jumps, *   // ignore shortcuts at this stage
  *to* VirtualNeighbor
*carry* *in* double average_util = (@ set_average_util() @)
*along*
  *from* VirtualAdjacency
  *through* -> *, jumps, *
  *to* VirtualNeighbor
*wrapper* Ring
  (@
     compute_utilization_bf0(Z);   // first compute standard utilization
  @)
*wrapper* VirtualAdjacency
  (@
     if (average_util)
       get_next_util()->set_val(average_util);
   @)
*wrapper* VirtualNeighbor
  (@
     if (average_util)
       get_util()->set_val(average_util);
   @)


// Bias factor 2

*operation* void compute_utilization_bf2(double Z, int iteration)
*traverse*
  *from* Ring
  *through* -> *, jumps, *   // ignore shortcuts at this stage
  *to* VirtualNeighbor
*wrapper* Ring
  (@
     compute_utilization_bf0(Z);   // first compute standard utilization
  @)
*wrapper* VirtualAdjacency
  (@
     double past_util = *get_next_past_util();
     double bf0_util = *get_next_util();
     double util = (bf0_util + past_util)/(double)iteration;
     get_next_util()->set_val(util);
     get_next_past_util()->set_val(past_util + util);
   @)
*wrapper* VirtualNeighbor
  (@
     double past_util = *get_past_util();
     double bf0_util = *get_util();
     double util = (bf0_util + past_util)/(double)iteration;
     get_util()->set_val(util);
     get_past_util()->set_val(past_util + util);
   @)


// Bias factor 3

*operation* void compute_utilization_bf3(double Z)
*traverse*
  *from* Ring
  *through* -> *, jumps, *   // ignore shortcuts at this stage
  *to* VirtualNeighbor
*wrapper* Ring
  (@
     compute_utilization_bf0(Z);   // first compute standard utilization
  @)
*wrapper* VirtualAdjacency
  (@
     double past_util = *get_next_past_util();
     double bf0_util = *get_next_util();
     double util = (bf0_util + past_util)/2.0;
     get_next_util()->set_val(util);
     get_next_past_util()->set_val(util);
   @)
*wrapper* VirtualNeighbor
  (@
     double past_util = *get_past_util();
     double bf0_util = *get_util();
     double util = (bf0_util + past_util)/2.0;
     get_util()->set_val(util);
     get_past_util()->set_val(util);
   @)


// Bias factor 4

*operation* void compute_utilization_bf4(double Z)
*traverse*
  *from* Ring
  *through* -> *, jumps, *   // ignore shortcuts at this stage
  *to* VirtualNeighbor
*wrapper* Ring
  (@
     compute_utilization_bf0(Z);   // first compute standard utilization
  @)
*wrapper* VirtualAdjacency
  (@
     double bf0_util = *get_next_util();
     if (bf0_util == 1.0)
       get_next_util()->set_val(0.5);
   @)
*wrapper* VirtualNeighbor
  (@
     double bf0_util = *get_util();
     if (bf0_util == 1.0)
       get_util()->set_val(0.5);
   @)


// The utilization of a shortcut link is equal to the utilization of
// the corresponding default link.

*operation* void compute_shortcut_utilization()
*traverse*
  *from* Ring
  *through* -> *, shortcuts, *
  *to* VirtualNeighbor
*carry* *in* Ring* ring = (@ this @)
*along*
  *from* Ring
  *through* -> *, shortcuts, *
  *to* VirtualNeighbor
*wrapper* VirtualNeighbor
  (@
     VirtualAdjacency* adj = ring->find(get_neighbor());
     VirtualAdjacency* prev_adj = ring->get_prevdefault(adj);
     double util = *(prev_adj->get_next_util());
     get_util()->set_val(util);
  @)


// set the utilization of each outgoing link to the average
// utilization of the outgoing links.

*operation* double set_average_util()
*init* (@ 0 @)
*traverse* 
  *from* VirtualAdjacency
  *through* -> *, jumps, *
  *to* VirtualNeighbor
*carry* *inout* int congested = (@ 0 @)
*along*
  *from* VirtualAdjacency
  *through* -> *, jumps, *
  *to* VirtualNeighbor
*wrapper* VirtualAdjacency
  *prefix*
  (@
     double util = *get_next_util();
     return_val += util;
     if (util == 1)
       congested = 1;
   @)
*wrapper* VirtualAdjacency
  *suffix*
  (@
     if (congested)
       return_val = return_val/(get_jumps()->list_length() + 1);
     else
       return_val = 0;
   @)
*wrapper* VirtualNeighbor
  (@
     double util = *get_util();
     return_val += util;
     if (util == 1)
       congested = 1;
  @)