.. _program_listing_file_src_routing_routing.h:

Program Listing for File routing.h
==================================

|exhale_lsh| :ref:`Return to documentation for file <file_src_routing_routing.h>` (``src/routing/routing.h``)

.. |exhale_lsh| unicode:: U+021B0 .. UPWARDS ARROW WITH TIP LEFTWARDS

.. code-block:: cpp

   #ifndef ROUTING_H
   #define ROUTING_H
   
   #include <stdlib.h>
   
   #include <algorithm>
   #include <cmath>
   #include <cstring>
   #include <ctime>
   #include <fstream>
   #include <future>
   #include <iomanip>
   #include <iostream>
   #include <list>
   #include <numeric>
   #include <queue>
   #include <set>
   #include <stack>
   #include <string>
   #include <thread>
   #include <unordered_set>
   #include <vector>
   
   #include "../sta/sta.h"
   #include "constructTiming.h"
   #include "delay_lib.h"
   #include "json.hpp"
   #include "modeling.h"
   
   
   struct mesh {
     int id;         
     int distance;   
     int cutweight;  
     int prev;       
   
     bool operator<(const mesh &rhs) const
     {
       return distance < rhs.distance ||
              (distance == rhs.distance && cutweight < rhs.cutweight);
     }
   };
   
   struct SlackStat {
     double min_slack;        
     int tdm_cut_min_slack;   
     int die_cut_min_slack;   
   };
   
   struct Edge {
     int u, v;          
     bool uv_disabled;  
     bool vu_disabled;  
     int uv_flow;       
     int vu_flow;       
     int capacity;      
     int gio_capacity;  
   };
   
   void output_cut_result(const graph &finest, const vector<int> &parts);
   
   bool is_diff_fpga(int a, int b);
   
   void dijkstra_tdm(vector<vector<double>> &graph_cost, int src,
                     double lambda_tdm, double lambda_die, vector<double> &dist,
                     vector<int> &prev);
   
   void prim_mst(const vector<vector<double>> &cost_mat, const vector<int> &nodes,
                 vector<int> &parent);
   
   void add_path_by_prev(int dst, const vector<int> &prev,
                         set<pair<int, int>> &route_tree, vector<int> &parent,
                         vector<vector<int>> &cut_mat,
                         vector<vector<double>> &cost_mat,
                         const vector<vector<double>> &inc_mat,
                         bool is_diff_fpga(int, int));
   
   std::pair<int, int> norm_edge(int u, int v);
   
   long long pack_edge(int u, int v);
   
   class cut_net {
    public:
     vector<int> fpga_nodes;      
     int net_id;                  
     double routing_cost;         
     double clock_period;         
     vector<int> route_graph;     
     vector<int> route_graph_old; 
     double delay;                
     bool bypass = false;         
   };
   
   struct WorstPathCache {
     int worst_sink = -1;     
     double worst_delay = 0.0; 
     std::vector<std::pair<int, int>> edges; 
     std::vector<int> nodes;   
     std::string desc;         
   };
   
   class cut_timing_path {
    public:
     vector<int> path;          
     vector<int> arcs;          
     vector<int> path_arcs;     
     vector<int> timing_edges;  
     int orig_tp_id = 0;        
   
     int cut;                   
     int die_cut;               
     double slack;              
     double slack_old;          
     double cut_slack;          
     double cut_slack_old;      
     float cp = 0;              
     std::string clock_domain;  
   
     bool operator==(const cut_timing_path &other) const
     {
       return path == other.path && arcs == other.arcs;
     }
     // int get_cut_slack(double cut_delay = 0)
     // {
     //   return slack - cut_delay * cut;
     // }
   };
   
   struct IncrementalDmax {
     int F;  
     const std::vector<std::vector<int>> &cap;  
     double alpha;  
     double beta;   
   
     std::vector<std::vector<int>> net_cnt;  
     std::vector<std::vector<double>> delay; 
     std::vector<std::vector<double>> tdm;   
     std::vector<double> net_delay;          
     double die_delay = 0.0;                 
     std::unordered_map<long long, std::vector<int>> edge_to_nets; 
   
     IncrementalDmax(int F_, const std::vector<std::vector<int>> &cap_,
                     double alpha_, double beta_, double die_delay_)
         : F(F_),
           cap(cap_),
           alpha(alpha_),
           beta(beta_),
           net_cnt(F_, std::vector<int>(F_, 0)),
           delay(F_, std::vector<double>(F_, 0.0)),
           tdm(F_, std::vector<double>(F_, 0.0)),
           die_delay(die_delay_)
     {
     }
   
     static inline long long k(int u, int v)
     {
       return pack_edge(u, v);
     }
   
     void build_from(
         const flat_hash_map<int, std::set<std::pair<int, int>>> &route_trees,
         const std::vector<cut_net> &cut_nets)
     {
       // 1) net_cnt from trees (each net counts an undirected edge once)
       for (auto &kv : route_trees) {
         std::unordered_set<long long> seen;
         for (auto [u, v] : kv.second) {
           if (u == v)
             continue;
           long long kk = k(u, v);
           if (seen.insert(kk).second) {
             int a = (int)(kk >> 32), b = (int)(kk & 0xffffffff);
             net_cnt[a][b] += 1;
           }
         }
       }
       // 2) delay / tdm from net_cnt + cap
       for (int u = 0; u < F; ++u)
         for (int v = u + 1; v < F; ++v) {
           int w = cap[u][v];
           int N = net_cnt[u][v];
           if (w > 0 && N > 0) {
             int r     = (double)N / (double)w;
             tdm[u][v] = tdm[v][u] = r;
             delay[u][v] = delay[v][u] = beta + alpha * r;
           }
         }
       // 3) edge_to_nets index
       edge_to_nets.clear();
       for (int lid = 0; lid < (int)cut_nets.size(); ++lid) {
         auto it = route_trees.find(cut_nets[lid].net_id);
         if (it == route_trees.end())
           continue;
         std::unordered_set<long long> seen;
         for (auto [u, v] : it->second) {
           long long kk = k(u, v);
           if (seen.insert(kk).second)
             edge_to_nets[kk].push_back(lid);
         }
       }
       // 4) net_delay by BFS on each net’s own tree (with current delay)
       net_delay.assign(cut_nets.size(), 0.0);
       for (int lid = 0; lid < (int)cut_nets.size(); ++lid) {
         const auto &net = cut_nets[lid];
         if (net.fpga_nodes.empty())
           continue;
         int src = net.fpga_nodes[0];
   
         std::vector<std::vector<int>> adj(F);
         auto it = route_trees.find(net.net_id);
         if (it != route_trees.end()) {
           for (auto [u, v] : it->second) {
             adj[u].push_back(v);
             adj[v].push_back(u);
           }
         }
         auto bfs_path = [&](int s, int t) {
           std::vector<int> q;
           q.reserve(F);
           q.push_back(s);
           std::vector<int> par(F, -1);
           par[s] = -2;
           for (size_t i = 0; i < q.size() && par[t] == -1; ++i) {
             int x = q[i];
             for (int y : adj[x])
               if (par[y] == -1) {
                 par[y] = x;
                 q.push_back(y);
                 if (y == t)
                   break;
               }
           }
           std::vector<int> path;
           if (par[t] == -1)
             return path;
           for (int cur = t; cur != -2; cur = par[cur]) path.push_back(cur);
           std::reverse(path.begin(), path.end());
           return path;
         };
         double worst = 0.0;
         for (size_t i = 1; i < net.fpga_nodes.size(); ++i) {
           int sink  = net.fpga_nodes[i];
           auto path = bfs_path(src, sink);
           if (path.empty()) {
             path = {src, sink};
           }
           double sum = 0.0;
           for (size_t e = 1; e < path.size(); ++e)
             sum += delay[path[e - 1]][path[e]];
           worst = std::max(worst, sum);
         }
         net_delay[lid] = worst;
       }
     }
   
     void apply_edge_delta(int u, int v, int delta)
     {
       int &N = net_cnt[u][v];
       N      = std::max(0, N + delta);
       int w  = cap[u][v];
       if (w > 0 && N > 0) {
         if (is_diff_fpga(u, v)) {
           double r    = (double)N / (double)w;
           tdm[u][v]   = r;
           delay[u][v] = beta + alpha * r;
         } else {
           tdm[u][v]   = 0.0;
           delay[u][v] = die_delay;
         }
       } else {
         tdm[u][v]   = 0.0;
         delay[u][v] = 0.0;
       }
     }
     void apply_edge_delta_nodirection(int u, int v, int delta)
     {
       if (u > v)
         std::swap(u, v);
       int &N = net_cnt[u][v];
       N      = std::max(0, N + delta);
       int w  = cap[u][v];
       if (w > 0 && N > 0) {
         if (is_diff_fpga(u, v)) {
           double r  = (double)N / (double)w;
           tdm[u][v] = tdm[v][u] = r;
           delay[u][v] = delay[v][u] = beta + alpha * r;
         } else {
           tdm[u][v] = tdm[v][u] = 0.0;
           delay[u][v] = delay[v][u] = die_delay;
         }
       } else {
         tdm[u][v] = tdm[v][u] = 0.0;
         delay[u][v] = delay[v][u] = 0.0;
       }
     }
     void recompute_nets(
         const std::vector<int> &nets,
         const flat_hash_map<int, std::set<std::pair<int, int>>> &route_trees,
         const std::vector<cut_net> &cut_nets)
     {
       for (int lid : nets) {
         const auto &net = cut_nets[lid];
         if (net.fpga_nodes.empty()) {
           net_delay[lid] = 0.0;
           continue;
         }
         int src = net.fpga_nodes[0];
   
         std::vector<std::vector<int>> adj(F);
         auto it = route_trees.find(net.net_id);
         if (it != route_trees.end()) {
           for (auto [u, v] : it->second) {
             adj[u].push_back(v);
             adj[v].push_back(u);
           }
         }
   
         auto bfs_path = [&](int s, int t) {
           std::vector<int> q;
           q.reserve(F);
           q.push_back(s);
           std::vector<int> par(F, -1);
           par[s] = -2;
           for (size_t i = 0; i < q.size() && par[t] == -1; ++i) {
             int x = q[i];
             for (int y : adj[x])
               if (par[y] == -1) {
                 par[y] = x;
                 q.push_back(y);
                 if (y == t)
                   break;
               }
           }
           std::vector<int> path;
           if (par[t] == -1)
             return path;
           for (int cur = t; cur != -2; cur = par[cur]) path.push_back(cur);
           std::reverse(path.begin(), path.end());
           return path;
         };
   
         double worst = 0.0;
         for (size_t i = 1; i < net.fpga_nodes.size(); ++i) {
           int sink  = net.fpga_nodes[i];
           auto path = bfs_path(src, sink);
   
           if (path.empty()) {
             path = {src, sink};
           }
   
           double sum = 0.0;
           for (size_t e = 1; e < path.size(); ++e) {
             int u = path[e - 1], v = path[e];
             bool inter = is_diff_fpga(u, v);
             if (!inter) {
               sum += die_delay;
             } else {
               sum += delay[u][v];
             }
           }
           // spdlog::debug(
           //     "[recompute_nets] net {} path from {} to {} with delay {}",
           //     net.net_id, src + 1, sink + 1, sum);
   
           worst = std::max(worst, sum);
         }
         // 打印最终计算出的 net_delay
         // spdlog::debug("[recompute_nets] net {} delay updated: {:.1f}",
         // net.net_id,
         //               worst);
   
         net_delay[lid] = worst;
       }
     }
     std::pair<double, int> global_worst(
         const std::vector<cut_net> &cut_nets) const
     {
       double gmax = 0.0;
       int gnet    = -1;
       for (int lid = 0; lid < (int)net_delay.size(); ++lid) {
         if (net_delay[lid] > gmax) {
           gmax = net_delay[lid];
           gnet = cut_nets[lid].net_id;
         }
       }
       return {gmax, gnet};
     }
   
     void index_edge_for_net(int u, int v, int lid, bool add)
     {
       long long kk = k(u, v);
       auto &vec    = edge_to_nets[kk];
       if (add) {
         if (vec.empty() || std::find(vec.begin(), vec.end(), lid) == vec.end())
           vec.push_back(lid);
       } else {
         auto it = std::find(vec.begin(), vec.end(), lid);
         if (it != vec.end())
           vec.erase(it);
       }
     }
   
     std::pair<double, int> global_worst_lid() const
     {
       double gmax  = 0.0;
       int best_lid = -1;
       for (int lid = 0; lid < (int)net_delay.size(); ++lid) {
         if (net_delay[lid] > gmax) {
           gmax     = net_delay[lid];
           best_lid = lid;
         }
       }
       return {gmax, best_lid};
     }
   };
   
   struct WorstInfo {
     double worst_delay;           
     int worst_net_id;             
     std::string worst_path_desc;  
   };
   
   struct PendingEdge {
     int u = -1;       
     int v = -1;       
     int times = 0;    
     double tdm = 0;   
     int tdm_real = 0; 
   };
   
   namespace std {
   template <>
   struct hash<cut_timing_path> {
     size_t operator()(const cut_timing_path &ctp) const noexcept
     {
       size_t seed = ctp.path.size();
       for (auto &i : ctp.path) {
         seed ^= hash<int>()(i) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
       }
       for (auto &i : ctp.arcs) {
         seed ^= hash<int>()(i) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
       }
       return seed;
     }
   };
   }  // namespace std
   
   class Routing {
    public:
     // 输入数据
     const graph &finest;  
     const vector<pair<int, int>> &die_parts; 
     fpga &fpgas;  
     const vector<DieConnection> &die_connections; 
     const shared_ptr<mulClockAttr> &mul_clock_attr; 
     vector<SimpleTiming> simpleTimings; 
   
     // 路由结果与中间矩阵
     flat_hash_map<int, set<pair<int, int>>> route_trees; 
     flat_hash_map<int, vector<RouteTreeEdge>> route_trees_edges; 
     vector<cut_timing_path> cut_timing_paths; 
     vector<cut_net> cut_nets; 
     vector<vector<int>> cut_mat; 
     vector<vector<int>> board_capacity; 
     vector<vector<int>> die_graph; 
     vector<vector<int>> die_physical_links; 
     vector<vector<int>> die_gio_links; 
     vector<vector<int>> die_mgt_links; 
     vector<vector<double>> cost_mat; 
     vector<vector<double>> inc_mat; 
     vector<vector<double>> die_dist; 
     vector<vector<int>> routing_graph; 
     unordered_map<cut_timing_path, double> cut_to_tp_id; 
     const DelayLibrary *delayLib = nullptr; 
     vector<vector<double>> tdm_mat; 
     vector<vector<int>> cutweights; 
   
     // 路由参数与运行状态
     double cut_delay; 
     double tdm_delay; 
     double die_delay; 
     bool tdm_aware;   
     string timing_routing_cost_mode = "critical_minmax_hop"; 
     double timing_hop_penalty_multiplier = 0.5; 
     bool has_die; 
     double clock_period; 
     int channel_grouping_capacity; 
     vector<Edge> disabled_edges; 
   
     enum class LinkType : uint8_t { INTRA = 0, GIO = 1, MGT = 2 };
     static constexpr double INF_COST = 1e100; 
     vector<vector<int>> load_gio; 
     vector<vector<int>> load_mgt; 
     bool delayLibReady = false; 
     double a = 1.0; 
     double b = 0.0; 
     double c = 0.0; 
     const int max_negotiation_iter = 1; 
     int free = 0; 
     double cong_alpha = 9.0; 
     double cong_lambda = 0.0; 
     double lambda_jump = 0; 
     const double INF = numeric_limits<double>::infinity(); 
     int Wtotal = 0; 
     double improve_eps = 1e-5; 
     bool contest = false; 
     bool use_hierarchy_delay = false; 
   
     Routing(const graph &finest, const vector<pair<int, int>> &die_parts,
             fpga &fpgas, const vector<DieConnection> &die_connections,
             double cut_delay, double tdm_delay, double die_delay, bool tdm_aware,
             const shared_ptr<mulClockAttr> &mul_clock_attr, bool has_die,
             double routing_cost_factor, vector<SimpleTiming> simpleTimings,
             const DelayLibrary *delayLib);
   
     inline RatioLib edge_lib(int u, int v);
   
     void die_routing();
     void die_routing_1();
     void die_routing_huang();
     void board_routing_huang(const vector<int> &parts);
     void die_routing_old();
     void die_routing_direction();
   
     void die_routing_synergistic_paper();
     void die_routing_near_optimal_paper();
     void board_routing_synergistic_paper(const vector<int> &parts);
     void board_routing_near_optimal_paper(const vector<int> &parts);
     void die_routing_negotiation_paper(const std::string &tag,
                                        const vector<int> *board_parts = nullptr);
   
     void export_routing_trees(flat_hash_map<int, vector<RouteTreeEdge>> &trees);
     void die_graph_from_connections();
     void build_board_capacity_from_connections();
     void init_mat(bool board_level = false);
     void ensure_type_aware_mats();
     double typed_edge_weight(int u, int v, LinkType tp) const;
     void dijkstra_typed(int s, std::vector<double> &dist,
                         std::vector<int> &parent_node,
                         std::vector<LinkType> &parent_type) const;
     void apply_path_and_update(int src, int dst,
                                const std::vector<int> &parent_node,
                                const std::vector<LinkType> &parent_type,
                                std::set<std::pair<int, int>> &route_tree);
     void route_one_net_gio_mgt(int net_local_id);
     void route_nets_gio_mgt_min_delay(const std::vector<int> &net_order);
     void adjust_die_graph_direction(bool board_level = false);
     void adjust_die_graph_direction_old();
     void adjust_die_graph_direction_contest();
     void adjust_die_graph_direction_update();
     void check_cut(vector<vector<int>> &cut_weights);
     void calc_die_dist(bool board_level = false);
     void routing_huang_impl(const vector<int> *board_parts);
     void export_cut_info();
     vector<int> build_target_net_order(
         const unordered_set<int> &target_nets,
         const vector<cut_timing_path> &cut_timing_paths,
         const vector<cut_net> &cut_nets, bool isMultiClock);
     SlackStat recompute_cut_slack(const vector<cut_timing_path> &cut_timing_paths,
                                   const vector<cut_net> &cut_nets,
                                   const vector<vector<double>> &cost_mat,
                                   const vector<vector<int>> &cut_mat,
                                   bool tdm_aware, bool update);
     void classify_critical_nets(const vector<cut_net> &cut_nets,
                                 vector<int> &critical_nets,
                                 vector<int> &non_critical_nets);
     void routing(const graph &finest, const vector<int> &parts, const fpga &fpgas,
                  const shared_ptr<mulClockAttr> &mul_clock_attr, double tdm_delay,
                  float &cut_delay,
                  flat_hash_map<int, set<pair<int, int>>> &route_trees,
                  vector<SimpleTiming> &simpleTimings);
     inline double lib_delay(RatioLib lib, double r) const;
     inline double lib_slope(RatioLib lib, double r) const;
     DelayScope delay_scope_for_parts(int src_part, int dst_part) const;
     inline double scoped_lib_delay(DelayScope scope, RatioLib lib, double r) const;
     inline double scoped_lib_slope(DelayScope scope, RatioLib lib, double r) const;
   
    private:
     inline int flatten_id(const pair<int, int> &id) const;
     inline pair<int, int> unflatten_id(int id) const;
     double routing_cost_factor;  
   };
   
   flat_hash_map<int, vector<vector<int>>> routing(
       const graph &g, const vector<int> &parts,
       const vector<vector<int>> &cutweights,
       const vector<vector<int>> &cutweights_assignment,
       vector<cut_net> &cut_nets);
   
   flat_hash_map<int, set<pair<int, int>>> routeTrees(
       flat_hash_map<int, vector<vector<int>>> &routes);
   
   void dump_die_cut_result(const vector<pair<int, int>> &die_parts);
   
   double reform_timing_paths(const graph &finest, const vector<int> &parts,
                              vector<cut_timing_path> &cut_tps,
                              vector<cut_net> &cut_nets,
                              const shared_ptr<mulClockAttr> &mul_clock_attr,
                              unordered_map<cut_timing_path, double> &cut_to_tp_id,
                              vector<SimpleTiming> &simpleTimings);
   
   double reform_timing_paths_old(const graph &finest, const vector<int> &parts,
                                  vector<cut_timing_path> &cut_tps,
                                  vector<cut_net> &cut_nets);
   
   void convert_route_trees(
       const flat_hash_map<int, set<pair<int, int>>> &route_trees,
       flat_hash_map<int, vector<RouteTreeEdge>> &trees);
   
   double lib_delay(RatioLib lib, double r);
   double lib_slope(RatioLib lib);
   double lib_rmin(RatioLib lib);
   double lib_max(RatioLib lib);
   
   namespace routing_flow {
   void routingFlow(const graph &finest, const vector<int> &parts,
                    const vector<pair<int, int>> &die_parts, fpga &fpgas,
                    const vector<vector<int>> &cutweights, params &para,
                    Routing &router, HSFullTiming::HSPartitionFlow &pFlow,
                    DelayLibrary *delayLib,
                    const vector<CutConnection> &cutConnections,
                    const string &io3_filename = "");
   }
   
   #endif