2 * The auto-fill walk: which solutions to compute on an idle machine, and in
3 * what order.
4 *
5 * The whole space is about 8,000 runs — roughly three GPU-weeks — so it is
6 * exhaustible in principle, and the question is only what to do first.
7 * Demand for it is nothing like uniform: a visitor starts at the defaults and
8 * changes one dropdown at a time, so the chance that a combination is ever
9 * requested falls off steeply with the number of knobs that differ from the
10 * defaults. The walk therefore proceeds by that distance — every one-knob
11 * deviation before any two-knob one — which fills the region people actually
12 * ask for within a day rather than a month, and still covers everything in
13 * the limit.
14 *
15 * Within a distance the order is random, and that is the whole coordination
16 * mechanism between machines: several idle browsers walking the same tiers in
17 * different orders, each skipping what it finds already cached, rarely
18 * duplicate each other's work and need no coordinator, no queue and no
19 * knowledge of one another.
20 *
21 * The seed and dt are pinned rather than surveyed (see AUTO_SEED / AUTO_DT).
22 */
23import type { Params } from '../mgpu/registry.ts';
24import {
25 MODEL_CHOICES,
26 DEFAULT_MODEL_KEY,
27 GEOMETRY_CHOICES,
28 AUTO_DT,
29 type DiscreteChoice,
30} from './options.ts';
31import { DEFAULT_GEOMETRY_KEY } from '../geom/registry.ts';
33export interface AutoTarget {
34 model: string;
35 params: Params;
36 geometry: string;
37 geometryParams: Params;
38 /** How many knobs differ from the app's defaults. */
39 distance: number;
40}
42/**
43 * Every combination of a choice list, each with the number of entries that
44 * differ from their default. A key present in `pinned` takes that value in
45 * every combination and never counts toward the distance.
46 */
47function combos(
48 choices: DiscreteChoice[],
49 pinned: Params = {},
50): { values: Params; distance: number }[] {
51 let out = [{ values: { ...pinned }, distance: 0 }];
52 for (const c of choices) {
53 if (c.key in pinned) continue;
54 const next: typeof out = [];
55 for (const acc of out) {
56 for (const v of c.values) {
57 next.push({
58 values: { ...acc.values, [c.key]: v },
59 distance: acc.distance + (v === c.value ? 0 : 1),
60 });
61 }
62 }
63 out = next;
64 }
65 return out;
66}
68/** The surfaces to survey, each with its distance from the default shape:
69 * one for being a different geometry, one more per non-default parameter. */
70function geometryOptions(): { geometry: string; params: Params; distance: number }[] {
71 const out: { geometry: string; params: Params; distance: number }[] = [];
72 for (const [key, choices] of Object.entries(GEOMETRY_CHOICES)) {
73 for (const c of combos(choices)) {
74 // The ellipsoid with all axes 1 *is* the unit sphere, which the sphere
75 // geometry already covers. Computing it would fill a second hash with
76 // the same problem, so it is left out — 228 runs saved.
77 if (key === 'ellipsoid' && c.values.ax === 1 && c.values.ay === 1 && c.values.az === 1) {
78 continue;
79 }
80 out.push({
81 geometry: key,
82 params: c.values,
83 distance: (key === DEFAULT_GEOMETRY_KEY ? 0 : 1) + c.distance,
84 });
85 }
86 }
87 return out;
88}
90/** Every solution the walk will ever compute, unordered. */
91export function enumerateTargets(): AutoTarget[] {
92 const geometries = geometryOptions();
93 const out: AutoTarget[] = [];
94 for (const [modelKey, choices] of Object.entries(MODEL_CHOICES)) {
95 const modelDistance = modelKey === DEFAULT_MODEL_KEY ? 0 : 1;
96 for (const p of combos(choices, { dt: AUTO_DT })) {
97 for (const g of geometries) {
98 out.push({
99 model: modelKey,
100 params: p.values,
101 geometry: g.geometry,
102 geometryParams: g.params,
103 distance: modelDistance + p.distance + g.distance,
104 });
105 }
106 }
107 }
108 return out;
109}
111/**
112 * The walk order: by distance, randomly within each distance. Shuffling the
113 * whole list and then sorting by distance gives exactly that, since Array's
114 * sort is stable — the shuffle survives as the within-distance order.
115 */
116export function autoOrder(rand: () => number = Math.random): AutoTarget[] {
117 const all = enumerateTargets();
118 for (let i = all.length - 1; i > 0; i--) {
119 const j = Math.floor(rand() * (i + 1));
120 [all[i], all[j]] = [all[j], all[i]];
121 }
122 all.sort((a, b) => a.distance - b.distance);
123 return all;
124}