1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

// Copyright (c) 2020-2021 Thomas Kramer.
// SPDX-FileCopyrightText: 2022 Thomas Kramer <code@tkramer.ch>
//
// SPDX-License-Identifier: AGPL-3.0-or-later

//! Estimate wire lengths.
//!
//! # Example
//!
//! Get the wire length estimation of a cell without any net.
//! ```
//! use libreda_pnr::db;
//! use libreda_pnr::db::traits::*;
//! use libreda_pnr::metrics::wirelength_estimation;
//!
//! let mut chip = db::Chip::new();
//! let cell_top = chip.create_cell("TOP".to_string());
//!
//! let wire_length: i32 = wirelength_estimation::hpwl(&chip.cell_ref(&cell_top));
//! assert_eq!(wire_length, 0)
//! ```

use crate::db;
use crate::db::L2NBase;
use crate::db::reference_access::*;
use crate::db::traits::TryBoundingBox;
use num_traits::{Zero, One, Num, NumCast};

/// Compute the half-perimeter wire length estimation for the cell `top`.
/// Returns the sum of half-perimeters of each nets bounding box.
/// Respects the pin locations at sub cells (instead of just taking the sub cell location).
pub fn hpwl<C: L2NBase, L>(top: &CellRef<C>) -> L
    where C::Coord: NumCast,
          L: Num + NumCast + Zero {
    top.each_net()
        .map(|net| hpwl_for_net(&net))
        .map(|l| L::from(l).expect("Failed to cast HPLW of net to other datatype L."))
        .fold(Zero::zero(), |acc, x| acc + x)
}

/// Compute the half-perimeter wire length of a single net.
///
/// Returns the half perimeter of the bounding box around all pins connected to `net`.
pub fn hpwl_for_net<C: L2NBase>(net: &NetRef<C>) -> C::Coord {
    let bbox = net_bounding_box(&net);

    let hplw = if let Some(bbox) = bbox {
        bbox.width() + bbox.height()
    } else {
        C::Coord::zero()
    };
    debug_assert!(hplw >= C::Coord::zero(), "Half-perimeter wire length should not be negative.");
    hplw
}

/// Get the bounding box around all the pins connected to `net`.
/// `None` is returned when `net` is not connected to any pins or pin instances.
pub fn net_bounding_box<C: L2NBase>(net: &NetRef<C>) -> Option<db::Rect<C::Coord>> {
    let mut bbox: Option<db::Rect<_>> = None;
    let mut update_bbox = |p: db::Point<C::Coord>| {
        if let Some(bbox) = &mut bbox {
            *bbox = bbox.add_point(p);
        } else {
            bbox = Some(db::Rect::new(p, p));
        }
    };

    // Process all connected external pins.
    for pin in net.each_pin() {
        update_bbox(pin_location(&pin));
    }

    // Process all connected pin instances.
    for pin_inst in net.each_pin_instance() {
        update_bbox(pin_instance_location(&pin_inst));
    }

    bbox
}

/// Get an point-like approximation of a absolute pin instance location.
fn pin_instance_location<C: L2NBase>(pin_inst: &PinInstRef<C>) -> db::Point<C::Coord> {
    let pin = pin_inst.pin();
    let pin_loc = pin_location(&pin);
    let chip = pin.base();
    chip.get_transform(&pin_inst.cell_instance().id())
        .transform_point(pin_loc)
}

/// Get an point-like approximation of a pin location (relative to the cell).
/// If the pin has no shapes defined, return `(0, 0)`.
fn pin_location<C: L2NBase>(pin: &PinRef<C>) -> db::Point<C::Coord> {
    let chip = pin.base();

    // Compute the average location of the pin shapes.
    let mut sum: db::Point<C::Coord> = db::Point::zero();
    let mut count = C::Coord::zero();
    chip.shapes_of_pin(&pin.id())
        .filter_map(|shape_id| {
            chip.with_shape(&shape_id, |_layer, shape| {
                shape.try_bounding_box().map(|bbox| bbox.center())
            })
        })
        .for_each(|p| {
            sum = sum + p;
            count = count + C::Coord::one();
        });

    let avg = if count.is_zero() {
        sum
    } else {
        sum / count
    };
    avg
}

#[test]
fn test_hplw() {
    use crate::db;
    use crate::db::traits::*;

    let mut chip = db::Chip::new();
    let cell_top = chip.create_cell("TOP".to_string());
    let cell_sub = chip.create_cell("SUB".to_string());
    let pin_a = chip.create_pin(&cell_sub, "A".to_string(), db::Direction::Input);
    let net1 = chip.create_net(&cell_top, None);
    let inst1 = chip.create_cell_instance(&cell_top, &cell_sub, None);
    let inst2 = chip.create_cell_instance(&cell_top, &cell_sub, None);
    chip.set_transform(&inst1, db::SimpleTransform::translate(db::Vector::new(10, 10)));
    chip.set_transform(&inst2, db::SimpleTransform::translate(db::Vector::new(20, 20)));

    // Connect net to pins.
    chip.connect_pin_instance(&chip.pin_instance(&inst1, &pin_a), Some(net1.clone()));
    chip.connect_pin_instance(&chip.pin_instance(&inst2, &pin_a), Some(net1.clone()));


    let wire_length: i32 = hpwl(&chip.cell_ref(&cell_top));
    assert_eq!(wire_length, 10 + 10)
}