1/**
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 * The model is not one of those knobs. Someone who came for Allen–Cahn starts
16 * at its defaults, not at Schnakenberg's, so the three models are three
17 * origins rather than one origin and two deviations from it, and each is
18 * surrounded before any of them is explored far.
19 *
20 * Within a distance the order is random, and that is the whole coordination
21 * mechanism between machines: several idle browsers walking the same tiers in
22 * different orders, each skipping what it finds already cached, rarely
23 * duplicate each other's work and need no coordinator, no queue and no
24 * knowledge of one another.
25 *
26 * The seed and dt are pinned rather than surveyed (see AUTO_SEED / AUTO_DT).
27 */
28import type { Params } from '../mgpu/registry.ts';
29import {
30 MODEL_CHOICES,
31 GEOMETRY_CHOICES,
32 AUTO_DT,
33 AUTO_SEED,
34 T_END_CHOICE,
35 LMAX,
36 NITER,
37 LAM3,
38 type DiscreteChoice,
39} from './options.ts';
40import { DEFAULT_GEOMETRY_KEY } from '../geom/registry.ts';
41import { APP_NAME, FORMAT_VERSION, type CacheSpec } from './spec.ts';
43export interface AutoTarget {
44 model: string;
45 params: Params;
46 geometry: string;
47 geometryParams: Params;
48 /** How many knobs differ from this model's defaults — the model itself
49 * not being one of them. */
50 distance: number;
51}
53/**
54 * Every combination of a choice list, each with the number of entries that
55 * differ from their default. A key present in `pinned` takes that value in
56 * every combination and never counts toward the distance.
57 */
58function combos(
59 choices: DiscreteChoice[],
60 pinned: Params = {},
61): { values: Params; distance: number }[] {
62 let out = [{ values: { ...pinned }, distance: 0 }];
63 for (const c of choices) {
64 if (c.key in pinned) continue;
65 const next: typeof out = [];
66 for (const acc of out) {
67 for (const v of c.values) {
68 next.push({
69 values: { ...acc.values, [c.key]: v },
70 distance: acc.distance + (v === c.value ? 0 : 1),
71 });
72 }
73 }
74 out = next;
75 }
76 return out;
77}
79/** The surfaces to survey, each with its distance from the default shape:
80 * one for being a different geometry, one more per non-default parameter. */
81function geometryOptions(): { geometry: string; params: Params; distance: number }[] {
82 const out: { geometry: string; params: Params; distance: number }[] = [];
83 for (const [key, choices] of Object.entries(GEOMETRY_CHOICES)) {
84 for (const c of combos(choices)) {
85 // The ellipsoid with all axes 1 *is* the unit sphere, which the sphere
86 // geometry already covers. Computing it would fill a second hash with
87 // the same problem, so it is left out — 228 runs saved.
88 if (key === 'ellipsoid' && c.values.ax === 1 && c.values.ay === 1 && c.values.az === 1) {
89 continue;
90 }
91 out.push({
92 geometry: key,
93 params: c.values,
94 distance: (key === DEFAULT_GEOMETRY_KEY ? 0 : 1) + c.distance,
95 });
96 }
97 }
98 return out;
99}
101/** Every solution the walk will ever compute, unordered. */
102export function enumerateTargets(): AutoTarget[] {
103 const geometries = geometryOptions();
104 const out: AutoTarget[] = [];
105 for (const [modelKey, choices] of Object.entries(MODEL_CHOICES)) {
106 for (const p of combos(choices, { dt: AUTO_DT })) {
107 for (const g of geometries) {
108 out.push({
109 model: modelKey,
110 params: p.values,
111 geometry: g.geometry,
112 geometryParams: g.params,
113 distance: p.distance + g.distance,
114 });
115 }
116 }
117 }
118 return out;
119}
121/**
122 * The solution a target names. The seed is the pinned one, and the end time is
123 * the longest listed: a run reaching it passes through every shorter one and
124 * contributes those on the way, so one run fills the whole chain. The page
125 * sets its dropdowns from this rather than deciding the same thing twice.
126 */
127export function specForTarget(target: AutoTarget): CacheSpec {
128 return {
129 app: APP_NAME,
130 formatVersion: FORMAT_VERSION,
131 model: target.model,
132 params: { ...target.params },
133 geometry: target.geometry,
134 geometryParams: { ...target.geometryParams },
135 lmax: LMAX,
136 niter: NITER,
137 lam3: LAM3,
138 seed: AUTO_SEED,
139 tEnd: Math.max(...T_END_CHOICE.values),
140 };
141}
143/**
144 * The walk order: by distance, randomly within each distance. Shuffling the
145 * whole list and then sorting by distance gives exactly that, since Array's
146 * sort is stable — the shuffle survives as the within-distance order.
147 */
148export function autoOrder(rand: () => number = Math.random): AutoTarget[] {
149 const all = enumerateTargets();
150 for (let i = all.length - 1; i > 0; i--) {
151 const j = Math.floor(rand() * (i + 1));
152 [all[i], all[j]] = [all[j], all[i]];
153 }
154 all.sort((a, b) => a.distance - b.distance);
155 return all;
156}