Ph.D Thesis

Ph.D StudentHillel Eshcar
SubjectConcurrent Data Structures: Methodologies and
Inherent Limitations
DepartmentDepartment of Computer Science
Supervisor PROF. Hagit Attiya
Full Thesis textFull thesis text - English Version


Since clock frequency is hardly advancing in recent years, major chip manufacturers are shifting the focus from improving the speed of individual processors into increasing parallel processing capabilities . Multi-core architecture puts several cores on one chip, each running several threads in parallel.

At the heart of many concurrent applications lie concurrent data structures, the subject of this thesis. The main goal of this thesis is to facilitate writing, understanding, and maintaining concurrent data structures and concurrent applications in general.

We provide an algorithm for a multi-word synchronization operation, which accesses several data items in one atomic operation. In addition, we present a new approach in which implementations follow a built-in coloring scheme. Colors are integrated into items, and the implementation maintains a legal coloring while applying operations to data items. We demonstrate this approach with lock-free algorithms for list-based data structures. Our algorithms are the first to provably decrease interference among operations, thereby increasing the throughput of the execution.

In the transactional memory (TM) approach concurrent processes synchronize via in-memory transactions. It raises a lot of hope for mastering the complexity of concurrent programming. In its simplest form, the programmer defines a transaction by enclosing a set of statements in an atomic block; the underlying run time system is responsible for executing the transaction, while handling any contention issues.

To guide algorithm designers in their attempt to find better and more efficient implementations and to demonstrate which directions are futile, we explore the boundaries and tradeoffs of TM.

We show that there is an inherent tradeoff: no TM implementation can avoid interference on disjoint data and have read-only transactions that always complete successfully while never writing to the memory. In fact, we prove that read-only transactions in such implementations, reading t items, must write to at least t-1 memory locations.

In practice, TM must allow accessing the same items from inside and outside a transaction; this is crucial both for interoperability with legacy code and in order to improve the performance of the TM. Supporting privatization, allows the programmer make some items private to a process; the process can thereafter access them non-transactionally, without interference by other processes. We study the theoretical complexity of privatization, and show an inherent cost, linear in the number of privatized items.