resources/libraries/python/MLRsearch/discrete_interval.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 DiscreteInterval class."""
  15
  16 from dataclasses import dataclass
  17
  18 from .dataclass import secondary_field
  19 from .discrete_load import DiscreteLoad
  20 from .discrete_width import DiscreteWidth
  21
  22
  23 # TODO: Can this be frozen?
  24 @dataclass
  25 class DiscreteInterval:
  26     """Interval class with more computations available.
  27
  28     Along discrete form of width,
  29     a MLR specific way for halving the interval is also included.
  30
  31     The two primary field values do not have to be valid relevant bounds,
  32     but at the end of the search, they usually are.
  33
  34     The load values must be round.
  35     """
  36
  37     lower_bound: DiscreteLoad
  38     """Value for the lower intended load (or load stats or similar)."""
  39     upper_bound: DiscreteLoad
  40     """Value for the higher intended load (or load stats or similar)."""
  41     # Primary fields above, derived below.
  42     discrete_width: DiscreteWidth = secondary_field()
  43     """Discrete width between intended loads (upper_bound minus lower_bound)."""
  44
  45     def __post_init__(self) -> None:
  46         """Sort bounds by intended load, compute secondary quantities.
  47
  48         :raises RuntimeError: If a result used non-rounded load.
  49         """
  50         if not self.lower_bound.is_round:
  51             raise RuntimeError(f"Non-round lower bound: {self.lower_bound!r}")
  52         if not self.upper_bound.is_round:
  53             raise RuntimeError(f"Non-round upper bound: {self.upper_bound!r}")
  54         if self.lower_bound > self.upper_bound:
  55             tmp = self.lower_bound
  56             self.lower_bound = self.upper_bound
  57             self.upper_bound = tmp
  58         self.discrete_width = self.upper_bound - self.lower_bound
  59
  60     def __str__(self) -> str:
  61         """Convert to a short human-readable string.
  62
  63         :returns: The short string.
  64         :rtype: str
  65         """
  66         return (
  67             f"lower_bound=({self.lower_bound}),upper_bound=({self.upper_bound})"
  68         )
  69
  70     # TODO: Use "target" instad of "goal" in argument and variable names.
  71
  72     def width_in_goals(self, goal: DiscreteWidth) -> float:
  73         """Return relative width as a multiple of the given goal (int form).
  74
  75         Integer forms are used for computation, safe as loads are rounded.
  76         The result is a float, as self int may not be divisible by goal int.
  77
  78         :param goal: A relative width amount to be used as a unit.
  79         :type goal: DiscreteWidth
  80         :returns: Self width in multiples of (integer form of) goal width.
  81         :rtype: float
  82         """
  83         return int(self.discrete_width) / int(goal)
  84
  85     def middle(self, goal: DiscreteWidth) -> DiscreteLoad:
  86         """Return new intended load (discrete form) in the middle.
  87
  88         All calculations are based on int forms.
  89
  90         One of the halfs is rounded to a power-of-two multiple of the goal.
  91         The power that leads to most even split is used.
  92         Lower width is the smaller one (if not exactly even).
  93
  94         This approach prefers lower loads (to remain conservative) and can save
  95         some measurements (when all middle measurements have high loss).
  96         Note that when competing with external search from above,
  97         that search is already likely to produce widths that are
  98         power-of-two multiples of the target width.
  99
 100         If the interval width is one goal (or less), RuntimeError is raised.
 101         If the interval width is between one and two goals (not including),
 102         a more even split is attempted (using half the goal value).
 103
 104         :param goal: Target width goal to use for uneven halving.
 105         :type goal: DiscreteWidth
 106         :returns: New load to use for bisecting.
 107         :rtype: DiscreteLoad
 108         :raises RuntimeError: If an internal inconsistency is detected.
 109         """
 110         int_self, int_goal = int(self.discrete_width), int(goal)
 111         if int_self <= int_goal:
 112             raise RuntimeError(f"Do not halve small enough interval: {self!r}")
 113         if int_self == 2 * int_goal:
 114             # Even split, return here simplifies the while loop below.
 115             return self.lower_bound + goal
 116         if int_self < 2 * int_goal:
 117             # This can only happen when int_goal >= 2.
 118             # In this case, we do not have good enough split at this width goal,
 119             # but maybe this is not the final target, so we can attempt
 120             # a split at half width goal.
 121             if not int_goal % 2:
 122                 return self.middle(goal=goal.half_rounded_down())
 123             # Odd int_goal, so this must by the last phase. Do even split.
 124             lo_width = self.discrete_width.half_rounded_down()
 125             return self.lower_bound + lo_width
 126         hi_width = goal
 127         lo_width = self.discrete_width - hi_width
 128         # We know lo_width > hi_width because we did not do the even split.
 129         while 1:
 130             hi2_width = hi_width * 2
 131             lo2_width = self.discrete_width - hi2_width
 132             if lo2_width <= hi2_width:
 133                 break
 134             hi_width, lo_width = hi2_width, lo2_width
 135         # Which of the two options is more even? Product decides.
 136         if int(hi_width) * int(lo_width) > int(hi2_width) * int(lo2_width):
 137             # Previous attempt was more even, but hi_width was the smaller one.
 138             lo2_width = hi_width
 139         # Else lo2_width is more even and no larger than hi2_width.
 140         return self.lower_bound + lo2_width