Homegrown workqueue vs Intel TBB

Question

We are considering which parallel framework for C/C++ to use. We have some very special conditions and are not 100% sure, that e.g. TBB can add something "more".

• There are N running threads and one synchronized workqueue (using pthread mutex).
• Our jobs are prioritized (int).
• Jobs are put into the queue and idle thread takes a job with the highest priority.

This repeats until the queue is empty.

Well, and now, I'd like to know if some framework like TBB (Thread Building Blocks) can offer more for this special scenario from the algorithmic point of view?? (So, internals...)

Answer 1

In my opinion you could gain by replacing the heavy mutex with something more robust, like the spin_rw_mutex: http://threadingbuildingblocks.org/files/documentation/a00163.html. Since most likely insertion/removal operations are fast, you could benefit more from a non-blocking lock.

Answer 2

TBB 4 provides a concurrent_priority_queue (search 'priority' in the reference manual). Furthermore, using TBB is nice if you can design your program with tasks, not threads, in mind. Indeed, it provides a lot of stuff to describe dependancies between tasks. Also, TBB seems to be fairly portable if it's important for you.

Answer 3

I'd suggest taking a look at the TBB module summary pages and see if there is anything there that is useful to you.

For example, under the Containers section, there is not a concurrent_queue< T, A >, "A high-performance thread-safe non-blocking concurrent queue." It isn't a priority queue, so you'd have to build that yourself anyway.

On the other hand, under Synchronization, there are a few mutex variants that might make your life easier.

Bottom line: TBB isn't really all that magic, but it may be helpful.

Answer 4

TBB can provide you:

• Lock-free concurrent_queue. I don't remember anything about priority queue, but as James suggested in comments, you can build it yourself over cocurrent_queue.
• Memory allocators tuned for performance in multithreaded environment.
• Synchronization primitives like atomic variables
• just good ideas how multithreading stuff can be effectively implemented

Please note that even doing everything right and intensively using TBB it's possible you won't notice any performance gain in comparison with your own impelemntation. It highly depends on your system, especially if interthread communication and especially synchronization is a bottleneck. It is usually if your tasks are small and there're lots of them.

Answer 5

I have worked with a parallelization frameworks including OpenMP, Cilk. That gives a nice abstraction and make parallelizing comparatively easy. However, I doubt if these support priority queues directly or even if you can modify their task Queue.

you can do priority based queue using this customized TaskQueue.

If you want to use TBB, I have used it with OpenMP and it seems to blend in very nicely. Plus, you don't need to worry about concurrent containers. And it is very reliable compared to other implementations available by people.

Hope this helps.