Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 18

Proceedings of the 2019 Federated Conference on Computer Science and Information Systems

Best Response Dynamics for VLSI Physical Design Placement

,

DOI: http://dx.doi.org/10.15439/2019F91

Citation: Proceedings of the 2019 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 18, pages 147–156 ()

Full text

Abstract. 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.

References

  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.