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
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
// Copyright (c) 2020-2021 Thomas Kramer.
// SPDX-FileCopyrightText: 2022 Thomas Kramer <code@tkramer.ch>
//
// SPDX-License-Identifier: AGPL-3.0-or-later

//! Tools for inserting tie-cells to drive constant nets.


use crate::db;
use db::traits::*;
use db::{Direction, CoordinateType, TerminalId};

use num_traits::{PrimInt, NumCast};

/// Insert tie cells and connect unconnected LOW and HIGH nets.
///
/// Tie-cells are placed such that the maximal manhattan distance
/// to the sinks is kept below `max_distance`.
#[derive(Debug, Clone)]
pub struct SimpleTieCellInsertionEngine {

    /// Name of the tie-low cell to be used for buffering constant LOW nets.
    pub tie_cell_low: String,
    /// Name of the tie-high cell to be used for buffering constant HIGH nets.
    pub tie_cell_high: String,
    /// Maximal number of cells that should be driven by a tie-cell cell.
    /// Must be larger than `1`.
    pub max_fanout: u32,
    /// Maximal manhattan distance from the tie-cell to the attached sink.
    pub max_distance: db::Coord,
}


impl SimpleTieCellInsertionEngine {

    /// Insert tie cells to drive the sinks which are attached to this net.
    /// The net must be either the constant LOW or HIGH net.
    ///
    /// A tie cell is usually used to drive a cluster of many inputs. The way the
    /// clusters are formed depends on the locations of the inputs such that the wiring
    /// can be minimized from tie-cells to inputs but also the additional space required by tie-cells
    /// is reasonable (instead of placing a tie-cell for every input).
    pub fn insert_tie_cells_on_net<LN: NetlistEdit + LayoutEdit>(
        &self,
        chip: &mut LN,
        net: &LN::NetId,
    ) -> Result<(Vec<LN::CellInstId>, Vec<LN::NetId>), ()>
        where LN::Coord: PrimInt {
        // Check if the net is a special net (LOW or HIGH).
        if !chip.is_constant_net(&net) {
            let parent_name = chip.cell_name(&chip.parent_cell_of_net(&net));
            log::warn!("Net '{:?}' in '{}' is neither a constant LOW nor HIGH net.", &net, parent_name);
        }

        // Find the sinks of the net.
        let mut sinks = vec![];

        for t in chip.each_terminal_of_net(&net) {
            // A pin of the parent cell is considered to be a source when it's direction is 'INPUT',
            // however a pin instance that connects to a child instance is considered a sink when it's direction is 'INPUT'.
            match &t {
                TerminalId::PinId(p) => {
                    match chip.pin_direction(p) {
                        Direction::Output => sinks.push(t),
                        d => {
                            let cell_name = chip.cell_name(&chip.parent_cell_of_pin(&p));
                            let pin_name = chip.pin_name(p);
                            panic!("Cannot handle pin direction of pin '{}' in cell '{}': {:?} (must be an output)", pin_name, cell_name, d)
                        }
                    }
                }
                TerminalId::PinInstId(p) => {
                    match chip.pin_direction(&chip.template_pin(p)) {
                        Direction::Input => sinks.push(t),
                        d => {
                            let pin = chip.template_pin(p);
                            let cell_name = chip.cell_name(&chip.parent_cell_of_pin(&pin));
                            let pin_name = chip.pin_name(&pin);
                            panic!("Cannot handle pin direction of pin '{}' in cell '{}': {:?} (must be an input)", pin_name, cell_name, d)
                        }
                    }
                }
            }
        }

        log::debug!("Number of sinks: {}", sinks.len());

        self.insert_tie_cells(chip, &sinks)
    }

    /// All terminals must be in the same parent cell.
    /// Returns a vector of all added tie-cell instances and all added nets.
    fn insert_tie_cells<LN: NetlistEdit + LayoutEdit>(
        &self,
        chip: &mut LN,
        signal_sinks: &Vec<TerminalId<LN>>,
    ) -> Result<(Vec<LN::CellInstId>, Vec<LN::NetId>), ()>
        where LN::Coord: PrimInt {
        log::debug!("Insert tie-cells for {} sinks.", signal_sinks.len());

        // Store all nets and cells that are added in this step and return them later.
        let mut added_tie_cells = vec![];
        let mut added_nets = vec![];

        if signal_sinks.is_empty() {
            return Ok((added_tie_cells, added_nets));
        }


        let parent_cell = match &signal_sinks[0] {
            TerminalId::PinId(p) => chip.parent_cell_of_pin(p),
            TerminalId::PinInstId(p) => chip.parent_cell(&chip.parent_of_pin_instance(p))
        };


        // Sanity check: The source and all sinks must be connected to the same net.
        let source_net = chip.net_of_terminal(&signal_sinks[0]);
        if source_net.is_none() {
            log::error!("Sink terminal is not connected to any net.");
            // TODO: Pass a `Result::Err` instead o panicking?
            panic!("Source terminal is not connected to any net.");
        }

        {
            let is_connected_to_correct_nets = signal_sinks.iter()
                .all(|sink| chip.net_of_terminal(sink) == source_net);
            if !is_connected_to_correct_nets {
                log::error!("Sinks are not all connected to the same net as the source.");
                panic!("Sinks are not all connected to the same net as the source.");
            }
        }

        let source_net = source_net.unwrap();
        assert!(chip.is_constant_net(&source_net), "Net must be either constant LOW or HIGH for tie-cell insertion.");

        let net_value = source_net == chip.net_one(&parent_cell);
        let tie_cell_name = if net_value {
            &self.tie_cell_high
        } else {
            &self.tie_cell_low
        };
        // Find tie-cell cell to be used.
        log::info!("Use tie-cell '{}'.", &tie_cell_name);
        let tie_cell = chip.cell_by_name(tie_cell_name)
            .expect("Tie-cell not found.");


        // Detect inputs and the outputs of the tie-cell cell.
        let inputs: Vec<_> = chip.each_pin(&tie_cell)
            .filter(|pin| chip.pin_direction(&pin).is_input())
            .collect();
        assert_eq!(inputs.len(), 0, "Tie-cell must have no input pins.");

        let outputs: Vec<_> = chip.each_pin(&tie_cell)
            .filter(|pin| chip.pin_direction(&pin).is_output())
            .collect();
        assert_eq!(outputs.len(), 1, "Tie-cell must have exactly one output pin.");

        let tie_cell_output = outputs[0].clone();

        // Find locations of terminals.
        let terminal_location = |t: &TerminalId<LN>| {
            match t {
                TerminalId::PinId(_t) => {
                    // TODO: Find the location of the pin shape.
                    db::Point::zero()
                }
                TerminalId::PinInstId(t) => {
                    let inst = chip.parent_of_pin_instance(t);
                    let tf = chip.get_transform(&inst);
                    // Assume that the physical pin is close to the origin of the cell.
                    // This is good enough only for small standard-cells, not for big macro blocks.
                    let location = tf.transform_point(db::Point::zero());
                    location
                }
            }
        };

        // Build clusters that are driven by the same tie-cell.
        let clusters = {
            // Find sink locations.
            let sink_locations: Vec<_> = signal_sinks.iter()
                .map(terminal_location)
                .collect();

            // Find clusters.
            let (cluster_ids, num_clusters) = find_clusters(
                &sink_locations,
                self.max_fanout,
                NumCast::from(self.max_distance).unwrap());

            // Create a nested list of terminals for each cluster.
            let mut clusters = vec![vec![]; num_clusters as usize];
            for (i, cluster_id) in cluster_ids.iter().enumerate() {
                clusters[*cluster_id as usize].push((signal_sinks[i].clone(), sink_locations[i]));
            }
            clusters
        };

        // Create a tie-cell for each cluster.
        let mut name_counter = 0; // Counter for unique names of tie-cell instances.
        for cluster in clusters {
            let (sinks, positions): (Vec<_>, Vec<_>) = cluster.into_iter().unzip();
            let center = center_of_mass(&positions);

            // Create name for the tie-cell instance.
            let instance_name = loop {
                let name = format!("_tie_cell_{}", name_counter);
                name_counter += 1;
                if chip.cell_instance_by_name(&parent_cell, &name).is_none() {
                    break name;
                }
            };

            let tie_cell_inst = chip.create_cell_instance(&parent_cell, &tie_cell, Some(instance_name.into()));
            // Create output net.
            let new_net = chip.create_net(&parent_cell, None);

            // Connect output of the tie-cell to the buffered net.
            let tie_cell_output_pin = chip.pin_instance(&tie_cell_inst, &tie_cell_output);
            chip.connect_pin_instance(&tie_cell_output_pin, Some(new_net.clone()));

            // Set the location of the tie-cell.
            chip.set_transform(&tie_cell_inst, db::SimpleTransform::translate(center));

            // Connect the sinks to the tie_cell output.
            for sink in &sinks {
                let old_net = chip.connect_terminal(sink, Some(new_net.clone()));
                debug_assert_eq!(old_net.as_ref(), Some(&source_net), "Sink is expected to be connected to the source net.");
            }

            added_tie_cells.push(tie_cell_inst);
            added_nets.push(new_net);

        }
        Ok((added_tie_cells, added_nets))
    }
}


/// Group points together to clusters and return a vector with the cluster ID for each point and the number of clusters.
/// The clusters are formed as follows:
/// 1) Sort the points by (x, y).
/// 2) As long as there's an unassigned point: take the next unassigned point `p` and put it into the new cluster `c`.
/// 3) Take the closest point to the center of the bounding-box around `c`. If adding `p` to `c` does not enlarge the bounding box
/// around `c` beyond `max_cluster_span` then add `p` to `c` and repeat 3) otherwise go to 2).
///
/// * `max_cluster_size`: Maximal number of points in cluster.
/// * `max_cluster_span`: Maximal width and height of the bounding box around the cluster.
fn find_clusters<C: CoordinateType + PrimInt>(points: &Vec<db::Point<C>>,
                                              max_cluster_size: u32,
                                              max_cluster_span: C) -> (Vec<u32>, u32) {
    // For each point store the original index and the cluster ID.
    // The index used to map back to the original points after sorting.
    let mut points_with_cluster_id: Vec<(db::Point<_>, usize, u32)> = points.iter()
        .enumerate()
        .map(|(idx, p)| (*p, idx, 0))
        .collect();
    // Sort by locations.
    points_with_cluster_id.sort_by_key(|(p, _, _)| (p.x, p.y));

    let mut cluster_id = 0u32;
    // While there is a point that does not belong to a cluster
    // take the first one (sorted by x and y) and use it as a start
    // of the cluster.

    let mut current_cluster_points = vec![];

    // Find the first point without assigned cluster.
    while let Some((first_point_idx, _)) = points_with_cluster_id.iter()
        .enumerate()
        .find(|(_pos, (_, _, cluster))| *cluster == 0) {
        cluster_id += 1;

        // Assign the cluster ID.
        points_with_cluster_id[first_point_idx].2 = cluster_id;

        let start = points_with_cluster_id[first_point_idx].0;

        let mut bbox = db::Rect::new(start, start);

        current_cluster_points.clear();
        current_cluster_points.push(start);
        // Find closest neighbour.
        for _ in 1..max_cluster_size {

            // Compute center of mass of the cluster.
            let center = center_of_mass(&current_cluster_points);

            let closest = points_with_cluster_id.iter()
                .enumerate()
                .filter(|(_, (_, _, cluster))| *cluster == 0) // Take only unassigned sinks.
                .filter(|(_, (p, _, _))| {
                    let new_bbox = bbox.add_point(*p);
                    new_bbox.height() < max_cluster_span && new_bbox.width() < max_cluster_span
                })
                .min_by_key(|(_, (pos, _, _))| (center - *pos).norm1())
                .map(|(idx, _)| idx);

            if let Some(closest) = closest {
                points_with_cluster_id[closest].2 = cluster_id;
                let p = points_with_cluster_id[closest].0;
                current_cluster_points.push(p);
                // Update the cluster bounding box.
                bbox = bbox.add_point(p);
            } else {
                // No unassigned node found.
                break;
            }
        }
    }

    let num_clusters = cluster_id;

    let mut result = vec![0u32; points_with_cluster_id.len()];
    for (_p, index, cluster_id) in points_with_cluster_id {
        result[index] = cluster_id - 1; // `0` meant 'no cluster'
    }

    (result, num_clusters)
}

/// Compute the center of mass of a list of points.
fn center_of_mass<C: PrimInt>(points: &Vec<db::Point<C>>) -> db::Point<C> {
    // Sum up all points and divide by number of points.
    points.iter()
        .fold(db::Point::zero(), |a, b| a + b)
        / NumCast::from(points.len()).unwrap()
}