Highly-Efficient Concurrent Data Structures
Event details
| Date | 07.04.2014 |
| Hour | 11:00 › 12:00 |
| Speaker |
Panagiota Fatourou Panagiota Fatourou is an Assistant Professor at the Department of Computer Science, University of Crete, Greece and an affiliated faculty member of the Institute of Computer Science (ICS) of the Foundation for Research and Technology - Hellas (FORTH). Prior to joining the University of Crete and FORTH ICS, she was a full-time faculty member at the Department of Computer Science of the University of Ioannina, Greece. The academic years 1999-2000 and 2000-2001, she was a postdoc at Max-Planck Institut für Informatik, Saarbrücken, Germany, and at the Computer Science Department of the University of Toronto, Canada. She got a degree in Computer Science from the University of Crete, and a PhD degree in Computer Engineering from the University of Patras. Her research interests focus on the theory of parallel and distributed computing. |
| Location | |
| Category | Conferences - Seminars |
Abstract
We present highly-efficient synchronization techniques for asynchronous shared memory settings showing that they outperform all state-of-the-art lock-based and lock-free synchronization algorithms. We use these techniques to get efficient implementations of simple data structures, like stacks and queues.
We also present an implementation of a non-blocking binary search tree using single-word compare-and-swap operations. Insert and Delete operations that modify different parts of the tree do not interfere with one another, so they can run completely concurrently. Find operations only perform reads of shared memory. We provide an analysis to bound the worst-case amortized step complexity of performing a Find, Insert or Delete operation on this tree.
We present highly-efficient synchronization techniques for asynchronous shared memory settings showing that they outperform all state-of-the-art lock-based and lock-free synchronization algorithms. We use these techniques to get efficient implementations of simple data structures, like stacks and queues.
We also present an implementation of a non-blocking binary search tree using single-word compare-and-swap operations. Insert and Delete operations that modify different parts of the tree do not interfere with one another, so they can run completely concurrently. Find operations only perform reads of shared memory. We provide an analysis to bound the worst-case amortized step complexity of performing a Find, Insert or Delete operation on this tree.
Practical information
- Informed public
- Free
- This event is internal
Organizer
- EcoCloud
Contact
- Valérie Locca