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

논문 상세정보

상세배치를 위한 확장된 인터리빙 기법
An Extended Interleaving Technique for Detailed Placement

오은경   (동아대학교 컴퓨터공학과UU0000480  ); 허성우   (동아대학교 전자컴퓨터공학부UU0000480  );
  • 초록

    본 논문에서는 상세배치를 개선할 수 있는 확장된 인터리빙 기법을 제안한다. 기존의 행 -기반 인터리빙 기법은 한 행 내에서만 셀의 위치를 이동할 수 있는 제약이 있으며, 모든 셀이 여백 없이 인접해 있다는 가정 하에 적용 가능하였다. 본 논문에서 제안한 확장된 인터리빙 기법은 그런 제약을 극복하여 셀이 다른 행간에도 이동할 수 있도록 하였고, 또한 셀들 사이에 여백이 있는 경우에도 인터리빙 기법을 적용할 수 있도록 하였다. 반도체 설계 회사에서 사용 중인 CAD 툴에 의해 수렴된 상세배치를 제안된 인터리빙 기법을 이용하여 추가로 개선시킨 결과 HP(half perimeter)가 평균 9.5% 가 개선되었다.


    In this paper we propose an extended interleaving technique to improve a detailed placement. The existing row-based interleaving technique allows cells to move only within a row and it can be applied when there is no space between cells. The proposed extended-interleaving technique releases such constraints so that cells can move along with a vertical line parallel to a y-axis and space between cells is properly handled. Converged detailed-placements by a mature CAD tool have been improved by the proposed interleaving technique by 9.5% on average in half-perimeter wire length.


  • 주제어

    VLSI 레이아웃 .   표준 셀 .   배치 .   동적 프로그래밍 .   인터리빙 기법.  

  • 참고문헌 (34)

    1. P. Villanubia, 'Important Placement Considerations for Modern VLSI Chips,' Proc. of ISPD, pp. 6, 2003 
    2. R. Varadarajan, 'Convergence of Placement Technology in Physical Synthesis: Is Placement Really a Point Tool?,' Proc. of ISPD, pp. 6, 2003 
    3. C. Sechen and A. Sangiovanni- Vincentelli, 'TimberWolf3.2: A New Standard Cell Placement and Global Routing Package,' Proc. of DAC, pp. 432-439, 1986 
    4. Wern- Jieh and Carl Sechen, 'Efficient and Effective Placement for Very Large Circuits,' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp. 349-359, 1995 
    5. M. Sarrafzadeh and M. Wang, 'NRG: Global and Detailed Placement,' Proc. of ICCAD, pp, 532-537, 1997 
    6. C. Sechen and K. W. Lee, 'An Improved Simulated Annealing Algorithm for Row-Based Placement,' Proc. of ICCAD, pp. 478-481, 1987 
    7. X. Yang, M. Wang, K. Egur and M. Sarrafzadeh, 'A Snap-on Placement Tool,' Proc. of International Symposium on Physical Design, pp. 153-158, 2000 
    8. A. E. Caldwell, A. B. Kahng, and Igor L. Markov, 'Can Recursive Bisection Alone Produce Routable Placements?,' Proc. of DAC, pp. 477-482, 2000 
    9. D. J. -H. Huang and A. B. Kahng, 'Partitioning Based Standard-Cell Global Placement with an Exact Objective,' Proc. of International Symposium on Physical Design, pp. 18-25, 1997 
    10. M. C. Yildiz and P. H. Madden, 'Improved Cut Sequences for Partitioning Based Placement,' Proc. of DAC, pp. 776-729, 2001 
    11. Ke Zhong and S. Dutt, 'Effective Partition-Driven Placement with Simultaneous Level Processing and a Global Net Views,' Proc. of ICCAD, pp. 254-259, 2000 
    12. A. E. Caldwell, A. B. Kahng and I. L. Markov, 'Optimal End-Case Partitioners and Placers for Standard-Cell Layout,' Proc. of International Symposium on Physical Design, pp. 90-96, 1999 
    13. B. W. Kernighan and S. Lin, 'An Efficient Heuristic Procedure for Partitioning Graphs,' Bell Syst, Tech. J., vol. 49 no. 2, pp. 291-307, 1970 
    14. C. M. Fiduccia and R. M. Matteyses, 'A Linear Time Heuristic for Improving Network Partitions,' Proc. of DAC, pp. 175-181, 1982 
    15. Natarajan Viswanathan, Chris C. Chu, 'FastPlace: Efficient Analytical Placement Using Cell Shifting, Iterative Local Refinement and a Hybrid Net Model,' IEEE Trans. CAD of Integrated Circuits and Systems, Vol. 24, No.5, pp. 722-733, 2005 
    16. H. Eisenmann and F. M. Johannes, 'Generic Global Placement and Floorplanning.' Proc. of DAC, pp. 269-274, 1998 
    17. Karthik Rajagopal, Tal Shaked, Yegna Parasuram, Tung Cao, Amit Chowdhary, Bill Halpin, 'Timing Driven Force Directed Placement with Physical Net Constraints,' Proc. of ISPD, pp. 60-66, 2003 
    18. Sung-Woo Hur, Tung Cao, Karthik Rajgopal, Yegna Parasurarn, Amit Chowdhary, Vladimir Tiourin, and Bill Halpin, 'Force Directed Mongrel with Physical Net Constraints,' Proc. of DAC, pp. 214-219, 2003 
    19. Adrew B. Kahng and Qinke Wang, 'Implementation and Extensibility of an Analytic Placer,' Proc. of ISPD, pp. 18-25, 2004 
    20. H. Etawil, S. Arebi, and A. Vannelli, 'Attractor Repeller Approach for Global Placement,' Proc. of ICCAD, pp. 20-24, 1999 
    21. Bo Hu, Marek-Sadowska, 'FAR: Fixed-Points Addition and Relaxation Based Placement,' Proc. ISPD, pp. 161-166, 2002 
    22. Jurgen M. Kleinhans, Georg Sigl, Frank M. Johannes, and Kurt Antreich, 'GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization,' IEEE Transactions on CAD, Volume 10, No.3, pp. 356-365, 1991 
    23. S. Goto, 'An Efficient Algorithm for the TwoDimensional Placement Problem in Electrical Circuit Layout,' IEEE Trans. Circuits and Systems, CAS-28, pp. 12-18, 1981 
    24. P. N. Parakh, R. B. Brown and Karem A. Sakallah, 'Congestion Driven Quadratic Placement,' Proc. of DAC, pp. 275-278, 1998 
    25. X. Yang, B.-K. Choi, and M. Sarrafzadeh, 'Routability Driven White Space Allocation for Fixed-Die Standard-Cell Placement,' Proc. of ISPD, pp. 42-47, 2002 
    26. Maogang Wang, X. Yang, Ken Eguro, and M. Sarrafzadeh, 'Dragon2000: Placement of Industrial Circuits,' Proc. of ICCAD, pp. 260-263, 2000 
    27. X. Yang, B-K. Choi, and M. Sarrafzadeh, 'A Standard-Cell Placement Tool for Designs with High Row Utilization,' International Conference on Computer Design, pp. 45-49 2002 
    28. Tony Chan, Jason Cong, Tianming Kong, Joseph R. Shinnerl, 'Multilevel Optimization for Large-Scale Circuit Placement,' Proc. of ICCAD, pp. 171-176, 2000 
    29. S. Hur and J. Lillis, 'Mongrel: Hybrid Techniques for Standard Cell Placement,' Proc. of ICCAD, pp. 165-170, 2000 
    30. S. Chowdhury, 'Analytical Approaches to the Combinatorial Optimization in Linear Placement,' IEEE Trans. CAD, Vol. 8, pp. 630-639, 1989 
    31. Y. Saab, 'An Improved Linear Placement Algorithm Using Node Compaction,' IEEE Trans. on CAD, Vol. 15, No.8, pp. 952-958, 1996 
    32. C. J. Alpert and A. B. Kahng, 'A General Framework for Vertex Orderings, with Applications to Netlist Clustering,' IEEE Trans. On VLSI Systems, Vol. 4, No.2, pp. 240-246, 1996 
    33. Sung-Woo Hur and John Lillis, 'Relaxation and Clustering in a Local Search Framework: Application to Linear Placement,' Proc. of DAC, pp. 360-366, 1999 
    34. A.B.Kahng, P.Tucker, and A.lelikovsky, 'Optimization of Linear Placements for Wirelength Minimization with Free Sites,' Proc. of ASP-DAC, pp. 241-244, 1999 

 저자의 다른 논문

  • 오은경 (6)

    1. 2003 "표준 셀 배치를 위한 하이브리드 기법" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 30 (10): 595~602    
    2. 2006 "배선밀집도 드리븐 배치" 정보처리학회논문지. The KIPS transactions. Part A. Part A a13 (1): 57~70    
    3. 2008 "배선 밀집도를 완화하기 위한 개선된 광역배치 기법" 정보과학회논문지. Journal of KIISE. 컴퓨팅의 실제 및 레터 14 (4): 431~435    
  • 허성우 (12)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

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

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

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

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

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