CPHASH: A cache-partitioned hash table
CPHash is a concurrent hash table for multicore processors. CPHash partitions its table across the caches of cores and uses message passing to transfer lookups/inserts to a partition. CPHash's message passing avoids the need for locks, pipelines batches of asynchronous messages, and packs multi...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/72613 https://orcid.org/0000-0003-0238-2703 https://orcid.org/0000-0001-7098-586X |
| _version_ | 1826201855011586048 |
|---|---|
| author | Metreveli, Zviad Zeldovich, Nickolai Kaashoek, M. Frans |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Metreveli, Zviad Zeldovich, Nickolai Kaashoek, M. Frans |
| author_sort | Metreveli, Zviad |
| collection | MIT |
| description | CPHash is a concurrent hash table for multicore processors. CPHash partitions its table across the caches of cores and uses message passing to transfer lookups/inserts to a partition. CPHash's message passing avoids the need for locks, pipelines batches of asynchronous messages, and packs multiple messages into a single cache line transfer. Experiments on a 80-core machine with 2 hardware threads per core show that CPHash has ~1.6x higher throughput than a hash table implemented using fine-grained locks. An analysis shows that CPHash wins because it experiences fewer cache misses and its cache misses are less expensive, because of less contention for the on-chip interconnect and DRAM. CPServer, a key/value cache server using CPHash, achieves ~5% higher throughput than a key/value cache server that uses a hash table with fine-grained locks, but both achieve better throughput and scalability than memcached. The throughput of CPHash and CPServer also scale near-linearly with the number of cores. |
| first_indexed | 2024-09-23T11:57:57Z |
| format | Article |
| id | mit-1721.1/72613 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:57:57Z |
| publishDate | 2012 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/726132022-09-27T23:07:24Z CPHASH: A cache-partitioned hash table Metreveli, Zviad Zeldovich, Nickolai Kaashoek, M. Frans Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Kaashoek, M. Frans Metreveli, Zviad Zeldovich, Nickolai Kaashoek, M. Frans CPHash is a concurrent hash table for multicore processors. CPHash partitions its table across the caches of cores and uses message passing to transfer lookups/inserts to a partition. CPHash's message passing avoids the need for locks, pipelines batches of asynchronous messages, and packs multiple messages into a single cache line transfer. Experiments on a 80-core machine with 2 hardware threads per core show that CPHash has ~1.6x higher throughput than a hash table implemented using fine-grained locks. An analysis shows that CPHash wins because it experiences fewer cache misses and its cache misses are less expensive, because of less contention for the on-chip interconnect and DRAM. CPServer, a key/value cache server using CPHash, achieves ~5% higher throughput than a key/value cache server that uses a hash table with fine-grained locks, but both achieve better throughput and scalability than memcached. The throughput of CPHash and CPServer also scale near-linearly with the number of cores. Quanta Computer (Firm) National Science Foundation (U.S.). (Award 915164) 2012-09-11T15:15:28Z 2012-09-11T15:15:28Z 2012-02 Article http://purl.org/eprint/type/ConferencePaper 978-1-4503-1160-1 http://hdl.handle.net/1721.1/72613 Zviad Metreveli, Nickolai Zeldovich, and M. Frans Kaashoek. 2012. CPHASH: a cache-partitioned hash table. In Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming (PPoPP '12). ACM, New York, NY, USA, 319-320. https://orcid.org/0000-0003-0238-2703 https://orcid.org/0000-0001-7098-586X en_US http://dx.doi.org/10.1145/2145816.2145874 Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming (PPoPP '12) Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Association for Computing Machinery (ACM) MIT web domain |
| spellingShingle | Metreveli, Zviad Zeldovich, Nickolai Kaashoek, M. Frans CPHASH: A cache-partitioned hash table |
| title | CPHASH: A cache-partitioned hash table |
| title_full | CPHASH: A cache-partitioned hash table |
| title_fullStr | CPHASH: A cache-partitioned hash table |
| title_full_unstemmed | CPHASH: A cache-partitioned hash table |
| title_short | CPHASH: A cache-partitioned hash table |
| title_sort | cphash a cache partitioned hash table |
| url | http://hdl.handle.net/1721.1/72613 https://orcid.org/0000-0003-0238-2703 https://orcid.org/0000-0001-7098-586X |
| work_keys_str_mv | AT metrevelizviad cphashacachepartitionedhashtable AT zeldovichnickolai cphashacachepartitionedhashtable AT kaashoekmfrans cphashacachepartitionedhashtable |