[parsec-users] Question about canneal

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:

----
annealer_thread::move_decision_t annealer_thread::accept_move(routing_cost_t
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){
                         return move_decision_accepted_bad;
                 } 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?

Thanks in advance,
Marc
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/parsec-users/attachments/20081119/cf06b3e5/attachment.htm>


More information about the parsec-users mailing list