The Taub Faculty of Computer Science Events and Talks

Shared-memory multiprocessors execute concurrently multiple threads of computation that communicate and synchronize through shared memory. Typically, this communication and synchronization is done via concurrent data structures. The efficiency of these data structures is crucial to performance. Furthermore, new challenges arise in designing scalable concurrent data structures that can perform well with an increasing number of concurrent threads. Non-blocking data structures are scalable and provide a progress guarantee. If several threads attempt to concurrently apply an operation on the structure, it is guaranteed that one of the threads will eventually make progress. Consequently, the popular mutual exclusion synchronization protocol cannot be used in non-blocking data structures. We address the design of a high-performance, concurrent, non-blocking data structures for shared memory multi-processor platforms. We present a high performance linked list and priority queue, the first non-blocking balanced B+tree, as well as a method for managing the memory for lock-free and wait-free data structures. This last result provides a performance boost to the data structures that care for dynamic memory management and will be discussed in details in the lecture. All the above-mentioned algorithms were evaluated empirically and shown to provide high throughput and performance.