Relaxed Priority Queue & Evaluation of Locks

dc.contributor.authorAndersson, Ludvig
dc.contributor.authorRudén, Andreas
dc.contributor.departmentChalmers tekniska högskola / Institutionen för data och informationstekniksv
dc.contributor.departmentChalmers University of Technology / Department of Computer Science and Engineeringen
dc.contributor.examinerLjunglöf, Peter
dc.contributor.supervisorTsigas, Philippas
dc.date.accessioned2024-01-02T07:45:09Z
dc.date.available2024-01-02T07:45:09Z
dc.date.issued2023
dc.date.submitted2023
dc.description.abstractWe present a new, lock-free and concurrent priority queue, utilizing some ideas from [1] by Rukundo et al., that relaxes the traditional sequential semantics of the delete_min operation to achieve better scalability and performance. This relaxation is such that delete_min operations can be k-out-of-order when compared to sequential semantics, for which k has a well-defined upper bound. We experimentally compare our priority queue to established, concurrent priority queues, both with relaxed and non-relaxed semantics, and find that ours performs well. Furthermore, we conduct tests with locks using data structures from [1] by Rukundo et al., comparing the data structures’ performance when making use of a mix of atomic instructions and locks to that of the original design, which only utilizes atomic instructions. This allowed us to use different underlying data structures, and 3 different data structures using locks were tested; a linked list, a dynamic array, and a list of small arrays. We find that in some instances, this leads to increased cache-locality in data access patterns, and therefore an overall increase in performance. As an example of this, a speedup of up to 7.6 times was observed for the largest relaxation of the queue when using an array, compared to the original, with large improvements for other data structures as well.
dc.identifier.coursecodeDATX05
dc.identifier.urihttp://hdl.handle.net/20.500.12380/307483
dc.language.isoeng
dc.setspec.uppsokTechnology
dc.subjectConcurrency
dc.subjectData Structures
dc.subjectAlgorithms
dc.subjectPriority Queue
dc.subjectSemantic Relaxation
dc.subjectLock-free
dc.subjectScalability
dc.subjectScalability
dc.titleRelaxed Priority Queue & Evaluation of Locks
dc.type.degreeExamensarbete för masterexamensv
dc.type.degreeMaster's Thesisen
dc.type.uppsokH
local.programmeComputer science – algorithms, languages and logic (MPALG), MSc
Ladda ner
Original bundle
Visar 1 - 1 av 1
Hämtar...
Bild (thumbnail)
Namn:
CSE 23-99 AR LA.pdf
Storlek:
667.45 KB
Format:
Adobe Portable Document Format
Beskrivning:
License bundle
Visar 1 - 1 av 1
Hämtar...
Bild (thumbnail)
Namn:
license.txt
Storlek:
2.35 KB
Format:
Item-specific license agreed upon to submission
Beskrivning: