Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/15323
Title: High performance sequential and lock-free parallel access priority queue structures
Authors: GOH SIOW MONG
Keywords: Priority queue, calendar queue, pending event set, future event list, discrete event simulation, simulator
Issue Date: 20-May-2006
Source: 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.
URI: http://scholarbank.nus.edu.sg/handle/10635/15323
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

OPEN

NoneView/Download

Page view(s)

244
checked on Dec 18, 2017

Download(s)

286
checked on Dec 18, 2017

Google ScholarTM

Check


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