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 DiscreteInterval class."""
16 from dataclasses import dataclass
18 from .dataclass import secondary_field
19 from .discrete_load import DiscreteLoad
20 from .discrete_width import DiscreteWidth
23 # TODO: Can this be frozen?
25 class DiscreteInterval:
26 """Interval class with more computations available.
28 Along discrete form of width,
29 a MLR specific way for halving the interval is also included.
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.
34 The load values must be round.
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)."""
45 def __post_init__(self) -> None:
46 """Sort bounds by intended load, compute secondary quantities.
48 :raises RuntimeError: If a result used non-rounded load.
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
60 def __str__(self) -> str:
61 """Convert to a short human-readable string.
63 :returns: The short string.
67 f"lower_bound=({self.lower_bound}),upper_bound=({self.upper_bound})"
70 # TODO: Use "target" instad of "goal" in argument and variable names.
72 def width_in_goals(self, goal: DiscreteWidth) -> float:
73 """Return relative width as a multiple of the given goal (int form).
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.
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.
83 return int(self.discrete_width) / int(goal)
85 def middle(self, goal: DiscreteWidth) -> DiscreteLoad:
86 """Return new intended load (discrete form) in the middle.
88 All calculations are based on int forms.
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).
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.
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).
104 :param goal: Target width goal to use for uneven halving.
105 :type goal: DiscreteWidth
106 :returns: New load to use for bisecting.
108 :raises RuntimeError: If an internal inconsistency is detected.
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.
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
127 lo_width = self.discrete_width - hi_width
128 # We know lo_width > hi_width because we did not do the even split.
130 hi2_width = hi_width * 2
131 lo2_width = self.discrete_width - hi2_width
132 if lo2_width <= hi2_width:
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.
139 # Else lo2_width is more even and no larger than hi2_width.
140 return self.lower_bound + lo2_width