You are here

The Design, Implementation, and Refinement of Wait-Free Algorithms and Containers

Download pdf | Full Screen View

Date Issued:
2015
Abstract/Description:
My research has been on the development of concurrent algorithms for shared memory systems that provide guarantees of progress.Research into such algorithms is important to developers implementing applications on mission critical and time sensitive systems.These guarantees of progress provide safety properties and freedom from many hazards, such as dead-lock, live-lock, and thread starvation.In addition to the safety concerns, the fine-grained synchronization used in implementing these algorithms promises to provide scalable performance in massively parallel systems.My research has resulted in the development of wait-free versions of the stack, hash map, ring buffer, vector, and a multi-word compare-and-swap algorithms.Through this experience, I have learned and developed new techniques and methodologies for implementing non-blocking and wait-free algorithms.I have worked with and refined existing techniques to improve their practicality and applicability.In the creation of the aforementioned algorithms, I have developed an association model for use with descriptor-based operations.This model, originally developed for the multi-word compare-and-swap algorithm, has been applied to the design of the vector and ring buffer algorithms.To unify these algorithms and techniques, I have released Tervel, a wait-free library of common algorithms and containers.This library includes a framework that simplifies and improves the design of non-blocking algorithms.I have reimplemented several algorithms using this framework and the resulting implementation exhibits less code duplication and fewer perceivable states.When reimplementing algorithms, I have adapted their Application Programming Interface (API) specification to remove ambiguity and non-deterministic behavior found when using a sequential API in a concurrent environment.To improve the performance of my algorithm implementations, I extended OVIS's Lightweight Distributed Metric Service (LDMS)'s data collection and transport system to support performance monitoring using perf_event and PAPI libraries.These libraries have provided me with deeper insights into the behavior of my algorithms, and I was able to use these insights to improve the design and performance of my algorithms.
Title: The Design, Implementation, and Refinement of Wait-Free Algorithms and Containers.
13 views
8 downloads
Name(s): Feldman, Steven, Author
Dechev, Damian, Committee Chair
Heinrich, Mark, Committee Member
Orooji, Ali, Committee Member
Mucciolo, Eduardo, Committee Member
University of Central Florida, Degree Grantor
Type of Resource: text
Date Issued: 2015
Publisher: University of Central Florida
Language(s): English
Abstract/Description: My research has been on the development of concurrent algorithms for shared memory systems that provide guarantees of progress.Research into such algorithms is important to developers implementing applications on mission critical and time sensitive systems.These guarantees of progress provide safety properties and freedom from many hazards, such as dead-lock, live-lock, and thread starvation.In addition to the safety concerns, the fine-grained synchronization used in implementing these algorithms promises to provide scalable performance in massively parallel systems.My research has resulted in the development of wait-free versions of the stack, hash map, ring buffer, vector, and a multi-word compare-and-swap algorithms.Through this experience, I have learned and developed new techniques and methodologies for implementing non-blocking and wait-free algorithms.I have worked with and refined existing techniques to improve their practicality and applicability.In the creation of the aforementioned algorithms, I have developed an association model for use with descriptor-based operations.This model, originally developed for the multi-word compare-and-swap algorithm, has been applied to the design of the vector and ring buffer algorithms.To unify these algorithms and techniques, I have released Tervel, a wait-free library of common algorithms and containers.This library includes a framework that simplifies and improves the design of non-blocking algorithms.I have reimplemented several algorithms using this framework and the resulting implementation exhibits less code duplication and fewer perceivable states.When reimplementing algorithms, I have adapted their Application Programming Interface (API) specification to remove ambiguity and non-deterministic behavior found when using a sequential API in a concurrent environment.To improve the performance of my algorithm implementations, I extended OVIS's Lightweight Distributed Metric Service (LDMS)'s data collection and transport system to support performance monitoring using perf_event and PAPI libraries.These libraries have provided me with deeper insights into the behavior of my algorithms, and I was able to use these insights to improve the design and performance of my algorithms.
Identifier: CFE0005946 (IID), ucf:50813 (fedora)
Note(s): 2015-12-01
Ph.D.
Engineering and Computer Science, Computer Science
Doctoral
This record was generated from author submitted information.
Subject(s): concurrency -- non-blocking -- wait-free -- lock-free
Persistent Link to This Record: http://purl.flvc.org/ucf/fd/CFE0005946
Restrictions on Access: public 2015-12-15
Host Institution: UCF

In Collections