Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Recent analytical global placers use density constraints to approximate non-overlap constraints and show very successful results. In this paper we unify a wide range of density smoothing techniques that we call global smoothing, and present a highly efficient method to compute the gradient of such smoothed densities used in several well-known analytical placers [3, 5, 7]. Our method reduces the complexity of the gradient computation by a factor of n compared to a naïve method, where n is the number of modules. Furthermore, with this efficient gradient computation we can come up with an efficient nonlinear programming-based placement framework, which supercedes the existing force-directed placement methods [4, 7]. An application of our technique, as the engine of a multilevel placer, achieved 13% and 15% wirelength improvement compared with SCAMPI [13] and mPL6 [3] on IBM-HB+ benchmark [13]

REFERENCES

• 1: S. N. Adya , S. Chaturvedi , J. A. Roy , D. A. Papa , I. L. Markov, Unification of partitioning, placement and floorplanning, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.550-557, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382639]
• 2: K. Arrow, L. Huriwicz, and H. Uzawa. Studies in Nonlinear Programming, Stanford University Press, Stanford, CA, 1958.
• 3: Tony F. Chan , Jason Cong , Joseph R Shinnerl , Kenton Sze , Min Xie, mPL6: enhanced multilevel mixed-size placement, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123055]
• 4: Tony Chan , Jason Cong , 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]
• 5: Tung-Chieh Chen , Zhe-Wei Jiang , Tien-Chang Hsu , Hsin-Chen Chen , Yao-Wen Chang, A high-quality mixed-size analytical placer considering preplaced blocks and density constraints, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233538]
• 6: Jason Cong , Min Xie, A robust detailed placement for mixed-size IC designs, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan [doi>10.1145/1118299.1118353]
• 7: Hans Eisenmann , Frank M. Johannes, Generic global placement and floorplanning, Proceedings of the 35th annual conference on Design automation, p.269-274, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277119]
• 8: A. B. Kahng , S. Reda , Qinke Wang, Architecture and details of a high quality, large-scale analytical placer, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.891-898, November 06-10, 2005, San Jose, CA
• 9: David G. Luenberger, Optimization by Vector Space Methods, John Wiley & Sons, Inc., New York, NY, 1997
• 10: Gi-Joon Nam, ISPD 2006 Placement Contest: Benchmark Suite and Results, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123042]
• 11: Gi-Joon Nam , Charles J. Alpert , Paul Villarrubia , Bruce Winter , Mehmet Yildiz, The ISPD2005 placement contest and benchmark suite, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055182]
• 12: W. C. Naylor, R. Donelly, and L. Sha, Non-linear Optimization System and Method for Wire Length and Delay Optimization for an Automatic Electric Circuit Placer, US Patent 6301693, October 2001.
• 13: Aaron N. Ng , Igor L. Markov , Rajat Aggarwal , Venky Ramachandran, Solving hard instances of floorplacement, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123047]
• 14: J. Nocedal and S. J. Wright. Numerical Optimization 2nd ed., Springer, 2006.
• 15: A. D. Polyanin. Handbook of Linear Partial Differential Equations for Engineers and Scientists, Chapman & Hall/CRC, 2002.
• 16: Peter Spindler , Frank M. Johannes, Fast and robust quadratic placement combined with an exact linear net model, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233537]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design

Keywords:
force-directed method, mixed-size placement