DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2018.18

NUMASK: High Performance Scalable Skip List for NUMA

Authors: Henry Daly, Ahmed Hassan, Michael F. Spear, and Roberto Palmieri

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

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.

Cite as

Henry Daly, Ahmed Hassan, Michael F. Spear, and Roberto Palmieri. NUMASK: High Performance Scalable Skip List for NUMA. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 18:1-18:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{daly_et_al:LIPIcs.DISC.2018.18,
  author =	{Daly, Henry and Hassan, Ahmed and Spear, Michael F. and Palmieri, Roberto},
  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 =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.18},
  URN =		{urn:nbn:de:0030-drops-98076},
  doi =		{10.4230/LIPIcs.DISC.2018.18},
  annote =	{Keywords: Skip list, NUMA, Concurrent Data Structure}
}

Search Results

Documents authored by Daly, Henry

NUMASK: High Performance Scalable Skip List for NUMA

Abstract

Cite as

Thanks for your feedback!

Could not send message