One Computer Science MSc thesis to be presented on 23 April

Wednesday, 23 April there will be a master thesis presentation in Computer Science at Lund University, Faculty of Engineering.

The presentation will take place in E:1426.

Note to potential opponents: Register as an opponent to the presentation of your choice by sending an email to the examiner for that presentation (firstname.lastname@cs.lth.se). Do not forget to specify the presentation you register for! Note that the number of opponents may be limited (often to two), so you might be forced to choose another presentation if you register too late. Registrations are individual, just as the oppositions are! More instructions are found on this page.

11:00-12:00 in E:1426

Presenter: Isabella Ljung 
Title: Solving the minimum spanning tree problem - a parallel algorithm
Examiner: Michael Doggett
Supervisor: Jonas Skeppstedt (LTH)

In this thesis the problem of the minimum spanning tree is researched. The aim is to compare a parallel algorithm to a fast sequential algorithm, in this case Jarnik’s, and to find which method of synchronisation is the fastest. The parallel algorithm is based on Bader-Cong’s algorithm from 2006. The algorithm in this thesis is modified and the used synchronisation are locks, atomic variables and hardware transactional memory. Testing is performed on graphs of varying sizes, the number of vertices varies from 10 000 to 10 000 000 vertices and the graphs tested are both sparse and dense. For small input Jarnik’s algorithm is faster but for larger graphs the parallel algorithm is significantly faster. The parallel version is up to 229,8% faster than the sequential algorithm. The fastest method of synchronisation is most often atomic variables and hardware transactional memory is usually the worst.

Link to popular science summary: To be uploaded