global.hpp File Reference

Global placement (design doc 04 §3 A–C). More...

#include <array>
#include <cstdint>
#include <string>
#include <vector>
#include "place/legality.hpp"

Go to the source code of this file.

Classes
struct	tmk::place::SpreadStats

Namespaces
namespace	tmk
namespace	tmk::place

Functions
void	tmk::place::quadratic_place (const Problem &p, Placement &pl, int relinearise, const std::vector< Point > *anchor=nullptr, const std::vector< double > *anchor_w=nullptr)
	(A) Solves the B2B quadratic program for the movable parts (rotations taken from pl), relinearise times.
SpreadStats	tmk::place::spread (const Problem &p, Placement &pl, int max_iterations=40, double target_overflow=0.10, std::vector< Placement > *trace=nullptr)
	(B) SimPL loop starting from a quadratic placement pl; on return pl holds the spread (upper-bound) placement.
double	tmk::place::density_overflow (const Problem &p, const Placement &pl)
	Bin density overflow of a placement: Σ max(0, demand − capacity) / Σ demand over a bin grid per side.
std::array< double, 2 >	tmk::place::utilisation (const Problem &p)
	Movable courtyard area (incl. clearance) / free board area, per side.
int	tmk::place::optimise_rotations (const Problem &p, Placement &pl, int max_passes=20)
	(C) Rotation coordinate descent over the movable parts (HPWL of each part's nets).
std::vector< std::vector< int > >	tmk::place::part_nets (const Problem &p)
	Nets touching each part (sorted, unique).

Detailed Description

Global placement (design doc 04 §3 A–C).

(A) Quadratic placement with the bound-to-bound (B2B) net model: Spindler, Schlichtmann, Johannes, "Kraftwerk2 — A Fast Force-Directed Quadratic Placement Approach Using an Accurate Net Model", IEEE TCAD 27(8), 2008. Each net connects every pin to the net's two extreme pins with weight w·2/((p−1)·|x_i − x_j|), which reproduces HPWL at the linearisation point; the SPD systems are solved with Jacobi-preconditioned conjugate gradient (Eigen) and re-linearised. (B) Spreading: SimPL (Kim, Lee, Markov, "SimPL: An Effective Placement Algorithm", ICCAD 2010 / TCAD 2012): alternate the quadratic solve (lower-bound placement) with a rough legalisation (upper-bound placement) and pull the parts towards it with anchor pseudo-nets of growing weight. (C) Rotation: coordinate descent; each step is the exact HPWL optimum for one part with the others fixed.

Definition in file global.hpp.