inference-engine/src/inference_engine/memory_solver.cpp

   1 // Copyright (C) 2018 Intel Corporation
   2 //
   3 // SPDX-License-Identifier: Apache-2.0
   4 //
   5
   6 #include "memory_solver.hpp"
   7
   8 #include "details/ie_exception.hpp"
   9
  10 #include <algorithm>
  11 #include <vector>
  12 #include <map>
  13
  14 namespace InferenceEngine {
  15
  16 MemorySolver::MemorySolver(const std::vector<Box> boxes) : _boxes(boxes) {
  17     int max_ts = 0;
  18     for (const Box &box : _boxes) max_ts = std::max(std::max(max_ts, box.start), box.finish);
  19     for (Box &box : _boxes) if (box.finish == -1) box.finish = max_ts;
  20
  21     // sort by start and finish ts
  22     std::sort(_boxes.begin(), _boxes.end(), [](const Box& l, const Box& r) -> bool
  23         { return l.start < r.start || (l.start == r.start && l.finish < r.finish); });
  24
  25     // remove unused timestamps (not a begin of some box)
  26     // each ts should start a box
  27     std::vector<bool> ts_exist(max_ts+1);
  28     for (const Box &b : _boxes) ts_exist[b.start] = true;
  29
  30     int rm_ts_s = 0, rm_ts_f = 0;
  31     int ts_s = 0, ts_f = 0;
  32     for (Box &b : _boxes) {
  33         while (ts_s < b.start) if (!ts_exist[ts_s++]) rm_ts_s++;
  34
  35         if (ts_f > b.finish + 1) { ts_f = ts_s; rm_ts_f = rm_ts_s; }
  36         while (ts_f <= b.finish) if (!ts_exist[ts_f++]) rm_ts_f++;
  37
  38         b.start -= rm_ts_s;
  39         b.finish -= rm_ts_f;
  40     }
  41     _time_duration = ts_f - rm_ts_f;
  42 }
  43
  44 inline bool popupTogetherWith(MemorySolver::Box &box_new, const MemorySolver::Box &box_old) {
  45     if (box_new.id+box_new.size > box_old.id &&
  46         box_old.id+box_old.size > box_new.id) {
  47         // Move the new one up. There is an intersection
  48         box_new.id = box_old.id + box_old.size;
  49         return true;
  50     } else {
  51         return false;
  52     }
  53 }
  54
  55 int MemorySolver::solve() {
  56     maxTopDepth();  // at first make sure that we no need more for boxes sorted by box.start
  57     std::vector<std::vector<const Box*>> time_slots(_time_duration);
  58     for (auto & slot : time_slots) slot.reserve(_top_depth);  // 2D array [_time_duration][_top_depth]
  59
  60     // Sort be box size. First is biggest
  61     // Comment this line to check other order of box putting
  62     std::sort(_boxes.begin(), _boxes.end(), [](const Box& l, const Box& r)
  63         { return l.size > r.size; });
  64
  65     int _min_required = 0;
  66
  67     for (Box& box : _boxes) {
  68         // start from bottom and will lift it up if intersect with other present
  69         int id = box.id;
  70         box.id = 0;  // id will be used as a temp offset storage
  71         bool popped_up;
  72         do {
  73             popped_up = false;
  74             for (int i_slot = box.start; i_slot <= box.finish; i_slot++) {
  75                 for (auto *box_in_slot : time_slots[i_slot]) {
  76                     // intersect with already stored boxes for all covered time slots
  77                     // and move up the new one if needed
  78                     popped_up |= popupTogetherWith(box, *box_in_slot);
  79                 }
  80             }
  81         } while (popped_up);
  82
  83         // add current box to covered time slot
  84         for (int i_slot = box.start; i_slot <= box.finish; i_slot++)
  85             time_slots[i_slot].push_back(&box);
  86
  87         // store the max top bound for each box
  88         _min_required = std::max(_min_required, box.id + box.size);
  89         _offsets[id] = box.id;
  90     }
  91
  92     return _min_required;
  93 }
  94
  95 int MemorySolver::maxDepth() {
  96     if (_depth == -1) calcDepth();
  97     return _depth;
  98 }
  99
 100 int MemorySolver::maxTopDepth() {
 101     if (_top_depth == -1) calcDepth();
 102     return _top_depth;
 103 }
 104
 105 int MemorySolver::getOffset(int id) const {
 106     auto res = _offsets.find(id);
 107     if (res == _offsets.end()) THROW_IE_EXCEPTION << "There are no box for provided ID";
 108     return res->second;
 109 }
 110
 111 //======== Private =============//
 112
 113 void MemorySolver::calcDepth() {
 114     int top_depth = 0;
 115     int depth = 0;
 116     std::map<int, std::vector<const Box*>> release_at;
 117
 118     for (const Box& box : _boxes) {
 119         int time = box.start;
 120         depth += box.size;
 121         top_depth++;
 122
 123         release_at[box.finish+1].push_back(&box);
 124
 125         for (const Box *b : release_at[time]) {
 126             depth -= b->size;
 127             top_depth--;
 128         }
 129         release_at.erase(time);
 130         IE_ASSERT(top_depth > 0);
 131
 132         _top_depth = std::max(_top_depth, top_depth);
 133         _depth = std::max(_depth, depth);
 134     }
 135 }
 136
 137 }  // namespace InferenceEngine