A look at the “computation graph” section of the Intel Threading Building Blocks Library from the point of view of a BPMS system developer
We develop a system for managing business processes and administrative regulations. We were interested in the tbb :: flow section of the C ++ Template of the Intel Threading Building Blocks (TBB), so the pictures that we saw in the library description seemed very similar to the pictures of the business process graph of process automation systems.
A more detailed study of TBB turned out that the object with which the tbb :: flow section works is very different from the classic business processes, but it turned out to be so interesting that we decided to write how it is perceived by the BPMS developers.
The TBB library was developed by Intel for parallel programming. The library contains algorithms and data structures that allow the programmer to avoid difficulties arising from the use of traditional implementations of operating system threads. That is, with the help of this library, developers will be able to achieve additional performance gains without touching on the complex issues of low-level assignment of threads to specific processor cores.
')
All operations in the library are treated as “tasks” that are dynamically distributed between the processor cores. A program written using TBB creates, synchronizes, and destroys task dependency graphs in accordance with the algorithm. Then tasks are executed according to dependencies. This approach allows you to program parallel algorithms at a high level, abstracting from the details of the architecture of a particular machine.
A library is a collection of class templates and functions for parallel programming. The library implemented:
The library must specify the task. Further, the library itself will display tasks on threads in an optimal way.
This construction is devoted to the library section - tbb :: flow. The dependencies of many applications running in the operating system are well described as messages moving between nodes of the message flow graph. These messages may contain data, or simply be signals that the “predecessor” has ended. These messages are somewhat similar to the management points of BPM systems.
Nodes of the graph are associated with applications that execute tasks. (In BPMS, nodes in a graph also perform tasks, but nodes are not associated with task performers, but only with tasks themselves).
There are three main components in the section:
The Graph object is the owner of all tasks generated on behalf of the corresponding message flow graph.
Objects Nodes trigger user-defined functional objects or control messages as inbound / outbound relative to other nodes.
Edges are connections between nodes (similar to transitions in BPMS).
Edges dynamically switch between pull and push protocols. The graph can be represented as a construction G = (V, S, L), in which V is the set of nodes, S is the set of edges using the Push-protocol, L is the set of edges using the Pull-protocol.
For each edge (Vi, Vj), Vi is a predecessor (predecessor, or sender) and Vj is a follower (successor, or receiver). in the case of the push of the protocol (S), messages sent along the edge are initiated by the predecessor, which attempts to transmit them to the recipient. In the case of protocol pull (L), messages are initiated by the follower (receiver), who tries to get them from the predecessor (sender).
If the attempt to send a message along the edge failed, then the edge is switched to another protocol mode. This is a very interesting design, there is nothing like this in BPMS, a node cannot “reflect” a control point there.
Using the protocol switching mechanism is a key difference between the TBB library and other similar libraries, which, in the event of a failure, simply periodically attempt to transmit the message. This mechanism can significantly improve the efficiency of interaction between applications.
Body Objects are used in graph nodes. These objects are provided by users. These objects can be created by functional objects, or by special expressions.
Body objects passed between nodes are copied. Therefore, changing the Body object in the receiver node does not change the corresponding Body object in the sender node. It is also very different from BPMS, because there is no data in the management points, the management points are only markers pointing to the active nodes of the business process, and the data is in variables related to the entire instance of the business process.
Node buffer_node. The node has an unlimited buffer for messages of type "T". The node “passes” messages to its successors (to one of the successors) in random order. If successor reflects the message, then the node tries to send this message to another successor.
The queue_node node. The node has an unlimited buffer for messages of type "T". The node “passes” messages in the FIFO order (to one of the successors). In this case, successors are sorted in the order in which they are registered in the node. If successor reflects the message, the node sends this message to the next one in the list to successor.
The priority_queue_node node. The node “flips” the messages in order of priority. (That is, of all the available messages, the node first tries to push the message with the highest priority). Attempts to send a message continue until one of the successors accepts the message, or all the successors are enumerated. If any of the successors received the message, then it is removed from the buffer.
The sequencer_node node. The node has an unlimited buffer for messages of type "T". The node “passes through” the messages in sequential order ... If the successor reflects the message, then the node sends this message to the next successor.
Join_node node The node creates a tuple (vector) from the messages that have come along all the incoming edges, multiplies and “flips” this tuple with all its successors. The node supports three message buffering policies: reservation, queue, and tag_matching.
Policy queuing: All incoming messages on each edge are arranged according to the principle of first-in first-out. If there is at least one message on each edge, then all first-out messages are removed from the edges and the tuple is sent to all successors.
Reserving policy: Only 1, or 0 messages are allowed on each edge. Arriving messages on the edge, on which there is already a message, are reflected. Further attempts are being made to pull the predecessors, from which there are no messages on the edges. If for each edge it was possible to receive a message, then all messages are removed from the edges and the tuple is sent to the successor
Policy tag_matching: For each incoming message, on each edge, a special user-prepared functional object is executed, which associates with the message tag. Then the messages on each edge are grouped in a hash table according to their tags. If there is at least one message with a given tag on each edge, then all such messages are removed from the edges and the tuple is sent to all successors.
Or_node node The node propagates and “flips” the message with all its successors, regardless of which incoming edge this message came from.
Split_node node A node that has one incoming edge and more than one outgoing. On an incoming transition, a node receives message tuples. The node is a variant of multifunction_output_node, in which the body sends each element of the incoming tuple along the outgoing edge in accordance with the index of the element in the tuple.
Source_node node This node may be missing a predecessor. A node is never executed in parallel. The node performs its body function and sends the result simultaneously to all its successors.
The continue_node node. After the node receives a message from predecessor, it executes its body objects. Only after that he redirects continue_msg to his successor.
Function_node node The node has a restriction on concurrent actions. If the node cannot process the message immediately, then it puts the message in the FIFO buffer. You can make this setting that if the FIFO buffer is full, the node refuses to process the incoming message.
Multioutput_function_node node. A node that has only one incoming edge and more than one outgoing. The node has a limit on the number of simultaneously processed incoming messages. When the limit is exceeded, the node executes for incoming body messages that have been set by the user. These bodies create messages that are sent to successors.
Broadcast_node node The node propagates and “flips” the incoming message with all its successors
Node write_once_node. This node has a buffer with only one element that cannot be dynamically replaced. Only after an explicit clear command, the buffer can accept a new message.
The overwrite_node node. This node has a buffer with only one element that can be dynamically replaced (overwrite).
The limiter_node node. A node that counts and limits the number of messages that pass through it. The node propagates and “flushes” the incoming message to all its successors, but stops accepting new messages if the message limit is exceeded
We see that the functionality of these nodes is significantly richer than the functionality of the BPMS nodes. Similarly to the nodes of the tbb :: flow section, there is a possibility in BPMS to multiply control points for all outgoing transitions from a node, there is also a possibility to merge control points that came to a node through all incoming transitions, it is possible to “push through” control points that came from any incoming transition on a single outgoing transition. However, in BPMS there is no such thing as a buffer, there is no “rolling out” the message in a random order, BPMS control points have no priorities, no concept of control points tuple, no such concepts as pushing and pulling the control point.
Thus, acquaintance with the TBB library tbb :: flow section shows the BPMS developer with which actually simple object he works and how much this object can be complicated by expanding the behavior of the graph elements. It also becomes clear how much you can increase the functionality of BPMS by adding additional elements to its scheme, similar to those in the tbb :: flow TBB section.
Link to TBB library description
A more detailed study of TBB turned out that the object with which the tbb :: flow section works is very different from the classic business processes, but it turned out to be so interesting that we decided to write how it is perceived by the BPMS developers.
The TBB library was developed by Intel for parallel programming. The library contains algorithms and data structures that allow the programmer to avoid difficulties arising from the use of traditional implementations of operating system threads. That is, with the help of this library, developers will be able to achieve additional performance gains without touching on the complex issues of low-level assignment of threads to specific processor cores.
')
All operations in the library are treated as “tasks” that are dynamically distributed between the processor cores. A program written using TBB creates, synchronizes, and destroys task dependency graphs in accordance with the algorithm. Then tasks are executed according to dependencies. This approach allows you to program parallel algorithms at a high level, abstracting from the details of the architecture of a particular machine.
Library structure
A library is a collection of class templates and functions for parallel programming. The library implemented:
- parallel algorithms: for, reduce, do, scan, while, pipeline, sort
- thread safe containers: vector, queue, hash table
- scalable memory allocators
- mutexes
- atomic operations
- global timestamp
- task Manager
- computation graph
The library must specify the task. Further, the library itself will display tasks on threads in an optimal way.
Description of the computational graph
This construction is devoted to the library section - tbb :: flow. The dependencies of many applications running in the operating system are well described as messages moving between nodes of the message flow graph. These messages may contain data, or simply be signals that the “predecessor” has ended. These messages are somewhat similar to the management points of BPM systems.
Nodes of the graph are associated with applications that execute tasks. (In BPMS, nodes in a graph also perform tasks, but nodes are not associated with task performers, but only with tasks themselves).
The main components of the section tbb :: flow
There are three main components in the section:
- Graph (A graph object)
- Node
- Edge
The Graph object is the owner of all tasks generated on behalf of the corresponding message flow graph.
Objects Nodes trigger user-defined functional objects or control messages as inbound / outbound relative to other nodes.
Edges are connections between nodes (similar to transitions in BPMS).
Messaging protocol
Edges dynamically switch between pull and push protocols. The graph can be represented as a construction G = (V, S, L), in which V is the set of nodes, S is the set of edges using the Push-protocol, L is the set of edges using the Pull-protocol.
For each edge (Vi, Vj), Vi is a predecessor (predecessor, or sender) and Vj is a follower (successor, or receiver). in the case of the push of the protocol (S), messages sent along the edge are initiated by the predecessor, which attempts to transmit them to the recipient. In the case of protocol pull (L), messages are initiated by the follower (receiver), who tries to get them from the predecessor (sender).
If the attempt to send a message along the edge failed, then the edge is switched to another protocol mode. This is a very interesting design, there is nothing like this in BPMS, a node cannot “reflect” a control point there.
Using the protocol switching mechanism is a key difference between the TBB library and other similar libraries, which, in the event of a failure, simply periodically attempt to transmit the message. This mechanism can significantly improve the efficiency of interaction between applications.
Objects - Body Objects
Body Objects are used in graph nodes. These objects are provided by users. These objects can be created by functional objects, or by special expressions.
Body objects passed between nodes are copied. Therefore, changing the Body object in the receiver node does not change the corresponding Body object in the sender node. It is also very different from BPMS, because there is no data in the management points, the management points are only markers pointing to the active nodes of the business process, and the data is in variables related to the entire instance of the business process.
Types of vertices (types of nodes of the graph) and a description of how they work
Buffering node block
Node buffer_node. The node has an unlimited buffer for messages of type "T". The node “passes” messages to its successors (to one of the successors) in random order. If successor reflects the message, then the node tries to send this message to another successor.
The queue_node node. The node has an unlimited buffer for messages of type "T". The node “passes” messages in the FIFO order (to one of the successors). In this case, successors are sorted in the order in which they are registered in the node. If successor reflects the message, the node sends this message to the next one in the list to successor.
The priority_queue_node node. The node “flips” the messages in order of priority. (That is, of all the available messages, the node first tries to push the message with the highest priority). Attempts to send a message continue until one of the successors accepts the message, or all the successors are enumerated. If any of the successors received the message, then it is removed from the buffer.
The sequencer_node node. The node has an unlimited buffer for messages of type "T". The node “passes through” the messages in sequential order ... If the successor reflects the message, then the node sends this message to the next successor.
Split / Join node block
Join_node node The node creates a tuple (vector) from the messages that have come along all the incoming edges, multiplies and “flips” this tuple with all its successors. The node supports three message buffering policies: reservation, queue, and tag_matching.
Policy queuing: All incoming messages on each edge are arranged according to the principle of first-in first-out. If there is at least one message on each edge, then all first-out messages are removed from the edges and the tuple is sent to all successors.
Reserving policy: Only 1, or 0 messages are allowed on each edge. Arriving messages on the edge, on which there is already a message, are reflected. Further attempts are being made to pull the predecessors, from which there are no messages on the edges. If for each edge it was possible to receive a message, then all messages are removed from the edges and the tuple is sent to the successor
Policy tag_matching: For each incoming message, on each edge, a special user-prepared functional object is executed, which associates with the message tag. Then the messages on each edge are grouped in a hash table according to their tags. If there is at least one message with a given tag on each edge, then all such messages are removed from the edges and the tuple is sent to all successors.
Or_node node The node propagates and “flips” the message with all its successors, regardless of which incoming edge this message came from.
Split_node node A node that has one incoming edge and more than one outgoing. On an incoming transition, a node receives message tuples. The node is a variant of multifunction_output_node, in which the body sends each element of the incoming tuple along the outgoing edge in accordance with the index of the element in the tuple.
Functional node block
Source_node node This node may be missing a predecessor. A node is never executed in parallel. The node performs its body function and sends the result simultaneously to all its successors.
The continue_node node. After the node receives a message from predecessor, it executes its body objects. Only after that he redirects continue_msg to his successor.
Function_node node The node has a restriction on concurrent actions. If the node cannot process the message immediately, then it puts the message in the FIFO buffer. You can make this setting that if the FIFO buffer is full, the node refuses to process the incoming message.
Multioutput_function_node node. A node that has only one incoming edge and more than one outgoing. The node has a limit on the number of simultaneously processed incoming messages. When the limit is exceeded, the node executes for incoming body messages that have been set by the user. These bodies create messages that are sent to successors.
Node block Other
Broadcast_node node The node propagates and “flips” the incoming message with all its successors
Node write_once_node. This node has a buffer with only one element that cannot be dynamically replaced. Only after an explicit clear command, the buffer can accept a new message.
The overwrite_node node. This node has a buffer with only one element that can be dynamically replaced (overwrite).
The limiter_node node. A node that counts and limits the number of messages that pass through it. The node propagates and “flushes” the incoming message to all its successors, but stops accepting new messages if the message limit is exceeded
We see that the functionality of these nodes is significantly richer than the functionality of the BPMS nodes. Similarly to the nodes of the tbb :: flow section, there is a possibility in BPMS to multiply control points for all outgoing transitions from a node, there is also a possibility to merge control points that came to a node through all incoming transitions, it is possible to “push through” control points that came from any incoming transition on a single outgoing transition. However, in BPMS there is no such thing as a buffer, there is no “rolling out” the message in a random order, BPMS control points have no priorities, no concept of control points tuple, no such concepts as pushing and pulling the control point.
findings
Thus, acquaintance with the TBB library tbb :: flow section shows the BPMS developer with which actually simple object he works and how much this object can be complicated by expanding the behavior of the graph elements. It also becomes clear how much you can increase the functionality of BPMS by adding additional elements to its scheme, similar to those in the tbb :: flow TBB section.
Link to TBB library description
Source: https://habr.com/ru/post/171271/
All Articles