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,
30 T_END_CHOICE,
31 LMAX,
32 NITER,
33 LAM3,
1a1e473Add auto-fill: work through the parameter space on an idle machineJeremy Magland 34 type DiscreteChoice,
35} from './options.ts';
36import { DEFAULT_GEOMETRY_KEY } from '../geom/registry.ts';
c2317d0Fill the cache from the command line, without a browserJeremy Magland 37import { APP_NAME, FORMAT_VERSION, type CacheSpec } from './spec.ts';
39export interface AutoTarget {
40 model: string;
41 params: Params;
42 geometry: string;
43 geometryParams: Params;
44 /** How many knobs differ from the app's defaults. */
45 distance: number;
46}
48/**
49 * Every combination of a choice list, each with the number of entries that
50 * differ from their default. A key present in `pinned` takes that value in
51 * every combination and never counts toward the distance.
52 */
53function combos(
54 choices: DiscreteChoice[],
55 pinned: Params = {},
56): { values: Params; distance: number }[] {
57 let out = [{ values: { ...pinned }, distance: 0 }];
58 for (const c of choices) {
59 if (c.key in pinned) continue;
60 const next: typeof out = [];
61 for (const acc of out) {
62 for (const v of c.values) {
63 next.push({
64 values: { ...acc.values, [c.key]: v },
65 distance: acc.distance + (v === c.value ? 0 : 1),
66 });
67 }
68 }
69 out = next;
70 }
71 return out;
72}
74/** The surfaces to survey, each with its distance from the default shape:
75 * one for being a different geometry, one more per non-default parameter. */
76function geometryOptions(): { geometry: string; params: Params; distance: number }[] {
77 const out: { geometry: string; params: Params; distance: number }[] = [];
78 for (const [key, choices] of Object.entries(GEOMETRY_CHOICES)) {
79 for (const c of combos(choices)) {
80 // The ellipsoid with all axes 1 *is* the unit sphere, which the sphere
81 // geometry already covers. Computing it would fill a second hash with
82 // the same problem, so it is left out — 228 runs saved.
83 if (key === 'ellipsoid' && c.values.ax === 1 && c.values.ay === 1 && c.values.az === 1) {
84 continue;
85 }
86 out.push({
87 geometry: key,
88 params: c.values,
89 distance: (key === DEFAULT_GEOMETRY_KEY ? 0 : 1) + c.distance,
90 });
91 }
92 }
93 return out;
94}
96/** Every solution the walk will ever compute, unordered. */
97export function enumerateTargets(): AutoTarget[] {
98 const geometries = geometryOptions();
99 const out: AutoTarget[] = [];
100 for (const [modelKey, choices] of Object.entries(MODEL_CHOICES)) {
101 const modelDistance = modelKey === DEFAULT_MODEL_KEY ? 0 : 1;
102 for (const p of combos(choices, { dt: AUTO_DT })) {
103 for (const g of geometries) {
104 out.push({
105 model: modelKey,
106 params: p.values,
107 geometry: g.geometry,
108 geometryParams: g.params,
109 distance: modelDistance + p.distance + g.distance,
110 });
111 }
112 }
113 }
114 return out;
115}
118 * The solution a target names. The seed is the pinned one, and the end time is
119 * the longest listed: a run reaching it passes through every shorter one and
120 * contributes those on the way, so one run fills the whole chain. The page
121 * sets its dropdowns from this rather than deciding the same thing twice.
122 */
123export function specForTarget(target: AutoTarget): CacheSpec {
124 return {
125 app: APP_NAME,
126 formatVersion: FORMAT_VERSION,
127 model: target.model,
128 params: { ...target.params },
129 geometry: target.geometry,
130 geometryParams: { ...target.geometryParams },
131 lmax: LMAX,
132 niter: NITER,
133 lam3: LAM3,
134 seed: AUTO_SEED,
135 tEnd: Math.max(...T_END_CHOICE.values),
136 };
137}
140 * The walk order: by distance, randomly within each distance. Shuffling the
141 * whole list and then sorting by distance gives exactly that, since Array's
142 * sort is stable — the shuffle survives as the within-distance order.
143 */
144export function autoOrder(rand: () => number = Math.random): AutoTarget[] {
145 const all = enumerateTargets();
146 for (let i = all.length - 1; i > 0; i--) {
147 const j = Math.floor(rand() * (i + 1));
148 [all[i], all[j]] = [all[j], all[i]];
149 }
150 all.sort((a, b) => a.distance - b.distance);
151 return all;
152}