I ran across this interesting paper today: http://www.cs.tau.ac.il/research/moran.tzafrir/papers/spaa2010_flat_combinin... It discusses "Flat Combining" (FC) as a technique for building scalable concurrent data structures. It has two notable characteristics: 1) Concurrent data structures are built from sequential data structures in a way that is very similar to protecting it with a single mutex. This makes them much easier to implement than a plain lock-free data structure. 2) Such data structures are more scalable (in throughput versus number of threads/processes) than using a normal global lock approach. Reading it made me think of three possibilities that we should investigate at some point: 1) I don't think that we've measured the scalability of the nemesis shared memory queues as the number of communicating processes increases. It's possible that the current swap/CAS-based design may bottleneck on access to the tail of the queue. I don't have a good sense for what the maximal enqueue/dequeue rate would be for a single process sending messages as fast as possible. 2) If item (1) turns out to be a problem, we could investigate an FC-based solution. I'm fairly certain this is doable and would be scalable in throughput vs. processes, but I don't know what the latency impact would be for ping-pong or other microbenchmarks. 3) FC might provide an alternative way to scalably implement multithreaded MPI receive queues, possibly without penalizing the MPI_ANY_SOURCE case as severely as our current designs do. The general concept already shares some similarity with the "channelized recvq" design, but instead it "channelizes" on a per-thread basis. I need to think more about how this all would work, and how it would interact with a channelized DCMF/PAMI, there could be real problems. I also haven't been able to decide whether recvq operations are actually combinable or not, a necessary condition for using FC, IIUC. -Dave
I think this is something certainly worth looking into. Rajeev On Apr 14, 2011, at 2:53 PM, Dave Goodell wrote:
I ran across this interesting paper today:
http://www.cs.tau.ac.il/research/moran.tzafrir/papers/spaa2010_flat_combinin...
It discusses "Flat Combining" (FC) as a technique for building scalable concurrent data structures. It has two notable characteristics:
1) Concurrent data structures are built from sequential data structures in a way that is very similar to protecting it with a single mutex. This makes them much easier to implement than a plain lock-free data structure.
2) Such data structures are more scalable (in throughput versus number of threads/processes) than using a normal global lock approach.
Reading it made me think of three possibilities that we should investigate at some point:
1) I don't think that we've measured the scalability of the nemesis shared memory queues as the number of communicating processes increases. It's possible that the current swap/CAS-based design may bottleneck on access to the tail of the queue. I don't have a good sense for what the maximal enqueue/dequeue rate would be for a single process sending messages as fast as possible.
2) If item (1) turns out to be a problem, we could investigate an FC-based solution. I'm fairly certain this is doable and would be scalable in throughput vs. processes, but I don't know what the latency impact would be for ping-pong or other microbenchmarks.
3) FC might provide an alternative way to scalably implement multithreaded MPI receive queues, possibly without penalizing the MPI_ANY_SOURCE case as severely as our current designs do. The general concept already shares some similarity with the "channelized recvq" design, but instead it "channelizes" on a per-thread basis. I need to think more about how this all would work, and how it would interact with a channelized DCMF/PAMI, there could be real problems. I also haven't been able to decide whether recvq operations are actually combinable or not, a necessary condition for using FC, IIUC.
-Dave
participants (2)
-
Dave Goodell -
Rajeev Thakur