Placement algorithms

rig.place_and_route.place.sa.place(vertices_resources, nets, machine, constraints, effort=1.0, random=<module 'random' from '/usr/lib/python2.7/random.pyc'>, on_temperature_change=None, kernel=<class 'rig.place_and_route.place.sa.python_kernel.PythonKernel'>, kernel_kwargs={})

A flat Simulated Annealing based placement algorithm.

This placement algorithm uses simulated annealing directly on the supplied problem graph with the objective of reducing wire lengths (and thus, indirectly, the potential for congestion). Though computationally expensive, this placer produces relatively good placement solutions.

The annealing temperature schedule used by this algorithm is taken from “VPR: A New Packing, Placement and Routing Tool for FPGA Research” by Vaughn Betz and Jonathan Rose from the “1997 International Workshop on Field Programmable Logic and Applications”.

Two implementations of the algorithm’s kernel are available:

• PythonKernel A pure Python implementation which is available on all platforms supported by Rig.
• CKernel A C implementation which is typically 50-150x faster than the basic Python kernel. Since this implementation requires a C compiler during installation, it is an optional feature of Rig. See the CKernel's documentation for details.

The fastest kernel installed is used by default and can be manually chosen using the kernel argument.

This algorithm produces INFO level logging information describing the progress made by the algorithm.

Parameters:

effort : float

A scaling factor for the number of iterations the algorithm should run for. 1.0 is probably about as low as you’ll want to go in practice and runtime increases linearly as you increase this parameter.

random : random.Random

A Python random number generator. Defaults to import random but can be set to your own instance of random.Random to allow you to control the seed and produce deterministic results. For results to be deterministic, vertices_resources must be supplied as an collections.OrderedDict.

on_temperature_change : callback_function or None

An (optional) callback function which is called every time the temperature is changed. This callback can be used to provide status updates

The callback function is passed the following arguments:

• iteration_count: the number of iterations the placer has attempted (integer)
• placements: The current placement solution.
• cost: the weighted sum over all nets of bounding-box size. (float)
• acceptance_rate: the proportion of iterations which have resulted in an accepted change since the last callback call. (float between 0.0 and 1.0)
• temperature: The current annealing temperature. (float)
• distance_limit: The maximum distance any swap may be made over. (integer)

If the callback returns False, the anneal is terminated immediately and the current solution is returned.

kernel : Kernel

A simulated annealing placement kernel. A sensible default will be chosen based on the available kernels on this machine. The kernel may not be used if the placement problem has a trivial solution.

kernel_kwargs : dict

Optional kernel-specific keyword arguments to pass to the kernel constructor.

rig.place_and_route.place.rcm.place(vertices_resources, nets, machine, constraints)

Assigns vertices to chips in Reverse-Cuthill-McKee (RCM) order.

The RCM algorithm (in graph-centric terms) is a simple breadth-first-search-like heuristic which attempts to yield an ordering of vertices which would yield a 1D placement with low network congestion. Placement is performed by sequentially assigning vertices in RCM order to chips, also iterated over in RCM order.

This simple placement scheme is described by Torsten Hoefler and Marc Snir in their paper entitled ‘Generic topology mapping strategies for large-scale parallel architectures’ published in the Proceedings of the international conference on Supercomputing, 2011.

This is a thin wrapper around the sequential placement algorithm which uses an RCM ordering for iterating over chips and vertices.

Parameters:

breadth_first : bool

Should vertices be placed in breadth first order rather than the iteration order of vertices_resources. True by default.

rig.place_and_route.place.hilbert.place(vertices_resources, nets, machine, constraints, breadth_first=True)

Places vertices in breadth-first order along a hilbert-curve path through the chips in the machine.

This is a thin wrapper around the sequential placement algorithm which optionally uses the breadth_first_vertex_order() vertex ordering (if the breadth_first argument is True, the default) and hilbert_chip_order() for chip ordering.

Parameters:

breadth_first : bool

Should vertices be placed in breadth first order rather than the iteration order of vertices_resources. True by default.

rig.place_and_route.place.breadth_first.place(vertices_resources, nets, machine, constraints, chip_order=None)

Places vertices in breadth-first order onto chips in the machine.

This is a thin wrapper around the sequential placement algorithm which uses the breadth_first_vertex_order() vertex ordering.

Parameters:

chip_order : None or iterable

The order in which chips should be tried as a candidate location for a vertex. See the sequential placer’s argument of the same name.

rig.place_and_route.place.sequential.place(vertices_resources, nets, machine, constraints, vertex_order=None, chip_order=None)

Blindly places vertices in sequential order onto chips in the machine.

This algorithm sequentially places vertices onto chips in the order specified (or in an undefined order if not specified). This algorithm is essentially the simplest possible valid placement algorithm and is intended to form the basis of other simple sequential and greedy placers.

The algorithm proceeds by attempting to place each vertex on the a chip. If the vertex fits we move onto the next vertex (but keep filling the same vertex). If the vertex does not fit we move onto the next candidate chip until we find somewhere the vertex fits. The algorithm will raise an rig.place_and_route.exceptions.InsufficientResourceError if it has failed to fit a vertex on every chip.

Parameters:

vertex_order : None or iterable

The order in which the vertices should be attemted to be placed.

If None (the default), the vertices will be placed in the default iteration order of the vertices_resources argument. If an iterable, the iteration sequence should produce each vertex in vertices_resources exactly once.

chip_order : None or iterable

The order in which chips should be tried as a candidate location for a vertex.

If None (the default), the chips will be used in the default iteration order of the machine object (a raster scan). If an iterable, the iteration sequence should produce (x, y) pairs giving the coordinates of chips to use. All working chip coordinates must be included in the iteration sequence exactly once. Additional chip coordinates of non-existant or dead chips are also allowed (and will simply be skipped).

rig.place_and_route.place.rand.place(vertices_resources, nets, machine, constraints, random=<module 'random' from '/usr/lib/python2.7/random.pyc'>)

A random placer.

This algorithm performs uniform-random placement of vertices (completely ignoring connectivty) and thus in the general case is likely to produce very poor quality placements. It exists primarily as a baseline comparison for placement quality and is probably of little value to most users.

Parameters:

random : random.Random

Defaults to import random but can be set to your own instance of random.Random to allow you to control the seed and produce deterministic results. For results to be deterministic, vertices_resources must be supplied as an collections.OrderedDict.