Program Listing for File routing.h¶
↰ Return to documentation for file (src/routing/routing.h)
#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>> ∩
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 ¶,
Routing &router, HSFullTiming::HSPartitionFlow &pFlow,
DelayLibrary *delayLib,
const vector<CutConnection> &cutConnections,
const string &io3_filename = "");
}
#endif