A Distributed Hash Table for Shared Memory

Wytse Hendrikus Marinus Oortwijn; Tom van Dijk; Jan Cornelis van de Pol

doi:10.1007/978-3-319-32152-3_2

A Distributed Hash Table for Shared Memory

Wytse Hendrikus Marinus Oortwijn, Tom van Dijk, Jan Cornelis van de Pol

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

26 Downloads (Pure)

Abstract

Distributed algorithms for graph searching require a high-performance CPU-efficient hash table that supports find-or-put. This operation either inserts data or indicates that it has already been added before. This paper focuses on the design and evaluation of such a hash table, targeting supercomputers. The latency of find-or-put is minimized by using one-sided RDMA operations. These operations are overlapped as much as possible to reduce waiting times for roundtrips. In contrast to existing work, we use linear probing and argue that this requires less roundtrips. The hash table is implemented in UPC. A peak-throughput of 114.9 million op/s is reached on an Infiniband cluster. With a load-factor of 0.9, find-or-put can be performed in 4.5μs on average. The hash table performance remains very high, even under high loads.

Original language	Undefined
Title of host publication	Parallel Processing and Applied Mathematics
Subtitle of host publication	11th International Conference, PPAM 2015, Krakow, Poland, September 6-9, 2015. Revised Selected Papers, Part II
Editors	Roman Wyrzykowski, Ewa Deelman, Jack Dongarra, Konrad Karczewski, Jacek Kitowski, Kazimierz Wiatr
Place of Publication	London
Publisher	Springer
Pages	15-24
Number of pages	10
ISBN (Electronic)	978-3-319-32152-3
ISBN (Print)	978-3-319-32151-6
DOIs	https://doi.org/10.1007/978-3-319-32152-3_2
Publication status	Published - Sep 2015
Event	11th International Conference on Parallel Processing and Applied Mathematics (PPAM 2016), Revised Selected Papers. - Krakow, Poland Duration: 6 Sep 2015 → 9 Sep 2015 Conference number: 11

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Verlag
Volume	9574
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	11th International Conference on Parallel Processing and Applied Mathematics (PPAM 2016), Revised Selected Papers.
Abbreviated title	PPAM 2015
Country	Poland
City	Krakow
Period	6/09/15 → 9/09/15

Keywords

high-performance computing
remote direct memory access
EWI-26785
IR-99479
par- titioned global address space
METIS-316032
Distributed hash table

Cite this

Oortwijn, W. H. M., van Dijk, T., & van de Pol, J. C. (2015). A Distributed Hash Table for Shared Memory. In R. Wyrzykowski, E. Deelman, J. Dongarra, K. Karczewski, J. Kitowski, & K. Wiatr (Eds.), Parallel Processing and Applied Mathematics: 11th International Conference, PPAM 2015, Krakow, Poland, September 6-9, 2015. Revised Selected Papers, Part II (pp. 15-24). (Lecture Notes in Computer Science; Vol. 9574). London: Springer. https://doi.org/10.1007/978-3-319-32152-3_2

Oortwijn, Wytse Hendrikus Marinus ; van Dijk, Tom ; van de Pol, Jan Cornelis. / A Distributed Hash Table for Shared Memory. Parallel Processing and Applied Mathematics: 11th International Conference, PPAM 2015, Krakow, Poland, September 6-9, 2015. Revised Selected Papers, Part II. editor / Roman Wyrzykowski ; Ewa Deelman ; Jack Dongarra ; Konrad Karczewski ; Jacek Kitowski ; Kazimierz Wiatr. London : Springer, 2015. pp. 15-24 (Lecture Notes in Computer Science).

@inproceedings{e92e09c88ccf4abb91277b062b004a6a,

title = "A Distributed Hash Table for Shared Memory",

abstract = "Distributed algorithms for graph searching require a high-performance CPU-efficient hash table that supports find-or-put. This operation either inserts data or indicates that it has already been added before. This paper focuses on the design and evaluation of such a hash table, targeting supercomputers. The latency of find-or-put is minimized by using one-sided RDMA operations. These operations are overlapped as much as possible to reduce waiting times for roundtrips. In contrast to existing work, we use linear probing and argue that this requires less roundtrips. The hash table is implemented in UPC. A peak-throughput of 114.9 million op/s is reached on an Infiniband cluster. With a load-factor of 0.9, find-or-put can be performed in 4.5μs on average. The hash table performance remains very high, even under high loads.",

keywords = "high-performance computing, remote direct memory access, EWI-26785, IR-99479, par- titioned global address space, METIS-316032, Distributed hash table",

author = "Oortwijn, {Wytse Hendrikus Marinus} and {van Dijk}, Tom and {van de Pol}, {Jan Cornelis}",

note = "eemcs-eprint-26785",

year = "2015",

month = "9",

doi = "10.1007/978-3-319-32152-3_2",

language = "Undefined",

isbn = "978-3-319-32151-6",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "15--24",

editor = "Roman Wyrzykowski and Ewa Deelman and Jack Dongarra and Konrad Karczewski and Jacek Kitowski and Kazimierz Wiatr",

booktitle = "Parallel Processing and Applied Mathematics",

}

Oortwijn, WHM, van Dijk, T & van de Pol, JC 2015, A Distributed Hash Table for Shared Memory. in R Wyrzykowski, E Deelman, J Dongarra, K Karczewski, J Kitowski & K Wiatr (eds), Parallel Processing and Applied Mathematics: 11th International Conference, PPAM 2015, Krakow, Poland, September 6-9, 2015. Revised Selected Papers, Part II. Lecture Notes in Computer Science, vol. 9574, Springer, London, pp. 15-24, 11th International Conference on Parallel Processing and Applied Mathematics (PPAM 2016), Revised Selected Papers., Krakow, Poland, 6/09/15. https://doi.org/10.1007/978-3-319-32152-3_2

A Distributed Hash Table for Shared Memory. / Oortwijn, Wytse Hendrikus Marinus; van Dijk, Tom ; van de Pol, Jan Cornelis.

Parallel Processing and Applied Mathematics: 11th International Conference, PPAM 2015, Krakow, Poland, September 6-9, 2015. Revised Selected Papers, Part II. ed. / Roman Wyrzykowski; Ewa Deelman; Jack Dongarra; Konrad Karczewski; Jacek Kitowski; Kazimierz Wiatr. London : Springer, 2015. p. 15-24 (Lecture Notes in Computer Science; Vol. 9574).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - A Distributed Hash Table for Shared Memory

AU - Oortwijn, Wytse Hendrikus Marinus

AU - van Dijk, Tom

AU - van de Pol, Jan Cornelis

N1 - eemcs-eprint-26785

PY - 2015/9

Y1 - 2015/9

N2 - Distributed algorithms for graph searching require a high-performance CPU-efficient hash table that supports find-or-put. This operation either inserts data or indicates that it has already been added before. This paper focuses on the design and evaluation of such a hash table, targeting supercomputers. The latency of find-or-put is minimized by using one-sided RDMA operations. These operations are overlapped as much as possible to reduce waiting times for roundtrips. In contrast to existing work, we use linear probing and argue that this requires less roundtrips. The hash table is implemented in UPC. A peak-throughput of 114.9 million op/s is reached on an Infiniband cluster. With a load-factor of 0.9, find-or-put can be performed in 4.5μs on average. The hash table performance remains very high, even under high loads.

AB - Distributed algorithms for graph searching require a high-performance CPU-efficient hash table that supports find-or-put. This operation either inserts data or indicates that it has already been added before. This paper focuses on the design and evaluation of such a hash table, targeting supercomputers. The latency of find-or-put is minimized by using one-sided RDMA operations. These operations are overlapped as much as possible to reduce waiting times for roundtrips. In contrast to existing work, we use linear probing and argue that this requires less roundtrips. The hash table is implemented in UPC. A peak-throughput of 114.9 million op/s is reached on an Infiniband cluster. With a load-factor of 0.9, find-or-put can be performed in 4.5μs on average. The hash table performance remains very high, even under high loads.

KW - high-performance computing

KW - remote direct memory access

KW - EWI-26785

KW - IR-99479

KW - par- titioned global address space

KW - METIS-316032

KW - Distributed hash table

U2 - 10.1007/978-3-319-32152-3_2

DO - 10.1007/978-3-319-32152-3_2

M3 - Conference contribution

SN - 978-3-319-32151-6

T3 - Lecture Notes in Computer Science

SP - 15

EP - 24

BT - Parallel Processing and Applied Mathematics

A2 - Wyrzykowski, Roman

A2 - Deelman, Ewa

A2 - Dongarra, Jack

A2 - Karczewski, Konrad

A2 - Kitowski, Jacek

A2 - Wiatr, Kazimierz

PB - Springer

CY - London

ER -

Oortwijn WHM, van Dijk T , van de Pol JC. A Distributed Hash Table for Shared Memory. In Wyrzykowski R, Deelman E, Dongarra J, Karczewski K, Kitowski J, Wiatr K, editors, Parallel Processing and Applied Mathematics: 11th International Conference, PPAM 2015, Krakow, Poland, September 6-9, 2015. Revised Selected Papers, Part II. London: Springer. 2015. p. 15-24. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-32152-3_2

Access to Document

10.1007/978-3-319-32152-3_2

CP51
open
Accepted author version, 736 KB