Simulated Annealing Based Placement

An experimental simulated-annealing based placer.

The annealing algorithm is broken into two components: the high-level algorithm implementation place() and a simulated annealing placement Kernel.

The algorithm takes care of initial placement, handles special-case “trivial” placement problems where no placer effort is requried, handles details of constraints, and manages the annealing scheudle.

The kernel is responsible for performing the kernel of the annealing operation: swapping vertices, evaluating the change in cost and reverting (some) bad swaps. Since this is the most performance-sensitive part of the algorithm, its implementation may be swapped for more efficient implementations as required. A portable, but slow, kernel written in Python is included in PythonKernel.

Kernel Prototype

All kernel implementations should obey the following interface:

class rig.place_and_route.place.sa.kernel.Kernel(vertices_resources, movable_vertices, fixed_vertices, initial_placements, nets, machine, random, **kwargs)

A general API for a SA algorithm kernel.

__init__(vertices_resources, movable_vertices, fixed_vertices, initial_placements, nets, machine, random, **kwargs)

Initialise the algorithm kernel with a placement problem.

Placement problems are described simillarly to the normal Rig fashion with the main exception that no constraints may be given.

A kernel need not be able to handle the following special-case placement problems:

• Where no resource types exist
• For 1x1 machines (or smaller…)
• With no vertices are movable
• Only nets with zero weights
• Only nets with < 2 uniqe vertices

Parameters:

vertices_resources : {vertex: {resource: value, …}, …}

The resources consumed by all vertices.

movable_vertices : {vertex, …}

Identifies all movable vertices.

fixed_vertices : {vertex, …}

Identifies all non-movable vertices.

initial_placements : {vertex: (x, y), …}

Gives the initial location of all vertices.

nets : [Net, …]

The nets which connect all movable and fixed vertices.

machine : Machine

This machine must have the resources consumed by the initial placement subtracted from each chip. This object may be modified at will.

random : random.Random

The random number generator to use.

run_steps(num_steps, distance_limit, temperature)

Attempt num_steps swaps.

Parameters:

num_steps : int

The number of swap attempts to be made.

distance_limit : int

The maximum distance over which a swap may be made (as the “radius” of a square).

temperature : float

The current annealing temperature.

Returns:

num_accepted : int

The number accepted swaps.

cost : float

The global cost of the placement after all swaps have been completed.

cost_delta_sd : float

The standard deviation of the cost changes resulting from each swap.

get_placements()

Get the current placement solution.

Returns:

{vertex: (x, y), …}

__weakref__

list of weak references to the object (if defined)

Available Kernels

class rig.place_and_route.place.sa.python_kernel.PythonKernel(vertices_resources, movable_vertices, fixed_vertices, initial_placements, nets, machine, random, no_warn=False)

An implementation of the Simulated Annealing placement algorithm kernel written in Python.

This implementation is not optimised for runtime but should produce good quality, correct results on any platform, albeit slowly.

This kernel will display a warning/hint if placement is taking a long time suggesting installing rig_c_sa to enable use of the faster CKernel. To disable this warning, the kernel takes an optional no_warn argument which, when True, disables the warning.