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.

354 lines
13 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/>.
*/
//! Standard-cell placement based on the simulation of the movement of electrical charges.
use itertools::Itertools;
use super::types::*;
use super::nbody;
use super::spring_force;
use libreda_pnr::db;
use db::{TryCastCoord, TryBoundingBox, ToPolygon};
pub use libreda_pnr::place::stdcell_placer::SimpleStdCellPlacer;
use std::rc::Rc;
use std::collections::{HashMap, HashSet};
use libreda_pnr::db::{REdge, SInt, UInt, NetlistBase};
use log::{debug, info, warn, error};
use std::convert::TryFrom;
/// Standard-cell placer that simulates the cells as electrically charged particles
/// which are connected by springs according to their connectivity.
///
/// This placer works best with a decent initial placement such as the one from
/// the quadratic placer.
#[derive(Clone)]
pub struct ElectronPlacer<N: NetlistBase> {
/// Maximum number of iterations.
max_iter: u64,
/// Strength of the electro static repulsion.
repulsion: f64,
/// Dimensions of the cells to be used.
cell_dimensions: Option<HashMap<N::CellId, db::Rect<db::Coord>>>,
}
impl<N: NetlistBase> ElectronPlacer<N> {
/// Create a default quadratic placer.
pub fn new() -> Self {
ElectronPlacer {
max_iter: 100,
repulsion: 0.5,
cell_dimensions: None,
}
}
/// Set the maximum number of iterations.
pub fn max_iter(mut self, max_iter: u64) -> Self {
self.max_iter = max_iter;
self
}
/// Set the balance between spring forces and electro-static repulsion.
/// Values from 0.0 - 1.0 are accepted.
pub fn repulsion(mut self, repulsion: f64) -> Self {
assert!(0.0 <= repulsion && repulsion <= 1.0);
self.repulsion = repulsion;
self
}
}
impl<N: NetlistBase> SimpleStdCellPlacer<N> for ElectronPlacer<N> {
fn name(&self) -> &str {
"ElectronPlacer"
}
fn set_cell_dimensions(&mut self, cell_dimensions: HashMap<N::CellId, db::Rect<db::Coord>>) {
self.cell_dimensions = Some(cell_dimensions)
}
fn find_cell_positions_impl(&self,
netlist: &N,
circuit: &N::CellId,
core_area: &db::SimplePolygon<db::SInt>,
initial_positions: &HashMap<N::CellInstId, db::Point<db::SInt>>,
fixed_instances: &HashSet<N::CellInstId>,
) -> HashMap<N::CellInstId, db::Point<i32>> {
info!("Run electro-static placement.");
// Check that the core area is a rectangle and convert it to a rectangle.
let core_area_bbox = core_area.try_bounding_box().unwrap();
let core_area_poly = core_area_bbox.to_polygon().exterior;
if &core_area_poly != core_area {
let msg = "Shapes other than rectangles are not yet supported as core area.";
error!("{}", msg);
panic!("{}", msg);
}
let core_area = core_area_bbox.cast();
if self.cell_dimensions.is_none() {
error!("This placer needs to know cell dimensions. Call `set_cell_dimensions()` first.");
panic!("Cell dimensions are not set.")
}
let cell_dimensions = self.cell_dimensions.as_ref().unwrap();
// // Get positions for all fixed instances.
// let fixed_positions = fixed_instances.iter()
// .map(|&i| (i, initial_positions[&i]))
// .collect();
debug!("Prepare netlist for placer.");
// Create nets as needed by the placer.
let net_map: HashMap<_, _> = netlist.each_internal_net(circuit)
.enumerate()
.map(|(i, net)| (
net,
super::types::Net(i)
))
.collect();
// Create components (equivalent to cells) as needed by the placer.
let all_instances: Vec<_> = netlist.each_cell_instance_vec(circuit);
// Create components (cells/electrons).
let mut cells_without_dimension = HashSet::new(); // Keep track of cells that don't have a dimension defined.
let components: Vec<_> = all_instances.iter()
.map(|inst_id| {
// Find all nets connected to this instance.
let nets: Vec<_> = netlist.each_external_net(inst_id)
.unique()
.collect();
// Convert to nets as needed by the placer.
let nets: Vec<_> = nets.iter()
.map(|net| *net_map.get(net).unwrap())
.collect();
// Get the initial location.
let initial_location = initial_positions.get(inst_id).copied();
let fixed_location = fixed_instances.contains(inst_id);
if fixed_location {
assert!(initial_location.is_some(), "Location is not provided for fixed instance.");
}
// Find cell dimension (width x height).
let cell_dim = cell_dimensions.get(&netlist.template_cell(inst_id))
.map(|r| (r.width() as f64, r.height() as f64))
.unwrap_or_else(|| {
cells_without_dimension.insert(netlist.template_cell(inst_id));
(1.0, 1.0)
});
let component = Component {
nets: nets,
size: cell_dim,
location: initial_location.map(|p| p.v().cast()),
fixed_location: fixed_location,
};
component
}).collect();
// Warn about cells that don't have an abutment box defined.
if !cells_without_dimension.is_empty() {
log::warn!("Number of cells without defined dimensions: {}", cells_without_dimension.len());
log::warn!("Cells without defined dimensions: {}",
cells_without_dimension.iter().map(|c| netlist.cell_name(c)).join(", "));
}
debug!("Run placer.");
debug!("Core area: {:?}", &core_area);
let positions = place(
core_area,
&components,
self.repulsion,
self.max_iter);
debug!("Placer finished.");
assert_eq!(positions.len(), all_instances.len());
debug!("Convert positions into output format.");
// Convert positions in desired format.
let result = positions.iter().zip(all_instances)
.map(|(p, inst)| (inst, db::Point::from(p).cast()))
.collect();
debug!("Done.");
result
}
}
/// Perform placement by simulating electrostatic repulsion and
/// attraction by springs of connected components.
fn place(
core_area: db::Rect<FloatType>,
components: &Vec<Component>,
repulsion: f64,
num_iterations: u64) -> Vec<Vec2D> {
assert!(repulsion >= 0.0 && repulsion <= 1.0);
// Make sure the position vector is inside the core area.
// Points outside of the core area are projected on the boundary of the core area.
let clip_to_core_area = |pos: Vec2D| -> Vec2D {
let x = pos.x.max(core_area.lower_left().x)
.min(core_area.upper_right().x);
let y = pos.y.max(core_area.lower_left().y)
.min(core_area.upper_right().y);
Vector::new(x, y)
};
// Compute center of weight of all fixed components.
let center_of_weight: Vec2D = components.iter()
.filter(|c| c.fixed_location)
.filter_map(|c| c.location)
.sum();
let default_location = center_of_weight;
// Precision of n-body simulation.
let quad_tree_threshold = 0.5;
// For each net find all components that are connected to it.
let component_indices_by_net =
{
let mut component_indices_by_net: HashMap<Net, Vec<usize>> = HashMap::new();
// Loop over all components...
for (i, c) in components.iter().enumerate() {
// ... loop over all nets of a component
for &net in &c.nets {
// ... add the component to the set of components of this net.
component_indices_by_net.entry(net)
.or_insert(vec![])
.push(i);
}
}
component_indices_by_net
};
// Find initial locations.
let locations = components.iter().map(|c|
{
let loc = c.location.unwrap_or(default_location);
loc
}
).collect();
// Create closure for performing one placement step based on initial locations.
let placement_step = |locations: Vec<Vec2D>| -> Vec<Vec2D> {
debug_assert_eq!(locations.len(), components.len());
let particles: Vec<Particle> = components.iter()
.zip(&locations)
.map(|(comp, loc)| {
let charge = comp.size.0 * comp.size.1;
Particle::new(loc, charge)
})
.collect();
// Calculate total spring force for each component.
let spring_forces = {
// Allocate zero vectors.
let mut spring_forces = vec![Cost::zero(); particles.len()];
// Calculate spring forces for each net.
let indexed_forces = component_indices_by_net.iter().flat_map(|(_net, component_indices)| {
let locations = component_indices.iter().map(|&i|
locations[i]).collect();
let forces = spring_force::calculate_spring_forces(&locations);
let indexed_forces = component_indices.iter().zip(forces);
indexed_forces
});
// Accumulate spring forces of different nets for each component.
for (&component_index, force) in indexed_forces {
spring_forces[component_index] += force;
}
spring_forces
};
let total_forces: Vec<Cost> = if repulsion == 0.0 {
spring_forces
} else {
// Calculate total electric force for each component.
let electric_forces =
nbody::calculate_electric_forces(&particles, quad_tree_threshold);
// Add electric force and spring force.
let total_forces: Vec<Cost> = electric_forces.iter()
.zip(spring_forces)
.map(|(&fe, fs)|
fe * repulsion + fs * (1. - repulsion) // Add forces.
).collect();
total_forces
};
// Get absolute value of maximum force.
let max_gradient = total_forces.iter()
.map(|f| f.gradient.norm2_squared()) // Calculate absolute values.
.fold(0., |acc, x| if x > acc { x } else { acc }) // Find maximum.
.sqrt();
let max_hessian_abs = total_forces.iter()
.map(|f| f.hessian.0.norm2_squared() + f.hessian.1.norm2_squared()) // Calculate absolute values.
.fold(0., |acc, x| if x > acc { x } else { acc }) // Find maximum.
.sqrt();
// TODO: calculate this by the derivative of the force (hessian).
// let step = 1. / max_gradient * 1000.0;
let step = 1. / max_gradient * 10000.0;
// dbg!(max_gradient);
// dbg!(max_hessian_abs);
// // let step = 1. / max_hessian_abs * 1.0;
// dbg!(step);
let total_cost: FloatType = total_forces.iter()
.map(|f| f.cost)
.sum();
// dbg!(total_cost);
// Update locations.
let new_locations = locations.iter()
.zip(total_forces).zip(components)
.map(|((&loc, force), component)|
if component.fixed_location {
loc
} else {
loc + force.gradient * step
}
)
.map(clip_to_core_area) // Make sure the new locations are inside the core.
.collect();
new_locations
};
// Do placement iterations.
(0..num_iterations).fold(locations, |old_locations, _i|
placement_step(old_locations),
)
}