• 2021.4
  • 09/27/2021
  • Public Content
Contents

Flow Graph Basics: Reservation

Intel® oneAPI Threading Building Blocks (oneTBB) flow graph
join_node
has four possible policies:
queueing
,
reserving
,
key_matching
and
tag_matching
.
join_nodes
need messages at every input before they can create an output message. The reserving
join_node
does not have internal buffering, and it does not pull messages from its inputs until it has a message at each input. To create an output message it temporarily reserves a message at each input port, and only if all input ports succeed reserving messages will an output message be created. If any input port fails to reserve a message, no message will be pulled by the
join_node
.
To support the reserving
join_node
some nodes support
reservation
of their outputs. The way reservation works is:
  • When a node connected to a reserving
    join_node
    in push state tries to push a message, the
    join_node
    always rejects the push and the edge connecting the nodes is switched to pull mode.
  • The reserving input port calls
    try_reserve
    on each edge in pull state. This may fail; if so, the reserving input port switches that edge to push state, and tries to reserve the next node connected by an edge in pull state. While the input port’s predecessor is in reserved state, no other node can retrieve the reserved value.
  • If each input port successfully reserves an edge in pull state, the reserving
    join_node
    will create a message using the reserved messages and try to push the resulting message to any nodes connected to it.
  • If the message is successfully pushed to a successor, the predecessors that were reserved are signaled that the messages were used (by calling
    try_consume()
    .) Those messages will be discarded by the predecessor nodes, because they have been successfully pushed.
  • If the message was not successfully pushed to any successor, the predecessors that were reserved are signaled that the messages were not used (by calling
    try_release()
    .) At this point, the messages may be pushed to or pulled by other nodes.
Because the reserving
join_node
will only attempt to push when each input port has at least one edge in a pull state, and will only attempt to create and push a message if all input ports succeed reserving messages, at least one of the predecessors to each of the reserving
join_node
input ports must be reservable.
The following example demonstrates a reserving
join_node
’s behavior.
buffer_nodes
buffer their output, so they accept a switch of their output edge from push to pull mode.
broadcast_nodes
do not buffer messages and do not support
try_get()
or
try_reserve()
.
void run_example2() { // example for Flow_Graph_Reservation.xml graph g; broadcast_node<int> bn(g); buffer_node<int> buf1(g); buffer_node<int> buf2(g); typedef join_node<tuple<int,int> reserving> join_type; join_type jn(g); buffer_node<join_type::output_type> buf_out(g); join_type::output_type tuple_out; int icnt; // join_node predecessors are both reservable buffer_nodes make_edge(buf1,input_port<0>jn)); make_edge(bn,input_port<0>jn)); // attach a broadcast_node make_edge(buf2,input_port<1>jn)); make_edge(jn, buf_out); bn.try_put(2); buf1.try_put(3); buf2.try_put(4); buf2.try_put(7); g.wait_for_all(); while (buf_out.try_get(tuple_out)) { printf("join_node output == (%d,%d)\n",get<0>tuple_out), get<1>tuple_out) ); } if(buf1.try_get(icnt)) printf("buf1 had %d\n", icnt); else printf("buf1 was empty\n"); if(buf2.try_get(icnt)) printf("buf2 had %d\n", icnt); else printf("buf2 was empty\n"); }
In the example above, port 0 of the reserving
join_node
jn
has two predecessors: a
buffer_node
buf1
and a
broadcast_node
bn
. Port 1 of the
join_node
has one predecessor,
buffer_node
buf2
.
image0
We will discuss one possible execution sequence (the scheduling of tasks may differ slightly, but the end result will be the same.)
bn.try_put(2);
bn
attempts to forward 2 to
jn
.
jn
does not accept the value and the arc from
bn
to
jn
reverses. Because neither bn nor jn buffer messages, the message is dropped. Because not all the inputs to
jn
have available predecessors,
jn
does nothing further.
Any node which does not support reservation will not work correctly when attached to a reserving
join_node
. This program demonstrates why this occurs; connecting non-reserving nodes to nodes requiring support for reservation is
not
recommended practice.
image1
buf1.try_put(3);
buf1
attempts to forward 3 to
jn
.
jn
does not accept the value and the arc from
buf1
to
jn
reverses. Because not all the inputs to
jn
have available predecessors,
jn
does nothing further.
image2
buf2.try_put(4);
buf2
attempts to forward 4 to
jn
.
jn
does not accept the value and the arc from
buf2
to
jn
reverses. Now both inputs of
jn
have predecessors, a task to build and forward a message from
jn
will be spawned. We assume that task is not yet executing.
image3
buf2.try_put(7);
buf2
has no successor (because the arc to
jn
is reversed,) so it stores the value 7.
image4
Now the task spawned to run
jn
runs.
  • jn
    tries to reserve
    bn
    , which fails. The arc to
    bn
    switches back to the forward direction.
  • jn
    tries to reserve
    buf1
    , which succeeds (reserved nodes are colored grey.)
    jn
    receives the value 3 from
    buf1
    , but it remains in
    buf1
    (in case the attempt to forward a message from
    jn
    fails.)
  • jn
    tries to reserve
    buf2
    , which succeeds.
    jn
    receives the value 4 from
    buf2
    , but it remains in
    buf2
    .
  • jn
    constructs the output message
    tuple<3,4>
    .
image5
Now
jn
pushes its message to
buf_out
, which accepts it. Because the push succeeded,
jn
signals
buf1
and
buf2
that the reserved values were used, and the buffers discard those values. Now
jn
attempts to reserve again.
  • No attempt to pull from
    bn
    is made, because the edge from
    bn
    to
    jn
    is in push state.
  • jn
    tries to reserve
    buf1
    , which fails. The arc to
    buf1
    switches back to the forward direction.
  • jn
    does not try any further actions.
image6
No further activity occurs in the graph, and the
wait_for_all()
will complete. The output of this code is
join_node output == (3,4) buf1 was empty buf2 had 7

Product and Performance Information

1

Performance varies by use, configuration and other factors. Learn more at www.Intel.com/PerformanceIndex.