Article

Free access

Multiprocessor-based placement by simulated annealing

Authors:

Saul A. Kravitz,

Rob A. RutenbarAuthors Info & Claims

DAC '86: Proceedings of the 23rd ACM/IEEE Design Automation Conference

Pages 567 - 573

Published: 02 July 1986 Publication History

PDF eReader

Abstract

Simulated annealing methods have proven to be particularly successful in physical design applications, but often require burdensome, long run times. This paper studies the design and analysis of standard cell placement by annealing in a multiprocessor environment. Annealing is not static: we observe that the temperature parameter which controls hill-climbing in simulated annealing changes the behavior of an annealing algorithm as it runs, and strongly influences the choice of multiprocessor partitioning strategy. We introduce the idea of adaptive strategies that exhibit different speedups across different temperature ranges. Measured performance of parallel placement algorithms running on a multiprocessor demonstrate practical speedups consistent with our predictions.

References

[1]

R. Ba~roa et al., "MACH-I: Aa Operating System Environment for Large-Scale Multiprocessor Applications", IEEE Software, July 1985.

Google Scholar

[2]

D. Chyan, and M. Breuer, "A Placement Algorithm for Array Processors", Proc. of the DA Con f, IEEE, 1983.

Digital Library

Google Scholar

[3]

A. Iosupovici, C. King, and M. Breuer, "A Module Interchange Placement Machine", Proc. of the DA Con f, IEEE, 1983.

Digital Library

Google Scholar

[4]

S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi, "Optimization by Simulated Annealing", Science, 220(4598):671-680, May 1983.

Crossref

Google Scholar

[5]

S. Kravitz, "Multiprocessor-Bazed Placement by Simulated Annealing", Research Report CMUCAD-86-6, Dept. of ECE, Carnegie-Mellon University, February 1986.

Google Scholar

[6]

C. Sechea, A. Sangiovaani Vineentelli, "The Timberwolf Placement and Routing Package", IEEE Journal of Solid-State Circuits, SC-20(2):510-522, April 1985.

Crossref

Google Scholar

[7]

R. Smith, "Accelerator Plans for Iterative Improvement Placement", Presentation at IEEE Physical Design Workshop, January 1985.

Google Scholar

[8]

P. Spira and C. Hage, "Hardware Acceleration of Gate Array Layout", Proc. of the DA Gonf, IEEE, June 1985.

Digital Library

Google Scholar

[9]

K. Ueda, T. Komatsubara, and T. Hosaka, "A Parallel Processing Approach for Logic Module Placement", IEEE Trans. on CAD, CAD-2(1):39-47, January 1983.

Google Scholar

Cited By

View all

Bollinger SMidkiff S(1991)Heuristic Technique for Processor and Link Assignment in MulticomputersIEEE Transactions on Computers10.1109/12.7641040:3(325-333)Online publication date: 1-Mar-1991
https://dl.acm.org/doi/10.1109/12.76410
Banerjee PJones MSargent J(1990)Parallel Simulated Annealing Algorithms for Cell Placement on Hypercube MultiprocessorsIEEE Transactions on Parallel and Distributed Systems10.1109/71.801281:1(91-106)Online publication date: 1-Jan-1990
https://dl.acm.org/doi/10.1109/71.80128
Slagle JBose ABusalacchi PWee C(1989)Enhanced simulated annealing for automatic reconfiguration of multiprocessors in spaceProceedings of the 2nd international conference on Industrial and engineering applications of artificial intelligence and expert systems - Volume 110.1145/66617.66666(401-408)Online publication date: 6-Jun-1989
https://dl.acm.org/doi/10.1145/66617.66666
Show More Cited By

Index Terms

Multiprocessor-based placement by simulated annealing

Recommendations

Placement by Simulated Annealing on a Multiprocessor

Physical design tools based on simulated annealing algorithms have been shown to produce results of extremely high quality, but typically at a very high cost in execution time. This paper selects a representative annealing application--standard cell ...
Solving hard satisfiability problems with synchronous simulated annealing on the AP1000 multiprocessor
SPDP '95: Proceedings of the 7th IEEE Symposium on Parallel and Distributeed Processing

Solving the hard satisfiability problem is difficult and time-consuming for even modest sized problem instances. This paper presents a parallel synchronous simulated annealing method for solving the Random L-Sat problem on a large scale distributed-...
Clustering based simulated annealing for standard cell placement
DAC '88: Proceedings of the 25th ACM/IEEE Design Automation Conference

Simulated annealing has been shown to be effective in producing good quality results for the standard cell placement problem. Its main drawback is the excessive computation time required, which increases significantly with the problem size. In this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '86: Proceedings of the 23rd ACM/IEEE Design Automation Conference

July 1986

835 pages

ISBN:0818607025

Chairman:
Don Thomas
IBM, Thomas J. Watson Research Center, Yorktown Heights, NY

Publisher

IEEE Press

Publication History

Published: 02 July 1986

Check for updates

Qualifiers

Article

Acceptance Rates

DAC '86 Paper Acceptance Rate 124 of 300 submissions, 41%;

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
280
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)1

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bollinger SMidkiff S(1991)Heuristic Technique for Processor and Link Assignment in MulticomputersIEEE Transactions on Computers10.1109/12.7641040:3(325-333)Online publication date: 1-Mar-1991
https://dl.acm.org/doi/10.1109/12.76410
Banerjee PJones MSargent J(1990)Parallel Simulated Annealing Algorithms for Cell Placement on Hypercube MultiprocessorsIEEE Transactions on Parallel and Distributed Systems10.1109/71.801281:1(91-106)Online publication date: 1-Jan-1990
https://dl.acm.org/doi/10.1109/71.80128
Slagle JBose ABusalacchi PWee C(1989)Enhanced simulated annealing for automatic reconfiguration of multiprocessors in spaceProceedings of the 2nd international conference on Industrial and engineering applications of artificial intelligence and expert systems - Volume 110.1145/66617.66666(401-408)Online publication date: 6-Jun-1989
https://dl.acm.org/doi/10.1145/66617.66666
Lam JDelosme JShaklee DNewton A(1988)Performance of a new annealing scheduleProceedings of the 25th ACM/IEEE Design Automation Conference10.5555/285730.285780(306-311)Online publication date: 1-Jun-1988
https://dl.acm.org/doi/10.5555/285730.285780
Jones MBanerjee P(1987)Performance of a parallel algorithm for standard cell placement on the Intel hypercubeProceedings of the 24th ACM/IEEE Design Automation Conference10.1145/37888.38015(807-813)Online publication date: 1-Oct-1987
https://dl.acm.org/doi/10.1145/37888.38015
Hancock JDasGupta SThomas D(1986)Tutorial on parallel processing for design automation applications (tutorial session)Proceedings of the 23rd ACM/IEEE Design Automation Conference10.5555/318013.318025(69-77)Online publication date: 2-Jul-1986
https://dl.acm.org/doi/10.5555/318013.318025

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Placement by Simulated Annealing on a Multiprocessor

Solving hard satisfiability problems with synchronous simulated annealing on the AP1000 multiprocessor

Clustering based simulated annealing for standard cell placement