Incorrect output from join_node

[DSEAframework]

Summary

In a graph that merges two tokens, the output from the join_node is not in the expected order when executed with multiple threads.

Version

2022.3.0 extracted from oneapi-tbb-2022.3.0-lin.tgz

Environment

• Hardware
  Multi-core workstation
• OS name and version
  Ubuntu 24.04
• Compiler version
  gcc 13.3

Observed Behavior

The output of a join_node is not correct. The join_node has two inputs. The first input is a sequence of tuples (0,0), (1,1), (2,2), (3, 3)... The second input is a sequence of ints: 0, 1, 2, 3, 4, 5,.... The expected output is a sequence of tuples: ((0,0),0), ((1,1),1), ((2,2),2), ...
The observed output is sometime incorrect: ((0,0),0), ((2,2),1), ((1,1),2), ((3,3),3)
It seems the order of the first port is processed in incorrect order.
If the execution of the code is limited to one core via numactl, the output is correct.

Expected Behavior

The input of the join_node should be stored in a FIFO so that order is preserved. The output of the join_node should be independent of the number of cores and reproducible.

Steps To Reproduce

1. Extract oneTBB
2. source oneapi-tbb-2022.3.0/env/vars.sh
3. Build: g++ main.cpp -ltbb -o test_app
4. Run ./test_app the program prints !!! if the order of tokens is incorrect

main.cpp

[kboyarinov]

@DSEAframework,

Thank you for your question.
The root cause lies in incorrect assumptions about how a queueing join_node orders its output.
When items from two input streams (one from input_node and one from try_put) arrive at n_join_receive, each arriving item checks whether a corresponding item is available on the other port. Because both streams are synchronized (0 pairs with 0, 1 with 1, ets.), the tuples formed by the first node are initially correct: {0, 0}, {1, 1}, ....
However, once a tuple is constructed, the join_node spawns a service task responsible for broadcasting the tuple to its successors. This is where the problem occurs: these service tasks may be stolen by TBB worker threads and executed in a non-deterministic order. As a result, tuples can arrive at the n_receiver function node in an unspecified order. This also explains why the example behaves correctly in a serial environment.
Since n_receiver is a serial node, it processes items strictly in the order in which they are submitted-but that order has already been disrupted by the out-of-order execution of the service tasks coming from n_join_receive.
Consequently, the first port of n_join_worker receives a "mixed" input stream (e.g. {0, 0}, {2, 2}, {1, 1}, ...), while the second port receives the correctly ordered stream coming directly from try_put (0, 1, 2, ...)`. Because the node is queueing, tuples are joined in the order of arrival, leading to the mismatched output you observed.

Summary:
A queueing join_node guarantees FIFO order only for tuple formation, but it does not guarantee that successor nodes will receive the tuples in the same order.

To achieve the expected behavior in your graph, the n_join_worker node should be changed to a key_matching join_node.

[DSEAframework]

@kboyarinov, thank you for your fast reply!

I will check out the solution you suggested and report back.
After reading "Reestablish Order After Parallelism as Needed" in "Today's TBB" I realized that another solution might be to insert a sequencer_node.

Do I have to expect changing order of messages when using function_node and split_node?

[kboyarinov]

@DSEAframework

Yes, sequencer_node is another viable option to reestablish the order of the messages.

For the nodes you mention, current implementation of split_node do not spawn any service tasks. However, I don't recommend strictly count on this while developing your application, since this is an unspecified part of the behavior that can change in the future.

For function_node, it really depends on the policy and the concurrency limit. A queuing node with serial concurrency limit will preserve the order (and it is guaranteed), but if the concurrency limit is not serial, there can be several simultaneous tasks executing corresponding bodies on inputs, so the output order is non-deterministic (similar to the join_node case I described).

[DSEAframework]

I used a sequencer_node to restore the order of messages.

Thanks @kboyarinov for your help!