Skip to main navigation Skip to search Skip to main content

Efficient Solving of Markov Decision Processes on GPUs Using Parallelized Sparse Matrices

  • Adrian Sapio
  • , Shuvra S. Bhattacharyya
  • , Marilyn Wolf

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

11 Citations (Scopus)

Abstract

Markov Decision Processes (MDPs) provide important capabilities for facilitating the dynamic adaptation of hardware and software configurations to the environments in which they operate. However, the use of MDPs in embedded signal processing systems is limited because of the large computational demands for solving this class of system models. This paper presents Sparse Parallel Value Iteration (SPVI), a new algorithm for solving large MDPs on resource-constrained embedded systems that are equipped with mobile GPUs. SPVI leverages recent advances in parallel solving of MDPs and adds sparse linear algebra techniques to significantly outperform the state-of-the-art. The method and its application are described in detail, and demonstrated with case studies that are implemented on an NVIDIA Tegra K1 System On Chip (SoC). The experimental results show execution time improvements in the range of 65 % -78% for several applications. SPVI also lifts restrictions required by other MDP solver approaches, making it more widely compatible with large classes of optimization problems.

Original languageEnglish
Title of host publication2018 Conference on Design and Architectures for Signal and Image Processing, DASIP 2018
PublisherIEEE COMPUTER SOCIETY PRESS
Pages13-18
Number of pages6
ISBN (Electronic)9781538682371
DOIs
Publication statusPublished - Dec 2018
Publication typeA4 Article in conference proceedings
EventConference on Design and Architectures for Signal and Image Processing - Porto, Portugal
Duration: 10 Oct 2018 → 12 Oct 2018

Publication series

NameConference on Design and Architectures for Signal and Image Processing, DASIP
ISSN (Print)2164-9766

Conference

ConferenceConference on Design and Architectures for Signal and Image Processing
Country/TerritoryPortugal
CityPorto
Period10/10/18 → 12/10/18

Keywords

  • CUDA
  • GPU
  • Markov decision processes
  • MDP
  • Sparsity
  • Value iteration

Publication forum classification

  • Publication forum level 1

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design
  • Computer Vision and Pattern Recognition
  • Hardware and Architecture
  • Signal Processing
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Efficient Solving of Markov Decision Processes on GPUs Using Parallelized Sparse Matrices'. Together they form a unique fingerprint.

Cite this