steiner_tree/
lut.rs

1// SPDX-FileCopyrightText: 2022 Thomas Kramer <code@tkramer.ch>
2//
3// SPDX-License-Identifier: GPL-3.0-or-later
4
5//! Data structure of the lookup table.
6
7use super::hanan_grid::HananGridWithCoords;
8use super::marker_types::Canonical;
9use super::position_sequence::PositionSequence;
10use super::wirelength_vector::*;
11use super::HananCoord;
12use crate::point::Point;
13use crate::tree::Tree;
14use num_traits::{Num, PrimInt, Zero};
15use std::iter::Sum;
16use std::ops::Add;
17
18/// Lookup-table for nets of low degree.
19#[derive(Clone, Debug)]
20pub struct LookupTable {
21    /// Lookup tables for each degree of net.
22    pub(crate) sub_lut_by_degree: Vec<SubLookupTable>,
23}
24
25impl LookupTable {
26    /// Find a rectilinear steiner minimal tree which connects all pins.
27    /// Number of de-duplicated pins cannot be larger than the maximum supported number of pins of the
28    /// lookup table.
29    ///
30    /// Returns: (tree edges, tree weight).
31    pub fn rsmt_low_degree<T>(&self, mut pins: Vec<Point<T>>) -> (Vec<(Point<T>, Point<T>)>, T)
32    where
33        T: Ord + Copy + Num + Zero + Sum + std::fmt::Debug,
34    {
35        // Normalize pins.
36        pins.sort();
37        pins.dedup();
38
39        let num_pins = pins.len();
40
41        if num_pins <= 1 {
42            return (vec![], Zero::zero());
43        }
44
45        assert!(
46            pins.len() <= self.max_degree(),
47            "number of pins exceeds the supported maximal net degree"
48        );
49
50        let position_sequence = PositionSequence::from_points(&pins);
51        let group_index = position_sequence.group_index();
52
53        let sub_lut = self.get_sub_lut(num_pins);
54        debug_assert_eq!(sub_lut.values.len(), (1..num_pins + 1).product());
55
56        // Resolve eventual redirect to other group index.
57        let (powvs, transform) = sub_lut.resolve_group_index(group_index);
58
59        // Transform the points into the target group.
60        pins.iter_mut().for_each(|p| {
61            *p = transform.transform_point(*p);
62        });
63
64        // Find coordinates of Hanan grid lines.
65        let xs = {
66            let mut xs: Vec<_> = pins.iter().map(|p| p.x).collect();
67            xs.sort();
68            xs
69        };
70        let ys = {
71            let mut ys: Vec<_> = pins.iter().map(|p| p.y).collect();
72            ys.sort();
73            ys
74        };
75
76        // Evaluate POWVs, find the POWV which leads to shortest wirelength.
77        let best_powv_and_post = {
78            // Compute scalar product of wirelength vector and edge count vector.
79            let compute_wire_length = |powv: &WirelenghtVector| -> T {
80                let (h, v) = powv.hv_vectors();
81
82                // Compute distances between Hanan grid lines.
83                let edge_widths_horizontal = xs.windows(2).map(|w| w[1] - w[0]);
84                let edge_widths_vertical = ys.windows(2).map(|h| h[1] - h[0]);
85                debug_assert_eq!(h.len(), edge_widths_horizontal.len());
86                debug_assert_eq!(v.len(), edge_widths_vertical.len());
87
88                let wl_horiz: T = h
89                    .iter()
90                    .zip(edge_widths_horizontal)
91                    .map(|(count, w)| (0..*count).map(|_| w).sum())
92                    // .fold(Zero::zero(), |acc,x| acc+x); // sum
93                    .sum();
94
95                let wl_vert: T = v
96                    .iter()
97                    .zip(edge_widths_vertical)
98                    .map(|(count, w)| (0..*count).map(|_| w).sum())
99                    .sum();
100
101                wl_horiz + wl_vert
102            };
103
104            powvs
105                .into_iter()
106                .map(|powv| {
107                    (
108                        powv,
109                        compute_wire_length(&powv.potential_optimal_wirelength_vector),
110                    )
111                })
112                .min_by_key(|(_powv, wire_len)| *wire_len)
113        };
114
115        let (best_powv_and_post, wire_length) = best_powv_and_post.expect("no steiner tree found");
116
117        // Transform a point from the hanan grid with unit distances to the original grid.
118        let transform_point_to_original_grid =
119            |p: Point<HananCoord>| -> Point<T> { Point::new(xs[p.x as usize], ys[p.y as usize]) };
120
121        let tree_edges = best_powv_and_post
122            .potential_optimal_steiner_tree
123            .all_edges()
124            .map(|e| (e.start(), e.end())) // Remove zero-length edges.
125            .map(|(a, b)| {
126                (
127                    transform_point_to_original_grid(a),
128                    transform_point_to_original_grid(b),
129                )
130            });
131
132        // Transform back to original group.
133        let inverse_transform = transform.inverse();
134
135        let tree = tree_edges
136            .map(|(a, b)| {
137                (
138                    inverse_transform.transform_point(a),
139                    inverse_transform.transform_point(b),
140                )
141            })
142            .filter(|(a, b)| a != b)
143            .collect();
144
145        (tree, wire_length)
146    }
147
148    /// Get maximum number of pins which is supported by the lookup-table.
149    pub fn max_degree(&self) -> usize {
150        self.sub_lut_by_degree.len() + 1
151    }
152
153    /// Get the lookup-table for a net of degree `num_pins`.
154    pub fn get_sub_lut(&self, num_pins: usize) -> &SubLookupTable {
155        assert!(num_pins >= 2, "no LUT for less than 2 pins");
156        &self.sub_lut_by_degree[num_pins - 2]
157    }
158
159    /// Print number of POWVs and POSTs.
160    pub fn print_statistics(&self) {
161        for (degree, sub_lut) in self.sub_lut_by_degree.iter().enumerate() {
162            let degree = degree + 2;
163            let max_num_powvs = sub_lut
164                .values
165                .iter()
166                .filter_map(|v| match v {
167                    ValuesOrRedirect::Values(v) => Some(v.len()),
168                    ValuesOrRedirect::Redirect { .. } => None,
169                })
170                .max()
171                .unwrap_or(0);
172
173            let total_num_powvs: usize = sub_lut
174                .values
175                .iter()
176                .map(|v| match v {
177                    ValuesOrRedirect::Values(v) => v.len(),
178                    ValuesOrRedirect::Redirect { group_index, .. } => {
179                        match &sub_lut.values[*group_index] {
180                            ValuesOrRedirect::Values(v) => v.len(),
181                            _ => panic!("invalid double-redirect"),
182                        }
183                    }
184                })
185                .sum();
186            let average_num_pows = (total_num_powvs as f64) / (sub_lut.values.len() as f64);
187
188            println!(
189                "degree={}, max. number of POWVs = {}, avg. num. POWVs = {:.3}",
190                degree, max_num_powvs, average_num_pows
191            );
192        }
193    }
194}
195
196#[test]
197fn test_rsmt_low_degree() {
198    let lut = super::gen_lut::gen_full_lut(5);
199
200    // 3 points
201    let points = vec![(5, 0).into(), (0, 10).into(), (10, 10).into()];
202    let (rsmt, wl) = lut.rsmt_low_degree(points);
203    assert_eq!(rsmt.len(), 3);
204    assert_eq!(wl, 20);
205
206    // 4 points
207    let points = vec![(0, 0).into(), (2, 1).into(), (2, 4).into(), (4, 2).into()];
208    let (rsmt, wl) = lut.rsmt_low_degree(points);
209    assert_eq!(rsmt.len(), 5);
210    assert_eq!(wl, 8);
211
212    // 5 points (cross with a center)
213    let points = vec![
214        (10, 5).into(),
215        (5, 0).into(),
216        (5, 5).into(),
217        (0, 5).into(),
218        (5, 10).into(),
219    ];
220    let (rsmt, wl) = lut.rsmt_low_degree(points);
221    assert_eq!(rsmt.len(), 4);
222    assert_eq!(wl, 20);
223}
224
225/// Lookup-table for a single degree of nets.
226#[derive(Clone, Debug)]
227pub struct SubLookupTable {
228    /// Potential optimal wire-length vectors and trees, indexed by their 'group index'.
229    pub(crate) values: Vec<ValuesOrRedirect>,
230}
231
232impl SubLookupTable {
233    /// Get the POWVs and POSTs for a group index. Follow symlinks to other groups.
234    ///
235    /// Returns the vector of POWVs and POSTs plus the transform which must be applied to convert
236    /// the pins.
237    fn resolve_group_index(&self, group_index: usize) -> (&Vec<LutValue>, Transform) {
238        let lut_value = &self.values[group_index];
239
240        // Resolve eventual redirect to other group index.
241        match lut_value {
242            ValuesOrRedirect::Values(values) => (values, Transform::identity()),
243            &ValuesOrRedirect::Redirect {
244                group_index,
245                transform,
246            } => {
247                // Resolve redirection.
248                let values = match &self.values[group_index] {
249                    ValuesOrRedirect::Values(values) => values,
250                    _ => panic!("lookup-table contains nested redirects"),
251                };
252                (values, transform)
253            }
254        }
255    }
256}
257
258/// A pair of a wirelength vector with a tree.
259#[derive(Clone, Debug)]
260pub struct LutValue {
261    /// 'POWV'
262    pub(crate) potential_optimal_wirelength_vector: WirelenghtVector,
263    /// 'POST'
264    pub(crate) potential_optimal_steiner_tree: Tree<Canonical>,
265}
266
267/// Contains either the POWVs for a group or redirects to another group which is equivalent
268/// under rotations and/or mirroring transforms.
269#[derive(Debug, Clone)]
270pub enum ValuesOrRedirect {
271    /// Wirelength vectors and trees for this group.
272    Values(Vec<LutValue>),
273    /// Redirection to another equivalent group (under the given transformation).
274    Redirect {
275        /// Index of the redirect.
276        group_index: usize,
277        /// Transformation that needs to be applied to get from the current group to the redirect.
278        transform: Transform,
279    },
280}
281
282/// Geometrical transformation of pins and trees.
283/// Note: After applying the transformation, the points and trees must be shifted
284/// such that the lower left corner of the bounding box is on `(0, 0)`.
285#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
286pub struct Transform {
287    /// Mirror at y-axis.
288    mirror_x: bool,
289    /// Rotations by multiple of 90 degrees.
290    rotate: u8,
291}
292
293impl Transform {
294    /// Create a new transformation.
295    pub fn new(rotate: u8, mirror_x: bool) -> Self {
296        Self {
297            rotate: rotate % 4,
298            mirror_x,
299        }
300    }
301
302    /// Identity transform.
303    pub fn identity() -> Self {
304        Self::new(0, false)
305    }
306
307    /// Get the inverse transform.
308    pub fn inverse(&self) -> Self {
309        let r = if self.mirror_x {
310            self.rotate
311        } else {
312            4 - self.rotate
313        };
314        Self::new(r, self.mirror_x)
315    }
316
317    /// Apply the transform to a point.
318    pub fn transform_point<T>(&self, mut p: Point<T>) -> Point<T>
319    where
320        T: Copy + Num + Zero,
321    {
322        for _ in 0..self.rotate {
323            p.rotate_ccw90();
324        }
325
326        if self.mirror_x {
327            p.x = T::zero() - p.x;
328        }
329
330        p
331    }
332}
steiner_tree/lut.rs

steiner_tree/
lut.rs
