1 /** 2 * Copyright 2020-2023 Huawei Technologies Co., Ltd 3 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 8 * http://www.apache.org/licenses/LICENSE-2.0 9 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef MINDSPORE_CCSRC_BACKEND_COMMON_SOMAS_SOMAS_SOLVER_ALG_H_ 18 #define MINDSPORE_CCSRC_BACKEND_COMMON_SOMAS_SOMAS_SOLVER_ALG_H_ 19 20 #include <algorithm> 21 #include <cassert> 22 #include <chrono> 23 #include <cstddef> 24 #include <cstring> 25 #include <list> 26 #include <memory> 27 #include <numeric> 28 #include <set> 29 #include <stack> 30 #include <utility> 31 #include <vector> 32 33 #include "utils/hash_map.h" 34 #include "backend/common/somas/somas_solver_pre.h" 35 #include "utils/ms_context.h" 36 37 using std::pair; 38 using std::set; 39 using std::stack; 40 using std::vector; 41 42 namespace mindspore { 43 namespace somas { 44 constexpr auto kDefaultAlignmentSize = 512; 45 46 class Interval { 47 public: Interval()48 Interval() : m_a_(0), m_b_(0) {} Interval(const SomasSolverTensorDescPtr & t)49 explicit Interval(const SomasSolverTensorDescPtr &t) : m_a_(t->offset_), m_b_(t->offset_ + t->size_) {} Interval(const size_t & a,const size_t & b)50 Interval(const size_t &a, const size_t &b) : m_a_(a), m_b_(b) {} Interval(const Interval & in)51 Interval(const Interval &in) { 52 if (this == &in) { 53 return; 54 } 55 m_a_ = in.m_a_; 56 m_b_ = in.m_b_; 57 } 58 ~Interval() = default; 59 intersect(const Interval & i)60 bool intersect(const Interval &i) const { return (in(i.m_a_) || in(i.m_b_)); } in(const size_t & a)61 bool in(const size_t &a) const { return ((a > m_a_) && (a < m_b_)); } intersection(const Interval & i)62 Interval intersection(const Interval &i) { 63 if (m_a_ < i.m_a_) { 64 return Interval(m_a_, i.m_b_); 65 } else { 66 return Interval(i.m_a_, m_b_); 67 } 68 } merge(const Interval & i)69 void merge(const Interval &i) { 70 m_a_ = std::min(m_a_, i.m_a_); 71 m_b_ = std::max(m_b_, i.m_b_); 72 } lb()73 size_t &lb() { return m_a_; } ub()74 size_t &ub() { return m_b_; } contains(size_t width)75 bool contains(size_t width) const { return (m_b_ - m_a_) >= width; } contains(const Interval & a)76 bool contains(const Interval &a) const { return ((a.m_a_ >= m_a_) && (a.m_b_ <= m_b_)); } 77 Interval &operator=(const Interval &in) { 78 if (this == &in) { 79 return *this; 80 } 81 m_a_ = in.m_a_; 82 m_b_ = in.m_b_; 83 return *this; 84 } 85 86 private: 87 size_t m_a_; 88 size_t m_b_; 89 }; 90 91 class BlockTensor { 92 public: 93 SomasSolverTensorDescPtr m_start_tensor_; 94 mindspore::HashMap< 95 uint32_t, std::set<pair<size_t, size_t>, bool (*)(const pair<size_t, size_t> &, const pair<size_t, size_t> &)>> 96 offsets_candidates_; 97 uint32_t m_current_sol_; 98 bool m_bre_allocate_; 99 mindspore::HashMap<uint32_t, size_t> offsets_; 100 size_t m_size_; BlockTensor()101 BlockTensor() 102 : m_start_tensor_(nullptr), 103 offsets_candidates_(), 104 m_current_sol_(0), 105 m_bre_allocate_(true), 106 offsets_(), 107 m_size_(0) {} 108 ~BlockTensor() = default; BlockTensor(const BlockTensor & bt)109 BlockTensor(const BlockTensor &bt) { 110 if (this == &bt) { 111 return; 112 } 113 m_bre_allocate_ = bt.m_bre_allocate_; 114 m_current_sol_ = 0; 115 m_start_tensor_ = bt.m_start_tensor_; 116 offsets_candidates_ = bt.offsets_candidates_; 117 offsets_ = bt.offsets_; 118 m_size_ = bt.m_size_; 119 } 120 121 BlockTensor &operator=(const BlockTensor &bt) { 122 if (this == &bt) { 123 return *this; 124 } 125 m_bre_allocate_ = bt.m_bre_allocate_; 126 m_current_sol_ = 0; 127 m_start_tensor_ = bt.m_start_tensor_; 128 offsets_candidates_ = bt.offsets_candidates_; 129 offsets_ = bt.offsets_; 130 m_size_ = bt.m_size_; 131 return *this; 132 } Alone()133 bool Alone() const { return ((nullptr == m_start_tensor_->right_) && (nullptr == m_start_tensor_->left_)); } 134 }; 135 136 struct AllocatedTensorInfo { 137 size_t index_; 138 size_t size_; 139 size_t offset_; AllocatedTensorInfoAllocatedTensorInfo140 explicit AllocatedTensorInfo(const SomasSolverTensorDescPtr &tensor) 141 : index_(tensor->index_), size_(tensor->size_), offset_(tensor->offset_) {} 142 }; 143 144 class FootPrint : public std::enable_shared_from_this<FootPrint> { 145 public: 146 uint32_t m_solId_; 147 FootPrint()148 FootPrint() 149 : m_solId_(0), 150 m_foot_print_next_(nullptr), 151 m_offset_(0), 152 m_starts_({}), 153 m_alignment_(0), 154 m_branching_strategy_(0), 155 m_algorithm_(0) {} 156 ~FootPrint() = default; setAlignment(const size_t a)157 void setAlignment(const size_t a) { m_alignment_ = a; } setBranchingStrategy(uint32_t bs)158 void setBranchingStrategy(uint32_t bs) { m_branching_strategy_ = bs; } setCurrentSol(uint32_t solId)159 void setCurrentSol(uint32_t solId) { m_solId_ = solId; } setAlgorithm(uint32_t algorithm)160 void setAlgorithm(uint32_t algorithm) { m_algorithm_ = algorithm; } 161 void addElem(BlockTensor *block, const size_t &offset); 162 void addTensorsInfo(BlockTensor *elemIndex); Next()163 std::shared_ptr<FootPrint> &Next() { return m_foot_print_next_; } getStarts()164 vector<BlockTensor *> &getStarts() { return m_starts_; } 165 void Destroy(); getOffset()166 const size_t getOffset() const { return m_offset_; } setOffset(const size_t & offset)167 void setOffset(const size_t &offset) { m_offset_ = offset; } 168 bool findOffset(const std::vector<VectorBitSet> *constraints, const BlockTensor &block, size_t *offset); 169 bool findFirst(vector<Interval> *interval_v, const BlockTensor &block, size_t *offset); 170 size_t Result(); 171 void printStats(); 172 173 private: 174 std::shared_ptr<FootPrint> m_foot_print_next_; 175 size_t m_offset_; 176 vector<BlockTensor *> m_starts_; 177 vector<AllocatedTensorInfo> m_tensors_info_; 178 size_t m_alignment_; 179 uint32_t m_branching_strategy_; 180 uint32_t m_algorithm_; 181 }; 182 183 class FastHeuristic { 184 public: FastHeuristic()185 FastHeuristic() : m_alignment_(kDefaultAlignmentSize), m_tensors_allocated_(0) {} 186 ~FastHeuristic() = default; 187 setAlignment(const size_t & a)188 void setAlignment(const size_t &a) { m_alignment_ = a; } 189 void Destroy(); 190 bool Eval(vector<BlockTensor> *block_tensors_v, const std::shared_ptr<FootPrint> &foot_print, 191 const std::vector<VectorBitSet> *pConstraints); 192 193 private: 194 size_t m_alignment_; 195 size_t m_tensors_allocated_; 196 }; 197 } // namespace somas 198 } // namespace mindspore 199 200 #endif // MINDSPORE_CCSRC_BACKEND_COMMON_SOMAS_SOMAS_SOLVER_ALG_H_ 201