Dr. CU 详细布线算法设计

项目概述

Dr. CU是香港中文大学研究团队开发的VLSI详细布线工具。与全局布线不同，详细布线需要处理许多详细的设计规则，并在显著更大的布线网格图上执行。在先进技术节点下，它成为VLSI物理设计流程中最复杂和耗时的阶段。

核心创新点

1. 两级稀疏数据结构 - 用于高效存储和查询布线信息
2. 最优的正确构造路径搜索 - 确保设计规则满足
3. 高效的大规模并行方案 - 支持多线程加速

---

数据结构设计

1. 几何基元 (GeoPrimitive.h)

1.1 网格点 (GridPoint)

class GridPoint {
public:
    int layerIdx;        // 金属层索引
    int trackIdx;        // 走线道索引
    int crossPointIdx;   // 交叉点索引
};

网格点是详细布线中的基本坐标单元，表示在特定金属层的特定走线道上的特定交叉点位置。

1.2 网格边 (GridEdge)

class GridEdge {
public:
    GridPoint u, v;  // 两个端点
};

网格边有两种类型：

• 通孔边: 连接不同层的两个网格点
• 线段边: 同一层内连接两个网格点，包括顺线方向和逆线方向

1.3 网格盒 (GridBoxOnLayer)

class GridBoxOnLayer {
public:
    int layerIdx;                      // 金属层索引
    utils::IntervalT<int> trackRange;       // 走线道范围
    utils::IntervalT<int> crossPointRange;  // 交叉点范围
};

用于表示布线引导区域和引脚访问区域在网格图中的范围。

2. 布线网格 (RouteGrid.h/cpp)

RouteGrid是整个详细布线器的核心数据结构，采用两级稀疏存储策略：

2.1 金属层信息存储

// 1. 已布线线段存储
// (layerIdx, trackIdx) -> (crossPointRange, netIdxs)
vector<vector<boost::icl::interval_map<int, std::set<int>>>> routedWireMap;

// 2. 不良线段存储 (由于与引脚/障碍物冲突)
// (layerIdx, trackIdx) -> (crossPointRange, netIdx)
vector<vector<boost::icl::interval_map<int, PoorWire>>> poorWireMap;

// 3. 历史违规线段存储
// (layerIdx, trackIdx) -> (crossPointRange, discountedUsage)
vector<vector<boost::icl::interval_map<int, HistWire>>> histWireMap;

这种存储方式利用了Boost库的区间映射 (interval_map) 来高效存储和查询线段信息。

2.2 通孔信息存储

// (layerIdx, trackIdx) -> (crossPointIdx, netIdx)
ViaMapT routedViaMap;          // 主版本，由下方网格点记录
ViaMapT routedViaMapUpper;     // 由上方网格点记录
NDViaMapT routedNonDefViaMap;  // 非默认通孔映射

2.3 固定金属存储

RTrees fixedMetals;  // box -> netIdx

使用R-tree空间索引结构存储固定的金属障碍物（如单元引脚、阻挡块）。

3. 网格图拓扑 (GridGraph.h)

class GridGraph {
private:
    int edgeCount;

    // 顶点属性
    std::unordered_map<int, int> vertexToPin;  // 顶点索引 -> 引脚索引
    vector<vector<int>> pinToVertex;           // 引脚索引 -> 顶点索引列表
    std::unordered_set<int> fakePins;          // 跨层访问点
    vector<db::GridPoint> vertexToGridPoint;   // 顶点 -> 网格点映射
    vector<bool> minAreaFixable;               // 是否可修复最小面积违规

    // 邻接表
    vector<std::array<int, 6>> conn;           // 6个方向的连接
    vector<db::CostT> vertexCost;              // 顶点代价
    vector<std::array<db::CostT, 6>> edgeCost; // 边代价
};

网格图是一个稀疏图，每个顶点最多有6个方向的边：

• BACKWARD/FORWARD: 顺线方向前后
• UP/DOWN: 层间上下
• LEFT/RIGHT: 逆线方向左右

---

核心算法

1. 布线网格图构建 (GridGraphBuilder.cpp)

1.1 构建流程

run()
├── 1. 为每个网格点分配索引
├── 2. 添加引导-引脚连接
├── 3. 添加引导间连接
├── 4. 添加逆线方向连接
├── 5. 添加引导内连接
└── 6. 设置最小面积标志

1.2 引导内连接

对于每个布线引导盒，添加两种连接：

顺线方向连接:

void connectGuide(int guideIdx) {
    // 沿走线道方向连接相邻交叉点
    // 计算线段代价 = 线长代价 + 违规代价
    // 包括：短路代价、间距代价、历史代价
}

逆线方向连接:

void addRegWrongWayConn(int guideIdx) {
    // 沿垂直于走线道方向连接
    // 使用更高的代价系数来惩罚逆线布线
    int numWrongWayPoint = (cpRange.range() + 1) * wrongWayPointDensity;
    db::CostT wrongWayCost = wrongWayPenaltyCoeff * pitch;
}

逆线方向连接是稀疏添加的，通过wrongWayPointDensity参数控制密度，以平衡搜索空间和布线质量。

1.3 引导间连接

void connectTwoGuides(int guideIdx1, int guideIdx2) {
    // 处理三种连接情况：
    // 1. 同层重叠区域：添加顺线和逆线连接
    // 2. 相邻层：通过通孔连接
    // 3. 通孔代价计算
}

2. 迷宫布线 (MazeRoute.cpp)

2.1 算法流程

run()
├── 1. 构建网格图
├── 2. 初始化优先队列和代价上界
├── 3. 从起始引脚开始Dijkstra搜索
│   ├── 优先队列排序：cost为主，costUB为辅
│   ├── 剪枝：通过代价上界剪枝
│   └── 最小面积惩罚处理
└── 4. 回溯构建Steiner树

2.2 Dijkstra搜索核心

db::RouteStatus MazeRoute::route(int startPin) {
    // 优先队列定义
    auto solComp = [](const auto& lhs, const auto& rhs) {
        return rhs->cost < lhs->cost ||
               (rhs->cost == lhs->cost && rhs->costUB < lhs->costUB);
    };
    std::priority_queue<..., decltype(solComp)> solQueue(solComp);

    // 初始化：从起始引脚的所有访问点开始
    for (auto vertex : graph.getVertices(startPin)) {
        DBU minLen = graph.isFakePin(vertex) ? 0 :
                     database.getLayer(...).getMinLen();
        updateSol(std::make_shared<Solution>(
            graph.getVertexCost(vertex), minLen,
            graph.getVertexCost(vertex), vertex, nullptr));
    }

    // 主循环：依次连接每个引脚
    while (nPinToConnect != 0) {
        // Dijkstra搜索直到到达下一个未访问引脚
        while (!solQueue.empty()) {
            auto newSol = solQueue.top();
            int u = newSol->vertex;
            solQueue.pop();

            // 检查是否到达引脚
            dstPinIdx = graph.getPinIdx(u);
            if (dstPinIdx != -1 && visitedPin.find(dstPinIdx) == visitedPin.end()) {
                dstVertex = newSol;
                break;
            }

            // 剪枝：通过上界剪枝
            if (vertexCostUBs[u] < newSol->cost) continue;

            // 扩展邻居节点
            for (auto direction : directions) {
                if (!graph.hasEdge(u, direction)) continue;

                int v = graph.getEdgeEndPoint(u, direction);

                // 计算新代价
                db::CostT w = graph.getEdgeCost(u, direction) +
                              graph.getVertexCost(v);

                // 最小面积惩罚
                db::CostT penalty = 0;
                if (switchLayer(direction) &&
                    uLayer.hasMinLenVioAcc(newSol->len)) {
                    if (graph.isMinAreaFixable(u))
                        penalty = uLayer.getMinLen() - newSol->len;
                    else
                        penalty = database.getUnitMinAreaVioCost();
                }

                db::CostT newCost = w + newSol->cost + penalty;

                // 上界剪枝
                if (newCost < vertexCostUBs[v]) {
                    updateSol(std::make_shared<Solution>(...));
                }
            }
        }
    }
}

2.3 最小面积捕获路径搜索

这是Dr. CU的核心创新之一。在先进工艺节点中，金属线段有最小长度要求。算法通过以下方式处理：

1. 代价上界剪枝: 每个顶点维护一个代价上界 vertexCostUBs[v]，只有当新路径代价小于上界时才扩展
2. 潜在惩罚计算: 在每个顶点预先计算可能的未来最小面积违规惩罚
3. 正确构造: 通过标记可修复节点，确保找到的路径满足设计规则

3. 多网络布线调度 (Router.cpp & Scheduler.cpp)

3.1 撕开重布线 (Rip-up and Reroute, RRR)

void Router::run() {
    for (iter = 0; iter < rrrIterLimit; iter++) {
        // 1. 获取需要重新布线的网络
        vector<int> netsToRoute = getNetsToRoute();

        if (iter > 0) {
            // 2. 更新历史代价
            updateCost(netsToRoute);

            // 3. 拆除违规网络
            ripup(netsToRoute);
        }

        // 4. 布线所有网络
        route(netsToRoute);
    }

    // 5. 后处理
    finish();
}

3.2 历史代价机制

void Router::updateCost(const vector<int>& netsToRoute) {
    database.addHistCost();        // 添加历史代价
    database.fadeHistCost(netsToRoute);  // 衰减当前重布网络的历史代价
}

历史代价用于避免网络在相同位置重复布线，帮助解决局部最优问题。

3.3 并行调度

void Router::route(const vector<int>& netsToRoute) {
    // 1. 初始化单网络布线器
    vector<SingleNetRouter> routers;
    for (int netIdx : netsToRoute) {
        routers.emplace_back(database.nets[netIdx]);
    }

    // 2. 预布线（可并行）
    runJobsMT(netsToRoute.size(), [&](int netIdx) {
        routers[netIdx].preRoute();
    });

    // 3. 调度：将网络分组为可并行执行的批次
    Scheduler scheduler(routers);
    const vector<vector<int>>& batches = scheduler.schedule();

    // 4. 按批次执行迷宫布线和提交
    for (const vector<int>& batch : batches) {
        // 4.1 迷宫布线（可并行）
        runJobsMT(batch.size(), [&](int jobIdx) {
            routers[batch[jobIdx]].mazeRoute();
        });

        // 4.2 提交到数据库（可并行）
        runJobsMT(batch.size(), [&](int jobIdx) {
            if (db::isSucc(router.status))
                router.commitNetToDB();
        });

        // 4.3 获取通孔类型（可并行）
        runJobsMT(batch.size(), [&](int jobIdx) {
            if (db::isSucc(router.status))
                postRoute.getViaTypes();
        });
    }
}

调度器原理：

• 使用空间R-tree检测网络之间的冲突
• 将不冲突的网络分到同一批次
• 同一批次内的网络可以安全地并行布线
• 不同批次之间需要同步，确保数据一致性

4. 代价计算

4.1 边代价组成

CostT getEdgeCost(const GridEdge& edge, const int netIdx) const {
    // 基础线长代价
    CostT cost = unitWireCost * length;

    // 违规代价
    cost += getEdgeVioCost(edge, netIdx);

    return cost;
}

4.2 违规代价检测

CostT getEdgeVioCost(const GridEdge& edge, const int netIdx,
                     bool histCost = true) const {
    // 1. 短路违规检测
    auto shortUsages = getShortWireSegmentUsageOnOvlpWire(ts, netIdx);

    // 2. 间距违规检测
    auto spaceVioCPs = getWireSegmentSpaceVioOnWires(ts, netIdx);

    // 3. 历史违规
    if (histCost) {
        auto histUsages = getShortWireSegmentUsageOnOvlpHistWire(ts, netIdx);
    }

    // 综合计算违规代价
    return unitWireCost * shortLength +
           unitShortVioCost[layerIdx] * shortVioCount +
           unitSpaceVioCost * spaceVioCount +
           histCost;
}

4.3 通孔代价计算

CostT getViaCost(const GridPoint& via, const int netIdx) const {
    // 基础通孔代价
    CostT cost = unitViaCost;

    // 1. 通孔对通孔违规
    unsigned viaOnViaUsage = getViaUsageOnVias(via, netIdx);

    // 2. 通孔对线段违规
    unsigned viaOnWireUsage = getViaUsageOnWires(via, netIdx);

    // 3. 历史通孔代价
    HistUsageT histUsage = getViaHistUsage(via);

    // 4. 不良通孔检测
    ViaPoorness poorness = getViaPoorness(via, netIdx);

    return cost + violationCost + histCost;
}

---

算法流程图

主流程

                    ┌─────────────────┐
                    │   输入: LEF/    │
                    │   DEF/GUIDES    │
                    └────────┬────────┘
                             │
                             ▼
                    ┌─────────────────┐
                    │   初始化数据库   │
                    │   - 标记引脚     │
                    │   - 标记障碍物   │
                    │   - 切割引导区   │
                    └────────┬────────┘
                             │
                             ▼
                ┌────────────────────────┐
                │  RRR迭代 (rrrIterLimit) │
                └────────────┬───────────┘
                             │
            ┌────────────────┴────────────────┐
            ▼                                 ▼
    ┌───────────────┐                 ┌───────────────┐
    │ iter = 0?     │                 │ iter > 0?     │
    │ 所有网络      │    ◄────────────│ 违规网络      │
    └───────┬───────┘                 └───────┬───────┘
            │                                 │
            ▼                                 ▼
    ┌───────────────┐                 ┌───────────────┐
    │  直接布线     │                 │  更新历史代价  │
    └───────┬───────┘                 └───────┬───────┘
            │                                 │
            │                                 ▼
            │                         ┌───────────────┐
            │                         │  拆除违规网络  │
            │                         └───────┬───────┘
            │                                 │
            └────────────┬────────────────────┘
                         ▼
                ┌───────────────────┐
                │   单网络布线      │
                │   - 构建网格图    │
                │   - 迷宫搜索      │
                │   - 提交结果      │
                └─────────┬─────────┘
                          │
                          ▼
                ┌───────────────────┐
                │   后处理          │
                │   - 最小面积修复  │
                │   - 通孔类型选择  │
                │   - 开路修复      │
                └─────────┬─────────┘
                          │
                          ▼
                ┌───────────────────┐
                │   输出: DEF       │
                └───────────────────┘

单网络布线流程

                ┌───────────────────┐
                │  SingleNetRouter  │
                └─────────┬─────────┘
                          │
            ┌─────────────┼─────────────┐
            ▼             ▼             ▼
    ┌───────────┐ ┌───────────┐ ┌───────────┐
    │ preRoute  │ │ mazeRoute │ │ commitDB  │
    └─────┬─────┘ └─────┬─────┘ └─────┬─────┘
          │             │             │
          ▼             ▼             ▼
    ┌───────────┐ ┌───────────┐ ┌───────────┐
    │ 构建引导  │ │构建网格图 │ │ 更新资源  │
    │ 连接图    │ │ Dijkstra  │ │ 标记占用  │
                │ │ 搜索      │ │ 检测违规  │
                └───────────┘ └───────────┘

迷宫布线流程

                ┌───────────────────┐
                │  MazeRoute::run() │
                └─────────┬─────────┘
                          │
                          ▼
                ┌───────────────────┐
                │ GridGraphBuilder  │
                │ 构建局部网格图     │
                └─────────┬─────────┘
                          │
                ┌─────────┴─────────┐
                ▼                   ▼
    ┌───────────────────┐ ┌───────────────────┐
    │  添加引导内连接   │ │  添加引导间连接   │
    │  - 顺线方向       │ │  - 层间通孔       │
    │  - 逆线方向       │ │  - 同层重叠       │
    └─────────┬─────────┘ └─────────┬─────────┘
              │                       │
              └───────────┬───────────┘
                          ▼
                ┌───────────────────┐
                │   Dijkstra搜索    │
                │                   │
                │ ┌───────────────┐ │
                │ │ 优先队列      │ │
                │ │ PQ<Solution>  │ │
                │ └───────┬───────┘ │
                │         │         │
                │ ┌───────▼───────┐ │
                │ │ 弹出最小cost  │ │
                │ └───────┬───────┘ │
                │         │         │
                │    ┌────┴────┐    │
                │    ▼         ▼    │
                │ ┌────┐   ┌────┐  │
                │ │是引脚? │ │否  │  │
                │ └┬───┘   └┬───┘  │
                │  │         │      │
                │  │    ┌────▼────┐ │
                │  │    │扩展邻居  │ │
                │  │    │-6个方向 │ │
                │  │    │-剪枝    │ │
                │  │    │-更新PQ  │ │
                │  │    └────┬────┘ │
                │  │         │      │
                │  ▼         ▼      │
                │ ┌─────────────┐  │
                │ │ 标记路径为0  │  │
                │ │ 继续搜索    │  │
                │ └─────────────┘  │
                │                   │
                └─────────┬─────────┘
                          │
                          ▼
                ┌───────────────────┐
                │  getResult()      │
                │  回溯构建Steiner树 │
                └───────────────────┘

并行调度流程

                ┌───────────────────┐
                │    所有网络       │
                └─────────┬─────────┘
                          │
                          ▼
                ┌───────────────────┐
                │    预布线阶段     │
                │   (可完全并行)    │
                └─────────┬─────────┘
                          │
                          ▼
                ┌───────────────────┐
                │   调度器分组      │
                │ Scheduler         │
                └─────────┬─────────┘
                          │
              ┌───────────┼───────────┐
              ▼           ▼           ▼
        ┌─────────┐ ┌─────────┐ ┌─────────┐
        │ Batch 0 │ │ Batch 1 │ │ Batch 2 │
        │ 网络1,2 │ │ 网络3,4 │ │ 网络5,6 │
        └────┬────┘ └────┬────┘ └────┬────┘
             │           │           │
             ▼           ▼           ▼
        ┌─────────┐ ┌─────────┐ ┌─────────┐
        │迷宫布线 │ │迷宫布线 │ │迷宫布线 │
        │ 并行执行│ │ 并行执行│ │ 并行执行│
        └────┬────┘ └────┬────┘ └────┬────┘
             │           │           │
             ▼           ▼           ▼
        ┌─────────┐ ┌─────────┐ ┌─────────┐
        │提交DB   │ │提交DB   │ │提交DB   │
        │ 并行执行│ │ 并行执行│ │ 并行执行│
        └────┬────┘ └────┬────┘ └────┬────┘
             │           │           │
             └───────────┼───────────┘
                         ▼
                ┌───────────────────┐
                │   下一批次        │
                └───────────────────┘

---

关键数据流

1. 网络数据流

原始输入 (LEF/DEF)
        │
        ▼
Rsyn解析
        │
        ▼
Net对象
        │
        ├─→ rsynPins: 引脚信息
        ├─→ pinAccessBoxes: 引脚访问盒
        ├─→ routeGuides: 布线引导
        └─→ gridTopo: 网格Steiner树
        │
        ▼
LocalNet对象 (单网络布线)
        │
        ├─→ gridRouteGuides: 网格化的引导
        ├─→ gridPinAccessBoxes: 网格化的访问盒
        ├─→ guideConn: 引导连接图
        └─→ guideAdj: 引领邻接图
        │
        ▼
GridGraph (迷宫搜索)
        │
        ├─→ conn: 邻接表
        ├─→ vertexCost: 顶点代价
        └─→ edgeCost: 边代价
        │
        ▼
GridSteiner树 (布线结果)
        │
        ▼
提交到RouteGrid
        │
        ├─→ routedWireMap: 线段占用
        ├─→ routedViaMap: 通孔占用
        └─→ histWireMap: 历史违规

2. 代价计算流

GridEdge/GridPoint
        │
        ▼
查询RouteGrid
        │
        ├─→ routedWireMap: 已占用线段
        ├─→ poorWireMap: 不良线段
        ├─→ histWireMap: 历史代价
        ├─→ routedViaMap: 已占用通孔
        └─→ fixedMetals: 固定障碍
        │
        ▼
检测违规
        │
        ├─→ 短路: 重叠检查
        ├─→ 间距: 最小间距检查
        ├─→ 通孔违规: Via-on-Via, Via-on-Wire
        └─→ 历史代价: 累加历史违规
        │
        ▼
计算总代价
        │
        ├─→ wireCost = unitWireCost × length
        ├─→ viaCost = unitViaCost + violationCost
        ├─→ shortCost = unitShortVioCost × count
        ├─→ spaceCost = unitSpaceVioCost × count
        └─→ histCost = histUsage × coeff
        │
        ▼
返回总CostT

---

核心算法伪代码

1. 迷宫布线算法

def maze_routing(start_pin, all_pins, grid_graph):
    """
    改进的Dijkstra算法，用于连接多个引脚
    """
    # 初始化
    priority_queue = PriorityQueue()
    vertex_cost_ub = {v: infinity for v in grid_graph.vertices}
    pin_solutions = {}
    visited_pins = {start_pin}

    # 从起始引脚的所有访问点开始
    for vertex in grid_graph.get_pin_vertices(start_pin):
        cost = grid_graph.get_vertex_cost(vertex)
        min_len = get_min_length(vertex)
        priority_queue.push(Solution(cost, min_len, cost, vertex, None))
        vertex_cost_ub[vertex] = cost

    # 依次连接每个引脚
    while len(visited_pins) < len(all_pins):
        dst_vertex = None
        dst_pin = None

        # Dijkstra主循环
        while not priority_queue.empty():
            current = priority_queue.pop()
            u = current.vertex

            # 检查是否到达新引脚
            pin_idx = grid_graph.get_pin_index(u)
            if pin_idx is not None and pin_idx not in visited_pins:
                dst_vertex = current
                dst_pin = pin_idx
                break

            # 上界剪枝
            if vertex_cost_ub[u] < current.cost:
                continue

            # 扩展6个方向的邻居
            for direction in [BACKWARD, FORWARD, UP, DOWN, LEFT, RIGHT]:
                if not grid_graph.has_edge(u, direction):
                    continue

                v = grid_graph.get_edge_end(u, direction)

                # 计算新代价
                edge_cost = grid_graph.get_edge_cost(u, direction)
                vertex_cost = grid_graph.get_vertex_cost(v)
                new_cost = current.cost + edge_cost + vertex_cost

                # 最小面积惩罚
                penalty = 0
                if is_layer_change(direction):
                    if has_min_area_violation(current.length):
                        if is_min_area_fixable(u):
                            penalty = get_min_length() - current.length
                        else:
                            penalty = UNIT_MIN_AREA_VIO_COST

                new_cost += penalty

                # 计算新的长度
                new_length = compute_new_length(current, u, v)

                # 计算潜在惩罚
                potential_penalty = 0
                if has_min_area_violation(new_length):
                    if is_min_area_fixable(v):
                        potential_penalty = get_min_length() - new_length
                    else:
                        potential_penalty = UNIT_MIN_AREA_VIO_COST

                cost_upper_bound = new_cost + potential_penalty

                # 更新
                if new_cost < vertex_cost_ub[v]:
                    priority_queue.push(
                        Solution(new_cost, new_length, cost_upper_bound, v, current)
                    )
                    vertex_cost_ub[v] = new_cost

        # 找到下一个引脚的连接路径
        if dst_vertex is None:
            return FAIL_DISCONNECTED

        pin_solutions[dst_pin] = dst_vertex

        # 将路径上的顶点代价设为0（Steiner点）
        temp = dst_vertex
        while temp is not None and temp.cost != 0:
            min_len = get_min_length(temp.vertex)
            priority_queue.push(Solution(0, min_len, 0, temp.vertex, temp.prev))
            temp = temp.prev

        # 标记目标引脚的所有访问点
        for vertex in grid_graph.get_pin_vertices(dst_pin):
            if vertex != dst_vertex.vertex:
                cost = grid_graph.get_vertex_cost(vertex)
                min_len = get_min_length(vertex)
                priority_queue.push(Solution(cost, min_len, cost, vertex, None))

        visited_pins.add(dst_pin)

    # 回溯构建Steiner树
    return build_steiner_tree(pin_solutions)

2. RRR主流程

def ripup_and_reroute(all_nets, max_iterations=10):
    """
    撕开重布线主流程
    """
    database = initialize_database(all_nets)

    for iteration in range(max_iterations):
        print(f"RRR Iteration {iteration}")

        # 1. 获取需要布线的网络
        if iteration == 0:
            nets_to_route = all_nets  # 首次迭代：所有网络
        else:
            # 后续迭代：只处理有违规的网络
            nets_to_route = [net for net in all_nets
                           if check_violation(net)]

        if not nets_to_route:
            break  # 没有违规，完成

        # 2. 更新历史代价
        if iteration > 0:
            database.add_history_cost()
            database.fade_history_cost(nets_to_route)

        # 3. 拆除违规网络的布线
        if iteration > 0:
            for net in nets_to_route:
                ripup_net(net)

        # 4. 重新布线
        route_nets(nets_to_route)

    # 5. 后处理
    post_route(all_nets)
    write_def("output.def")

def route_nets(nets):
    """
    并行布线多个网络
    """
    # 1. 初始化单网络布线器
    routers = [SingleNetRouter(net) for net in nets]

    # 2. 预布线（可并行）
    parallel_execute([router.pre_route for router in routers])

    # 3. 调度：分组网络
    scheduler = Scheduler(routers)
    batches = scheduler.schedule()

    # 4. 按批次布线
    for batch in batches:
        # 4.1 迷宫布线（并行）
        parallel_execute([routers[i].maze_route for i in batch])

        # 4.2 提交到数据库（并行）
        parallel_execute([routers[i].commit for i in batch])

        # 4.3 选择通孔类型（并行）
        parallel_execute([select_via_types(routers[i].db_net) for i in batch])

3. 调度算法

def schedule_networks(routers):
    """
    将网络分组为可并行执行的批次
    """
    rtrees = build_spatial_rtrees()

    unassigned = set(range(len(routers)))
    batches = []

    while unassigned:
        current_batch = []

        for net_idx in list(unassigned):
            # 检查与当前批次是否冲突
            if not has_conflict(routers[net_idx], current_batch, rtrees):
                current_batch.append(net_idx)
                unassigned.remove(net_idx)
                # 更新空间索引
                update_rtree(rtrees, routers[net_idx])

        batches.append(current_batch)

    return batches

def has_conflict(router, batch, rtrees):
    """
    检查网络是否与批次中任何网络冲突
    """
    net_boxes = get_network_bounding_boxes(router.db_net)

    for net_idx in batch:
        batch_boxes = get_bounding_boxes(rtrees, net_idx)

        # 检查空间重叠
        for box1 in net_boxes:
            for box2 in batch_boxes:
                if boxes_overlap(box1, box2):
                    return True  # 有冲突，不能并行

    return False  # 无冲突，可以并行

---

设计规则处理

1. 最小面积规则

// 检查最小面积违规
bool hasMinLenVioAcc(DBU currentLen) {
    return currentLen < getMinLen();
}

// 处理最小面积违规
if (switchLayer(direction) && uLayer.hasMinLenVioAcc(newSol->len)) {
    if (graph.isMinAreaFixable(u) || dstPinIdx != -1) {
        // 可以修复：添加长度惩罚
        penalty = uLayer.getMinLen() - newSol->len;
    } else {
        // 无法修复：添加巨大的违规代价
        penalty = database.getUnitMinAreaVioCost();
    }
}

2. 间距规则

// 检测间距违规
vector<int> getWireSegmentSpaceVioOnWires(const TrackSegment& ts, int netIdx) {
    vector<int> vioCPs;

    // 遍历线段上的每个交叉点
    iterateWireSegments(ts, netIdx, [&](const auto& interval, int usage) {
        if (usage > 0) {
            // 检查间距
            if (get_spacing() < min_spacing) {
                vioCPs.push_back(interval.low);
                vioCPs.push_back(interval.high);
            }
        }
    });

    return vioCPs;
}

3. 通孔规则

// 检查通孔违规
int getViaFixedVio(const GridPoint& via, const ViaType& viaType, int netIdx) {
    int vio = 0;

    // 1. 通孔对固定金属的违规
    BoxOnLayer viaBox = get_via_box(via, viaType);
    vio += getFixedMetalVio(viaBox.lower, netIdx);
    vio += getFixedMetalVio(viaBox.upper, netIdx);

    // 2. 通孔对通孔的违规
    vio += getViaUsageOnVias(via, netIdx, &viaType);

    // 3. 通孔对线段的违规
    vio += getViaUsageOnWires(via, netIdx, &viaType);

    return vio;
}

---

性能优化技术

1. 稀疏存储

// 使用区间映射存储线段，只存储有占用位置
vector<vector<boost::icl::interval_map<int, std::set<int>>>> routedWireMap;

// 优势：
// 1. 空间高效：空轨道不占用存储
// 2. 查询快速：O(log n)区间查询
// 3. 合并方便：自动合并相邻区间

2. 上界剪枝

// 每个顶点维护最小代价上界
vector<db::CostT> vertexCostUBs;

// 剪枝条件
if (vertexCostUBs[u] < newSol->cost) {
    continue;  // 跳过劣质解
}

// 效果：
// - 显著减少搜索空间
// - 加速收敛

3. 并行化

// 使用线程池并行执行独立任务
MTStat runJobsMT(int numJobs, const std::function<void(int)>& handle) {
    vector<std::thread> threads;
    vector<double> durations(numThreads, 0.0);

    for (int t = 0; t < numThreads; ++t) {
        threads.emplace_back([&, t]() {
            auto t0 = std::chrono::high_resolution_clock::now();

            for (int j = t; j < numJobs; j += numThreads) {
                handle(j);
            }

            auto t1 = std::chrono::high_resolution_clock::now();
            durations[t] = std::chrono::duration<double>(t1 - t0).count();
        });
    }

    for (auto& th : threads) {
        th.join();
    }

    return MTStat(durations);
}

4. 批处理同步

// 通过批次划分减少同步开销
for (const auto& batch : batches) {
    // 批次内并行执行
    runJobsMT(batch.size(), [&](int jobIdx) {
        // 无锁操作
        routers[batch[jobIdx]].mazeRoute();
    });

    // 批次间同步（较少发生）
    #pragma omp barrier
}

---

总结

Dr. CU详细布线工具的核心设计思想：

1. 稀疏化: 通过两级稀疏数据结构和稀疏网格图，大幅降低内存占用和计算复杂度

2. 正确构造: 最小面积捕获路径搜索确保生成满足设计规则的布线解

3. 迭代优化: RRR框架配合历史代价机制，逐步优化布线质量

4. 并行加速: 智能调度器识别可并行网络，最大化多核利用率

这些技术的结合使得Dr. CU能够在先进工艺节点的复杂设计规则下，高效地完成详细布线任务。