Visible to Intel only — GUID: GUID-327ED36E-EF08-4EC1-A95D-B28922F67005
Package Contents
Parallelizing Simple Loops
Parallelizing Complex Loops
Parallelizing Data Flow and Dependence Graphs
Work Isolation
Exceptions and Cancellation
Containers
Mutual Exclusion
Timing
Memory Allocation
The Task Scheduler
Design Patterns
Migrating from Threading Building Blocks (TBB)
Constrained APIs
Invoke a Callable Object
Appendix A Costs of Time Slicing
Appendix B Mixing With Other Threading Packages
References
parallel_for_each Body semantics and requirements
parallel_sort ranges interface extension
TBB_malloc_replacement_log Function
Type-specified message keys for join_node
Scalable Memory Pools
Helper Functions for Expressing Graphs
concurrent_lru_cache
task_group extensions
The customizing mutex type for concurrent_hash_map
Visible to Intel only — GUID: GUID-327ED36E-EF08-4EC1-A95D-B28922F67005
Non-Preemptive Priorities
Problem
Choose the next work item to do, based on priorities.
Context
The scheduler in oneAPI Threading Building Blocks (oneTBB) chooses tasks using rules based on scalability concerns. The rules are based on the order in which tasks were spawned or enqueued, and are oblivious to the contents of tasks. However, sometimes it is best to choose work based on some kind of priority relationship.
Forces
Given multiple work items, there is a rule for which item should be done next that is not the default oneTBB rule.
Preemptive priorities are not necessary. If a higher priority item appears, it is not necessary to immediately stop lower priority items in flight. If preemptive priorities are necessary, then non-preemptive tasking is inappropriate. Use threads instead.
Solution
Put the work in a shared work pile. Decouple tasks from specific work, so that task execution chooses the actual piece of work to be selected from the pile.
Example
The following example implements three priority levels. The user interface for it and top-level implementation follow:
enum Priority {
P_High,
P_Medium,
P_Low
};
template<typename Func>
void EnqueueWork( Priority p, Func f ) {
WorkItem* item = new ConcreteWorkItem<Func>( p, f );
ReadyPile.add(item);
}
The caller provides a priority p and a functor f to routine EnqueueWork. The functor may be the result of a lambda expression. EnqueueWork packages f as a WorkItem and adds it to global object ReadyPile.
Class WorkItem provides a uniform interface for running functors of unknown type:
// Abstract base class for a prioritized piece of work.
class WorkItem {
public:
WorkItem( Priority p ) : priority(p) {}
// Derived class defines the actual work.
virtual void run() = 0;
const Priority priority;
};
template<typename Func>
class ConcreteWorkItem: public WorkItem {
Func f;
/*override*/ void run() {
f();
delete this;
}
public:
ConcreteWorkItem( Priority p, const Func& f_ ) :
WorkItem(p), f(f_)
{}
};
Class ReadyPile contains the core pattern. It maintains a collection of work and fires off tasks through the oneapi::tbb::task_group::run interface and then choose a work from the collection:
class ReadyPileType {
// One queue for each priority level
oneapi::tbb::concurrent_queue<WorkItem*> level[P_Low+1];
oneapi::tbb::task_group tg;
public:
void add( WorkItem* item ) {
level[item->priority].push(item);
tg.run(RunWorkItem());
}
void runNextWorkItem() {
// Scan queues in priority order for an item.
WorkItem* item=NULL;
for( int i=P_High; i<=P_Low; ++i )
if( level[i].try_pop(item) )
break;
assert(item);
item->run();
}
};
ReadyPileType ReadyPile;
The task added by add(item) does not necessarily execute that item. The task itself executes runNextWorkItem(), which may find a higher priority item. There is one task for each item, but the mapping resolves when the task actually executes, not when it is created.
Here are the details of class RunWorkItem:
class RunWorkItem {
void operator()() {
ReadyPile.runNextWorkItem();
};
};
RunWorkItem objects are fungible. They enable the oneTBB scheduler to choose when to do a work item, not which work item to do.
Other priority schemes can be implemented by changing the internals for ReadyPileType. A priority queue could be used to implement very fine grained priorities.
The scalability of the pattern is limited by the scalability of ReadyPileType. Ideally scalable concurrent containers should be used for it.