From 2a2db590fd179dcb8e1a575293cd2b887e2dc246 Mon Sep 17 00:00:00 2001 From: Georgios Pinitas Date: Wed, 15 Aug 2018 12:14:46 +0100 Subject: COMPMID-1505: Add native grouping support at graph level Change-Id: Iedc91b0aee743b59af5140c8acb8124548da3163 Reviewed-on: https://eu-gerrit-1.euhpc.arm.com/144362 Tested-by: Jenkins Reviewed-by: Giorgio Arena Reviewed-by: Michele DiGiorgio --- arm_compute/graph/algorithms/Algorithms.h | 2 +- arm_compute/graph/algorithms/BFS.h | 123 ------------------------- arm_compute/graph/algorithms/TopologicalSort.h | 54 +++++++++++ 3 files changed, 55 insertions(+), 124 deletions(-) delete mode 100644 arm_compute/graph/algorithms/BFS.h create mode 100644 arm_compute/graph/algorithms/TopologicalSort.h (limited to 'arm_compute/graph/algorithms') diff --git a/arm_compute/graph/algorithms/Algorithms.h b/arm_compute/graph/algorithms/Algorithms.h index f89856f327..7af2455e93 100644 --- a/arm_compute/graph/algorithms/Algorithms.h +++ b/arm_compute/graph/algorithms/Algorithms.h @@ -24,6 +24,6 @@ #ifndef __ARM_COMPUTE_GRAPH_ALGORITHMS_H__ #define __ARM_COMPUTE_GRAPH_ALGORITHMS_H__ -#include "arm_compute/graph/algorithms/BFS.h" +#include "arm_compute/graph/algorithms/TopologicalSort.h" #endif /* __ARM_COMPUTE_GRAPH_ALGORITHMS_H__ */ diff --git a/arm_compute/graph/algorithms/BFS.h b/arm_compute/graph/algorithms/BFS.h deleted file mode 100644 index 97292d733b..0000000000 --- a/arm_compute/graph/algorithms/BFS.h +++ /dev/null @@ -1,123 +0,0 @@ -/* - * Copyright (c) 2018 ARM Limited. - * - * SPDX-License-Identifier: MIT - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to - * deal in the Software without restriction, including without limitation the - * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or - * sell copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in all - * copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - */ -#ifndef __ARM_COMPUTE_GRAPH_ALGORITHM_BFS_H__ -#define __ARM_COMPUTE_GRAPH_ALGORITHM_BFS_H__ - -#include "arm_compute/graph/Graph.h" - -#include -#include - -namespace arm_compute -{ -namespace graph -{ -namespace detail -{ -/** Checks if all the input dependencies of a node have been visited - * - * @param[in] node Node to check - * @param[in] visited Vector that contains the visited information - * - * @return True if all inputs dependencies have been visited else false - */ -inline bool all_inputs_are_visited(const INode *node, const std::vector &visited) -{ - ARM_COMPUTE_ERROR_ON(node == nullptr); - const Graph *graph = node->graph(); - ARM_COMPUTE_ERROR_ON(graph == nullptr); - - bool are_all_visited = true; - for(const auto &input_edge_id : node->input_edges()) - { - if(input_edge_id != EmptyNodeID) - { - const Edge *input_edge = graph->edge(input_edge_id); - ARM_COMPUTE_ERROR_ON(input_edge == nullptr); - ARM_COMPUTE_ERROR_ON(input_edge->producer() == nullptr); - if(!visited[input_edge->producer_id()]) - { - are_all_visited = false; - break; - } - } - } - - return are_all_visited; -} -} // namespace detail - -/** Breadth first search traversal - * - * @param g Graph to traverse - * - * @return A vector with the node id traversal order - */ -inline std::vector bfs(Graph &g) -{ - std::vector bfs_order_vector; - - // Created visited vector - std::vector visited(g.nodes().size(), false); - - // Create BFS queue - std::list queue; - - // Push inputs and mark as visited - for(auto &input : g.nodes(NodeType::Input)) - { - if(input != EmptyNodeID) - { - visited[input] = true; - queue.push_back(input); - } - } - - // Iterate over vector and edges - while(!queue.empty()) - { - // Dequeue a node from queue and process - NodeID n = queue.front(); - bfs_order_vector.push_back(n); - queue.pop_front(); - - const INode *node = g.node(n); - ARM_COMPUTE_ERROR_ON(node == nullptr); - for(const auto &eid : node->output_edges()) - { - const Edge *e = g.edge(eid); - ARM_COMPUTE_ERROR_ON(e == nullptr); - if(!visited[e->consumer_id()] && detail::all_inputs_are_visited(e->consumer(), visited)) - { - visited[e->consumer_id()] = true; - queue.push_back(e->consumer_id()); - } - } - } - - return bfs_order_vector; -} -} // namespace graph -} // namespace arm_compute -#endif /* __ARM_COMPUTE_GRAPH_ALGORITHM_BFS_H__ */ diff --git a/arm_compute/graph/algorithms/TopologicalSort.h b/arm_compute/graph/algorithms/TopologicalSort.h new file mode 100644 index 0000000000..6684844790 --- /dev/null +++ b/arm_compute/graph/algorithms/TopologicalSort.h @@ -0,0 +1,54 @@ +/* + * Copyright (c) 2018 ARM Limited. + * + * SPDX-License-Identifier: MIT + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to + * deal in the Software without restriction, including without limitation the + * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or + * sell copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ +#ifndef __ARM_COMPUTE_GRAPH_ALGORITHM_TOPOLOGICAL_SORT_H__ +#define __ARM_COMPUTE_GRAPH_ALGORITHM_TOPOLOGICAL_SORT_H__ + +#include "arm_compute/graph/Types.h" + +#include + +namespace arm_compute +{ +namespace graph +{ +// Forward declarations +class Graph; + +/** Breadth first search traversal + * + * @param g Graph to traverse + * + * @return A vector with the node id traversal order + */ +std::vector bfs(Graph &g); +/** Depth first search traversal + * + * @param g Graph to traverse + * + * @return A vector with the node id traversal order + */ +std::vector dfs(Graph &g); +} // namespace graph +} // namespace arm_compute +#endif /* __ARM_COMPUTE_GRAPH_ALGORITHM_TOPOLOGICAL_SORT_H__ */ -- cgit v1.2.1