From: Prasanna Kumar Jayapal (prasak_at_winse.microsoft.com)
Date: Wed Jan 28 2004 - 00:33:49 PST
This paper (by Anderson et al) talks about different alternatives for the thread management in the shared memory multiprocessor system and the performance implications of each of them, specifically looking at efficiency and throughput. Later on, it presents the Ethernet-style backoff algorithm for the locks that is much more efficient than the other traditional methods.
The five different thread management techniques discussed in this paper are:
1. Single Lock: Here the throughput is limited because the thread management path is serialized.
2. Multiple Locks: Here the throughput is improved, but needs more lock accesses which increases latency.
3. Local Free Lists: This is better than the first two approaches. This decreases latency, also has better throuput as only the accesses to the ready queue are serialized.
4. Idle Queue: This is an interesting approach as the work searches for processors instead of processors searching for work. This method is effective when there are idle processors, but latency will increase if the processors are busy.
5. Local Ready Queue: Here the Ready queue serialization is removed, but this results in imbalanced load on the processors as one might have an empty queue while the other might have a bunch of threads waiting.
In the next section, different alternatives for the spin-lock management are discussed.
1. Sping on Xchgb: This is a very primitive method where all the processors are repeatedly trying to acquire the lock and constantly contesting for the bus resources.
2. Sping on Read: This is a slightly improved method, where the processor tries to get the lock and on failure spins in the local cache reading the lock memory location, till it becomes available.
3. Ethernet Style Backoff: In this method, the processor estimates the possibility of acquiring the lock based on its previous experiences and tries only if the possibility is high. Although this could lead to starvation of some processors, from the results its seems to be the best approach.
The measurement results and the graphs were nice to see for both the thread management as well as the spin-lock alternatives. But it was filled with too many details and it was difficult to concentrate and understand. Overall, I felt this was a difficult paper to read through.
This archive was generated by hypermail 2.1.6 : Wed Jan 28 2004 - 00:33:46 PST