1 /** 2 * Copyright 2020 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_OPTIMIZER_SOMAS_SOMAS_SOLVER_PRE_H_ 18 #define MINDSPORE_CCSRC_BACKEND_OPTIMIZER_SOMAS_SOMAS_SOLVER_PRE_H_ 19 20 #include <algorithm> 21 #include <cassert> 22 #include <cstddef> 23 #include <cstring> 24 #include <iostream> 25 #include <map> 26 #include <memory> 27 #include <stack> 28 #include <unordered_map> 29 #include <vector> 30 #include "backend/session/kernel_graph.h" 31 32 using std::unordered_map; 33 using std::vector; 34 35 namespace mindspore { 36 namespace somas { 37 constexpr char const *sortingNames[6] = {"size(>), index(<)", 38 "size(>), index(>)", 39 "size(>), constraints(<), index(<)", 40 "size(>), constraints(<), index(>)", 41 "size(>), constraints(>), index(<)", 42 "size(>), constraints(>), index(>)"}; 43 constexpr char const *branchingNames[4] = {"bestfit", "smallest", "largest", "worstfit"}; 44 constexpr char const *algorithmTypeNames[2] = {"Shared Objects", "Single Object"}; 45 constexpr auto kParallelComputeSizeThreshold = 2000; 46 enum Status { FAILED, SUCCESS }; 47 enum AlgorithmType { kManyObjects = 0, kSingleObject, kNumAlgorithmTypes }; 48 enum SortingType { 49 kGreaterSizeSmallerIndex = 0, 50 #ifdef SOMAS_DEBUG 51 kGreaterSizeGreaterIndex, 52 kGreaterSizeSmallerConstraintsSmallerIndex, 53 kGreaterSizeSmallerConstraintsGreaterIndex, 54 kGreaterSizeGreaterConstraintsSmallerIndex, 55 kGreaterSizeGreaterConstraintsGreaterIndex, 56 #endif 57 kNumSortingTypes 58 }; 59 enum FittingType { 60 kBest = 0, 61 kSmallest, 62 #ifdef SOMAS_DEBUG 63 kLargest, 64 kWorst, 65 #endif 66 kNumFittingTypes 67 }; 68 69 class DynamicBitSet { 70 const size_t bit_width_ = 64; 71 GetIndex(size_t index)72 inline size_t GetIndex(size_t index) const { return index / bit_width_; } 73 GetBitMask(size_t index)74 inline uint64_t GetBitMask(size_t index) const { 75 return (((uint64_t)0x1) << (bit_width_ - 1 - (index % bit_width_))); 76 } 77 Reset(uint64_t val)78 inline void Reset(uint64_t val) { 79 bit_.clear(); 80 for (size_t i = 0; i < bit_size_; i++) { 81 bit_.push_back(val); 82 } 83 } 84 85 public: 86 size_t bit_size_; 87 std::vector<uint64_t> bit_; DynamicBitSet(size_t count)88 explicit DynamicBitSet(size_t count) { 89 bit_size_ = (count + bit_width_ - 1) / bit_width_; 90 Reset(0x0); 91 } 92 93 ~DynamicBitSet() = default; 94 95 void SetBitTrue(size_t index, bool log = false) { 96 if (log) { 97 MS_LOG(INFO) << GetIndex(index) << " " << GetBitMask(index); 98 } 99 bit_[GetIndex(index)] |= GetBitMask(index); 100 } 101 SetBitFalse(size_t index)102 void SetBitFalse(size_t index) { bit_[GetIndex(index)] &= (~GetBitMask(index)); } 103 IsBitTrue(size_t index)104 bool IsBitTrue(size_t index) const { return (bit_[GetIndex(index)] & GetBitMask(index)) != 0x0; } 105 CountOnesNum()106 size_t CountOnesNum() const { 107 size_t ret = 0; 108 static char ones_num_in_hex[] = "\0\1\1\2\1\2\2\3\1\2\2\3\2\3\3\4"; 109 for (size_t i = 0; i < bit_size_; i++) { 110 auto value = bit_[i]; 111 if (value == 0) { 112 continue; 113 } 114 char *char_value = reinterpret_cast<char *>(&value); 115 for (size_t j = 0; j < bit_width_ / CHAR_BIT; j++) { 116 ret += ones_num_in_hex[char_value[j] & 0xF]; 117 char_value[j] >>= 4; 118 ret += ones_num_in_hex[char_value[j] & 0xF]; 119 } 120 } 121 return ret; 122 } 123 Log()124 void Log() { 125 std::cout << "Start Print Bitset "; 126 for (size_t i = 0; i < bit_size_; i++) { 127 std::cout << " bit [" << std::dec << i << "] = " << std::hex << bit_[i] << std::dec; 128 } 129 std::cout << std::endl; 130 } 131 Union(DynamicBitSet * a,DynamicBitSet * b)132 friend void Union(DynamicBitSet *a, DynamicBitSet *b) { 133 for (size_t i = 0; i < (*a).bit_size_; i++) { 134 (*a).bit_[i] |= (*b).bit_[i]; 135 } 136 } 137 }; 138 139 struct SomasSolverTensorDesc { 140 size_t index_; 141 size_t size_; 142 size_t offset_; 143 bool lifelong_; 144 size_t constraints_; 145 using SomasSolverTensorDescPtr = std::shared_ptr<SomasSolverTensorDesc>; 146 SomasSolverTensorDescPtr right_; 147 SomasSolverTensorDescPtr left_; 148 bool blocked_; 149 150 SomasSolverTensorDesc() = default; 151 SomasSolverTensorDescSomasSolverTensorDesc152 SomasSolverTensorDesc(size_t index, size_t size, size_t offset, bool blifelong) 153 : index_(index), size_(size), offset_(offset), lifelong_(blifelong) { 154 constraints_ = 0; 155 right_ = nullptr; 156 left_ = nullptr; 157 blocked_ = false; 158 } 159 UpdateSomasSolverTensorDesc160 void Update(size_t index, size_t size, size_t offset, bool blifelong, size_t constraints) { 161 index_ = index; 162 size_ = size; 163 offset_ = offset; 164 lifelong_ = blifelong; 165 constraints_ = constraints; 166 } 167 168 friend std::ostream &operator<<(std::ostream &out, const SomasSolverTensorDescPtr n) { 169 out << n->index_ << " " << n->size_ << " " << n->offset_ << "\n"; 170 return out; 171 } 172 friend std::istream &operator>>(std::istream &in, SomasSolverTensorDescPtr n) { 173 in >> n->index_ >> n->size_ >> n->offset_; 174 return in; 175 } 176 }; 177 using SomasSolverTensorDescPtr = std::shared_ptr<SomasSolverTensorDesc>; 178 typedef std::unordered_map<size_t, SomasSolverTensorDescPtr> TensorsDescMap; 179 class SomasSolverPre { 180 public: 181 SomasSolverPre() = default; 182 ~SomasSolverPre() = default; 183 184 SomasSolverPre(const SomasSolverPre &) = delete; 185 SomasSolverPre &operator=(const SomasSolverPre &) = delete; 186 GetMaxOffset()187 size_t GetMaxOffset() { return max_offset_; } 188 189 Status Solving(const session::KernelGraph *graph, TensorsDescMap *tensors, 190 const std::vector<DynamicBitSet> *pConstraints, const vector<vector<size_t>> &continuous_v, 191 bool bVerifySolution, // true -> Check continuous and non overlapping constraints solution 192 bool ball = true, // true -> run full set of heuristics, false -> run single heuristic specified 193 SortingType sorting = kGreaterSizeSmallerIndex, FittingType fitting = kBest, 194 AlgorithmType algorithm = kManyObjects); 195 196 void Log(const session::KernelGraph *graph, const TensorsDescMap &tensors, 197 const std::vector<DynamicBitSet> *pConstraints_v, const vector<vector<size_t>> &continuous_v); 198 199 Status CheckTensors(const TensorsDescMap *pTensors, uint32_t index1, uint32_t index2); 200 Status AddContiguousInfoInMap(const vector<vector<size_t>> &continuous_v, TensorsDescMap *pTensors); 201 Status AddContiguousInfoInMultiMaps(const vector<vector<size_t>> &continuous_v, vector<TensorsDescMap> *vecTensorsMap, 202 const TensorsDescMap *pTensors); 203 204 private: 205 size_t max_offset_; 206 void SolverInputLog(const session::KernelGraph *graph, const TensorsDescMap &tensors, 207 const vector<vector<size_t>> &continuous_v); 208 void SolverOutputLog(const session::KernelGraph *graph, const TensorsDescMap &tensors) const; 209 vector<TensorsDescMap> CreateTensorsMaps(const TensorsDescMap &tensors, size_t total_sol); 210 void TensorRelationLog(const std::vector<DynamicBitSet> *pConstraints, const session::KernelGraph *graph); 211 }; 212 using SomasSolverPrePtr = std::shared_ptr<SomasSolverPre>; 213 } // namespace somas 214 } // namespace mindspore 215 216 #endif // MINDSPORE_CCSRC_BACKEND_OPTIMIZER_SOMAS_SOMAS_SOLVER_PRE_H_ 217