License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2018.18
URN: urn:nbn:de:0030-drops-98076
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9807/
Go to the corresponding LIPIcs Volume Portal

Daly, Henry ; Hassan, Ahmed ; Spear, Michael F. ; Palmieri, Roberto

NUMASK: High Performance Scalable Skip List for NUMA

pdf-format:
LIPIcs-DISC-2018-18.pdf (0.7 MB)

Abstract

This paper presents NUMASK, a skip list data structure specifically designed to exploit the characteristics of Non-Uniform Memory Access (NUMA) architectures to improve performance. NUMASK deploys an architecture around a concurrent skip list so that all metadata accesses (e.g., traversals of the skip list index levels) read and write memory blocks allocated in the NUMA zone where the thread is executing. To the best of our knowledge, NUMASK is the first NUMA-aware skip list design that goes beyond merely limiting the performance penalties introduced by NUMA, and leverages the NUMA architecture to outperform state-of-the-art concurrent high-performance implementations. We tested NUMASK on a four-socket server. Its performance scales for both read-intensive and write-intensive workloads (tested up to 160 threads). In write-intensive workload, NUMASK shows speedups over competitors in the range of 2x to 16x.

BibTeX - Entry

@InProceedings{daly_et_al:LIPIcs:2018:9807,
  author =	{Henry Daly and Ahmed Hassan and Michael F. Spear and Roberto Palmieri},
  title =	{{NUMASK: High Performance Scalable Skip List for NUMA}},
  booktitle =	{32nd International Symposium on Distributed Computing  (DISC 2018)},
  pages =	{18:1--18:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Ulrich Schmid and Josef Widder},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9807},
  URN =		{urn:nbn:de:0030-drops-98076},
  doi =		{10.4230/LIPIcs.DISC.2018.18},
  annote =	{Keywords: Skip list, NUMA, Concurrent Data Structure}
}

Keywords: Skip list, NUMA, Concurrent Data Structure
Collection: 32nd International Symposium on Distributed Computing (DISC 2018)
Issue Date: 2018
Date of publication: 04.10.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI