NDLI: Phase-concurrent hash tables for determinism

Please wait, while we are loading the content...

A distributed perspective on graph connectivity and cuts

On dynamic bin packing for resource allocation in the cloud

On computing maximal independent sets of hypergraphs in parallel

Brief announcement: few buffers, many hot spots, and no tree saturation (with high probability)

Provably good scheduling for parallel programs that use data structures through implicit batching

Scheduling selfish jobs on multidimensional parallel machines

A simple and practical linear-work parallel algorithm for connectivity

The PCL theorem: transactions cannot be parallel, consistent and live

Brief announcement: fairness-efficiency tradeoffs in tiered storage allocation

Automatic complexity analysis of explicitly parallel programs

A universal approach to data center network design

Simple dynamics for plurality consensus

Finding approximate partitions and splitters in external memory

Parallel peeling algorithms

On the online fault-tolerant server consolidation problem

Hierarchical graph partitioning

Brief announcement: queue delegation locking

Phase-concurrent hash tables for determinism

LP rounding and combinatorial algorithms for minimizing active and busy time

Executing dynamic data-graph computations deterministically using chromatic scheduling

Adaptive integration of hardware and software lock elision techniques

Brief announcement: deadline-aware scheduling of big-data processing jobs

Parallel streaming frequency-based aggregates

(Near) optimal resource-competitive broadcast with jamming

On characterizing the data movement complexity of computational DAGs for parallel execution

Balanced allocations and double hashing

Competitively scheduling tasks with intermediate parallelizability

Simple parallel and distributed algorithms for spectral graph sparsification

Brief announcement: fast dual ring queues

Scheduling shared continuous resources on many-cores

Ordering heuristics for parallel graph coloring

Transaction-friendly condition variables

Brief announcement: parallelization of asynchronous variational integrators forshared memory architectures

Ephemeral networks with random availability of links: diameter and connectivity

Tradeoffs between synchronization, communication, and computation in parallel linear algebra computations

Experimental analysis of space-bounded schedulers

Brief announcement: concurrent data structures for efficient streaming aggregation

A note on multiprocessor speed scaling with precedence constraints

Brief annoucement: a distributed minimum cut approximation scheme

Locality-based network creation games

Brief announcement: cache-oblivious scheduling of streaming pipelines

Brief announcement: amoebot -- a new model for programmable matter

Brief announcement: persistent unfairness arising from cache residency imbalance

Brief announcement: faster 3-periodic merging networks

Phase-concurrent hash tables for determinism

Content Provider	ACM Digital Library
Author	Shun, Julian Blelloch, Guy E.
Abstract	We present a deterministic phase-concurrent hash table in which operations of the same type are allowed to proceed concurrently, but operations of different types are not. Phase-concurrency guarantees that all concurrent operations commute, giving a deterministic hash table state, guaranteeing that the state of the table at any quiescent point is independent of the ordering of operations. Furthermore, by restricting our hash table to be phase-concurrent, we show that we can support operations more efficiently than previous concurrent hash tables. Our hash table is based on linear probing, and relies on history-independence for determinism. We experimentally compare our hash table on a modern 40-core machine to the best existing concurrent hash tables that we are aware of (hopscotch hashing and chained hashing) and show that we are 1.3--4.1 times faster on random integer keys when operations are restricted to be phase-concurrent. We also show that the cost of insertions and deletions for our deterministic hash table is only slightly more expensive than for a non-deterministic version that we implemented. Compared to standard sequential linear probing, we get up to 52 times speedup on 40 cores with dual hyper-threading. Furthermore, on 40 cores insertions are only about 1.3 times slower than random writes (scatter). We describe several applications which have deterministic solutions using our phase-concurrent hash table, and present experiments showing that using our phase-concurrent deterministic hash table is only slightly slower than using our non-deterministic one and faster than using previous concurrent hash tables, so the cost of determinism is small.
Starting Page	96
Ending Page	107
Page Count	12
File Format	PDF
ISBN	9781450328210
DOI	10.1145/2612669.2612687
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-06-23
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Determinism Applications Hash table
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in