Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
High Performance Implementationof Winner Selection Algorithms
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology.
2017 (English)Independent thesis Advanced level (professional degree), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

The process to find candidates, that fit certain win-conditions, from a collectionof wagers is the purpose of a winner selection algorithm. These candidates are filtered out in different groups called winning groups depending on the win-conditions. Svenska Spel AB is the largest company in the regulated gaming market in Sweden. It is crucial for winner selection algorithms at Svenska Spel to run as efficiently as possible, since results needs to be produced in near real time for many different games. Additionally, new services and features can be developed by having efficient algorithms that are not feasible with current sequential implementations. In this paper a variety of parallel approaches using OpenMP, Pthreads and CUDA are investigated to create efficient implementations of winner selection algorithms for the games Lotto and Bomben at Svenska Spel. Various preprocessing schemes are used on the original dataset to affect calculation times and enable different types of algorithms. Some of the algorithms are also extended, meaning they run on several, if not all, permutations of possible outcomes, something that is not possible to execute in reasonable time with thecurrent implementations. If these extended runs are feasible then it enables the possibility for new functionality with a more detailed statistical overview thatwere too compute heavy or slow to determine before. OpenMP and Pthreads run on the CPU while the CUDA algorithm uses the GPU. By using a baseline implementation they are all individually compared to determine their speed up. The effect preprocessing overhead and data allocation for CUDA is also evaluated. It results indicate that by performing all required preprocessing for the different approaches do not yield any performance gain. The preprocessing time, and data transfer to the GPU, occupies too large of a chunk of the execution timethat it is impossible to gain anything from doing the computations in parallel. However, by utilizing the preprocessed data several times significant speed upcan be achieved. The extended algorithm for Lotto runs more than 200 times faster on the GPU compared to the baseline algorithm. The parallel implementations for Bomben ranges from seven to 20 times the speed up, whichis not as impressive but arguable usable in different cases.

Place, publisher, year, edition, pages
2017. , p. 84
Series
UPTEC IT, ISSN 1401-5749 ; 17026
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:uu:diva-341767OAI: oai:DiVA.org:uu-341767DiVA, id: diva2:1182760
Educational program
Master of Science Programme in Information Technology Engineering
Supervisors
Examiners
Available from: 2018-02-14 Created: 2018-02-14 Last updated: 2018-02-21Bibliographically approved

Open Access in DiVA

fulltext(3063 kB)22 downloads
File information
File name FULLTEXT01.pdfFile size 3063 kBChecksum SHA-512
db10e0de01776246d6bf9e75cf4516400601a0deaf4b1562352b67d6044dd910dd9365fbeca5b8c52f5ec17ed295fa57be3c3dea9ee8f00f9bf0883af68c7f9d
Type fulltextMimetype application/pdf

By organisation
Department of Information Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 22 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 48 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf