The KIPS Transactions:PartA (정보처리학회논문지A)

Korea Information Processing Society (한국정보처리학회)
권호 표지
DOI QR코드

DOI QR Code

Routing Congestion Driven Placement

배선밀집도 드리븐 배치

  • 오은경 (동아대학교 컴퓨터공학과) ;
  • 허성우 (동아대학교 전기전자컴퓨터공학부)
  • Published : 2006.02.01
Download PDF
⟨ Previous Next ⟩

Abstract

This paper describes a new effective algorithm to estimate routing congestion and to resolve highly congested regions for a given detailed placement. The major features of the proposed technique can be summarized as follows. Firstly, if there are congested regions due to some nets which pass through the regions it can determine which cells affect those congested spots seriously and moves some of them to resolve congestion effectively. Secondly, since the proposed technique uses the ripple movement technique to move cells it resolves congestion without sacrificing wire length. Thirdly, we use an efficient incremental data structure to trace the changes in congestion and wire length as cells move. Hence, selection of cells to move could be very accurate and fast in the course of iteration. Finally, although an MST net model is used to resolve congestion in this paper, proposed technique can be work with any net model. Particularly, if proposed technique can obtain routing information from a real router, congestion can be resolved more effectively. Experimental results show that the proposed technique can resolve congestion effectively and efficiently without sacrificing wire length.

본 논문에서는 주어진 상세배치의 배선밀집도를 예측하고, 배선밀집도가 높은 지역을 효과적으로 해결하는 새로운 알고리즘을 소개한다. 제안된 기법의 특징은 다음과 같다. 첫째, 특정지역을 관통하는 넷이 많아 그 지역의 배선밀집도가 높을 경우 관통하는 넷에 연결된 셀들을 효과적으로 찾아내어 그들의 위치를 조정함으로써 배선밀집도를 완화시킨다. 둘째, 리플이동 (ripple movement) 기법을 이용하여 셀들을 이동함으로써 배선길이를 희생시키지 않으면서 배선밀집도를 완화시킨다. 셋째, 셀의 이동에 따른 배선밀집도의 변화 및 배선길이의 변화를 효과적으로 추적할 수 있도록 증분 자료구조 (incremental data structure)를 사용하였기 때문에 실시간으로 변화되는 상황에 적합한 셀 선택이 이루어지며, 실행시간도 매우 빠른 장점이 있다. 마지막으로, 본 논문에서는 MST 넷 모델을 사용하여 배선밀집도를 예측하지만 제안한 기법은 특정 넷 모델에 상관없이 적용할 수 있다. 특히 실제 라우터로부터 배선정보를 얻을 수 있다면, 배선밀집도는 더욱 효과적으로 해결될 수 있다. 제안된 기법을 이용한 실험결과는 배선길이를 희생하지 않으면서 배선밀집도를 매우 효과적으로 개선할 수 있음을 보여준다.

Keywords

References

  1. A. E. Caldwell, A. B. Kahng, and Igor L. Markov, 'Can Recursive Bisection Alone Produce Routable Placements?,' Proc. of DAC, pp.477-482, 2000 https://doi.org/10.1145/337292.337549
  2. D. J. -H. Huang and A. B. Kahng, 'Partitioning-Based Standard-Cell Global Placement with an Exact Objective,' Proc. of ISPD, pp.18-25, 1997 https://doi.org/10.1145/267665.267674
  3. M. C. Yildiz and P. H. Madden 'Improved Cut Sequences for Partitioning Based Placement,' Proc. of DAC, pp.776-729, 2001 https://doi.org/10.1145/378239.379064
  4. X. Yang, M. Wang,? K. Egur and M. Sarrafzadeh, 'A Snap-on Placement Tool,' Proc. of ISPD, pp.153-158, 2000 https://doi.org/10.1145/332357.332392
  5. 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 https://doi.org/10.1109/ICCAD.2000.896482
  6. A. E. Caldwell, A. B. Kahng and I. L. Markov, 'Optimal End-Case Partitioners and Placers for Standard-Cell Layout,' Proc. of ISPD, pp.90-96, 1999 https://doi.org/10.1145/299996.300032
  7. 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 https://doi.org/10.1002/j.1538-7305.1970.tb01770.x
  8. C. M. Fiduccia and R. M. Matteyses, 'A Linear Time Heuristic for Improving Network Partitions,' Proc. of DAC, pp.175-181, 1982
  9. Y. G. Saab, 'A Fast Clustering-Based Min-Cut Placement Algorithm with Simulated Annealing Performance,' VLSI Design, Vol.5, No.1, pp.37-48, 1996 https://doi.org/10.1155/1996/58084
  10. 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 https://doi.org/10.1109/43.365125
  11. S. Goto, 'An Efficient Algorithm for the Two-Dimensional Placement Problem in Electrical Circuit Layout,' IEEE Trans. Circuits and Systems, CAS-28, pp.12-18, 1981 https://doi.org/10.1109/TCS.1981.1084903
  12. H. Eisenmann and F. M. Johannes, 'Generic Global Placement and Floorplanning,' Proc. of DAC, pp.269-274, 1998 https://doi.org/10.1145/277044.277119
  13. H. Etawil, S. Arebi, and A. Vannelli, 'Attractor-Repeller Approach for Global Placement,' Proc. of ICCAD, pp.20-24, 1999 https://doi.org/10.1109/ICCAD.1999.810613
  14. Maogang Wang, X. Yang, Ken Eguro, and M. Sarrafzadeh, 'Dragon2000: Placement of Industrial Circuits,' Proc. of ICCAD, pp 260-263, 2000
  15. 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 https://doi.org/10.1109/ICCD.2002.1106746
  16. S. Hur and J. Lillis, 'Mongrel: Hybrid Techniques for Standard Cell Placement,' Proc. of ICCAD, pp.165-170, 2000 https://doi.org/10.1109/ICCAD.2000.896468
  17. G. Meixner and U. Lauther, 'Congestion-Driven Placement Using a New Multi-Partitioning Heuristic,' Porc. of ICCAD, pp.332-335, 1990 https://doi.org/10.1109/ICCAD.1990.129917
  18. Maogang Wang, Xiaojian Yang, Majid Sarrafzadeh, 'Congestion Minimization During Placement,' IEEE Trans. CAD of Integrated Circuits and Systems, Vol.19, No.10, pp.1140-1148, 2000 https://doi.org/10.1109/43.875296
  19. M. Wang and M. Sarrafzadeh, 'Modeling and Minimization of Routing Congestion,' Proc. of ASP-DAC, pp.185-190, 2000 https://doi.org/10.1109/ASPDAC.2000.835094
  20. M. Wang and M. Sarrafzadeh, 'On the Behavior of Congestion Minimization During Placement,' Proc. of International Symposium on Physical Design, pp.145-150, 1999 https://doi.org/10.1145/299996.300044
  21. C.C.Chang, Jason Cong, Zhigang Pan, Zin Yuan, 'Multilevel Global Placement With Congestion Control,' IEEE Trans. CAD of Integrated Circuits and Systems, Vol.22, No.4, pp.395-409, 2003 https://doi.org/10.1109/TCAD.2003.809661
  22. Jason Cong and Majid Sarrafzadeh, 'Incremental Physical Design,' Proc. of ISPD, pp.84-92, 2000 https://doi.org/10.1145/332357.332379
  23. Olivier Coudert, Jason Cong, Sharad Malik, and Majid Sarrafzadeh, 'Incremental CAD,' Proc. of ICCAD, pp.236-243, 2000 https://doi.org/10.1109/ICCAD.2000.896480
  24. Ulrich Brenner & Andre Rohe, 'An Effective Congestion-Driven Placement Framework,' IEEE Trans. CAD of Integrated Circuits and Systems, Vol.22, No.4, pp.387-394, 2003 https://doi.org/10.1109/TCAD.2003.809662
  25. P. N. Parakh, R. B. Brown and Karem A. Sakallah, 'Congestion Driven Quadratic Placement,' Proc. of DAC, pp.275-278, 1998 https://doi.org/10.1145/277044.277121
  26. Wenting How, Hong Yu, Xianlong Hong, Yici Cai, Weimin Wu, Jun Gu, bunch, and William H.Kao, 'A New Congestion Driven Placement Algorithm Based on Cell Inflation,' Proc. of ASP-DAC, pp.605-608, 2001 https://doi.org/10.1109/ASPDAC.2001.913375
  27. Andrew B. Kahng and Xu Xu, 'Accurate Pseudo-Constructive Wirelength and Congestion Estimation,' ACM International Workshop on System-Level Interconnect Prediction, pp.61-68, 2003 https://doi.org/10.1145/639929.639942
  28. Chris C. N. Chu, 'FLUTE: Fast Lookup Table Based Wirelength Estimation Technique,' Proc. ICCAD, pp.696-701, 2004 https://doi.org/10.1109/ICCAD.2004.1382665
  29. Chris Chu and Yiu-Chung Wong, 'Fast and Accurate Rectilinear Steiner Minimal Tree Algorithm for VLSI Design,' Proc. ISPD, pp.28-35, 2005 https://doi.org/10.1145/1055137.1055145
  30. M. Wang, X. Yang, K Eguro and M. Sarrafzadeh, 'Multi-center Congestion Estimation and Minimization During Placement,' Proc. ISPD, pp.147-152, 2000 https://doi.org/10.1145/332357.332391
  31. Xiaojian Yang, Ryan Kastner, M.Sarrafzadeh, 'Congestion Reduction During Placement Based on Integer Programming,' Proc. ICCAD, pp.573-576, 2001 https://doi.org/10.1109/ICCAD.2001.968712