IVGCVSW-6298 'IMemoryOptimizerStrategy Add declarations and constant layer strategy'

* Added IMemoryOptimizerStrategy interface
* Added ConstLayerMemoryOptimizer strategy

Signed-off-by: Sadik Armagan <sadik.armagan@arm.com>
Change-Id: I6a92e659379e5cc39c375b669678eee8a8c08c20

11 files changed, 241 insertions, 2 deletions

diff --git a/include/armnn/Types.hpp b/include/armnn/Types.hpp
index 19e93c3c7e..0b7b941008 100644
--- a/include/armnn/Types.hpp
+++ b/include/armnn/Types.hpp
@@ -213,6 +213,19 @@ enum class MemorySource : uint32_t
     DmaBufProtected = 4
 };
 
+enum class MemBlockStrategyType
+{
+    // MemBlocks can be packed on the Y axis only.
+    // In other words MemBlocks with overlapping lifetimes cannot use the same MemBin,
+    // equivalent to blob or pooling memory management.
+    SingleAxisPacking  = 0,
+
+    // MemBlocks can be packed on the Y and X axis.
+    // In other words MemBlocks with overlapping lifetimes can use the same MemBin,
+    // equivalent to offset or slab memory management.
+    MultiAxisPacking  = 1
+};
+
 /// Each backend should implement an IBackend.
 class IBackend
 {
diff --git a/include/armnn/backends/CMakeLists.txt b/include/armnn/backends/CMakeLists.txt
index 58d0abf872..19046ed977 100644
--- a/include/armnn/backends/CMakeLists.txt
+++ b/include/armnn/backends/CMakeLists.txt
@@ -10,6 +10,7 @@ list(APPEND armnnBackendsAPI_sources
      IBackendInternal.hpp
      IBackendContext.hpp
      IMemoryManager.hpp
+     IMemoryOptimizerStrategy.hpp
      ITensorHandle.hpp
      ITensorHandleFactory.hpp
      IWorkload.hpp
diff --git a/include/armnn/backends/IMemoryOptimizerStrategy.hpp b/include/armnn/backends/IMemoryOptimizerStrategy.hpp
new file mode 100644
index 0000000000..ec6d838aae
--- /dev/null
+++ b/include/armnn/backends/IMemoryOptimizerStrategy.hpp
@@ -0,0 +1,57 @@
+//
+// Copyright © 2021 Arm Ltd and Contributors. All rights reserved.
+// SPDX-License-Identifier: MIT
+//
+#pragma once
+
+#include <armnn/Types.hpp>
+
+namespace armnn
+{
+
+// A MemBlock represents a memory usage requirement in time and space and can be seen as essentially a rectangle
+struct MemBlock
+{
+    MemBlock(const unsigned int startOfLife,
+             const unsigned int endOfLife,
+             const size_t memSize,
+             size_t offset,
+             const unsigned int index)
+    : m_StartOfLife(startOfLife), m_EndOfLife(endOfLife), m_MemSize(memSize), m_Offset(offset), m_Index(index) {}
+
+    const unsigned int m_StartOfLife; // Y start
+    const unsigned int m_EndOfLife; // Y end
+
+    const size_t m_MemSize; // X start
+    size_t m_Offset; // X end
+
+    const unsigned int m_Index; // Index to keep order
+};
+
+// A MemBin represents a single contiguous area of memory that can store 1-n number of MemBlocks
+struct MemBin
+{
+    std::vector<MemBlock> m_MemBlocks;
+    size_t m_MemSize;
+};
+
+// IMemoryOptimizerStrategy will set m_Offset of the MemBlocks,
+// sort them into 1-n bins, then pair each bin of MemBlocks with an int specifying it's total size
+// A IMemoryOptimizerStrategy must ensure that
+// 1: All MemBlocks have been assigned to a MemBin
+// 2: No MemBlock is assigned to multiple MemBins
+// 3: No two MemBlocks in a MemBin overlap in the X dimension
+//    (a strategy cannot change the y axis or length of a MemBlock)
+class IMemoryOptimizerStrategy
+{
+public:
+    virtual ~IMemoryOptimizerStrategy() {}
+
+    virtual std::string GetName() const = 0;
+
+    virtual MemBlockStrategyType GetMemBlockStrategyType() const = 0;
+
+    virtual std::vector<MemBin> Optimize(std::vector<MemBlock>& memBlocks) = 0;
+};
+
+} // namespace armnn
\ No newline at end of file
diff --git a/src/backends/backendsCommon/CMakeLists.txt b/src/backends/backendsCommon/CMakeLists.txt
index 2b48532961..129cdbe9f1 100644
--- a/src/backends/backendsCommon/CMakeLists.txt
+++ b/src/backends/backendsCommon/CMakeLists.txt
@@ -47,6 +47,8 @@ list(APPEND armnnBackendsCommon_sources
     WorkloadUtils.hpp
 )
 
+add_subdirectory(memoryOptimizationStrategies)
+
 if(BUILD_UNIT_TESTS)
     add_subdirectory(test)
 endif()
diff --git a/src/backends/backendsCommon/common.cmake b/src/backends/backendsCommon/common.cmake
index 347d60254b..d5973be89f 100644
--- a/src/backends/backendsCommon/common.cmake
+++ b/src/backends/backendsCommon/common.cmake
@@ -5,4 +5,6 @@
 
 add_subdirectory(${PROJECT_SOURCE_DIR}/src/backends/backendsCommon)
 list(APPEND armnnLibraries armnnBackendsCommon)
+list(APPEND armnnLibraries armnnMemoryOptimizationStrategies)
 list(APPEND armnnUnitTestLibraries armnnBackendsCommonUnitTests)
+list(APPEND armnnUnitTestLibraries armnnMemoryOptimizationStrategiesUnitTests)
\ No newline at end of file
diff --git a/src/backends/backendsCommon/common.mk b/src/backends/backendsCommon/common.mk
index 47ceffe37d..7ebc9975c3 100644
--- a/src/backends/backendsCommon/common.mk
+++ b/src/backends/backendsCommon/common.mk
@@ -23,7 +23,8 @@ COMMON_SOURCES := \
     UnmapWorkload.cpp \
     WorkloadData.cpp \
     WorkloadFactory.cpp \
-    WorkloadUtils.cpp
+    WorkloadUtils.cpp \
+    memoryOptimizationStrategies/ConstLayerMemoryOptimizerStrategy.cpp
 
 # COMMON_TEST_SOURCES contains the list of files to be included
 # in the Android unit test build (armnn-tests) and it is picked
@@ -95,7 +96,8 @@ COMMON_TEST_SOURCES := \
     test/layerTests/StridedSliceTestImpl.cpp \
     test/layerTests/SubtractionTestImpl.cpp \
     test/layerTests/TransposeConvolution2dTestImpl.cpp \
-    test/layerTests/UnidirectionalSequenceLstmTestImpl.cpp
+    test/layerTests/UnidirectionalSequenceLstmTestImpl.cpp \
+    memoryOptimizationStrategies/test/ConstLayerMemoryOptimizerStrategyTests.cpp
 
 ifeq ($(ARMNN_REF_ENABLED),1)
 COMMON_TEST_SOURCES += \
diff --git a/src/backends/backendsCommon/memoryOptimizationStrategies/CMakeLists.txt b/src/backends/backendsCommon/memoryOptimizationStrategies/CMakeLists.txt
new file mode 100644
index 0000000000..6f3708beaa
--- /dev/null
+++ b/src/backends/backendsCommon/memoryOptimizationStrategies/CMakeLists.txt
@@ -0,0 +1,21 @@
+#
+# Copyright © 2021 Arm Ltd and Contributors. All rights reserved.
+# SPDX-License-Identifier: MIT
+#
+
+list(APPEND armnnMemoryOptimizationStrategies_sources
+     ConstLayerMemoryOptimizerStrategy.hpp
+     ConstLayerMemoryOptimizerStrategy.cpp
+)
+
+if(BUILD_UNIT_TESTS)
+    add_subdirectory(test)
+endif()
+
+add_library(armnnMemoryOptimizationStrategies OBJECT ${armnnMemoryOptimizationStrategies_sources})
+target_include_directories(armnnMemoryOptimizationStrategies PRIVATE ${PROJECT_SOURCE_DIR}/include/armnn)
+target_include_directories(armnnMemoryOptimizationStrategies PRIVATE ${PROJECT_SOURCE_DIR}/src/armnn)
+target_include_directories(armnnMemoryOptimizationStrategies PRIVATE ${PROJECT_SOURCE_DIR}/src/armnnUtils)
+target_include_directories(armnnMemoryOptimizationStrategies PRIVATE ${PROJECT_SOURCE_DIR}/src/backends)
+target_include_directories(armnnMemoryOptimizationStrategies PRIVATE ${PROJECT_SOURCE_DIR}/src/profiling)
+target_include_directories(armnnMemoryOptimizationStrategies PRIVATE ${PROJECT_SOURCE_DIR}/profiling/common/include)
\ No newline at end of file
diff --git a/src/backends/backendsCommon/memoryOptimizationStrategies/ConstLayerMemoryOptimizerStrategy.cpp b/src/backends/backendsCommon/memoryOptimizationStrategies/ConstLayerMemoryOptimizerStrategy.cpp
new file mode 100644
index 0000000000..8abf32c096
--- /dev/null
+++ b/src/backends/backendsCommon/memoryOptimizationStrategies/ConstLayerMemoryOptimizerStrategy.cpp
@@ -0,0 +1,43 @@
+//
+// Copyright © 2021 Arm Ltd and Contributors. All rights reserved.
+// SPDX-License-Identifier: MIT
+//
+
+#include "ConstLayerMemoryOptimizerStrategy.hpp"
+
+namespace armnn
+{
+
+std::string ConstLayerMemoryOptimizerStrategy::GetName() const
+{
+    return m_Name;
+}
+
+MemBlockStrategyType ConstLayerMemoryOptimizerStrategy::GetMemBlockStrategyType() const
+{
+    return m_MemBlockStrategyType;
+}
+
+// A IMemoryOptimizerStrategy must ensure that
+// 1: All MemBlocks have been assigned to a MemBin
+// 2: No MemBlock is assigned to multiple MemBins
+// 3: No two MemBlocks in a MemBin overlap in the X dimension
+std::vector<MemBin> ConstLayerMemoryOptimizerStrategy::Optimize(std::vector<MemBlock>& memBlocks)
+{
+    std::vector<MemBin> memBins;
+    memBins.reserve(memBlocks.size());
+
+    for (auto& memBlock : memBlocks)
+    {
+        MemBin memBin;
+        memBin.m_MemSize = memBlock.m_MemSize;
+        memBin.m_MemBlocks.reserve(1);
+        memBlock.m_Offset = 0;
+        memBin.m_MemBlocks.push_back(memBlock);
+        memBins.push_back(memBin);
+    }
+
+    return memBins;
+}
+
+} // namespace armnn
\ No newline at end of file
diff --git a/src/backends/backendsCommon/memoryOptimizationStrategies/ConstLayerMemoryOptimizerStrategy.hpp b/src/backends/backendsCommon/memoryOptimizationStrategies/ConstLayerMemoryOptimizerStrategy.hpp
new file mode 100644
index 0000000000..3f803abe87
--- /dev/null
+++ b/src/backends/backendsCommon/memoryOptimizationStrategies/ConstLayerMemoryOptimizerStrategy.hpp
@@ -0,0 +1,31 @@
+//
+// Copyright © 2021 Arm Ltd and Contributors. All rights reserved.
+// SPDX-License-Identifier: MIT
+//
+#pragma once
+
+#include <armnn/Types.hpp>
+#include <armnn/backends/IMemoryOptimizerStrategy.hpp>
+
+namespace armnn
+{
+// ConstLayerMemoryOptimizer: Create a unique MemBin for each MemBlock and assign it an offset of 0
+class ConstLayerMemoryOptimizerStrategy : public IMemoryOptimizerStrategy
+{
+public:
+    ConstLayerMemoryOptimizerStrategy()
+    : m_Name(std::string("ConstLayerMemoryOptimizerStrategy"))
+    , m_MemBlockStrategyType(MemBlockStrategyType::SingleAxisPacking) {}
+
+    std::string GetName() const override;
+
+    MemBlockStrategyType GetMemBlockStrategyType() const override;
+
+    std::vector<MemBin> Optimize(std::vector<MemBlock>& memBlocks) override;
+
+private:
+    std::string m_Name;
+    MemBlockStrategyType m_MemBlockStrategyType;
+};
+
+} // namespace armnn
\ No newline at end of file
diff --git a/src/backends/backendsCommon/memoryOptimizationStrategies/test/CMakeLists.txt b/src/backends/backendsCommon/memoryOptimizationStrategies/test/CMakeLists.txt
new file mode 100644
index 0000000000..5b2489d2e9
--- /dev/null
+++ b/src/backends/backendsCommon/memoryOptimizationStrategies/test/CMakeLists.txt
@@ -0,0 +1,16 @@
+#
+# Copyright © 2021 Arm Ltd and Contributors. All rights reserved.
+# SPDX-License-Identifier: MIT
+#
+
+list(APPEND armnnMemoryOptimizationStrategiesUnitTests_sources
+     ConstLayerMemoryOptimizerStrategyTests.cpp
+)
+
+add_library(armnnMemoryOptimizationStrategiesUnitTests OBJECT ${armnnMemoryOptimizationStrategiesUnitTests_sources})
+target_include_directories(armnnMemoryOptimizationStrategiesUnitTests PRIVATE ${PROJECT_SOURCE_DIR}/src/armnn)
+target_include_directories(armnnMemoryOptimizationStrategiesUnitTests PRIVATE ${PROJECT_SOURCE_DIR}/src/armnnUtils)
+target_include_directories(armnnMemoryOptimizationStrategiesUnitTests PRIVATE ${PROJECT_SOURCE_DIR}/src/backends)
+target_include_directories(armnnMemoryOptimizationStrategiesUnitTests PRIVATE ${PROJECT_SOURCE_DIR}/src/profiling)
+target_include_directories(armnnMemoryOptimizationStrategiesUnitTests PRIVATE ${PROJECT_SOURCE_DIR}/profiling/common/include)
+target_include_directories(armnnMemoryOptimizationStrategiesUnitTests PRIVATE ${PROJECT_SOURCE_DIR}/third-party)
diff --git a/src/backends/backendsCommon/memoryOptimizationStrategies/test/ConstLayerMemoryOptimizerStrategyTests.cpp b/src/backends/backendsCommon/memoryOptimizationStrategies/test/ConstLayerMemoryOptimizerStrategyTests.cpp
new file mode 100644
index 0000000000..95569dcc0a
--- /dev/null
+++ b/src/backends/backendsCommon/memoryOptimizationStrategies/test/ConstLayerMemoryOptimizerStrategyTests.cpp
@@ -0,0 +1,51 @@
+//
+// Copyright © 2021 Arm Ltd and Contributors. All rights reserved.
+// SPDX-License-Identifier: MIT
+//
+
+#include <backendsCommon/memoryOptimizationStrategies/ConstLayerMemoryOptimizerStrategy.hpp>
+
+#include <doctest/doctest.h>
+#include <vector>
+
+using namespace armnn;
+
+TEST_SUITE("ConstLayerMemoryOptimizerStrategyTestSuite")
+{
+
+TEST_CASE("ConstLayerMemoryOptimizerStrategyTest")
+{
+    // create a few memory blocks
+    MemBlock memBlock0(0, 2, 20, 0, 0);
+    MemBlock memBlock1(2, 3, 10, 20, 1);
+    MemBlock memBlock2(3, 5, 15, 30, 2);
+    MemBlock memBlock3(5, 6, 20, 50, 3);
+    MemBlock memBlock4(7, 8, 5, 70, 4);
+
+    std::vector<MemBlock> memBlocks;
+    memBlocks.reserve(5);
+    memBlocks.push_back(memBlock0);
+    memBlocks.push_back(memBlock1);
+    memBlocks.push_back(memBlock2);
+    memBlocks.push_back(memBlock3);
+    memBlocks.push_back(memBlock4);
+
+    // Optimize the memory blocks with ConstLayerMemoryOptimizerStrategy
+    ConstLayerMemoryOptimizerStrategy constLayerMemoryOptimizerStrategy;
+    CHECK_EQ(constLayerMemoryOptimizerStrategy.GetName(), std::string("ConstLayerMemoryOptimizerStrategy"));
+    CHECK_EQ(constLayerMemoryOptimizerStrategy.GetMemBlockStrategyType(), MemBlockStrategyType::SingleAxisPacking);
+    auto memBins = constLayerMemoryOptimizerStrategy.Optimize(memBlocks);
+    CHECK(memBins.size() == 5);
+
+    CHECK(memBins[1].m_MemBlocks.size() == 1);
+    CHECK(memBins[1].m_MemBlocks[0].m_Offset == 0);
+    CHECK(memBins[1].m_MemBlocks[0].m_MemSize == 10);
+    CHECK(memBins[1].m_MemBlocks[0].m_Index == 1);
+
+    CHECK(memBins[4].m_MemBlocks.size() == 1);
+    CHECK(memBins[4].m_MemBlocks[0].m_Offset == 0);
+    CHECK(memBins[4].m_MemBlocks[0].m_MemSize == 5);
+    CHECK(memBins[4].m_MemBlocks[0].m_Index == 4);
+}
+
+}