Award Date

12-1-2016

Degree Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science

First Committee Member

Ajoy K. Datta

Second Committee Member

John Minor

Third Committee Member

Ju-Yeon Jo

Fourth Committee Member

Emma Regentova

Number of Pages

98

Abstract

We present a non-blocking algorithm for a concurrent heap in asynchronous shared memory multiprocessors. Processors in these machines often execute instructions at varying speeds and are subject to arbitrarily long delays. Our implementation supports Non-blocking Insert, Delete, and Find-Min operations on a heap. Non-blocking techniques avoid the drawbacks associated with mutual exclusion and also admit improved parallelism. Insert and DeleteMin operations in heap take more than one atomic instruction to complete, thus, it is possible that a new operation may be started before the previous one completes, leaving heap inconsistent between operations. We have represented heap as an array of pointers. Any modification to the heap is done by using single-word Compare&Swap instructions. If all update operations modify different parts of the heap, they run completely concurrently. Our approach guarantees lock-freedom for all concurrent threads and wait-freedom if threads execute operations on different nodes of the heap.

Keywords

Concurrent Data Structures; Heap; Multicore Systems

Disciplines

Computer Sciences

File Format

pdf

Degree Grantor

University of Nevada, Las Vegas

Language

English

Rights

IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/

Download


Share

COinS