global_router.hpp File Reference

Global routing on a coarse 3-D tile graph (design doc 05 §4 and §19, roadmap M6; CPU, the only path: §19 shows why there is no GPU version). More...

#include <array>
#include <cstdint>
#include <vector>
#include "core/units.hpp"
#include "geom/point.hpp"
#include "model/board.hpp"

Go to the source code of this file.

Classes
struct	tmk::route::GlobalNet
struct	tmk::route::GlobalOptions
struct	tmk::route::CutLine
	A straight line across the whole board and what has to cross it (escalation rung R6, doc 05 §20; the cut argument of Maley, "Single-Layer Wire Routing and Compaction", 1990, at the resolution of the capacity samples). More...
struct	tmk::route::GlobalResult

Namespaces
namespace	tmk
namespace	tmk::route

Functions
GlobalResult	tmk::route::global_route (const Obstacles &obs, const geom::Box &bounds, int layers, const std::vector< GlobalNet > &nets, const GlobalOptions &opt)

Detailed Description

Global routing on a coarse 3-D tile graph (design doc 05 §4 and §19, roadmap M6; CPU, the only path: §19 shows why there is no GPU version).

The board is cut into square tiles about eight track pitches wide. Each tile edge on each copper layer gets a capacity: how many tracks fit across the narrowest cut between the two tile centres, measured with the exact obstacle model; each tile gets a via capacity (free via sites). Every two-pin connection is routed on the tile graph with A* (length + via cost + congestion), then negotiated congestion (PathFinder: McMurchie and Ebeling, FPGA 1995) rips up connections on overflowed edges or via tiles and re-routes them with growing history costs. Connections of one net share edges: an edge carries a net once however many of its connections use it, and a connection pays no congestion on an edge its net already holds, so a net's connections merge into a tree with shared trunks (the demand side of a Steiner topology). All costs are integers. The result is a corridor per connection: the tiles of its path on the layers it uses, widened by one tile, which the detailed router uses as soft guidance.

Definition in file global_router.hpp.