Skip to main content
Top
Published in: The Journal of Supercomputing 2/2014

01-08-2014

An augmented Lagrangian method for VLSI global placement

Authors: Wenxing Zhu, Jianli Chen, Weiguo Li

Published in: The Journal of Supercomputing | Issue 2/2014

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

By ignoring some cell overlaps, global placement computes the best position for each cell to minimize the wirelength. It is an important stage in very large scale integration (VLSI) physical design, since circuit performance heavily depends on the placement results. In this paper, we propose an augmented Lagrangian method to solve the VLSI global placement problem. In the proposed method, a cautious dynamic density weight strategy is used to balance the wirelength objective and the density constraints, and an adaptive step size is used to obtain a trade-off between runtime and solution quality. The proposed method is tested on the IBM mixed-size benchmarks and the International Symposium on Physical Design 2006 placement contest benchmarks. Experimental results show that our global placement method outperforms the state-of-the-art placement approaches in terms of solution quality on most of the benchmarks.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Alpert CJ, Mehta DP (2008) Handbook of algorithm for physical design automation. Auerbach Publications, New York, pp 277–284 Alpert CJ, Mehta DP (2008) Handbook of algorithm for physical design automation. Auerbach Publications, New York, pp 277–284
2.
go back to reference Chu C (2008) Chapter 11: placement in electronic design automation: synthesis, verification, and testing. In: Wang LT, Chang YW, Cheng KT (eds) Elsevier, Morgan Kaufmann Chu C (2008) Chapter 11: placement in electronic design automation: synthesis, verification, and testing. In: Wang LT, Chang YW, Cheng KT (eds) Elsevier, Morgan Kaufmann
3.
go back to reference Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-Completeness. W. H, Freeman and Company, NY Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-Completeness. W. H, Freeman and Company, NY
4.
go back to reference Donath WE (1980) Complexity theory and design automation. In: ACM/IEEE design automation conference, pp 412–419 Donath WE (1980) Complexity theory and design automation. In: ACM/IEEE design automation conference, pp 412–419
5.
go back to reference Nam GJ, Cong J (2007) Modern circuit placement: best practices and results. Springer, New York Nam GJ, Cong J (2007) Modern circuit placement: best practices and results. Springer, New York
6.
go back to reference Chang YW, Jiang ZW, Chen TC (2009) Essential issues in analytical placement algorithms. IPSJ Trans Syst LSI Des Methodol 2:145–166CrossRef Chang YW, Jiang ZW, Chen TC (2009) Essential issues in analytical placement algorithms. IPSJ Trans Syst LSI Des Methodol 2:145–166CrossRef
7.
go back to reference Sechen C, Sangiovanni-Vincentelli AL (1986) Timberwolf 3.2: a new standard cell placement and global routing package. In: Proceedings ACM/IEEE design automation conference. pp 432–439 Sechen C, Sangiovanni-Vincentelli AL (1986) Timberwolf 3.2: a new standard cell placement and global routing package. In: Proceedings ACM/IEEE design automation conference. pp 432–439
8.
go back to reference Wang M, Yang X, Sarrafzadeh M (2000) Dragon 2000: standard-cell placement tool for large industry circuits. In: Proceedings IEEE/ACM international conference on computer-aided design. pp 260–263 Wang M, Yang X, Sarrafzadeh M (2000) Dragon 2000: standard-cell placement tool for large industry circuits. In: Proceedings IEEE/ACM international conference on computer-aided design. pp 260–263
9.
go back to reference Taghavi T, Yang X, Choi BK (2005) Dragon 2005: large-scale mixed-size placement toll. In: Proceedings IEEE/ACM international conference on computer-aided design. pp 212–217 Taghavi T, Yang X, Choi BK (2005) Dragon 2005: large-scale mixed-size placement toll. In: Proceedings IEEE/ACM international conference on computer-aided design. pp 212–217
10.
go back to reference Chen J, Zhu WX, Ali MM (2011) A hybrid simulated annealing algorithm for nonslicing VLSI floorplanning. IEEE Trans Syst Man Cybern Part C Appl Rev 41(4):544–553 Chen J, Zhu WX, Ali MM (2011) A hybrid simulated annealing algorithm for nonslicing VLSI floorplanning. IEEE Trans Syst Man Cybern Part C Appl Rev 41(4):544–553
11.
go back to reference Caldwell AE, Kahng AB, Markov IL (2000) Can recursive bisection produce routable placements. In: Proceedings IEEE/ACM international conference on computer-aided design. pp 477–482 Caldwell AE, Kahng AB, Markov IL (2000) Can recursive bisection produce routable placements. In: Proceedings IEEE/ACM international conference on computer-aided design. pp 477–482
12.
go back to reference Roy JA, Papa DA, Adya SN, Chan HH, Ng AN, Lu JF, Markov IL (2005) Capo: robust and scalable open-source min-cut floorplacer. In Proceedings international symposium on physical design. pp 224–226 Roy JA, Papa DA, Adya SN, Chan HH, Ng AN, Lu JF, Markov IL (2005) Capo: robust and scalable open-source min-cut floorplacer. In Proceedings international symposium on physical design. pp 224–226
13.
go back to reference Agnihotri AR, Ono S, Li C, Yildiz MC, Khatkhate A, Koh CK, Madden PH (2005) Recursive bisection placement: feng shui 5.0 implementation detail. In: Proceedings international symposium on physical sesign. pp 230–232 Agnihotri AR, Ono S, Li C, Yildiz MC, Khatkhate A, Koh CK, Madden PH (2005) Recursive bisection placement: feng shui 5.0 implementation detail. In: Proceedings international symposium on physical sesign. pp 230–232
14.
go back to reference Roy JA, Adya SN, Papa DA, Markov IL (2006) Min-cut floorplacement. IEEE Trans Comput Aided Des Integr Circuits Syst 25(7):1313–1326 Roy JA, Adya SN, Papa DA, Markov IL (2006) Min-cut floorplacement. IEEE Trans Comput Aided Des Integr Circuits Syst 25(7):1313–1326
15.
go back to reference Caldwell AE, Kahng AB, Markov IL (2000) Design and implementation of move-based heuristics for VLSI hypergraph partitioning. ACM J Exp Algorithm 5 Caldwell AE, Kahng AB, Markov IL (2000) Design and implementation of move-based heuristics for VLSI hypergraph partitioning. ACM J Exp Algorithm 5
16.
go back to reference Karypis G, Aggarwal R, Kumar V, Shekhar S (1997) Multilevel hypergraph partitioning: applications in VLSI domain. In: Proceedings Asia and South Pacific design automation conference. pp 526–529 Karypis G, Aggarwal R, Kumar V, Shekhar S (1997) Multilevel hypergraph partitioning: applications in VLSI domain. In: Proceedings Asia and South Pacific design automation conference. pp 526–529
17.
go back to reference Luo T, Pan DZ (2008) Dplace2.0: a stable and efficient analytical placement based on diffusion. In: Proceedings Asia and South Pacific design automation conference. pp 346–351 Luo T, Pan DZ (2008) Dplace2.0: a stable and efficient analytical placement based on diffusion. In: Proceedings Asia and South Pacific design automation conference. pp 346–351
18.
go back to reference Viswanathan N, Pan M, Chu C (2007) Fastplace 3.0: a fast multilevel quadratic placement algorithm with placement congestion control. In: Proceedings Asia and South Pacific design automation conference. pp 135–140 Viswanathan N, Pan M, Chu C (2007) Fastplace 3.0: a fast multilevel quadratic placement algorithm with placement congestion control. In: Proceedings Asia and South Pacific design automation conference. pp 135–140
19.
go back to reference Kahng AB, Wang Q (2006) A faster implementation of APlace. In: Proceedings international symposium on physical design. pp 218–220 Kahng AB, Wang Q (2006) A faster implementation of APlace. In: Proceedings international symposium on physical design. pp 218–220
20.
go back to reference Spindler P, Johannes FM (2006) Fast and robust quadratic placement combined with an exact linear net model. In: Proceeding IEEE/ACM international conference on computer-aided design. pp 179–186 Spindler P, Johannes FM (2006) Fast and robust quadratic placement combined with an exact linear net model. In: Proceeding IEEE/ACM international conference on computer-aided design. pp 179–186
21.
go back to reference Chan T, Cong J, Shinnerl J, Sze K, Xie M (2006) mPL6: Enhanced multilevel mixed-sized placement. In: Proceedings international symposium on physical design. pp 212–214 Chan T, Cong J, Shinnerl J, Sze K, Xie M (2006) mPL6: Enhanced multilevel mixed-sized placement. In: Proceedings international symposium on physical design. pp 212–214
22.
go back to reference Chen TC, Jiang ZW, Hsu TC, Chen HC, Chang YW (2006) A high-quality mixed-size analytical placer considering preplaced blocks and density constraints. In: Proceedings IEEE/ACM international conference on computer-aided design. pp 187–192 Chen TC, Jiang ZW, Hsu TC, Chen HC, Chang YW (2006) A high-quality mixed-size analytical placer considering preplaced blocks and density constraints. In: Proceedings IEEE/ACM international conference on computer-aided design. pp 187–192
23.
go back to reference Spindler P, Schlichtmann U, Johannes FM (2008) Kraftwerk2- a fast force-directed quadratic placement approach using an accurate net model. IEEE Trans Comput Aided Des Integr Circuits Syst 27(8):1389–1411 Spindler P, Schlichtmann U, Johannes FM (2008) Kraftwerk2- a fast force-directed quadratic placement approach using an accurate net model. IEEE Trans Comput Aided Des Integr Circuits Syst 27(8):1389–1411
24.
go back to reference Chen TC, Jiang ZW, Hsu TC, Chen HC, Chang YW (2008) NTUplace3: an analytical placer for large-scale mixed-size design with preplaced blocks and density constraints. IEEE Trans Comput Aided Des Integr Circuits Syst 27(7):1228–1240 Chen TC, Jiang ZW, Hsu TC, Chen HC, Chang YW (2008) NTUplace3: an analytical placer for large-scale mixed-size design with preplaced blocks and density constraints. IEEE Trans Comput Aided Des Integr Circuits Syst 27(7):1228–1240
25.
go back to reference Chen J, Zhu W (2012) An analytical placer for VLSI standard cell placement. IEEE Trans Comput Aided Des Integr Circuits Syst 31(8):1208–1221 Chen J, Zhu W (2012) An analytical placer for VLSI standard cell placement. IEEE Trans Comput Aided Des Integr Circuits Syst 31(8):1208–1221
26.
go back to reference Viswanathan N, Nam GJ, Alpert CJ, Villarrubia P, Ren H, Chu C (2007) RQL: global placement via relaxed quadratic spreading and linearization. In: Proceedings ACM/IEEE design automation conference. pp 453–458 Viswanathan N, Nam GJ, Alpert CJ, Villarrubia P, Ren H, Chu C (2007) RQL: global placement via relaxed quadratic spreading and linearization. In: Proceedings ACM/IEEE design automation conference. pp 453–458
27.
go back to reference Kim MC, Lee DJ, Markov IL (2012) SimPL: an effective placement algorithm. IEEE Trans Comput Aided Des Integr Circuits Syst 31(1):50–60 Kim MC, Lee DJ, Markov IL (2012) SimPL: an effective placement algorithm. IEEE Trans Comput Aided Des Integr Circuits Syst 31(1):50–60
28.
go back to reference Kim MC, Markov IL (2012) ComPLx: a competitive primal-dual Lagrange optimization for global placement. In: Proceedings ACM/IEEE design automation conference. pp 747–752 Kim MC, Markov IL (2012) ComPLx: a competitive primal-dual Lagrange optimization for global placement. In: Proceedings ACM/IEEE design automation conference. pp 747–752
29.
go back to reference Kim MC, Viswanathan N, Alpert CJ, Markov IL, Ramji S (2012) MAPLE: multilevel adaptive placement for mixed-size designs. In: Proceedings international symposium on physical design. pp 193–200 Kim MC, Viswanathan N, Alpert CJ, Markov IL, Ramji S (2012) MAPLE: multilevel adaptive placement for mixed-size designs. In: Proceedings international symposium on physical design. pp 193–200
30.
go back to reference Li C, Xie M, Koh CK, Cong J, Madden PH (2007) Recursive function smoothing of half-perimeter wirelength for analytical placement. In: Proceedings international symposium on physical design. pp 26–28 Li C, Xie M, Koh CK, Cong J, Madden PH (2007) Recursive function smoothing of half-perimeter wirelength for analytical placement. In: Proceedings international symposium on physical design. pp 26–28
31.
go back to reference Markov IL, Hu J, Kim MC (2012) Progress and challenges in VLSI placement research. In: Proceedings IEEE/ACM international conference on computer-aided design. pp 275–282 Markov IL, Hu J, Kim MC (2012) Progress and challenges in VLSI placement research. In: Proceedings IEEE/ACM international conference on computer-aided design. pp 275–282
36.
go back to reference Naylor WC, Donelly R, Sha L (2001) US patent 6,301,693: Nonlinear optimization system and method for wire length and delay optimization for an automatic electric circuit placer Naylor WC, Donelly R, Sha L (2001) US patent 6,301,693: Nonlinear optimization system and method for wire length and delay optimization for an automatic electric circuit placer
37.
go back to reference He BS, Yang H, Wang SL (2000) Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities. J Optim Theory Appl 106(2):337–356CrossRefMATHMathSciNet He BS, Yang H, Wang SL (2000) Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities. J Optim Theory Appl 106(2):337–356CrossRefMATHMathSciNet
38.
go back to reference Chan T, Cong J, Sze K (2005) Multilevel generalized force-directed method for circuit placement. In: Proceedings international symposium on physical design. pp 185–192 Chan T, Cong J, Sze K (2005) Multilevel generalized force-directed method for circuit placement. In: Proceedings international symposium on physical design. pp 185–192
Metadata
Title
An augmented Lagrangian method for VLSI global placement
Authors
Wenxing Zhu
Jianli Chen
Weiguo Li
Publication date
01-08-2014
Publisher
Springer US
Published in
The Journal of Supercomputing / Issue 2/2014
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-014-1113-1

Other articles of this Issue 2/2014

The Journal of Supercomputing 2/2014 Go to the issue

EditorialNotes

Preface

Premium Partner