Placement: An Essential Reading List

Categories

• Overviews and Surveys
• Floorplanning and Floorplacement
• Global Placement
• Detailed Placement
• Regularization
• Suboptimality Quantification
• Machine Learning
• Heuristic and Metaheuristic
• Analog
• Datapath

Overviews and Surveys

• I. L. Markov, J. Hu and M. Kim, “Progress and Challenges in VLSI Placement Research", Proc. ICCAD, 2012, pp. 275-282. (Link)
• I. L. Markov, J. Hu and M. Kim, “Progress and Challenges in VLSI Placement Research", Proc. of the IEEE, 103(11) (2015), pp. 1985-2003. (Link)
• C. J. Alpert, S. K. Karandikar, Z. Li, G.-J. Nam, S. T. Quay, H. Ren, C. N. Sze, P. G. Villarrubia and M. C. Yildiz, “Techniques for Fast Physical Synthesis", Proc. IEEE 95(3) (2007), pp. 573-599. (Link)
• OpenROAD. (Link)
• Andrew B. Kahng, Jens Lienig, Igor L. Markov, Jin Hu, "VLSI Physical Design: From Graph Partitioning to Timing Closure". (Link)

Floorplanning and Floorplacement

• A. N. Ng, I. L. Markov, R. Aggarwal and V. Ramachandran, “Solving Hard Instances of Floorplacement", Proc. ISPD, 2006, pp. 170-177. (Link)
• P.-N. Guo, C.-K. Cheng and T. Yoshimura, “An O-tree Representation of Non-slicing Floorplan and its Applications", Proc. DAC, 1999, pp. 268-273. (Link)
• T.-C. Chen and Y.-W. Chang, “Modern Floorplanning Based on B*-tree and Fast Simulated Annealing", IEEE TCAD 25(4) (2006), pp. 637-650. (Link)
• D. F. Wong and C. L. Liu, “A New Algorithm for Floorplan Design", Proc. DAC, 1986, pp.101-107. (Link)
• J. A. Roy, S. N. Adya, D. A. Papa and I. L. Markov, “Min-cut Floorplacement", IEEE TCAD 25(7) (2006), pp. 1313-1326. (Link)
• S. N. Adya and I. L. Markov, “Fixed-outline Floorplanning Through Better Local Search", Proc. ICCD, 2001, pp. 328-333. (Link)
• J. A. Roy, D. A. Papa, S. N. Adya, H. H. Chan, A. N. Ng, J. F. Lu and I. L. Markov, “Capo: Robust and Scalable Opensource Min-cut Floorplacer”, Proc. ISPD, 2005, pp. 224-226. (Link)
• H. Murata, K. Fujiyoshi, S. Nakatake and Y. Kajitani, “VLSI Module Placement Based on Rectangle-packing by the Sequence-pair", IEEE TCAD 15(12) (1996), pp. 1518-1524. (Link)

Global Placement

• C. Cheng, A. B. Kahng, I. Kang and L. Wang, "RePlAce: Advancing Solution Quality and Routability Validation in Global Placement", IEEE TCAD 38(9) (2019), pp. 1717-1730. (Link)
• C. J. Alpert, T. Chan, D. J. Huang, A. B. Kahng, I. Markov, P. Mulet and K. Yan, “Faster Minimization of Linear Wirelength for Global Placement", Proc. ISPD, 1997, pp.4-11. (Link)
• A. A. Kennings and I. L. Markov, “Analytical Minimization of Halfperimeter Wirelength”, Proc. ASP-DAC, 2000, pp. 179-184. (Link)
• J. Lu, H. Zhuang, P. Chen, H. Chang, C. Chang, Y.Wong, L.Sha, D. Huang, Y. Luo, C. Teng and C. Cheng, “ePlace-MS: Electrostatics-Based Placement for Mixed-Size Circuits", IEEE TCAD 34(5) (2015), pp.685-698. (Link)
• Y. Lin, S. Dhar,W. Li, H. Ren, B. Khailany and D. Z. Pan, “DREAMPIace: Deep Learning Toolkit- Enabled GPU Acceleration for Modern VLSI Placement", Proc. DAC, 2019, pp. 1-6. (Link)
• G.-J. Nam, C. J. Alpert, P. Villarrubia, B. Winter and M. Yildiz, “The ISPD 2005 Placement Contest and Benchmark Suite", Proc. ISPD, 2005, pp. 216-220. (Link)
• T. Chan, J. Cong, J. Shinnerl, K. Sze and M. Xie, “mPL6: Enhanced Multilevel Mixed-size Placement", Proc. ISPD, 2006, pp. 212-214. (Link)
• W. Naylor, R. Donelly, and L. Sha, “Non-Linear Optimization System and Method for Wire Length and Delay Optimization for an Automatic Electric Circuit Placer”, U.S. Patent 6301693, Oct. 2001. (Link)
• N. Viswanathan and C. Chu, “FastPlace: Efficient Analytical Placement Using Cell Shifting, Iterative Local Refinement, and a Hybrid Net Model", IEEE TCAD 24(5) (2005), pp. 722-733. (Link)
• N. Viswanathan, M. Pan and C. Chu, “FastPlace 3.0: A Fast Multilevel Quadratic Placement Algorithm with Placement Congestion Control", Proc. ASP-DAC, 2007, pp.135-140. (Link)
• M. Hsu, Y. Chen, C. Huang, S. Chou, T. Lin, T. Chen and Y. Chang, “NTUplace4h: A Novel Routability-Driven Placement Algorithm for Hierarchical Mixed-Size Circuit Designs", IEEE TCAD 33(12) (2014), pp. 1914-1927. (Link)
• J. A. Roy, D. A. Papa and I. L. Markov, “Capo: Congestion-driven Placement for Standard-cell and RTL Netlists with Incremental Capability", Modern Circuit Placement, Springer, 2007. (Link)

Detailed Placement

• Y. Lin,W. Li, J. Gu, H. Ren, B. Khailany and D. Z. Pan, “ABCDPlace: Accelerated Batch-Based Concurrent Detailed Placement on Multithreaded CPUs and GPUs", IEEE TCAD 39(12) (2020), pp.5083-5096. (Link)
• M. Pan and C. Chu, “IPR: An Integrated Placement and Routing Algorithm", Proc. DAC, 2007, pp. 59-62. (Link)
• B. Hu and M. Marek-Sadowska, “FAR: Fixed-pointsAddition and Relaxation Based Placement", Proc. ISPD, 2002, pp.161–166. (Link)

Regularization

• C. J. Alpert, T. Chan, D. J. Huang, A. B. Kahng, I. Markov, P. Mulet and K. Yan, “Faster Minimization of Linear Wirelength for Global Placement", Proc. ISPD, 1997, pp.4-11. (Link)
• A. A. Kennings and I. L. Markov, “Analytical Minimization of Halfperimeter Wirelength”, Proc. ASP-DAC, 2000, pp. 179-184. (Link)
• R. Baldick, A. B. Kahng, A. Kennings, and I. L. Markov, “Function smoothing with applications to VLSI layout”, Proc. ASP-DAC, 1999, pp. 225-228. (Link)

Suboptimality Quantification

• C. -C. Chang, J. Cong and M. Xie, "Optimality and scalability study of existing placement algorithms", Proc. ASP-DAC, 2003, pp. 612-627. (Link)
• J. Cong, M. Romesis and M. Xie, "Optimality, scalability and stability study of partitioning and placement algorithms", Proc. ISPD, 2003, pp. 88-94. (Link)

Machine Learning

• A. Mirhoseini, A. Goldie, M. Yazgan, J. Jiang, E. Songhori, et al., “Chip Placement with Deep Reinforcement Learning", arXiv 2004.10746, 2020. (Link)
• Y. Lin, S. Dhar,W. Li, H. Ren, B. Khailany and D. Z. Pan, “DREAMPIace: Deep Learning Toolkit- Enabled GPU Acceleration for Modern VLSI Placement", Proc. DAC, 2019, pp. 1-6. (Link)
• A. B. Kahng, “Machine Learning Applications in Physical Design: Recent Results and Directions", Proc. ISPD, 2018, pp. 68-73. (Link)
• A. B. Kahng, “Reducing Time and Effort in IC Implementation: A Roadmap of Challenges and Solutions", Proc. DAC, 2018, pp. 1-6. (Link)
• A. B. Kahng, “MLCAD Today and Tomorrow: Learning, Optimization and Scaling", MLCAD Workshop, Nov. 2020. (Keynote Link)
• IEEE CEDA Design AutomationWebiNar (DAWN) Event 1: Machine Learning For EDA. (Link)
• ACM/IEEE Workshop on Machine Learning for CAD (MLCAD). (Link)
• R. Puri, “Engineering the Future of AI for Enterprises”, ICCAD keynote, 2020. (Link)
• G. Huang, J. Hu, Y. He, J. Liu, M. Ma, Z, Shen, J.Wu, Y. Xu, H. Zhang, K. Zhong, X. Ning, Y. Ma, H. Yang, B. Yu, H. Yang and Y. Wang, “Machine Learning for Electronic Design Automation: A Survey”, ACM TODAES (2021), pp. 1-44. (Link)
• Y. Bengio, A. Lodi and A. Prouvost, “Machine Learning for Combinatorial Optimization: a Methodological Tour d’Horizon”, Eur. J. Oper. Res. 290(2) (2021), pp. 405-421. (Link)
• R. Sutton, “The Bitter Lesson" blog post, March 13, 2019. (Link)

Heuristic and Metaheuristic

• D. Aldous and U. Vazirani, ““Go with the Winners” Algorithms”, Proc. FOCS, 1994, pp. 492–501. (Link)
• K. D. Boese, A. B. Kahng and S. Muddu, “A New Adaptive Multistart Technique for Combinatorial Global Optimizations”, OR Letts. 16(2) (1994), pp. 101-113. (Link)
• J. Kennedy and R. Eberhart, “Particle Swarm Optimization”, Proc. ICNN Vol. 4, 1995, pp. 1942-1948. (Link)
• K. Deb, A. Pratap, S. Agarwal and T. Meyarivan, “A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II”, IEEE Trans. Evol. Comp. 6(2) (2002), pp. 182-197. (Link)
• A. B. Kahng and S. Mantik, “On Mismatches Between Incremental Optimizers and Instance Perturbations in Physical Design Tools", Proc. ICCAD, 2000, pp. 17-21. (Link)
• O. Coudert, J. Cong, S. Malik and M. Sarrafzadeh, “Incremental CAD”, Proc. ICCAD, 2000, pp. 236-244. (Link)
• T.-B. Chan, A. B. Kahng and M. Woo, “Revisiting Inherent Noise Floors for Interconnect Prediction", Proc. SLIP, 2020. (Link)

Analog

• R. Dreslinski, D. Wentzloff, M. Fayazi, K. Kwon, D. Blaauw, D. Sylvester, B. Calhoun, M. Coltella and D. Urquhart, “Fully-Autonomous SoC Synthesis using Customizable Cell-Based Synthesizable Analog Circuits”, 2019, (GitHub Link) (Link)
• K. Kunal, M. Madhusudan, A. K. Sharma,W. Xu, S. M. Burns, R. Harjani, J. Hu, D. A. Kirkpatrik and S. Sapatnekar, “ALIGN: Open-Source Analog Layout Automation from the Ground Up”, Proc. DAC, 2019, pp. 1-4. (GitHub Link) (Link)
• B. Xu, K. Zhu, M. Liu, Y. Lin, S. Li, X. Tang, N. Sun and D. Z. Pan, “Magical: Toward Fully Automated Analog IC Layout Leveraging Human and Machine Intelligence.”, Proc. ICCAD, 2019, pp. 1-8. (GitHub Link) (Link)

Data Path

• R. X. T. Nijssen and C. A. J. van Eijk, “Regular Layout Generation of Logically Optimized Datapaths", Proc. ISPD, 1997, pp. 42-47. (Link)
• T. T. Ye and G. D. Micheli, “Data Path Placement with Regularity", Proc. ICCAD, 2000, pp. 264-270. (Link)
• S. Arikati and R. Varadarajan, “A Signature Based Approach to Regularity Extraction," Proc. ICCAD, 1997, pp. 542-545. (Link)