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.

149 lines
4.0 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/>.
*/
//! Data types used in this crate.
pub use libreda_pnr::db::{Vector, Zero};
use std::ops::{Add, AddAssign, Mul};
/// Floating point type used for the computations in this crate.
pub type FloatType = f64;
pub type Vec2D = Vector<FloatType>;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct Net(pub usize);
/// Simplified representation of a standard-cell.
#[derive(Debug, Clone, PartialEq)]
pub struct Component {
/// Nets to which the component is connected.
pub nets: Vec<Net>,
/// Width and height of the component.
pub size: (f64, f64),
/// Location of the component.
pub location: Option<Vec2D>,
/// Tell if the location of the component shall not be changed.
pub fixed_location: bool,
}
#[derive(Clone, Copy, PartialEq, Debug)]
pub struct Cost {
pub cost: FloatType,
pub gradient: Vec2D,
pub hessian: (Vec2D, Vec2D),
}
impl Cost {
pub fn zero() -> Self {
Cost {
cost: 0.,
gradient: Vec2D::zero(),
hessian: (Vec2D::zero(), Vec2D::zero()),
}
}
}
impl Add for Cost {
type Output = Self;
fn add(self, rhs: Self) -> Self {
Cost {
cost: self.cost + rhs.cost,
gradient: self.gradient + rhs.gradient,
hessian: {
let (x1, y1) = self.hessian;
let (x2, y2) = rhs.hessian;
(x1 + x2, y1 + y2)
},
}
}
}
impl AddAssign for Cost
{
fn add_assign(&mut self, rhs: Self) {
self.cost += rhs.cost;
self.gradient += rhs.gradient;
self.hessian.0 += rhs.hessian.0;
self.hessian.1 += rhs.hessian.1;
}
}
impl Mul<FloatType> for Cost {
type Output = Self;
fn mul(self, rhs: FloatType) -> Self {
Cost {
cost: self.cost * rhs,
gradient: self.gradient * rhs,
hessian: {
let (x1, y1) = self.hessian;
(x1 * rhs, y1 * rhs)
},
}
}
}
#[derive(Clone, Copy, PartialEq, Debug)]
pub struct Particle {
pub location: Vec2D,
pub charge: FloatType,
}
impl Particle {
/// Create a new Particle.
pub fn new<L: Into<Vec2D>>(location: L, charge: FloatType) -> Self {
Particle {
location: location.into(),
charge: charge.into(),
}
}
/// Calculate the force onto the particle `self` from the particle `other`.
/// Also calculates the derivative of the force.
pub fn force_from(&self, other: &Particle) -> Cost {
let l1 = self.location;
let l2 = other.location;
if l1 == l2 {
Cost::zero()
} else {
let dist = l1 - l2;
let dist_abs = dist.norm2();
let qq = self.charge * other.charge;
let energy = 1. / dist_abs * self.charge * other.charge;
// Calculate gradient of energy (electric force).
let f = (dist / dist_abs.powi(3)) * qq;
// Electric force derived by radius.
// let f_derivative = (dist / dist_abs.powi(4)) * -2.0 * qq;
let f_derivative = (f / dist_abs) * -2.0;
Cost {
cost: energy,
gradient: f,
hessian: (f_derivative, f_derivative),
}
}
}
}