| /* |
| * Copyright (c) 2021 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 SRC_RUNTIME_CL_MLGO_HEURISTIC_TREE_H |
| #define SRC_RUNTIME_CL_MLGO_HEURISTIC_TREE_H |
| |
| #include "arm_compute/core/Types.h" |
| #include "src/runtime/CL/mlgo/Common.h" |
| |
| #include <map> |
| #include <memory> |
| #include <string> |
| #include <utility> |
| |
| namespace arm_compute |
| { |
| namespace mlgo |
| { |
| /** Conditional ops */ |
| enum class ConditionalOp |
| { |
| EQ, /**< Equal */ |
| LT, /**< Less than */ |
| LE, /**< Less than or equal to */ |
| GT, /**< Greater than */ |
| GE, /**< Greater than or equal to */ |
| }; |
| |
| /** A branch condition expression evaluating: feature op threshold */ |
| struct Condition |
| { |
| std::string feature; /**< Feature name */ |
| ConditionalOp op; /**< Condtional op */ |
| float threshold; /**< Threshold value */ |
| }; |
| |
| /** GEMM Shape used for query */ |
| struct GEMMShape |
| { |
| unsigned int m; /**< Number of rows for the lhs matrix. Lhs matrix NOT transposed */ |
| unsigned int n; /**< Number of columns for the rhs matrix. Rhs matrix NOT transposed */ |
| unsigned int k; /**< Number of rows for the rhs matrix. Rhs matrix NOT transposed */ |
| unsigned int b; /**< Batch size */ |
| }; |
| |
| /** A binary decision tree based heuristic */ |
| class HeuristicTree |
| { |
| public: |
| using NodeID = size_t; |
| using TreeID = size_t; |
| using Index = std::tuple<HeuristicType, std::string, DataType>; |
| enum class NodeType |
| { |
| Branch, |
| Leaf |
| }; |
| struct Node |
| { |
| virtual NodeType type() const = 0; |
| virtual ~Node() = default; |
| }; |
| |
| struct BranchNode : public Node |
| { |
| BranchNode(NodeID id, Condition cond, NodeID t_node, NodeID f_node) |
| : id{ id }, condition{ cond }, true_node{ t_node }, false_node{ f_node } |
| { |
| } |
| NodeType type() const override |
| { |
| return NodeType::Branch; |
| } |
| NodeID id; |
| Condition condition; |
| NodeID true_node; |
| NodeID false_node; |
| }; |
| |
| template <typename T> |
| struct LeafNode : public Node |
| { |
| LeafNode(NodeID id, T val) |
| : id{ id }, value{ val } |
| { |
| } |
| NodeType type() const override |
| { |
| return NodeType::Leaf; |
| } |
| NodeID id; |
| T value; |
| }; |
| |
| public: |
| /** Constructor */ |
| HeuristicTree(); |
| /** Constructor */ |
| HeuristicTree(TreeID id, HeuristicType h_type, const std::string &ip_target, DataType data_type); |
| // Since the HeuristicTree is a handle that owns the the nodes, it is move-only |
| /** Prevent copy construction */ |
| HeuristicTree(const HeuristicTree &) = delete; |
| /** Prevent copy assignment */ |
| HeuristicTree &operator=(const HeuristicTree &) = delete; |
| /** Move constructor */ |
| HeuristicTree(HeuristicTree &&other) noexcept = default; |
| /** Move assignment */ |
| HeuristicTree &operator=(HeuristicTree &&other) = default; |
| |
| /** Query a leaf value given a gemm shape |
| * |
| * @tparam T Leaf value type |
| * @param shape A @ref GEMMShape for the query |
| * @return std::pair<bool, T> Outcome contains bool, signalling if the query succeeded or not |
| */ |
| template <typename T> |
| std::pair<bool, T> query(GEMMShape shape) const; |
| |
| /** Add a leaf node |
| * |
| * @tparam T Leaf value type |
| * @param id Leaf node ID |
| * @param leaf_value Leaf node value |
| * @return bool If the addition succeeded or not |
| */ |
| template <typename T> |
| bool add_leaf(NodeID id, T leaf_value); |
| /** Add a branch node |
| * |
| * @param id Branch node ID |
| * @param cond Branch node @ref Condition |
| * @param true_node True node's ID |
| * @param false_node False node's ID |
| * @return bool If the addition succeeded or not |
| */ |
| bool add_branch(NodeID id, Condition cond, NodeID true_node, NodeID false_node); |
| |
| /** Get tree ID |
| * @return TreeID |
| */ |
| TreeID id() const |
| { |
| return _id; |
| } |
| |
| /** Get tree index |
| * @return Index |
| */ |
| Index index() const |
| { |
| return std::make_tuple(_heuristic_type, _ip_target, _data_type); |
| } |
| |
| /** Check if tree is valid |
| * @return bool |
| */ |
| bool check(); |
| |
| private: |
| static constexpr size_t _max_query_depth{ 1000 }; // Maximum depth of query |
| static constexpr size_t _max_num_nodes{ 100000 }; // Maximum number of nodes contained by the tree |
| static constexpr NodeID _root{ 0 }; // Root tree ID |
| |
| private: |
| bool check_if_structurally_correct() const; |
| |
| private: |
| TreeID _id; /**< Heuristic tree ID */ |
| HeuristicType _heuristic_type; /**< Heuristic type */ |
| std::string _ip_target; /**< IP target associated with the tree */ |
| DataType _data_type; /**< Data type associated with the tree */ |
| std::map<NodeID, std::unique_ptr<Node>> _tree; /**< Tree representation */ |
| }; |
| } // namespace mlgo |
| |
| } // namespace arm_compute |
| |
| #endif //SRC_RUNTIME_CL_MLGO_HEURISTIC_TREE_H |