Google Research

Fast and Highly Scalable Bayesian MDP on a GPU Platform

  • He Zhou
  • Sunil P. Khatri
  • Jiang Hu
  • Frank Liu
  • Cliff Sze
ACM Conference on Bioinformatics, Computational Biology, and Health Informatics (ACM BCB), ACM (2017)


By employing Optimal Bayesian Robust (OBR), Bayesian Markov Decision Process (BMDP) can be a power optimization method to solve large problems. However, due to the “curse of dimensionality”, the data storage limitation hinders the practical application of BMDP. To overcome this impediment, we propose a novel Improved Compressed Sparse Row (ICSR) data structure in this paper, and developed the implementation of BMDP solver with ICSR technique on a heterogeneous platform with GPU. The simulation results demonstrate that our techniques achieve about a 5× reduction in memory utilization over using full matrix, and an average speedup of 4.1× over using full matrix. Additionally, we present a study of the tradeoff between the runtime and the trends of result difference between our ICSR techniques and using full matrix.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work