본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

1-Steiner 트리 알고리즘을 응용한 시간 지향 배선 방법
Timing-Driven Routing Method by Applying the 1-Steiner Tree Algorithm

심호   (삼성전자 반도체 연구소 메모리 CAE 팀CC0101996  ); 임종석   (서강대학교 컴퓨터학과UU0000674  );
  • 초록

    본 논문에서는 1-Steiner 휴리스틱 알고리즘을 응용하여 단일 소스 네트와 다중 소스 네트를 배선하는 두 가지 시간 지향(timing-driven) 배선 방법을 제안한다. 이 방법은1-Steiner 휴리스틱 알고리즘의 계산값 (cost)을 지연시간으로 수정한 것으로 이 방법의 특징은 모든 터미널이 임계터미널인 경우와 또 임계터미널이 부분적으로 존재하는 경우의 단일 소스 네트와 다중 소스 네트를 배선하는 데 동시 적용할 수 있다는 점이다. 실험결과 단일 소스를 배선하는 알고리즘은 기존의 SERT와 SERT-C에 비해 지연시간이 각각 평균 2.1%, 10.6% 감소하는 성능을 보였다. 그리고 다중 소스를 배선하는 알고리즘은 기존의 MCMD A-tree 알고리즘과 비교했을 때 모든 소스, 터미널 쌍이 임계쌍(critical pair)일 경우는 최대 지연 시간이 평균 2.7% 증가했지만 부분적인 임계쌍이 존재할 때는 최대 지연 시간이 평균 1.4% 감소하는 유사한 결과를 도출한다.


    In this paper, we propose two timing-driven routing algorithms for single-source net and multi-source net as applications of 1-Steiner heuristic algorithm. Using the method of substituting the cost of 1-Steiner heuristic algorithms with interconnection delay, our routing algorithms can route both single-source net and multi-source net which have all critical source-terminal pairs or one critical pair efficiently Our single-source net routing algorithm reduced the average maximum interconnection delay by up to 2.1% as compared with previous single-source routing algorithm, SERT, and 10.6% as compared with SERT-C. and Our multi-source net routing algorithm increased the average maximum interconnection delay by up to 2.7% as compared with MCMD A-tree, but outperforms it by up to average 1.4% when the signal net has only subset of critical node pairs.


  • 참고문헌 (15)

    1. M. Garey, D.S. Johnson, 'The Rectilinear Steiner Problem is NP-Complete,' SIAM J. App. Math, 32(4), pp. 826-834, 1977 
    2. M. Hanan, 'On Steiner's Problem with Rectilinear Distance,' SIAM J. App. Math. 14, pp. 255-265, 1966 
    3. C.J. Alpert, T.C. Hu, J.H. Huang, A.B. Kahng, 'A Direct Combination of The Prim and Dijkstra Constructions for Improved Performance-Driven Routing,' in Proc. IEEE Int. Symp. on Circuits Syst., 1993, pp. 1869-1872 
    4. J. Cong, P.H. Madden, 'Performance Driven Routing with Multiple Sources,' IEEE Trans. Computer-Aided Design, V.16, pp. 410-419, April 1997 
    5. J. Lillis, C.K. Cheng, 'Timing Optimization for Multisource Nets: Characterization and Optimal Repeater Insertion,' IEEE Trans. Computer-Aided Design, V.18, pp. 322-331, March 1999 
    6. J. Cong, L. He, 'Optimal Wiresizing for Interconnects with Multiple Sources,' ACM Trans. Design Automation of Electronic Systems, Vol. 1, pp. 478-511, Oct. 1996 
    7. A.B. Kahng, G. Robins, On Optimal Interconnections for VLSI. Norwell, MA : Kluwer Academic, 1995 
    8. K.D. Boese, A.B. Kahng, G. Robins, 'High Performance Routing Trees with Identified Critical Sinks,' in Proc. ACM/IEEE Design Automat. Conf., 1993, pp. 182-187 
    9. K.D. Boese, A.B. Kahng, G. Robins, 'Nearoptimal Critical Sink Routing Tree Constructions,' IEEE Trans. Computer-Aided Design, Vol. 14, pp. 1417-1436, Dec. 1995 
    10. H. Hou, J. Hu, S.S. Sapatnekar, 'Non-Hanan Routing,' IEEE Trans. Computer-Aided Design, V.18, pp. 436-444, April 1999 
    11. W.C. Elmore, 'The Transient Response of Damped Linear Network with Particular Regard to Wideband Amplifier,' J. Applied Physics, pp. 55-63, 1948 
    12. K.D. Boese, A.B. Kahng, B.A. McCoy, G. Robins, 'Fidelity and Near-Optimality of Elmore-Based Routing Constructions,' in Proc. IEEE Intl. Conf. on Computer Design, 1993, pp. 81-84 
    13. D. Richards, 'Fast Heuristic Algorithms for Rectilinear Steiner Trees,' Algorithmica 4, pp. 191-207, 1989 
    14. J. Cong, C.K. Koh, 'Performance-Driven Interconnect Design Based on Distributed RC Delay Model,' in Proc. ACM/IEEE Design Automat. Conf., 1993, pp. 606-611 
    15. A.B. Kahng, G. Robins, 'A New Class of Iterative Steiner Tree Heuristics with Good Performance,' IEEE Trans. Computer-Aided Design, Vol. 11, pp. 893-902, July 1992 

 저자의 다른 논문

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기