physdes/

dme_algorithm.rs

//! Deferred Merge Embedding (DME) algorithm for clock tree synthesis.
//!
//! Implements the DME algorithm for constructing zero-skew clock trees
//! with Manhattan geometry. Supports both linear and Elmore delay models.

use std::cell::RefCell;
use std::collections::HashMap;
use std::rc::Rc;

use crate::generic::MinDist;
use crate::interval::Interval;
use crate::manhattan_arc::ManhattanArc;
use crate::point::Point;

/// A clock sink with name, position, and capacitance.
#[derive(Debug, Clone)]
pub struct Sink {
    pub name: String,
    pub position: Point<i32, i32>,
    pub capacitance: f64,
}

impl Sink {
    pub fn new(name: &str, position: Point<i32, i32>, capacitance: f64) -> Self {
        Sink {
            name: name.to_string(),
            position,
            capacitance,
        }
    }
}

/// A node in the clock tree.
#[derive(Debug, Clone)]
pub struct TreeNode {
    pub name: String,
    pub position: Point<i32, i32>,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
    pub parent: Option<Rc<RefCell<TreeNode>>>,
    pub wire_length: i32,
    pub delay: f64,
    pub capacitance: f64,
    pub need_elongation: bool,
}

impl TreeNode {
    pub fn new(name: &str, position: Point<i32, i32>) -> Self {
        TreeNode {
            name: name.to_string(),
            position,
            left: None,
            right: None,
            parent: None,
            wire_length: 0,
            delay: 0.0,
            capacitance: 0.0,
            need_elongation: false,
        }
    }

    pub fn is_leaf(&self) -> bool {
        self.left.is_none() && self.right.is_none()
    }
}

/// Abstract delay model for wire delay calculation.
pub trait DelayCalculator {
    fn calculate_wire_delay(&self, length: i32, load_capacitance: f64) -> f64;
    fn calculate_wire_delay_per_unit(&self, load_capacitance: f64) -> f64;
    fn calculate_wire_capacitance(&self, length: i32) -> f64;
    fn calculate_tapping_point(
        &self,
        node_left: &mut TreeNode,
        node_right: &mut TreeNode,
        distance: i32,
    ) -> (i32, f64);
}

/// Linear delay model: delay proportional to wire length.
pub struct LinearDelayCalculator {
    pub delay_per_unit: f64,
    pub capacitance_per_unit: f64,
}

impl LinearDelayCalculator {
    pub fn new(delay_per_unit: f64, capacitance_per_unit: f64) -> Self {
        LinearDelayCalculator {
            delay_per_unit,
            capacitance_per_unit,
        }
    }
}

impl DelayCalculator for LinearDelayCalculator {
    fn calculate_wire_delay(&self, length: i32, _load_capacitance: f64) -> f64 {
        self.delay_per_unit * length as f64
    }

    fn calculate_wire_delay_per_unit(&self, _load_capacitance: f64) -> f64 {
        self.delay_per_unit
    }

    fn calculate_wire_capacitance(&self, length: i32) -> f64 {
        self.capacitance_per_unit * length as f64
    }

    fn calculate_tapping_point(
        &self,
        node_left: &mut TreeNode,
        node_right: &mut TreeNode,
        distance: i32,
    ) -> (i32, f64) {
        let skew = node_right.delay - node_left.delay;
        let extend_left = ((skew / self.delay_per_unit + distance as f64) / 2.0).round() as i32;
        let delay_left = node_left.delay + extend_left as f64 * self.delay_per_unit;

        node_left.wire_length = extend_left;
        node_right.wire_length = distance - extend_left;

        let (extend_left, delay_left) = if extend_left < 0 {
            node_left.wire_length = 0;
            node_right.wire_length = distance - extend_left;
            node_right.need_elongation = true;
            (0, node_left.delay)
        } else if extend_left > distance {
            node_right.wire_length = 0;
            node_left.wire_length = extend_left;
            node_left.need_elongation = true;
            (distance, node_right.delay)
        } else {
            (extend_left, delay_left)
        };

        (extend_left, delay_left)
    }
}

/// Elmore delay model: considers wire resistance and capacitance.
pub struct ElmoreDelayCalculator {
    pub unit_resistance: f64,
    pub unit_capacitance: f64,
}

impl ElmoreDelayCalculator {
    pub fn new(unit_resistance: f64, unit_capacitance: f64) -> Self {
        ElmoreDelayCalculator {
            unit_resistance,
            unit_capacitance,
        }
    }
}

impl DelayCalculator for ElmoreDelayCalculator {
    fn calculate_wire_delay(&self, length: i32, load_capacitance: f64) -> f64 {
        let wire_resistance = self.unit_resistance * length as f64;
        let wire_capacitance = self.unit_capacitance * length as f64;
        wire_resistance * (wire_capacitance / 2.0 + load_capacitance)
    }

    fn calculate_wire_delay_per_unit(&self, load_capacitance: f64) -> f64 {
        self.unit_resistance * (self.unit_capacitance / 2.0 + load_capacitance)
    }

    fn calculate_wire_capacitance(&self, length: i32) -> f64 {
        self.unit_capacitance * length as f64
    }

    fn calculate_tapping_point(
        &self,
        node_left: &mut TreeNode,
        node_right: &mut TreeNode,
        distance: i32,
    ) -> (i32, f64) {
        let skew = node_right.delay - node_left.delay;
        let r = distance as f64 * self.unit_resistance;
        let c = distance as f64 * self.unit_capacitance;

        let z = (skew + r * (node_right.capacitance + c / 2.0))
            / (r * (c + node_right.capacitance + node_left.capacitance));

        let extend_left = (z * distance as f64).round() as i32;
        let r_left = extend_left as f64 * self.unit_resistance;
        let c_left = extend_left as f64 * self.unit_capacitance;
        let delay_left = node_left.delay + r_left * (c_left / 2.0 + node_left.capacitance);

        node_left.wire_length = extend_left;
        node_right.wire_length = distance - extend_left;

        let (extend_left, delay_left) = if extend_left < 0 {
            node_left.wire_length = 0;
            node_right.wire_length = distance - extend_left;
            node_right.need_elongation = true;
            (0, node_left.delay)
        } else if extend_left > distance {
            node_right.wire_length = 0;
            node_left.wire_length = extend_left;
            node_left.need_elongation = true;
            (distance, node_right.delay)
        } else {
            (extend_left, delay_left)
        };

        (extend_left, delay_left)
    }
}

/// Results of clock skew analysis.
#[derive(Debug, Clone)]
pub struct SkewAnalysis {
    pub max_delay: f64,
    pub min_delay: f64,
    pub skew: f64,
    pub sink_delays: Vec<f64>,
    pub total_wirelength: i32,
    pub delay_model: String,
}

/// Detailed tree statistics.
#[derive(Debug, Clone)]
pub struct TreeStatistics {
    pub nodes: Vec<NodeInfo>,
    pub wires: Vec<WireInfo>,
    pub sinks: Vec<String>,
    pub total_nodes: i32,
    pub total_sinks: i32,
    pub total_wires: i32,
}

#[derive(Debug, Clone)]
pub struct NodeInfo {
    pub name: String,
    pub position: (i32, i32),
    pub node_type: String,
    pub delay: f64,
    pub capacitance: f64,
}

#[derive(Debug, Clone)]
pub struct WireInfo {
    pub from_node: String,
    pub to_node: String,
    pub length: i32,
    pub from_pos: (i32, i32),
    pub to_pos: (i32, i32),
}

/// The DME algorithm for clock tree synthesis.
pub struct DMEAlgorithm {
    sinks: Vec<Sink>,
    delay_calculator: Box<dyn DelayCalculator>,
    node_id: i32,
}

impl DMEAlgorithm {
    pub fn new(sinks: Vec<Sink>, calculator: Box<dyn DelayCalculator>) -> Self {
        assert!(!sinks.is_empty(), "No sinks provided");
        DMEAlgorithm {
            sinks,
            delay_calculator: calculator,
            node_id: 0,
        }
    }

    /// Builds the zero-skew clock tree.
    pub fn build_clock_tree(&mut self) -> Rc<RefCell<TreeNode>> {
        let nodes: Vec<Rc<RefCell<TreeNode>>> = self
            .sinks
            .iter()
            .map(|s| {
                let mut node = TreeNode::new(&s.name, s.position);
                node.capacitance = s.capacitance;
                Rc::new(RefCell::new(node))
            })
            .collect();

        let merging_tree = self.build_merging_tree(&nodes, false);
        let mut merging_segments = HashMap::new();
        self.compute_merging_segment(Rc::clone(&merging_tree), &mut merging_segments);
        self.embed_node(Rc::clone(&merging_tree), None, &merging_segments);
        self.compute_delays(Rc::clone(&merging_tree), 0.0);
        merging_tree
    }

    fn build_merging_tree(
        &mut self,
        nodes: &[Rc<RefCell<TreeNode>>],
        vertical: bool,
    ) -> Rc<RefCell<TreeNode>> {
        if nodes.len() == 1 {
            return Rc::clone(&nodes[0]);
        }

        let mut sorted = nodes.to_vec();
        if vertical {
            sorted.sort_by(|a, b| a.borrow().position.xcoord.cmp(&b.borrow().position.xcoord));
        } else {
            sorted.sort_by(|a, b| a.borrow().position.ycoord.cmp(&b.borrow().position.ycoord));
        }

        let mid = sorted.len() / 2;
        let left_group: Vec<_> = sorted[..mid].to_vec();
        let right_group: Vec<_> = sorted[mid..].to_vec();

        let left_child = self.build_merging_tree(&left_group, !vertical);
        let right_child = self.build_merging_tree(&right_group, !vertical);

        let id = format!("n{}", self.node_id);
        self.node_id += 1;
        let pos = left_child.borrow().position;
        let parent = Rc::new(RefCell::new(TreeNode::new(&id, pos)));
        {
            let mut p = parent.borrow_mut();
            p.left = Some(Rc::clone(&left_child));
            p.right = Some(Rc::clone(&right_child));
        }
        left_child.borrow_mut().parent = Some(Rc::clone(&parent));
        right_child.borrow_mut().parent = Some(Rc::clone(&parent));

        parent
    }

    fn compute_merging_segment(
        &self,
        node: Rc<RefCell<TreeNode>>,
        segments: &mut HashMap<*const TreeNode, ManhattanArc<Interval<i32>>>,
    ) -> ManhattanArc<Interval<i32>> {
        let is_leaf = node.borrow().is_leaf();
        let node_ptr: *const TreeNode = &*node.borrow();

        if is_leaf {
            let pos = node.borrow().position;
            let ms1 = ManhattanArc::from_point(pos);
            let ms = ManhattanArc::new(
                Interval::new(ms1.xcoord(), ms1.xcoord()),
                Interval::new(ms1.ycoord(), ms1.ycoord()),
            );
            segments.insert(node_ptr, ms);
            return ms;
        }

        let left = node.borrow().left.as_ref().map(Rc::clone);
        let right = node.borrow().right.as_ref().map(Rc::clone);
        let left = left.expect("Internal node missing left child");
        let right = right.expect("Internal node missing right child");

        let left_ms = self.compute_merging_segment(Rc::clone(&left), segments);
        let right_ms = self.compute_merging_segment(Rc::clone(&right), segments);

        let distance = left_ms.min_dist_with(&right_ms) as i32;

        let (extend_left, delay_left) = self.delay_calculator.calculate_tapping_point(
            &mut left.borrow_mut(),
            &mut right.borrow_mut(),
            distance,
        );
        node.borrow_mut().delay = delay_left;

        let merged_segment = left_ms.merge_with(&right_ms, extend_left);
        segments.insert(node_ptr, merged_segment);

        let wire_cap = self.delay_calculator.calculate_wire_capacitance(distance);
        node.borrow_mut().capacitance =
            left.borrow().capacitance + right.borrow().capacitance + wire_cap;

        merged_segment
    }

    fn embed_node(
        &self,
        node: Rc<RefCell<TreeNode>>,
        parent_segment: Option<&ManhattanArc<Interval<i32>>>,
        segments: &HashMap<*const TreeNode, ManhattanArc<Interval<i32>>>,
    ) {
        let node_ptr: *const TreeNode = &*node.borrow();
        let node_segment = segments
            .get(&node_ptr)
            .expect("Merging segment not found for node");

        if parent_segment.is_none() {
            // Root node: use upper corner of merging segment
            let upper = Point::new(node_segment.impl_p.xcoord.ub, node_segment.impl_p.ycoord.ub);
            node.borrow_mut().position = upper;
        } else {
            let parent_pos = node.borrow().parent.as_ref().map(|p| p.borrow().position);
            if let Some(pp) = parent_pos {
                let nearest = node_segment.nearest_point_to(&pp);
                node.borrow_mut().position = nearest;
                let dist = node.borrow().position.min_dist_with(&pp);
                node.borrow_mut().wire_length = dist as i32;
            }
        }

        let left = node.borrow().left.as_ref().map(Rc::clone);
        let right = node.borrow().right.as_ref().map(Rc::clone);

        if let Some(l) = left {
            self.embed_node(l, Some(node_segment), segments);
        }
        if let Some(r) = right {
            self.embed_node(r, Some(node_segment), segments);
        }
    }

    fn compute_delays(&self, node: Rc<RefCell<TreeNode>>, parent_delay: f64) {
        let has_parent = node.borrow().parent.is_some();
        if has_parent {
            let wire_delay = self
                .delay_calculator
                .calculate_wire_delay(node.borrow().wire_length, node.borrow().capacitance);
            node.borrow_mut().delay = parent_delay + wire_delay;
        } else {
            node.borrow_mut().delay = 0.0;
        }

        let current_delay = node.borrow().delay;
        let left = node.borrow().left.as_ref().map(Rc::clone);
        let right = node.borrow().right.as_ref().map(Rc::clone);

        if let Some(l) = left {
            self.compute_delays(l, current_delay);
        }
        if let Some(r) = right {
            self.compute_delays(r, current_delay);
        }
    }

    /// Analyzes clock skew of the constructed tree.
    pub fn analyze_skew(&self, root: Rc<RefCell<TreeNode>>) -> SkewAnalysis {
        let mut sink_delays = Vec::new();
        collect_sink_delays(&root, &mut sink_delays);

        if sink_delays.is_empty() {
            panic!("No sink delays collected");
        }

        let max_delay = sink_delays
            .iter()
            .cloned()
            .fold(f64::NEG_INFINITY, f64::max);
        let min_delay = sink_delays.iter().cloned().fold(f64::INFINITY, f64::min);
        let skew = max_delay - min_delay;
        let total_wl = total_wirelength(&root);
        #[allow(clippy::incompatible_msrv)]
        let delay_model = std::any::type_name_of_val(&*self.delay_calculator).to_string();

        SkewAnalysis {
            max_delay,
            min_delay,
            skew,
            sink_delays,
            total_wirelength: total_wl,
            delay_model,
        }
    }
}

fn collect_sink_delays(node: &Rc<RefCell<TreeNode>>, sink_delays: &mut Vec<f64>) {
    if node.borrow().is_leaf() {
        sink_delays.push(node.borrow().delay);
    }
    let left = node.borrow().left.as_ref().map(Rc::clone);
    let right = node.borrow().right.as_ref().map(Rc::clone);
    if let Some(l) = left {
        collect_sink_delays(&l, sink_delays);
    }
    if let Some(r) = right {
        collect_sink_delays(&r, sink_delays);
    }
}

fn total_wirelength(node: &Rc<RefCell<TreeNode>>) -> i32 {
    let mut total = node.borrow().wire_length;
    let left = node.borrow().left.as_ref().map(Rc::clone);
    let right = node.borrow().right.as_ref().map(Rc::clone);
    if let Some(l) = left {
        total += total_wirelength(&l);
    }
    if let Some(r) = right {
        total += total_wirelength(&r);
    }
    total
}

/// Extracts detailed statistics from a clock tree.
pub fn get_tree_statistics(root: Rc<RefCell<TreeNode>>) -> TreeStatistics {
    let mut stats = TreeStatistics {
        nodes: Vec::new(),
        wires: Vec::new(),
        sinks: Vec::new(),
        total_nodes: 0,
        total_sinks: 0,
        total_wires: 0,
    };
    traverse_tree(&root, None, &mut stats);
    stats.total_nodes = stats.nodes.len() as i32;
    stats.total_sinks = stats.sinks.len() as i32;
    stats.total_wires = stats.wires.len() as i32;
    stats
}

fn traverse_tree(
    node: &Rc<RefCell<TreeNode>>,
    parent: Option<&Rc<RefCell<TreeNode>>>,
    stats: &mut TreeStatistics,
) {
    let n = node.borrow();
    stats.nodes.push(NodeInfo {
        name: n.name.clone(),
        position: (n.position.xcoord, n.position.ycoord),
        node_type: if n.is_leaf() {
            "sink".to_string()
        } else {
            "internal".to_string()
        },
        delay: n.delay,
        capacitance: n.capacitance,
    });

    if n.is_leaf() {
        stats.sinks.push(n.name.clone());
    }

    if let Some(p) = parent {
        let pb = p.borrow();
        stats.wires.push(WireInfo {
            from_node: pb.name.clone(),
            to_node: n.name.clone(),
            length: n.wire_length,
            from_pos: (pb.position.xcoord, pb.position.ycoord),
            to_pos: (n.position.xcoord, n.position.ycoord),
        });
    }

    let left = n.left.as_ref().map(Rc::clone);
    let right = n.right.as_ref().map(Rc::clone);
    drop(n);

    if let Some(l) = left {
        traverse_tree(&l, Some(node), stats);
    }
    if let Some(r) = right {
        traverse_tree(&r, Some(node), stats);
    }
}