Best response dynamics for VLSI physical design placement

• Autorzy: Rapoport Michael , Tamir Tami

Identyfikatory

DOI

10.15439/2019F91

• Konferencja: Federated Conference on Computer Science and Information Systems (14 ; 01-04.09.2019 ; Leipzig, Germany)
• Języki publikacji: EN

Abstrakty

EN

The physical design placement problem is one of the hardest and most important problems in micro chips production. The placement defines how to place the electrical components on the chip. We consider the problem as a combinatorial optimization problem, whose instance is defined by a set of $2$-dimensional rectangles, with various sizes and wire connectivity requirements. We focus on minimizing the placement area and the total wire length.

Słowa kluczowe

EN

combinatorial mathematics; game theory; integrated circuit layout; network routing; search problems; simulated annealing; VLSI

PL

kombinatoryka; teoria gier; układ scalony; ruter; problemy wyszukiwawcze; VLSI

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2019
• Tom: Vol. 18
• Strony: 147--156
• Opis fizyczny: Bibliogr. 25 poz., rys., wz., wykr.

Twórcy

autor

Rapoport Michael

• School of Computer Science, The Interdisciplinary Center, Herzliya, Israel

autor

Tamir Tami

• School of Computer Science, The Interdisciplinary Center, Herzliya, Israel

Bibliografia

• 1. S. N. Adya and I. L. Markov. Combinatorial techniques for mixed-Size placement. ACM Transactions on Design Automation of Electronic Systems, Vol. 10(1), http://dx.doi.org/10.1145/1044111.1044116, 2005.
• 2. C.J. Alpert, D.P. Mehta, and S. S. Sapatnekar. Handbook of Algorithms for Physical Design Automation, Auerbach Publications, 2008.
• 3. Y.C. Chang, Y. W. Chang, G. M. Wu, and S. W. Wu. B∗ -Trees: a new representation for non-slicing floorplans. Proc. of the 37th Annual Design Automation Conference, pp. 458-463, DOI: 10.1145/337292.337541, 2000.
• 4. C. Chu. Electronic Design Automation: Synthesis, Verification, and Test. Chapter 11: Placement. pp. 635–685. Springer, 2009.
• 5. E. Even-Dar and Y. Mansour. Fast Convergence of Selfish Rerouting. In Proc. of SODA, pp. 772–781, DOI: 10.1145/1070432.1070541, 2005.
• 6. M. Feldman, Y. Snappir, and T. Tamir. The Efficiency of Best-Response Dynamics. The 10th International Symposium on Algorithmic Game Theory (SAGT), http://dx.doi.org/10.1007/978-3-319-66700-3-15, 2017.
• 7. S. H. Gerez. Algorithms for VLSI Design Automation. John Wiley & Sons, Inc., NY, USA. 1999.
• 8. P. Ghosal and T. Samanta. Thermal-aware Placement of Standard Cells and Gate Arrays: Studies and Observations, Symposium on VLSI. IEEE Computer Society Annual, DOI: 10.1109/ISVLSI.2008.37, 2008.
• 9. E. Huang and R. E. Korf. Optimal Rectangle Packing: An Absolute Placement Approach. Journal of Artificial Intelligence Research, vol. 46:47–87, 2012.
• 10. Intel Core i7 processors. http://www.intel.com/content/www/us/en/products/processors/core/i7-processors.html, 2008.
• 11. Z. Jiang, H. Chen, T. Chen and Y. Chang. Challenges and Solutions in Modern VLSI Placement, International Symposium on VLSI Design, Automation and Test (VLSI-DAT), http://dx.doi.org/10.1109/VDAT.2007.373223, 2007.
• 12. J. Kleinberg and E. Tardos. Chapter 12: Local Search. Algorithm Design. Addison-Wesley, pp. 690–700, 2005.
• 13. A. Khachaturyan, S. Semenovskaya, and B. Vainshtein. Statistical-Thermodynamic Approach to Determination of Structure Amplitude Phases, Sov. Phys. Crystallography. Vol. 24(5):519–524, 1979
• 14. A. B. Kahng, J. Lienig, I. L. Markov, and J. Hu. VLSI Physical Design: From Graph Partitioning to Timing Closure. Springer, http://dx.doi.org/10.1007/978-90-481-9591-6, 2011.
• 15. T. Lengauer. Combinatorial Algorithms for Integrated Circuits. Wiley-Teubner, http://dx.doi.org/10.1007/978-3-322-92106-2, 1990.
• 16. Y. Lin, B. Yu, X. Xu, J. Gao, N. Viswanathan, W. Liu, Z. Li, C. J. Alpert, ad D. Z. Pan. MrDP: Multiple-row Detailed Placement of Heterogeneous-sized Cells for Advanced Nodes. IEEE/ACM International Conference on Computer-Aided Design (ICCAD), http://dx.doi.org/10.1109/TCAD.2017.2748025, 2016.
• 17. I. L Markov, J. Hu, and M. Kim. Progress and Challenges in VLSI Placement Research. Computer-Aided Design (ICCAD),IEEE/ACM International Conference, http://dx.doi.org/10.1145/2429384.2429441, 2012.
• 18. H. Murata and E. S. Kuh. Sequence-pair based place-ment method for hard/soft/pre-placed modules. Proc. of the international symposium on Physical design, pp. 167–172, http://dx.doi.org/10.1145/274535.274560, 1998.
• 19. R. Norman, J. Last, and I. Haas. Solid-state Micrologic Elements, Solid-State Circuits Conference. Digest of Technical Papers. pp. 82–83, http://dx.doi.org/10.1109/ISSCC.1960.1157264, 1960.
• 20. S. Pattanaik, S. P. Bhoi, and R. Mohanty. Simulated Annealing Based Placement Algorithms and Research Challenges. Journal of Global Research in Computer Science. Vol. 3(6), 2012.
• 21. N. Quinn and M. Breuer. A forced directed component placement procedure for printed circuit boards. IEEE Transactions on Circuits and Systems, Vol. 26(6), 1979.
• 22. S. Reda and A. Chowdhary. Effective linear programming based placement methods. Proc. of the international symposium on Physical design, pp. 186–191, DOI:10.1.1.83.2416, 2006.
• 23. R. A. Rutenbar. Simulated Annealing Algorithms: An Overview. IEEE Circuits and Devices Magazine, Vol.5(1):19-26, 1989.
• 24. K. Shahookar and P. Mazumder. VLSI Cell Placement Techniques. ACM Computing Surveys, Vol. 23(2):143-220, 1991.
• 25. Z. Yang and S. Areibi. Global Placement Techniques for VLSI Physical Design Automation. Proc. of the 15th Intl. Conf. on Computer Applications in Industry and Engineering, 2002.

Uwagi

1. Track 1: Artificial Intelligence and Applications

2. Technical Session: 12th International Workshop on Computational Optimization

3. Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).