Abstract
Massively parallel implementations of simulated annealing algorithms to solve NP-complete combinatorial problems are discussed. All solutions are based upon the processor farm model, where each worker tries a distinct rearrangement to improve the current solution.
Several strategies to reduce inconsistencies due to concurrent worker activities, while preserving a large amount of effective parallelism, are proposed and evaluated. The effectiveness of the processor farm model and the architectural requirements for its implementation are discussed as well.
We have used Occam as implementation language and an architecture including 40 Transputers has been used for actual evaluations.
The combinatorial optimization problem chosen to test the implementation is the chip placement, a step of VLSI circuit design that defines placement of functional units to reduce both the length and the congestion of connections among them.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
E.H.L.Aart, J.H.M.Korst, "Bolzmann Machines and Their Applications", Proc. of PARLE 87, LCNS 258, 259, 1987.
V.Ansade, R.Cornu-Emieux, B.Faure, G.Mazare, P.Objois, "Algorithms dedicated to a network of asyncronous cells", in Parallel Algorithms & Architecture, North-Holland, 1986.
F.Darema, S.Kirpatrick, V.A.Norton, "Parallel algorithms for chip placement by simulated annealing", IBM Jour. of Res. and Develop., vol. 31, no.3, May 87.
J.G.Donnet, D.R.Skillicorn, "Code partitioning by Simulated Annealing", Proc. Int. Conf. on Parallel Processing and Applications, pp. 303–308, L'Aquila, Italy, September 1987.
T.C.Hu, E.S.Ku, "Theory and concepts of circuit layout", in VLSI Circuit Layout: Theory and Design, IEEE PRESS, 3–17, 1985.
S.Kirpatrick, C.D.Gellatt, H.P.Vecchi, "Optimization by simulated annealing", SCIENCE, no. 220, p. 671, 1983.
D. May, R. Shepherd, C. Keane, "Communicating process architecture: Transputer and Occam", in Future parallel computers: an advanced course, LNCS 272, pp. 35–81, 1986.
Inmos, Occam 2 Reference Manual, Prentice Hall, 1986.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1989 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Baiardi, F., Orlando, S. (1989). Strategies for a massively parallel implementation of simulated annealing. In: Odijk, E., Rem, M., Syre, JC. (eds) PARLE '89 Parallel Architectures and Languages Europe. PARLE 1989. Lecture Notes in Computer Science, vol 366. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-51285-3_46
Download citation
DOI: https://doi.org/10.1007/3-540-51285-3_46
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-51285-1
Online ISBN: 978-3-540-46184-5
eBook Packages: Springer Book Archive