CPMO --- Constrained Placement by Multilevel Optimization


Multilevel Optimization with Nonconvex Nonlinear Programming for Large Scale Circuit Placement with Complex Constraints.

Supported by the SRC as Task 1091.001, continued from Task 686.001,
and by the NSF as grant CCR-9901153, CCF-0430077 and CCF-0528583.


People

Project Director Jason Cong
Principal Investigators Jason Cong and Tony Chan
Current Student Guojie Luo and Eric Radke
Former Members Chin-Chih Chang, Tim Kong, Michalis Romesis,
Joe Shinnerl, Kenton Sze, Xin Yuan, Min Xie


Introduction

Placement is one of the most important steps in the post-RTL synthesis process, as it directly defines the interconnects, which are now the bottleneck in circuit and system performance in deep submicron technologies. The placement problem has been studied extensively in the past 30 years. However, a study from UCLA shows that existing placement solutions are surprisingly far from optimal. Using a set of cleverly constructed circuit placement examples with known optima (PEKO) that match many industrial circuit characteristics, the study shows that the results of leading placement tools from both industry and academia are 70% to 150% away from the optimal solutions in terms of the total wirelength on these cases [Chang et al., 2003]. If such a gap could be closed, the resulting benefit would be equivalent to advancing several technology generations. In comparison, the introduction of copper interconnects is equivalent to a 30% wirelength reduction, and so is each process technology scaling. But both require multi-billion dollar investments.


Project Objectives

We shall develop a highly scalable placement engine that provides significant quality improvement over the existing state-of-the-art placement tools to reduce the gap between current achievable solutions and the optimal solutions. The placement engine will be built on the multilevel optimization framework, which has strong advantages in scalability, flexibility, and adaptability to new and complex constraints. We plan to apply recent advances in multilevel optimization and adapt and extend them to the problems and challenges unique to VLSI placement. In particular, our research will lead to efficient solutions to the following placement problems. (i) The large-scale mixed-size placement problem, which has become very common for advanced IC designs, with the extensive reuse of IP blocks for multi-million-gate ASICs and SOC designs. We must efficiently handle a very large number of standard cells mixed with many big macros, such as ROMs, RAMs and IP blocks. (ii) The constraint-driven placement problem, which considers delay, routability, and possibly other manufacturing- related constraints. We shall also develop new metrics and examples for measuring the quality of results in meeting such constraints. (iii) Incremental placement, which supports frequent dynamic netlist adjustment (say, due to physical re-synthesis) and design updates. Our three-year target is to achieve significant improvement in quality of results over state-of-the-art solutions with clearly measured goals on benchmarks with known optima, e.g., 20-30% gap reduction in wirelength.


Project Outcome Highlight

Related Benchmarks

Related Materials


Software


Publications

Book

  1. Jason Cong and Joseph Shinnerl (editors). Multilevel Optimization in VLSICAD. Kluwer Academic Publishers, Boston, 2003.
  2. Gi-Joon Nam and Jason Cong (editors). Modern Circuit Placement. Springer Publishers, 2007.

Journal Papers

  1. C.-C. Chang, J. Cong, D. Pan, and X. Yuan, "Multilevel Global Placement with Congestion Control," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 22, no. 4, pp. 395-409, April, 2003.
  2. C.-C. Chang, J. Cong, M. Romesis, and M. Xie, "Optimality and Scalability Study of Existing Placement Algorithms," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp.537 - 549, April, 2004.
  3. Jason Cong, Joseph R. Shinnerl, Min Xie, Tim Kong, and Xin Yuan, "Large-Scale Circuit Placement," ACM Transactions on Design Automation of Electronic Systems, Vol. 10, No. 2, April 2005.

Conference Papers

  1. T. Chan, J. Cong, T. Kong and J. Shinnerl, "Multilevel Optimization for Large-scale Circuit Placement," Proc. IEEE International Conference on Computer Aided Design, San Jose, California, pp. 171-176, November, 2000.
  2. C-C. Chang, J. Cong, Z. Pan and X. Yuan, "Physical Hierarchy Generation with Routing Congestion and Control," Proc. International Symposium on Physical Design, pp36-41, San Diego, California, April 2002.
  3. C.-C. Chang, J. Cong and M. Xie, "Optimality and Scalability Study of Existing Placement Algorithms," Asia South Pacific Design Automation Conference, Kitakyushu, Japan, pp 621-627, January 2003.
  4. C.-C. Chang, J. Cong and X. Yuan, "Multi-level Placement for Large-Scale Mixed-Size IC Designs," Proc. Asia South Pacific Design Automation Conference, pp 325-330, January 2003.
  5. J. Cong, M. Romesis and M. Xie, "Optimality, Scalability and Stability Study of Partitioning and Placement Algorithms," Proceedings of the International Symposium on Physical Design, Monterey, California, pp. 88-94, April, 2003.
  6. J. Cong, and X. Yuan, "Multilevel Global Placement with Retiming," ACM/SIGDA Proceedings of the 40th Design Automation Conference, Anaheim, California, pp 208 - 213, June 2003.
  7. T. F. Chan, J. Cong, J. Shinnerl and K. Sze, "An Enhanced Multilevel Algorithm for Circut Placement," Proc. IEEE International Conference on Computer Aided Design, San Jose, California, pp. 299-306, November, 2003.
  8. Jason Cong, Tim Kong, Joseph R. Shinnerl, Min Xie, and Xin Yuan, "Large-Scale Circuit Placement: Gap and Promise," Proceedings of the International Conference on Computer-Aided Design, pp. 883-890, November, 2003.
  9. Jason Cong, Gabriele Nataneli, Michail Romesis, and Joseph R. Shinnerl, "An Area-Optimality Study of Floorplanning," Proceedings of the International Symposium on Physical Design, pp. 78-83, April, 2004.
  10. Tony F. Chan, Jason Cong, and Kenton Sze, "Multilevel Generalized Force-Directed Method for Circuit Placement ," Proceedings of the International Symposium on Physical Design, pp. 185-192, April, 2005. (Best Paper Award)
  11. J. Cong, M. Romesis and J. Shinnerl, "Robust Mixed-Size Placement Under Tight White-Space Constraints," Proceedings of the 2005 IEEE/ACM International Conference on Computer Aided Design, San Jose, California, pp. 165-172, November 2005.
  12. J. Cong and Min Xie, "A Robust Detailed Placement for Mixed-Size IC Designs," Proceedings of the 11th Asia and South Pacific Design Automation Conference (ASP-DAC 2006), pp. 188-194, January 2006.
  13. J. Cong and G. Luo, "Highly Efficient Gradient Computation for Density Constrained Analytical Placement Problems," Proceedings of the International Symposium on Physical Design, Portland, OR, April 2008, to appear.

Technical Reports

  1. T. Kong and J. Shinnerl, "Implementing Lanczos-Based Preconditioned Modified Conjugate Gradients," UCLA Computer Science Department TR 010037, November, 2001.
  2. T. Kong, "An Adaptation of the Fast Multipole Method to a Nonanalytic Potential Field for Overlapping Disks in the Plane," UCLA Computer Science Department TR 010038, November, 2001.
  3. J. Shinnerl, "A Theorem on Partitioning a Sorted List of Numbers with an Application to VLSI Floorplanning," UCLA Computer Science Department TR 040006, February, 2004.

Sponsors


Copyright 2007. The Regents of the University of California.