| 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 |