Performance improvement in tensor allocation
- Tensor allocation verification was O(N^2), is now closer to O(N)
- Removed a sort in HillClimb allocator
Change-Id: I286a269881490c485cc2b0eeab3b1ecffa8f3df0
Signed-off-by: Louis Verhaard <louis.verhaard@arm.com>
diff --git a/ethosu/vela/live_range.py b/ethosu/vela/live_range.py
index 0cc89e2..de001e5 100644
--- a/ethosu/vela/live_range.py
+++ b/ethosu/vela/live_range.py
@@ -16,6 +16,8 @@
# Description:
# Build a live range graph for tensors in one or more subgraphs. Used for tensor allocation as well as in the scheduler.
# Can work with either a pass packed subgraph or a scheduled subgraph.
+from typing import List
+
from .nn_graph import PassPlacement
from .operation import Op
from .tensor import MemType
@@ -99,6 +101,7 @@
class LiveRangeGraph:
def __init__(self):
+ self.lrs: List[LiveRange] = [] # List of all created ranges
self.ranges = {} # tens -> range
self.ignore_tensors = set()
self.processed_subgraphs = set()
@@ -114,6 +117,7 @@
# No live range found for the tensor, create a new one
rng = LiveRange(tens, alignment)
self.ranges[tens] = rng
+ self.lrs.append(rng)
return rng
def fuse_ranges(self, in_tens, out_tens):