Escape planning, version 2 (roadmap M9; design doc 05 §3 and §14): min-cost-flow channel assignment for deep ball-grid arrays, layer by layer. More...

#include <functional>
#include <vector>
#include "route/escape.hpp"

Classes
struct	tmk::route::FlowEscapeInput
struct	tmk::route::RingPlan
	Per ring (1 = perimeter) of the planned arrays: how the pins that need routing were assigned. More...
struct	tmk::route::FlowEscapeStats

Namespaces
namespace	tmk
namespace	tmk::route

Functions
std::vector< int >	tmk::route::array_rings (const model::Board &b, const std::vector< char > &needs, const EscapeOptions &o={})
	Deep arrays: SMD pads of one footprint on a regular square grid (every pad within pitch / 8 of a grid point, at most one pad per point, at least 30 % of the points populated, at least 5 x 5) with at least one pin that needs routing in the third ring or deeper.
std::vector< EscapeCorridor >	tmk::route::plan_escapes_flow (const model::Board &b, const std::vector< char > &needs, const FlowEscapeInput &in, const EscapeOptions &o={}, FlowEscapeStats *stats=nullptr)
	Plans the deep arrays by min-cost flow and every other dense package as version 1 does (plan_escapes).

Detailed Description

Escape planning, version 2 (roadmap M9; design doc 05 §3 and §14): min-cost-flow channel assignment for deep ball-grid arrays, layer by layer.

Version 1 (escape.hpp) sends perimeter pins straight out and every inner ball to a fixed dog-bone via site. In an array deeper than two rings that leaves the channels between balls unassigned: which inner ball uses which gap, on which layer, is decided by whichever net's search runs first. Here each deep array gets the network-flow escape model with diagonal capacities (Yan & Wong, "A correct network flow model for escape routing", DAC 2009): the square gaps between four balls are graph nodes, the gap between two neighbouring balls is an edge whose capacity is the number of tracks that fit there, and every gap node carries a capacity from its diagonals, which every track turning in or crossing the gap must pass (we take the narrower diagonal for both, which is conservative). A min-cost max flow from the balls to the outside of the array gives each escaping ball a channel sequence. Layers are assigned one after another, as in the layer-by-layer escape of Ozdal & Wong ("Algorithms for simultaneous escape routing and layer assignment of dense PCBs", TCAD 2006) and Lin et al. (DAC 2021): the pad layer first; the balls that cannot leave on it get a dog-bone via site (an assignment, also by min-cost flow, to interstitial sites no pad-layer escape crosses); then each further layer routes the remaining vias out between the via sites, which are that layer's obstacles.

The result is a set of corridors the router reserves exactly as version 1's: reservations only remove options from other nets, every commit is still checked exactly, so the plan cannot create violations. Integer costs, pads and layers in board order and fixed arc order make it deterministic.

Definition in file escape_flow.hpp.

Classes

Namespaces

Functions

Detailed Description