최적화 기법을 활용한 PCB 자동 설계 방법 연구
Automated PCB Design Methods using Integer Programming
- 주제(키워드) PCB , Automated design , Escape routing , Optimization , Integer Programming
- 주제(DDC) 621.381
- 발행기관 아주대학교 일반대학원
- 지도교수 구형일
- 발행년도 2025
- 학위수여년월 2025. 2
- 학위명 박사
- 학과 및 전공 일반대학원 전자공학과
- 실제URI http://www.dcollection.net/handler/ajou/000000034698
- 본문언어 한국어
- 저작권 아주대학교 논문은 저작권에 의해 보호받습니다.
초록/요약
PCB 설계 단계에서 칩의 집적도가 올라감에 따라 칩 내부의 신호를 외부로 연결하는 이스케이프 라우팅 단계의 난이도와 시간이 비약적으로 상승하였고 PCB 설계 효율성을 증대시키기 위해서 이스케이프 라우팅의 자동화 알고리즘에 대한 수요가 증가하였지만 실제 설계에 적용할 수 있는 자동화 기술에 대한 연구가 부족한 상황이다. 따라서 본 학위 논문에서는 PCB 자동 설계 방법을 다루고 있다. 첫 번째로 본 논문은 혼합 신호의 이스케이프 라우팅 모델링 및 differential pair의 라우팅 효율성을 높이기 위한 방법에 대해 다룬다. 기존의 이스케이프 라우팅 방법들은 많이 사용되는 두 가지의 핀 배열 중에 하나를 상정하고 모델링을 하였기 때문에 두 가지 배열에 모두 적용할 수 없다. 제안하는 방법은 이를 해결하고자 두 배열 모두 활용 가능하도록 모델링하였다. 또한 두 신호가 pair로 라우팅 되는 differential pair의 경우, 기존 방법에서는 라우팅 문제를 두 신호가 만나서 pair를 이루는 과정과 pair가 라우팅 되는 과정 두 가지 task로 나눠서 수행하는 경우가 많고, 여러 differential pair 가 복잡한 형태로 배열되어있는 경우를 해결하지 못 해서 실제 설계 케이스에서 라우팅 성공률이 낮게 측정됨을 확인하였다. 이를 해결하기 위해 본 연구에서는 두 가지 task를 따로 수행하는 것이 아니라 라우팅 최적 해를 찾을 때 두 가지를 동시에 고려할 수 있도록 모델링해서 복잡한 상황에서도 라우팅 성공률을 높일 수 있었다. 개발한 알고리즘은 직접 설계자가 수행한 manual 라우팅 결과와 비교했을 때 보다 더 많은 신호를 배선 길이를 적게 사용하면서 라우팅할 수 있었다. 두 번째로 칩의 집적도가 올라감에 따라 단일 레이어가 아니라 레이어 여러 개에서 설계 되는 케이스가 일반적이기 때문에 멀티레이어 상황에서 이스케이프 라우팅 효율성을 높이기 위한 방법은 연구하였다. 제안하는 방법은 single 신호와 differential pair 모두 멀티레이어 라우팅에서는 라우팅 가능한 전체 레이어를 모두 고려해서 라우팅하기 때문에 단일 레이어마다 라우팅하는 방법에 비해 더 많은 신호를 라우팅하는 결과를 보여주었다. 이 때, 앞서 언급한 두 differential pair 가 만나고 라우팅되는 과정을 멀티레이어 상에서 효율적으로 동작하도록 설계하였다. 이러한 결과는 연구한 모델링에서는 다양한 종류의 비아를 적용 가능하기 때문에 설계자가 원하는 조건을 반영할 수 있다는 점에서 설계자가 설정한 조건 하에서 라우팅 가능한 신호의 비율 및 공간 사용 정도 등을 빠르게 리포트하고 이를 통해 설계자가 다양한 설계에 대한 선택지를 빠르게 확인할 수 있다는 점에서 큰 도움을 줄 수 있다. 마지막으로 본 논문은 이스케이프 라우팅 결과가 모델링된 형태로만 활용되는 것을 넘어 실제 설계 레벨에서의 결과를 도출할 수 있도록 PCB 레이아웃 변환 알고리즘을 제안한다. 제안하는 방법은 그래프 모델링 상에서 얻어진 이스케이프 라우팅 결과를 PCB 레이아웃으로 변환할 때 PCB 레이아웃 설계 룰을 충족하도록 설계하였다. 제안하는 방법은 먼저 이스케이프 라우팅 결과에서 가이드가 될 수 있는 좌표들을 추출한다. 그 다음에 레이아웃 변환 문제를 추출한 좌표들 사이에 PCB 레이아웃 설계 룰을 만족하도록 새로운 좌표 값을 추가하는 문제로 변환하고 좌표 값들을 최적화 기법을 통해 구하였다. 이 때 레이아웃 설계 룰을 constraint로 변환하여 설계 룰을 만족하는 레이아웃 결과를 도출해냈다. 기존에 그래프 레벨로만 얻어졌던 이스케이프 라우팅 결과를 실제 PCB 좌표 상에 레이아웃으로 변환 가능하기 때문에 이스케이프 라우팅 자동화 측면에서 좋은 결과를 보여주었다.
more초록/요약
In PCB design, as chip integration levels continue to increase, the difficulty and time required for escape routing, which connects internal chip signals to external outputs, have risen dramatically. This has led to an increasing demand for automation algorithms in escape routing to improve PCB design efficiency. However, there is currently a shortage of research addressing the functionalities required in actual design processes. Therefore, this paper focuses on methods for automated PCB design. First, the paper deals with an escape-routing modeling technique for mixed signals and a method to improve the routing efficiency of differential pairs. Existing escape routing methods are typically modeled based on one of the two most common pin arrangements, making it impossible to handle both arrangements in a single approach. To address this limitation, the proposed method is modeled to accommodate both pin arrangements. In addition, for the differential pair where two signals must be routed as a pair, the previous methods often separate the routing process into two tasks: merging the two signals into a pair and then routing them. In cases where multiple differential pairs are arranged in a complex manner, existing methods fail to achieve a high success rate in actual design scenarios. To alleviate this issue, this research simultaneously considers both tasks when searching for the optimal routing solution, thus achieving a higher success rate even under complex conditions. Compared to manual routing performed by a designer, the developed algorithm can route more signals using shorter routing lengths. Second, because chips are typically designed with multiple layers rather than a single layer as integration increases, this study explores methods to improve escape routing efficiency in multilayer settings. The proposed approach considers every layer that can be routed in a multilayer environment for both single signals and differential pairs, leading to better routing results (i.e., routing a greater number of signals) compared to layer-by-layer routing. In this scenario, the previously mentioned pairing and routing process of the two differential pairs is designed to operate efficiently across multiple layers. Moreover, because the modeling in this research allows for various types of vias to be utilized, designers can reflect their desired conditions in the model. As a result, the system can quickly report the ratio of signals that can be routed and the extent of space usage under the conditions set by the designer, enabling rapid evaluation of different design choices. Lastly, this paper proposes a PCB layout conversion algorithm that goes beyond simply using the modeled escape routing results. The algorithm transforms the graph modeled escape routing outcomes into practical PCB layouts that adhere to PCB design rules. First, coordinates that can serve as guides are extracted from the escape routing results. Next, the layout conversion problem is reformulated as one of adding new coordinate values between these extracted points to satisfy PCB design rules. Using optimization techniques, these coordinate values are determined. By incorporating design rules as constraints, the final layout complies with the required regulations. Since the escape routing results, previously available only at the graph level, can now be converted into actual PCB coordinates, this method significantly advances automation in escape routing.
more목차
제 1 장 서론 1
1.1 연구 배경 1
1.2 연구 내용 3
1.2.1 혼합 신호 이스케이프 라우팅 알고리즘 연구 3
1.2.2 멀티레이어 이스케이프 라우팅 알고리즘 연구 4
1.2.3 PCB 레이아웃 변환 알고리즘 연구 4
1.2.4 논문의 구성 5
제 2 장 관련 연구 6
2.1 혼합 신호 이스케이프 라우팅의 수학적 모델링 6
2.2 멀티레이어 라우팅 8
2.3 레이아웃 변환 알고리즘 9
제 3 장 혼합 신호 라우팅 알고리즘 11
3.1 핀 배열 그래프 모델링 11
3.2 혼합 신호 라우팅 알고리즘 12
3.2.1 Variables 와 notations 12
3.2.2 Single 신호 constraints 13
3.2.3 Differential pair 라우팅 방법 및 constraints 13
3.2.4 Capacity 와 비아 관련 constraint 17
3.2.5 비용 함수 19
3.3 실험 결과 19
3.4 요약 28
제 4 장 멀티레이어 라우팅 29
4.1 Single 신호의 멀티레이어 이스케이프 라우팅 알고리즘 29
4.2 Differential pair 멀티레이어 이스케이프 라우팅 방법 32
4.3 비아 타입 적용 38
4.4 비용 함수 39
4.5 실험 결과 40
4.6 요약 41
제 5 장 PCB 레이아웃 변환 알고리즘 45
5.1 제안하는 레이아웃 변환 알고리즘 45
5.2 레이아웃 변환 수식화 49
5.2.1 Waypoint 연결성 constraints 49
5.2.2 레이아웃 clearance constraints 51
5.3 비용 함수 56
5.4 레이아웃 변환 결과 58
5.5 요약 64
제 6 장 결 론 65
참고문헌 67
Abstract 72
