Methods and systems for testing parallel queues

Details Methods and systems for testing parallel queues Methods and systems for testing parallel queues

1999-09-23

2003-01-21

Baderman, Scott (Department: 2184)

Error detection/correction and fault detection/recovery

Data processing system error or fault handling

Reliability and availability

C707S793000

Reexamination Certificate

active

06510531

ABSTRACT:

BACKGROUND
1. Technical Field
The present invention relates generally to the field data structures and, in particular to methods and systems for testing parallel queues.
2. Background Description
Operations on basic data structures/objects such as shared queues, priority queues, stacks, and counters can often dominate the execution time of a parallel program. This dominance arises due to the large number of operations on the data structure by the processors, including multiple operations contending for the shared data structure at the same time. An example would be a shared queue used to hold tasks available for execution by the processors, where multiple processors grab tasks from the head of the queue and deposit new tasks to the tail of the queue. There are considerable performance gains that arise from the development of 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, including servicing multiple requests simultaneously or even out-of-order. Examples include implementations based on the following: counting networks, as described by J. Aspnes, M. Herlihy, and N. Shavit, in “Counting Networks”, Journal of the ACM, 41(5):1020-1048, 1994; elimination trees, as described by N. Shavit and D. Touitou, in “Elimination Trees and the Construction of Pools and Stacks”, Proc. 7
th
ACM Symp. on Parallel Algorithms and Architectures, pp. 54-63, July 1995; diffracting trees, as described by N. Shavit, E. Upfal, and A. Zemach, in “A Steady State Analysis of Diffracting Trees”, Proc. 8
th
ACM Symp. on Parallel Algorithms and Architectures, pp. 33-41, June 1996; or combining funnels with elimination, as described by N. Shavit and A. Zemach, in “Combining Funnels”, Proc. 17
th
ACM Symp. on Principles of Distributed Computing, pp. 61-70, June-July 1998. In fact, the only requirement of the implementation is that it preserves the (serial) semantics of the data structure, as observed by the processors interacting with the data structure. The complexity of the implementation and the difficulty in reasoning about asynchronous parallel systems increases concerns regarding possible bugs in the implementation.
Prior testing of parallel executions has involved both distinct values and arbitrary values. For distinct values, it is guaranteed that each value inserted into a data structure is distinct. In contrast, for arbitrary values, there is no such guarantee.
Prior testing of parallel executions has also involved linearizable data objects and non-linearizable data objects. In a linearizable data object, each operation takes place over a time interval, and consists of two events, the first being the invocation of the operation by the processor, and the second being the receipt of the response (either a value or an acknowledgment) by the processor. This is described further by M. P. Herlihy and J. M. Wing, in “Linearizability: A Correctness Condition for Concurrent Objects”, ACM Trans. on Programming Languages and Systems, 12(3):463-492, 1990.
For a trace to be valid for a linearizable data object, there must be a topological sort that (i) respects the order between any two events with non-overlapping intervals, and (ii) obeys the serial semantics of the data object. Thus the partial order is an interval order.
Linearizable data objects (also known as atomic objects) are well-studied (see e.g., N. Lynch, Distributed Algorithms, Morgan Kaufmann, San Francisco, Calif., chap. 13, 1996), as they have a number of desirable properties. In contrast, with non-linearizable data structures, there are no time intervals to respect. In this case, typically, the only partial order information is a total order within each processor. Thus the partial order is a union of chains (total orders), one per processor. The correctness condition does not impose any restrictions based on the real time that events occur. This correctness condition is denoted sequential consistency, and is a popular correctness condition for shared memory multiprocessors. Sequential consistency is described by L. Lamport, in “How to Make a Multiprocessor Computer that Correctly Executes Multiprocess Programs”, IEEE Trans. on Computers, C-28(9):690-691, 1979. For comparison, more general non-linearizable data structures in which the partial order can be a series-parallel order (modeling some form of fork-join parallelism) or even an arbitrary partial order, were considered by J. L. Bruno, P. B. Gibbons, and S. Phillips, in “Testing Concurrent Data Structures”, Technical report, AT&T Bell Laboratories, Murray Hill, N.J., December 1994.
A summary of related work in testing parallel executions will now be given. With respect to the problem of testing parallel executions of arbitrary linearizable shared data structures, a study of the same is described by J. M. Wing and C. Gong, in “Testing and Verifying Concurrent Objects”, J. Parallel and Distributed Computing, 17:164-182, 1993. In the preceding article, the problem of testing arbitrary linearizable data structures is shown to be NP-complete, and an exponential time algorithm is devised. Wing and Gong also developed a simulation environment for implementing their testing algorithms.
Certification trails for testing sequential executions of balanced binary trees, priority queues, union-find structures, and mergeable priority queues have been defined and studied by G. F. Sullivan and G. M. Masson, in “Using Certification Trails to Achieve Software Fault Tolerance”, Proc. 20
th
IEEE Fault-Tolerant Computing Symp., pp. 423-31, 1990; G. F. Sullivan and G. M. Masson, in “Certification Trails for Data Structures”, Proc. 21
st
IEEE Fault-Tolerant Computing Symp., pp. 240-47, 1991; and J. Bright and G. Sullivan, in “Checking Mergeable Priority Queues”, Proc. 24
th
IEEE Fault-Tolerant Computing Symp., pp. 144-53, June 1994. In this approach, the data structure code is modified to output additional information to assist in testing.
Other work on sequential testing and related issues includes: K.-H. Huang and J. Abraham, “Algorithm-based Fault Tolerance for Matrix Operations”, IEEE Trans. on Computers, C-33(6):518-528, 1984; B. Dixon, M. Rauch, and R. E. Tarjan, “Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time”, SIAM Journal on Computing, 21(6):1184-1192, 1992; and P. Ramanan, “Testing the Optimality of Alphabetic Trees”, Theoretical Computer Science, 93:279-302, 1992.
Note that unlike testing sequential executions, testing parallel executions focuses on topological sorting since it does not assume a centralized serialization point or a central module implementing the data structure. This serialization point or central module is undesirable since it imposes a serial bottleneck in the parallel program. The sequential trace work, in contrast, focuses on testing procedures that are more efficient in time and/or space than the implementation being tested. These are also the concerns of the works on sequential program checking, such as those described by, for example: M. Blum and S. Kannan, “Designing Programs that Check Their Work”, Proc. 21
st
ACM Symp on Theory of Computing, pp. 86-97, May 1989; M. Blum, M. Luby, and R. Rubinfeld, in “Self-testing/correcting with Applications to Numerical Problems”, Proc. 22
nd
ACM Symp. on Theory of Computing, pp. 73-83, May 1990; and M. Blum, W. Evans, P. Gemmell, S. Kannan, and M. Naor, in “Checking the Correctness of Memories”, Algorithmica, 12(2/3):225-244, 1994.
In a recent independent work, algorithms for checking sequential priority queues were presented by U. Finkler and K. Mehlhorn, in “Checking Priority Queues”, Proc. 10
th
ACM-SIAM Symp. on Discrete Algorithms, pp. S901-02, January 1999. Their algorithms observe the sequential stream of operations at the data structure, and check to see if this stream is legal.
Testing the serializability of database transactions has been proven to be NP-complete by C. Papadimitriou, in “The Theory of Database Concurrency Contro

Affiliated with

Also associated with

Rating

Methods and systems for testing parallel queues does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Methods and systems for testing parallel queues, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and systems for testing parallel queues will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3017632