OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Lock-Free Search Data Structures: Throughput Modeling with Poisson Processes

Atalar, Aras and Renaud-Goud, Paul and Tsigas, Philippas Lock-Free Search Data Structures: Throughput Modeling with Poisson Processes. (2018) In: 22rd International Conference On Principles Of Distributed Systems (OPODIS 2018), 17 December 2018 - 19 December 2018 (Hong Kong, China).

(Document in English)

PDF (Publisher's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: https://doi.org/10.4230/LIPIcs.OPODIS.2018.9


This paper considers the modeling and the analysis of the performance of lock-free concurrentsearch data structures. Our analysis considers such lock-free data structures that are utilizedthrough a sequence of operations which are generated with a memoryless and stationary accesspattern. Our main contribution is a new way of analyzing lock-free concurrent search datastructures: our execution model matches with the behavior that we observe in practice andachieves good throughput predictions.Search data structures are formed of basic blocks, usually referred to as nodes, which can beaccessed by two kinds of events, characterized by their latencies; (i) CAS events originated as aresult of modifications of the search data structure (ii) Read events that occur during traversals.An operation triggers a set of events, and the running time of an operation is computed as thesum of the latencies of these events. We identify the factors that impact the latency of suchevents on a multi-core shared memory system. The main challenge (though not the only one) isthat the latency of each event mainly depends on the state of the caches at the time when it istriggered, and the state of caches is changing due to events that are triggered by the operationsof any thread in the system. Accordingly, the latency of an event is determined by the orderingof the events on the timeline.Search data structures are usually designed to accommodate a large number of nodes, whichmakes the occurrence of an event on a given node rare at any given time. In this context, wemodel the events on each node as Poisson processes from which we can extract the frequency andprobabilistic ordering of events that are used to estimate the expected latency of an operation,and in turn the throughput. We have validated our analysis on several fundamental lock-freesearch data structures such as linked lists, hash tables, skip lists and binary trees.

Item Type:Conference or Workshop Item (Paper)
Additional Information:ISBN:978-3-95977-098-9 https://drops.dagstuhl.de/opus/volltexte/2018/10069/
HAL Id:hal-02493874
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > Chalmers University of Technology (SWEDEN)
Laboratory name:
Deposited On:05 Feb 2020 09:14

Repository Staff Only: item control page