Layering Data Structures over Skip Graphs for Increased NUMA Locality
| Autor: | Samuel Thomas, Hammurabi Mendes |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Structure (mathematical logic)
Scheme (programming language) Computer science Locality 020207 software engineering 0102 computer and information sciences 02 engineering and technology Skip graph Data structure Abstract data type 01 natural sciences 010201 computation theory & mathematics Synchronization (computer science) 0202 electrical engineering electronic engineering information engineering Hardware_ARITHMETICANDLOGICSTRUCTURES Priority queue Algorithm computer computer.programming_language |
| Zdroj: | PODC |
| DOI: | 10.1145/3293611.3331576 |
| Popis: | We present a lock-free, linearizable, and NUMA-aware data structure that implements sets, maps, and priority queue abstract data types (ADTs), based on using thread-local, sequential maps that are used to "jump" to suitable positions in a lock-free, linearizable variant of a skip graph. Our skip graph is suitably constrained in height and subjected to a data partition scheme that reduces contention and increases NUMA locality. We developed an additional skip graph variant, which we call sparse skip graph, that causes our thread-local maps as well as our shared structure to become more sparse. Compared to using regular skip graphs, sparse skip graphs show increased performance in workloads dominated by "insert" or "remove" operations, and comparable performance in workloads dominated by "contains" operations. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|