Techniques for scalable and effective routability evaluation

Abstract

Routing congestion has become a critical layout challenge in nanoscale circuits since it is a critical factor in determining the routability of a design. An unroutable design is not useful even though it closes on all other design metrics. Fast design closure can only be achieved by accurately evaluating whether a design is routable or not early in the design cycle. Lately, it has become common to use a “light mode” version of a global router to quickly evaluate the routability of a given placement. This approach suffers from three weaknesses: (i) it does not adequately model local routing resources, which can cause incorrect routability predictions that are only detected late, during detailed routing; (ii) the congestion maps obtained by it tend to have isolated hotspots surrounded by noncongested spots, called “noisy hotspots”, which further affects the accuracy in routability evaluation; and (iii) the metrics used to represent congestion may yield numbers that do not provide sufficient intuition to the designer, and moreover, they may often fail to predict the routability accurately. This article presents solutions to these issues. First, we propose three approaches to model local routing resources. Second, we propose a smoothing technique to reduce the number of noisy hotspots and obtain a more accurate routability evaluation result. Finally, we develop a new metric which represents congestion maps with higher fidelity. We apply the proposed techniques to several industrial circuits and demonstrate that one can better predict and evaluate design routability and that congestion mitigation tools can perform much better to improve the design routability.

References

1. C. J. Alpert and G. E. Tellez. 2010. The importance of routing congestion analysis. DAC Knowledge Center Online Article. http://www.dac.com/back\_end+topics.aspx?article=47&topic=2.
2. C. J. Alpert, Z. Li, M. D. Moffitt, G. J. Nam, J. A. Roy, and G. Tellez. 2010. What makes a design difficult to route. In Proceedings of the ACM International Symposium on Physical Design. ACM, New York, NY, 7--12.
3. C. Ansótegui, M. Sellmann, and K. Tierney. 2009. A gender-based genetic algorithm for the automatic configuration of algorithms. In Principles and Practice of Constraint Programming, Lecture Notes in Computer Science, vol. 5732, Springer, Berlin, 142--157.
4. J. Bergstra and Y. Bengio. 2012. Random search for hyper-parameter optimization. J. Mach. Learn. Res. 13, 281--305.
5. U. Brenner and A. Rohe. 2002. An effective congestion driven placement framework. In Proceedings of the ACM International Symposium on Physical Design. ACM, New York, NY, 6--11.
6. T. Chan, J. Cong, and K. Sze. 2005. Multilevel generalized force-directed method for circuit placement. In Proceedings of the ACM International Symposium on Physical Design. ACM, New York, NY, 185--192.
7. Y.-J. Chang, Y.-T. Lee, and T.-C. Wang. 2008. NTHU-Route 2.0: A fast and stable global router. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. IEEE, Los Alamitos, CA, 338--343.
8. H.-Y. Chen, S.-J. Chou, and Y.-W. Chang. 2010. Density gradient minimization with coupling-constrained dummy fill for CMP control. In Proceedings of the ACM International Symposium on Physical Design. ACM, New York, NY, 105--111.
9. H.-Y. Chen, S.-J. Chou, S.-L. Wang, and Y.-W. Chang. 2007. Novel wire density driven full-chip routing for CMP variation control. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. IEEE, Los Alamitos, CA, 831--838.
10. H.-Y. Chen, C.-H. Hsu, and Y.-W. Chang. 2009. High-performance global routing with fast overflow reduction. In Proceedings of the Asia-South Pacific Design Automation Conference. IEEE, Los Alamitos, CA, 582--587.
11. T.-C. Chen, A. Chakraborty, and D. Z. Pan. 2008a. An integrated nonlinear placement framework with congestion and porosity aware buffer planning. In Proceedings of the ACM/IEEE Design Automation Conference. ACM, New York, NY, 702--707.
12. T.-C. Chen, Z.-W. Jiang, T.-C. Hsu, H.-C. Chen, and Y.-W. Chang. 2008b. NTUplace3: An analytical placer for large-scale mixed-size designs with preplaced blocks and density constraints. IEEE Trans. Comput.-Aid. Des. Integr. Circuit Syst. 27, 7, 1228--1240.
13. M. Cho, K. Lu, K. Yuan, and D. Z. Pan. 2007. BoxRouter 2.0: Architecture and implementation of a hybrid and robust global router. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. IEEE, Los Alamitos, CA, 503--508.
14. M. Cho, D. Z. Pan, H. Xiang, and R. Puri. 2006. Wire density driven global routing for CMP variation and timing. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. ACM, New York, NY, 487--492.
15. C. Chu and Y.-C. Wong. 2008. FLUTE: Fast lookup table based rectilinear steiner minimal tree algorithm for VLSI design. IEEE Trans. Comput.-Aid. Des. Integr. Circuits Syst. 27, 1, 70--83.
16. A. E. Eiben and S. K. Smit. 2011. Parameter tuning for configuring and analyzing evolutionary algorithms. Swarm Evol. Comput. 1, 1, 19--31.
17. M. Gester, D. Müller, T. Nieberg, C. Panten, C. Schulte, and J. Vygen. 2012. Algorithms and data structures for fast and good VLSI routing. In Proceedings of the ACM/EDAC/IEEE Design Automation Conference. ACM, New York, NY, 459--464.
18. M. Gester, D. Müller, T. Nieberg, C. Panten, C. Schulte, and J. Vygen. 2013. BonnRoute: Algorithms and data structures for fast and good VLSI routing. ACM Trans. Des. Autom. Electron. Syst. 18, 2, 32:1--32:24.
19. X. He, T. Huang, L. Xiao, H. Tian, G. Cui, and E. F. Y. Young. 2011. Ripple: An effective routability-driven placer by iterative cell movement. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. IEEE, Los Alamitos, CA, 74--79.
20. P. Heckbert. 1997. Fast surface particle repulsion. Tech. rep. CMU-CS-97-130. Carnegie Mellon University, Pittsburgh, PA.
21. M.-K. Hsu, S. Chou, T.-H. Lin, and Y.-W. Chang. 2011. Routability-driven analytical placement for mixed-size circuit designs. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. IEEE, Los Alamitos, CA, 80--84.
22. J. Hu, M.-C. Kim, and I. L. Markov. 2013. Taming the complexity of coordinated place and route. In Proceedings of the ACM/EDAC/IEEE Design Automation Conference. ACM, New York, NY, 1--7.
23. Z.-W. Jiang, B.-Y. Su, and Y.-W. Chang. 2008. Routability-driven analytical placement by net overlapping removal for large-scale mixed-size designs. In Proceedings of the ACM/IEEE Design Automation Conference. ACM, New York, NY, 167--172.
24. A. B. Kahng and Q. Wang. 2005. Implementation and extensibility of an analytic placer. IEEE Trans. Comput.-Aid. Des. Integr. Circuits Syst. 24, 5, 734--747.
25. M.-C. Kim, J. Hu, D.-J. Lee, and I. L. Markov. 2011. A SimPLR method for routability-driven placement. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. IEEE, Los Alamitos, CA, 67--73.
26. Y. Li, A. Farshidi, L. Behjat, and W. Swartz. 2012. High performance post-placement length estimation techniques. Int. J. Inform. Comput. Sci. 1, 6, 144--152.
27. J. Lou, S. Thakur, S. Krishnamoorthy, and H. S. Sheng. 2002. Estimating routing congestion using probabilistic analysis. IEEE Trans. Comput.-Aid. Des. Integr. Circuits Syst. 21, 1, 32--41.
28. M. D. Moffitt. 2008. MaizeRouter: Engineering an effective global router. IEEE Trans. Comput.-Aid. Des. Integr. Circuits Syst. 27, 11, 2017--2026.
29. W. C. Naylor, R. Donelly, and L. Sha. 2003. Non-linear optimization system and method for wire length and delay optimization for an automatic electric circuit placer. U.S. Patent 6671859 Bl.
30. D. O. Ouma, D. S. Boning, J. E. Chung, W. G. Easter, V. Saxena, S. Misra, and A. Crevasse. 2002. Characterization and modeling of oxide chemical-mechanical polishing using planarization length and pattern density concepts. IEEE Trans. Semiconduct. Manufac. 15, 2, 232--244.
31. M. Pan and C. Chu. 2006. FastRoute: A step to integrate global routing into placement. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. ACM, New York, NY, 464--471.
32. M. Pan and C. Chu. 2007. IPR: An integrated placement and routing algorithm. In Proceedings of the ACM/IEEE Design Automation Conference. ACM, New York, NY, 59--62.
33. J. A. Roy, N. Viswanathan, G.-J. Nam, C. J. Alpert, and I. L. Markov. 2009. CRISP: Congestion reduction by iterated spreading during placement. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. ACM, New York, NY, 357--362.
34. H. Shojaei, A. Davoodi, and J. T. Linderoth. 2011. Congestion analysis for global routing via integer programming. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. IEEE, Los Alamitos, CA, 256--262.
35. T. Taghavi, C. Alpert, A. Huber, Z. Li, G.-J. Nam, and S. Ramji. 2010. New placement prediction and mitigation techniques for local routing congestion. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. IEEE, Los Alamitos, CA, 621--624.
36. R. Tian, D. F. Wong, and R. Boone. 2001. Model-based dummy feature placement for oxide chemical-mechanical polishing manufacturability. IEEE Trans. Comput.-Aid. Des. Integr. Circuits Syst. 20, 7, 902--910.
37. N. Viswanathan, C. Alpert, C. Sze, Z. Li, and Y. Wei. 2012. The DAC 2012 routability-driven placement contest and benchmark suite. In Proceedings of the ACM/EDAC/IEEE Design Automation Conference. ACM, New York, NY, 774--782.
38. N. Viswanathan, C. J. Alpert, C. Sze, Z. Li, G.-J. Nam, and J. A. Roy. 2011. The ISPD-2011 routability-driven placement contest and benchmark suite. In Proceedings of the ACM International Symposium on Physical Design. ACM, New York, NY, 141--146.
39. Y. Wei and S. S. Sapatnekar. 2010. Dummy fill optimization for enhanced manufacturability. In Proceedings of the ACM International Symposium on Physical Design. ACM, New York, NY, 97--104.
40. Y. Wei, C. Sze, N. Viswanathan, Z. Li, C. J. Alpert, L. Reddy, A. D. Huber, G. E. Tellez, D. Keller, and S. S. Sapatnekar. 2012. GLARE: Global and local wiring aware routability evaluation. In Proceedings of the ACM/EDAC/IEEE Design Automation Conference. ACM, New York, NY, 768--773.
41. J. Westra, C. Bartels, and P. Groeneveld. 2004. Probabilistic congestion prediction. In Proceedings of the ACM International Symposium on Physical Design. ACM, New York, NY, 204--209.
42. T.-H. Wu, A. Davoodi, and J. T. Linderoth. 2010. A parallel integer programming approach to global routing. In Proceedings of the ACM/IEEE Design Automation Conference. ACM, New York, NY, 194--199.
43. Y. Xu, Y. Zhang, and C. Chu. 2009. FastRoute 4.0: Global router with efficient via minimization. In Proceedings of the Asia-South Pacific Design Automation Conference. IEEE, Los Alamitos, CA, 576--581.
44. Y. Zhang and C. Chu. 2011. RegularRoute: An efficient detailed router with regular routing patterns. In Proceedings of the ACM International Symposium on Physical Design. ACM, New York, NY, 45--52.
45. Y. Zhang and C. Chu. 2012. GDRouter: Interleaved global routing and detailed routing for ultimate routability. In Proceedings of the ACM/EDAC/IEEE Design Automation Conference. ACM, New York, NY, 597--602.

Index Terms

• Hardware

  • Electronic design automation

    • Physical design (EDA)

      • Placement

      • Wire routing