Debian Codegraph @

autoray/experimental/complexity_tracing.py

raw
1 """
2 Functionality for tracing through an autoray.lazy computation and estimating
3 the cost and scaling.
4
5 In the following there are ``cost_*`` functions that estimate the total cost
6 of a given operation, including sub-leading factors. There are also
7 `cost_scaling_*` functions that only consider the leading factor of the cost,
8 so that we can prime number decompose it and extract the scaling.
9 """
10
11 import math
12
13
14 def cost_tensordot(x):
15 x1, x2, axes = x.args
16 shape1, shape2 = x1.shape, x2.shape
17 cost = math.prod(shape1) * math.prod(shape2)
18 for d in axes[0]:
19 cost //= shape1[d]
20 return cost
21
22
23 cost_scaling_tensordot = cost_tensordot
24
25
26 def cost_qr(x):
27 (A,) = x.deps
28 shape = A.shape
29 m = max(shape)
30 n = min(shape)
31 return 2 * m * n**2 - (2 / 3) * n**3
32
33
34 def cost_svd(x):
35 (A,) = x.deps
36 shape = A.shape
37 m = max(shape)
38 n = min(shape)
39 return 4 * m * n**2 - (4 / 3) * n**3
40
41
42 def cost_eigh(x):
43 (A,) = x.deps
44 m = A.shape[0]
45 return 8 / 3 * m**3
46
47
48 def cost_scaling_linalg(x):
49 """Here we only care about the leading factor of the cost, which we need to
50 preserve so that we can prime number decompose it.
51 """
52 (A,) = x.deps
53 shape = A.shape
54 m = max(shape)
55 n = min(shape)
56 return m * n**2
57
58
59 cost_scaling_qr = cost_scaling_svd = cost_scaling_linalg
60
61
62 def cost_matmul(x):
63 A, B = x.deps
64 return A.shape[0] * A.shape[1] * B.shape[1]
65
66
67 cost_scaling_matmul = cost_matmul
68
69
70 def cost_einsum(x):
71 eq, *operands = x.args
72 lhs = eq.split("->")[0]
73 terms = lhs.split(",")
74 size_dict = {
75 ix: d
76 for term, x in zip(terms, operands)
77 for ix, d in zip(term, x.shape)
78 }
79 return math.prod(size_dict.values())
80
81
82 cost_scaling_einsum = cost_einsum
83
84
85 def cost_linear(x):
86 return math.prod(x.shape)
87
88
89 def cost_nothing(x):
90 return 0
91
92
93 COSTS = {
94 "qr": cost_qr,
95 "qr_stabilized": cost_qr,
96 "qr_stabilized_numba": cost_qr,
97 "svd": cost_svd,
98 "svd_truncated": cost_svd,
99 "svd_truncated_numba": cost_svd,
100 "svd_truncated_numpy": cost_svd,
101 "eigh": cost_eigh,
102 "linalg_eigh": cost_eigh,
103 "tensordot": cost_tensordot,
104 "matmul": cost_matmul,
105 "einsum": cost_einsum,
106 # other cheap ops
107 "mul": cost_linear,
108 "sum": cost_linear,
109 "add": cost_linear,
110 "neg": cost_linear,
111 "sqrt": cost_linear,
112 "cupy_sqrt": cost_linear,
113 "pow": cost_linear,
114 "truediv": cost_linear,
115 "log10": cost_linear,
116 "cupy_log10": cost_linear,
117 "norm": cost_linear,
118 "linalg_norm": cost_linear,
119 "reshape": cost_linear,
120 "conj": cost_linear,
121 "conjugate": cost_linear,
122 "cupy_conjugate": cost_linear,
123 "clip": cost_linear,
124 "transpose": cost_linear,
125 "absolute": cost_linear,
126 "trace": cost_linear,
127 "torch_transpose": cost_linear,
128 "clamp": cost_linear,
129 "getitem": cost_nothing,
130 "None": cost_nothing,
131 }
132
133
134 def cost_node(x, allow_missed=True):
135 f = x.fn_name
136 if f in COSTS:
137 return COSTS[f](x)
138 elif allow_missed:
139 return 0
140 else:
141 raise ValueError(f"Cost for {f} not implemented.")
142
143
144 def compute_cost(z, print_missed=True):
145 C = 0
146 missed = {}
147 for node in z.descend():
148 f = node.fn_name
149 if f in COSTS:
150 C += COSTS[f](node)
151 else:
152 missed[f] = missed.get(f, 0) + 1
153
154 if missed and print_missed:
155 import warnings
156
157 warnings.warn(f"Missed {missed} in cost computation.")
158
159 return C
160
161
162 COST_SCALINGS = {
163 "qr": cost_scaling_qr,
164 "qr_stabilized": cost_scaling_qr,
165 "qr_stabilized_numba": cost_scaling_qr,
166 "svd": cost_scaling_svd,
167 "svd_truncated": cost_scaling_svd,
168 "svd_truncated_numba": cost_scaling_svd,
169 "svd_truncated_numpy": cost_scaling_svd,
170 "eigh": cost_scaling_linalg,
171 "tensordot": cost_scaling_tensordot,
172 "matmul": cost_scaling_matmul,
173 "einsum": cost_scaling_einsum,
174 # other cheap ops
175 "mul": cost_linear,
176 "sum": cost_linear,
177 "add": cost_linear,
178 "neg": cost_linear,
179 "sqrt": cost_linear,
180 "pow": cost_linear,
181 "truediv": cost_linear,
182 "log10": cost_linear,
183 "norm": cost_linear,
184 "reshape": cost_linear,
185 "conj": cost_linear,
186 "conjugate": cost_linear,
187 "clip": cost_linear,
188 "transpose": cost_linear,
189 "absolute": cost_linear,
190 "trace": cost_linear,
191 "getitem": cost_nothing,
192 "None": cost_nothing,
193 }
194
195
196 def prime_factors(n) -> list[int]:
197 fs = []
198 if n <= 1:
199 return fs
200
201 while n % 2 == 0:
202 fs.append(2)
203 n = n // 2
204 for i in range(3, int(math.sqrt(n)) + 1, 2):
205 while n % i == 0:
206 fs.append(i)
207 n = n / i
208 if n > 2:
209 fs.append(n)
210 return fs
211
212
213 def is_prime(n: int) -> bool:
214 for i in range(int(n**0.5), 1, -2 if int(n**0.5) % 2 == 0 else -1):
215 if n % i == 0:
216 return False
217 return False if n in (0, 1) else True
218
219
220 def closest_prime(nt: int) -> int:
221 if is_prime(nt):
222 return nt
223 lower = None
224 higher = None
225 for i in range(nt if nt % 2 != 0 else nt - 1, 1, -2):
226 if is_prime(i):
227 lower = i
228 break
229 c = nt + 1
230 while higher is None:
231 if is_prime(c):
232 higher = c
233 else:
234 c += 2 if c % 2 != 0 else 1
235 return higher if lower is None or higher - nt < nt - lower else lower
236
237
238 def frequencies(it):
239 c = {}
240 for i in it:
241 c[i] = c.get(i, 0) + 1
242 return c
243
244
245 def compute_cost_scalings(z, factor_map, print_missed=True):
246 from autoray.lazy import descend
247
248 counts = {}
249 missed = {}
250
251 for node in descend(z):
252 f = node.fn_name
253
254 if f in COST_SCALINGS:
255 CS = COST_SCALINGS[f](node)
256 else:
257 missed[f] = missed.get(f, 0) + 1
258 continue
259
260 # group operations
261 key = (CS, f)
262 counts[key] = counts.get(key, 0) + 1
263
264 if missed and print_missed:
265 import warnings
266
267 warnings.warn(f"Missed {missed} in cost scaling computation.")
268
269 scalings = []
270
271 for key, freq in counts.items():
272 op = {
273 "cost": key[0],
274 "name": key[1],
275 "freq": freq,
276 }
277 pf = frequencies(prime_factors(op["cost"]))
278 for name, factor in factor_map.items():
279 op[name] = pf.pop(factor, 0)
280
281 if pf and print_missed:
282 import warnings
283
284 warnings.warn(
285 f"Missed prime factor(s) {pf} in cost scaling computation, "
286 f" for operation {op}."
287 )
288
289 scalings.append(op)
290
291 scalings.sort(key=lambda x: x["cost"], reverse=True)
292 return scalings