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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161

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

//! Representation of routing problems

use libreda_db::prelude as db;
use std::collections::HashMap;

// pub trait RoutingDesignRules<C: db::L2NBase> {
//
//     /// Metal routing layers, starting from the one closest to silicon.
//     fn routing_layers(&self) -> Vec<C::LayerId>;
//
//     /// Via routing layers.
//     fn via_layers(&self) -> Vec<C::LayerId>;
//
// }

/// Representation of the routing problem.
///
/// This excludes information directly related to the technology such as design rules.
pub trait RoutingProblem<C: db::L2NBase> {
    /// Get the base layout/netlist structure.
    fn fused_layout_netlist(&self) -> &C;

    /// Get the top cell whose content should be placed.
    fn top_cell(&self) -> C::CellId;

    /// Return the nets which should be routed.
    fn nets(&self) -> Box<dyn Iterator<Item=C::NetId> + '_>;

    /// Get the weight of a net. Default is `1.0`.
    /// When optimizing the wire-length, the *weighted* wire-length should be used.
    /// For example a weight `0.0` means that the net should not be considered for wire-length optimization.
    /// Place and route algorithms may or may not use the net weight.
    fn net_weight(&self, _net: &C::NetId) -> f64 {
        1.0
    }

    /// Weight of an 'arc', i.e. a net segment which starts at `signal_source` and ends at `signal_destination.
    /// Default weight is `1.0`.
    /// Place and route algorithms may or may not use the arc weight.
    fn arc_weight(&self, _signal_source: &db::TerminalId<C>, _signal_destination: &db::TerminalId<C>) -> f64 {
        1.0
    }

    /// Shapes where routes should not pass.
    fn blockages(&self) -> Box<dyn Iterator<Item=(C::LayerId, db::SimpleRPolygon<C::Coord>)>> {
        Box::new(std::iter::empty())
    }

    /// Routes must remain within this boundary.
    fn boundary(&self) -> Option<db::SimpleRPolygon<C::Coord>>;
}

/// Inputs for global routing algorithms.
pub trait GlobalRoutingProblem<C: db::L2NBase>: RoutingProblem<C> {}

/// Inputs for detail routing algorithms.
pub trait DetailRoutingProblem<C: db::L2NBase>: RoutingProblem<C> {
    /// Representation of a global route which guides a single net.
    type RoutingGuide: RoutingGuide<C>;

    /// Get the routing guide for this net.
    fn routing_guide(&self, net: &C::NetId) -> Option<&Self::RoutingGuide>;
}

/// Routing guide for a single net.
pub trait RoutingGuide<C: db::L2NBase> {
    /// Test if a point on a layer is included in the routing guide.
    fn contains_point(&self, layer: &C::LayerId, p: db::Point<C::Coord>) -> bool;

    /// Represent the routing guide as a collection of rectangles.
    fn to_rectangles(&self) -> Vec<(db::Rect<C::Coord>, C::LayerId)>;
}


/// Simple representation of the global and detail routing problems.
/// Implements the `RoutingProblem` traits.
#[derive(Clone)]
pub struct SimpleRoutingProblem<'a, LN, RoutingGuide = ()>
    where LN: db::L2NBase {
    /// A fused layout-netlist structure.
    pub chip: &'a LN,
    /// The ID of the top cell to be routed.
    pub top_cell: LN::CellId,
    /// The IDs of the nets to be routed.
    pub nets: Vec<LN::NetId>,
    /// Weights of nets for optimizing the total wire-length.
    /// Default weight is `1.0`. A net with weight `0.0` will not be optimized for length
    /// while a net with a high weight will be optimized for wiring length much more aggressively.
    pub net_weights: HashMap<LN::NetId, f64>,
    /// All routes should be contained within this boundary, if it is specified.
    pub boundary: Option<db::SimpleRPolygon<LN::Coord>>,
    /// Global routes.
    pub routing_guides: HashMap<LN::NetId, RoutingGuide>,
}

impl<'a, LN: db::L2NBase, RG> SimpleRoutingProblem<'a, LN, RG> {
    /// Create a new routing problem. By default, no nets are included.
    /// Nets which should be routed need to be added to the `nets` field.
    pub fn new(chip: &'a LN, top_cell: LN::CellId) -> Self {
        Self {
            chip,
            top_cell,
            nets: Default::default(),
            net_weights: Default::default(),
            boundary: Default::default(),
            routing_guides: Default::default(),
        }
    }

    /// Set global routes.
    pub fn with_routing_guides(mut self, routing_guides: HashMap<LN::NetId, RG>) -> Self {
        self.routing_guides = routing_guides;
        self
    }
}

impl<'a, LN, RG> RoutingProblem<LN> for SimpleRoutingProblem<'a, LN, RG>
    where LN: db::L2NBase {
    fn fused_layout_netlist(&self) -> &LN {
        self.chip
    }

    fn top_cell(&self) -> LN::CellId {
        self.top_cell.clone()
    }

    fn nets(&self) -> Box<dyn Iterator<Item=LN::NetId> + '_> {
        Box::new(self.nets.iter().cloned())
    }

    fn net_weight(&self, net: &LN::NetId) -> f64 {
        self.net_weights.get(net)
            .copied()
            .unwrap_or(1.0)
    }

    fn blockages(&self) -> Box<dyn Iterator<Item=(LN::LayerId, db::SimpleRPolygon<LN::Coord>)>> {
        Box::new(std::iter::empty())
    }

    fn boundary(&self) -> Option<db::SimpleRPolygon<LN::Coord>> {
        self.boundary.clone()
    }
}

impl<'a, LN: db::L2NBase, RG> GlobalRoutingProblem<LN> for SimpleRoutingProblem<'a, LN, RG> {}


impl<'a, LN: db::L2NBase, RG> DetailRoutingProblem<LN> for SimpleRoutingProblem<'a, LN, RG>
    where RG: RoutingGuide<LN> {
    type RoutingGuide = RG;

    fn routing_guide(&self, net: &LN::NetId) -> Option<&Self::RoutingGuide> {
        self.routing_guides.get(net)
    }
}