On 12/13/2010 11:32 PM, MICHAEL MCGRADY wrote:
Patricia
http://www.cse.lehigh.edu/~spear/
http://www.cs.rochester.edu/u/vmarathe/
http://www.cs.rice.edu/~wns1/
http://www.cs.rochester.edu/u/scott/papers/2003_FTDCS_IW.pdf
A few other sources that are not so antiquated, which is not a negative. I
have asked Prof Scott to share his latest research.
Good. I'll read those. Also, I'm trying looking for research on the
trade-off between blocking and non-blocking.
At the high level, the way I see it is that blocking has the
disadvantage that preemption of a thread while it holds the lock may
delay the rest of the threads until the first thread gets back on a
processor and finishes the critical region. The advantage is that
processors that are waiting do not use the processor-memory interconnect
and do not get in the way.
I've seen logic analyzer traces of 64 processors all trying to increment
the same atomic counter by one. The counter was implemented using
compare-and-swap. It looked something like this:
64 processors all look at the counter, and see it is zero.
64 processors all try to compare-and-swap change it to one.
1 processor succeeds, and goes on to do something else. The other 63 all
see the counter has changed, and try again.
63 processors all look at the counter, and see it is one.
...
The reality was not quite that tidy - some processors might not get to
see the new value of the counter until it has been incremented a couple
of times - but the point is that contention costs either way.
In something like outrigger, part of the solution may be to work on
having the optimal number of threads, so that the processors are kept
busy as long as there is work to do, but the threads are not tripping
over each other.
Patricia
