161 lines
6.7 KiB
Python
161 lines
6.7 KiB
Python
#!/usr/bin/env python3
|
|
"""attack-f6 ranking: read the scan CSVs of the harness, rank the programs by an exact op-count proxy (per-family
|
|
weights from `attack-f6 micro`) and by the measured time column, print the distribution, write the seed lists.
|
|
|
|
rank.py --scan scan-0.csv scan-50000.csv --weights "add=11,sub=10,..." [--column cold_min_ms] [--top 50]
|
|
[--out-prefix worst] [--regress]
|
|
|
|
The proxy of program p is sum over families F of w_F x (8 x base_F(p) + 8 x 27 x shadow_F(p)): every base instruction
|
|
runs 8 times per hash, every shadow instruction 216 times. Loads carry no weight (every class v4 program has 16).
|
|
"""
|
|
import argparse
|
|
import csv
|
|
import math
|
|
import sys
|
|
|
|
FAMILIES = ["add", "sub", "mul", "mulhi", "xor", "or", "rotl", "rotr", "mad", "shfl"]
|
|
ITER = 8
|
|
REPS = 27
|
|
|
|
|
|
def read(paths):
|
|
rows = []
|
|
for p in paths:
|
|
with open(p) as f:
|
|
for r in csv.DictReader(f):
|
|
rows.append(r)
|
|
return rows
|
|
|
|
|
|
def proxy(r, w):
|
|
s = 0.0
|
|
for f in FAMILIES:
|
|
s += w[f] * (ITER * int(r["base_" + f]) + ITER * REPS * int(r["shadow_" + f]))
|
|
return s
|
|
|
|
|
|
def pct(sorted_vals, q):
|
|
if not sorted_vals:
|
|
return float("nan")
|
|
k = min(len(sorted_vals) - 1, max(0, int(math.ceil(q * len(sorted_vals))) - 1))
|
|
return sorted_vals[k]
|
|
|
|
|
|
def dist(rows, col, label):
|
|
vals = sorted((float(r[col]), r["seed"]) for r in rows if r[col] not in ("", "0.000"))
|
|
if not vals:
|
|
print(f"{label}: no values in {col}")
|
|
return
|
|
v = [x for x, _ in vals]
|
|
n = len(v)
|
|
med = v[n // 2]
|
|
print(f"| {label} ({col}, n = {n:,}) | min {v[0]:.3f} ({vals[0][1]}) | median {med:.3f} | p99 {pct(v, 0.99):.3f} | p99.9 {pct(v, 0.999):.3f} | max {v[-1]:.3f} ({vals[-1][1]}) |")
|
|
return vals
|
|
|
|
|
|
def regress(rows, col):
|
|
"""Least squares of col on the per-hash family counts (ordinary normal equations; 10 unknowns and an intercept)."""
|
|
xs, ys = [], []
|
|
for r in rows:
|
|
if r[col] in ("", "0.000"):
|
|
continue
|
|
# no intercept: every class v4 program has 48 non-load base and 256 shadow instructions, so the total
|
|
# executed count is the same for all and an intercept would be collinear with it
|
|
xs.append([ITER * int(r["base_" + f]) + ITER * REPS * int(r["shadow_" + f]) for f in FAMILIES])
|
|
ys.append(float(r[col]))
|
|
k = len(FAMILIES)
|
|
ata = [[0.0] * k for _ in range(k)]
|
|
aty = [0.0] * k
|
|
for x, y in zip(xs, ys):
|
|
for i in range(k):
|
|
aty[i] += x[i] * y
|
|
for j in range(k):
|
|
ata[i][j] += x[i] * x[j]
|
|
# Gauss-Jordan
|
|
m = [row[:] + [aty[i]] for i, row in enumerate(ata)]
|
|
for c in range(k):
|
|
piv = max(range(c, k), key=lambda r: abs(m[r][c]))
|
|
m[c], m[piv] = m[piv], m[c]
|
|
if abs(m[c][c]) < 1e-12:
|
|
print("regression: singular")
|
|
return None
|
|
d = m[c][c]
|
|
m[c] = [v / d for v in m[c]]
|
|
for r in range(k):
|
|
if r != c and m[r][c] != 0.0:
|
|
f = m[r][c]
|
|
m[r] = [a - f * b for a, b in zip(m[r], m[c])]
|
|
coef = [m[i][k] for i in range(k)]
|
|
pred = [sum(c * xi for c, xi in zip(coef, x)) for x in xs]
|
|
ybar = sum(ys) / len(ys)
|
|
ss_res = sum((y - p) ** 2 for y, p in zip(ys, pred))
|
|
ss_tot = sum((y - ybar) ** 2 for y in ys)
|
|
r2 = 1 - ss_res / ss_tot if ss_tot > 0 else float("nan")
|
|
print(f"regression of {col} on per-hash family counts, no intercept (n = {len(ys):,}): R^2 {r2:.3f}")
|
|
print("| Family | ms per 1,000 executed instrs (regression) | us per 1,000 |")
|
|
print("|---|---|---|")
|
|
for f, c in zip(FAMILIES, coef):
|
|
print(f"| {f} | {c * 1000:.4f} | {c * 1e6:.2f} |")
|
|
return dict(zip(FAMILIES, coef))
|
|
|
|
|
|
def main():
|
|
ap = argparse.ArgumentParser()
|
|
ap.add_argument("--scan", nargs="+", required=True)
|
|
ap.add_argument("--weights", default="", help="add=us,sub=us,... per 1,000 instrs (from attack-f6 micro); default 1 each")
|
|
ap.add_argument("--column", default="cold_min_ms")
|
|
ap.add_argument("--top", type=int, default=50)
|
|
ap.add_argument("--out-prefix", default="")
|
|
ap.add_argument("--regress", action="store_true")
|
|
ap.add_argument("--label", default="scan")
|
|
a = ap.parse_args()
|
|
rows = read(a.scan)
|
|
print(f"{len(rows):,} programs read from {', '.join(a.scan)}")
|
|
w = {f: 1.0 for f in FAMILIES}
|
|
if a.weights:
|
|
for kv in a.weights.split(","):
|
|
k, v = kv.split("=")
|
|
w[k.strip()] = float(v)
|
|
for r in rows:
|
|
r["_proxy"] = proxy(r, w)
|
|
px = sorted(r["_proxy"] for r in rows)
|
|
print(f"| proxy (weighted instrs, n = {len(px):,}) | min {px[0]:.0f} | median {px[len(px) // 2]:.0f} | p99 {pct(px, 0.99):.0f} | p99.9 {pct(px, 0.999):.0f} | max {px[-1]:.0f} |")
|
|
vals = dist(rows, a.column, a.label)
|
|
if a.regress:
|
|
regress(rows, a.column)
|
|
by_proxy = sorted(rows, key=lambda r: -r["_proxy"])[: a.top]
|
|
by_time = sorted((r for r in rows if r[a.column] not in ("", "0.000")), key=lambda r: -float(r[a.column]))[: a.top]
|
|
pset = {r["seed"] for r in by_proxy}
|
|
tset = {r["seed"] for r in by_time}
|
|
print(f"worst {a.top} by proxy and worst {a.top} by {a.column}: {len(pset & tset)} seeds in both")
|
|
if vals:
|
|
# rank correlation (Spearman) between proxy and time over all rows
|
|
rp = {r["seed"]: i for i, r in enumerate(sorted(rows, key=lambda r: r["_proxy"]))}
|
|
rt = {s: i for i, (_, s) in enumerate(vals)}
|
|
common = [s for s in rt if s in rp]
|
|
n = len(common)
|
|
d2 = sum((rp[s] - rt[s]) ** 2 for s in common)
|
|
rho = 1 - 6 * d2 / (n * (n * n - 1)) if n > 2 else float("nan")
|
|
print(f"Spearman rank correlation proxy vs {a.column}: {rho:.3f} over {n:,}")
|
|
print(f"\nworst {a.top} by proxy (seed, proxy, {a.column}, shadow mix):")
|
|
for r in by_proxy[:10]:
|
|
print(f" {r['seed']} {r['_proxy']:.0f} {r[a.column]} " + " ".join(f"{f}={r['shadow_' + f]}" for f in FAMILIES))
|
|
print(f"worst {a.top} by {a.column}:")
|
|
for r in by_time[:10]:
|
|
print(f" {r['seed']} {r[a.column]} proxy {r['_proxy']:.0f} " + " ".join(f"{f}={r['shadow_' + f]}" for f in FAMILIES))
|
|
if a.out_prefix:
|
|
with open(a.out_prefix + "-proxy.txt", "w") as f:
|
|
f.write("\n".join(r["seed"] for r in by_proxy) + "\n")
|
|
with open(a.out_prefix + "-time.txt", "w") as f:
|
|
f.write("\n".join(r["seed"] for r in by_time) + "\n")
|
|
with open(a.out_prefix + "-union.txt", "w") as f:
|
|
seen = []
|
|
for r in by_proxy + by_time:
|
|
if r["seed"] not in seen:
|
|
seen.append(r["seed"])
|
|
f.write("\n".join(seen) + "\n")
|
|
print(f"wrote {a.out_prefix}-proxy.txt, -time.txt, -union.txt ({len(seen)} seeds)")
|
|
|
|
|
|
if __name__ == "__main__":
|
|
main()
|