tree 5643a27f8fa35e058aaf3656b4952d48e4645ee2
parent 721b82f257afae0170a60ba355efceef6cff2355
author Rob Hughes <robert.hughes@arm.com> 1573228210 +0000
committer Derek Lamberti <derek.lamberti@arm.com> 1573823484 +0000

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>