dme_algorithm.hpp

Go to the documentation of this file.

 
#pragma once
 
#include <cstddef>
#include <memory>
#include <optional>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
 
#include "manhattan_arc.hpp"
#include "point.hpp"
 
namespace recti {
 
    // Forward declarations
    class Tree;
 
    using NodeIdx = std::size_t;
 
    class Sink {
      public:
        std::string name;
        Point<int> position;
        double capacitance;
 
        constexpr Sink(const std::string& name, const Point<int>& position,
                       double capacitance = 1.0)
            : name(name), position(position), capacitance(capacitance) {}
    };
 
    class TreeNode {
      public:
        std::string name;
        Point<int> position;
        NodeIdx left = SIZE_MAX;    
        NodeIdx right = SIZE_MAX;   
        NodeIdx parent = SIZE_MAX;  
        int wire_length = 0;        
        double delay = 0.0;         
        double capacitance = 0.0;   
        bool need_elongation
            = false;  
 
        TreeNode(const std::string& name, const Point<int>& position)
            : name(name), position(position) {}
 
        bool is_leaf() const { return left == SIZE_MAX && right == SIZE_MAX; }
    };
 
    class Tree {
      private:
        std::vector<TreeNode> nodes;
 
      public:
        NodeIdx root = SIZE_MAX;
 
        Tree() = default;
 
        NodeIdx add(TreeNode node) {
            NodeIdx idx = nodes.size();
            nodes.push_back(std::move(node));
            return idx;
        }
 
        const TreeNode& get(NodeIdx idx) const { return nodes.at(idx); }
 
        TreeNode& get_mut(NodeIdx idx) { return nodes.at(idx); }
 
        std::pair<TreeNode&, TreeNode&> get_pair_mut(NodeIdx a, NodeIdx b) {
            return {nodes.at(a), nodes.at(b)};
        }
 
        std::size_t size() const { return nodes.size(); }
 
        bool empty() const { return nodes.empty(); }
    };
 
    struct TappingResult {
        int extend_left;
        int raw_extend_left;
        double delay_left;
    };
 
    class DelayCalculator {
      public:
        DelayCalculator() = default;
        DelayCalculator(const DelayCalculator&) = default;
        DelayCalculator& operator=(const DelayCalculator&) = default;
        DelayCalculator(DelayCalculator&&) = default;
        DelayCalculator& operator=(DelayCalculator&&) = default;
        virtual ~DelayCalculator() = default;
 
        virtual double calculate_wire_delay(int length, double load_capacitance) const = 0;
 
        virtual double calculate_wire_delay_per_unit(double load_capacitance) const = 0;
 
        virtual double calculate_wire_capacitance(int length) const = 0;
 
        virtual TappingResult calculate_tapping_point(int distance, double left_delay,
                                                      double right_delay, double left_capacitance,
                                                      double right_capacitance) const
            = 0;
    };
 
    class LinearDelayCalculator : public DelayCalculator {
      private:
        double delay_per_unit;        
        double capacitance_per_unit;  
 
      public:
        LinearDelayCalculator(double delay_per_unit = 1.0, double capacitance_per_unit = 1.0)
            : delay_per_unit(delay_per_unit), capacitance_per_unit(capacitance_per_unit) {}
 
        double calculate_wire_delay(int length, double /* load_capacitance */) const override {
            return delay_per_unit * static_cast<double>(length);
        }
 
        double calculate_wire_delay_per_unit(double /* load_capacitance */) const override {
            return delay_per_unit;
        }
 
        double calculate_wire_capacitance(int length) const override {
            return capacitance_per_unit * static_cast<double>(length);
        }
 
        TappingResult calculate_tapping_point(int distance, double left_delay, double right_delay,
                                              double /* left_capacitance */,
                                              double /* right_capacitance */) const override;
    };
 
    class ElmoreDelayCalculator : public DelayCalculator {
      private:
        double unit_resistance;   
        double unit_capacitance;  
 
      public:
        ElmoreDelayCalculator(double unit_resistance = 1.0, double unit_capacitance = 1.0)
            : unit_resistance(unit_resistance), unit_capacitance(unit_capacitance) {}
 
        double calculate_wire_delay(int length, double load_capacitance) const override {
            double wire_resistance = unit_resistance * length;
            double wire_capacitance = unit_capacitance * length;
            return wire_resistance * (wire_capacitance / 2 + load_capacitance);
        }
 
        double calculate_wire_delay_per_unit(double load_capacitance) const override {
            return unit_resistance * (unit_capacitance / 2 + load_capacitance);
        }
 
        double calculate_wire_capacitance(int length) const override {
            return unit_capacitance * length;
        }
 
        TappingResult calculate_tapping_point(int distance, double left_delay, double right_delay,
                                              double left_capacitance,
                                              double right_capacitance) const override;
    };
 
    struct SkewAnalysis {
        double max_delay;                 
        double min_delay;                 
        double skew;                      
        std::vector<double> sink_delays;  
        int total_wirelength;             
        std::string
            delay_model;  
    };
 
    struct TreeStatistics {
        struct NodeInfo {
            std::string name;              
            std::pair<int, int> position;  
            std::string type;              
            double delay;                  
            double capacitance;            
        };
 
        struct WireInfo {
            std::string from_node;         
            std::string to_node;           
            int length;                    
            std::pair<int, int> from_pos;  
            std::pair<int, int> to_pos;    
        };
 
        std::vector<NodeInfo> nodes;
        std::vector<WireInfo> wires;
        std::vector<std::string> sinks;
        int total_nodes = 0;
        int total_sinks = 0;
        int total_wires = 0;
    };
 
    class DMEAlgorithm {
      private:
        std::vector<Sink> sinks;
        std::unique_ptr<DelayCalculator> delay_calculator;
        int node_id = 0;
        Tree tree;
        std::optional<Point<int>> source;
 
      public:
        DMEAlgorithm(const std::vector<Sink>& sinks, std::unique_ptr<DelayCalculator> calculator)
            : sinks(sinks), delay_calculator(std::move(calculator)) {
            if (this->sinks.empty()) {
                throw std::invalid_argument("No sinks provided");
            }
        }
 
        DMEAlgorithm(const std::vector<Sink>& sinks, std::unique_ptr<DelayCalculator> calculator,
                     Point<int> source_position)
            : sinks(sinks), delay_calculator(std::move(calculator)), source(source_position) {
            if (this->sinks.empty()) {
                throw std::invalid_argument("No sinks provided");
            }
        }
 
        NodeIdx build_clock_tree();
 
        const Tree& get_tree() const { return tree; }
 
        Tree& get_tree_mut() { return tree; }
 
        SkewAnalysis analyze_skew(NodeIdx root) const;
 
      private:
        NodeIdx build_merging_tree(const std::vector<NodeIdx>& node_ids, bool vertical);
 
        ManhattanArc<Interval<int>, Interval<int>> _compute_merging_segment(
            NodeIdx node, std::unordered_map<NodeIdx, ManhattanArc<Interval<int>, Interval<int>>>&
                              merging_segments);
 
        std::unordered_map<NodeIdx, ManhattanArc<Interval<int>, Interval<int>>>
        compute_merging_segments(NodeIdx root);
 
        void _embed_node(
            NodeIdx node, const ManhattanArc<Interval<int>, Interval<int>>* parent_segment,
            const std::unordered_map<NodeIdx, ManhattanArc<Interval<int>, Interval<int>>>&
                merging_segments);
 
        NodeIdx embed_tree(
            NodeIdx merging_tree_root,
            const std::unordered_map<NodeIdx, ManhattanArc<Interval<int>, Interval<int>>>&
                merging_segments);
 
        void _compute_delays(NodeIdx node, double parent_delay);
 
        void compute_tree_parameters(NodeIdx root);
 
        int total_wirelength(NodeIdx root) const;
    };
 
    TreeStatistics get_tree_statistics(const Tree& tree, NodeIdx root);
 
    extern void example_dme_usage();
 
}  // namespace recti