A faster implementation of APlace

ABSTRACT

APlace is a high quality, scalable analytical placer. This paper describes our recent efforts to improve APlace for speed and scalability. We explore various wirelength and density approximation functions. We speed up the placer using a hybrid usage of wirelength and density approximaions during he course of multi-level placement, and obtain 2-2.5 imes speedup of global placement on the IBM ISPD04 and ISPD05 benchmarks. Recent applications of the APlace framework to supply voltage degradation-aware placement and lens aberration-aware timing-driven placement are also briefly described.

REFERENCES

• 1: Tony Chan , Jason Congy , Kenton Sze, Multilevel generalized force-directed method for circuit placement, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055177]
• 2: A.B. Kahng and Q. Wang, "Implementation and Extensibility of an Analytic Placer," IEEE Transactions on Computer-Aided Design 24(5)(2005), pp. 734--747.
• 3: Andrew B. Kahng , Sherief Reda , Qinke Wang, APlace: a general analytic placement framework, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055187]
• 4: A.B. Kahng, S. Reda, and Q. Wang, "Architecture and Details of a High Quality, Large-Scale Analytical Placer," in Proc. Int. Conf. Computer Aided Design 2005, pp. 891--898.
• 5: Andrew B. Kahng , Bao Liu , Qinke Wang, Supply Voltage Degradation Aware Analytical Placement, Proceedings of the 2005 International Conference on Computer Design, p.437-443, October 02-05, 2005 [doi>10.1109/ICCD.2005.101]
• 6: A.B. Kahng, C.-H. Park, P. Sharma and Q. Wang, "Lens Aberration-Aware Timing-Driven Placement," in Proc. Design Automation and Testing in Europe 2006, to appear.
• 7: Andrew A. Kennings , Igor L. Markov, Analytical minimization of half-perimeter wirelength, Proceedings of the 2000 conference on Asia South Pacific design automation, p.179-184, January 2000, Yokohama, Japan [doi>10.1145/368434.368600]
• 8: W. Naylor, "Non-Linear Optimization System and Method for Wire Length and Delay Optimization for an Automatic Electric Circuit Placer," US Patent 6301693, 2001.
• 9: Georg Sigl , Konrad Doll , Frank M. Johannes, Analytical placement: A linear or a quadratic objective function?, Proceedings of the 28th conference on ACM/IEEE design automation, p.427-432, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127707]
• 10: Natarajan Viswanathan , Chris Chong-Nuen Chu, FastPlace: efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981072]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms, Design, Performance

Keywords:
analytical placement, lens aberration, scalability, supply voltage degradation