Intel® threading building blocks (intel® tbb) developer guide 中文 parallelizing data flow and dependence graphs并行化data flow和依赖图.

https://www.threadingbuildingblocks.org/docs/help/index.htm

Parallelizing Data Flow and Dependency Graphs

In addition to loop parallelism, the Intel® Threading Building Blocks (Intel® TBB) library also supports graph parallelism. It's possible to create graphs that are highly scalable, but it is also possible to create graphs that are completely sequential.

除了循环并行化,tbb还支持图并行化。这使得创建高度扩展性的图有了可能,同时也能都创建完全顺序执行的图

Using graph parallelism, computations are represented by nodes and the communication channels between these computations are represented by edges. When a node in the graph receives a message, a task is spawned to execute its body object on the incoming message. Messages flow through the graph across the edges that connect the nodes. The following sections present two examples of applications that can be expressed as graphs. For more information on tasks, see the See Also section below.

图并行化中,计算被表示为节点,计算之间的通讯通道被表达为边。当一个节点收到消息,一个任务会被执行。消息通过连接节点的边来流过图。下面有两个例子

The following figure shows a streaming or data flow application where a sequence of values is processed as each value passes through the nodes in the graph. In this example, the sequence is created by a function F. For each value in the sequence, G squares the value and H cubes the value. J then takes each of the squared and cubed values and adds them to a global sum. After all values in the sequence are completely processed, sum is equal to the sum of the sequence of squares and cubes from 1 to 10. In a streaming or data flow graph, the values actually flow across the edges; the output of one node becomes the input of its successor(s).

下图是一个streaming or data flow 的应用

Simple Data Flow Graph 
Simple data flow graph

The following graphic shows a different form of graph application. In this example, a dependence graph is used to establish a partial ordering among the steps for making a peanut butter and jelly sandwich. In this partial ordering, you must first get the bread before spreading the peanut butter or jelly on the bread. You must spread on the peanut butter before you put away the peanut butter jar, and likewise spread on the jelly before you put away the jelly jar. And, you need to spread on both the peanut butter and jelly before putting the two slices of bread together. This is a partial ordering because, for example, it doesn't matter if you spread on the peanut butter first or the jelly first. It also doesn't matter if you finish making the sandwich before putting away the jars.

下图是另外一种图的应用,以dependence graph 的形式表达任务的步骤执行

Dependence Graph for Making a Sandwich 

 

While it can be inferred that resources, such as the bread, or the jelly jar, are shared between ordered steps, it is not explicit in the graph. Instead, only the required ordering of steps is explicit in a dependence graph. For example, you must "Put jelly on 1 slice" before you "Put away jelly jar".

The flow graph interface in the Intel TBB library allows you to express data flow and dependence graphs such as these, as well as more complicated graphs that include cycles, conditionals, buffering and more. If you express your application using the flow graph interface, the runtime library spawns tasks to exploit the parallelism that is present in the graph. For example, in the first example above, perhaps two different values might be squared in parallel, or the same value might be squared and cubed in parallel. Likewise in the second example, the peanut butter might be spread on one slice of bread in parallel with the jelly being spread on the other slice. The interface expresses what is legal to execute in parallel, but allows the runtime library to choose at runtime what will be executed in parallel.

tbb允许你表达data flow and dependence graphs。以及更复杂的图,比如包含cycle,条件,缓冲。。

The support for graph parallelism is contained within the namespace tbb::flow and is defined in the flow_graph.h header file.

See Also

Powered by Jekyll and Theme by solid

本站总访问量