Parallel implementation of simulated annealing using transaction processing : a preliminary study

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review

View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Title of host publicationIEEE Region 10's Annual International Conference, Proceedings
PublisherIEEE
Pages72-76
Volume1
Publication statusPublished - 1995

Publication series

Name
Volume1

Conference

TitleProceedings of the 1994 IEEE Region 10's 9th Annual International Conference (TENCON'94). Part 1 (of 2)
CitySingapore, Singapore
Period22 - 26 August 1994

Abstract

Simulated annealing is an effective method for solving large combinatorial optimization problems. It has been successfully applied to the cell placement and routing problem of VLSI circuit design [SE88], and other classical optimization problems such as the traveling salesman problem and the graph partitioning problem [LA88]. One major drawback of simulated annealing is that it requires substantial amount of computation time. In this paper, we present a new parallel implementation of simulated annealing which is based on the concurrency control theory of database systems. The parallelized computation is serializable, hence the result obtained is equivalent to an serial execution of the original sequential annealing algorithm. In our implementation, we assume a shared-memory MIMD multiprocessing environment with 16 to 32 processors. Preliminary analysis shows that our method is able to achieve an efficiency (ratio of speedup to the number of processors) of about 40 to over 90 percent depending on the acceptance rate.

Citation Format(s)

Parallel implementation of simulated annealing using transaction processing : a preliminary study. / Pao, Derek C W.

IEEE Region 10's Annual International Conference, Proceedings. Vol. 1 IEEE, 1995. p. 72-76.

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review