is Íslenska en English

Lokaverkefni (Meistara)

Háskólinn í Reykjavík > Tæknisvið / School of Technology > MSc Tölvunarfræðideild / Department of Computer Science >

Vinsamlegast notið þetta auðkenni þegar þið vitnið til verksins eða tengið í það: http://hdl.handle.net/1946/7419

Titill: 
  • Titill er á ensku GPU-based Markov decision process solver
  • Lausn Markov ákvörðunarferla á grafíkkortum
Námsstig: 
  • Meistara
Leiðbeinandi: 
Útdráttur: 
  • Útdráttur er á ensku

    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 ákvörðunarferlar (e. Markov Decision Processes) skilgreina stærðfræðilegan ramma fyrir ákvörðunartöku við aðstæður þar sem niðurstaðan er að hluta til slembikennd og að hluta til undir þeim komin sem tekur ákvörðunina. Notast er við Markov ávörðunarferla á mörgum mismunandi sviðum til dæmis við stjórnun vélmenna, í sjálfvirkri ákvörðunartöku og skipulagningu, hagfræði og framleiðslustjórnun. Til eru margar mismunandi aðferðir til þess að leysa Markov ákvörðunarferla. Gildisítrun (e. Value Iteration) er reiknirit sem fellur undir flokk kvikra bestunar aðferða (e. Dynamic Programming) og hægt er að nota til að leysa Markov ákvörðunar ferla. Á undanförnum árum hafa skjákort verið að þróast frá því að hafa mjög takmarkaða reiknigetu og þann eina tilgang að auka hraða ákveðins hluta grafík-pípunar yfir í að vera gríðarlega öflug og að fullu forritanleg kort, sem sérhæfð eru í samhliða vinnslu. Haustið 2007 kynnti NVIDIA CUDA, nýjung í bæði vél- og hugbúnaði sem gerir kleift að nýta skjákort á auðveldan hátt fyrir almenna útreikninga. Í þessari meistararitgerð kynnum við tvö reiknirit sem byggð eru á gildisítrun en nýta sér samhliða vinnslu og keyra á CUDA grafíkkortum. Við ræðum á hvaða mismunandi hátt reikniritin nýta sér möguleika CUDA kortsins til samhliða vinnslu og kynnum einnig umgjörð (e. Framework), sem við útfærðum, sem gerir aðilum kleift að beita reikniritunum á auðveldan hátt á Markov ákvörðunarferla innan C eða C++ forrita. Niðurstöður eru kynntar þar sem sýnt er fram á umtalsverða yfirburði reikniritanna sem að nýta sér samhliða vinnslu í samanburði við hefðbundna útfærslu sem keyrir eingöngu á örgjörva tölvunnar.

Athugasemdir: 
  • Tölvunarfræði, Thesis
Samþykkt: 
  • 25.1.2011
URI: 
  • http://hdl.handle.net/1946/7419


Skrár
Skráarnafn Stærð AðgangurLýsingSkráartegund 
MSc_Arsaell-Thor-Johannsson.pdf1.21 MBOpinnHeildartextiPDFSkoða/Opna