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:
6 # http://www.apache.org/licenses/LICENSE-2.0
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.
14 """Module defining BisectStrategy class."""
17 from dataclasses import dataclass
18 from typing import Optional, Tuple
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
28 class BisectStrategy(StrategyBase):
29 """Strategy to use when both bounds relevant to curent target are present.
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.
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.
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).
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.
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.
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."""
66 self, bounds: RelevantBounds
67 ) -> Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]]:
68 """Nominate a load candidate between bounds or extending from them.
70 The external search logic is offloaded into private methods.
71 If they return a truthy load, that is returned from here as well.
73 Only if the actual bisect is selected,
74 the per-selector expander is limited to the (smaller) new width.
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]]
81 if not bounds.clo or bounds.clo >= self.handler.max_load:
83 if not bounds.chi or bounds.chi <= self.handler.min_load:
85 interval = DiscreteInterval(bounds.clo, bounds.chi)
86 if interval.width_in_goals(self.target.discrete_width) <= 1.0:
88 bisect_load = interval.middle(self.target.discrete_width)
89 load, width = self._extend_lo(bounds, bisect_load)
91 self.expand_on_clo, self.expand_on_chi = False, True
92 self.debug(f"Preferring to extend down: {load}")
94 load, width = self._extend_hi(bounds, bisect_load)
96 self.expand_on_clo, self.expand_on_chi = True, False
97 self.debug(f"Preferring to extend up: {load}")
100 if self.not_worth(bounds=bounds, load=load):
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)
111 self, bounds: RelevantBounds, bisect_load: DiscreteLoad
112 ) -> Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]]:
113 """Compute load as if extending down, return it if preferred.
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.
123 # TODO: Simplify all the conditions or explain them better.
124 if not self.initial_upper_load:
126 if bisect_load >= self.initial_upper_load:
128 width = self.expander.get_width()
129 load = bounds.chi - width
130 load = self.handler.handle(
132 width=self.target.discrete_width,
138 if load <= bisect_load:
140 if load >= self.initial_upper_load:
142 if self.not_worth(bounds=bounds, load=load):
143 raise RuntimeError(f"Load not worth: {load}")
147 self, bounds: RelevantBounds, bisect_load: DiscreteLoad
148 ) -> Tuple[Optional[DiscreteLoad], Optional[DiscreteWidth]]:
149 """Compute load as if extending up, return it if preferred.
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.
159 # TODO: Simplify all the conditions or explain them better.
160 if not self.initial_lower_load:
162 if bisect_load <= self.initial_lower_load:
164 width = self.expander.get_width()
165 load = bounds.clo + width
166 load = self.handler.handle(
168 width=self.target.discrete_width,
174 if load >= bisect_load:
176 if load <= self.initial_lower_load:
178 if self.not_worth(bounds=bounds, load=load):
179 raise RuntimeError(f"Load not worth: {load}")
182 def won(self, bounds: RelevantBounds, load: DiscreteLoad) -> None:
183 """Expand width when appropriate.
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
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()