| # SPDX-FileCopyrightText: Copyright 2020-2023 Arm Limited and/or its affiliates <open-source-office@arm.com> |
| # |
| # SPDX-License-Identifier: Apache-2.0 |
| # |
| # Licensed under the Apache License, Version 2.0 (the License); you may |
| # not use this file except in compliance with the License. |
| # You may obtain a copy of the License at |
| # |
| # www.apache.org/licenses/LICENSE-2.0 |
| # |
| # Unless required by applicable law or agreed to in writing, software |
| # distributed under the License is distributed on an AS IS BASIS, WITHOUT |
| # WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| # See the License for the specific language governing permissions and |
| # limitations under the License. |
| # |
| # Description: |
| # The scheduler creates and searches for an optimal plan for the network, selecting block configurations and |
| # subdivisions for the Operators |
| # For Class name forward references for the type annotations. (see PEP 563). |
| from __future__ import annotations |
| |
| import copy |
| from collections import namedtuple |
| from enum import auto |
| from enum import IntEnum |
| from typing import Any |
| from typing import Dict |
| from typing import List |
| from typing import Optional |
| from typing import Tuple |
| from typing import TYPE_CHECKING |
| |
| # Import needed for Type annotations. Only import for Type checking to avoid run-time errors due to cyclic import. |
| if TYPE_CHECKING: |
| from .npu_performance import CycleCost |
| |
| import numpy as np |
| |
| from . import live_range |
| from . import npu_performance |
| from . import tensor_allocation |
| from . import weight_compressor |
| from .architecture_allocator import ArchitectureBlockConfig |
| from .architecture_allocator import find_block_config |
| from .architecture_allocator import get_ifm_area_required |
| from .architecture_allocator import to_upscale |
| from .architecture_allocator import is_nearest |
| from .architecture_features import ArchitectureFeatures |
| from .architecture_features import Block |
| from .cascade_builder import CascadeBuilder |
| from .cascade_builder import CascadeInfo |
| from .data_type import DataType |
| from .nn_graph import CascadedPass |
| from .nn_graph import Graph |
| from .nn_graph import Pass |
| from .nn_graph import PassPlacement |
| from .nn_graph import SchedulingStrategy |
| from .nn_graph import Subgraph |
| from .live_range import ofm_can_reuse_ifm |
| from .numeric_util import round_down |
| from .numeric_util import round_up |
| from .operation import Op |
| from .shape4d import Shape4D |
| from .tensor import MemArea |
| from .tensor import MemType |
| from .tensor import Tensor |
| from .tensor import TensorFormat |
| from .tensor import TensorPurpose |
| from .tensor import TensorSubPurpose |
| from .weight_compressor import NpuWeightTensor |
| |
| |
| def shape_for_format(shape: Shape4D, tensor_format: TensorFormat) -> Shape4D: |
| if tensor_format == TensorFormat.NHCWB16: |
| return shape.with_depth(round_up(shape.depth, 16)) |
| |
| return shape |
| |
| |
| class OptimizationStrategy(IntEnum): |
| """Enum defining the different optimization strategies for the Scheduler""" |
| |
| Size = auto() |
| Performance = auto() |
| |
| def __str__(self): |
| return self.name |
| |
| |
| class SchedulerOpInfo: |
| """Contains metadata about a SchedulerOperation that is unique to one Schedule""" |
| |
| def __init__( |
| self, |
| block_config: ArchitectureBlockConfig, |
| weights_size: int, |
| stripe_input: Shape4D, |
| stripe_input2: Optional[Shape4D], |
| stripe: Shape4D, |
| ): |
| self.block_config = block_config |
| self.weights_size = weights_size |
| self.stripe_input = stripe_input |
| self.stripe_input2 = stripe_input2 |
| self.stripe = stripe |
| self.cascade = 0 # Assigned by CascadeBuilder. 0 means not part of a cascade |
| self.time_index = None # Set by update_op_memory_snapshot |
| self.ofm_depth_slices: List[int] = [0, stripe.depth] |
| self.npu_weights_tensor: Optional[NpuWeightTensor] = None |
| self.npu_scales_tensor: Optional[NpuWeightTensor] = None |
| self.buffered_weight_tensors: List[Tensor] = [] |
| self.cycles: Optional[CycleCost] = None |
| self.slack_buffering_cycles = 0 |
| self.slack_buffering_memory = 0 |
| self.full_weight_transfer_cycles = 0 |
| |
| def copy(self): |
| res = SchedulerOpInfo( |
| self.block_config, |
| self.weights_size, |
| self.stripe_input, |
| self.stripe_input2, |
| self.stripe, |
| ) |
| res.cascade = self.cascade |
| return res |
| |
| def __str__(self): |
| res = f"\t\tBlock Config = {self.block_config}\n" |
| res += f"\t\tOFM Block = {self.block_config.ofm_block}\n" |
| res += f"\t\tIFM Stripe = {self.stripe_input}\n" |
| res += f"\t\tIFM2 Stripe = {self.stripe_input2}\n" |
| res += f"\t\tOFM Stripe = {self.stripe}\n" |
| res += f"\t\tEncoded Weights = {self.npu_weights_tensor and len(self.npu_weights_tensor.buffer)} bytes\n" |
| for idx, tens in enumerate(self.buffered_weight_tensors): |
| res += f"\t\tWeight buffer{idx + 1} = {tens.storage_size()} bytes\n" |
| res += f"\t\tDepth slices = {self.ofm_depth_slices}\n" |
| res += f"\t\tAssigned Cascade = {self.cascade}" |
| return res |
| |
| |
| class SchedulerOptions: |
| """Contains options for the Scheduler""" |
| |
| def __init__( |
| self, |
| optimization_strategy, |
| sram_target, |
| verbose_schedule, |
| ): |
| self.optimization_strategy = optimization_strategy |
| self.optimization_sram_limit = sram_target |
| self.verbose_schedule = verbose_schedule |
| |
| def __str__(self) -> str: |
| return f"{type(self).__name__}: {str(self.__dict__)}" |
| |
| __repr__ = __str__ |
| |
| |
| class SchedulerTensor: |
| def __init__(self, shape, dt, mem_area, _format): |
| self.dtype = dt |
| self.mem_area = mem_area |
| self.shape = shape |
| self.format = _format |
| self.connection = None |
| |
| |
| class SchedulerOperation: |
| """Scheduler internal representation of 'Operation' |
| This class can be seen as a node within the Scheduler Graph representation |
| """ |
| |
| def __init__(self, ps: Pass, arch: ArchitectureFeatures, nng: Graph): |
| self.arch = arch |
| self.parent_ps = ps |
| self.parent_op = ps.primary_op |
| self.name = ps.primary_op.name |
| self.op_type = ps.primary_op.type |
| self.activation = ps.primary_op.activation |
| self.kernel = ps.primary_op.kernel |
| self.resampling_mode = ps.primary_op.ifm_resampling_mode |
| self.reversed_operands = False |
| self.uses_scalar = ps.primary_op.ifm2 is not None and ( |
| ps.primary_op.ifm.shape == [] or ps.primary_op.ifm2.shape == [] |
| ) |
| |
| self.ifm_ublock = arch.ifm_ublock |
| |
| self.ifm = SchedulerTensor( |
| ps.ifm_shapes[0], |
| ps.ifm_tensor.dtype, |
| ps.ifm_tensor.mem_area, |
| ps.ifm_tensor.format, |
| ) |
| |
| self.ifm2 = None |
| if ps.ifm2_tensor: |
| self.ifm2 = SchedulerTensor( |
| ps.ifm_shapes[1], |
| ps.ifm2_tensor.dtype, |
| ps.ifm2_tensor.mem_area, |
| ps.ifm2_tensor.format, |
| ) |
| |
| self.ofm = SchedulerTensor( |
| ps.ofm_shapes[0], |
| ps.ofm_tensor.dtype, |
| ps.ofm_tensor.mem_area, |
| ps.ofm_tensor.format, |
| ) |
| |
| # LUT must be placed in shram area. The copy is done by DMA |
| # generated by the high level command stream generator. |
| for idx, tens in enumerate(self.parent_op.inputs): |
| if tens.purpose == TensorPurpose.LUT: |
| new_tens = tens.clone_into_shram(self.arch) |
| new_tens.consumer_list.append(self.parent_op) |
| self.parent_op.inputs[idx] = new_tens |
| |
| # Input volume width and height required to produce the smallest possible stripe |
| self.min_stripe_input_w, self.min_stripe_input_h = self._calculate_min_stripe_input() |
| |
| # Flags that marks whether this SchedulerOperation requires full IFM/OFM |
| self.requires_full_ifm = False |
| self.requires_full_ifm2 = False |
| self.requires_full_ofm = False |
| |
| self.evicted_fms_size = 0 |
| |
| self.index = 0 |
| |
| # Perform an IFM swap for certain binary elementwise operators |
| # in order to enable cascading, if the SchedOp conforms to |
| # Elementwise cascading rules. |
| # The non-constant/non-scalar/non-broadcast IFM should be the primary input |
| if self.op_type.is_binary_elementwise_op(): |
| ifm = self.parent_op.ifm |
| ifm2 = self.parent_op.ifm2 |
| ofm = self.parent_op.ofm |
| |
| ifm_can_swap = ifm.is_const or ifm.is_scalar |
| ifm2_can_be_primary = not (ifm2.is_const or ifm2.is_scalar or ifm2.is_broadcast(ofm)) |
| |
| if ifm_can_swap and ifm2_can_be_primary: |
| # IFM2 is the primary input |
| self.reversed_operands = True |
| self.ifm, self.ifm2 = self.ifm2, self.ifm |
| |
| self.parent_ps.ifm_shapes = self.parent_ps.ifm_shapes[::-1] |
| self.parent_ps.inputs = self.parent_ps.inputs[::-1] |
| self.parent_ps.ifm_tensor, self.parent_ps.ifm2_tensor = ( |
| self.parent_ps.ifm2_tensor, |
| self.parent_ps.ifm_tensor, |
| ) |
| |
| def add_ifm_connection(self, conn: "Connection"): |
| """Add input connection to another SchedulerOperation or Subgraph Input""" |
| conn.consumers.append(self) |
| self.ifm.connection = conn |
| |
| def add_ifm2_connection(self, conn: "Connection"): |
| """Add input connection to another SchedulerOperation or Subgraph Input""" |
| if self.ifm2: |
| conn.consumers.append(self) |
| self.ifm2.connection = conn |
| else: |
| assert False, f"Trying to set an IFM2 Connection to {self} which has no IFM2" |
| |
| def add_ofm_connection(self, conn: "Connection"): |
| """Add output connection to another SchedulerOperation or Subgraph Output""" |
| conn.producers.append(self) |
| self.ofm.connection = conn |
| |
| def get_dependants(self): |
| """Returns a list of the Ops that depend on this Operation's OFM""" |
| return self.ofm.connection.consumers |
| |
| def ifm_size_in_bytes(self) -> int: |
| """Returns size of the IFM in bytes""" |
| ifm_storage_shape = shape_for_format(self.ifm.shape, self.ifm.format) |
| return round_up(ifm_storage_shape.elements() * self.ifm.dtype.size_in_bytes(), Tensor.AllocationQuantum) |
| |
| def ifm2_size_in_bytes(self) -> int: |
| """Returns size of the IFM2 in bytes""" |
| if self.ifm2: |
| ifm2_storage_shape = shape_for_format(self.ifm2.shape, self.ifm2.format) |
| return round_up(ifm2_storage_shape.elements() * self.ifm2.dtype.size_in_bytes(), Tensor.AllocationQuantum) |
| |
| return 0 |
| |
| def ofm_size_in_bytes(self) -> int: |
| """Returns size of the OFM in bytes""" |
| ofm_storage_shape = shape_for_format(self.ofm.shape, self.ofm.format) |
| return round_up(ofm_storage_shape.elements() * self.ofm.dtype.size_in_bytes(), Tensor.AllocationQuantum) |
| |
| def create_scheduler_info(self, nng: Graph, stripe: Shape4D) -> SchedulerOpInfo: |
| """Returns schedule info about this SchedulerOperation based on how many ofm elements it should produce""" |
| ifm_shape = self.ifm.shape |
| ifm2_shape = self.ifm2.shape if self.ifm2 is not None else None |
| ofm_shape = stripe |
| |
| if ofm_shape != self.ofm.shape: |
| # Striped Op - Need to calculate stripe input volume |
| stripe_input_w, stripe_input_h = self._get_stripe_input_requirement(stripe) |
| # Ensure stripe input volume is within the full IFM volume |
| stripe_input_h = min(stripe_input_h, self.ifm.shape.height) |
| stripe_input_w = min(stripe_input_w, self.ifm.shape.width) |
| ifm_shape = ifm_shape.with_hw(stripe_input_h, stripe_input_w) |
| |
| if self.ifm2: |
| stripe_input2_h = min(stripe_input_h, self.ifm2.shape.height) |
| stripe_input2_w = min(stripe_input_w, self.ifm2.shape.width) |
| ifm2_shape = ifm2_shape.with_hw(stripe_input2_h, stripe_input2_w) |
| |
| block_config = self._get_block_config(ifm_shape, ifm2_shape, self.uses_scalar, ofm_shape) |
| |
| scheduler_op_info = SchedulerOpInfo(block_config, 0, ifm_shape, ifm2_shape, ofm_shape) |
| if self.parent_op.weights: |
| # Default full-depth weight encoding with no buffering |
| ( |
| scheduler_op_info.npu_weights_tensor, |
| scheduler_op_info.npu_scales_tensor, |
| ) = weight_compressor.encode_weight_and_scale_tensor( |
| self.arch, |
| self.parent_op, |
| self.parent_op.weights, |
| self.parent_op.bias, |
| self.kernel, |
| block_config, |
| [0, self.ofm.shape.depth], |
| ) |
| |
| self.parent_ps.block_config = block_config.old_style_representation() |
| return scheduler_op_info |
| |
| def _get_stripe_input_requirement(self, stripe_shape: Shape4D) -> Tuple[int, int]: |
| """Returns the amount of IFM required to produce the stripe with shape:'stripe_shape'""" |
| ofm_shape_to_produce = Block.from_shape(stripe_shape.as_list()) |
| |
| return get_ifm_area_required(ofm_shape_to_produce, self.kernel, self.resampling_mode) |
| |
| def _calculate_min_stripe_input(self) -> Tuple[int, int]: |
| # Calculate the input volume required height and width for the smallest possible stripe (h,w = 1,1) |
| min_stripe = self.ofm.shape.with_hw(1, 1) |
| return self._get_stripe_input_requirement(min_stripe) |
| |
| def _get_block_config( |
| self, ifm_shape: Shape4D, ifm2_shape: Optional[Shape4D], uses_scalar: bool, ofm_shape: Shape4D |
| ) -> Optional[ArchitectureBlockConfig]: |
| # Returns a block config and SHRAM layout |
| lut_banks = 2 if self.parent_op.activation_lut else 0 |
| return find_block_config( |
| self.arch, |
| self.op_type.npu_block_type, |
| ofm_shape, |
| ifm_shape, |
| ifm2_shape, |
| uses_scalar, |
| self.ifm.dtype.size_in_bits(), |
| self.kernel, |
| lut_banks, |
| self.parent_op.has_scaling(), |
| self.resampling_mode, |
| ) |
| |
| |
| class Connection: |
| """Scheduler internal representation of a Tensor that connects two SchedulerOperations |
| This class can be seen as an edge within the Scheduler Graph representation |
| """ |
| |
| def __init__(self, tensor: Tensor): |
| self.parent_tens = tensor |
| |
| # SchedulerOperation relationships |
| self.producers: List[SchedulerOperation] = [] |
| self.consumers: List[SchedulerOperation] = [] |
| |
| def __str__(self): |
| return f"<Connection {self.parent_tens.name}>" |
| |
| __repr__ = __str__ |
| |
| |
| class Schedule: |
| """Class that contains a solution of how to schedule an NPU subgraph and its cost""" |
| |
| def __init__(self, sg: Subgraph, label: str): |
| self.sg = sg |
| self.label = label |
| self.cost_map: Dict[SchedulerOperation, SchedulerOpInfo] = {} |
| self.cascades: Dict[int, CascadeInfo] = {} |
| self.fast_storage_peak_usage = 0 |
| self.memory_snapshot: Optional[List[int]] = None |
| |
| @property |
| def name(self): |
| return f"{self.sg.name}_{self.label}" |
| |
| |
| class Scheduler: |
| """Main class of the Vela Scheduling""" |
| |
| def __init__(self, nng: Graph, sg: Subgraph, arch: ArchitectureFeatures, options: SchedulerOptions): |
| self.nng = nng |
| self.sg = sg |
| self.arch = arch |
| self.sched_ops: List[SchedulerOperation] = [] |
| self.max_schedule: Optional[Schedule] = None |
| self.scheduler_options = options |
| |
| self.scratched_fms: Dict[Tensor, Any] = {} |
| self.evicted_fms: List[live_range.LiveRange] = [] |
| |
| def avoid_nhcwb16_for_ofm(self, tens, ps, arch): |
| """For elementwise ops when ifm is in nhwc format and not brick format aligned (16), |
| then if the ofm can overwrite the ifm it is better to enforce ofm format to nhwc in |
| order to reduce memory transactions""" |
| |
| op = ps.primary_op |
| if not op.type.is_elementwise_op(): |
| return False |
| |
| depth = op.ofm_shapes[0][-1] |
| if (depth % 16) == 0: |
| return False |
| |
| # Check if overwriting the inputs can be allowed |
| OpShapeTens = namedtuple("OpShapeTens", ["op_shape", "tens"]) |
| outp = OpShapeTens(op.ofm_shapes[0], op.ofm) |
| inps = [] |
| if op.ifm is not None: |
| inps.append(OpShapeTens(op.ifm_shapes[0], op.ifm)) |
| if op.ifm2 is not None: |
| inps.append(OpShapeTens(op.ifm_shapes[1], op.ifm2)) |
| |
| # Find an input tensor that can be overwritten by the output |
| for inp in inps: |
| if ( |
| # check op input and output shapes allow overlapping |
| inp.op_shape == outp.op_shape |
| # check input tensor is valid |
| and inp.tens is not None |
| and inp.tens.shape != [] |
| # check input and output tensors are compatible |
| and inp.tens.format == outp.tens.format |
| and inp.tens.dtype == outp.tens.dtype |
| ): |
| if inp.tens.format == TensorFormat.NHWC: |
| return True |
| |
| return False |
| |
| def create_scheduler_representation(self, arch: ArchitectureFeatures): |
| """Creates a Scheduler Graph representation""" |
| # Temporary dict for creating connections between the Operations |
| connections: Dict[Tensor, Connection] = {} |
| # Memory required for the largest FeatureMap that has to be full |
| min_memory_req = 0 |
| for ps in self.sg.passes: |
| if ps.primary_op: |
| # Set tensor format to NHCWB16 for output FeatureMaps, if possible |
| for output in ps.outputs: |
| if output in self.sg.output_tensors or output.purpose != TensorPurpose.FeatureMap: |
| continue |
| |
| if output.needs_linear_format: |
| continue |
| |
| if self.avoid_nhcwb16_for_ofm(output, ps, arch): |
| output.needs_linear_format = True |
| continue |
| |
| output.set_format(TensorFormat.NHCWB16, arch) |
| |
| # Create SchedulerOperations |
| op = SchedulerOperation(ps, arch, self.nng) |
| op.index = len(self.sched_ops) |
| |
| # Make connections |
| if ps.ifm_tensor not in connections: |
| connections[ps.ifm_tensor] = Connection(ps.ifm_tensor) |
| if ps.ifm2_tensor and ps.ifm2_tensor not in connections: |
| connections[ps.ifm2_tensor] = Connection(ps.ifm2_tensor) |
| if ps.ofm_tensor not in connections: |
| connections[ps.ofm_tensor] = Connection(ps.ofm_tensor) |
| |
| op.add_ifm_connection(connections[ps.ifm_tensor]) |
| if ps.ifm2_tensor: |
| op.add_ifm2_connection(connections[ps.ifm2_tensor]) |
| op.add_ofm_connection(connections[ps.ofm_tensor]) |
| |
| # Set requirements on the ifm/ofm buffers |
| self.sched_ops.append(op) |
| if ps.ifm_tensor in self.sg.input_tensors: |
| # This Op consumes a subgraph input |
| op.requires_full_ifm = True |
| if ps.ifm2_tensor and ps.ifm2_tensor in self.sg.input_tensors: |
| # This Op consumes a subgraph input |
| op.requires_full_ifm2 = True |
| if ps.ofm_tensor in self.sg.output_tensors: |
| # This Op produces a subgraph output |
| op.requires_full_ofm = True |
| if ps.ifm_tensor.needs_linear_format: |
| op.requires_full_ifm = True |
| if ps.ifm2_tensor and ps.ifm2_tensor.needs_linear_format: |
| op.requires_full_ifm2 = True |
| if ps.ofm_tensor.needs_linear_format or ps.primary_op.memory_function == Op.ConcatSliceWrite: |
| op.requires_full_ofm = True |
| if len(ps.primary_op.outputs) > 1 or len(ps.primary_op.outputs[0].consumer_list) > 1: |
| # Op has multiple outputs or consumers - requires full OFM |
| op.requires_full_ofm = True |
| |
| # Check memory requirements if this Op requires any full FeatureMaps |
| op_memory_req = 0 |
| if op.requires_full_ifm: |
| op_memory_req += op.ifm_size_in_bytes() |
| if op.requires_full_ifm2: |
| op_memory_req += op.ifm2_size_in_bytes() |
| if op.requires_full_ofm: |
| op_memory_req += op.ofm_size_in_bytes() |
| |
| min_memory_req = max(op_memory_req, min_memory_req) |
| |
| # Theoretical minimum required memory - used to guide the cascade building |
| self.min_memory_req = min_memory_req |
| |
| def create_initial_schedule(self) -> Schedule: |
| """Creates an initial schedule with no cascading or buffering of any kind""" |
| schedule = Schedule(self.sg, "MAX") |
| for op in self.sched_ops: |
| cost = op.create_scheduler_info(self.nng, op.ofm.shape) |
| cost.cycles = self.estimate_op_performance(op, cost.block_config, op.ofm.shape.depth) |
| schedule.cost_map[op] = cost |
| |
| return schedule |
| |
| def update_op_memory_snapshot(self, schedule: Schedule): |
| memories_list = [(self.arch.fast_storage_mem_area, set((MemType.Scratch, MemType.Scratch_fast)))] |
| |
| # Collect live ranges from tensors |
| lr_graph = live_range.LiveRangeGraph() |
| for mem_area, mem_type_set in memories_list: |
| live_range.extract_live_ranges_from_schedule( |
| self.sg, |
| mem_area, |
| mem_type_set, |
| lr_graph, |
| ) |
| |
| # Populate time-array with memory used by live ranges |
| temporal_usage = lr_graph.get_temporal_memory_usage(self.arch.fast_storage_mem_area) |
| schedule.memory_snapshot = temporal_usage |
| |
| # Set the peak memory usage |
| schedule.fast_storage_peak_usage = max(temporal_usage, default=0) |
| |
| def estimate_op_performance(self, op: SchedulerOperation, block_config, ofm_depth): |
| query = npu_performance.PerformanceQuery(op.op_type.npu_block_type) |
| query.ifm_shape = op.ifm.shape |
| query.ifm_memory_area = op.ifm.mem_area |
| query.ifm_bits = op.ifm.dtype.size_in_bits() |
| query.ifm_format = op.ifm.format |
| query.ifm2_shape = op.ifm2 and op.ifm2.shape |
| query.ifm2_memory_area = op.ifm2 and op.ifm2.mem_area |
| query.ifm2_bits = op.ifm2 and op.ifm2.dtype.size_in_bits() |
| query.ifm2_format = op.ifm2 and op.ifm2.format |
| query.ofm_shape = op.ofm.shape.with_depth(ofm_depth) |
| query.ofm_memory_area = op.ofm.mem_area |
| query.ofm_bits = op.ofm.dtype.size_in_bits() |
| query.ofm_format = op.ofm.format |
| if op.parent_op.bias: |
| query.const_shape = Shape4D(1, 1, 1, op.ofm.shape.depth) |
| query.const_memory_area = self.arch.fast_storage_mem_area |
| |
| query.kernel = op.kernel |
| query.config = block_config |
| |
| return npu_performance.measure_cycle_cost(self.arch, op.op_type, op.activation and op.activation.op_type, query) |
| |
| def estimate_element_access(self, op: SchedulerOperation, block_config, ofm_depth): |
| query = npu_performance.PerformanceQuery(op.op_type.npu_block_type) |
| query.ifm_shape = op.ifm.shape |
| query.ifm_memory_area = op.ifm.mem_area |
| query.ifm_bits = op.ifm.dtype.size_in_bits() |
| query.ifm_format = op.ifm.format |
| query.ifm2_shape = op.ifm2 and op.ifm2.shape |
| query.ifm2_memory_area = op.ifm2 and op.ifm2.mem_area |
| query.ifm2_bits = op.ifm2 and op.ifm2.dtype.size_in_bits() |
| query.ifm2_format = op.ifm2 and op.ifm2.format |
| query.ofm_shape = op.ofm.shape.with_depth(ofm_depth) |
| query.ofm_memory_area = op.ofm.mem_area |
| query.ofm_bits = op.ofm.dtype.size_in_bits() |
| query.ofm_format = op.ofm.format |
| if op.parent_op.bias: |
| query.const_shape = Shape4D(1, 1, 1, op.ofm.shape.depth) |
| query.const_memory_area = self.arch.fast_storage_mem_area |
| |
| query.kernel = op.kernel |
| query.config = block_config |
| |
| return npu_performance.measure_element_access(self.arch, query) |
| |
| def propose_schedule_buffering(self, ref_schedule: Schedule, staging_limit_bytes): |
| """Create a buffered schedule""" |
| buffered_schedule = Schedule(self.sg, f"{ref_schedule.label}_BUFFERED") |
| |
| prev_op = None |
| for sched_op in self.sched_ops: |
| if sched_op not in ref_schedule.cost_map: |
| # sched_op is not part of this sub-schedule - skip |
| continue |
| |
| self.propose_operator_buffering(sched_op, prev_op, buffered_schedule, ref_schedule, staging_limit_bytes) |
| prev_op = sched_op |
| |
| return buffered_schedule |
| |
| def propose_operator_buffering( |
| self, |
| sched_op: SchedulerOperation, |
| prev_op: Optional[SchedulerOperation], |
| buffered_schedule: Schedule, |
| ref_schedule: Schedule, |
| staging_limit_bytes, |
| ): |
| # Mild recursion might mean this Op has already been seen |
| if sched_op in buffered_schedule.cost_map: |
| return |
| |
| # Take the reference schedule as default costings for this schedule |
| ref_cost = ref_schedule.cost_map[sched_op] |
| cost = copy.copy(ref_cost) |
| cost.slack_buffering_cycles = ref_cost.cycles.op_cycles |
| memory_snapshot = ref_schedule.memory_snapshot |
| ref_memory_usage = memory_snapshot[ref_cost.time_index] if ref_cost.time_index < len(memory_snapshot) else 0 |
| cost.slack_buffering_memory = staging_limit_bytes - ref_memory_usage |
| buffered_schedule.cost_map[sched_op] = cost |
| |
| # Attempt weight buffering on anything with a weights tensor |
| if sched_op.parent_op.weights: |
| buffer_limit_bytes = cost.slack_buffering_memory |
| |
| # If applicable apply size limitation, but keep it within reason (ratio 1.5). |
| # Size limitation is used when use_fast_storage_for_feature_maps have |
| # detected that there are fms that do not fit in fast storage. |
| if sched_op.evicted_fms_size and ((buffer_limit_bytes / sched_op.evicted_fms_size) >= 1.5): |
| buffer_limit_bytes -= sched_op.evicted_fms_size |
| |
| self.propose_weight_buffering( |
| sched_op.parent_op.weights, |
| sched_op.parent_op.bias, |
| sched_op, |
| prev_op, |
| buffered_schedule, |
| ref_schedule, |
| buffer_limit_bytes, |
| ) |
| |
| return cost |
| |
| def weights_needs_dma(self, weight_tensor): |
| if weight_tensor and weight_tensor.mem_type not in (MemType.Scratch, MemType.Scratch_fast): |
| # Weights are in permanent storage |
| # Only when permanent storage differs from feature map storage, there is a point moving the data |
| if ( |
| weight_tensor.mem_area in (MemArea.Dram, MemArea.OffChipFlash) |
| and self.arch.permanent_storage_mem_area != self.arch.fast_storage_mem_area |
| ): |
| return True |
| return False |
| |
| def propose_weight_buffering( |
| self, |
| weight_tensor, |
| scale_tensor, |
| sched_op: SchedulerOperation, |
| prev_op: SchedulerOperation, |
| buffered_schedule: Schedule, |
| ref_schedule: Schedule, |
| buffer_limit_bytes, |
| ): |
| cost = buffered_schedule.cost_map[sched_op] |
| prev_cost = buffered_schedule.cost_map.get(prev_op) |
| ref_cost = ref_schedule.cost_map[sched_op] |
| assert cost and ref_cost |
| |
| needs_dma = self.weights_needs_dma(weight_tensor) |
| |
| ofm_full_depth_slices = [0, ref_cost.stripe.depth] |
| |
| # Encode weights for the full depth |
| full_weights, full_scales = weight_compressor.encode_weight_and_scale_tensor( |
| self.arch, |
| sched_op.parent_op, |
| weight_tensor, |
| scale_tensor, |
| sched_op.kernel, |
| cost.block_config, |
| ofm_full_depth_slices, |
| ) |
| full_weights_bytes = len(full_weights.buffer) |
| cost.ofm_depth_slices = ofm_full_depth_slices |
| |
| # No buffering required - take all the weights from permanent storage |
| if sched_op.op_type == Op.FullyConnected or not needs_dma: |
| cost.npu_weights_tensor = full_weights |
| cost.npu_scales_tensor = full_scales |
| return |
| |
| encoded_weights: Optional[NpuWeightTensor] = full_weights |
| encoded_scales = full_scales |
| |
| # How many NPU cycles are available under the previously executing |
| # operator and SRAM unused for performing buffered DMA transfers |
| slack_cycles = prev_cost.slack_buffering_cycles if prev_cost else 0 |
| slack_memory = prev_cost.slack_buffering_memory if prev_cost else 0 |
| |
| # Force full depth for cascaded Ops |
| if ref_cost.cascade != 0: |
| weight_tensor_purpose = TensorSubPurpose.Standard |
| weight_buffer_size = full_weights_bytes |
| # Update the memory snapshot to reflect the added size of the weights |
| ref_schedule.memory_snapshot[ref_cost.time_index] += weight_buffer_size |
| else: |
| # Estimate the buffering cycle time for the full set of weights |
| full_transfer_cycles = npu_performance.measure_mem2mem_cycles( |
| self.arch, weight_tensor.mem_area, self.arch.fast_storage_mem_area, full_weights_bytes |
| ) |
| cost.full_weight_transfer_cycles = full_transfer_cycles |
| |
| # Calculate the amount of prebuffering necessary (or what is possible with limited |
| # double buffer buffer size) |
| half_buffer_limit = buffer_limit_bytes // 2 |
| if full_transfer_cycles > slack_cycles: |
| prebuffer_ratio = slack_cycles / full_transfer_cycles |
| prebuffer_bytes = min(prebuffer_ratio * full_weights_bytes, half_buffer_limit) |
| else: |
| prebuffer_bytes = min(full_weights_bytes, half_buffer_limit) |
| |
| prebuffer_ratio = prebuffer_bytes / full_weights_bytes |
| |
| # Have to split the weights if the initial buffering can't store |
| # all of the compressed weights |
| if prebuffer_bytes < full_weights_bytes: |
| block_depth = cost.block_config.ofm_block.depth |
| |
| # Choose initial prebuffering depth (already buffer clamped) |
| prebuffer_depth = ref_cost.stripe.depth * prebuffer_ratio |
| prebuffer_depth = int(max(16, round_down(prebuffer_depth, ArchitectureFeatures.OFMSplitDepth))) |
| |
| # Calculate cycles executed during the prebuffer |
| pre_op_cycles = self.estimate_op_performance(sched_op, cost.block_config, prebuffer_depth) |
| buffering_depth = ref_cost.stripe.depth * (pre_op_cycles.op_cycles / full_transfer_cycles) |
| |
| # Choose initial buffering depth and clamp to the double buffering limit |
| buffering_depth = round_up(buffering_depth, block_depth) |
| buffering_bytes = (buffering_depth / ref_cost.stripe.depth) * full_weights_bytes |
| if buffering_bytes > half_buffer_limit: |
| buffering_depth = (half_buffer_limit / full_weights_bytes) * ref_cost.stripe.depth |
| |
| while True: |
| # Attempt to buffer whole blocks |
| if buffering_depth > block_depth: |
| buffering_depth = round_down(buffering_depth, block_depth) |
| else: |
| buffering_depth = round_down(buffering_depth, ArchitectureFeatures.OFMSplitDepth) |
| buffering_depth = int(max(buffering_depth, ArchitectureFeatures.OFMSplitDepth)) |
| |
| # Create list of depth slices |
| depth_slices = [0] |
| if prebuffer_depth < ref_cost.stripe.depth: |
| depth_slices += list(range(prebuffer_depth, ref_cost.stripe.depth, buffering_depth)) |
| depth_slices.append(ref_cost.stripe.depth) |
| |
| # Encode weights based depth slices |
| cost.ofm_depth_slices = depth_slices |
| encoded_weights, encoded_scales = weight_compressor.encode_weight_and_scale_tensor( |
| self.arch, |
| sched_op.parent_op, |
| weight_tensor, |
| scale_tensor, |
| sched_op.kernel, |
| cost.block_config, |
| cost.ofm_depth_slices, |
| ) |
| assert encoded_weights is not None |
| # Chosen buffering might not fit at all, iterate until it does |
| # or until the minimum usable slice size is reached |
| if ( |
| encoded_weights.double_buffer_size() <= buffer_limit_bytes |
| or prebuffer_depth == ArchitectureFeatures.OFMSplitDepth |
| ): |
| break |
| |
| if buffering_depth > prebuffer_depth: |
| buffering_depth = round_up(buffering_depth // 2, ArchitectureFeatures.OFMSplitDepth) |
| else: |
| prebuffer_depth = round_up(prebuffer_depth // 2, ArchitectureFeatures.OFMSplitDepth) |
| |
| # Calculate cycles required to run the last op for use as future slack |
| tail_cycles = self.estimate_op_performance( |
| sched_op, cost.block_config, depth_slices[-1] - depth_slices[-2] |
| ) |
| cost.slack_buffering_cycles = tail_cycles.op_cycles |
| |
| # Determine whether the weights need to be double buffered |
| weight_buffer_size = min(len(encoded_weights.buffer), encoded_weights.max_range_bytes()) |
| |
| # Only buffer weights if there's still space left for the buffer |
| if weight_buffer_size <= buffer_limit_bytes: |
| assert weight_buffer_size % 16 == 0 |
| # Determine whether to double buffer or single buffer |
| double_buffer_size = encoded_weights.double_buffer_size() |
| if (double_buffer_size <= buffer_limit_bytes) and (weight_buffer_size < len(encoded_weights.buffer)): |
| weight_tensor_purpose = TensorSubPurpose.DoubleBuffer |
| else: |
| weight_tensor_purpose = TensorSubPurpose.Standard |
| |
| cost.buffered_weight_tensors = [ |
| self.buffer_tensor( |
| encoded_weights, |
| weight_tensor_purpose, |
| encoded_weights.double_buffer_sizes[0], |
| weight_tensor.name + "_buffer", |
| ) |
| ] |
| if weight_tensor_purpose == TensorSubPurpose.DoubleBuffer: |
| buf2 = self.buffer_tensor( |
| encoded_weights, |
| weight_tensor_purpose, |
| encoded_weights.double_buffer_sizes[1], |
| weight_tensor.name + "_buffer2", |
| ) |
| cost.buffered_weight_tensors.append(buf2) |
| |
| # Note! OFM depth slices define slices as [0, s1, ... sn]. For example, [0, 70, 140] describes two slices |
| # (0-70 and 70-140) but has a length of 3, which would result in idx = 3 % 2 = 1 if two buffers were used. |
| last_used_buffer_idx = len(cost.ofm_depth_slices) % len(cost.buffered_weight_tensors) |
| weight_buffer_size = encoded_weights.double_buffer_sizes[last_used_buffer_idx] |
| |
| if ref_cost.cascade == 0: |
| # Determine if the lifetime can be extended and pre-buffer the first weight buffer |
| # under the previous operation |
| cost.buffered_weight_tensors[0].pre_buffer = encoded_weights.double_buffer_size() < slack_memory |
| |
| cost.slack_buffering_memory -= weight_buffer_size |
| else: |
| # Don't slice or buffer - use the whole depth from persistent storage |
| cost.ofm_depth_slices = ofm_full_depth_slices |
| encoded_weights = full_weights |
| encoded_scales = full_scales |
| |
| cost.npu_weights_tensor = encoded_weights |
| cost.npu_scales_tensor = encoded_scales |
| |
| def buffer_tensor(self, src_tensor: Tensor, sub_purpose: TensorSubPurpose, buffer_size: int, name: str) -> Tensor: |
| buffered_weight_tensor = Tensor([1, 1, 1, buffer_size], DataType.uint8, name) |
| buffered_weight_tensor.src_tensor = src_tensor |
| buffered_weight_tensor.mem_area = self.arch.fast_storage_mem_area |
| buffered_weight_tensor.mem_type = MemType.Scratch_fast |
| buffered_weight_tensor.purpose = TensorPurpose.Weights |
| buffered_weight_tensor.sub_purpose = sub_purpose |
| return buffered_weight_tensor |
| |
| def propose_minimal_schedule(self) -> Schedule: |
| """Proposes scheduling parameters where every operator is subdivided into the smallest stripe that satisfies the |
| next operators stride""" |
| min_schedule = Schedule(self.sg, "MIN") |
| cost_map = min_schedule.cost_map |
| |
| # Keep track of the previous Op - which consumes the current Op's OFM |
| prev_op: Optional[SchedulerOperation] = None |
| for sched_op in reversed(self.sched_ops): |
| min_stripe_height = prev_op.kernel.stride.y if prev_op else 1 |
| min_stripe = sched_op.ofm.shape.with_height(min_stripe_height) |
| |
| cost = sched_op.create_scheduler_info(self.nng, min_stripe) |
| cost.cycles = self.estimate_op_performance(sched_op, cost.block_config, sched_op.ofm.shape.depth) |
| cost_map[sched_op] = cost |
| |
| prev_op = sched_op |
| |
| return min_schedule |
| |
| def propose_schedule_striping(self, final_stripe: Shape4D, label: str, ref_schedule: Schedule) -> Schedule: |
| """Proposes new striping for a schedule. The stripe is derived from the ifm requirements of the next Op down""" |
| ref_cost = ref_schedule.cost_map |
| |
| striped_schedule = Schedule(self.sg, label) |
| stripe = final_stripe |
| for sched_op in reversed(self.sched_ops): |
| if sched_op not in ref_cost: |
| # sched_op is not part of the sub-schedule - skip |
| continue |
| |
| # Create a cost entry with the new stripe |
| cost = sched_op.create_scheduler_info(self.nng, stripe) |
| |
| weight_tensor = cost.npu_weights_tensor |
| for idx, buffered_tens in enumerate(ref_cost[sched_op].buffered_weight_tensors): |
| # If the weights are buffered in the reference schedule they should be in the new proposal |
| cost.buffered_weight_tensors.append( |
| self.buffer_tensor( |
| weight_tensor, |
| buffered_tens.sub_purpose, |
| weight_tensor.double_buffer_sizes[idx], |
| buffered_tens.name, |
| ) |
| ) |
| |
| # Estimate performance |
| cost.cycles = self.estimate_op_performance(sched_op, cost.block_config, sched_op.ofm.shape.depth) |
| striped_schedule.cost_map[sched_op] = cost |
| |
| # Calculate the preceeding Op's stripe. |
| |
| # In certain cases where an upscaling Op is cascaded, |
| # it may get instructed to produce an odd stripe height. |
| # Thus we need to force it back to even heights. |
| force_even_stripe_heights = False |
| for op in self.sched_ops: |
| # Check if the cascade has a Nearest Neighbor-op. |
| # If that is the case, force the stripes to be even. |
| if ( |
| ref_cost.get(op, None) |
| and ref_cost.get(sched_op, None) |
| and ref_cost[op].cascade == ref_cost[sched_op].cascade |
| and is_nearest(op.resampling_mode) |
| ): |
| force_even_stripe_heights = True |
| break |
| upscaling_remainder = stripe.height % to_upscale(sched_op.resampling_mode) |
| height = stripe.height + (stripe.height % 2 if force_even_stripe_heights else upscaling_remainder) |
| stripe = sched_op.ifm.shape.with_height(height * sched_op.kernel.stride.y) |
| |
| return striped_schedule |
| |
| def estimate_schedule_memory_usage(self, schedule: Schedule, non_local_mem_usage: dict): |
| """Estimates the memory usage of a schedule""" |
| cost = schedule.cost_map |
| cascades = schedule.cascades |
| peak_mem_usage = 0 |
| for sched_op in self.sched_ops: |
| if sched_op not in cost: |
| # sched_op is not part of the sub-schedule - skip |
| continue |
| |
| if cost[sched_op].cascade: |
| # This Op is part of a cascade - use the cascade's memory usage |
| cascade_info = cascades[cost[sched_op].cascade] |
| # Non-local memory usage is already included in the cascade_info |
| peak_mem_usage = max(cascade_info.mem_usage, peak_mem_usage) |
| else: |
| # This Op is not part of a cascade - calculate the memory usage |
| op_weight_buffer = sum(tens.storage_size() for tens in cost[sched_op].buffered_weight_tensors) |
| |
| op_mem_usage = ( |
| sched_op.ifm_size_in_bytes() |
| + sched_op.ofm_size_in_bytes() |
| + op_weight_buffer |
| + non_local_mem_usage.get(sched_op, 0) |
| ) |
| peak_mem_usage = max(op_mem_usage, peak_mem_usage) |
| |
| return peak_mem_usage |
| |
| def build_cascades_for_min_schedule(self, min_schedule: Schedule, max_template: Schedule, memory_limit: int): |
| # Update memory snapshot |
| self.sg.schedule = min_schedule |
| self.update_op_memory_snapshot(min_schedule) |
| |
| # Calculate residual memory for Min schedule |
| non_local_mem_usage = {} |
| for sched_op in self.sched_ops: |
| time_index = min_schedule.cost_map[sched_op].time_index |
| |
| if self.arch.is_spilling_enabled(): |
| # For Dedicated SRAM only the intermediate buffers are in SRAM, hence op_mem_usage is 0 |
| op_mem_usage = 0 |
| else: |
| # Min schedule only have ifm and ofm in SRAM (no buffered weigth tensors) |
| # Only include IFM's that are in the scratch area |
| ifm = sched_op.ifm.connection.parent_tens |
| ifm_size = ( |
| 0 if ifm.mem_type not in (MemType.Scratch, MemType.Scratch_fast) else sched_op.ifm_size_in_bytes() |
| ) |
| ofm_size = 0 if ofm_can_reuse_ifm(sched_op) else sched_op.ofm_size_in_bytes() |
| op_mem_usage = ifm_size + ofm_size |
| |
| non_local_mem_usage[sched_op] = min_schedule.memory_snapshot[time_index] - op_mem_usage |
| assert non_local_mem_usage[sched_op] >= 0 |
| |
| # Create cascades for Min schedule |
| cascade_builder = CascadeBuilder(self.sched_ops, self.arch.is_spilling_enabled(), non_local_mem_usage) |
| cascade_builder.build_cascades(min_schedule, max_template, memory_limit) |
| |
| def optimize_sub_schedule( |
| self, cascade_info: CascadeInfo, ref_schedule: Schedule, max_template: Schedule, memory_limit: int |
| ) -> Schedule: |
| """Extracts the Ops covered by the given cascade and creates a sub-schedule. The sub-schedule is optimized by |
| proposing weight buffering and then continously proposing new stripe sizes""" |
| ref_cost = ref_schedule.cost_map |
| # Extract the ops that are part of this sub-schedule |
| start = cascade_info.start |
| end = cascade_info.end |
| sub_schedule_ops = self.sched_ops[start : end + 1] |
| # Create a sub-schedule that contains only the costs for the Ops that are part of the sub-schedule |
| sub_schedule = Schedule(self.sg, f"SUB_{start}_{end}") |
| for sched_op in sub_schedule_ops: |
| sub_schedule.cost_map[sched_op] = ref_cost[sched_op] |
| |
| sub_schedule.cascades[end] = cascade_info |
| # Use the memory snapshot from the reference schedule |
| sub_schedule.memory_snapshot = ref_schedule.memory_snapshot |
| |
| # Calculate memory usage that is live during the sub-schedule but not part of it |
| time_for_cascade = ref_cost[sub_schedule_ops[0]].time_index |
| mem_usage_parallel_to_sub_schedule = ref_schedule.memory_snapshot[time_for_cascade] - cascade_info.mem_usage |
| # If the first Op's IFM has other consumers it has to live throughout the whole sub-schedule whether it's |
| # included in a cascade or not |
| persistent_initial_ifm = ( |
| sub_schedule_ops[0].ifm_size_in_bytes() if len(sub_schedule_ops[0].ifm.connection.consumers) > 1 else 0 |
| ) |
| # Calculate non-local-mem-usage per Operator |
| non_local_mem_usage = {} |
| for idx, sched_op in enumerate(sub_schedule_ops): |
| non_local_mem_usage[sched_op] = mem_usage_parallel_to_sub_schedule |
| if idx != 0: |
| non_local_mem_usage[sched_op] += persistent_initial_ifm |
| |
| cascade_builder = CascadeBuilder(sub_schedule_ops, self.arch.is_spilling_enabled(), non_local_mem_usage) |
| |
| # Start by adding buffering |
| buffered_sub_schedule = self.propose_schedule_buffering( |
| sub_schedule, self.scheduler_options.optimization_sram_limit |
| ) |
| # Copy the cascades over from the unbuffered-schedule |
| buffered_sub_schedule.cascades = sub_schedule.cascades |
| |
| # Generate the possible stripings for the final Op in the sub-schedule |
| final_ofm_shape = sub_schedule_ops[-1].ofm.shape |
| |
| # Skip testing the min stripe used in the MIN schedule since that will be used |
| # anyway if no new cascades are created below |
| last_op = sub_schedule_ops[-1] |
| min_stripe_h = sub_schedule.cost_map[last_op].stripe.height + 1 |
| |
| possible_stripes = [ |
| final_ofm_shape.with_height(stripe_h) for stripe_h in range(min_stripe_h, final_ofm_shape.height // 2 + 1) |
| ] |
| # Propose different striping |
| best_schedule = None |
| max_nbr_of_cascades = 0 |
| for iteration, proposed_stripe in enumerate(possible_stripes): |
| proposed_schedule = self.propose_schedule_striping( |
| proposed_stripe, f"OPTIMIZED_{iteration}", buffered_sub_schedule |
| ) |
| |
| cascade_builder.build_cascades(proposed_schedule, max_template, memory_limit) |
| nbr_of_cascades = len(proposed_schedule.cascades) |
| if iteration == 0: |
| # First iteration - used as limit to prevent splitting up the cascades |
| # Long cascades are better in order to reduce IFM/IFM dram bandwidth |
| max_nbr_of_cascades = nbr_of_cascades |
| |
| # Check if proposal fits |
| proposed_schedule_mem_usage = self.estimate_schedule_memory_usage(proposed_schedule, non_local_mem_usage) |
| if (proposed_schedule_mem_usage) <= memory_limit and nbr_of_cascades <= max_nbr_of_cascades: |
| best_schedule = proposed_schedule |
| |
| if not proposed_schedule.cascades: |
| # No cascading required - early exit |
| break |
| else: |
| break |
| |
| return best_schedule |
| |
| def optimize_schedule( |
| self, |
| schedule: Schedule, |
| max_sched: Schedule, |
| max_template: Schedule, |
| options: SchedulerOptions, |
| ) -> Schedule: |
| """Extracts sub-schedules based on the cascades and optimizes them and applies them to the final schedule""" |
| sram_limit = options.optimization_sram_limit |
| if max_sched.fast_storage_peak_usage < sram_limit and not self.arch.is_spilling_enabled(): |
| # Maximum performance schedule fits within the SRAM target |
| return max_sched |
| |
| # Iterate over a copy of the cascades since they may change during the loop |
| for cascade_info in list(schedule.cascades.values()): |
| # Optimize the sub-schedule in this cascade |
| opt_sub_schedule = self.optimize_sub_schedule(cascade_info, schedule, max_template, sram_limit) |
| if opt_sub_schedule: |
| # Remove the existing cascade |
| del schedule.cascades[cascade_info.end] |
| # Update the sub-schedule Op and cascade costs to the full schedule |
| schedule.cost_map.update(opt_sub_schedule.cost_map) |
| schedule.cascades.update(opt_sub_schedule.cascades) |
| |
| # Update memory snapshot |
| self.sg.schedule = schedule |
| self.update_op_memory_snapshot(schedule) |
| # Propose schedule buffering to the optimized schedule |
| optimized_sched = self.propose_schedule_buffering(schedule, self.scheduler_options.optimization_sram_limit) |
| # Copy the cascade's metadata from the unbuffered schedule |
| optimized_sched.cascades = schedule.cascades |
| return optimized_sched |
| |
| def optimize_weight_buffering_size( |
| self, |
| min_schedule: Schedule, |
| options: SchedulerOptions, |
| ): |
| default_schedule = self.sg.schedule |
| npu_performance.calc_new_performance_for_network(self.nng, self.arch, None, False) |
| default_tot_cycles = self.nng.cycles[npu_performance.PassCycles.Total] |
| default_dram_cycles = self.nng.cycles[npu_performance.PassCycles.DramAccess] |
| |
| # Restore mem/type for scratched_fms |
| for tens in self.scratched_fms: |
| tens.mem_area = self.scratched_fms[tens][0] |
| tens.mem_type = self.scratched_fms[tens][1] |
| |
| self.update_op_memory_snapshot(self.sg.schedule) |
| |
| # Collect live ranges from tensors |
| memories_list = [(self.arch.fast_storage_mem_area, set((MemType.Scratch, MemType.Scratch_fast)))] |
| lr_graph = live_range.LiveRangeGraph() |
| for mem_area, mem_type_set in memories_list: |
| live_range.extract_live_ranges_from_schedule( |
| self.sg, |
| mem_area, |
| mem_type_set, |
| lr_graph, |
| ) |
| |
| # Find the relation between the sched_op and the buffering tensor |
| weight_ops = {} |
| for sched_op in self.sched_ops: |
| cost = self.sg.schedule.cost_map[sched_op] |
| for tens in cost.buffered_weight_tensors: |
| weight_ops[tens] = sched_op |
| |
| # Filter out weight buffer live ranges |
| weight_lrs = [] |
| for lr in lr_graph.lrs: |
| for tens in lr.tensors: |
| if weight_ops.get(tens): |
| weight_lrs.append(lr) |
| break |
| |
| # See if any evicted fm overlaps with a weight buffering op. |
| # If this is the case add a size limitation to the buffering op |
| for lr in self.evicted_fms: |
| for weight_lr in weight_lrs: |
| if lr.overlaps_ranges(weight_lr): |
| for tens in weight_lr.tensors: |
| sched_op = weight_ops.get(tens) |
| if sched_op: |
| # Add size reduction to the op |
| sched_op.evicted_fms_size += lr.size |
| break |
| |
| self.sg.schedule = min_schedule |
| self.update_op_memory_snapshot(self.sg.schedule) |
| |
| # Run schedule buffering - with weight buffer size reduction |
| schedule = self.propose_schedule_buffering(self.sg.schedule, options.optimization_sram_limit) |
| schedule.cascades = self.sg.schedule.cascades |
| self.sg.schedule = schedule |
| |
| # Apply new buffer schdule and calc new performance |
| self.update_op_memory_snapshot(self.sg.schedule) |
| self.apply_schedule(self.sg.schedule) |
| self.use_fast_storage_for_feature_maps(self.sg.schedule, options.optimization_sram_limit) |
| |
| npu_performance.calc_new_performance_for_network(self.nng, self.arch, None, False) |
| new_tot_cycles = self.nng.cycles[npu_performance.PassCycles.Total] |
| new_dram_cycles = self.nng.cycles[npu_performance.PassCycles.DramAccess] |
| |
| improvement_tot = ( |
| round((default_tot_cycles - new_tot_cycles) / default_tot_cycles, 2) if default_tot_cycles != 0 else 0 |
| ) |
| improvement_dram = ( |
| round((default_dram_cycles - new_dram_cycles) / default_dram_cycles, 2) if default_dram_cycles != 0 else 0 |
| ) |
| |
| # Compare both total and dram improvement |
| if not (improvement_tot >= 0 and improvement_dram > 0): |
| # No improvement, restore the default schedule |
| for sched_op in self.sched_ops: |
| sched_op.evicted_fms_size = 0 |
| |
| for tens in self.scratched_fms: |
| tens.mem_area = self.scratched_fms[tens][0] |
| tens.mem_type = self.scratched_fms[tens][1] |
| |
| self.sg.schedule = default_schedule |
| self.update_op_memory_snapshot(self.sg.schedule) |
| self.apply_schedule(self.sg.schedule) |
| self.use_fast_storage_for_feature_maps(self.sg.schedule, options.optimization_sram_limit) |
| |
| def apply_schedule(self, sched: Schedule): |
| """Applies the given schedule as a final solution""" |
| for sched_op in self.sched_ops: |
| op_info = sched.cost_map[sched_op] |
| cascade_info = sched.cascades.get(op_info.cascade, None) |
| if cascade_info and sched_op in cascade_info.buffers: |
| buffer_tens = sched_op.ifm.connection.parent_tens |
| # Apply memory area and type |
| buffer_tens.mem_area = self.arch.fast_storage_mem_area |
| buffer_tens.mem_type = MemType.Scratch_fast |
| # Apply Rolling buffer |
| buffer_tens.set_format(TensorFormat.NHCWB16, self.arch) |
| buffer_tens.set_new_sub_purpose(TensorSubPurpose.RollingBufferY, cascade_info.buffers[sched_op].height) |
| |
| sched_op.parent_ps.block_config = op_info.block_config.old_style_representation() |
| |
| # Ensure that the src_tensor reference is set correctly |
| for tens in op_info.buffered_weight_tensors: |
| tens.src_tensor = op_info.npu_weights_tensor |
| |
| def use_fast_storage_for_feature_maps(self, schedule, staging_limit): |
| """Finds the set of feature maps that fits within the staging limit which combined has the largest amount of |
| access cycles and moves those feature map into fast storage""" |
| max_mem_usage = [] |
| base_mem_usage = [] |
| fast_storage_type = MemType.Scratch_fast |
| fast_storage_mem_area = self.arch.fast_storage_mem_area |
| self.evicted_fms = [] |
| |
| # Force all OFMs to fast-storage |
| for sched_op in self.sched_ops: |
| cost = schedule.cost_map[sched_op] |
| if cost.cascade == 0 and sched_op.get_dependants(): |
| ofm_tens = sched_op.ofm.connection.parent_tens |
| if not any(cons is None for cons in ofm_tens.consumer_list): |
| if ofm_tens not in self.scratched_fms: |
| # Remember default mem area and mem type, only done once |
| self.scratched_fms[ofm_tens] = (ofm_tens.mem_area, ofm_tens.mem_type) |
| |
| ofm_tens.mem_area = fast_storage_mem_area |
| ofm_tens.mem_type = fast_storage_type |
| |
| # Collect live ranges from tensors |
| memories_list = [(fast_storage_mem_area, set((MemType.Scratch, MemType.Scratch_fast)))] |
| lr_graph = live_range.LiveRangeGraph() |
| for mem_area, mem_type_set in memories_list: |
| live_range.extract_live_ranges_from_schedule( |
| self.sg, |
| mem_area, |
| mem_type_set, |
| lr_graph, |
| ) |
| max_mem_usage = lr_graph.get_temporal_memory_usage(fast_storage_mem_area) |
| |
| # If max_mem_usage does not exceed staging limit at any point all lrs fit and can stay in fast storage |
| if max(max_mem_usage) <= staging_limit: |
| return |
| |
| # Build up the base memory usage by removing the mem_usage of the lrs we previously moved to fast-storage |
| base_mem_usage = np.array(max_mem_usage) |
| curr_lrs = [] |
| for lr in lr_graph.lrs: |
| for tens in lr.tensors: |
| if self.scratched_fms.get(tens): |
| curr_lrs.append(lr) |
| base_mem_usage[lr.start_time : lr.end_time + 1] -= lr.size |
| break |
| competing_lrs = [] |
| competing_tens_access = {} |
| |
| # Evict live ranges that will never fit |
| for lr in curr_lrs.copy(): |
| base_usage = max(base_mem_usage[lr.start_time : lr.end_time + 1]) |
| if base_usage + lr.size > staging_limit: |
| # Lr will never fit and may thus be evicted |
| self.evicted_fms.append(lr) |
| FastStorageComponentAllocator.evict(lr, max_mem_usage, self.scratched_fms) |
| curr_lrs.remove(lr) |
| |
| # Keep live ranges that will always fit in fast storage and let the remaining ones compete |
| for lr in curr_lrs: |
| # Since max_mem_usage is the memory usage with all FMs still in fast-storage, |
| # the memory limit cannot be exceeded if max_mem_usage does not. |
| # Thus, the affected lrs can remain in fast-storage if the following is true |
| if max(max_mem_usage[lr.start_time : lr.end_time + 1]) <= staging_limit: |
| FastStorageComponentAllocator.keep(lr, base_mem_usage) |
| else: |
| competing_lrs.append(lr) |
| for tens in lr.tensors: |
| competing_tens_access[tens] = 0 |
| |
| # All lrs and their tensors have been handled if competing_lrs_sz is zero, we may thus return |
| if len(competing_lrs) == 0: |
| return |
| |
| # Estimate element access for all tensors that are competing for a place in fast-storage. |
| # This number is used when deciding which tensor that stays in fast-storage |
| for sched_op in self.sched_ops: |
| cost = schedule.cost_map[sched_op] |
| |
| if competing_tens_access.get(sched_op.ifm.connection.parent_tens) is not None: |
| tens = sched_op.ifm.connection.parent_tens |
| access = self.estimate_element_access(sched_op, cost.block_config, sched_op.ofm.shape.depth) |
| competing_tens_access[tens] += access.ifm_read[0] |
| |
| if sched_op.ifm2 and competing_tens_access.get(sched_op.ifm2.connection.parent_tens) is not None: |
| tens = sched_op.ifm2.connection.parent_tens |
| access = self.estimate_element_access(sched_op, cost.block_config, sched_op.ofm.shape.depth) |
| competing_tens_access[tens] += access.ifm_read[1] |
| |
| if competing_tens_access.get(sched_op.ofm.connection.parent_tens) is not None: |
| tens = sched_op.ofm.connection.parent_tens |
| access = self.estimate_element_access(sched_op, cost.block_config, sched_op.ofm.shape.depth) |
| competing_tens_access[tens] += access.ofm_write |
| |
| # Sort live ranges "from left to right" on the time axis to simplify checking overlapping ranges |
| competing_lrs = sorted(competing_lrs, key=lambda lr: (lr.start_time, lr.end_time + 1, lr.size)) |
| |
| # Remove lrs that have a live range that is too long compared to others. |
| # They are causing problems for the HillClimb Allocator when it has to |
| # change the allocation indices, in order to fit all the allocations into SRAM. |
| # This problem only occur in larger networks with complex graphs. |
| # |
| # Limit the number of items for allocate_component to work with max MAX_EXHAUSTIVE_ITEMS |
| # at the time. Too many will give too long compilation time |
| # |
| # Too long is currently decided to be (based on experience, analyzing many networks): |
| # Compare lr at postion i with lr at position i + MAX_EXHAUSTIVE_ITEMS. |
| # If end time differs by at least MAX_EXHAUSTIVE_LIFE_RANGE then do not include lr at position i. |
| if len(competing_lrs) > FastStorageComponentAllocator.MAX_EXHAUSTIVE_ITEMS: |
| # Create a copy of the original list to iterate over because the original version is modified in-loop |
| competing_lrs_copy = competing_lrs.copy() |
| for i, lr in enumerate(competing_lrs_copy): |
| lr_time = lr.end_time - lr.start_time |
| # Only check live ranges longer than MAX_EXHAUSTIVE_LIFE_RANGE |
| if lr_time >= FastStorageComponentAllocator.MAX_EXHAUSTIVE_LIFE_RANGE: |
| # Compare current lr with lr at position lr + MAX_EXHAUSTIVE_ITEMS |
| cmp_pos = min(i + FastStorageComponentAllocator.MAX_EXHAUSTIVE_ITEMS, len(competing_lrs) - 1) |
| |
| # Compare end times + plus a margin by MAX_EXHAUSTIVE_LIFE_RANGE |
| if ( |
| lr.end_time |
| > competing_lrs_copy[cmp_pos].end_time + FastStorageComponentAllocator.MAX_EXHAUSTIVE_LIFE_RANGE |
| ): |
| # Current lr live time stands out, remove it. No use adding it to the |
| # evicted_fms list since the lr should not be included in the fast storage allocation |
| FastStorageComponentAllocator.evict(lr, max_mem_usage, self.scratched_fms) |
| competing_lrs.remove(lr) |
| |
| # Split competing live ranges into components by finding disconnected groups of live ranges or components of |
| # max size MAX_EXHAUSTIVE_ITEMS |
| start = 0 |
| end_time = competing_lrs[0].end_time |
| component_allocator = FastStorageComponentAllocator(base_mem_usage, max_mem_usage, staging_limit) |
| component_ranges = [] |
| for i, lr in enumerate(competing_lrs): |
| nbr_items = i - start |
| if lr.start_time <= end_time and (nbr_items < FastStorageComponentAllocator.MAX_EXHAUSTIVE_ITEMS): |
| end_time = max(end_time, lr.end_time) |
| else: |
| # Number items reached max items or current lr's start time |
| # does not overlap with previous lr's end time |
| component_ranges.append((start, i)) |
| start = i |
| end_time = lr.end_time |
| component_ranges.append((start, len(competing_lrs))) |
| |
| # Allocate each component separately |
| for start, end in component_ranges: |
| component_allocator.allocate_component( |
| competing_lrs[start:end], |
| max_mem_usage, |
| base_mem_usage, |
| self.scratched_fms, |
| competing_tens_access, |
| self.evicted_fms, |
| ) |
| assert max(max_mem_usage) <= staging_limit, "Allocation exceeds staging limit" |
| |
| def print_schedule(self, schedule: Schedule): |
| print(f"Schedule: '{schedule.name}'") |
| for sched_op in self.sched_ops: |
| if sched_op not in schedule.cost_map: |
| # Sub-schedule printing |
| continue |
| |
| op_info = schedule.cost_map[sched_op] |
| print(f"\t{sched_op.index}: Operation {sched_op.name} - OFM {sched_op.ofm.shape}") |
| print(f"\t\tType: {sched_op.op_type}") |
| print(f"\t\tKernel: {sched_op.kernel}") |
| print(f"{op_info}") |
| mem_usage = ( |
| schedule.memory_snapshot[op_info.time_index] |
| if op_info.time_index < len(schedule.memory_snapshot) |
| else 0 |
| ) |
| print(f"\t\tSRAM Used: {mem_usage} bytes") |
| |
| print("\tCascades:") |
| for i, cascade in enumerate(schedule.cascades.values()): |
| print(f"\t\t{i}: {cascade.start} -> {cascade.end}, size: {cascade.mem_usage}") |
| |
| |
| def _update_memory_snapshot_for_all_npu_graphs(nng: Graph, arch: ArchitectureFeatures, schedulers): |
| mem_area = arch.fast_storage_mem_area |
| mem_type_set = set((MemType.Scratch, MemType.Scratch_fast)) |
| |
| # Collect live ranges for the full graph |
| # extract_live_ranges_from_cascaded_passes will start from the root sg and |
| # all sub graphs/cascaded passes will be visited and the correct time_index |
| # will be set for all the tensors. |
| lr_graph = live_range.LiveRangeGraph() |
| live_range.extract_live_ranges_from_cascaded_passes( |
| nng.get_root_subgraph(), |
| mem_area, |
| mem_type_set, |
| lr_graph, |
| Tensor.AllocationQuantum, |
| ) |
| # Populate time-array with memory used by live ranges |
| temporal_usage = lr_graph.get_temporal_memory_usage(arch.fast_storage_mem_area) |
| |
| # Update snapshot for all the npu sub graphs |
| # Not needed for the scheduler any longer but npu_performance |
| # is using this information so it must have the correct state |
| for sg in schedulers: |
| sg.schedule.memory_snapshot = temporal_usage |
| sg.schedule.fast_storage_peak_usage = max(temporal_usage, default=0) |
| |
| |
| def _update_tensor_allocation(nng: Graph, arch: ArchitectureFeatures, options): |
| """ |
| Creates live ranges and runs tensor allocator for the current schedule |
| (i.e. sg.schedule for all subgraphs), returns the maximum memory usage |
| and updates SchedulerOpInfo.mem_usage for all operations in the schedule. |
| """ |
| root_sg = nng.get_root_subgraph() |
| |
| alloc_list = [] |
| if arch.is_spilling_enabled(): |
| mem_alloc_scratch_fast = (arch.fast_storage_mem_area, set((MemType.Scratch_fast,))) |
| mem_alloc_scratch = (arch.feature_map_storage_mem_area, set((MemType.Scratch,))) |
| # Order is important |
| alloc_list.append(mem_alloc_scratch_fast) |
| alloc_list.append(mem_alloc_scratch) |
| else: |
| mem_alloc_scratch = (arch.feature_map_storage_mem_area, set((MemType.Scratch, MemType.Scratch_fast))) |
| alloc_list.append(mem_alloc_scratch) |
| |
| for mem_area, mem_type_set in alloc_list: |
| tensor_allocation.allocate_tensors( |
| nng, |
| root_sg, |
| arch, |
| mem_area, |
| mem_type_set, |
| tensor_allocator=options.tensor_allocator, |
| verbose_allocation=options.verbose_allocation, |
| cpu_tensor_alignment=options.cpu_tensor_alignment, |
| hillclimb_max_iterations=options.hillclimb_max_iterations, |
| ) |
| |
| |
| class FastStorageComponentAllocator: |
| MAX_EXHAUSTIVE_LIFE_RANGE = 20 |
| MAX_EXHAUSTIVE_ITEMS = 20 |
| |
| def __init__(self, base_mem_usage, max_mem_usage, staging_limit): |
| self.base_mem_usage = base_mem_usage |
| self.max_mem_usage = max_mem_usage |
| self.staging_limit = staging_limit |
| self.lrs = [] |
| self.evicted = [] |
| self.curr_evicted = [] |
| self.remaining_total_size = [] |
| self.best_score = 0 |
| self.competing_tens_access = {} |
| |
| def allocate_exhaustive(self, ix, score): |
| # Favour tensors with highest element access (score) |
| if ix >= self.num_lrs: |
| if score > self.best_score: |
| self.best_score = score |
| self.evicted = self.curr_evicted.copy() |
| return |
| |
| lr = self.lrs[ix] |
| |
| # If adding the tensor size to the base mem usage doesn't exceed the staging limit anywhere on the lr time |
| # range, it can fit and the case where the tensor is included needs to be checked |
| can_fit = max(self.base_mem_usage[lr.start_time : lr.end_time + 1]) + lr.size <= self.staging_limit |
| if can_fit: |
| # Tensor can fit, add tensor element access to the score and check case where tensor is included |
| self.curr_evicted[ix] = False |
| self.base_mem_usage = self.update_mem_usage(self.base_mem_usage, lr, True) |
| self.allocate_exhaustive(ix + 1, score + self.competing_tens_access[lr.tensors[0]]) |
| self.base_mem_usage = self.update_mem_usage(self.base_mem_usage, lr, False) |
| |
| # If the max mem usage doesn't exceed the staging limit anywhere on the lr time range, it always fits and the |
| # case where the tensor is not included can be skipped |
| always_fits = max(self.max_mem_usage[lr.start_time : lr.end_time + 1]) <= self.staging_limit |
| if not always_fits: |
| # Tensor doesn't always fit, check case when tensor is not included |
| self.curr_evicted[ix] = True |
| self.max_mem_usage = self.update_mem_usage(self.max_mem_usage, lr, False) |
| self.allocate_exhaustive(ix + 1, score) |
| self.max_mem_usage = self.update_mem_usage(self.max_mem_usage, lr, True) |
| |
| @staticmethod |
| def update_mem_usage(mem_usage, lr, increase): |
| size = lr.size if increase else -lr.size |
| for t in range(lr.start_time, lr.end_time + 1): |
| mem_usage[t] += size |
| return mem_usage |
| |
| @staticmethod |
| def evict(lr, max_mem_usage, scratched_fms): |
| for t in range(lr.start_time, lr.end_time + 1): |
| max_mem_usage[t] -= lr.size |
| for tens in lr.tensors: |
| if tens in scratched_fms: |
| tens.mem_area = scratched_fms[tens][0] |
| tens.mem_type = scratched_fms[tens][1] |
| |
| @staticmethod |
| def keep(lr, base_mem_usage): |
| for t in range(lr.start_time, lr.end_time + 1): |
| base_mem_usage[t] += lr.size |
| |
| def allocate_component(self, lrs, max_mem, min_mem, scratched_fms, competing_tens_access, evicted_fms): |
| self.lrs = lrs |
| self.num_lrs = len(lrs) |
| self.evicted = [0] * self.num_lrs |
| self.curr_evicted = [0] * self.num_lrs |
| self.best_score = -1 |
| self.competing_tens_access = competing_tens_access |
| # Recursively evaluate all permutations of allocations of the lrs found in the component. |
| # For every permutation that fits within the staging_limit there is a score calculated. |
| # The permutation with the highest score will then be chosen. The score is calculated |
| # as the sum of the actual element access (ifm read and ofm write) for all the |
| # including tensors. So it is not necessary the tensor with the biggest size that ends up |
| # being included in the result. |
| self.allocate_exhaustive(0, 0) |
| # Optimal allocation has been found, move lrs accordingly |
| for i, lr in enumerate(self.lrs): |
| if self.evicted[i]: |
| self.evict(lr, max_mem, scratched_fms) |
| if lr not in evicted_fms: |
| evicted_fms.append(lr) |
| else: |
| self.keep(lr, min_mem) |
| if lr in evicted_fms: |
| evicted_fms.remove(lr) |
| |
| |
| def schedule_passes(nng: Graph, arch: ArchitectureFeatures, options, scheduler_options: SchedulerOptions): |
| """Entry point for the Scheduler""" |
| # Initialize CPU subgraphs |
| schedulers = dict() |
| # Initialize schedulers with max schedule. Only schedule NPU subgraphs |
| for sg in nng.subgraphs: |
| if sg.placement != PassPlacement.Npu: |
| # Create cascaded passes for CPU Ops |
| cascaded_passes = [] |
| for idx, ps in enumerate(sg.passes): |
| cps = CascadedPass( |
| ps.name, |
| SchedulingStrategy.WeightStream, |
| ps.inputs, |
| [], |
| ps.outputs, |
| [ps], |
| ps.placement, |
| False, |
| ) |
| |
| cps.time = idx |
| ps.cascade = cps |
| cascaded_passes.append(cps) |
| |
| sg.cascaded_passes = cascaded_passes |
| else: |
| # Npu subgraph - create schedule |
| scheduler = Scheduler(nng, sg, arch, scheduler_options) |
| schedulers[sg] = scheduler |
| |
| scheduler.create_scheduler_representation(arch) |
| sg.sched_ops = scheduler.sched_ops |
| |
| # Create the Max schedule template |
| max_schedule_template = scheduler.create_initial_schedule() |
| scheduler.max_schedule = max_schedule_template |
| |
| # Create the optimimised Max schedule |
| sg.schedule = max_schedule_template |
| scheduler.update_op_memory_snapshot(max_schedule_template) |
| opt_max_schedule = scheduler.propose_schedule_buffering(max_schedule_template, 1 << 32) |
| sg.schedule = opt_max_schedule |
| scheduler.update_op_memory_snapshot(opt_max_schedule) |
| |
| # Create Min schedule |
| min_schedule = scheduler.propose_minimal_schedule() |
| initial_sram_limit = scheduler_options.optimization_sram_limit |
| if scheduler_options.optimization_strategy == OptimizationStrategy.Size: |
| initial_sram_limit = scheduler.min_memory_req |
| |
| # Build cascades for Min schedule |
| scheduler.build_cascades_for_min_schedule(min_schedule, max_schedule_template, initial_sram_limit) |
| sg.schedule = min_schedule |
| scheduler.update_op_memory_snapshot(min_schedule) |
| |
| if scheduler_options.optimization_strategy == OptimizationStrategy.Performance: |
| # Create an optimized schedule |
| sg.schedule = scheduler.optimize_schedule( |
| min_schedule, opt_max_schedule, max_schedule_template, scheduler_options |
| ) |
| scheduler.update_op_memory_snapshot(sg.schedule) |
| |
| scheduler.apply_schedule(sg.schedule) |
| scheduler.use_fast_storage_for_feature_maps(sg.schedule, scheduler_options.optimization_sram_limit) |
| |
| if scheduler_options.optimization_strategy == OptimizationStrategy.Performance and scheduler.evicted_fms: |
| # It might be possible to gain performance by reducing |
| # weight buffer size and instead fit fms in fast storage |
| scheduler.optimize_weight_buffering_size(min_schedule, scheduler_options) |
| |
| if scheduler_options.verbose_schedule: |
| scheduler.print_schedule(sg.schedule) |
| |
| # Make a full live range calculation starting from the root sg |
| _update_memory_snapshot_for_all_npu_graphs(nng, arch, schedulers) |
| |
| # Evaluate schedule |
| _update_tensor_allocation(nng, arch, options) |