ASIC place & route framework. This crate contains interface definitions of the core parts of the place & route flow.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

402 lines
17 KiB

* Copyright (c) 2020-2021 Thomas Kramer.
* This file is part of LibrEDA
* (see
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU Affero General Public License as
* published by the Free Software Foundation, either version 3 of the
* License, or (at your option) any later version.
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* GNU Affero General Public License for more details.
* You should have received a copy of the GNU Affero General Public License
* along with this program. If not, see <>.
//! Trait for a simplified router.
use crate::db as db;
use db::L2NEdit;
use db::{SInt, Geometry, SimpleRPolygon, Rect, Point};
use std::collections::{HashMap, HashSet};
use db::{Translate, ToPolygon};
/// Represents a routed net.
pub struct SimpleRoutedNet {
/// Geometries of the metal wires as a list of `(layer, geometry)` tuples.
pub routes: Vec<(u8, Geometry<SInt>)>,
/// Locations of vias as `(layer1, layer2, location)` tuples.
pub vias: Vec<(u8, u8, Point<SInt>)>,
/// Basic trait for a router with a simplified interface.
/// The simplified router gets as an input an already flattened set of
/// net terminal shapes that need to be connected.
pub trait SimpleRouter {
/// Get the name of the routing engine.
fn name(&self) -> &str;
/// Routing algorithm implementation.
fn compute_routes_impl(&self,
boundary: Rect<SInt>,
net_terminals: &HashMap<usize, Vec<Vec<(SimpleRPolygon<SInt>, u8)>>>,
obstacles: &Vec<(SimpleRPolygon<SInt>, u8)>,
) -> HashMap<usize, SimpleRoutedNet>;
/// Wrapper around `compute_route_impl()`.
/// Does some sanity checks before and after.
/// * `boundary`: Boundary of the area that can be used for the routing.
/// * `net_terminals`: Pin shapes for each net together with the layer number. Lowest layer is `0`.
/// * `obstacles`: Obstacle shapes together with the layer number.
/// Returns all freshly drawn routes.
fn compute_routes(&self,
boundary: Rect<SInt>,
net_terminals: &HashMap<usize, Vec<Vec<(SimpleRPolygon<SInt>, u8)>>>,
obstacles: &Vec<(SimpleRPolygon<SInt>, u8)>,
) -> HashMap<usize, SimpleRoutedNet> {
self.compute_routes_impl(boundary, net_terminals, obstacles)
/// Draw the computed routes into the layout.
/// * `routes`: Routes computed with `compute_routes()`.
/// * `routes_cell`: The cell where to draw the routes into.
/// * `routing_layers`: The metal layer stack starting with the layer ID of the lowest metal layer.
/// * `via_layers`: IDs of the via layers, starting with the lowest via layer which is the
/// via layer between the first two metal layers.
fn draw_routes<LN: L2NEdit<Coord=db::SInt>>(
chip: &mut LN,
routes: HashMap<usize, SimpleRoutedNet>,
routes_cell: LN::CellId,
routing_layers: &Vec<LN::LayerId>,
via_layers: &Vec<LN::LayerId>) {
for (_net, routed_net) in routes {
// Draw routing paths.
// Draw wires.
for (layer, shape) in routed_net.routes {
&routing_layers[layer as usize],
// Draw vias.
let via_shape0 = db::Rect::new((-20, -20), (20, 20));
for (layer1, layer2, location) in routed_net.vias {
assert_eq!(layer1 + 1, layer2, "Invalid via between two non-neighbour layers.");
let via_shape = via_shape0.translate(location.into());
&via_layers[layer1 as usize],
/// Route all nets in the `top_cell`.
/// * `top_cell`: The cell containing the layout to be routed.
/// * `routing_layers`: The metal layer stack starting with the layer ID of the lowest metal layer.
/// * `via_layers`: IDs of the via layers, starting with the lowest via layer which is the
/// via layer between the first two metal layers.
/// # Returns
/// * On success returns `Ok(())`.
/// * On failure, when some nets could not be routed returns a list of the unrouted nets `Err(unrouted nets)`.
fn route_all_nets<LN: L2NEdit<Coord=db::SInt>>(
chip: &mut LN,
top_cell: LN::CellId,
routing_layers: &Vec<LN::LayerId>,
via_layers: &Vec<LN::LayerId>,
) -> Result<(), Vec<LN::NetId>> {
let nets = chip.each_internal_net_vec(&top_cell);
self.route_nets(chip, top_cell, routing_layers, via_layers, &nets)
/// Route a set of nets and creates a new cell that contains the shapes of the routes.
/// Also outputs the routing terminal shapes to this cell (for debugging).
/// * `top_cell`: The cell containing the layout to be routed.
/// * `routing_layers`: The metal layer stack starting with the layer ID of the lowest metal layer.
/// * `via_layers`: IDs of the via layers, starting with the lowest via layer which is the
/// via layer between the first two metal layers.
/// * `nets`: The nets to be routed.
/// # Returns
/// * On success returns `Ok(())`.
/// * On failure, when some nets could not be routed returns a list of the unrouted nets `Err(unrouted nets)`.
fn route_nets<LN: L2NEdit<Coord=db::SInt>>(
chip: &mut LN,
top_cell: LN::CellId,
routing_layers: &Vec<LN::LayerId>, // TODO: Store technology information in the router implementation.
via_layers: &Vec<LN::LayerId>, // TODO: Store technology information in the router implementation.
nets: &Vec<LN::NetId>,
) -> Result<(), Vec<LN::NetId>> {
log::info!("Start router '{}'.",;
assert_eq!(routing_layers.len(), via_layers.len() + 1,
"There must be exactly one more routing layer than via layers.");
// ** PREPARE for ROUTING **
// Draw layout of routing terminals, i.e. pin shapes of cells and macros.
// Create flat structure of routing terminals.
// Plot pin shapes and net names.
// Create a cell which will contain the extracted routing terminals, i.e. cell pins.
let routing_cell = // Find a unused name for the cell containing the routes.
.map(|i| format!("routes_{}_{}",, i))
.find(|name| chip.cell_by_name(name).is_none())
.map(|name| chip.create_cell(
let routing_terminal_cell_inst = chip.create_cell_instance(
&top_cell, &routing_cell, None,
chip.set_transform(&routing_terminal_cell_inst, db::SimpleTransform::identity());
// Terminal shapes for each net.
// This shapes need to be connected by the router.
let mut net_terminals = HashMap::new();
log::info!("Extract net terminals.");
// Create all pin shapes and associate them with the connected net.
for circuit_inst in chip.each_cell_instance_vec(&top_cell) {
let template_circuit = chip.template_cell(&circuit_inst);
let circuit_name = chip.cell_name(&template_circuit);
log::debug!("Find net terminals of cell '{}'.", &circuit_name);
// Property key for the net property.
let property_key_net = LN::NameType::from("net".to_string());
let cell_position = Some(chip.get_transform(&circuit_inst));
// TODO: Assert that the cell is marked as 'placed'. Needs additional attributes.
if let Some(cell_position) = cell_position {
for pin_inst in chip.each_pin_instance_vec(&circuit_inst) {
let pin = chip.template_pin(&pin_inst);
let pin_name = chip.pin_name(&pin);
// Get the layout shapes of the pin.
let pin_shapes: Vec<_> = chip.shapes_of_pin(&pin).collect();
if pin_shapes.is_empty() {
log::warn!("No pin shape found for pin '{}' in cell '{}'.", &pin_name, &circuit_name);
// Get signal direction of the pin.
let signal_direction = chip.pin_direction(&pin);
// Find net connected to this pin.
if let Some(net) = chip.net_of_pin_instance(&pin_inst) {
let net_name = chip.net_name(&net);
let terminals = net_terminals.entry(net)
let mut pin_geometries = vec![];
for pin_shape in &pin_shapes {
chip.with_shape(pin_shape, |layer, g| {
pin_geometries.push((layer.clone(), g.clone()))
for (pin_shape_layer, geo) in pin_geometries {
// Create a transformed copy of the pin shape.
let geo_tf = geo.transformed(&cell_position);
// Remember the terminal of this net.
let terminal = (geo_tf.to_polygon(), pin_shape_layer.clone());
if signal_direction.is_output() {
// Put the signal source first.
terminals.insert(0, terminal);
} else {
// Add the terminal shape to the cell with routing terminals.
let shape = chip.insert_shape(&routing_cell,
&pin_shape_layer, geo_tf.clone());
// Store the net name in the layout as property and text label.
if let Some(net_name) = &net_name {
chip.set_shape_property(&shape, property_key_net.clone(), net_name.to_string().into());
// // Add a label for debugging.
let label_location = geo_tf.to_polygon().exterior.points[0];
let text = db::Text::new(net_name.to_string(), label_location).into();
} else {
let inst_name = chip.cell_instance_name(&circuit_inst)
.map(|s| s.to_string())
.unwrap_or_else(|| "<unnamed>".to_string());
log::warn!("No position found for cell '{}' (type '{}').", inst_name, circuit_name);
// Make immutable.
let net_terminals = net_terminals;
// Take only nets that should be routed.
let nets_set: HashSet<_> = nets.iter().cloned().collect();
let net_terminals: HashMap<_, _> = net_terminals.into_iter()
.filter(|(n, _)| nets_set.contains(n))
// Print some statistics on terminals.
let num_terminals: usize = net_terminals.values()
.map(|t| t.len())
let num_one_terminal_nets = net_terminals.iter()
.filter(|(_, t)| t.len() <= 1)
log::info!("Number of nets with terminals: {}", net_terminals.len());
log::info!("Number of net terminals: {}", num_terminals);
if num_one_terminal_nets > 0 {
log::warn!("Number of nets with less than two terminals: {}", num_one_terminal_nets);
// Mapping from layer IDs to subsequent layer numbers.
let layer_numbers: HashMap<_, _> = routing_layers.iter()
.map(|(i, layer)| (layer.clone(), i as u8))
// Convert terminals into rectilinear polygons.
let net_terminals: HashMap<_, _> = net_terminals.into_iter()
.map(|(net, terminals)| {
let r_terminals: Vec<_> = terminals.into_iter()
.map(|(t, layer)| {
assert_eq!(t.interiors.len(), 0, "Polygons with holes are not supported.");
.expect("Only rectilinear polygons are supported"),
layer_numbers[&layer])] // Assign correct layer.
(net, r_terminals)
// Create a set of obstacles.
// For testing everything is put on a single layer.
let mut obstacles: Vec<_> = net_terminals.values()
.flat_map(|terminals| terminals.iter()
obstacles.iter().all(|(poly, _)|
"Obstacle polygons must have counter-clock-wise orientation."
// Get the bounding box of the top cell.
let top_cell_bounding_box = chip.bounding_box(&top_cell).unwrap();
assert!(routing_layers.len() <= u8::max_value() as usize);
let num_layers = routing_layers.len() as u8;
// Draw a boundary shape around the core on all layers.
// for layer in 0..num_layers {
// // Add core boundary on each layer.
// // TODO: Needed for line-search router only.
// let bbox = top_cell_bounding_box.sized(1, 1);
// let bbox_outer = bbox.sized(1, 1);
// let boundary_inner: db::SimpleRPolygon<_> = bbox.into();
// let boundary_outer: db::SimpleRPolygon<_> = bbox_outer.into();
// let boundary_outer = boundary_outer.reversed();
// obstacles.push(
// // Containing box.
// // Hole (oriented clock wise).
// (boundary_inner, layer)
// );
// obstacles.push(
// // Outer border (oriented counter-clock wise).
// (boundary_outer, layer),
// );
// }
// Register existing shapes such as the power grid as obstacles.
for (layer_num, layer) in routing_layers.iter().enumerate() {
let layer_info = chip.layer_info(layer);
log::info!("Find obstacles on layer {}/{} (name={:?})", layer_info.index, layer_info.datatype,;
// let mut debug_shapes = Vec::new();
chip.for_each_shape_recursive(&top_cell, layer, |tf, _id, shape| {
let poly = shape.transformed(&tf).to_polygon();
assert_eq!(poly.interiors.len(), 0, "Polygons with holes are not supported.");
let rpoly = SimpleRPolygon::try_new(poly.exterior.points)
.expect("Only rectilinear polygons are supported");
// debug_shapes.push((rpoly.clone(), layer.clone()));
obstacles.push((rpoly, layer_num as u8));
log::info!("Number of obstacle shapes: {}", obstacles.len());
// Replace net IDs by identifiers of type usize.
// Create lookup table for the net-to-ID mapping.
let nets_to_be_routed: Vec<_> = net_terminals.keys().cloned().collect();
let net_id_lookup_table: HashMap<_, _> = nets_to_be_routed.iter()
.map(|(i, net)| (net.clone(), i))
// Replace net IDs with integers.
let terminals = net_terminals.into_iter()
.map(| (net, terms)| (net_id_lookup_table[&net], terms))
// TODO: This sizing is arbitrary.
let boundary = top_cell_bounding_box.sized(4000, 4000);
assert!(num_layers <= u8::MAX);
let result = self.compute_routes(
// Find nets that have not been routed.
let unrouted_nets: Vec<_> = nets_to_be_routed.iter()
.filter(|&n| !result.contains_key(&net_id_lookup_table[n]))
self.draw_routes(chip, result, routing_cell, routing_layers, via_layers);
if unrouted_nets.is_empty() {
} else {