Post-mortem black-box correctness tests for basic parallel data structures
Phillip B. Gibbons, John L. Bruno, Steven Phillips · 1999
Operations on basic data structures such as queues, priority queues, stacks, and counters can dominate the execution time of a parallel program due to their frequency and their coordination and contention overheads.There are considerable performance payoffs in developing highly-optimized, asynchronous, distributed, cache-conscious, parallel implementations of such data structures.Such implementations may employ a variety of tricks to reduce latencies and avoid serial bottlenecks, as long as the semantics of the data structure are preserved.The complexity of the implementation and the difficulty in reasoning about asynchronous systems increases concerns regarding possible bugs in the implementation.In this paper, we consider black box procedures for testing whether a parallel data structure behaved correctly.We present the first systematic study of algorithms and hardness results for such testing procedures, focusing on queues, priority queues, stacks, and counters, under various important scenarios.Our results demonstrate the importance of selecting test data such that distinct values are inserted into the data structure (as appropriate).In such cases, we present an O(n) time algorithm for testing linearizable queues, an O(nlog n) time algorithm for testing linearizable priority queues, and an O(np') time algorithm for testing non-linearizable queues, where n is the number of data structure operations and p is the number of processors.In contrast, we show that testing such data structures for executions with arbitrary input values is NP-complete.Our results also help clarify the thresholds between scenarios that admit polynomial time solutions and those that are NPcomplete.Our algorithms are the first nontrivial algorithms for these problems.