1 //
2 // Copyright © 2021 Arm Ltd and Contributors. All rights reserved.
3 // SPDX-License-Identifier: MIT
4 //
5 
6 #include <unordered_map>
7 #include <iostream>
8 #include "StrategyValidator.hpp"
9 
10 namespace armnn
11 {
12 
Optimize(std::vector<MemBlock> & memBlocks)13 std::vector<MemBin> StrategyValidator::Optimize(std::vector<MemBlock>& memBlocks)
14 {
15     // Condition #1: All Memblocks have been assigned to a MemBin
16 
17     // Condition #2: No Memblock is assigned to multiple MemBins
18 
19     // Condition #3: No two Memblocks in a MemBin overlap in both the X and Y axis
20     //               Memblocks in a MemBin can overlap on the X axis for SingleAxisPacking
21     //               Memblocks in a MemBin can overlap on the Y axis or the X for MultiAxisPacking but not both
22 
23     std::unordered_map<unsigned int, bool> validationMap;
24 
25     for (auto memBlock : memBlocks)
26     {
27         validationMap[memBlock.m_Index] = false;
28     }
29 
30     auto memBinVect = m_Strategy->Optimize(memBlocks);
31 
32     // Compare each of the input memblocks against every assignedBlock in each bin
33     // if we get through all bins without finding a block return
34     // if at any stage the block is found twice return
35 
36     for (auto memBin : memBinVect)
37     {
38         for (auto block : memBin.m_MemBlocks)
39         {
40             try
41             {
42                 if (!validationMap.at(block.m_Index))
43                 {
44                     validationMap.at(block.m_Index) = true;
45                 }
46                 else
47                 {
48                     throw MemoryValidationException("Condition #2: Memblock is assigned to multiple MemBins");
49                 }
50             }
51             catch (const std::out_of_range&)
52             {
53                 throw MemoryValidationException("Unknown index ");
54             }
55         }
56     }
57 
58     for (auto memBlock : memBlocks)
59     {
60         if (!validationMap.at(memBlock.m_Index))
61         {
62             throw MemoryValidationException("Condition #1: Block not found in any bin");
63         }
64     }
65 
66     // Check for overlaps once we know blocks are all assigned and no duplicates
67     for (auto bin : memBinVect)
68     {
69         for (unsigned int i = 0; i < bin.m_MemBlocks.size(); ++i)
70         {
71             auto Block1 = bin.m_MemBlocks[i];
72             auto B1Left = Block1.m_Offset;
73             auto B1Right = Block1.m_Offset + Block1.m_MemSize;
74 
75             auto B1Top = Block1.m_StartOfLife;
76             auto B1Bottom = Block1.m_EndOfLife;
77 
78             // Only compare with blocks after the current one as previous have already been checked
79             for (unsigned int j = i + 1; j < bin.m_MemBlocks.size(); ++j)
80             {
81                 auto Block2 = bin.m_MemBlocks[j];
82                 auto B2Left = Block2.m_Offset;
83                 auto B2Right = Block2.m_Offset + Block2.m_MemSize;
84 
85                 auto B2Top = Block2.m_StartOfLife;
86                 auto B2Bottom = Block2.m_EndOfLife;
87 
88                 switch (m_Strategy->GetMemBlockStrategyType())
89                 {
90                     case (MemBlockStrategyType::SingleAxisPacking):
91                     {
92                         if (B1Top <= B2Bottom && B1Bottom >= B2Top)
93                         {
94                             throw MemoryValidationException("Condition #3: "
95                                         "invalid as two Memblocks overlap on the Y axis for SingleAxisPacking");
96 
97                         }
98                         break;
99                     }
100                     case (MemBlockStrategyType::MultiAxisPacking):
101                     {
102                         // If overlapping on both X and Y then invalid
103                         if (B1Left <= B2Right && B1Right >= B2Left &&
104                             B1Top <= B2Bottom && B1Bottom >= B2Top)
105                         {
106                             // Condition #3: two Memblocks overlap on both the X and Y axis
107                             throw MemoryValidationException("Condition #3: "
108                                                             "two Memblocks overlap on both the X and Y axis");
109                         }
110                         break;
111                     }
112                     default:
113                         throw MemoryValidationException("Unknown MemBlockStrategyType");
114                 }
115             }
116         }
117     }
118 
119     // None of the conditions broken so return true
120     return memBinVect;
121 }
122 
123 } // namespace armnn