최적화 기법을 사용한 멀티레이어 이스케이프 라우팅 알고리즘 (Multi-layer Escape Routing Algorithm using Optimization Method)

서지정보

· 발행기관 : 대한전자공학회
· 수록지 정보 : 전자공학회논문지 / 62권 / 1호 / 43 ~ 55페이지
· 저자명 : 조범근, 구형일

초록

PCB(printed circuit board) 설계에서 이스케이프 라우팅은 칩의 집적도가 높아지고 부품 수가 늘어남에 설계 시간과 난이도가 높아지고 있어 자동화 연구가 활발히 이루어지고 있다. 기존 연구들에서는 단일 레이어만을 지원하거나 라우팅 영역의 제약이 없는 단순한 상황을 가정하고 있어 실제 설계에 활용이 제한적이다. 본 논문에서는 멀티레이어 이스케이프 라우팅을 효율적으로 수행하기 위한 알고리즘을 제안한다. 제안하는 알고리즘은 single 신호와 differential pair 모두 멀티레이어 상에서 이스케이프 라우팅을 한 번에 수행할 수 있으며, 특히 두 신호로 이루어진 differential pair가 한 지점에서 만나는 merge 과정과 두 신호가 같이 라우팅 되는 과정을 한 번에 고려해서 멀티레이어 상에서 효율적인 라우팅 결과를 얻을 수 있다. 또한 그래프 레벨에서 표현되는 라우팅 결과를 PCB layout 으로 변환하는 방법에 대해 제안한다. PCB layout 변환을 integer linear programming 문제로 정의하고 설계 조건을 constraint로 수식화해서 기존의 연구보다 다양한 조건과 형태의 입력을 일반화해서 처리할 수 있다. 제안하는 방법은 실제 설계 데이터에서 기존 연구보다 더 높은 라우팅 성공률을 보였고, 특히 differential pair가 여러 레이어에 걸쳐 위치가 조정되어 라우팅이 되기 때문에 어려운 조건에서도 더 많은 differential pair를 라우팅할 수 있음을 확인하였다.

영어초록

In PCB (Printed Circuit Board) design, escape routing has become increasingly time-consuming and complex due to higher chip integration densities and an increased number of components, leading to active research in automation. Previous research either support only single-layer routing or assume simplified scenarios without constraints on the routing area, which limits their practical application in actual designs. In this paper, we propose an algorithm to efficiently perform multi-layer escape routing. The proposed algorithm can simultaneously handle escape routing for both single signals and differential pairs across multiple layers. Specifically, by considering the merge process where the two signals of a differential pair merge at a single node and the process where they are routed together, we achieve efficient routing results on multiple layers. Additionally, we propose a method to convert routing results represented at the graph level into PCB layouts. By defining the PCB layout conversion as an integer linear programming problem and formulating design conditions as constraints, we can generalize and handle a wider variety of conditions and input forms compared to previous research. The proposed method demonstrated a higher routing success rate on actual design data compared to previous research. Notably, because the positions of differential pairs can be adjusted and routed across multiple layers, we confirmed that more differential pairs can be routed even under challenging conditions.

참고자료

· 없음