NNXSW-1853 Change SubgraphViewSelector algorithm
authorRob Hughes <robert.hughes@arm.com>
Fri, 8 Nov 2019 15:50:10 +0000 (15:50 +0000)
committerDerek Lamberti <derek.lamberti@arm.com>
Fri, 15 Nov 2019 13:11:24 +0000 (13:11 +0000)
commit30db8ad8b15e5d0e94ae2ff64c246350885c4b6b
tree5643a27f8fa35e058aaf3656b4952d48e4645ee2
parent721b82f257afae0170a60ba355efceef6cff2355
NNXSW-1853 Change SubgraphViewSelector algorithm

The current algorithm in SubgraphViewSelector has a bug that can lead to
it producing subgraphs which have a dependency cycle (see the newly
added test case 'ValidMerge' for a repro). It also fails to merge
subgraphs in some cases where it could, which leads to smaller subgraphs.
In the case of FSRCNN, the NPU cannot support these smaller subgraphs and
so this is blocking us from supporting that network.

This commit changes the algorithm to fix the dependency bug and
also make it so that subgraphs are merged in the cases that were missed
before. It also adds some unit tests to cover cases that were problematic
before, and to extend coverage for the new algorithm.

The new algorithm has two downsides compared to the previous one:

1. Disjoint subgraphs are not merged. This can never lead to a failed
compilation by the NPU and so I believe this is less of an issue than
the previous algorithm's "missed merges". This could however lead to a
runtime performance loss in some cases as the NPU will be unable
to parallelise as many operations. There are some unit tests that cover
this which I have disabled.
2. The performance is worse. I have spent some time analysing this and
for a graph with ~1000 layers the new algorithm takes 20ms vs. the
old algorithm's 4ms (on my desktop PC). I believe the performance is
still within acceptable limits. I also compared inception V3 (which was
the network which caused performance issues with the original version of
the splitting algorithm) and this new algorithm has not regressed there
(200-300us in both cases).

Change-Id: I1dd64a779f272723621e04d203b5a2752a6af2ef
Signed-off-by: Robert Hughes <robert.hughes@arm.com>
src/armnn/SubgraphViewSelector.cpp
src/armnn/SubgraphViewSelector.hpp
src/armnn/test/SubgraphViewTests.cpp
src/backends/backendsCommon/test/OptimizeSubgraphViewTests.cpp