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.

462 lines
19 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/>.
*/
//! Placement refinement based on solving the diffusion equation.
//!
//! # References
//!
//! 1) Diffusion-based placement migration: <http://users.ece.utexas.edu/~dpan/publications/dac05_dbp.pdf>
use std::mem;
pub use libreda_pnr::place::stdcell_placer::SimpleStdCellPlacer;
use libreda_pnr::db::*;
use libreda_pnr::db as db;
use std::rc::Rc;
use std::collections::{HashMap, HashSet};
use log::{debug, info, warn, error};
use itertools::Itertools;
use ndarray::prelude::*;
/// Simulate the diffusion of particles to spread standard cells in order to match
/// a certain maximal density.
///
/// This is not a global placer, but is intended as a refinement step. The initial positions
/// of the cells must be found with another placement algorithm.
#[derive(Clone)]
pub struct DiffusionPlacer<N: NetlistBase> {
bin_size: UInt,
max_density: f64,
cell_dimensions: HashMap<N::CellId, db::Rect<db::Coord>>,
max_iter: u64,
}
impl<N: NetlistBase> DiffusionPlacer<N> {
/// Create a new diffusion placer instance.
///
/// # Parameters
/// `bin_size`: Side length of the quadratic bins.
/// `max_density`: The maximal allowed density in a bin. Should be a value between 0 and 1.
pub fn new(bin_size: UInt, max_density: f64) -> Self {
assert!(max_density > 0.0, "Maximal density must be positive.");
if max_density > 1.0 {
// Maximal density above one does not make much sense.
warn!("Maximal density is larger than 1 ({}).", max_density);
}
Self {
bin_size,
max_density,
cell_dimensions: Default::default(),
max_iter: 0
}
}
/// Set the maximum number of iterations.
/// `0` means no limit.
pub fn max_iter(mut self, max_iter: u64) -> Self {
self.max_iter = max_iter;
self
}
}
// /// Create a `width`*`height` 2-dimensional array filled with a value.
// fn create_2d_array<T: Copy>(width: usize, height: usize, value: T) -> Vec<Vec<T>> {
// (0..width).map(
// |_i| vec![value; height]
// ).collect()
// }
/// Interpolate over a two dimensional grid cell.
/// The sample values are located on the corners of the quadratic grid cell:
///
/// ```txt
/// [[x10, x11]
/// [x00, x01]]
/// ```
///
/// The parameters `alpha` and `beta` give the position of the interpolation point.
fn interpolate2d(x00: f64, x10: f64, x01: f64, x11: f64, alpha: f64, beta: f64) -> f64 {
debug_assert!(alpha >= 0.0 && alpha <= 1.0);
debug_assert!(beta >= 0.0 && beta <= 1.0);
x00 + alpha * (x10 - x00) + beta * (x01 - x00) + alpha * beta * (x00 + x11 - x10 - x01)
}
#[test]
fn test_interpolate2d() {
assert!((interpolate2d(1., 2., 3., 4., 0., 0.) - 1.).abs() < 1e-6);
assert!((interpolate2d(1., 2., 3., 4., 1., 0.) - 2.).abs() < 1e-6);
assert!((interpolate2d(1., 2., 3., 4., 0., 1.) - 3.).abs() < 1e-6);
assert!((interpolate2d(1., 2., 3., 4., 1., 1.) - 4.).abs() < 1e-6);
assert!((interpolate2d(0., 1., 1., 0., 0.5, 0.5) - 0.5).abs() < 1e-6);
}
impl<N: NetlistBase> SimpleStdCellPlacer<N> for DiffusionPlacer<N> {
fn name(&self) -> &str {
"DiffusionPlacer"
}
fn set_cell_dimensions(&mut self, cell_dimensions: HashMap<N::CellId, db::Rect<db::Coord>>) {
self.cell_dimensions = cell_dimensions;
}
fn find_cell_positions_impl(&self,
netlist: &N,
circuit: &N::CellId,
core_area: &SimplePolygon<i32>,
initial_positions: &HashMap<N::CellInstId, Point<i32>>,
fixed_instances: &HashSet<N::CellInstId>,
) -> HashMap<N::CellInstId, Point<i32>> {
if self.cell_dimensions.is_empty() {
error!("This placer needs to know cell dimensions. Call `set_cell_dimensions()` first.");
panic!("Cell dimensions are not set.")
}
// Get bounding box of placement region.
let boundary_bbox = core_area.try_bounding_box().unwrap();
// Maximal allowed density.
let max_density = self.max_density;
let bin_size = self.bin_size as SInt;
debug_assert!(bin_size > 0);
// Area of a bin. Needed to compute the densities.
let bin_area = bin_size as f64 * bin_size as f64;
// Get number of bins.
// Extend the bins: Append a row of bins on all sides for handling boundaries properly.
let bin_extension = 1; // Extension towards each side.
let num_bin_x = ((boundary_bbox.width() + bin_size - 1) / bin_size) as usize + 2 * bin_extension;
let num_bin_y = ((boundary_bbox.height() + bin_size - 1) / bin_size) as usize + 2 * bin_extension;
let num_bins = num_bin_x * num_bin_y;
// let mut bin_density = create_2d_array(num_bin_x, num_bin_y, 0.0);
// let mut bin_velocity_x = create_2d_array(num_bin_x, num_bin_y, 0.0);
// let mut bin_velocity_y = create_2d_array(num_bin_x, num_bin_y, 0.0);
let mut bin_density = Array::from_elem((num_bin_x, num_bin_y), 0.0);
// Buffer for bin velocity values.
let mut bin_velocity_x = Array::from_elem((num_bin_x, num_bin_y), 0.0);
let mut bin_velocity_y = Array::from_elem((num_bin_x, num_bin_y), 0.0);
// Convert coordinates of cells into bin indices.
let bin_indices = |x: Coord, y: Coord| -> (usize, usize) {
let extension_size = bin_extension as Coord * bin_size;
let i = (x - boundary_bbox.lower_left().x + extension_size) / bin_size;
let j = (y - boundary_bbox.lower_left().y + extension_size) / bin_size;
let i = i.min(num_bin_x as Coord - 1)
.max(0) as usize;
let j = j.min(num_bin_y as Coord - 1)
.max(0) as usize;
debug_assert!(i < num_bin_x);
debug_assert!(j < num_bin_y);
// debug_assert!(i >= 0);
// debug_assert!(j >= 0);
(i, j)
};
// Compute the center coordinates of a bin.
let bin_center_location = |i: usize, j: usize| -> (Coord, Coord) {
let x = (i as Coord - bin_extension as Coord) * bin_size + boundary_bbox.lower_left().x;
let y = (j as Coord - bin_extension as Coord) * bin_size + boundary_bbox.lower_left().y;
// Bin (0, 0) is outside of the boundary (left, underneath).
(x + bin_size / 2, y + bin_size / 2)
};
// Create components (equivalent to cells) as needed by the placer.
let all_instances: Vec<_> = netlist.each_cell_instance_vec(circuit);
// Get initial cell positions as as floating point type.
let mut instance_positions: Vec<Point<f64>> = all_instances.iter()
.map(|inst_id| initial_positions.get(inst_id)
.expect("Need an initial position for all cells.")
.cast())
.collect();
// Get all cell areas.
let cell_areas: Vec<_> = all_instances.iter()
.map(|inst| {
let cell_id = netlist.template_cell(inst);
self.cell_dimensions.get(&cell_id)
.map(|r| r.width() * r.height())
.unwrap_or(0)
})
.collect();
// Map cells to bins and compute the density for each bin.
for inst in &all_instances {
// Get cell area.
let cell_id = netlist.template_cell(inst);
let (w, h) = self.cell_dimensions.get(&cell_id)
.map(|r| (r.width(), r.height()))
.unwrap_or((0, 0));
let cell_area = w as f64 * h as f64;
let pos = *initial_positions.get(&inst)
.expect("Need an initial position for all cells.");
// Find correct bin.
let (bin_x, bin_y) = bin_indices(pos.x, pos.y);
// Update density of the bin.
// TODO: Take into account that cells might be only partially inside the bin.
bin_density[[bin_x, bin_y]] += cell_area / bin_area;
}
// Compute the sum of excess densities and density shortage.
// Compute `A_o` and `A_s` as in [1](8).
let (area_over, area_under) = bin_density.iter()
.fold((0., 0.),
|(area_over, area_under), &d| {
if d < max_density {
// Accumulate density shortage.
(area_over, area_under + (max_density - d))
} else {
// Accumulate density excess.
(area_over + (d - max_density), area_under)
}
});
// Adjust densities such that the average density is equal to the maximum density.
// This helps avoiding over-spreading.
{
let density_correction_factor = area_over / area_under;
bin_density.iter_mut()
.for_each(|d| {
*d = if *d < max_density {
max_density - (max_density - *d) * density_correction_factor
} else {
*d
}
});
}
{
// Check that the average density now is (approximately) equal to the maximum density.
let density_sum: f64 = bin_density.iter().sum();
let average_density = density_sum / num_bins as f64;
debug_assert!((average_density - max_density).abs() < 1e-6);
}
// Solve the diffusion equation iteratively
// until all densities are below or equal to the maximal density.
let mut density_current = bin_density;
// Allocate a buffer for the densities of the next iteration.
let mut density_next = density_current.clone();
let mut iter_count = (0..).into_iter();
debug!("Maximum number of iterations: {}", self.max_iter);
loop {
// Stop condition: All bin densities are below the maximal density.
// Let find largest density.
let largest_density = density_current
.slice(s![1..num_bin_x-2, 1..num_bin_y-2])
.iter()
.fold(0., |acc: f64, &d| acc.max(d));
debug!("largest density = {}", largest_density);
if largest_density <= max_density {
// Reached the density constraint.
info!("Reached density constraint ({:.4} <= {:.4}).", largest_density, max_density);
break;
}
// Find location of largest density.
let indices = (0..num_bin_x).into_iter()
.flat_map(|x| (0..num_bin_y).into_iter().map(move |y| (x, y)));
let max_index = indices.max_by(|a, b|
density_current[[a.0, a.1]].partial_cmp(&density_current[[b.0, b.1]]).unwrap()
).unwrap();
info!("Maximal density in bin {}, {}", max_index.0, max_index.1);
// Break the loop when the maximum number of iterations is reached.
if self.max_iter != 0 {
if iter_count.next().unwrap() >= self.max_iter {
info!("Reached maximum number of iterations ({}).", self.max_iter);
info!("Did not reach density constraint ({:.4} <= {:.4}).", largest_density, max_density);
break;
}
}
{
// Check that the average density now is (approximately) equal to the maximum density.
// If the integration is done correctly the average density does not change.
let density_sum: f64 = density_current.iter().sum();
let average_density = density_sum / num_bins as f64;
debug_assert!((average_density - max_density).abs() < 1e-6);
}
// Make density constant among boundaries to assure that the diffusion is zero across
// the boundary.
let (mut boundary, next_to_boundary) = density_current.multi_slice_mut((s![0, ..], s![1, ..]));
boundary.assign(&next_to_boundary);
let (mut boundary, next_to_boundary) = density_current.multi_slice_mut((s![num_bin_x-1, ..], s![num_bin_x-2, ..]));
boundary.assign(&next_to_boundary);
let (mut boundary, next_to_boundary) = density_current.multi_slice_mut((s![.., 0], s![.., 1]));
boundary.assign(&next_to_boundary);
let (mut boundary, next_to_boundary) = density_current.multi_slice_mut((s![.., num_bin_y-1], s![.., num_bin_y-2]));
boundary.assign(&next_to_boundary);
// Compute velocities based on the gradient of the densities.
// Clear old velocities.
bin_velocity_x.fill(0.);
bin_velocity_y.fill(0.);
{
// Compute and update y-component of bin velocities.
let row_below = density_current.slice(s![.., 0..num_bin_y-2]);
let row_center = density_current.slice(s![.., 1..num_bin_y-1]);
let row_above = density_current.slice(s![.., 2..]);
// TODO: Compute this without allocation.
let new_bin_velocity_y = (&row_below - &row_above) / row_center * 0.5;
bin_velocity_y.slice_mut(s![.., 1..num_bin_y-1])
.assign(&new_bin_velocity_y);
}
{
// Compute and update x-component of bin velocities.
let col_left = density_current.slice(s![0..num_bin_x-2, ..]);
let col_center = density_current.slice(s![1..num_bin_x-1, ..]);
let col_right = density_current.slice(s![2.., ..]);
// TODO: Compute this without allocation.
let new_bin_velocity_x = (&col_left - &col_right) / col_center * 0.5;
bin_velocity_x.slice_mut(s![1..num_bin_x-1, ..])
.assign(&new_bin_velocity_x);
}
// Find largest bin speed to get an estimate for the time step.
let largest_bin_speed: f64 = bin_velocity_x.iter().zip(bin_velocity_y.iter())
.map(|(&vx, &vy)| vx.hypot(vy))
.fold(0., |vmax, v| vmax.max(v));
// Sanity checks: Speed must be larger than zero,
// otherwise the loop should have been stopped already.
debug_assert!(largest_bin_speed.is_normal());
debug_assert!(largest_bin_speed > 0.);
// TODO: Choose time step adaptively.
// Make sure the fastest cell does not move more than
// a fraction of the bin size per iteration.
// Speed is normalized to the bin size.
let f = 0.5; // Move not more than half the bin size per iteration.
let delta_time = (1. / largest_bin_speed).min(1.) * f;
// debug!("time step: {}", delta_time);
// let delta_time = 0.5;
// Compute the new locations of the cells based on the interpolated velocities.
// Compute the interpolated velocity at a certain position.
let cell_velocity = |pos_x: f64, pos_y: f64| -> Vector<f64> {
let half_bin_size = bin_size / 2;
// Get indices of lower left bin.
let (i, j) = bin_indices(pos_x as Coord - bin_size / 2,
pos_y as Coord - bin_size / 2);
// Get coordinates of bin center.
let (bin_x, bin_y) = bin_center_location(i, j);
debug_assert!(pos_x >= bin_x as f64);
debug_assert!(pos_y >= bin_y as f64);
let offset_x = (pos_x - bin_x as f64) / (bin_size as f64);
let offset_y = (pos_y - bin_y as f64) / (bin_size as f64);
let vx = interpolate2d(
bin_velocity_x[[i, j]],
bin_velocity_x[[i + 1, j]],
bin_velocity_x[[i, j + 1]],
bin_velocity_x[[i + 1, j + 1]],
offset_x,
offset_y,
);
let vy = interpolate2d(
bin_velocity_y[[i, j]],
bin_velocity_y[[i + 1, j]],
bin_velocity_y[[i, j + 1]],
bin_velocity_y[[i + 1, j + 1]],
offset_x,
offset_y,
);
// Computed velocity was normalized to a bin size of 1, need to scale by true bin size.
Vector::new(vx, vy) * (bin_size as f64)
};
// Update cell positions.
instance_positions.iter_mut()
.zip(&cell_areas)
.for_each(|(p, &area)| {
*p += cell_velocity(p.x, p.y) * delta_time
});
// let interp_velocity_x = |cell_loc_x: f64| -> f64 {
//
// };
// Compute next densities.
{
// Compute vertical second derivative.
{
// Create slice to be updated (excluding the first and last row).
let mut vertical = density_next.slice_mut(s![.., 1..num_bin_y-1]);
let row_below = density_current.slice(s![.., 0..num_bin_y-2]);
let row_center = density_current.slice(s![.., 1..num_bin_y-1]);
let row_above = density_current.slice(s![.., 2..]);
let vertical_derivative = delta_time * 0.5 * (&row_above - &(2.0 * &row_center) + &row_below);
vertical += &vertical_derivative;
}
// Compute horizontal second derivative.
{
// Create slice to be updated (excluding the first and last row).
let mut horizontal = density_next.slice_mut(s![1..num_bin_x-1, ..]);
let col_left = density_current.slice(s![0..num_bin_x-2, ..]);
let col_center = density_current.slice(s![1..num_bin_x-1, ..]);
let col_right = density_current.slice(s![2.., ..]);
let horizontal_derivative = delta_time * 0.5 * (&col_left - &(2.0 * &col_center) + &col_right);
horizontal += &horizontal_derivative;
}
}
// The next densities become the current densities for the next iteration.
density_current.clone_from(&density_next);
}
// Assemble cell positions into required hash map format.
let output = all_instances.iter()
.zip(instance_positions)
.map(|(id, pos)| (id.clone(), pos.cast()))
.collect();
output
}
}