Multiprocessor Hashtables

Greg linked to a great video discussing concurrent hashtables.

I talked about this problem earlier this month with regard to single threaded critical sections:

Now lets say you have two CPUs. Both are at 100% CPU.. CPU A goes to acquire a lock to compute the above critical section. CPU B then falls to 0% CPU and starts to run another thread which then calls the same critical section as CPU A. Now CPU B is deadlocked waiting for CPU A to complete but since A is at 100% it will take a while to return.

Ouch. Now CPU A has caused a denial of service on CPU B.

Apparently I’m not the only one realizing this problem. Azul sells machines with 750 processors. Wow.

Check out this Google tech talk video for more.



%d bloggers like this: