inference-engine/src/inference_engine/memory_solver.cpp

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