congestion.hpp File Reference

Routability estimate for placement (design doc 04 §3 B R(x), E β·RUDY overflow, G). More...

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

Go to the source code of this file.

Classes
struct	tmk::place::CongestionOptions
struct	tmk::place::CongestionMap

Namespaces
namespace	tmk
namespace	tmk::place
namespace	tmk::place::detail

Functions
CongestionMap	tmk::place::make_congestion_map (const Problem &p, const CongestionOptions &o={})
bool	tmk::place::rudy_net (const Problem &p, int net)
	True if the net contributes RUDY demand (signal nets with at least two pins).
Box	tmk::place::net_box (const Problem &p, const Placement &pl, int net)
	Pin bounding box of one net.
template<class Touch>
void	tmk::place::add_box_demand (const CongestionMap &m, const Box &b, int sign, std::vector< std::int64_t > &demand, Touch &&touch)
	Adds sign × the RUDY demand of a net with pin bounding box b to demand.
std::vector< std::int64_t >	tmk::place::rudy_demand (const Problem &p, const Placement &pl, const CongestionMap &m)
	From-scratch demand of a placement (reference path for the annealer's incremental bookkeeping).
std::int64_t	tmk::place::bin_overflow (std::int64_t demand, std::int64_t cap)
std::int64_t	tmk::place::total_overflow (const CongestionMap &m, const std::vector< std::int64_t > &demand)
std::int64_t	tmk::place::rudy_overflow (const Problem &p, const Placement &pl, const CongestionMap &m)
void	tmk::place::scale_bins (CongestionMap &m, const std::vector< Point > &pts, Coord radius, double factor)
	Multiplies the capacity of the bins within radius of each point by factor (once per bin per call).
Box	tmk::place::detail::rudy_box (const CongestionMap &m, const Box &b)
	RUDY box: the pin box widened to at least one bin per axis, so aligned pins do not give infinite density.

Detailed Description

Routability estimate for placement (design doc 04 §3 B R(x), E β·RUDY overflow, G).

RUDY (Rectangular Uniform wire DensitY; Spindler & Johannes, "Fast and accurate routing demand estimation for efficient routability-driven placement", DATE 2007): each signal net's half-perimeter wirelength is spread uniformly over its pin bounding box, so the demand of a bin is Σ_nets HPWL · area(box ∩ bin) / area(box). Every pin also consumes a fixed amount of track length in its bin (pin density). Capacity per bin is the track length the copper layers offer there (layers × bin² / pitch × usable fraction × fraction inside the outline). The cost is the total overflow Σ max(0, demand − capacity), all in integer nm so incremental and from-scratch evaluation agree exactly (CLAUDE.md rules 2 and 3).

Power nets (PNet::signal false) are left out (they are expected on pours or planes; the same reason they get a low HPWL weight). The router-in-the-loop (G) lowers the capacity of bins where the router failed (scale_bins), which is the PCB analogue of RePlAce's cell inflation in overflowed tiles.

Definition in file congestion.hpp.