anneal.hpp File Reference

(E) Detailed placement by simulated annealing (design doc 04 §3 E; Kirkpatrick, Gelatt, Vecchi, Science 1983; move set after TimberWolf, Sechen & Sangiovanni-Vincentelli, IEEE JSSC 1985). More...

#include <chrono>
#include <cstdint>
#include <vector>
#include "place/congestion.hpp"
#include "place/legality.hpp"

Go to the source code of this file.

Classes
struct	tmk::place::AnnealOptions
struct	tmk::place::AnnealResult
struct	tmk::place::LnsResult
	Large-neighbourhood search from start (legal): windows LNS windows (sizes and seeds from o; the stream is o.seed). More...
struct	tmk::place::WindowResult
	Exact window (doc 04 §3 F, without CP-SAT): the best placement of parts (others fixed) over a candidate set per part (its own spot, the other window parts' spots, its HPWL-optimal spot; four rotations each), by branch and bound with an HPWL bound. More...

Namespaces
namespace	tmk
namespace	tmk::place

Functions
double	tmk::place::trace_now ()
	Recording clock (video timelapse): steady-clock seconds. Only ever written to recordings.
AnnealResult	tmk::place::anneal (const Problem &p, const Placement &start, const AnnealOptions &o)
	start must be legal for every movable part.
std::int64_t	tmk::place::anneal_cost (const Problem &p, const Placement &pl, double alpha_cross_mm, double beta=0, const CongestionMap *m=nullptr, double via_mm=0)
	Cost used by the annealer, from scratch (reference path): weighted HPWL + α·crossings + β·RUDY overflow, all in the annealer's integer units.
LnsResult	tmk::place::lns_improve (const Problem &p, const Placement &start, const AnnealOptions &o, int windows)
WindowResult	tmk::place::solve_window (const Problem &p, Placement &pl, const std::vector< int > &parts, const AnnealOptions &o, bool prune=true, long max_leaves=200 '000)

Detailed Description

(E) Detailed placement by simulated annealing (design doc 04 §3 E; Kirkpatrick, Gelatt, Vecchi, Science 1983; move set after TimberWolf, Sechen & Sangiovanni-Vincentelli, IEEE JSSC 1985).

Moves: shift (radius shrinks with temperature), pull towards the weighted median of the connected pins, rotate by 90/180/270°, swap two interchangeable parts (same footprint, side and orientation class). Every move is checked exactly before it is applied, so the state is always legal. Cost (integer, incremental): weighted HPWL + α · (crossings between minimum-spanning-tree airwires of different signal nets), the crossings counted against a uniform segment grid. Independent runs with different seeds go in parallel and the best is kept (ties: lowest run index); run budgets are counted in moves, so results do not depend on thread timing unless the wall-time limit stops a run.

M8 additions (doc 04 §3 E, G):

• Parallel tempering (replica exchange; Swendsen & Wang, PRL 57, 1986; Hukushima & Nemoto, J. Phys. Soc. Jpn. 65, 1996): runs replicas at geometric temperatures run fixed-length sweeps in parallel; between sweeps, neighbouring temperatures exchange replicas with the Metropolis criterion, decided sequentially from a dedicated random stream, so the result does not depend on the thread count.
• Large-neighbourhood search (Shaw, "Using constraint programming and local search methods to solve vehicle routing problems", CP 1998): rip up a window of nearby parts and re-place them, exactly (branch and bound over candidate slots and rotations) for small windows, greedily otherwise; kept only if the cost falls.
• A routability term β · RUDY overflow (place/congestion.hpp).

Side assignment (doc 04 §3 C/E, D48; opt-in): a flip move puts a part on the other side (KiCad's mirrored footprint, problem.hpp kStates) at its body centre or at the weighted median of its nets, and the cost gains a via estimate for nets with surface-mount pins on both sides.

Definition in file anneal.hpp.