Parallel simulated annealing for emission tomography

K. A. Girodias, H. H. Barrett, R. L. Shoemaker

Research output: Contribution to journalArticlepeer-review

17 Scopus citations


A method for implementing simulated annealing in parallel to speed up the execution of emission tomography (ET) image reconstruction is presented. A high degree of parallelism can be attained by using a parallel-acceptance partitioning strategy, in which perturbations to subsets of the estimate are evaluated in parallel. However because the point spread function in ET imaging systems is globally dependent, processors cannot update the current estimate independently. Consequently, processors must be synchronized each time a perturbation is accepted to avoid introducing error. This can produce excessive communications overhead, especially when the acceptance rate is high. An energy function is constructed to reduce the synchronization requirements by using a reformulation of the log-likelihood function from the expectation maximization (EM) algorithm. The approach is to change the global dependence in the energy function from the current estimate to the estimate generated during the last iteration. The synchronization requirements for guaranteed convergence are then significantly reduced from once per acceptance to once per iteration. This parallel implementation on 54 Inmos T800 transputers connected in a ring topology resulted in execution times that were almost 50 times faster than on a VAX 8600.

Original languageEnglish (US)
Article number002
Pages (from-to)921-938
Number of pages18
JournalPhysics in medicine and biology
Issue number7
StatePublished - 1991

ASJC Scopus subject areas

  • Radiological and Ultrasound Technology
  • Radiology Nuclear Medicine and imaging


Dive into the research topics of 'Parallel simulated annealing for emission tomography'. Together they form a unique fingerprint.

Cite this