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

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