Advanced Concurrency Techniques for Concurrent Data Structures

Simple item page
dc.contributor.advisorMittal, Neeraj
dc.creatorGokhale, Shreyas
dc.date.accessioned2020-01-27T22:05:27Z
dc.date.available2020-01-27T22:05:27Z
dc.date.created2019-08
dc.date.issued2019-08
dc.date.submittedAugust 2019
dc.date.updated2020-01-27T22:05:27Z
dc.description.abstractConcurrent algorithms have gained importance as multi-core machines have become more ubiquitous. Several techniques are employed to enable the construction of such algorithms. We present algorithms for the Group Mutual Exclusion (GME) problem which can be used as an advanced concurrency technique to increase the performance of software built on concurrent data structures. The group mutual exclusion (GME) problem is a generalization of the classical mutual exclusion problem in which every critical section is associated with a type or session. Critical sections belonging to the same session can execute concurrently, whereas critical sections belonging to different sessions must be executed serially. The well-known read-write mutual exclusion problem is a special case of the group mutual exclusion problem. We present a new GME algorithm for an asynchronous shared-memory system under the Cache-Coherent model that, in addition to satisfying lockout freedom, bounded exit and concurrent entering properties, has O(1) step-complexity when the system contains no conflicting requests as well as O(1) space-complexity per GME object when the system contains sufficient number of GME objects. We also present a GME algorithm for the Distributed Shared Memory model that satisfies above properties and has optimal Remote Memory-Reference complexity. To the best of our knowledge, no existing GME algorithm has O(1) step-complexity for concurrent entering for either model. The Remote-Memory-Reference complexity of a request for cache-coherent model is only O(c˙) in the amortized case, where ˙c denotes the point contention of the request. Experiments indicate that our GME algorithm vastly outperforms well-known GME algorithms in most, if not all, cases. We also present a lock-based concurrent algorithm for a strictly-balanced red black tree data structure. Our algorithm can be implemented on hardware directly without requiring any additional system support such as transactional memory. We also make use of several optimizations to improve the performance of our tree. Our experimental results indicate that our lock-based algorithm for a strictly balanced binary search tree outperforms other relaxed balanced trees for read-dominated workloads.
dc.format.mimetypeapplication/pdf
dc.identifier.urihttps://hdl.handle.net/10735.1/7190
dc.language.isoen
dc.rights©2019 Shreyas Gokhale. All Rights Reserved.
dc.subjectComputer multitasking
dc.subjectComputer algorithms
dc.titleAdvanced Concurrency Techniques for Concurrent Data Structures
dc.typeDissertation
dc.type.materialtext
thesis.degree.departmentComputer Science
thesis.degree.grantorThe University of Texas at Dallas
thesis.degree.levelDoctoral
thesis.degree.namePHD

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
ETD-5608-011-GOKHALE-260798.35.pdf
Size:
999.46 KB
Format:
Adobe Portable Document Format
Description:
Dissertation
Download

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.84 KB
Format:
Plain Text
Description:
Download
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
5.84 KB
Format:
Plain Text
Description:
Download

Collections

UTD Theses and Dissertations