In this work 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, which explore the probability distributions of the unknown position variables using statistical sampling. We evaluated two basic partitioning strategies: 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 sampling chains intra-chain parallelism scales well on the first two platforms, with speedups of up to 12. On the other hand, inter-chain parallelism gives speedups of 12 only for very long Markov chains, sometimes of up to 60,000 samples, on all three platforms. We used the LogGP model to analyze our algorithms and predict their performance. We found the model a useful guide in our algorithm design, as well as useful for predicting performance. When running the inter-chain algorithm, the model predictions are within 5% of the actual execution times, while for intra-chain they are 7%-25% less than the measured times due to load imbalance not captured in the model.

Konstantinos Kleisouris is a Ph.D. candidate at the Computer Science Department of Rutgers, The State University of New Jersey. He works under the supervision of Prof. Richard Martin and his current research focuses on improving the speed of localization schemes based on Bayesian Networks. He holds an M.S. degree in Computer Science from Rutgers University and a B.S. degree in Computer Science from the University of Patras, Greece.