Distributed Simulated Annealing: Difference between revisions
From SCECpedia
Jump to navigationJump to search
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
== 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 == | == Performance Graphs == | ||
{| border="1" | {| border="1" | ||
Revision as of 22:23, 6 September 2011
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 | 
|
|
|
|
