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.

344 lines
14 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 <>.
//! Tools for inserting tie-cells to drive constant nets.
use crate::db;
use db::traits::*;
use db::{Direction, CoordinateType};
use num_traits::{PrimInt, NumCast};
/// Insert tie cells and connect unconnected LOW and HIGH nets.
/// Tie-cells are placed such that the maximal manhattan distance
/// to the sinks is kept below `max_distance`.
#[derive(Debug, Clone)]
pub struct SimpleTieCellInsertionEngine {
/// Name of the tie-low cell to be used for buffering constant LOW nets.
pub tie_cell_low: String,
/// Name of the tie-high cell to be used for buffering constant HIGH nets.
pub tie_cell_high: String,
/// Maximal number of cells that should be driven by a tie-cell cell.
/// Must be larger than `1`.
pub max_fanout: u32,
/// Maximal manhattan distance from the tie-cell to the attached sink.
pub max_distance: db::Coord,
impl SimpleTieCellInsertionEngine {
/// Insert tie cells to drive the sinks which are attached to this net.
/// The net must be either the constant LOW or HIGH net.
/// A tie cell is usually used to drive a cluster of many inputs. The way the
/// clusters are formed depends on the locations of the inputs such that the wiring
/// can be minimized from tie-cells to inputs but also the additional space required by tie-cells
/// is reasonable (instead of placing a tie-cell for every input).
pub fn insert_tie_cells_on_net<LN: NetlistEdit + LayoutEdit>(
chip: &mut LN,
net: &LN::NetId,
) -> Result<(Vec<LN::CellInstId>, Vec<LN::NetId>), ()>
where LN::Coord: PrimInt {
// Check if the net is a special net (LOW or HIGH).
if !chip.is_constant_net(&net) {
let parent_name = chip.cell_name(&chip.parent_cell_of_net(&net));
log::warn!("Net '{:?}' in '{}' is neither a constant LOW nor HIGH net.", &net, parent_name);
// Find the sinks of the net.
let mut sinks = vec![];
for t in chip.each_terminal_of_net(&net) {
// A pin of the parent cell is considered to be a source when it's direction is 'INPUT',
// however a pin instance that connects to a child instance is considered a sink when it's direction is 'INPUT'.
match &t {
TerminalId::PinId(p) => {
match chip.pin_direction(p) {
Direction::Output => sinks.push(t),
d => {
let cell_name = chip.cell_name(&chip.parent_cell_of_pin(&p));
let pin_name = chip.pin_name(p);
panic!("Cannot handle pin direction of pin '{}' in cell '{}': {:?} (must be an output)", pin_name, cell_name, d)
TerminalId::PinInstId(p) => {
match chip.pin_direction(&chip.template_pin(p)) {
Direction::Input => sinks.push(t),
d => {
let pin = chip.template_pin(p);
let cell_name = chip.cell_name(&chip.parent_cell_of_pin(&pin));
let pin_name = chip.pin_name(&pin);
panic!("Cannot handle pin direction of pin '{}' in cell '{}': {:?} (must be an input)", pin_name, cell_name, d)
log::debug!("Number of sinks: {}", sinks.len());
self.insert_tie_cells(chip, &sinks)
/// All terminals must be in the same parent cell.
/// Returns a vector of all added tie-cell instances and all added nets.
fn insert_tie_cells<LN: NetlistEdit + LayoutEdit>(
chip: &mut LN,
signal_sinks: &Vec<TerminalId<LN>>,
) -> Result<(Vec<LN::CellInstId>, Vec<LN::NetId>), ()>
where LN::Coord: PrimInt {
log::debug!("Insert tie-cells for {} sinks.", signal_sinks.len());
// Store all nets and cells that are added in this step and return them later.
let mut added_tie_cells = vec![];
let mut added_nets = vec![];
if signal_sinks.is_empty() {
return Ok((added_tie_cells, added_nets));
let parent_cell = match &signal_sinks[0] {
TerminalId::PinId(p) => chip.parent_cell_of_pin(p),
TerminalId::PinInstId(p) => chip.parent_cell(&chip.parent_of_pin_instance(p))
// Sanity check: The source and all sinks must be connected to the same net.
let source_net = chip.net_of_terminal(&signal_sinks[0]);
if source_net.is_none() {
log::error!("Sink terminal is not connected to any net.");
// TODO: Pass a `Result::Err` instead o panicking?
panic!("Source terminal is not connected to any net.");
let is_connected_to_correct_nets = signal_sinks.iter()
.all(|sink| chip.net_of_terminal(sink) == source_net);
if !is_connected_to_correct_nets {
log::error!("Sinks are not all connected to the same net as the source.");
panic!("Sinks are not all connected to the same net as the source.");
let source_net = source_net.unwrap();
assert!(chip.is_constant_net(&source_net), "Net must be either constant LOW or HIGH for tie-cell insertion.");
let net_value = source_net == chip.net_one(&parent_cell);
let tie_cell_name = if net_value {
} else {
// Find tie-cell cell to be used.
log::info!("Use tie-cell '{}'.", &tie_cell_name);
let tie_cell = chip.cell_by_name(tie_cell_name)
.expect("Tie-cell not found.");
// Detect inputs and the outputs of the tie-cell cell.
let inputs: Vec<_> = chip.each_pin(&tie_cell)
.filter(|pin| chip.pin_direction(&pin).is_input())
assert_eq!(inputs.len(), 0, "Tie-cell must have no input pins.");
let outputs: Vec<_> = chip.each_pin(&tie_cell)
.filter(|pin| chip.pin_direction(&pin).is_output())
assert_eq!(outputs.len(), 1, "Tie-cell must have exactly one output pin.");
let tie_cell_output = outputs[0].clone();
// Find locations of terminals.
let terminal_location = |t: &TerminalId<LN>| {
match t {
TerminalId::PinId(_t) => {
// TODO: Find the location of the pin shape.
TerminalId::PinInstId(t) => {
let inst = chip.parent_of_pin_instance(t);
let tf = chip.get_transform(&inst);
// Assume that the physical pin is close to the origin of the cell.
// This is good enough only for small standard-cells, not for big macro blocks.
let location = tf.transform_point(db::Point::zero());
// Build clusters that are driven by the same tie-cell.
let clusters = {
// Find sink locations.
let sink_locations: Vec<_> = signal_sinks.iter()
// Find clusters.
let (cluster_ids, num_clusters) = find_clusters(
// Create a nested list of terminals for each cluster.
let mut clusters = vec![vec![]; num_clusters as usize];
for (i, cluster_id) in cluster_ids.iter().enumerate() {
clusters[*cluster_id as usize].push((signal_sinks[i].clone(), sink_locations[i]));
// Create a tie-cell for each cluster.
let mut name_counter = 0; // Counter for unique names of tie-cell instances.
for cluster in clusters {
let (sinks, positions): (Vec<_>, Vec<_>) = cluster.into_iter().unzip();
let center = center_of_mass(&positions);
// Create name for the tie-cell instance.
let instance_name = loop {
let name = format!("_tie_cell_{}", name_counter);
name_counter += 1;
if chip.cell_instance_by_name(&parent_cell, &name).is_none() {
break name;
let tie_cell_inst = chip.create_cell_instance(&parent_cell, &tie_cell, Some(instance_name.into()));
// Create output net.
let new_net = chip.create_net(&parent_cell, None);
// Connect output of the tie-cell to the buffered net.
let tie_cell_output_pin = chip.pin_instance(&tie_cell_inst, &tie_cell_output);
chip.connect_pin_instance(&tie_cell_output_pin, Some(new_net.clone()));
// Set the location of the tie-cell.
chip.set_transform(&tie_cell_inst, db::SimpleTransform::translate(center));
// Connect the sinks to the tie_cell output.
for sink in &sinks {
let old_net = chip.connect_terminal(sink, Some(new_net.clone()));
debug_assert_eq!(old_net.as_ref(), Some(&source_net), "Sink is expected to be connected to the source net.");
Ok((added_tie_cells, added_nets))
/// Group points together to clusters and return a vector with the cluster ID for each point and the number of clusters.
/// The clusters are formed as follows:
/// 1) Sort the points by (x, y).
/// 2) As long as there's an unassigned point: take the next unassigned point `p` and put it into the new cluster `c`.
/// 3) Take the closest point to the center of the bounding-box around `c`. If adding `p` to `c` does not enlarge the bounding box
/// around `c` beyond `max_cluster_span` then add `p` to `c` and repeat 3) otherwise go to 2).
/// * `max_cluster_size`: Maximal number of points in cluster.
/// * `max_cluster_span`: Maximal width and height of the bounding box around the cluster.
fn find_clusters<C: CoordinateType + PrimInt>(points: &Vec<db::Point<C>>,
max_cluster_size: u32,
max_cluster_span: C) -> (Vec<u32>, u32) {
// For each point store the original index and the cluster ID.
// The index used to map back to the original points after sorting.
let mut points_with_cluster_id: Vec<(db::Point<_>, usize, u32)> = points.iter()
.map(|(idx, p)| (*p, idx, 0))
// Sort by locations.
points_with_cluster_id.sort_by_key(|(p, _, _)| (p.x, p.y));
let mut cluster_id = 0u32;
// While there is a point that does not belong to a cluster
// take the first one (sorted by x and y) and use it as a start
// of the cluster.
let mut current_cluster_points = vec![];
// Find the first point without assigned cluster.
while let Some((first_point_idx, _)) = points_with_cluster_id.iter()
.find(|(_pos, (_, _, cluster))| *cluster == 0) {
cluster_id += 1;
// Assign the cluster ID.
points_with_cluster_id[first_point_idx].2 = cluster_id;
let start = points_with_cluster_id[first_point_idx].0;
let mut bbox = db::Rect::new(start, start);
// Find closest neighbour.
for _ in 1..max_cluster_size {
// Compute center of mass of the cluster.
let center = center_of_mass(&current_cluster_points);
let closest = points_with_cluster_id.iter()
.filter(|(_, (_, _, cluster))| *cluster == 0) // Take only unassigned sinks.
.filter(|(_, (p, _, _))| {
let new_bbox = bbox.add_point(*p);
new_bbox.height() < max_cluster_span && new_bbox.width() < max_cluster_span
.min_by_key(|(_, (pos, _, _))| (center - *pos).norm1())
.map(|(idx, _)| idx);
if let Some(closest) = closest {
points_with_cluster_id[closest].2 = cluster_id;
let p = points_with_cluster_id[closest].0;
// Update the cluster bounding box.
bbox = bbox.add_point(p);
} else {
// No unassigned node found.
let num_clusters = cluster_id;
let mut result = vec![0u32; points_with_cluster_id.len()];
for (_p, index, cluster_id) in points_with_cluster_id {
result[index] = cluster_id - 1; // `0` meant 'no cluster'
(result, num_clusters)
/// Compute the center of mass of a list of points.
fn center_of_mass<C: PrimInt>(points: &Vec<db::Point<C>>) -> db::Point<C> {
// Sum up all points and divide by number of points.
.fold(db::Point::zero(), |a, b| a + b)
/ NumCast::from(points.len()).unwrap()