1 /* Copyright 2019 The TensorFlow Authors. All Rights Reserved. 2 3 Licensed under the Apache License, Version 2.0 (the "License"); 4 you may not use this file except in compliance with the License. 5 You may obtain a copy of the License at 6 7 http://www.apache.org/licenses/LICENSE-2.0 8 9 Unless required by applicable law or agreed to in writing, software 10 distributed under the License is distributed on an "AS IS" BASIS, 11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 See the License for the specific language governing permissions and 13 limitations under the License. 14 ==============================================================================*/ 15 16 #ifndef TENSORFLOW_LITE_DELEGATES_GPU_COMMON_MEMORY_MANAGEMENT_GREEDY_BY_BREADTH_ASSIGNMENT_H_ 17 #define TENSORFLOW_LITE_DELEGATES_GPU_COMMON_MEMORY_MANAGEMENT_GREEDY_BY_BREADTH_ASSIGNMENT_H_ 18 19 #include <stddef.h> 20 21 #include <vector> 22 23 #include "tensorflow/lite/delegates/gpu/common/memory_management/types.h" 24 #include "tensorflow/lite/delegates/gpu/common/status.h" 25 26 namespace tflite { 27 namespace gpu { 28 29 // Assigns given tensors to shared objects, using the following greedy 30 // algorithm: 31 // - We have tensor usage records of all intermideate tensors as an input. Each 32 // record consists of tensor size, first and last tasks, that use it. Let's call 33 // [first_task..last_task] a tensor usage interval; 34 // - For each task calculate its TaskProfile. By breadth of the task we 35 // understand sum of sizes of all tensors in its TaskProfile; 36 // - Iterate through all tasks in non-increasing order of breadth; 37 // - For each of these tasks iterate through all tensors in its TaskProfile in 38 // non-increasing order of tensor_size; 39 // - For every such tensor usage record find a shared object, that is not 40 // assigned to some tensors, which usage intervals intersect with usage interval 41 // of current tensor; 42 // - If there are no suitable shared objects, assign current tensor to the new 43 // object with size equal to current tensor's size; 44 // - If there are suitable objects with size greater than or equal to current 45 // tensor’s size, assign current tensor to the smallest of them; 46 // - If there are suitable objects only with size less than current tensor’s 47 // size, assign current tensor to the largest of them and increase its size. 48 absl::Status GreedyByBreadthAssignment( 49 const std::vector<TensorUsageRecord<size_t>>& usage_records, 50 ObjectsAssignment<size_t>* assignment); 51 52 } // namespace gpu 53 } // namespace tflite 54 55 #endif // TENSORFLOW_LITE_DELEGATES_GPU_COMMON_MEMORY_MANAGEMENT_GREEDY_BY_BREADTH_ASSIGNMENT_H_ 56