From: Reed, R. W <rob...@in...> - 2008-03-21 21:35:07
|
It all has to do with cache lines. And is probably more appropriate a topic for tbb-users. I've added it to the list. If we continue this discussion, we should probably do it over there. The hit from atomic operations is not as severe as when using a mutex, but not negligible. A cache line on current Intel(r) Architecture is 64 bytes. If Processing Element A does an atomic operation on 4 bytes of Cache Line 1, it doesn't need to write the 4 bytes all the way to memory. By the MESI protocol for cache coherence, all it has to have is Exclusive access to the cache line. The "atomic" part is the guarantee that PE-A either already has Line 1 in Modified state or can convert it from Exclusive or Shared state to Modified without any other intervening operations. In MESI, the process for converting from Shared to Modified involves a broadcast called Read For Ownership, which essentially forces all other PEs, if they have that cache line in Shared state, to mark it Invalid. All this involves various snoop traffic as the PEs exchange information about their cache lines. If Processing Element B wants to twiddle any of the bytes in Cache Line 1, it must contend with PE-A for ownership of the cache line. In MESI, PE-B's RFO would be aborted so that PE-A could grab the bus and write Line 1 back to memory. PE-B would try again, doing another RFO as the first step in its read-modify-write cycle. And there're other complications like write-through versus write-back caches. So contention is still an issue. _______________________________________________________________________ Robert Reed Rob...@in... Intel SSG/ Developer Products Division/ Performance, Analysis and Threading Lab/ Technical Consulting Dept. JF1-15, 2111 NE 25th Ave phone 503-264-9624 Hillsboro, OR 97124 mobile 503-830-1530 fax 503-264-9227 The only thing that saves us from the bureaucracy is inefficiency. An efficient bureaucracy is the greatest threat to liberty. --Eugene McCarthy ________________________________________________________________________ ________________________________ From: tbb...@li... [mailto:tbb...@li...] On Behalf Of Adrien Guillon Sent: Friday, March 21, 2008 12:42 PM To: for people interested in developing TBB itself Subject: Re: [Tbb-develop] TBB Priority Queue The part that puzzled me was how multiple atomic operations could cause performance bottlenecks. As for priority queues by their nature having internal dependencies which prohibit efficient concurrent behavior, it's quite possible. I am currently devoting some effort to the study of efficient parallel containers. I haven't searched for texts on the subject yet, rather I am waiting for my multi-core programming books from Intel Press to understand more about what the containers should look like and how they should behave for good performance. Once I understand what I'm looking for, I will attempt to design some better behaved containers, and perhaps understand the TBB containers better. AJ On Fri, Mar 21, 2008 at 3:22 PM, Reed, Robert W <rob...@in...<mailto:rob...@in...>> wrote: I'm not sure I agree, Adrien. Publishing bad code doesn't necessarily provide any lessons to the reader. If there was a demonstration of how to avoid the shoals of bad code provided in such a release, there'd be a positive lesson there. If the answer is that priority queues by their very nature have too many internal dependencies to permit concurrent thread access, then you might have to accept that priority queue accesses are serial events. You put a global lock around your STL priority queue and try to minimize the use of it. The only reason I could see for wanting such failed implementations is the expectation that you could do better. Personally I don't see the value there. _______________________________________________________________________ Robert Reed Rob...@in...<mailto:Rob...@in...> Intel SSG/ Developer Products Division/ Performance, Analysis and Threading Lab/ Technical Consulting Dept. JF1-15, 2111 NE 25th Ave phone 503-264-9624 Hillsboro, OR 97124 mobile 503-830-1530 fax 503-264-9227 Imagine the Creator as a low comedian, and at once the world becomes explicable. --H.L. Mencken ________________________________________________________________________ ________________________________ From: tbb...@li...<mailto:tbb...@li...> [mailto:tbb...@li...<mailto:tbb...@li...>] On Behalf Of Adrien Guillon Sent: Friday, March 21, 2008 8:36 AM To: for people interested in developing TBB itself Subject: [Tbb-develop] TBB Priority Queue It was mentioned on the forums that a TBB priority queue was implemented before, but that the performance was horrible due to many atomic operations. Could we have this code made public so that we can learn from your mistakes without making them ourselves? AJ ------------------------------------------------------------------------- This SF.net email is sponsored by: Microsoft Defy all challenges. Microsoft(R) Visual Studio 2008. http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ _______________________________________________ Tbb-develop mailing list Tbb...@li...<mailto:Tbb...@li...> https://lists.sourceforge.net/lists/listinfo/tbb-develop |