resources/libraries/python/MLRsearch/strategy/bisect.py

   1 # Copyright (c) 2023 Cisco and/or its affiliates.
   2 # Licensed under the Apache License, Version 2.0 (the "License");
   3 # you may not use this file except in compliance with the License.
   4 # You may obtain a copy of the License at:
   5 #
   6 #     http://www.apache.org/licenses/LICENSE-2.0
   7 #
   8 # Unless required by applicable law or agreed to in writing, software
   9 # distributed under the License is distributed on an "AS IS" BASIS,
  10 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  11 # See the License for the specific language governing permissions and
  12 # limitations under the License.
  13
  14 """Module defining BisectStrategy class."""
  15
  16
  17 from dataclasses import dataclass
  18 from typing import Optional, Tuple
  19
  20 from ..discrete_interval import DiscreteInterval
  21 from ..discrete_load import DiscreteLoad
  22 from ..discrete_width import DiscreteWidth
  23 from ..relevant_bounds import RelevantBounds
  24 from .base import StrategyBase
  25
  26
  27 @dataclass
  28 class BisectStrategy(StrategyBase):
  29     """Strategy to use when both bounds relevant to curent target are present.
  30
  31     Primarily, this strategy is there to perform internal search.
  32     As powers of two are fiendly to binary search,
  33     this strategy relies on the splitting logic described in DiscreteInterval.
  34
  35     The main reason why this class is so long is that a mere existence
  36     of a valid bound for the current target does not imply
  37     that bound is a good approximation of the final conditional throughput.
  38     The bound might become valid due to efforts of a strategy
  39     focusing on an entirely different search goal.
  40
  41     On the other hand, initial bounds may be better approximations,
  42     but they also may be bad approximations (for example
  43     when SUT behavior strongly depends on trial duration).
  44
  45     Based on comparison of existing current bounds to intial bounds,
  46     this strategy also mimics what would external search do
  47     (if the one current bound was missing and other initial bound was current).
  48     In case that load value is closer to appropriate inital bound
  49     (compared to how far the simple bisect between current bounds is),
  50     that load is nominated.
  51
  52     It turns out those "conditional" external search nominations
  53     are quite different from unconditional ones,
  54     at least when it comes to handling limits
  55     and tracking when width expansion should be applied.
  56     That is why that logic is here
  57     and not in some generic external search class.
  58     """
  59
  60     expand_on_clo: bool = False
  61     """If extending up, width should be expanded when load becomes clo."""
  62     expand_on_chi: bool = False
  63     """If extending down, width should be expanded when load becomes chi."""
  64
  65     def nominate(
  66         self, bounds: RelevantBounds
  67     ) -> Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]]:
  68         """Nominate a load candidate between bounds or extending from them.
  69
  70         The external search logic is offloaded into private methods.
  71         If they return a truthy load, that is returned from here as well.
  72
  73         Only if the actual bisect is selected,
  74         the per-selector expander is limited to the (smaller) new width.
  75
  76         :param bounds: Freshly updated bounds relevant for current target.
  77         :type bounds: RelevantBounds
  78         :returns: Two nones or candidate intended load and duration.
  79         :rtype: Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]]
  80         """
  81         if not bounds.clo or bounds.clo >= self.handler.max_load:
  82             return None, None
  83         if not bounds.chi or bounds.chi <= self.handler.min_load:
  84             return None, None
  85         interval = DiscreteInterval(bounds.clo, bounds.chi)
  86         if interval.width_in_goals(self.target.discrete_width) <= 1.0:
  87             return None, None
  88         bisect_load = interval.middle(self.target.discrete_width)
  89         load, width = self._extend_lo(bounds, bisect_load)
  90         if load:
  91             self.expand_on_clo, self.expand_on_chi = False, True
  92             self.debug(f"Preferring to extend down: {load}")
  93             return load, width
  94         load, width = self._extend_hi(bounds, bisect_load)
  95         if load:
  96             self.expand_on_clo, self.expand_on_chi = True, False
  97             self.debug(f"Preferring to extend up: {load}")
  98             return load, width
  99         load = bisect_load
 100         if self.not_worth(bounds=bounds, load=load):
 101             return None, None
 102         self.expand_on_clo, self.expand_on_chi = False, False
 103         self.debug(f"Preferring to bisect: {load}")
 104         width_lo = DiscreteInterval(bounds.clo, load).discrete_width
 105         width_hi = DiscreteInterval(load, bounds.chi).discrete_width
 106         width = min(width_lo, width_hi)
 107         self.expander.limit(width)
 108         return load, width
 109
 110     def _extend_lo(
 111         self, bounds: RelevantBounds, bisect_load: DiscreteLoad
 112     ) -> Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]]:
 113         """Compute load as if extending down, return it if preferred.
 114
 115         :param bounds: Freshly updated bounds relevant for current target.
 116         :param bisect_load: Load when bisection is preferred.
 117         :type bounds: RelevantBounds
 118         :type bisect_load: DiscreteLoad
 119         :returns: Two nones or candidate intended load and duration.
 120         :rtype: Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]]
 121         :raises RuntimeError: If an internal inconsistency is detected.
 122         """
 123         # TODO: Simplify all the conditions or explain them better.
 124         if not self.initial_upper_load:
 125             return None, None
 126         if bisect_load >= self.initial_upper_load:
 127             return None, None
 128         width = self.expander.get_width()
 129         load = bounds.chi - width
 130         load = self.handler.handle(
 131             load=load,
 132             width=self.target.discrete_width,
 133             clo=bounds.clo,
 134             chi=bounds.chi,
 135         )
 136         if not load:
 137             return None, None
 138         if load <= bisect_load:
 139             return None, None
 140         if load >= self.initial_upper_load:
 141             return None, None
 142         if self.not_worth(bounds=bounds, load=load):
 143             raise RuntimeError(f"Load not worth: {load}")
 144         return load, width
 145
 146     def _extend_hi(
 147         self, bounds: RelevantBounds, bisect_load: DiscreteLoad
 148     ) -> Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]]:
 149         """Compute load as if extending up, return it if preferred.
 150
 151         :param bounds: Freshly updated bounds relevant for current target.
 152         :param bisect_load: Load when bisection is preferred.
 153         :type bounds: RelevantBounds
 154         :type bisect_load: DiscreteLoad
 155         :returns: Two nones or candidate intended load and duration.
 156         :rtype: Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]]
 157         :raises RuntimeError: If an internal inconsistency is detected.
 158         """
 159         # TODO: Simplify all the conditions or explain them better.
 160         if not self.initial_lower_load:
 161             return None, None
 162         if bisect_load <= self.initial_lower_load:
 163             return None, None
 164         width = self.expander.get_width()
 165         load = bounds.clo + width
 166         load = self.handler.handle(
 167             load=load,
 168             width=self.target.discrete_width,
 169             clo=bounds.clo,
 170             chi=bounds.chi,
 171         )
 172         if not load:
 173             return None, None
 174         if load >= bisect_load:
 175             return None, None
 176         if load <= self.initial_lower_load:
 177             return None, None
 178         if self.not_worth(bounds=bounds, load=load):
 179             raise RuntimeError(f"Load not worth: {load}")
 180         return load, width
 181
 182     def won(self, bounds: RelevantBounds, load: DiscreteLoad) -> None:
 183         """Expand width when appropriate.
 184
 185         :param bounds: Freshly updated bounds relevant for current target.
 186         :param load: The current load, so strategy does not need to remember.
 187         :type bounds: RelevantBounds
 188         :type load: DiscreteLoad
 189         """
 190         if self.expand_on_clo and load == bounds.clo:
 191             self.expander.expand()
 192         elif self.expand_on_chi and load == bounds.chi:
 193             self.expander.expand()