---
title: "혼잡한 배선을 지우고 다시 그릴 때 비용이 바뀌는 과정"
author: "브레이브브라우저쓰자"
published_at: "2026-10-24T09:50:04.634Z"
updated_at: "2026-10-06T02:04:15.249Z"
tags: ["rip-up and reroute"]
canonical_url: "https://ariser.io/@writer_a9817d5a8de0/%ED%98%BC%EC%9E%A1%ED%95%9C-%EB%B0%B0%EC%84%A0%EC%9D%84-%EC%A7%80%EC%9A%B0%EA%B3%A0-%EB%8B%A4%EC%8B%9C-%EA%B7%B8%EB%A6%B4-%EB%95%8C-%EB%B9%84%EC%9A%A9%EC%9D%B4-%EB%B0%94%EB%80%8C%EB%8A%94-%EA%B3%BC%EC%A0%95"
ai_assisted: true
---

# 혼잡한 배선을 지우고 다시 그릴 때 비용이 바뀌는 과정

이 글은 AI가 활용됐습니다.

[원문](https://ariser.io/@writer_a9817d5a8de0/%ED%98%BC%EC%9E%A1%ED%95%9C-%EB%B0%B0%EC%84%A0%EC%9D%84-%EC%A7%80%EC%9A%B0%EA%B3%A0-%EB%8B%A4%EC%8B%9C-%EA%B7%B8%EB%A6%B4-%EB%95%8C-%EB%B9%84%EC%9A%A9%EC%9D%B4-%EB%B0%94%EB%80%8C%EB%8A%94-%EA%B3%BC%EC%A0%95)

배선 연결 하나가 가장 짧은 통로를 먼저 차지했다. 뒤에 온 연결도 그곳을 원한다면, 두 번째 연결만 멀리 우회시키는 것이 항상 좋은 선택일까? 먼저 만든 경로를 고정하면 전체 해결이 어려워질 수 있다. Rip-up and reroute는 기존 경로의 일부를 지워 자원을 되돌린 다음, 바뀐 비용을 사용해 다시 연결하는 방법이다.

## 지우는 것은 연결 요구가 아니라 경로 선택이다

배선이 지나간 경계에는 사용량이 기록된다. 기존 경로를 제거할 때는 그 경로가 차지하던 사용량도 줄여야 한다. 이후 탐색은 다른 연결이 아직 사용 중인 자원을 고려해 새로운 후보를 선택한다. Net의 논리적인 연결 요구까지 삭제하는 작업은 아니다.

OpenROAD FastRoute의 rip-up 구현도 경로를 검사하여 다시 연결할 필요가 있는지 결정하고, 제거할 경로가 통과한 경계의 usage를 감소시킨다. 같은 경로를 남겨 둔 채 재탐색하면 자신의 기존 자원 점유를 다른 연결의 수요처럼 중복 계산할 수 있다. [FastRoute RipUp.cpp의 경로 제거](https://github.com/The-OpenROAD-Project/OpenROAD/blob/master/src/grt/src/fastroute/src/RipUp.cpp)

## 짧은 통로 하나에 세 연결이 몰린 예제

설명용 배선 문제에서 P 통로는 길이 비용이 4, 용량은 1이다. Q 통로는 길이 비용이 6, 용량은 2다. 세 net은 모두 어느 통로로든 연결할 수 있고 다른 제약은 없다고 하자. 처음에는 길이만 보고 세 net을 P로 보냈다. P 사용량은 3, overflow는 2다.

경로 선택 비용을 다음처럼 정의해 보자. 이 식은 실제 FastRoute의 비용식을 그대로 옮긴 것이 아니라 현재 경쟁의 효과를 보기 위한 가상 규칙이다.

```text
후보 비용 = 길이 + 10 × max(배치 후 사용량 − 용량, 0)
```

Net 하나를 제거한 뒤 현재 사용량을 기준으로 순차 재배선한다. A를 P에서 빼면 P에 2개가 남는다. A를 다시 P에 넣는 비용은 4+10×2=24이고, 비어 있는 Q에 넣는 비용은 6이다. A는 Q를 선택한다.

B를 P에서 빼면 P에 1개, Q에 1개가 있다. B를 P에 넣으면 비용 14, Q에 넣으면 6이므로 B도 Q를 선택한다. 마지막으로 C를 P에서 빼면 P는 비고 Q에는 2개가 있다. C를 P에 넣으면 비용 4, Q에 넣으면 16이므로 C는 P를 선택한다. 결과는 P에 1개, Q에 2개로 overflow가 0이고 길이 합은 16이다. 처음의 길이 합 12보다 길지만 용량 조건을 만족한다.

## 모두 같은 스냅샷을 보면 왕복할 수 있다

여기서 세 net을 동시에 다시 선택하게 하면 결과가 달라질 수 있다. 각 net이 다른 두 net의 기존 P 경로가 그대로라고 보고 자신의 경로만 제거한 같은 스냅샷을 읽으면, 세 net 모두 P 비용 24와 Q 비용 6을 비교해 Q를 선택한다. 그러면 Q에 3개가 몰려 용량 2를 넘는다.

다음 반복에서도 각 net이 다른 두 net의 Q 점유를 그대로 읽고 자기 경로만 제거하면, Q 재삽입 비용은 16이고 P 비용은 4다. 세 net 모두 P로 돌아온다. 현재 비용만 보고 같은 시점에 반응하는 이 가상 알고리즘은 P와 Q 사이를 왕복한다. 반복 횟수를 늘리는 것만으로 문제가 풀리지 않는 사례다.

순차 갱신은 앞선 선택을 다음 net이 볼 수 있게 한다. 과거에 혼잡했던 자원에 추가 비용을 남기는 방식은 잠시 비었다는 이유로 모든 연결이 다시 몰리는 것을 억제할 수 있다. 실제 FastRoute의 maze 탐색에도 현재 사용량과 가중된 이전 사용량을 비용 계산에 반영하는 코드가 있다. 실제 비용은 이 글의 단순한 10배 초과량 식과 다르다. [maze.cpp의 relaxAdjacent와 getCost](https://github.com/The-OpenROAD-Project/OpenROAD/blob/master/src/grt/src/fastroute/src/maze.cpp)

## 다시 그리기에도 해결할 수 없는 조건이 있다

두 통로의 총 용량이 3인데 필수 연결이 4개라면, 다른 선택지가 없는 이 모델에서는 적어도 하나의 초과가 남는다. 경로 순서나 혼잡 비용을 바꾸어도 이 자원 부족을 없앨 수 없다. 새로운 통로나 층을 확보하거나 배치를 바꾸는 등 문제 조건을 바꾸어야 한다.

자원이 충분한 경우에도 탐색 순서, 비용의 크기, 허용 우회와 반복 제한에 따라 결과가 달라질 수 있다. 과거 비용을 크게 넣으면 혼잡은 피하면서 지나치게 긴 경로를 택할 수도 있다. 긴 우회가 중요한 경로의 타이밍을 악화시킬 가능성도 있으므로 overflow만 줄였다고 모든 품질이 좋아졌다고 결론 내리지 않는다.

OpenROAD global routing 문서는 혼잡 제거 반복 수와 타이밍이 중요한 net의 우선순위를 별도 옵션으로 제공한다. 결과를 읽을 때는 남은 overflow, 길이와 중요한 경로의 상태를 함께 보고, 반복이 멈춘 이유도 구분해야 한다. [global_route의 반복·우선순위 옵션](https://openroad.readthedocs.io/en/latest/main/src/grt/README.html#global-route)

Rip-up and reroute는 먼저 만든 경로를 포기할 수 있어서 전체 자원 경쟁을 다시 조정한다. 잘 작동하려면 제거한 점유를 정확히 되돌리고, 다른 연결의 최신 선택과 필요한 이력을 비용에 반영해야 한다. 반복의 목적은 같은 선을 계속 그리는 것이 아니라, 함께 수용 가능한 경로 조합을 찾아가는 데 있다.