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 proceedingConference contributionAcademicpeer-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 languageUndefined
    Title of host publicationParallel Processing and Applied Mathematics
    Subtitle of host publication11th International Conference, PPAM 2015, Krakow, Poland, September 6-9, 2015. Revised Selected Papers, Part II
    EditorsRoman Wyrzykowski, Ewa Deelman, Jack Dongarra, Konrad Karczewski, Jacek Kitowski, Kazimierz Wiatr
    Place of PublicationLondon
    PublisherSpringer
    Pages15-24
    Number of pages10
    ISBN (Electronic)978-3-319-32152-3
    ISBN (Print)978-3-319-32151-6
    DOIs
    Publication statusPublished - Sep 2015
    Event11th International Conference on Parallel Processing and Applied Mathematics (PPAM 2016), Revised Selected Papers. - Krakow, Poland
    Duration: 6 Sep 20159 Sep 2015
    Conference number: 11

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer Verlag
    Volume9574
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    Conference11th International Conference on Parallel Processing and Applied Mathematics (PPAM 2016), Revised Selected Papers.
    Abbreviated titlePPAM 2015
    CountryPoland
    CityKrakow
    Period6/09/159/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