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
A Comparison of Performance Between a CPU and a GPU on Prime Factorization Using Eratosthene's Sieve and Trial Division
KTH, School of Computer Science and Communication (CSC).
KTH, School of Computer Science and Communication (CSC).
2017 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesisAlternative title
En jämförelse i prestanda mellan en CPU och en GPU avseende primtalsfaktorisering med hjälp av Eratosthenes såll och Försöksdivison (Swedish)
Abstract [en]

There has been remarkable advancement in Multi-cored Processing Units over the past decade. GPUs, which were originally designed as a specialized graphics processor, are today used in a wide variety of other areas. Their ability to solve parallel problems is unmatched due to their massive amount of simultaneously running cores. Despite this, most algorithms in use today are still fully sequential and do not utilize the processing power available. The Sieve of Eratosthenes and Trial Division are two very naive algorithms which combined can be used to find a number's unique combinataion of prime factors.

This paper sought to compare the performance of a CPU and a GPU when tasked with prime factorization on seven different data sets. Five different programs were created, two running both algorithms on the CPU, two running both algorithms on the GPU and one program utilizing both. Each data set was presented multiple times to each program in different sizes ranging from one to half a million. The result was uniform in that the CPU greatly outperformed the GPU in every test case for this specific implementation.

Abstract [sv]

Flerkärniga processorer har under det senaste årtiondet utvecklats markant. Grafikkorten, designade för att excellera i grafiktunga beräkningar, används idag inom flera andra områden. Kortens förmåga att lösa paralleliserbara problem är oöverträffad tack vare deras massiva antal kärnor. Trots detta är majoriteten av algoritmer idag fortfarande helt sekventiella. Eratosthenes såll och Försöksdivision är två väldigt naiva algoritmer som tillsammans kan användas för att finna ett tals unika uppsättning primtalsfaktorer.

Det här arbetet strävade efter att jämföra prestandan mellan en CPU och en GPU vad gäller uppgiften att faktorisera tal från sju olika uppsättningar data. Fem implementationer skrevs, varav två var begränsade till CPU:ns processorkraft, två begränsade till GPU:ns processorkraft och en som utnyttjade båda. Varje uppsättning data förekom i olika storlekar i omfånget ental till en halv miljon. Resultatet var entydigt på så sätt att CPU:n markant överträffade GPU:n i samtliga testfall.

Place, publisher, year, edition, pages
2017. , 26 p.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-208678OAI: oai:DiVA.org:kth-208678DiVA: diva2:1107835
Subject / course
Computer Science
Educational program
Master of Science in Engineering - Computer Science and Technology
Supervisors
Examiners
Available from: 2017-06-18 Created: 2017-06-11 Last updated: 2017-06-18Bibliographically approved

Open Access in DiVA

fulltext(431 kB)91 downloads
File information
File name FULLTEXT01.pdfFile size 431 kBChecksum SHA-512
95ca8cc81e243dee872ab63c5d67a4ca4c8c7539f2f5658b219092a89b4867fe2810e7f9db486c96993c3f9a3e595de6f5f987a7e4bfd6a2158d6831834b4581
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Borg, Caroline W.Dackebro, Erik
By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 91 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

Total: 94 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