Parallel Lauritzen-Spiegelhalter algorithm for probabilistic inference

Alexander V. Kozlov, Jaswinder Pal Singh

Research output: Contribution to journalConference articlepeer-review

41 Scopus citations


Probabilistic inference in belief networks is a promising technique for diagnosis, forecasting and decision analysis tasks. Unfortunately, exact inference can be very expensive computationally. In this paper, we examine whether probabilistic inference can be sped up effectively through parallel computation on real multiprocessors. Our experiments are performed on a 32-processor Stanford DASH multiprocessor, a cache-coherent shared-address-space machine with physically distributed main memory. We find that the major part of the calculation can be moved outside the actual propagation through the network, and yields good speedups. Speedups for the propagation itself depend on the structure of the network and the size of the cliques that the algorithm creates. We demonstrate good speedup on a CPCS subnetwork used for medical diagnosis. This result as well as a tendency for the speedup to increase with the size of the network invites practical application of parallel techniques for large Bayesian networks in expert systems.

Original languageEnglish (US)
Pages (from-to)320-329
Number of pages10
JournalProceedings of the ACM/IEEE Supercomputing Conference
StatePublished - 1994
Externally publishedYes
EventProceedings of the 1994 Supercomputing Conference - Washington, DC, USA
Duration: Nov 14 1994Nov 18 1994

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering


Dive into the research topics of 'Parallel Lauritzen-Spiegelhalter algorithm for probabilistic inference'. Together they form a unique fingerprint.

Cite this