Distributed Simulated Annealing

Serial SA Algorithm

• s = s0; e = E(s)
• sbest = s; ebest = e
• k = 0
• while k < max_iterations:
  • snew = neighbour(s)
  • enew = E(snew)
  • if P(e, enew, temperature) > random(); then
    • s = snew; e = enew
  • if enew < ebest
    • sbest = snew; ebest = enew
  • k++'

Parallel SA Algorithm

• s = s0; e = E(s)
• sbest = s; ebest = e
• k = 0
• while k < max_iterations
  • on n processors, do nSubIterations iterations of serial SA
  • find processor with best overall (lowest energy) solution, sbest
  • redistribute sbest, ebest to all processors
  • k += nSubIterations

Performance Graphs

Dataset	ncal_constrained	ncal_unconstrained	state_constrained	state_unconstrained
Energy vs Time
Avg Energy vs Time
Serial Time vs Parallel Time
Time Speedup vs Time
Std. Dev. vs Time
Improvement vs Energy