Marc de Kruijf dekruijf at cs.wisc.edu
Wed Nov 19 10:22:52 EST 2008

```Hello all,

I am confused about the internal workings of the canneal application, and
was wondering if someone could help explain a partiular part of the program
to me.

The goal of the algorithm is to minimize chip routing costs.  It does this
by computing the cost/benefit associated with swapping pairs of elements,
probabilistically executing the swap based on this cost/benefit value, and
iterating until the solution becomes stable.  So far so good.  Now here's
the code which computes the cost/benefit for a given element:

----
routing_cost_t netlist_elem::swap_cost(location_t* old_loc, location_t*
new_loc)
{
routing_cost_t no_swap = 0;
routing_cost_t yes_swap = 0;

for (int i = 0; i< fanin.size(); ++i){
location_t* fanin_loc = fanin[i]->present_loc.Get();
no_swap += fabs(old_loc->x - fanin_loc->x);
no_swap += fabs(old_loc->y - fanin_loc->y);

yes_swap += fabs(new_loc->x - fanin_loc->x);
yes_swap += fabs(new_loc->y - fanin_loc->y);
}

for (int i = 0; i< fanout.size(); ++i){
location_t* fanout_loc = fanout[i]->present_loc.Get();
no_swap += fabs(old_loc->x - fanout_loc->x);
no_swap += fabs(old_loc->y - fanout_loc->y);

yes_swap += fabs(new_loc->x - fanout_loc->x);
yes_swap += fabs(new_loc->y - fanout_loc->y);
}

return no_swap - yes_swap;
}
----

>From the code, we see that no_swap is the sum of the Manhattan distances
between the *old *(current) location and each of the element's fan-in and
fan-out elements, while yes_swap is the sum of the Manhattan distances
between the *new *(proposed) location and those elements.

Intuitively, a high sum value is worse than a low sum value, because it
implies a greater distance and therefore a higher cost.  This implies that
if no_swap > yes_swap, the swap is favorable, and not favorable otherwise.
This in turn implies that a positive return value indicates the swap should
be accepted, and that a negative value indicates the swap should be rejected
(probabilistically).

However, the algorithm does not behave this way, it appears.  In fact, it
seems to do the *opposite*.  Eventually we get to the following code, where
the return value is represented by delta_cost:

----
delta_cost, double T, Rng* rng)
{
//always accept moves that lower the cost function
if (delta_cost < 0){
return move_decision_accepted_good;
} else {
double random_value = rng->drand();
double boltzman = exp(- delta_cost/T);
if (boltzman > random_value){
} else {
return move_decision_rejected;
}
}
}
----

Note that the move/swap is accepted if the delta_cost value is *negative*.
Can someone please explain this to me?