FEAST
| Autor: | Aravind Natarajan, Arunmoezhi Ramachandran, Neeraj Mittal |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Amortized analysis
Computer science Concurrent data structure 020207 software engineering 0102 computer and information sciences 02 engineering and technology Parallel computing 01 natural sciences Computer Science Applications Tree (data structure) Computational Theory and Mathematics Shared memory 010201 computation theory & mathematics Hardware and Architecture Binary search tree Modeling and Simulation 0202 electrical engineering electronic engineering information engineering Non-blocking algorithm Enhanced Data Rates for GSM Evolution Software |
| Zdroj: | ACM Transactions on Parallel Computing. 7:1-64 |
| ISSN: | 2329-4957 2329-4949 |
| DOI: | 10.1145/3391438 |
| Popis: | We present a lock-free algorithm for concurrent manipulation of a binary search tree (BST) in an asynchronous shared memory system that supports search, insert, and delete operations. In addition to read and write instructions, our algorithm uses (single-word) compare-and-swap (CAS) and bit-test-and-set (BTS) read-modify-write (RMW) instructions, both of which are commonly supported by many modern processors including Intel 64 and AMD64. In contrast to most of the existing concurrent algorithms for a binary search tree, our algorithm is edge-based rather than node-based. When compared to other concurrent algorithms for a binary search tree, modify (insert and delete) operations in our algorithm (a) work on a smaller section of the tree, (b) execute fewer RMW instructions, or (c) use fewer dynamically allocated objects. In our experiments, our lock-free algorithm significantly outperformed all other algorithms for a concurrent binary search tree especially when the contention was high. We also describe modifications to our basic lock-free algorithm so that the amortized complexity of any operation in the modified algorithm can be bounded by the sum of the tree height and the point contention to within a constant factor while preserving the other desirable features of our algorithm. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|