The School of Computer Science at the University of Windsor is pleased to present…  

Colloquium Presentation by Dr. Trevor Brown 

“Fast and simple concurrent data structures using PathCAS” 

Date: Friday, December 2, 2022

Time: 11:00 am – 12:00 pm

Location: Erie Hall, Room 3123

Reminders: Two-part attendance is mandatory; arrive 5-10 minutes prior to the event starting – LATECOMERS WILL NOT BE ADMITTED once the door has been closed and the presentation has begun. Please be respectful of the presenter by NOT knocking on the door for admittance.

Abstract: 

Concurrent data structures are important building blocks for modern software, as they can be accessed by multiple threads of execution at the same time. To maximize the performance of concurrent data structures, researchers have often turned to highly complex fine-grained synchronization techniques. The resulting algorithms are fast but very difficult to reason about. On the other hand, simple synchronization techniques, such as hand-over-hand locking, or transactional memory, are easy to understand but can have limited performance or portability compared to handcrafted algorithms.

Techniques at both ends of this complexity-performance spectrum have been extensively explored, but less is known about the middle ground: techniques that are willing to sacrifice some performance for simplicity while remaining competitive with state-of-the-art handcrafted designs. In this talk, I will first survey simple techniques for designing concurrent data structures and illustrate when they perform well or poorly compared to state-of-the-art handcrafted data structures. I will then present PathCAS, a novel synchronization technique that carefully combines existing ideas with new insights while avoiding common overheads. PathCAS can be used to implement efficient search data structures relatively simply, and the resulting implementations can be competitive with highly tuned, handcrafted algorithms.

Keywords: Concurrency, data structures, synchronization, locks, lock-free

Biography: 

Dr. Trevor Brown is an assistant professor in the Cheriton School of Computer Science at the University of Waterloo. He did his PhD at the University of Toronto under Faith Ellen, and did postdocs at the Technion under Hagit Attiya and at IST Austria under Dan Alistarh. His research interests lie at the intersection between theory and practice and are focused on concurrent data structures, memory management, and the exploration of modern hardware features such as transactional memory and non-volatile RAM.