[parsec-users] Question about canneal

Christian Bienia cbienia at CS.Princeton.EDU
Wed Nov 19 12:42:48 EST 2008


Marc,

 

This is a bug in a program. Simply return yes_swap - no_swap. Thanks for
telling us about it.

 

The bug shouldn't change the characteristics of the program.

 

- Chris

 

 

From: parsec-users-bounces at lists.cs.princeton.edu
[mailto:parsec-users-bounces at lists.cs.princeton.edu] On Behalf Of Marc de
Kruijf
Sent: Wednesday, November 19, 2008 10:23 AM
To: parsec-users at lists.cs.princeton.edu
Subject: [parsec-users] Question about canneal

 

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/615d32fd/attachment.htm>


More information about the parsec-users mailing list