Parallel algorithms for Bayesian indoor positioning systems

Konstantinos Kleisouris, Richard P. Martin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

We present two parallel algorithms and their Unified Parallel C implementations for Bayesian indoor positioning systems. Our approaches are founded on Markov Chain Monte Carlo simulations. We evaluated two basic partitioning schemes: inter-chain partitioning which distributes entire Markov chains to different processors, and intra-chain which distributes a single chain across processors. Evaluations on a 16-node symmetric multiprocessor, a 4-node cluster comprising of quad processors, and a 16 single-processor-node cluster, suggest that for short chains intra-chain scales well on the first two platforms with speedups of up to 12. On the other hand, inter-chain gives speedups of 12 only for very long chains, sometimes of up to 60,000 iterations, on all three platforms. We used the LogGP model to analyze our algorithms and predict their performance. Model predictions for inter-chain are within 5% of the actual execution time, while for intra-chain they are 7%-25% less due to load imbalance not captured in the model.

Original languageEnglish (US)
Title of host publication2007 International Conference on Parallel Processing, ICPP
DOIs
StatePublished - 2007
Event36th International Conference on Parallel Processing in Xi'an, ICPP - Xi'an, China
Duration: Sep 10 2007Sep 14 2007

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918

Other

Other36th International Conference on Parallel Processing in Xi'an, ICPP
CountryChina
CityXi'an
Period9/10/079/14/07

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Engineering(all)

Fingerprint Dive into the research topics of 'Parallel algorithms for Bayesian indoor positioning systems'. Together they form a unique fingerprint.

Cite this