EDA 中的 PlaceRoute 流程——Route 概述

目录

• Route 概述
  • Route 相关概念
• Global Route
• Detail Route
• 基础布线算法
  • BFS
  • 拓扑排序

Route 概述

通常当芯片完成时钟树综合后，就进入了 Route 阶段，对应下图 PR Flow 中 Routing and postroute optimization 这步。
Route 的目的是将芯片中所有的宏单元，标准单元以及输入输出端口等按照其逻辑关系互连，同时还伴随时序，功耗，拥塞，信号完整性，DRC，DFM 等的优化。
通常时钟信号有较高的优先级，在 CTS 阶段已经完成布线，Routing 阶段完成普通逻辑信号的布线。

PR Flow 与 Route Flow

Route 相关概念

1. Grid point：成阵列均匀分布在芯片区域的一系列虚拟的布线参考格点；
2. Track：横向或纵向穿过 grid 的一系列虚拟的线；
3. Pitch：相邻两条 track 的间距；
4. Trace：以 track 为线道的实际金属布线，trace 的中心和 track 重合；
5. Global routing cell(Gcell)：布线区域被均匀地分割成的一系列紧挨着的虚拟小方格。

Route 大致可以分为 global route、track assignment、detail route 等步骤。

1. Global route：基于避免拥塞，减小线长等原则为需要布线的信号分配合适的 Gcells 进行虚拟的连接;
2. Track assignment：在 global route 的基础上分配具体的 track 并布上实际的金属线；
3. Detail route：在 track assignment 阶段布线的基础上修复 DRC 等；
4. Search and repair：通过 Subbox 扫描布线区域不断修复剩余 DRC 等问题。

GlobalRoute

TrackAssignment

Global Route

GlobalRoute 对所有的线网在粗粒度的网格图上进行布线, 确定所有线网的大概走线，即对每条线网进行布线区域的分配。
首先将布线区域构建出图的模型，然后将所有 Net 分配到对应的图模型数据，最后按照最小化所有 Net 走向的溢出值。如下图所示， GR 实际上是在分配 GCell 上的布线资源，所以必须要保证 GCell 的使用量不超过 GCell 实际的容量，避免出现 overflow。

单层 GCell 构图

多层 GCell 构图

布线方向

overflow region

Detail Route

Detail Route 阶段会将 GCell 内分配的 wire 按要求连接，连接时需要遵循一些设计规则（Design Rule），保证在 route 结束后，设计规则检查（Design Rule Check）清零。

DR 效果示意图

不同工艺的布线层资源与效果

基础设计规则

基础布线算法

detail route 过程类似寻找两点之间的最短路径，其实现也是基于相关算法。

BFS

迷宫算法的基础是广度优先搜索（BFS），以下图为例说明。我们的目标是寻找从 S 到 T 的最小路径：可以先通过广度优先搜索可以确定几条同等优势的路径，然后从最优的几条路径中选择其中一条。

BFS

拓扑排序

拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

1. 每个顶点出现且只出现一次；
2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

通过如下步骤可以得到一个 DAG 图的拓扑排序：

1. 从图中选择一个入度为 0 的顶点并输出；
2. 从图中删除该顶点和所有以它为起点的有向边；
3. 重复步骤 1 和 2，直到当前 DAG 为空，或者当前图中不存在无前驱顶点为止（此时说明 DAG 中存在一个环）。

拓扑排序

从拓扑排序开始推广，可以得到其他相关算法：

相关算法