Article

Free access

A loosely coupled parallel algorithm for standard cell placement

Authors:

Carl SechenAuthors Info & Claims

ICCAD '94: Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design

Pages 137 - 144

Published: 06 November 1994 Publication History

Abstract

We present a loosely coupled parallel algorithm for the placement of standard cell integrated circuits. Our algorithm is a derivative of simulated annealing. The implementation of our algorithm is targeted towards networks of UNIX workstations. This is the very first reported parallel algorithm for standard cell placement which yields as good or better placement results than its serial version. In addition, it is the first parallel placement algorithm reported which offers nearly linear speedup, in terms of the number of processors (workstations) used, over the serial version. Despite using the rather slow local area network as the only means of interprocessor communication, the processor utilization is quite high, up to 98% for 2 processors and 90% for 6 processors. The new parallel algorithm has yielded the best overall results ever reported for the set of MCNC standard cell benchmark circuits.

References

[1]

E Banerjee and M. Jones, "A Parallel Simulated Annealing for Standard Cell Placement on a Hypercube Computer." Proc. Intl. Conf. on Computer-Aided Design (1986): 34-37.

[2]

A. Casotto, E Romeo, and A. Sangiovanni-Vincentelli, "A Parallel Simulated Annealing Algorithm for the Placement of Macro-Cells." Proc. Intl. Conf. on Computer-Aided Design (1986): 30-33.

[3]

A. Casotto, E Romeo, and A. Sangiovanni-Vincentelli, "A Parallel Simulated Annealing Algorithm for the Placement of Macro-Cells." IEEE Trans. on CAD, Volume 6, No. 5, pp 838-847, Sep 1987.

Digital Library

[4]

A. Casotto, A. Sangiovanni-Vincentelli, "Placement of Standard Cells Using Simulated Annealing on the Connection Machine." Proc. Intl. Conf. on Computer-Aided Design (1987): 350-353.

[5]

K. Doll, E M. Johannes, and G. Sigl, "Accurate Net Models for Placement Improvement by Network Flow Methods." Proc. Intl. Conf. on Computer-Aided Design, 1992, pp. 594-597.

Digital Library

[6]

K. Doll, F. M. Johannes, and G. Sigl, "Domino: Deterministic Placement Improvement with Hill-climbing Capabilities." Proc. VLSI, 1991, pp. 3b.l.l-3b.l.10.

[7]

R. Jayaraman and F. Darema, "Error Tolerance in Parallel Simulated Annealing Techniques." Proc. Intl. Conf. on Computer Design (1988): 545-548.

[8]

M. Jones and E Banerjee, "Performance of a Parallel Algorithm for Standard Cell Placement on the Intel Hypercube." Proc. 24th Design Automation Conf. (1987): 807-813.

Digital Library

[9]

S. Kim, "Improved Algorithms for Cell Placement and their Parallel Implementations," Tech. Rep. #CRHC-93-18, UILU-ENG-93-2231, University of Illinois, Urbana, IL, July 1993.

[10]

S. Kim, J. Chandy, B. Ramkumar, S. Parkes and E Banerjee, "Proper- PLACE: A Portable, Parallel Algorithm for Standard Cell Placement," Proc. 8th Int. Parallel Processing Symp., Cancun, Mexico, April 1994.

Digital Library

[11]

J.M. Kleinhans, G. Sigl, E M. Johannes, and K. J. Antreich, "GORD- IAN: VLSI Placement by Quadratic Programming and Slicing Optimization." IEEE Trans. on CAD, Volume 10, No. 3, 1991, pp 356-365.

Digital Library

[12]

R. Kling and E Banerjee, "Concurrent ESP: A Placement Algorithm for Execution on Distributed Processors." Proc. Intl. Conf. on Computer-Aided Design (1987): 354-357.

[13]

K. Kozminski, "Benchmarks for Layout Synthesis." Proc. 28th Design Automation Conf., 1991, pp. 265-270.

Digital Library

[14]

S. Kravitz and R. Rutenbar, "Placement by Simulated Annealing on a Multiprocessor." IEEE Trans. on CAD, Volume 6, No. 4, pp 534-549, Jul 1987.

Digital Library

[15]

J. Lam, J. M. Delosme, and C. Sechen, "Performance of a New Annealing Schedule." Proc. 25th Design Automation Conf. (1988): 306-311.

Digital Library

[16]

D. Mitra, R. Romeo, and A. Sangiovanni-Vincentelli, "Convergence and Finite-Time Behavior of Simulated Annealing." Advances in Applied Probability, Vol. 18. No. 3, pp. 747-771, 1986.

[17]

S. Mohan, and E Mazumder, "Wolverines: Standard Cell Placement on a Network of Workstations." IEEE Trans. on CAD, Volume 12, No. 9, pp 1312-26, Sep 1993.

Digital Library

[18]

J. S. Rose, D. R. Blythe, W. M. Snelgrove, and Z. G. Vranesic, "Fast, High Quality VLSI Placement on an MIMD Multiprocessor." Proc. Intl. Conf. on Computer-Aided Design (1986): 42-45.

[19]

J. S. Rose, D. R. Blythe, W. M. Snelgrove, and Z. G. Vranesic, "Parallel Standard Cell Placement Algorithms with Quality Equivalent to Simulated Annealing." IEEE Trans. on CAD, Volume 7, No. 3, pp 387-396, Mar 1988.

Digital Library

[20]

R. Rutenbar and S. Kravitz, "Layout by Annealing in a Parallel Environment." Proc. Intl. Conf. on Computer Design (1986): 434-437.

[21]

J. S. Sargent and E Banerjee, "A Parallel Row-Based Algorithm for Standard Cell Placement with Integrated Error Control." Proc. 26th Design Automation Conf. (1989): 590-593.

Digital Library

[22]

A. Srinivasan, K. Chaudhary, and E. S. Kuh, "RITUAL: A Performance Driven Placement Algorithm for Small Cell ICs." Proc. Intl. Conf. on Computer-Aided Design, 1991, pp. 48-51.

[23]

C. Sechen and A. Sangiovanni-Vincentelli, "The Timberwolf Placement and Routing Package." IEEE J. of Solid-State Circuits, vol SC- 20, no 2, pp 510-522, Apr 1985.

[24]

C. Sechen and K. W. Lee, "An Improved Simulated Annealing Algorithm for Row-based Placement." Proc. Intl. Conf. on Computer- Aided Design (1987): 478-481.

[25]

G. Sigl, K. Doll, and E M. Johannes, "Analytical Placement: A Linear or a Quadratic Objective Function?" Proc. Design Automation Conference, 1991, pp. 427-432.

Digital Library

[26]

W. Sun and C. Sechen, "Efficient and Effective Placement for Very Large Circuits." Proc. Intl. Conf. on Computer-Aided Design (1993): 170-177.

Digital Library

[27]

W. Sun and C. Sechen, "Efficient and Effective Placement for Very Large Circuits." submitted to IEEE Trans. on CAD.

Digital Library

[28]

W. Swartz and C. Sechen, "New Algorithms for the Placement and Routing of Macro Cells," Proc. Int. Conf. on Computer-Aided Design, 1990, pp. 336- 339.

[29]

W. Swartz, "Automatic Layout of Analog and Digital Mixed Macro/ Standard Cell Integrated Circuits.", Ph. D. Thesis, Yale University, 1993.

Digital Library

[30]

Chi-Pong Wong and Roll-Dieter Fiebrich, "Simulated Annealing- Based Circuit Placement Algorithm on the Connection Machine System." Proc. Intl. Conf. on Computer Design (1987): 78-82.

Cited By

Wang CLemieux GWawrzynek JCompton K(2011)Scalable and deterministic timing-driven parallel placement for FPGAsProceedings of the 19th ACM/SIGDA international symposium on Field programmable gate arrays10.1145/1950413.1950445(153-162)Online publication date: 27-Feb-2011
https://dl.acm.org/doi/10.1145/1950413.1950445
Ababei C(2009)Speeding up FPGA placement via partitioning and multithreadingInternational Journal of Reconfigurable Computing10.1155/2009/5147542009(1-1)Online publication date: 1-Jan-2009
https://dl.acm.org/doi/10.1155/2009/514754
Ludwin ABetz VPadalia KHutton MChow P(2008)High-quality, deterministic parallel placement for FPGAs on commodity hardwareProceedings of the 16th international ACM/SIGDA symposium on Field programmable gate arrays10.1145/1344671.1344676(14-23)Online publication date: 24-Feb-2008
https://dl.acm.org/doi/10.1145/1344671.1344676
Show More Cited By

Index Terms

A loosely coupled parallel algorithm for standard cell placement
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing
  2. Very large scale integration design
    1. Application-specific VLSI designs
      1. Application specific processors

Recommendations

A parallel standard cell placement algorithm

We present a loosely coupled parallel algorithm for the placement of standard cell integrated circuits. Our algorithm is a derivative of simulated annealing. The implementation of our algorithm is targeted toward networks of Unix workstations. This is ...
A Parallel Circuit-Partitioned Algorithm for Timing-Driven Standard Cell Placement

Simulated annealing based standard cell placement for VLSI designs has long been acknowledged as a computation-intensive process, and as a result, several research efforts have been undertaken to parallelize this algorithm. Parallel placement is most ...
Parallel algorithms for standard cell placement using simulated annealing

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '94: Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design

November 1994

771 pages

ISBN:0897916905

Chairmen:
Jochen A. G. Jess
Eindhoven Univ. of Technology, Eindhoven, The Netherlands
,
Richard Rudell
Synopsys, Inc., Mountain View, CA

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CS: Computer Society

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 06 November 1994

Check for updates

Qualifiers

Article

Conference

ICCAD '94

Sponsor:

SIGDA
IEEE-CS

ICCAD '94: International Conference on Computer Aided Design

November 6 - 10, 1994

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
261
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)3

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang CLemieux GWawrzynek JCompton K(2011)Scalable and deterministic timing-driven parallel placement for FPGAsProceedings of the 19th ACM/SIGDA international symposium on Field programmable gate arrays10.1145/1950413.1950445(153-162)Online publication date: 27-Feb-2011
https://dl.acm.org/doi/10.1145/1950413.1950445
Ababei C(2009)Speeding up FPGA placement via partitioning and multithreadingInternational Journal of Reconfigurable Computing10.1155/2009/5147542009(1-1)Online publication date: 1-Jan-2009
https://dl.acm.org/doi/10.1155/2009/514754
Ludwin ABetz VPadalia KHutton MChow P(2008)High-quality, deterministic parallel placement for FPGAs on commodity hardwareProceedings of the 16th international ACM/SIGDA symposium on Field programmable gate arrays10.1145/1344671.1344676(14-23)Online publication date: 24-Feb-2008
https://dl.acm.org/doi/10.1145/1344671.1344676
Wang MYang XSarrafzadeh MSentovich E(2000)Dragon2000Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design10.5555/602902.602961(260-263)Online publication date: 5-Nov-2000
https://dl.acm.org/doi/10.5555/602902.602961
Haldar MNayak AChoudhary ABanerjee PSarrafzadeh MBanerjee PRoy K(2000)Parallel algorithms for FPGA placementProceedings of the 10th Great Lakes symposium on VLSI10.1145/330855.330988(86-94)Online publication date: 2-Mar-2000
https://dl.acm.org/doi/10.1145/330855.330988
Eisenmann HJohannes FChawla BBryant RRabaey J(1998)Generic global placement and floorplanningProceedings of the 35th annual Design Automation Conference10.1145/277044.277119(269-274)Online publication date: 1-May-1998
https://dl.acm.org/doi/10.1145/277044.277119
Chandy JBanerjee P(1996)Parallel simulated annealing strategies for VLSI cell placementProceedings of the 9th International Conference on VLSI Design: VLSI in Mobile Communication10.5555/525699.834730Online publication date: 3-Jan-1996
https://dl.acm.org/doi/10.5555/525699.834730

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents