טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentTimnat Shahar
SubjectPractical Parallel Data Structures
DepartmentDepartment of Computer Science
Supervisor Professor Erez Petrank
Full Thesis textFull thesis text - English Version


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.