Change search
ReferencesLink to record
Permanent link

Direct link
Performance analysis of multithreaded sorting algorithms
Blekinge Institute of Technology, Faculty of Computing, Department of Computer Science and Engineering.
Blekinge Institute of Technology, Faculty of Computing, Department of Computer Science and Engineering.
2015 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

Context. Almost all of the modern computers today have a CPU withmultiple cores, providing extra computational power. In the new ageof big data, parallel execution is essential to improve the performanceto an acceptable level. With parallelisation comes new challenges thatneeds to be considered.

Objectives. In this work, parallel algorithms are compared and analysedin relation to their sequential counterparts, using the Java platform.Through this, find the potential speedup for multithreading andwhat factors affects the performance. In addition, provide source codefor multithreaded algorithms with proven time complexities.

Methods. A literature study was conducted to gain knowledge anddeeper understanding into the aspects of sorting algorithms and thearea of parallel computing. An experiment followed of implementing aset of algorithms from which data could be gather through benchmarkingand testing. The data gathered was studied and analysed with itscorresponding source code to prove the validity of parallelisation.

Results. Multithreading does improve performance, with two threadsin average providing a speedup of up to 2x and four threads up to3x. However, the potential speedup is bound to the available physicalthreads of the CPU and dependent of balancing the workload.

Conclusions. The importance of workload balancing and using thecorrect number of threads in relation to the problem to be solved,needs to be carefully considered in order to utilize the extra resourcesavailable to its full potential.

Place, publisher, year, edition, pages
2015. , 80 p.
Keyword [en]
Sorting algorithms, multithreading, time complexity, benchmarking
National Category
Computer Science
URN: urn:nbn:se:bth-10404OAI: diva2:839729
Subject / course
DV1478 Bachelor Thesis in Computer Science
Educational program
DVGDS Computer and System Science
Available from: 2015-08-03 Created: 2015-07-04 Last updated: 2015-08-03Bibliographically approved

Open Access in DiVA

Performance analysis of multithreaded sorting algorithms(1678 kB)437 downloads
File information
File name FULLTEXT02.pdfFile size 1678 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Nordin, HenrikJouper, Kevin
By organisation
Department of Computer Science and Engineering
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 437 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: 294 hits
ReferencesLink to record
Permanent link

Direct link