Example standard-cell placement engine for the LibrEDA-Rust framework. This placement algorithm simulates the movement of electric charges that are sparsely connected by springs (wires).
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.

440 lines
16 KiB

/*
* Copyright (c) 2019-2020 Thomas Kramer.
*
* This file is part of LibrEDA
* (see https://codeberg.org/libreda).
*
* 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
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* 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 <http://www.gnu.org/licenses/>.
*/
//! The quadratic placer does global placement of standard-cells by minimizing the quadratic wire-length.
//! It yields solutions quickly but they have strong overlaps and do not respect any density constraints.
//! Quadratic placement is therefore used mainly as an initial value for other placers.
use super::sparse_matrix::SparseRowSquareMatrix;
use libreda_pnr::db;
use db::*;
pub use libreda_pnr::place::stdcell_placer::SimpleStdCellPlacer;
use std::rc::Rc;
use std::collections::{HashMap, HashSet};
use argmin::prelude as am;
use argmin::solver::conjugategradient::ConjugateGradient;
use argmin::core::Error;
use log::{debug, info};
/// The quadratic placement algorithm minimizes the quadratic distance between components.
///
/// This can be thought of connecting components with springs if they are connected by a net
/// and then finding the equilibrium position where all resulting forces onto the movable components are
/// zero. Only fixed components (like pads) experience a force.
///
/// The resulting placement has strong overlaps and is typically used as an initial value
/// for other placers such as electro-static placement.
#[derive(Clone)]
pub struct SimpleQuadraticPlacer {
/// Maximum number of iterations.
max_iter: u64
}
impl SimpleQuadraticPlacer {
/// Create a default quadratic placer.
pub fn new() -> Self {
SimpleQuadraticPlacer {
max_iter: 100
}
}
/// Set the maximum number of iterations.
pub fn max_iter(mut self, max_iter: u64) -> Self {
self.max_iter = max_iter;
self
}
}
impl<N: NetlistBase> SimpleStdCellPlacer<N> for SimpleQuadraticPlacer {
fn name(&self) -> &str {
"QuadraticPlacer"
}
fn find_cell_positions_impl(&self,
netlist: &N,
circuit: &N::CellId,
core_area: &SimplePolygon<SInt>,
initial_positions: &HashMap<N::CellInstId, Point<SInt>>,
fixed_instances: &HashSet<N::CellInstId>,
) -> HashMap<N::CellInstId, Point<i32>> {
info!("Run quadratic placement.");
// Get positions for all fixed instances.
let fixed_positions = fixed_instances.iter()
.map(|i| (i.clone(), initial_positions[i]))
.collect();
debug!("Create linear equation system from netlist.");
let ((m, b_x, b_y), movable_instance_ids) =
create_equation_system(netlist, circuit, &fixed_positions);
// Get the number of additional points that have been added as centers
// of multi-terminal nets (They are represented in a star topology).
let num_net_center_points = b_x.len() - movable_instance_ids.len();
// ArgminOp
let operator_x = CgSolver {
matrix_a: m.clone()
};
let operator_y = CgSolver {
matrix_a: m.clone()
};
// Compute default initial position
// as the average of all fixed positions.
let default_position = fixed_positions.values().copied().sum::<Point<SInt>>()
/ (fixed_positions.len() as SInt);
// Get initial guesses for x and y based on initial positions.
// Get initial positions, default is (0, 0).
let initial_positions = movable_instance_ids.iter()
.map(|idx| initial_positions.get(idx)
.copied()
.unwrap_or(default_position)
)
// Add initial positions for net center points.
.chain((0..num_net_center_points).map(|_| Point::zero()));
// Split initial positions into x and y vectors.
let (init_x, init_y): (Vec<_>, Vec<_>) = initial_positions
// Split into tuple and cast to float.
.map(|p| (p.x as f32, p.y as f32))
// Split into x and y vectors.
.unzip();
assert_eq!(init_x.len(), b_x.len());
assert_eq!(init_y.len(), b_y.len());
// Solve for x.
debug!("Solve Ax = b_x.");
let solver_x: ConjugateGradient<_, f32> = ConjugateGradient::new(b_x).unwrap();
let res_x = am::Executor::new(operator_x, solver_x, init_x)
.max_iters(self.max_iter)
.run().unwrap();
let best_x = res_x.state.best_param;
// Solve for y.
debug!("Solve Ay = b_y.");
let solver_y: ConjugateGradient<_, f32> = ConjugateGradient::new(b_y).unwrap();
let res_y = am::Executor::new(operator_y, solver_y, init_y)
.max_iters(self.max_iter)
.run().unwrap();
let best_y = res_y.state.best_param;
// Assemble x and y vector into points
// and associate them together with the circuit instance indices.
let positions: HashMap<_, _> = best_x.into_iter()
.zip(best_y)
.map(|(x, y)| Point::new(x as SInt, y as SInt))
.zip(movable_instance_ids)
.map(|(p, id)| (id, p))
.collect();
info!("Done.");
positions
}
}
/// The quadratic placement algorithm minimizes the quadratic distance between components.
///
/// This can be thought of connecting components with springs if they are connected by a net
/// and then finding the equilibrium position where all resulting forces onto the movable components are
/// zero. Only fixed components (like pads) experience a force.
///
/// Positions can be found by solving the following equation system:
/// `A*x = b_x, A*y = b_y`.
///
/// Where `A` can be constructed as follows:
/// Get connectivity matrix `C` first. Then `A = -C + d`.
/// `d` is a diagonal matrix where `d[i, i] = sum(row(C, i)) + (sum of weights of all wires from cell i to pads)`
///
/// Construct `b_x`:
/// If gate i connects to a pad at `(x_i, y_i)` with a wire with weight `w_i: b_x[i] = w_i * x_i`
/// Same for `b_y`.
///
/// Nets with more than two terminals are converted into a star topology.
/// Create `A`, `b_x` and `b_y` such that the positions of the cells can be found
/// by solving `Ax = b_x` and `Ay = b_y`.
///
/// # Returns
/// Returns a tuple `((A, b_x, b_y), Vec of movable circuit instances)`.
/// The ordering of the movable circuit instances corresponds to the ordering used
/// in the equation system.
fn create_equation_system<N: NetlistBase>(
netlist: &N,
circuit: &N::CellId,
fixed_positions: &HashMap<N::CellInstId, db::Point<db::SInt>>)
-> ((SparseRowSquareMatrix<f32>, Vec<f32>, Vec<f32>), Vec<N::CellInstId>) {
assert_eq!(netlist.num_pins(circuit), 0, "Top level circuit is not allowed to have pins.");
// Group nets by nets that have two or less terminals and nets that have more than two terminals.
let (nets_simple, nets_multi): (Vec<_>, Vec<_>) = netlist.each_internal_net(circuit)
.partition(|net| netlist.num_net_pin_instances(net) <= 2);
let (_cells_fixed, mut cells_movable): (Vec<_>, Vec<_>) =
netlist.each_cell_instance(circuit)
.partition(|inst| fixed_positions.contains_key(inst));
// Sort by id to make the ordering deterministic.
cells_movable.sort_by_key(|c| netlist.cell_instance_name(c));
let cells_movable = cells_movable; // Make immutable.
let num_movable_cells = cells_movable.len();
let num_nets_multi = nets_multi.len();
let num_variable_points = num_movable_cells + num_nets_multi;
// Assign indices to all movable cells.
let movable_cell_indices: HashMap<_, _> = cells_movable.iter()// TODO: Necessary?
.enumerate()
.map(|(i, c)| (c, i))
.collect();
// Assign indices to all virtual center nodes of multi-terminal nets.
let net_center_point_indices: HashMap<_, _> = nets_multi.iter()
.enumerate()
.map(|(i, net)| (net, i + num_movable_cells))
.collect();
let mut m_conn = SparseRowSquareMatrix::new(num_variable_points);
let mut b_x = vec![0.0; num_variable_points];
let mut b_y = vec![0.0; num_variable_points];
let mut weights_to_fixed = vec![0.0; num_variable_points];
// Process nets with at most two terminals.
for net in &nets_simple {
// Get all circuit instances connected to the net.
let cells: Vec<_> = netlist.each_circuit_instance_of_net_vec(net);
assert!(cells.len() <= 2);
if cells.len() == 2 {
let cell_id_1 = &cells[0];
let cell_id_2 = &cells[1];
let idx1 = movable_cell_indices.get(cell_id_1);
let idx2 = movable_cell_indices.get(cell_id_2);
match (idx1, idx2) {
(Some(&idx1), Some(&idx2)) => {
// Both movable.
let weight = 1.0;
m_conn.add_at(idx1, idx2, weight);
m_conn.add_at(idx2, idx1, weight);
}
(Some(&idx1), None) => {
// Idx1 is connected to a fixed component.
let fixed_pos = fixed_positions[cell_id_2];
let weight = 1.0;
b_x[idx1] += weight * fixed_pos.x as f32;
b_y[idx1] += weight * fixed_pos.y as f32;
weights_to_fixed[idx1] += weight;
}
(None, Some(&idx2)) => {
// Idx2 is connected to a fixed component.
let fixed_pos = fixed_positions[cell_id_1];
let weight = 1.0;
b_x[idx2] += weight * fixed_pos.x as f32;
b_y[idx2] += weight * fixed_pos.y as f32;
weights_to_fixed[idx2] += weight;
}
_ => {}
}
}
}
// Process multi-terminal nets.
for net in &nets_multi {
// Get all circuit instances connected to the net.
let cells: Vec<_> = netlist.each_circuit_instance_of_net_vec(net);
assert!(cells.len() > 2);
let idx_net_center = net_center_point_indices[net];
for cell in cells {
let idx_cell = movable_cell_indices.get(&cell);
if let Some(&idx_cell) = idx_cell {
// Cell is movable.
let weight = 1.0;
m_conn.add_at(idx_net_center, idx_cell, weight);
m_conn.add_at(idx_cell, idx_net_center, weight);
} else {
// Cell is fixed.
let fixed_pos = fixed_positions[&cell];
let weight = 1.0;
b_x[idx_net_center] += weight * fixed_pos.x as f32;
b_y[idx_net_center] += weight * fixed_pos.y as f32;
weights_to_fixed[idx_net_center] += weight;
}
}
}
// Compute sums of each row as needed for computing `d`.
let row_sums: Vec<f32> = (0..m_conn.dim())
.map(|i| m_conn.iter_row(i)
.map(|(_, v)| v)
.sum()
)
.collect();
// Create diagonal matrix d.
// where `d[i, i] = sum(row(C, i)) + (sum of weights of all wires from cell i to pads)`
let mut d = SparseRowSquareMatrix::new(row_sums.len());
for i in 0..m_conn.dim() {
let d_ii = weights_to_fixed[i] + row_sums[i];
d.set(i, i, d_ii);
}
// Compute matrix `A`.
let a = &d - &m_conn;
// dbg!(&b_x);
((a, b_x, b_y), cells_movable)
}
/// Iteratively solve a linear system of the form `Ax = b`
/// where `A` is positive-definite.
struct CgSolver {
matrix_a: SparseRowSquareMatrix<f32>,
}
impl am::ArgminOp for CgSolver {
type Param = Vec<f32>;
type Output = Vec<f32>;
type Hessian = ();
type Jacobian = ();
type Float = f32;
fn apply(&self, param: &Self::Param) -> Result<Self::Output, Error> {
Ok(self.matrix_a.mul_vec(param))
}
}
#[test]
fn test_create_connectivity_matrix() {
// Construct simple circuit with three placed cells and three non-placed cells.
let mut netlist = db::Chip::new();
let top = netlist.create_cell("top".into());
// Fixed circuit.
let pad = netlist.create_cell("pad".into());
netlist.create_pin(&pad, "A".into(), db::Direction::InOut);
// Circuit to be placed.
let cell = netlist.create_cell("cell".into());
netlist.create_pin(&cell, "A".into(), db::Direction::InOut);
netlist.create_pin(&cell, "B".into(), db::Direction::InOut);
netlist.create_pin(&cell, "C".into(), db::Direction::InOut);
let pad_a = netlist.create_circuit_instance(&top, &pad, None);
let pad_b = netlist.create_circuit_instance(&top, &pad, None);
let pad_c = netlist.create_circuit_instance(&top, &pad, None);
let cell_a = netlist.create_circuit_instance(&top, &cell, None);
let cell_b = netlist.create_circuit_instance(&top, &cell, None);
let cell_c = netlist.create_circuit_instance(&top, &cell, None);
let cell_d = netlist.create_circuit_instance(&top, &cell, None);
// Connect the instances.
// Nets to pads.
let net_a = netlist.create_net(&top,Some("A".into()));
let net_b = netlist.create_net(&top,Some("B".into()));
let net_c = netlist.create_net(&top,Some("C".into()));
// Nets between cells.
let net1 = netlist.create_net(&top,Some("1".into()));
let net2 = netlist.create_net(&top,Some("2".into()));
let net3 = netlist.create_net(&top,Some("3".into()));
netlist.connect_pin_instance(&netlist.each_pin_instance_vec(&pad_a)[0], Some(net_a.clone()));
netlist.connect_pin_instance(&netlist.each_pin_instance_vec(&pad_b)[0], Some(net_a.clone()));
netlist.connect_pin_instance(&netlist.each_pin_instance_vec(&pad_c)[0], Some(net_a.clone()));
netlist.connect_pin_instance(&netlist.each_pin_instance_vec(&cell_a)[0], Some(net_a.clone()));
netlist.connect_pin_instance(&netlist.each_pin_instance_vec(&cell_a)[1], Some(net1.clone()));
netlist.connect_pin_instance(&netlist.each_pin_instance_vec(&cell_a)[2], Some(net2.clone()));
netlist.connect_pin_instance(&netlist.each_pin_instance_vec(&cell_b)[0], Some(net_b.clone()));
netlist.connect_pin_instance(&netlist.each_pin_instance_vec(&cell_b)[1], Some(net1.clone()));
netlist.connect_pin_instance(&netlist.each_pin_instance_vec(&cell_b)[2], Some(net3.clone()));
netlist.connect_pin_instance(&netlist.each_pin_instance_vec(&cell_c)[0], Some(net_c.clone()));
netlist.connect_pin_instance(&netlist.each_pin_instance_vec(&cell_c)[1], Some(net3.clone()));
netlist.connect_pin_instance(&netlist.each_pin_instance_vec(&cell_c)[2], Some(net1.clone()));
// Make sure there is at least a net with more than two terminals.
netlist.connect_pin_instance(&netlist.each_pin_instance_vec(&cell_d)[0], Some(net1.clone()));
let fixed_positions: HashMap<_, _> =
vec![
(pad_a.clone(), db::Point::new(1, 1)),
(pad_b.clone(), db::Point::new(100, 2)),
(pad_c.clone(), db::Point::new(50, 100)),
].into_iter().collect();
let ((m, b_x, b_y), cells) =
create_equation_system(&netlist, &top, &fixed_positions);
// println!("{}", &m);
// dbg!(&b_x);
// dbg!(&b_y);
// Solve for x coordinates.
let operator = CgSolver {
matrix_a: m.clone()
};
// Initial guess.
let init_param = vec![0.0; b_x.len()];
let solver_x: ConjugateGradient<_, f32> = ConjugateGradient::new(b_x.clone()).unwrap();
let res_x = am::Executor::new(operator, solver_x, init_param)
.max_iters(200)
.run().unwrap();
let best_x = res_x.state.best_param;
// Associate x coordinates with cells and print them.
let mut x_coords: Vec<_> = cells.iter().zip(&best_x)
.map(|(cell, x)| (netlist.cell_instance_name(cell), *x))
.collect();
x_coords.sort_by_key(|e| e.0.clone());
// println!("{:?}", x_coords);
// Check if the solution `x` is actually close to the real solution.
let test_b = m.mul_vec(&best_x);
// dbg!(&test_b);
let abs_diff_sum: f32 = test_b.iter().zip(&b_x)
.map(|(a, b)| (a - b).abs())
.sum();
assert!(abs_diff_sum < 1e-3);
}