Please use this identifier to cite or link to this item:
Title: High performance sequential and lock-free parallel access priority queue structures
Keywords: Priority queue, calendar queue, pending event set, future event list, discrete event simulation, simulator
Issue Date: 20-May-2006
Citation: GOH SIOW MONG (2006-05-20). High performance sequential and lock-free parallel access priority queue structures. ScholarBank@NUS Repository.
Abstract: This thesis presents novelties in the area of high performance sequential and lock-free parallel access priority queues. The choice of a high speed priority queue structure plays an integral role in numerous applications, particularly for sizeable scenarios such as large-scale discrete event simulations. The conventional priority queues fall into two categories: sorted-discipline and unsorted-discipline. We present a new paradigm called epoch-based deferred-sort priority queues (EDPQs) which have a combination of both sorted and unsorted-discipline structures. EDPQ is based on a novel structure called Twol and we prove that Twol-based EDPQs have constant-A? O(1) amortized complexity, where A? is the mean of jump of event distribution. For the parallel access domain, we extend the sequential Twol structure to derive a novel lock-free Twol priority queue which is the first multi-tier multi-bucket structure invented for lock-free parallel access. Lock-free Twol is non-blocking, linearizable, and has high degree of disjoint-access parallelism and scalability.
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
GohSiowMong_PhD_ECE_2006.pdf1.72 MBAdobe PDF



Page view(s)

checked on Apr 20, 2019


checked on Apr 20, 2019

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.