【agent辅助pcb routing coding学习】实践8 bga fanout 算法学习
·
BGA Fanout 算法
1. 算法概述
1.1 目的
BGA Fanout 算法用于为BGA（球栅阵列）封装的芯片自动创建扇出走线，将内部焊盘的信号通过布线通道引导到BGA边界外，为后续的完整布线做准备。
1.2 核心思想
- 45度扇出: 从每个焊盘以45度角引出短线(stub)连接到布线通道
- 通道布线: 沿水平或垂直通道将信号引导到BGA边界
- 层分配: 智能分配不同层以避免同一通道内的走线冲突
- 差分对支持: 自动识别并成对路由差分信号
2. 算法输入与输出
2.1 输入参数
| 参数 | 类型 | 说明 |
|---|---|---|
footprint | Footprint | BGA封装的焊盘信息 |
pcb_data | PCBData | 完整PCB数据（包含现有走线） |
net_filter | List[str] | 可选：要包含的网络模式过滤列表 |
diff_pair_patterns | List[str] | 可选：差分对网络匹配模式（如 *lvds*） |
layers | List[str] | 可用布线层列表（默认 ['F.Cu', 'B.Cu']） |
track_width | float | 走线宽度（mm，默认0.1） |
clearance | float | 最小间距（mm，默认0.1） |
diff_pair_gap | float | 差分对P/N间距（mm，默认0.101） |
exit_margin | float | BGA边界外的延伸距离（mm，默认0.5） |
primary_escape | str | 主要逃逸方向（‘horizontal’或’vertical’） |
via_size | float | 过孔外径（mm，默认0.5） |
via_drill | float | 过孔钻孔直径（mm，默认0.3） |
check_for_previous | bool | 是否检查并跳过已有扇出的焊盘 |
no_inner_top_layer | bool | 是否禁止内部焊盘使用顶层（F.Cu） |
2.2 输出结果
| 返回值 | 类型 | 说明 |
|---|---|---|
tracks | List[Dict] | 扇出走线段列表，每个包含： |
- start: 起点坐标 (x, y) | ||
- end: 终点坐标 (x, y) | ||
- width: 走线宽度 | ||
- layer: 层名 | ||
- net_id: 网络ID | ||
vias_to_add | List[Dict] | 需要添加的过孔列表 |
vias_to_remove | List[Dict] | 需要移除的过孔列表 |
3. 算法流程
3.1 主流程 generate_bga_fanout()
┌─────────────────────────────────────────────────────────────────┐
│ generate_bga_fanout │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ Step 1: 分析BGA网格结构 │
│ - 分析焊盘位置提取网格参数 │
│ - 计算 X/Y 方向的间距 (pitch_x, pitch_y) │
│ - 识别行和列的位置 │
│ - 计算边界和中心点 │
│ - 计算布线通道（位于行/列之间） │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ Step 2: 检查已有扇出（可选） │
│ if check_for_previous: │
│ - 扫描现有走线识别已扇出的网络 │
│ - 记录被占用的出口位置 │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ Step 3: 识别差分对 │
│ if diff_pair_patterns: │
│ - 根据网络名模式匹配差分对 │
│ - 验证P/N焊盘位置关系（相邻） │
│ - 预分配逃逸方向以避免重叠 │
│ - 计算是否需要相邻通道布线 │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ Step 4: 为每个焊盘创建路由 │
│ for pad in footprint.pads: │
│ - 跳过未连接的焊盘 │
│ - 跳过已扇出的焊盘（如果启用） │
│ - 判断是否为差分对的一部分 │
│ ┌─────────────┐ │
│ │是差分对？ │ │
│ └─────────────┘ │
│ │ │ │
│ 是 否 │
│ │ │ │
│ ▼ ▼ │
│ 处理差分对 create_single_ended_route() │
│ (P/N一起) (单端信号路由) │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ Step 5: 连接相邻同网络焊盘 │
│ - 检测同网络且相邻的焊盘 │
│ - 直接连接它们而不单独扇出到边界 │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ Step 6: 通道上焊盘重分配 │
│ - 检测位于通道上的焊盘（零长度stub） │
│ - 如果直线路径被其他焊盘阻挡 │
│ → 重新分配到相邻通道并添加45度绕行 │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ Step 7: 智能层分配 │
│ assign_layers_smart(): │
│ - 边缘焊盘 → 顶层 (F.Cu) │
│ - 差分对 → 同一层（避免层间不匹配） │
│ - 内部焊盘 → 按通道+方向分组 │
│ - 避免同通道内的走线重叠 │
│ - 检查与现有走线的冲突 │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ Step 8: 计算出口折角（Jog） │
│ calculate_jog_ends_for_routes(): │
│ - 计算BGA边缘到首排焊盘的距离 │
│ - 为每条路由计算出口处的45度折角 │
│ - 差分对外侧走线延伸以保持恒定间距 │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ Step 9: 生成走线段 │
│ generate_tracks_from_routes(): │
│ - 将路由对象转换为走线段字典 │
│ - 边缘焊盘：直接水平/垂直走线 │
│ - 内部焊盘：45度stub + 通道走线 + 折角 │
│ - 差分对：特殊处理以保持恒定间距 │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ Step 10: 碰撞检测与解决 │
│ detect_collisions(): │
│ - 检测新走线之间的冲突 │
│ - 检测与现有走线的冲突 │
│ if 发现冲突: │
│ resolve_collisions(): │
│ - 尝试重新分配层 │
│ - 尝试使用备用通道 │
│ - 失败的网络从输出中移除 │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ Step 11: 层重平衡（可选） │
│ if collisions_remaining == 0 and len(layers) > 1: │
│ rebalance_layers(): │
│ - 在各层之间均匀分配走线 │
│ - 改善层利用率 │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ Step 12: 过孔管理 │
│ manage_vias(): │
│ - 为非顶层走线的SMD焊盘添加过孔 │
│ - 移除顶层走线上不必要的过孔 │
│ - 通孔焊盘不需要过孔（已连接所有层） │
└─────────────────────────────────────────────────────────────────┘
│
▼
返回 (tracks, vias_to_add, vias_to_remove)
3.2 BGA网格分析 analyze_bga_grid()
┌─────────────────────────────────────────────────────────────────┐
│ analyze_bga_grid │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 提取焊盘坐标 │
│ x_positions = sorted(set(pad.global_x for pad in pads)) │
│ y_positions = sorted(set(pad.global_y for pad in pads)) │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 计算间距 │
│ x_diffs = [x_positions[i+1] - x_positions[i] for ...] │
│ y_diffs = [y_positions[i+1] - y_positions[i] for ...] │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 确定主导间距 │
│ - 四舍五入到0.01mm精度 │
│ - 统计每个间距值的出现次数 │
│ - 选择出现次数 >50% 的间距值作为主导间距 │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 返回 BGAGrid 对象: │
│ - pitch_x, pitch_y: X/Y方向间距 │
│ - rows: Y坐标列表（行） │
│ - cols: X坐标列表（列） │
│ - center_x, center_y: BGA中心 │
│ - min/max_x/y: 边界（扩展±pitch/2） │
└─────────────────────────────────────────────────────────────────┘
3.3 通道计算 calculate_channels()
┌─────────────────────────────────────────────────────────────────┐
│ calculate_channels │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 创建水平通道（行之间） │
│ for i in range(len(rows) - 1): │
│ y_pos = (rows[i] + rows[i+1]) / 2 │
│ channels.append(Channel(orientation='horizontal', │
│ position=y_pos, index=idx)) │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 创建垂直通道（列之间） │
│ for i in range(len(cols) - 1): │
│ x_pos = (cols[i] + cols[i+1]) / 2 │
│ channels.append(Channel(orientation='vertical', │
│ position=x_pos, index=idx)) │
└─────────────────────────────────────────────────────────────────┘
通道示意图：
焊盘布局：
. . . . (行)
● ● │ ● ●
────┼────── ← 水平通道 (在行之间)
● ● │ ● ●
────┼──────
● ● │ ● ●
垂直通道 ↓ ↓ ↓ (在列之间)
3.4 焊盘分类 is_edge_pad()
┌─────────────────────────────────────────────────────────────────┐
│ is_edge_pad │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 检查焊盘是否在边界行/列 │
│ on_left = |pad_x - grid.cols[0]| < tolerance │
│ on_right = |pad_x - grid.cols[-1]| < tolerance │
│ on_top = |pad_y - grid.rows[0]| < tolerance │
│ on_bottom = |pad_y - grid.rows[-1]| < tolerance │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 返回 (is_edge, escape_direction) │
│ - 边缘焊盘：返回True和逃逸方向 │
│ - 内部焊盘：返回False和空字符串 │
└─────────────────────────────────────────────────────────────────┘
3.5 逃逸通道查找 find_escape_channel()
┌─────────────────────────────────────────────────────────────────┐
│ find_escape_channel (单端信号) │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────┐
│ 是边缘焊盘？ │
└─────────────────┘
│ │
是 否
│ │
▼ ▼
返回 (None, 计算到各边缘的距离
edge_dir) dist_left/right/up/down
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 构建选项列表 (距离, 方向, 方向性) │
│ options = [ │
│ (dist_left, 'left', 'horizontal'), │
│ (dist_right, 'right', 'horizontal'), │
│ (dist_up, 'up', 'vertical'), │
│ (dist_down, 'down', 'vertical') │
│ ] │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 按距离排序（最近的边优先） │
│ options.sort(key=lambda x: x[0]) │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 遍历选项，找到可用通道 │
│ for dist, escape_dir, orientation in options: │
│ if orientation == 'horizontal': │
│ best = closest_horizontal_channel_to(pad_y) │
│ else: │
│ best = closest_vertical_channel_to(pad_x) │
│ if best found: │
│ return (best, escape_dir) │
└─────────────────────────────────────────────────────────────────┘
3.6 45度Stub生成 create_45_stub()
┌─────────────────────────────────────────────────────────────────┐
│ create_45_stub │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────┐
│ 水平通道？ │
└─────────────────┘
│ │
是 否
│ │
▼ ▼
┌──────────────────────────┐ ┌──────────────────────────┐
│ 目标Y = channel.position │ │ 目标X = channel.position │
│ + offset │ │ + offset │
│ │ │ │
│ dy = target_y - pad_y │ │ dx = target_x - pad_x │
│ │ │ │
│ 保持45度角: dx = |dy| │ │ 保持45度角: dy = |dx| │
│ │ │ │
│ 根据逃逸方向确定dx符号: │ │ 根据逃逸方向确定dy符号: │
│ right: dx = +|dy| │ │ down: dy = +|dx| │
│ left: dx = -|dy| │ │ up: dy = -|dx| │
└──────────────────────────┘ └──────────────────────────┘
│ │
└─────┬─────┘
│
▼
返回 (pad_x + dx, pad_y + dy)
或 (target_x, pad_y + dy)
45度Stub示例：
水平通道情况：
┌─────────────────────────────────
│ 通道中心线 (channel.position)
└─────────────────────────────────
↑
│ dy_to_target
│
●─────────────────────┘ 45度角
pad
└─→ dx = |dy| (向右逃逸)
3.7 差分对处理
3.7.1 差分对识别
┌─────────────────────────────────────────────────────────────────┐
│ find_differential_pairs() │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 解析差分对模式 │
│ 示例模式: "*_P", "*_N" 或 "*_LVDS_P", "*_LVDS_N" │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 匹配P/N网络对 │
│ for net_name in footprint网络: │
│ if 匹配P模式: │
│ 查找对应的N网络 │
│ if找到: │
│ 验证焊盘位置（应该相邻） │
│ 创建 DiffPairPads 记录 │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 返回差分对字典: │
│ {pair_id: DiffPairPads(p_pad, n_pad, pair_id)} │
└─────────────────────────────────────────────────────────────────┘
3.7.2 差分对逃逸分配
┌─────────────────────────────────────────────────────────────────┐
│ assign_pair_escapes() │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 按到最近边缘的距离排序（最近的优先处理） │
│ - 最近的边缘对选择最少 │
│ - 需要先分配以避免被占 │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 对每对差分对: │
│ ┌──────────────────────────────────────────────────────────┐ │
│ │ 1. 尝试主要方向 (primary_orientation) │ │
│ │ 2. 检查通道和层是否可用 │ │
│ │ 3. 如果被占用，尝试次要方向 │ │
│ │ 4. 标记出口位置为已占用 │ │
│ └──────────────────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 特殊处理: │
│ - 边缘对：直接使用边缘方向 │
│ - 半边缘对：一边直出，一边绕行 │
│ - 内部对：通过通道逃逸 │
└─────────────────────────────────────────────────────────────────┘
3.7.3 相邻通道判断
┌─────────────────────────────────────────────────────────────────┐
│ 判断是否需要相邻通道布线 │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 计算差分对参数: │
│ half_pair_spacing = (track_width + diff_pair_gap) / 2 │
│ via_radius = via_size / 2 │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 计算最大允许偏移: │
│ 水平逃逸（左/右）→ 受pitch_y约束 │
│ max_offset_h = pitch_y/2 - via_radius - width/2 - clearance │
│ │
│ 垂直逃逸（上/下）→ 受pitch_x约束 │
│ max_offset_v = pitch_x/2 - via_radius - width/2 - clearance │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 判断: │
│ use_adjacent_channels_h = (half_pair_spacing > max_offset_h) │
│ use_adjacent_channels_v = (half_pair_spacing > max_offset_v) │
└─────────────────────────────────────────────────────────────────┘
相邻通道布线示意：
同一通道内布线（间距足够）：
←─spacing──→
───P─────────channel─────────
───N─────────channel─────────
(P和N在通道内偏移)
相邻通道布线（间距不足）：
←pitch→
● ● via via
│ │
──┼──channel 1──P────────
│ │
──┼──channel 2──N────────
(P和N各占一个通道，都居中)
3.8 智能层分配 assign_layers_smart()
┌─────────────────────────────────────────────────────────────────┐
│ assign_layers_smart() │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 初始化: │
│ - 边缘焊盘 → F.Cu（顶层） │
│ - 半边缘差分对 → 全部F.Cu │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 分组内部焊盘: │
│ 按 (channel_index, escape_dir) 分组 │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 对每组: │
│ ┌──────────────────────────────────────────────────────────┐ │
│ │ 1. 按通道上的位置排序（从内到外或从外到内） │ │
│ │ 2. 贪心层分配： │ │
│ │ for route in group_routes: │ │
│ │ if 差分对已分配 → 使用相同层 │ │
│ │ for layer in candidate_layers: │ │
│ │ if 与本组已分配走线无冲突: │ │
│ │ if 与边缘走线无交叉冲突: │ │
│ │ if 与现有走线无冲突: │ │
│ │ route.layer = layer │ │
│ │ if 差分对: 分配partner到同层 │ │
│ │ break │ │
│ └──────────────────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────────────────┘
3.9 走线生成 generate_tracks_from_routes()
┌─────────────────────────────────────────────────────────────────┐
│ generate_tracks_from_routes() │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────┐
│ 邻居连接？ │
└─────────────────┘
│ │
是 否
│ │
▼ ▼
┌────────────────┐ ┌─────────────────────┐
│直接连接段 │ │ 边缘焊盘？ │
│pad→exit │ ｜ │
└────────────────┘ └─────────────────────┘
│ │
是 否
│ │
▼ ▼
┌──────────────┐ ┌──────────────────┐
│直接/收敛 │ │45°stub + 通道 │
│+ jog │ │+ jog │
└──────────────┘ └──────────────────┘
边缘焊盘走线生成：
单端边缘:
pad ───────────────────→ exit
│
└─→ jog_end (45度折角)
差分边缘（收敛）:
pad_P ──→ stub_end ────────→ exit ──→ jog_end
45° │
└─→ jog_end (外侧延伸)
pad_N ──→ stub_end ────────→ exit ──→ jog_end
45°
内部焊盘走线生成：
正常内部:
pad ───→ stub_end ──────────→ exit ──→ jog_end
45° (通道走线)
半边缘内部（帐篷形）:
pad ───→ channel_pt ───→ channel_pt2 ──→ stub_end ──→ exit ──→ jog_end
45° (通道内) (返回)
通道上焊盘（重分配后）:
pad
│
└─→ pre_channel_jog (45度绕行)
│
└─→ exit ──→ jog_end
3.10 碰撞检测 detect_collisions()
┌─────────────────────────────────────────────────────────────────┐
│ detect_collisions() │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 初始化: │
│ collision_count = 0 │
│ collision_pairs = [] │
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 双重循环检查: │
│ for i, t1 in enumerate(tracks): │
│ for t2 in tracks[i+1:]: │
│ ┌────────────────────────────────────────────────────────┐│
│ │ if 不同层: 跳过 ││
│ │ if 相同网络: 跳过 ││
│ │ if 同一差分对: 跳过 ││
│ │ if check_segment_collision(): ││
│ │ collision_count += 1 ││
│ │ if len < max: collision_pairs.append((t1, t2)) ││
│ └────────────────────────────────────────────────────────┘│
└─────────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────┐
│ 同样检查现有走线: │
│ for t1 in tracks: │
│ for t2 in existing_tracks: │
│ ... (相同检查逻辑) │
└─────────────────────────────────────────────────────────────────┘
│
▼
返回 (collision_count, collision_pairs)
4. 关键数据结构
4.1 BGAGrid
@dataclass
class BGAGrid:
pitch_x: float # X方向间距
pitch_y: float # Y方向间距
rows: List[float] # 行的Y坐标列表
cols: List[float] # 列的X坐标列表
center_x: float # 中心X坐标
center_y: float # 中心Y坐标
min_x: float # 边界最小X
max_x: float # 边界最大X
min_y: float # 边界最小Y
max_y: float # 边界最大Y
4.2 Channel
@dataclass
class Channel:
orientation: str # 'horizontal' 或 'vertical'
position: float # 通道位置坐标（Y或X）
index: int # 通道索引
4.3 FanoutRoute
@dataclass
class FanoutRoute:
pad: Pad # 焊盘对象
pad_pos: Tuple[float, float] # 焊盘位置
stub_end: Tuple[float, float] # 45度stub终点
exit_pos: Tuple[float, float] # BGA边界出口位置
channel: Channel # 使用的通道（None表示边缘）
escape_dir: str # 逃逸方向
is_edge: bool # 是否为边缘焊盘
layer: str # 分配的层
pair_id: str # 差分对ID（None表示单端）
is_p: bool # 是否为P信号（差分对）
jog_end: Tuple # 折角终点
jog_extension: Tuple # 差分对外侧延伸点
channel_point: Tuple # 半边缘绕行的第一个通道点
channel_point2: Tuple # 半边缘绕行的第二个通道点
pre_channel_jog: Tuple # 通道上焊盘的重分配绕行点
neighbor_connection: bool # 是否为邻居连接
4.4 DiffPairPads
@dataclass
class DiffPairPads:
p_pad: Pad # 正相信号焊盘
n_pad: Pad # 反相信号焊盘
pair_id: str # 差分对唯一标识
is_complete: bool # 是否完整（P和N都存在）
5. 算法原理
5.1 45度扇出原理
为什么使用45度？
- 电磁兼容性: 45度拐角比90度拐角反射更小
- 阻抗连续: 45度拐角能更好地保持特性阻抗
- 制造友好: 45度拐角比圆角更容易制造
- 空间效率: 在紧凑的BGA间距内最大化走线空间
45度Stub的几何关系：
真45度角的特性：|dx| = |dy|
焊盘 (pad_x, pad_y)
│
│ dy
│
└──────────→ 通道
dx
其中: |dx| = |dy| (保证45度)
5.2 通道布线原理
通道的作用：
- 在BGA焊盘阵列之间提供可布线空间
- 避免与焊盘和过孔冲突
- 通道位于行/列的正中间
通道选择策略：
对于内部焊盘:
1. 计算到四个边缘的距离
2. 选择最近的边缘方向
3. 在该方向上找到最近的通道
4. 45度stub连接到该通道
5.3 层分配策略
层分配原则：
- 边缘焊盘优先: 边缘焊盘信号最短，放在顶层
- 差分对同层: P/N必须在同一层以保持时序匹配
- 避免冲突: 同通道内使用不同层避免重叠
- 均匀分配: 各层走线数量尽量均衡
层分配算法：
贪心策略:
1. 按通道+方向分组
2. 每组内按位置排序
3. 依次为每条走线分配可用层
4. 检查与已分配走线的冲突
5. 选择第一个无冲突的层
5.4 差分对特殊处理
差分对要求：
- 等长: P和N走线长度相等
- 等间距: 全程保持恒定间距
- 同层: 必须在同一层布线
- 最小反射: 拐角处外侧走线需延伸
外侧延伸计算：
45度拐角处外侧延伸 = pair_spacing × (√2 - 1)
≈ pair_spacing × 0.414
这样可保持拐角前后的垂直间距不变
示例：
拐角前: ────P 走线平行，间距 = d
│
N
拐角处: ──┐P
└──┐
N
外侧延伸 = 0.414×d
拐角后: │P
│ 走线平行，间距 = d
N───
5.5 碰撞检测原理
线段碰撞检测：
两线段 (p1, p2) 和 (p3, p4) 的碰撞判断:
1. 包围盒检查（快速排除）:
if max(min(x)) < min(max(x)) and max(min(y)) < min(max(y)):
可能碰撞，继续详细检查
else:
无碰撞
2. 距离检查（精确判断）:
计算两线段之间的最小距离
if distance < min_spacing:
碰撞
else:
无碰撞
6. 配置参数
| 参数 | 默认值 | 说明 |
|---|---|---|
track_width | 0.1mm | 扇出走线宽度 |
clearance | 0.1mm | 最小间距 |
diff_pair_gap | 0.101mm | 差分对间距 |
via_size | 0.5mm | 过孔外径 |
via_drill | 0.3mm | 过孔钻孔 |
exit_margin | 0.5mm | BGA边界外延伸 |
primary_escape | ‘horizontal’ | 首选逃逸方向 |
force_escape_direction | False | 强制方向 |
rebalance_escape | False | 重平衡逃逸分配 |
7. 边界情况处理
7.1 小间距BGA
- 使用相邻通道布线
- 每条差分线各占一个通道
- 避免间距不足导致的冲突
7.2 已有扇出
- 检测现有走线
- 跳过已扇出的网络
- 避免占用的出口位置
7.3 边缘焊盘冲突
- 垂直逃逸可能水平边缘走线冲突
- 优先分配不同层
- 检测交叉点并调整
7.4 通孔焊盘
- 通孔焊盘已连接所有层
- 不需要添加过孔
- 仍然阻挡所有层的走线
8. 性能考虑
8.1 时间复杂度
- 网格分析: O(N)，N为焊盘数量
- 差分对匹配: O(N²)，N为焊盘数量
- 逃逸分配: O(M×K)，M为差分对数，K为通道数
- 层分配: O(R²×L)，R为路由数，L为层数
- 碰撞检测: O(T²)，T为走线段数量
- 总复杂度: O(N² + T²)
8.2 优化策略
- 早期过滤: 跳过未连接焊盘
- 分组处理: 按通道分组减少冲突检查
- 增量检测: 只检查相关层的碰撞
- 空间索引: 可扩展为使用四叉树加速
9. 示例
9.1 单端信号扇出
输入: BGA封装，10x10焊盘，间距1.0mm
输出:
- 边缘焊盘: 36个直接水平/垂直引出
- 内部焊盘: 64个通过45度stub + 通道引出
- 总走线段: 约200段（包括折角）
9.2 差分对扇出
输入: DDR4 DQ信号，8对差分
输出:
- 识别: 16个焊盘组成8对
- 分配: 优先水平逃逸
- 布线: P/N成对，同层等间距
- 特殊: 外侧走线延伸保持间距
10. 总结
BGA Fanout 算法通过以下关键技术实现高效的扇出走线：
- 智能网格分析: 自动识别BGA结构和布线通道
- 45度扇出: 符合信号完整性要求的标准扇出方式
- 通道布线: 利用焊盘间隙进行高效布线
- 智能层分配: 避免冲突的同时优化层利用率
- 差分对支持: 自动识别并正确处理差分信号
- 碰撞检测: 确保生成走线符合设计规则
- 增量处理: 支持多次运行和已有扇出检测
该算法已成功应用于多种BGA封装的扇出布线，包括:
- DDR3/DDR4内存
- 高速接口（USB, PCIe, Ethernet）
- 处理器BGA封装
- FPGA I/O扇出
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
6
0- 0
已为社区贡献4条内容
所有评论(0)