본 논문은 배선간의 간격 조정을 통하여 혼신을 최소화하는 방법을 다룬다. 제시된 방법은 선형 프로그래밍을 이용하며, 정확한 혼신 계산을 위해 수평 배선 조각과 수직 배선 조각에서의 혼신을 모두 고려한다. 본 논문에서는 최장 길이 경로 문제를 이용하여 수직 배선 조각간의 결합 길이를 예측하는 방법을 제안한다. 이를 이용하면 실수 변수만으로 선형 프로그래밍 문제를 생성할 수 있으므로 문제 해결 시간이 매우 빠르다. 제시된 방법은 기존의 연구 결과인 wire perturbation 방법에 비해 실행 시간과 혼신 최소화 율에서 보다 나은 성능을 보였다. 혼신 최소화 율의 경우, 제안된 방법은 wire perturbation 방법에 비해 최고 혼신의 경우 평균 11.2% 향상된 결과를 보였고, 전체 혼신의 경우 3% 향상된 결과를 얻었다. 또한 제시된 방법의 수행 시간은 회로 Deutsch의 경우 11초 이내에 해결하는 빠른 속도를 보였다.
This paper deals with a crosstalk minimization method by wire spacing. The suggested method uses linear programming method and consider crosstalk of both horizontal segments and vertical segments. In this paper, we suggest a method which can predict the coupling length between vertical segments in the final routing result using longest path algorithm. By the suggested method, we can make LP problem without integer variable. Therefore, it is much faster to solve the problem. In the case of crosstalk optimization, the suggested method optimized peak crosstalk 11.2%, and 3% total crosstalk more than wire perturbation method. The execution time of the suggested method is as fast as it takes 11 seconds when Deutsch is optimized.
