Concurrent data structure: Difference between revisions

Revision as of 13:28, 23 November 2009

Revision as of 14:36, 24 November 2009

Line 67:

of theory on the design of concurrent data structures (see

bibliographical references).

==Design and Implementation==

Concurrent data structures are significantly more difficult to design

and to verify as correct than their sequential counterparts.

The primary source of this additional difficulty is concurrency, exacerbated by the fact that

threads must be thought of as being completely asynchronous:

they are subject to operating system preemption, page faults,

interrupts, and so on.

On today's machines, the layout of processors and

memory, the layout of data in memory, the communication load on the

various elements of the multiprocessor architecture all influence performance.

Furthermore, there is a tension between correctness and performance: algorithmic enhancements that seek to improve performance often make it more difficult to design and verify a correct

data structure implementation.

A key measure for performance is scalability, captured by the the [[speedup}]] of the implementation. Speedup is a measure of how

effectively the application is utilizing the machine it is running

on. On a machine with P processors, the '''speedup''' is the ratio of the structures execution time on a single processor to its execution time on T processors. Ideally, we want linear speedup: we would like to achieve a

speedup of P when using P processors. Data structures whose

speedup grows with P are called '''scalable'''.

==References==