inference-engine/tests/unit/mem_solver/mem_solver_test.cpp

   1 // Copyright (C) 2018 Intel Corporation
   2 //
   3 // SPDX-License-Identifier: Apache-2.0
   4 //
   5
   6 #include <gtest/gtest.h>
   7
   8 #include "memory_solver.hpp"
   9 #include "details/ie_exception.hpp"
  10
  11 using namespace testing;
  12 using namespace InferenceEngine;
  13 using Box = InferenceEngine::MemorySolver::Box;
  14
  15 TEST(MemSolverTest, LinearAndEven) {
  16     int n = 0;
  17     std::vector<Box> boxes {  //  |
  18             {n, ++n, 2},      //  |      ____
  19             {n, ++n, 2},      //  |   __|____|__
  20             {n, ++n, 2},      //  |__|____||____|__
  21     };                        //      0  1  2  3
  22
  23     MemorySolver ms(boxes);
  24     EXPECT_EQ(ms.solve(), 4);
  25     EXPECT_EQ(ms.maxDepth(), 4);
  26     EXPECT_EQ(ms.maxTopDepth(), 2);
  27 }
  28
  29 TEST(MemSolverTest, LinearAndNotEven) {
  30     int n = 0;
  31     std::vector<Box> boxes {  //  |      ____
  32             {n, ++n, 2},      //  |     |____|__
  33             {n, ++n, 2},      //  |   ____ |    |
  34             {n, ++n, 3},      //  |__|____||____|__
  35     };                        //      0  1  2  3
  36
  37     MemorySolver ms(boxes);
  38     EXPECT_EQ(ms.solve(), 5);
  39     EXPECT_EQ(ms.maxDepth(), 5);
  40     EXPECT_EQ(ms.maxTopDepth(), 2);
  41 }
  42
  43
  44 TEST(MemSolverTest, LinearWithEmptyExecIndexes) {
  45     int n = 2;
  46     std::vector<Box> boxes {   //  |         _______
  47             {n, n+=2, 2},      //  |        |_______|_____
  48             {n, n+=2, 2},      //  |   _______    |       |
  49             {n, n+=2, 3},      //  |__|_______|___|_______|__
  50     };                         //      2  3  4  5  6  7  8
  51
  52     MemorySolver ms(boxes);
  53     EXPECT_EQ(ms.solve(), 5);
  54     EXPECT_EQ(ms.maxDepth(), 5);
  55     EXPECT_EQ(ms.maxTopDepth(), 2);
  56 }
  57
  58 TEST(MemSolverTest, DISABLED_Unefficiency) {
  59
  60     std::vector<Box> boxes{    //  |            __________
  61             {6, 7, 3},         //  |   ____    |_3________|
  62             {2, 5, 2},         //  |  |_4__|_____ |    |
  63             {5, 8, 2},         //  |__|_2________||_1__|___
  64             {2, 3, 2},         //      2  3  4  5  6  7  8
  65     };
  66
  67     MemorySolver ms(boxes);
  68     EXPECT_EQ(ms.solve(), 5); // currently we have answer 6
  69     EXPECT_EQ(ms.maxDepth(), 5);
  70     EXPECT_EQ(ms.maxTopDepth(), 2);
  71 }
  72
  73 TEST(MemSolverTest, OverlappingBoxes) {
  74
  75     std::vector<Box> boxes{    //  |            __________
  76             {6, 7, 4},         //  |   ____    |_3________|
  77             {2, 5, 3},         //  |  |_4__|_____ |    |
  78             {5, 8, 2},         //  |__|_2________||_1__|___
  79             {2, 3, 2},         //      2  3  4  5  6  7  8
  80     };
  81
  82     MemorySolver ms(boxes);
  83     EXPECT_EQ(ms.solve(), 6);
  84     EXPECT_EQ(ms.maxDepth(), 6);
  85     EXPECT_EQ(ms.maxTopDepth(), 2);
  86 }
  87
  88 TEST(MemSolverTest, EndOnSeveralBegins) {
  89
  90     std::vector<Box> boxes {   //  |      ____
  91             {0, 1, 2},         //  |     |____| ____
  92             {1, 2, 2},         //  |           |____|__
  93             {3, 3, 2},         //  |   ____    |_______|
  94             {3, 5, 2},         //  |__|____|___|_|_________
  95             {3, 4, 2},         //      0  1  2  3  4  5  6
  96     };
  97
  98     MemorySolver ms(boxes);
  99     EXPECT_EQ(ms.solve(), 6);
 100     EXPECT_EQ(ms.maxDepth(), 6);
 101     EXPECT_EQ(ms.maxTopDepth(), 3);
 102 }
 103
 104 TEST(MemSolverTest, ToEndBoxes) {
 105
 106     std::vector<Box> boxes {   //  |      _____________
 107             {0, 1, 2},         //  |     |_____________>>
 108             {1,-1, 2},         //  |           |____|__
 109             {3, 3, 2},         //  |   ____    |_______>>
 110             {3,-1, 2},         //  |__|____|___|_|_________
 111             {3, 4, 2},         //      0  1  2  3  4  5  6
 112     };
 113
 114     MemorySolver ms(boxes);
 115     EXPECT_EQ(ms.solve(), 8);
 116     EXPECT_EQ(ms.maxDepth(), 8);
 117     EXPECT_EQ(ms.maxTopDepth(), 4);
 118 }
 119
 120 TEST(MemSolverTest, LastAndToEndBox) {
 121
 122     std::vector<Box> boxes {   //  |                     _
 123             {0, 1, 2},         //  |            ____    |_>>
 124             {6,-1, 2},         //  |           |____|__
 125             {3, 3, 2},         //  |   ____    |_______|
 126             {3, 5, 2},         //  |__|____|___|_|_________
 127             {3, 4, 2},         //      0  1  2  3  4  5  6
 128     };
 129
 130     MemorySolver ms(boxes);
 131     EXPECT_EQ(ms.solve(), 6);
 132     EXPECT_EQ(ms.maxDepth(), 6);
 133     EXPECT_EQ(ms.maxTopDepth(), 3);
 134 }
 135
 136 TEST(MemSolverTest, OptimalAlexnet) {
 137     std::vector<std::vector<int>> shapes {
 138             {3,227,227},  // in
 139             {96 ,55,55},  // conv1
 140             {96 ,55,55},  // relu1
 141             {96 ,55,55},  // norm1
 142             {96 ,27,27},  // pool1
 143             {256,27,27},  // conv2
 144             {256,27,27},  // relu2
 145             {256,27,27},  // norm2
 146             {256,13,13},  // pool2
 147             {384,13,13},  // conv3
 148             {384,13,13},  // relu3
 149             {384,13,13},  // conv4
 150             {384,13,13},  // relu4
 151             {256,13,13},  // conv5
 152             {256,13,13},  // relu5
 153             {256, 6, 6},  // pool5
 154             {1,1 ,4069},  // fc6
 155             {1,1 ,4069},  // relu6
 156             {1,1 ,4069},  // fc7
 157             {1,1 ,4069},  // relu7
 158             {1,1 ,1000},  // fc8
 159             {1,1 ,1000},  // loss
 160     };
 161
 162     int n = 0;
 163     std::vector<Box> boxes;
 164     for (const auto &sh : shapes) boxes.push_back( {n, ++n, sh[0]*sh[1]*sh[2]} );
 165
 166     // For linear topology bottom score is reachable minRequired == maxDepth
 167     MemorySolver ms(boxes);
 168     EXPECT_EQ(ms.solve(), ms.maxDepth());
 169     EXPECT_EQ(ms.maxTopDepth(), 2);
 170 }
 171
 172 TEST(MemSolverTest, GetOffsets) {
 173     int n = 0;
 174     std::vector<Box> boxes{   //  |
 175             {n, ++n, 2, 0},   //  |      ____  ____
 176             {n, ++n, 2, 1},   //  |   __|____||____|
 177             {n, ++n, 2, 2},   //  |__|____||____|_____
 178             {n, ++n, 2, 3},   //      0  1  2  3  4
 179     };
 180
 181     MemorySolver ms(boxes);
 182     ms.solve();
 183
 184     //  The correct answer is [0, 2, 0, 2] or [2, 0, 2, 0].
 185     EXPECT_EQ(ms.getOffset(0) + ms.getOffset(1), 2);
 186     EXPECT_EQ(ms.getOffset(1) + ms.getOffset(2), 2);
 187     EXPECT_EQ(ms.getOffset(2) + ms.getOffset(3), 2);
 188 }
 189
 190 TEST(MemSolverTest, GetOffsetThows) {
 191     int n = 0, id = 0;
 192     std::vector<Box> boxes{      //  |
 193             {n, ++n, 2, id++},   //  |      ____  ____
 194             {n, ++n, 2, id++},   //  |   __|____||____|
 195             {n, ++n, 2, id++},   //  |__|____||____|_____
 196             {n, ++n, 2, id++},   //      0  1  2  3  4
 197     };
 198
 199     MemorySolver ms(boxes);
 200     ms.solve();
 201
 202     EXPECT_THROW(ms.getOffset(100), details::InferenceEngineException);
 203 }
 204
 205 TEST(MemSolverTest, NoOverlapping) {
 206
 207     int n = 0;                //  |         _____________
 208     std::vector<Box> boxes{   //  |   _____|___1_________|
 209             {4, 8, 1, n++},   //  |  |_2_____|    ____
 210             {6, 7, 3, n++},   //  |  |    |      |    |
 211             {2, 3, 3, n++},   //  |__|_3__|______|_3__|___
 212             {2, 4, 2, n++},   //      2  3  4  5  6  7  8
 213     };
 214
 215     MemorySolver ms(boxes);
 216     ms.solve();
 217     // TODO: Current algorithm doesn't solve that case. Uncomment check to see inefficiency
 218     // EXPECT_EQ(ms.solve(), 5);
 219
 220     auto no_overlap = [&](Box box1, Box box2) -> bool {
 221         int off1 = ms.getOffset(box1.id);
 222         int off2 = ms.getOffset(box2.id);
 223         return box1.finish < box2.start || box1.start > box2.finish ||
 224                off1 + box1.size <= off2 || off1 >= off2 + box2.size;
 225     };
 226
 227     for (int i = 0; i < n; i++)
 228     for (int j = i+1; j < n; j++)
 229         ASSERT_TRUE(no_overlap(boxes[i], boxes[j])) << "Box overlapping is detected";
 230 }
 231
 232 TEST(MemSolverTest, BestSolution1) {
 233
 234     int n = 0;                //  |         _______
 235     std::vector<Box> boxes{   //  |        |_2_____|__
 236             {2, 3, 1, n++},   //  |      ____    |    |
 237             {3, 4, 1, n++},   //  |   __|_1__|   |    |
 238             {4, 6, 2, n++},   //  |__|_1__|______|_3__|___
 239             {6, 7, 3, n++},   //      2  3  4  5  6  7  8
 240     };
 241
 242     MemorySolver ms(boxes);
 243     EXPECT_EQ(ms.solve(), 5);
 244
 245     auto no_overlap = [&](Box box1, Box box2) -> bool {
 246         int off1 = ms.getOffset(box1.id);
 247         int off2 = ms.getOffset(box2.id);
 248         return box1.finish < box2.start || box1.start > box2.finish ||
 249                off1 + box1.size <= off2 || off1 >= off2 + box2.size;
 250     };
 251
 252     for (int i = 0; i < n; i++)
 253         for (int j = i+1; j < n; j++)
 254             ASSERT_TRUE(no_overlap(boxes[i], boxes[j])) << "Box overlapping is detected";
 255 }
 256