Maximum Tolerable Error Bound In Distributed Simulated Annealing

ETRI Journal

关键词: Maximum Tolerable Error Bound In Distributed Simulated Annealing;   

Others  :  1183936
DOI  :  10.4218/etrij.94.0194.0001

【 摘 要 】

Simulated annealing is an attractive but expensive, heuristic method for approximating the solution to combinatorial optimization problems. Attempts to parallel simulated annealing, particularly on distributed memory multicomputers, are hampered by the algorithm’s requirement of a globally consistent system state. In a multicomputer, maintaining the global state S involves explicit message traffic and is a critical performance bottleneck. To mitigate this bottleneck, it becomes necessary to amortize the overhead of these state updates over as many parallel state changes as possible. By using this technique, errors in the actual cost C(S) of a particular state S will be introduced into the annealing process, The paper places analytically derived bounds on this error in order to assure convergence to the correct optimal result. The resulting parallel simulated annealing algorithm dynamically changes the frequency of global updates as a function of the annealing control parameter, i.e. temperature. Implementation results on an Intel iPSC/2 are reported.

   

【 参考文献 】

• [1]Kirkpatrick, S., Gellatt Jr., CD. and Vecci, MP., "Optimization by Simulated Annealing," Science, Vol. 220, 1983, pp 975-986.
• [2]van Laarhoven, P.J.M., and Aarts, E.H.L., "Simulated Annealing: Theory and Applications," D. Reidei Publishing Co., 1988.
• [3]Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A. and Teller, E. "Equation of State Calculations by Fast Computing Machines," Chem. Physics, Vol. 21, 1953, pp 1087-1092.
• [4]Lutfiyya H., McMillin B., Poshyanonda P., and Dagli C., "Composite Stock Cutting Through Simulated Annealing," Mathl. Comput. Modeling, Vol. 16, No. 1, 1992. pp 57-74. Pergamon Press, New York.
• [5]Greening, D.R., "A Taxonomy of Parallel Simulated Annealing Techniques," Computer Science Technical Report, University of California, Los Angeles, CSD-890050, August 1989.
• [6]Jayaraman, R. and Darma, F., "Error Tolerance in Parallel Simulated Annealing Technique," Proc. the International Conference on Computer Design, 1988.
• [7]Grover, L.K., "A New Simulated Annealing Algorithm for Standard Cell Placement," Proc. the International Conference on Computer-Aided Design, November 1986.
• [8]Banerjee, P., Jones. M.H., and Sargent, J.S., "Parallel Simulated Annealing Algorithm for Cell Placement on 1-lypercube Multiprocessors,’ IEEE Trans. on Parallel and Distributed System, Vol. 1, No. 1, January 1990.
• [9]M.D. Durand, "Parallel Simulated Annealing: Accuracy versus speed in placement," IEEE Design and Test, June 1989, pp 8-34.
• [10]Casotto, A., Romeo, F. and Sangiovanni Vincenelli, A.,"A Parallel Simulated Annealing Algorithm for the Placement of Macro-Cells," IEEE Transactions on Computer-Aided Design, September 1987, pp 838-847.
• [11]J.S. Rose, D.R. Blythe, W.M. Snelgrove, and Z.G Vranesic, "Fast, High Quality VLSI Placement on an M1MD Multiprocessor," Proc. International conference on Computer-Aided Design, 1986, pp 42-45.
• [12]F. Darema and G.F. Pfister, "Multipurpose Parallelism for VLSI CAD on the RP3," IEEE Design & Test of Computers, pp 19-27, Oct. 1987.
• [13]Jayaraman, R. and Rutenbar, R.A., "Floor planning by Annealing on a Hypercube Multiprocessor," Proc. the International Conference on Computer- Aided Design, 1987.
• [14]Jonathan Rose, Wolfgang Klebsch, and J. Wolf, "Temperature Measurement and Equilibrium Dynamics of Simulated Annealing Placement,’ IEEE Trans. on Computer-Aided Design, Vol. 9, No. 3, March 1990.
• [15]White, S.R., "Concepts of Scales in Simulated Annealing," Proc. IEEE Int. Conference on Computer Design, Port Chester, November 1984, pp 646-651.