Technical Report PHD-2015-06

TR#:PHD-2015-06
Class:PHD
Title: Practical Parallel Data Structures
Authors: Shahar Timnat
Supervisors: Erez Petrank
PDFPHD-2015-06.pdf
Abstract: In today's world, where nearly every desktop and laptop contains several cores, parallel computing has become the standard. Concurrent data structures are designed to utilize all available cores to achieve faster performance. In this thesis we design new concurrent data structures, we provide techniques for improving the guarantees of concurrent data structures, we propose efficient iterators for concurrent data structures, we propose new programming techniques, and we formally prove some inherent limitations of concurrent data structures.

In particular, we study data structures that offer progress guarantees. Wait-freedom, which is the strongest progress guarantee by the standard definitions, is a central concept in this thesis. We start by designing the first wait-free linked-list with practical performance. We then generalize the technique, and offer an automatic transformation that allows even a non-expert to design efficient wait-free data structures. We use the proposed transformation to obtain fast wait-free skiplist, and binary search tree.

Our study continues with an investigation of the concept of help in wait-free algorithms. The wait-free progress guarantee is often achieved by allowing some threads to help other threads complete their own work. We propose a formal definition for the notion of help, and prove that many wait-free data structures cannot be implemented without using help.

Our next step is to design an iterator that can be used in concurrent wait-free data structures. An iterator is an interface which allows a traversal of all of the nodes that belong to a certain data structure. Until recently, no wait-free data structures offered support for an iterator. Finally, we propose a programming paradigm that facilitates the use of hardware transactional memory (HTM) with concurrent data structures, and particularly with concurrent data structures that provide a progress guarantee.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2015/PHD/PHD-2015-06), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2015
To the main CS technical reports page

Computer science department, Technion
admin