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.

404 lines
14 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/>.
*/
//! Electro-static standard-cell placer which uses the `argmin` crate for the optimization steps.
use argmin::prelude as am;
use argmin::solver::conjugategradient::ConjugateGradient;
use argmin::solver::conjugategradient::NonlinearConjugateGradient;
use argmin::solver::gradientdescent::SteepestDescent;
use argmin::solver::linesearch::HagerZhangLineSearch;
use argmin::solver::conjugategradient::PolakRibiere;
use argmin::solver::linesearch::MoreThuenteLineSearch;
use itertools::Itertools;
use super::types::*;
use super::nbody;
use super::spring_force;
use libreda_pnr::db;
use db::TryCastCoord;
pub use libreda_pnr::place::stdcell_placer::SimpleStdCellPlacer;
use std::rc::Rc;
use std::collections::{HashMap, HashSet};
use libreda_pnr::db::{SInt, UInt, NetlistBase};
use log::{debug, info, warn, error};
/// Alternative implementation of the electro static placement algorithm
/// using the `argmin` optimization crate.
#[derive(Clone)]
pub struct ElectronPlacerArgmin<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> ElectronPlacerArgmin<N> {
/// Create a default quadratic placer.
pub fn new() -> Self {
ElectronPlacerArgmin {
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 ElectronPlacerArgmin<N> {
fn name(&self) -> &str {
"ElectronPlacer (Argmin)"
}
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.");
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 components: Vec<_> = all_instances.iter()
.map(|inst| {
// Find all nets connected to this instance.
let nets = netlist.each_external_net(inst).unique();
// Convert to nets as needed by the placer.
let nets: Vec<_> = nets
.map(|net| *net_map.get(&net).unwrap())
.collect();
// Get the initial location.
let initial_location = initial_positions.get(inst).copied();
let fixed_location = fixed_instances.contains(inst);
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))
.map(|r| (r.width() as f64, r.height() as f64))
.unwrap_or_else(|| {
warn!("No dimension defined for cell '{:?}'.", netlist.cell_instance_name(inst));
(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();
debug!("Run placer.");
let positions = place(&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(components: &Vec<Component>, repulsion: f64, max_iter: u64) -> Vec<Vec2D> {
assert!(repulsion >= 0.0 && repulsion <= 1.0);
let default_location = Vec2D::zero();
// 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.
let set = component_indices_by_net.get_mut(&net);
if let Some(v) = set {
// Push to existing vector.
v.push(i);
} else {
// Create new vector.
component_indices_by_net.insert(net, vec!(i));
}
}
}
component_indices_by_net
};
// Find initial locations.
let initial_locations: Vec<Vec2D> = components.iter().map(|c|
{
let loc = c.location.unwrap_or(default_location);
loc
}
).collect();
struct OptimizationProblem {
components: Vec<Component>,
/// Balance between spring forces and electro-static force.
repulsion: FloatType,
/// Trade-off accuracy and efficiency of quad-tree.
quad_tree_threshold: f64,
/// For each net the components connected to it.
component_indices_by_net: HashMap<Net, Vec<usize>>,
}
impl OptimizationProblem {
/// Compute spring forces and electro-static forces.
/// * `locations`: Positions of the particles to be placed.
fn compute_forces(&self, locations: &Vec<Vec2D>) -> Vec<Cost> {
let particles: Vec<Particle> = self.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 = self.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 repulsion = self.repulsion;
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, self.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
};
total_forces
}
}
/// Convert (x,y) vectors into a flat vector of floats
/// by interleaving x and y coordinates.
fn vector2floats(vec: &Vec<Vec2D>) -> Vec<f64> {
let mut out = Vec::new();
out.reserve(vec.len() * 2);
for v in vec {
out.push(v.x);
out.push(v.y);
}
out
}
/// Inverse of `vector2float1`.
fn floats2vector(floats: &Vec<f64>) -> Vec<Vec2D> {
let mut out = Vec::new();
out.reserve(floats.len() / 2);
for i in 0..floats.len() / 2 {
let x = floats[2 * i];
let y = floats[2 * i + 1];
out.push((x, y).into());
}
out
}
impl am::ArgminOp for OptimizationProblem {
type Param = Vec<f64>;
type Output = f64;
type Hessian = ();
type Jacobian = ();
type Float = f64;
fn apply(&self, param: &Self::Param) -> Result<Self::Output, am::Error> {
let locations = floats2vector(param);
// Expensive computation.
let cost = self.compute_forces(&locations);
let cost_sum = cost.iter()
.map(|c| c.cost)
.sum();
Ok(cost_sum)
}
fn gradient(&self, param: &Self::Param) -> Result<Self::Param, am::Error> {
let locations = floats2vector(param);
// Expensive computation.
let cost = self.compute_forces(&locations);
let gradient = cost.iter()
.map(|c| -c.gradient)
.collect();
let gradient = vector2floats(&gradient);
Ok(gradient)
}
}
let operator = OptimizationProblem {
components: components.clone(),
repulsion: repulsion,
quad_tree_threshold: quad_tree_threshold,
component_indices_by_net: component_indices_by_net,
};
// Define initial values.
let init_param: Vec<f64> = vector2floats(&initial_locations);
// // Set up line search.
// let linesearch = MoreThuenteLineSearch::new();
// let beta_method = PolakRibiere::new();
//
// // See: https://github.com/argmin-rs/argmin/blob/master/examples/nonlinear_cg.rs
// // Set up nonlinear conjugate gradient method.
// let solver = NonlinearConjugateGradient::new(linesearch, beta_method)
// .unwrap()
// // Set the number of iterations when a restart should be performed
// // This allows the algorithm to "forget" previous information which may not be helpful anymore.
// .restart_iters(10)
// // Set the value for the orthogonality measure.
// // Setting this parameter leads to a restart of the algorithm (setting beta = 0) after two
// // consecutive search directions are not orthogonal anymore. In other words, if this condition
// // is met:
// //
// // `|\nabla f_k^T * \nabla f_{k-1}| / | \nabla f_k ||^2 >= v`
// //
// // A typical value for `v` is 0.1.
// .restart_orthogonality(0.1);
let linesearch = MoreThuenteLineSearch::new();
// Set up solver
let solver = SteepestDescent::new(linesearch);
// Run solver
let res = am::Executor::new(operator, solver, init_param)
.add_observer(am::ArgminSlogLogger::term(), am::ObserverMode::Always)
.max_iters(max_iter)
// Set target cost function value
.target_cost(0.0)
.run().unwrap();
let best = res.state.best_param;
let best_locations = floats2vector(&best);
// dbg!(&best_locations);
best_locations
}