GPU-based Markov decision process solver
Ársæll Þór Jóhannsson · 2009
Markov Decision Processes provide a mathematical framework for modeling decision making in situations where outcomes are partly random and partly under the control of the decision maker. MDPs are used in a variety of areas including robotics, automated control, planning, economics and manufacturing. For the solving of MDPs various different approaches exists. Value Iteration is an algorithm which falls under the class of Dynamic Programming methods and can be used to solve MDPs. In recent years Graphics Processing Units have been evolving rapidly from being very limited processing devices with the sole purpose of accelerating certain parts of the graphics pipeline into fully programmable and powerful parallel processing units. In the autumn of 2007 NVIDIA introduced CUDA, a hardware and software architecture for utilizing the GPU for general purpose calculations. In this thesis we introduce two parallel CUDA based implementations of the Value Iteration algorithm: Block Divided Iteration and Result Divided Iteration. We discuss the different approaches each algorithm takes for utilization of the parallel processing power of the CUDA device. We also present a framework we implemented which enables researchers to easily apply the parallel algorithms to MDPs within C or C++ applications. Empirical results are also presented which show a substantial performance improvement achieved by the parallel algorithms compared to a sequential implementation running on a CPU.%%%%Markov akvorðunarferlar (e. Markov Decision Processes) skilgreina staerðfraeðilegan ramma fyrir akvorðunartoku við aðstaeður þar sem niðurstaðan er að hluta til slembikennd og að hluta til undir þeim komin sem tekur akvorðunina. Notast er við Markov avorðunarferla a morgum mismunandi sviðum til daemis við stjornun velmenna, i sjalfvirkri akvorðunartoku og skipulagningu, hagfraeði og framleiðslustjornun. Til eru margar mismunandi aðferðir til þess að leysa Markov akvorðunarferla. Gildisitrun (e. Value Iteration) er reiknirit sem fellur undir flokk kvikra bestunar aðferða (e. Dynamic Programming) og haegt er að nota til að leysa Markov akvorðunar ferla. A undanfornum arum hafa skjakort verið að þroast fra þvi að hafa mjog takmarkaða reiknigetu og þann eina tilgang að auka hraða akveðins hluta grafik-pipunar yfir i að vera griðarlega oflug og að fullu forritanleg kort, sem serhaefð eru i samhliða vinnslu. Haustið 2007 kynnti NVIDIA CUDA, nýjung i baeði vel- og hugbunaði sem gerir kleift að nýta skjakort a auðveldan hatt fyrir almenna utreikninga. I þessari meistararitgerð kynnum við tvo reiknirit sem byggð eru a gildisitrun en nýta ser samhliða vinnslu og keyra a CUDA grafikkortum. Við raeðum a hvaða mismunandi hatt reikniritin nýta ser moguleika CUDA kortsins til samhliða vinnslu og kynnum einnig umgjorð (e. Framework), sem við utfaerðum, sem gerir aðilum kleift að beita reikniritunum a auðveldan hatt a Markov akvorðunarferla innan C eða C++ forrita. Niðurstoður eru kynntar þar sem sýnt er fram a umtalsverða yfirburði reikniritanna sem að nýta ser samhliða vinnslu i…