Francis Murtagh | ca49a24 | 2021-09-28 15:30:31 +0100 | [diff] [blame] | 1 | // |
| 2 | // Copyright © 2021 Arm Ltd and Contributors. All rights reserved. |
| 3 | // SPDX-License-Identifier: MIT |
| 4 | // |
| 5 | |
Jim Flynn | e1fdd28 | 2021-10-26 21:26:10 +0100 | [diff] [blame] | 6 | #include <unordered_map> |
| 7 | #include <iostream> |
| 8 | #include "StrategyValidator.hpp" |
Francis Murtagh | ca49a24 | 2021-09-28 15:30:31 +0100 | [diff] [blame] | 9 | |
| 10 | namespace armnn |
| 11 | { |
| 12 | |
Jim Flynn | e1fdd28 | 2021-10-26 21:26:10 +0100 | [diff] [blame] | 13 | std::vector<MemBin> StrategyValidator::Optimize(std::vector<MemBlock>& memBlocks) |
Francis Murtagh | ca49a24 | 2021-09-28 15:30:31 +0100 | [diff] [blame] | 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 | |
Jim Flynn | e1fdd28 | 2021-10-26 21:26:10 +0100 | [diff] [blame] | 23 | std::unordered_map<unsigned int, bool> validationMap; |
| 24 | |
| 25 | for (auto memBlock : memBlocks) |
| 26 | { |
| 27 | validationMap[memBlock.m_Index] = false; |
| 28 | } |
| 29 | |
Francis Murtagh | ca49a24 | 2021-09-28 15:30:31 +0100 | [diff] [blame] | 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 | |
Jim Flynn | e1fdd28 | 2021-10-26 21:26:10 +0100 | [diff] [blame] | 36 | for (auto memBin : memBinVect) |
Francis Murtagh | ca49a24 | 2021-09-28 15:30:31 +0100 | [diff] [blame] | 37 | { |
Jim Flynn | e1fdd28 | 2021-10-26 21:26:10 +0100 | [diff] [blame] | 38 | for (auto block : memBin.m_MemBlocks) |
Francis Murtagh | ca49a24 | 2021-09-28 15:30:31 +0100 | [diff] [blame] | 39 | { |
Jim Flynn | e1fdd28 | 2021-10-26 21:26:10 +0100 | [diff] [blame] | 40 | try |
Francis Murtagh | ca49a24 | 2021-09-28 15:30:31 +0100 | [diff] [blame] | 41 | { |
Jim Flynn | e1fdd28 | 2021-10-26 21:26:10 +0100 | [diff] [blame] | 42 | if (!validationMap.at(block.m_Index)) |
Francis Murtagh | ca49a24 | 2021-09-28 15:30:31 +0100 | [diff] [blame] | 43 | { |
Jim Flynn | e1fdd28 | 2021-10-26 21:26:10 +0100 | [diff] [blame] | 44 | validationMap.at(block.m_Index) = true; |
| 45 | } |
| 46 | else |
| 47 | { |
| 48 | throw MemoryValidationException("Condition #2: Memblock is assigned to multiple MemBins"); |
Francis Murtagh | ca49a24 | 2021-09-28 15:30:31 +0100 | [diff] [blame] | 49 | } |
| 50 | } |
Jim Flynn | e1fdd28 | 2021-10-26 21:26:10 +0100 | [diff] [blame] | 51 | catch (const std::out_of_range&) |
| 52 | { |
| 53 | throw MemoryValidationException("Unknown index "); |
| 54 | } |
Francis Murtagh | ca49a24 | 2021-09-28 15:30:31 +0100 | [diff] [blame] | 55 | } |
Jim Flynn | e1fdd28 | 2021-10-26 21:26:10 +0100 | [diff] [blame] | 56 | } |
| 57 | |
| 58 | for (auto memBlock : memBlocks) |
| 59 | { |
| 60 | if (!validationMap.at(memBlock.m_Index)) |
Francis Murtagh | ca49a24 | 2021-09-28 15:30:31 +0100 | [diff] [blame] | 61 | { |
Jim Flynn | e1fdd28 | 2021-10-26 21:26:10 +0100 | [diff] [blame] | 62 | throw MemoryValidationException("Condition #1: Block not found in any bin"); |
Francis Murtagh | ca49a24 | 2021-09-28 15:30:31 +0100 | [diff] [blame] | 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 assignedBlock = bin.m_MemBlocks[i]; |
| 72 | auto xStart = assignedBlock.m_Offset; |
| 73 | auto xEnd = assignedBlock.m_Offset + assignedBlock.m_MemSize; |
| 74 | |
| 75 | auto yStart = assignedBlock.m_StartOfLife; |
| 76 | auto yEnd = assignedBlock.m_EndOfLife; |
| 77 | auto assignedIndex = assignedBlock.m_Index; |
| 78 | |
| 79 | // Only compare with blocks after the current one as previous have already been checked |
| 80 | for (unsigned int j = i + 1; j < bin.m_MemBlocks.size(); ++j) |
| 81 | { |
| 82 | auto otherAssignedBlock = bin.m_MemBlocks[j]; |
| 83 | auto xStartAssigned = otherAssignedBlock.m_Offset; |
| 84 | auto xEndAssigned = otherAssignedBlock.m_Offset + otherAssignedBlock.m_MemSize; |
| 85 | |
| 86 | auto yStartAssigned = otherAssignedBlock.m_StartOfLife; |
| 87 | auto yEndAssigned = otherAssignedBlock.m_EndOfLife; |
| 88 | auto otherIndex = otherAssignedBlock.m_Index; |
| 89 | |
| 90 | // If overlapping on both X and Y then invalid |
| 91 | // Inside left of rectangle & Inside right of rectangle |
| 92 | if ((((xStart >= xStartAssigned) && (xEnd <= xEndAssigned)) && |
| 93 | // Inside bottom of rectangle & Inside top of rectangle |
| 94 | ((yStart >= yStartAssigned) && (yEnd <= yEndAssigned))) && |
| 95 | // Cant overlap with itself |
| 96 | (assignedIndex != otherIndex)) |
| 97 | { |
| 98 | // Condition #3: two Memblocks overlap on both the X and Y axis |
Jim Flynn | e1fdd28 | 2021-10-26 21:26:10 +0100 | [diff] [blame] | 99 | throw MemoryValidationException("Condition #3: two Memblocks overlap on both the X and Y axis"); |
Francis Murtagh | ca49a24 | 2021-09-28 15:30:31 +0100 | [diff] [blame] | 100 | } |
| 101 | |
| 102 | switch (m_Strategy->GetMemBlockStrategyType()) |
| 103 | { |
| 104 | case (MemBlockStrategyType::SingleAxisPacking): |
| 105 | { |
| 106 | // Inside bottom of rectangle & Inside top of rectangle |
| 107 | if (((yStart >= yStartAssigned) && (yEnd <= yEndAssigned)) && |
| 108 | // Cant overlap with itself |
| 109 | (assignedIndex != otherIndex)) |
| 110 | { |
Jim Flynn | e1fdd28 | 2021-10-26 21:26:10 +0100 | [diff] [blame] | 111 | throw MemoryValidationException("Condition #3: " |
| 112 | "invalid as two Memblocks overlap on the Y axis for SingleAxisPacking"); |
| 113 | |
Francis Murtagh | ca49a24 | 2021-09-28 15:30:31 +0100 | [diff] [blame] | 114 | } |
| 115 | break; |
| 116 | } |
| 117 | case (MemBlockStrategyType::MultiAxisPacking): |
| 118 | { |
| 119 | break; |
| 120 | } |
| 121 | default: |
Jim Flynn | e1fdd28 | 2021-10-26 21:26:10 +0100 | [diff] [blame] | 122 | throw MemoryValidationException("Unknown MemBlockStrategyType"); |
Francis Murtagh | ca49a24 | 2021-09-28 15:30:31 +0100 | [diff] [blame] | 123 | } |
| 124 | } |
Francis Murtagh | ca49a24 | 2021-09-28 15:30:31 +0100 | [diff] [blame] | 125 | } |
| 126 | } |
| 127 | |
| 128 | // None of the conditions broken so return true |
Jim Flynn | e1fdd28 | 2021-10-26 21:26:10 +0100 | [diff] [blame] | 129 | return memBinVect; |
Francis Murtagh | ca49a24 | 2021-09-28 15:30:31 +0100 | [diff] [blame] | 130 | } |
| 131 | |
| 132 | } // namespace armnn |