Simulated Annealing

Simulated Annealing

Mapper2.SA.place! — Function.
place!(map::Map; kwargs...) :: SAState

Run simulated annealing placement directly on map.

Records the following metrics into map.metadata:

  • placement_struct_time - Amount of time it took to build the SAStruct from map.

  • placement_struct_bytes - Number of bytes allocated during the construction of the SAStruct

  • placement_time - Running time of placement.

  • placement_bytes - Number of bytes allocated during placement.

  • placement_objective - Final objective value of placement.

Keyword Arguments

  • seed - Seed to provide the random number generator. Specify this to a constant value for consistent results from run to run.

    Default: rand(UInt64)

  • move_attempts :: Integer - Number of successful moves to generate between state updates. State updates include adjusting temperature, move distance limit, state displaying etc.

    Higher numbers will generally yield higher quality placement but with a longer running time.

    Default: 20000

  • initial_temperature :: Float64 - Initial temperature that the system begins its warming process at. Due to the warming procedure, this should not have much of an affect on placement.

    Default: 1.0.

  • supplied_state :: Union{SAState,Nothing} - State type to use for this placement. Can be used to resume placement where it left off from a previous run. If nothing, a new SAState object will be initialized.

    Default: nothing

  • movegen :: MoveGenerator - The MoveGenerator to use for this placement.

    Default: CachedMoveGenerator

  • warmer - The SAWarm warming schedule to use.

    Default: DefaultSAWarm

  • cooler - The SACool cooling schedule to use.

    Default: DefaultSACool

  • limiter - The SALimit move distance limiting algorithm to use.

    Default: DefaultSALimit

  • doner - The SADone exit condition to use.

    Default: DefaultSADone

source

SAState

Mapper2.SA.SAState — Type.
mutable struct SAState

Fields

  • temperature

    Current Temperature of the system.

  • objective

    Current objective value.

  • distance_limit

    Current distance limit.

  • distance_limit_int

    Current distance limit as an integer.

  • max_distance_limit

    Maximum distance limit for this architecture.

  • recent_move_attempts

  • recent_successful_moves

  • recent_accepted_moves

  • recent_deviation

  • warming

    Current warming state

  • total_moves

    Total number of move attempts made

  • successful_moves

    Number of successful move generations

  • accepted_moves

    Number of moves accepted

  • moves_per_second

    Moves per second

  • deviation

    Average Deviaation

  • start_time

    Creation time of the structure

  • run_time

    Running Time - only an approximate measure

  • display_updates

  • last_update_time

    Time of the last update

  • dt

    Update Interval

  • aux_cost

    Auxiliary cost

Documentation

State tracking struct for Simulated Annealing placement.

Method List

SAState(temperature, distance_limit, objective)

defined at /home/travis/build/hildebrandmw/Mapper2.jl/src/Place/SA/State.jl:57.

source

Warming

Warming involve increasing the temperature of the simulated annealing system until certain criteria are reached, at which the true simulated annealing algorithm takes place. It is important to begin a placement at a high temperature because this early phase is responsible for creating a high level idea for what the final placement will look like.

The default implementation described below heats up the the system until a certain high fraction of generated moves are accepted, allowing the initial temperature to depend on the specific characteristics of the architecture and taskgraph being placed.

Mapper2.SA.SAWarm — Type.
abstract type SAWarm

Fields

Documentation

Abstract type controlling the warming cycle of Simulated Annealing placement.

API

Implementations

Method List

source
Mapper2.SA.warm! — Function.
warm!(warmer :: SAWarm, state :: SAState)

Increase state.temperature according to warmer. If warmer decides that the system is done warming up, it must set state.warming = false.

Method List

warm!(w, state)

defined at /home/travis/build/hildebrandmw/Mapper2.jl/src/Place/SA/Algorithm.jl:79.

source
Mapper2.SA.DefaultSAWarm — Type.
mutable struct DefaultSAWarm <: Mapper2.SA.SAWarm

Fields

  • ratio

  • multiplier

  • decay

Documentation

Default imeplementation of SAWarm.

On each invocation, will multiply the temperature of the anneal by multiplier. When the acceptance ratio rises above ratio, warming routine will end.

To prevent unbounded warming, the ratio field is multiplied by the decay field on each invocation.

Method List

DefaultSAWarm(ratio, multiplier, decay)
DefaultSAWarm(ratio, multiplier, decay)

defined at /home/travis/build/hildebrandmw/Mapper2.jl/src/Place/SA/Algorithm.jl:72.

source

Cooling

Over the course of simulated annealing placement, the temperature of the system is slowly lowered, increasing the probability that an objective-increasing move will be rejected. The simplest is multiplying the temperature by a common factor $\alpha < 1$ so

\[T_{new} = \alpha T_{old}.\]

Rasing the value of $\alpha$ results in higher quality results at the cost of a longer run time.

Mapper2.SA.SACool — Type.
abstract type SACool

Fields

Documentation

Cooling schedule for Simulated Annealing placement.

API

Implementations

Method List

source
Mapper2.SA.cool! — Function.
cool!(cooler :: SACool, state :: SAState)

When called, may decrease state.temperature.

Method List

cool!(c, state)

defined at /home/travis/build/hildebrandmw/Mapper2.jl/src/Place/SA/Algorithm.jl:140.

source
Mapper2.SA.DefaultSACool — Type.
struct DefaultSACool <: Mapper2.SA.SACool

Fields

  • alpha

Documentation

Default cooling schedule. Each invocation, will multiply the temperature of the anneal by the alpha parameter.

Method List

DefaultSACool(alpha)
DefaultSACool(alpha)

defined at /home/travis/build/hildebrandmw/Mapper2.jl/src/Place/SA/Algorithm.jl:137.

source

Move Distance Limiting

TODO

Mapper2.SA.SALimit — Type.
abstract type SALimit

Fields

Documentation

Type that controls the length contraction mechanism of Simulated Annealing placement.

API

Implmementations

Method List

source
Mapper2.SA.limit! — Function.
limit!(limiter :: SALimit, state :: SAState)

Mutate state.distance_limit when called.

source
Mapper2.SA.DefaultSALimit — Type.
struct DefaultSALimit <: Mapper2.SA.SALimit

Fields

  • ratio

  • minimum

Documentation

Default distance limit updater. Will adjust the distance limit so approximate ratio of moves are accepted. Will not set state.limit lower than minimum.

Method List

DefaultSALimit(ratio, minimum)
DefaultSALimit(ratio, minimum)

defined at /home/travis/build/hildebrandmw/Mapper2.jl/src/Place/SA/Algorithm.jl:180.

DefaultSALimit(ratio)

defined at /home/travis/build/hildebrandmw/Mapper2.jl/src/Place/SA/Algorithm.jl:184.

source

Terminating Placement

TODO

Mapper2.SA.SADone — Type.
abstract type SADone

Fields

Documentation

Control when to terminate Simulated Annealing placement.

API

Implementations

  • [DefaultSADone]

Method List

source
Mapper2.SA.sa_done — Function.
sa_done(doner :: SADone, state :: SAState)

Return true to finish placement.

source
Mapper2.SA.DefaultSADone — Type.
struct DefaultSADone <: Mapper2.SA.SADone

Fields

  • atol

Documentation

Default end detection. Will return true when objective deviation is less than atol.

Method List

DefaultSADone(atol)
DefaultSADone(atol)

defined at /home/travis/build/hildebrandmw/Mapper2.jl/src/Place/SA/Algorithm.jl:238.

source