Thomas Anderson,
Edward Lazowska, and Henry Levy.
The Performance Implications of Thread Management Alternatives for
Shared-Memory Multiprocessors. IEEE
Transactions on Computers, vol. 38, n. 12, December 1989, pages 1631 -
1644. Also appeared in Proc. 1989 ACM SIGMETRICS Conference, May
1989.
Abstract:
Threads ("lightweight"
processes) have become a common element of new languages and operating
systems. This paper examines the performance implications of several data
structure and algorithm alternatives for thread management in shared-memory
multiprocessors. Both experimental measurements and analytical model
projections are presented. For applications with fine-grained parallelism,
small differences in thread management are shown to have significant performance
impact, often posing a tradeoff between throughput and latency. Per-processor
data structures can be used to to improve throughput, and in some circumstances
to avoid locking, improving latency as well. The method used by processors to
queue for locks is also shown to affect performance significantly. Normal
methods of critical resource waiting can substantially degrade performance with
moderate numbers of waiting processors. We present an Ethernet-style backoff
algorithm that largely eliminates this effect.