[Bf-blender-cvs] [9ef272bae31] master: Task: Graph Flow Task Scheduling
Jeroen Bakker
noreply at git.blender.org
Mon May 25 12:38:35 CEST 2020
Commit: 9ef272bae31931fe9afc0c037259fd936540ae0b
Author: Jeroen Bakker
Date: Mon May 25 12:24:56 2020 +0200
Branches: master
https://developer.blender.org/rB9ef272bae31931fe9afc0c037259fd936540ae0b
Task: Graph Flow Task Scheduling
Add TBB::flow graph scheduling to BLI_task.
Using flow graphs, a graph of nodes (tasks) and links can be defined.
Work can flow though the graph. During this process the execution of the nodes will be
scheduled among the available threads.
We are planning to use this to improve the threading in the draw manager.
The implemented API is still limited it only supports sequential flows. Joins and buffers
are not supported. We could eventually support them as part of an CPP API. These features
from uses compile time templates and are hard to make a clean C-API for this.
Reviewed By: Sergey Sharybin, Brecht van Lommel
Differential Revision: https://developer.blender.org/D7578
===================================================================
M source/blender/blenlib/BLI_task.h
M source/blender/blenlib/CMakeLists.txt
A source/blender/blenlib/intern/task_graph.cc
A tests/gtests/blenlib/BLI_task_graph_test.cc
M tests/gtests/blenlib/CMakeLists.txt
===================================================================
diff --git a/source/blender/blenlib/BLI_task.h b/source/blender/blenlib/BLI_task.h
index 64dfdc2ad25..a4a855c354b 100644
--- a/source/blender/blenlib/BLI_task.h
+++ b/source/blender/blenlib/BLI_task.h
@@ -237,6 +237,82 @@ BLI_INLINE void BLI_parallel_range_settings_defaults(TaskParallelSettings *setti
* Only here for code to be removed. */
int BLI_task_parallel_thread_id(const TaskParallelTLS *tls);
+/* Task Graph Scheduling */
+/* Task Graphs can be used to create a forest of directional trees and schedule work to any tree.
+ * The nodes in the graph can be run in separate threads.
+ *
+ * +---- [root] ----+
+ * | |
+ * v v
+ * [node_1] +---- [node_2] ----+
+ * | |
+ * v v
+ * [node_3] [node_4]
+ *
+ * TaskGraph *task_graph = BLI_task_graph_create();
+ * TaskNode *root = BLI_task_graph_node_create(task_graph, root_exec, NULL, NULL);
+ * TaskNode *node_1 = BLI_task_graph_node_create(task_graph, node_exec, NULL, NULL);
+ * TaskNode *node_2 = BLI_task_graph_node_create(task_graph, node_exec, NULL, NULL);
+ * TaskNode *node_3 = BLI_task_graph_node_create(task_graph, node_exec, NULL, NULL);
+ * TaskNode *node_4 = BLI_task_graph_node_create(task_graph, node_exec, NULL, NULL);
+ *
+ * BLI_task_graph_edge_create(root, node_1);
+ * BLI_task_graph_edge_create(root, node_2);
+ * BLI_task_graph_edge_create(node_2, node_3);
+ * BLI_task_graph_edge_create(node_2, node_4);
+ *
+ * Any node can be triggered to start a chain of tasks. Normally you would trigger a root node but
+ * it is supported to start the chain of tasks anywhere in the forest or tree. When a node
+ * completes, the execution flow is forwarded via the created edges.
+ * When a child node has multiple parents the child node will be triggered once for each parent.
+ *
+ * BLI_task_graph_node_push_work(root);
+ *
+ * In this example After `root` is finished, `node_1` and `node_2` will be started.
+ * Only after `node_2` is finished `node_3` and `node_4` will be started.
+ *
+ * After scheduling work we need to wait until all the tasks have been finished.
+ *
+ * BLI_task_graph_work_and_wait();
+ *
+ * When finished you can clean up all the resources by freeing the task_graph. Nodes are owned by
+ * the graph and are freed task_data will only be freed if a free_func was given.
+ *
+ * BLI_task_graph_free(task_graph);
+ *
+ * Work can enter a tree on any node. Normally this would be the root_node.
+ * A `task_graph` can be reused, but the caller needs to make sure the task_data is reset.
+ *
+ * ** Task-Data **
+ *
+ * Typically you want give a task data to work on.
+ * Task data can be shared with other nodes, but be carefull not to free the data multiple times.
+ * Task data is freed when calling `BLI_task_graph_free`.
+ *
+ * MyData *task_data = MEM_callocN(sizeof(MyData), __func__);
+ * TaskNode *root = BLI_task_graph_node_create(task_graph, root_exec, task_data, MEM_freeN);
+ * TaskNode *node_1 = BLI_task_graph_node_create(task_graph, node_exec, task_data, NULL);
+ * TaskNode *node_2 = BLI_task_graph_node_create(task_graph, node_exec, task_data, NULL);
+ * TaskNode *node_3 = BLI_task_graph_node_create(task_graph, node_exec, task_data, NULL);
+ * TaskNode *node_4 = BLI_task_graph_node_create(task_graph, node_exec, task_data, NULL);
+ *
+ */
+struct TaskGraph;
+struct TaskNode;
+
+typedef void (*TaskGraphNodeRunFunction)(void *__restrict task_data);
+typedef void (*TaskGraphNodeFreeFunction)(void *task_data);
+
+struct TaskGraph *BLI_task_graph_create(void);
+void BLI_task_graph_work_and_wait(struct TaskGraph *task_graph);
+void BLI_task_graph_free(struct TaskGraph *task_graph);
+struct TaskNode *BLI_task_graph_node_create(struct TaskGraph *task_graph,
+ TaskGraphNodeRunFunction run,
+ void *task_data,
+ TaskGraphNodeFreeFunction free_func);
+bool BLI_task_graph_node_push_work(struct TaskNode *task_node);
+void BLI_task_graph_edge_create(struct TaskNode *from_node, struct TaskNode *to_node);
+
#ifdef __cplusplus
}
#endif
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index 18d58cdcaf3..8f1511ca118 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -119,6 +119,7 @@ set(SRC
intern/string_utf8.c
intern/string_utils.c
intern/system.c
+ intern/task_graph.cc
intern/task_iterator.c
intern/task_pool.cc
intern/task_range.cc
diff --git a/source/blender/blenlib/intern/task_graph.cc b/source/blender/blenlib/intern/task_graph.cc
new file mode 100644
index 00000000000..9a7f18c8348
--- /dev/null
+++ b/source/blender/blenlib/intern/task_graph.cc
@@ -0,0 +1,161 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+/** \file
+ * \ingroup bli
+ *
+ * Task graph.
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_task.h"
+
+#include <memory>
+#include <vector>
+
+#ifdef WITH_TBB
+/* Quiet top level deprecation message, unrelated to API usage here. */
+# define TBB_SUPPRESS_DEPRECATED_MESSAGES 1
+# include <tbb/flow_graph.h>
+# include <tbb/tbb.h>
+#endif
+
+/* Task Graph */
+struct TaskGraph {
+#ifdef WITH_TBB
+ tbb::flow::graph tbb_graph;
+#endif
+ std::vector<std::unique_ptr<TaskNode>> nodes;
+
+#ifdef WITH_CXX_GUARDEDALLOC
+ MEM_CXX_CLASS_ALLOC_FUNCS("task_graph:TaskGraph")
+#endif
+};
+
+/* TaskNode - a node in the task graph. */
+struct TaskNode {
+ /* TBB Node. */
+#ifdef WITH_TBB
+ tbb::flow::continue_node<tbb::flow::continue_msg> tbb_node;
+#endif
+ /* Successors to execute after this task, for serial execution fallback. */
+ std::vector<TaskNode *> successors;
+
+ /* User function to be executed with given task data. */
+ TaskGraphNodeRunFunction run_func;
+ void *task_data;
+ /* Optional callback to free task data along with the graph. If task data
+ * is shared between nodes, only a single task node should free the data. */
+ TaskGraphNodeFreeFunction free_func;
+
+ TaskNode(TaskGraph *task_graph,
+ TaskGraphNodeRunFunction run_func,
+ void *task_data,
+ TaskGraphNodeFreeFunction free_func)
+ :
+#ifdef WITH_TBB
+ tbb_node(task_graph->tbb_graph,
+ tbb::flow::unlimited,
+ std::bind(&TaskNode::run, this, std::placeholders::_1)),
+#endif
+ run_func(run_func),
+ task_data(task_data),
+ free_func(free_func)
+ {
+ }
+
+ TaskNode(const TaskNode &other) = delete;
+ TaskNode &operator=(const TaskNode &other) = delete;
+
+ ~TaskNode()
+ {
+ if (task_data && free_func) {
+ free_func(task_data);
+ }
+ }
+
+#ifdef WITH_TBB
+ tbb::flow::continue_msg run(const tbb::flow::continue_msg UNUSED(input))
+ {
+ tbb::this_task_arena::isolate([this] { run_func(task_data); });
+ return tbb::flow::continue_msg();
+ }
+#endif
+
+ void run_serial()
+ {
+ run_func(task_data);
+ for (TaskNode *successor : successors) {
+ successor->run_serial();
+ }
+ }
+
+#ifdef WITH_CXX_GUARDEDALLOC
+ MEM_CXX_CLASS_ALLOC_FUNCS("task_graph:TaskNode")
+#endif
+};
+
+TaskGraph *BLI_task_graph_create(void)
+{
+ return new TaskGraph();
+}
+
+void BLI_task_graph_free(TaskGraph *task_graph)
+{
+ delete task_graph;
+}
+
+void BLI_task_graph_work_and_wait(TaskGraph *task_graph)
+{
+#ifdef WITH_TBB
+ task_graph->tbb_graph.wait_for_all();
+#endif
+}
+
+struct TaskNode *BLI_task_graph_node_create(struct TaskGraph *task_graph,
+ TaskGraphNodeRunFunction run,
+ void *user_data,
+ TaskGraphNodeFreeFunction free_func)
+{
+ TaskNode *task_node = new TaskNode(task_graph, run, user_data, free_func);
+ task_graph->nodes.push_back(std::unique_ptr<TaskNode>(task_node));
+ return task_node;
+}
+
+bool BLI_task_graph_node_push_work(struct TaskNode *task_node)
+{
+#ifdef WITH_TBB
+ if (BLI_task_scheduler_num_threads() > 1) {
+ return task_node->tbb_node.try_put(tbb::flow::continue_msg());
+ }
+#endif
+
+ task_node->run_serial();
+ return true;
+}
+
+void BLI_task_graph_edge_create(struct TaskNode *from_node, struct TaskNode *to_node)
+{
+#ifdef WITH_TBB
+ if (BLI_task_scheduler_num_threads() > 1) {
+ tbb::flow::make_edge(from_node->tbb_node, to_node->tbb_node);
+ return;
+ }
+#endif
+
+ from_node->successors.push_back(to_node);
+}
diff --git a/tests/gtests/blenlib/BLI_task_graph_test.cc b/tests/gtests/blenlib/BLI_task_graph_test.cc
new file mode 100644
index 00000000000..efcbf923625
--- /dev/null
+++ b/tests/gtests/blenlib/BLI_task_graph_test.cc
@@ -0,0 +1,188 @@
+/* Apache License, Version 2.0 */
+
+#include "testing/testing.h"
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_task.h"
+
+struct TaskData {
+ int value;
+ int store;
+};
+
+static void TaskData_increase_value(void *taskdata)
+{
+ TaskData *data = (TaskData *)taskdata;
+ data->value += 1;
+}
+static void TaskData_decrease_value(void *taskdata)
+{
+ TaskData *data = (TaskData *)taskdata;
+ data->value -= 1;
+}
+static void TaskData_multiply_by_two_value(void *taskdata)
+{
+ TaskData *data = (TaskData *)taskdata;
+ data->value *= 2;
+}
+
+static void TaskData_multiply_by_two_store(void *taskdata)
+{
+ TaskData *data = (TaskData *)taskdata;
+ data->store *= 2;
+}
+
+static void TaskData_store_valu
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list