Concurrent data structure: Difference between revisions

Revision as of 14:41, 24 November 2009

Revision as of 14:41, 24 November 2009

Line 88:

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'''. The extent to which one can speed upscale the performance of a concurrent data structure is captured by a formula know as [[Amdahl's law]] and

more refined versions of it such as [[Gustafson's law]].