1,364 Posts served

5,674 Conversations started

Tasks for Doing and Threads for Waiting

By Arch Robison (Intel) (19 posts) on June 5, 2008 at 7:35 pm

TBB started out as a task-based framework for parallel programming.  TBB 2.1 adds threads.  This note explains the new threading interface, when to use it, and when to use tasks instead.

TBB tasks rely on non-preemptive cooperative scheduling based on work stealing, similar to Cilk. Once the TBB scheduler starts a task on a software thread, it does not switch to another task except at well-defined points (specifically, while waiting for its child tasks to complete). For compute-bound workloads, this style of scheduling has multiple benefits:

• Cooperative scheduling has low context switch overhead.
• Work stealing has good cache locality and certain space guarantees (see Cilk papers)
• Lastly, and most important, actual parallelism can be matched to available parallelism. In task-based programming, the programmer is expected to provide too much parallelism (“parallel slack” in Cilk parlance), and the scheduler will extract just enough parallelism to keep the machine humming, not swamped.

But programs are not only about calculation.  Programs also often have to wait on external events.  For sake of timely response, the wait needs to be done by a preemptively scheduled thread that can be scheduled when the event occurs. Of course interrupts or polling sometimes work. Interrupts are a bit of a combination of cooperative and preemptive scheduler.  The cooperative part is using an existing thread, the preemptive part is using it any time. That can be the best of both (preemptive and low overhead) or the worse of both (interrupt handlers are typically constrained on what they are allowed to do).  Polling usually scales poorly – composing two polling components requires composing their polling loops or using separate threads for the two polling loops.

Tasks can block, but doing so has two problems:

• The underlying thread sits idle until the task unblocks.
• Tasks (and their threads) waiting on it to also sit idle.  I.e., blocking propagates along a dependence chain.

In an ideal world, the scheduler would fire up other threads to run tasks in the meantime.  To do this efficiently requires user-level scheduling support that is not (at least yet) available in all operating systems targeted by TBB. But even with that support, there is another issue.  K blocked threads consume K stacks. Most of these stacks might be quite small, but current calling conventions require that programmers specify a fixed stack size (or use a default one) that is typically much larger than necessary for the common case. Changing the calling convention to be more like Cilk’s would solve this problem, but calling conventions take a long time to reform.

So in addition to tasks, TBB 2.1 has a class tbb_thread, which is a thin wrapper around a platform’s native thread. The interface is as close to the C++ 200x std::thread as we could make it given the limitations of C++ 1998. In particular:

• Lack of variadic templates restricts us to a fixed limit on template arguments.
• Lack or rvalue references implies slightly more overhead because copy-construction has to be used instead of move construction.
• Time is measured in the existing TBB timing interface tick_count::interval_t instead of the templated time interface in C++ 200x. We had to draw the line somewhere on where to stop pulling in C++ 200x.

We chose to call it tbb::tbb_thread and not tbb::thread to avoid name collisions when the ISO std::thread becomes available and a program liberally employs “using” directives.

Because tbb::tbb_thread is a thin wrapper around native threads, threads are heavier than tasks. They take longer to create and destroy.  They have associated stacks.  They are preemptively scheduled, so they guarantee concurrency, which is useful when you need it, but comes at the price of oversubscription if misused.  But they can block without impacting other threads or tasks. 

So TBB 2.1 has two ways to get things done: tasks and threads. When designing a program, try to separate calculating work from waiting work. Use tasks for calculation and threads for waiting. When a thread needs to do calculations, it can do it with tasks. Avoid having a task block on an external event. Software components doing waiting should call on components doing calculation, not the other way around.

Categories: Multicore, Threading Building Blocks

Comments (5) 

By Hot Tutorials on June 6th, 2008 at 6:40 am
Once the TBB scheduler starts a task on a software thread, it does not switch to another task except at well-defined points (specifically, while waiting for its child tasks to complete). For compute-bound workloads, this style of ... <http://softwareblogs.intel.com/2008/06/05/tasks-for-doing-and-threads-for-waiting/> Intel® Software Network Blogs... <http://softwareblogs.intel.com> Windows Mobile Application Developer / Confidential Software ... Design, implement scalable technical solutions and develop Windows Mobile applications to meet the business

By Aj Guillon on June 7th, 2008 at 1:15 pm
I think it is excellent that the TBB team has provided a direct thread interface, so that programmers can get the best of both worlds. I haven't looked extensively at TBB 2.1 yet, but it sounds like I should do that today. Will TBB's internal use of threads be ported to use tbb::tbb_thread? If not done already, and if possible, this would make it easier to understand the internal TBB code.

By Arch Robison (Intel) on June 10th, 2008 at 8:55 am
There's irony here. The draft ISO C++ 200x thread interface has no way to specify the stack size of a thread. By popular demand, TBB 2.1 adds that hook, and so we can't use tbb_thread for the TBB worker threads.

By milom on August 19th, 2008 at 7:57 am
Having low-level thread support is great. Yet, once you give a programmer a hammer, everything looks like a nail. Certainly tasks and blocking don't mix well. And threads are a way to handle such blocking. But instead of just supporting generic "blocking" perhaps it makes sense to focus on the root problem of why programs have blocking: I/O. Would it instead make sense to add a really minimal interface to TBB for doing asynchronous & buffered file and network I/O?

Another way to look at this: parallelism can either be thread-based or task-based. Concurrent I/O issues can either be thread-based or "event"-based. Instead of going toward explicit threaded, perhaps TBB can unify events and tasks. An example: maybe TBB could add a "parallel_scan" for processing chunks of a file in parallel (generating tasks on the fly to handle them). Or maybe I/O could be integrated into the pipeline parallelism pattern supported by TBB?

By Arch Robison (Intel) on August 19th, 2008 at 11:17 am
I agree. tbb_thread is a sledge hammer. It was added relatively late in the design cycle after an alternative for "blocking tasks" did not work out. We figured it was a simple solution that could crudely smash anything. An event -based model would be more elegant. We would have to figure out how to integrate it with task-based programming. In particular, a composition model needs to be figured out that uses standard calling conventions.

What do you think?

Name (required)

Email (required; will not be displayed on this page)

Your URL (optional)

Comments (required)