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_SIZE_ASSIGNMENT_H_ 17 #define TENSORFLOW_LITE_DELEGATES_GPU_COMMON_MEMORY_MANAGEMENT_GREEDY_BY_SIZE_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 offsets, using the following greedy algorithm: 30 // - We have tensor usage records of all intermideate tensors as an input. Each 31 // record consists of tensor size, first and last tasks, that use it. Let's call 32 // [first_task..last_task] a tensor usage interval; 33 // - Iterate through tensor usage records in non-increasing order of 34 // corresponding tensor sizes; 35 // - For each of these records consider already assigned tensors, which usage 36 // intervals intersect with usage interval of current tensor, and find the 37 // smallest gap in memory between them such, that current tensor fits into that 38 // gap; 39 // - If such a gap has been found, current tensor should be allocated into this 40 // gap. Otherwise we can allocate it after the rightmost tensor, which usage 41 // interval intersects with usage interval of current tensor. So we assign 42 // corresponding offset to current tensor and the tensor becomes assigned. 43 absl::Status GreedyBySizeAssignment( 44 const std::vector<TensorUsageRecord<size_t>>& usage_records, 45 OffsetsAssignment* assignment); 46 47 // Assigns given tensors to shared objects, using the following greedy 48 // algorithm: 49 // - We have tensor usage records of all intermideate tensors as an input. Each 50 // record consists of tensor size, first and last tasks, that use it. Let's call 51 // [first_task..last_task] a tensor usage interval; 52 // - Distance between two usage intervals is the absolute difference between 53 // closest tasks in their intervals. If two usage intervals don't intersect, 54 // than the distance between them is positive; 55 // - Calculate positional maximums vector, e.g. the vector of lower bounds on 56 // size of each shared object; 57 // - For each tensor find the rightmost positional maximum, that is greater or 58 // equal, than current tensor's size (call it position); 59 // - Iterate through all tensors in non-decreasing order of their 60 // SizeDistPriority (described above); 61 // - For every such tensor, assign it to the object, that already has tensor, 62 // which usage interval has the smallest existing positive distance to the 63 // current tensor's usage interval (this distance and object id are already 64 // precalculated in its SizeDistPriority record). Size of the chosen object can 65 // possible increase; 66 // - If there are several such objects, use the largest one; 67 // - If there are no suitable shared objects, assign current tensor to the new 68 // object with size equal to current tensor's size; 69 // - Modify SizeDistPriority records of tensors, that haven't been assigned yet, 70 // to reflect distance changes after that assignment. 71 absl::Status GreedyBySizeDistPriorityAssignment( 72 const std::vector<TensorUsageRecord<size_t>>& usage_records, 73 ObjectsAssignment<size_t>* assignment); 74 75 } // namespace gpu 76 } // namespace tflite 77 78 #endif // TENSORFLOW_LITE_DELEGATES_GPU_COMMON_MEMORY_MANAGEMENT_GREEDY_BY_SIZE_ASSIGNMENT_H_ 79