nx_select_joint.nx source
↩ module page · 340 lines · 12884 B
1// nx_select_joint.nx -- joint DAG variant selector (MVP: 2-node).
2//
3// SA-5 partial milestone of NISHI_SELF_ASSEMBLY_ROADMAP.md. Full N-
4// node ILP solver deferred to next session; this MVP demonstrates the
5// LOAD-BEARING property: layout compatibility across an edge can
6// force the solver to pick a NON-LOCALLY-OPTIMAL variant at one
7// node to enable a cheaper variant at another node.
8//
9// Selection function (joint, 2-node):
10//
11// S_joint(G, P, K, π) = argmin_{(a, b)}
12// cost(a, P, K, π) + cost(b, P, K, π) + transfer_cost(a, b)
13// s.t. requires(a) ⊆ P AND requires(b) ⊆ P
14// out_layout(a) compatible-with in_layout(b)
15//
16// transfer_cost(a, b) = 0 when out_layout(a) == in_layout(b)
17// (V1; SA-6 will add real transform-bytes cost)
18//
19// MVP scope (this session):
20// - Exactly 2 nodes (producer -> consumer); 1 edge
21// - Exhaustive search over all (a, b) candidate pairs
22// - Layout-compat edge constraint (nx_layout_compatible)
23// - Returns selected indices via *i64 array out[0], out[1]
24//
25// Deferred:
26// - N-node DAGs with topological order + chain composition (next session)
27// - ILP solver for hard cases (SA-6+)
28// - Greedy + backtrack heuristic for large DAGs (SA-7)
29// - Real transfer_cost from edge bandwidth (SA-6 with nx_calibrate
30// emitting bytes-on-wire estimates)
31// - Cross-edge layout transform variants (SA-7)
32//
33// genealogy_id: petabricks_2009 + halide_schedule_search_2019 +
34// polly_loop_polyhedral + cardinal_2026-05-19_self_assembly
35// lineage_id: substrate_select_joint_v1
36//
37// nx_capability_manifest:
38// variant_class: capability_select_joint
39// variant_id: capability_select_joint_v1_two_node_exhaustive
40// requires_isa: [rv64imac, x86_64]
41// requires_syscalls: [mmap]
42// requires_ram_min_b: 4096
43// tier_floor: NX_TIER_MOBILE
44// tier_ceiling: NX_TIER_HPC
45// cost_model:
46// flops_per_n: 1.0 // ~N_a * N_b candidate pairs probed
47// bytes_per_n: 8.0 // pointer per probe
48// syscalls_per_n: 0.0
49// adversary_class: THREAT_AI_ADVERSARY
50//
51// nx_safety_envelope:
52// intended_use: "Joint variant selector across 2-node DAG;
53// enforces layout-compatibility edge constraint"
54// sil_target: SIL2
55// evidence: [exhaustive_no_skipped_pairs, layout_compat_enforced,
56// pure_function_no_side_effects]
57// verdict: NOT_YET_EVALUATED
58
59import "nx_syscalls.nx"
60import "nx_probe.nx"
61import "nx_calibrate.nx"
62import "nx_select.nx"
63const NX_MAGIC_9223372036854775000: i64 = 9223372036854775000
64
65// ===== Joint-selection verdicts ==================================
66const NX_SEL_JOINT_OK: i64 = 0
67const NX_SEL_JOINT_BAD_INPUT: i64 = -1
68const NX_SEL_JOINT_NO_FEASIBLE_PAIR: i64 = -2
69
70// ===== Joint-DAG node ============================================
71// A node holds an array of candidate manifest pointers (same shape
72// the single-class selector consumes). n_candidates is the per-node
73// candidate count; can vary per node.
74struct NxJointNode {
75 variant_class: i64,
76 manifest_ptrs: *i64, // *i64 array of i64-cast NxManifest pointers
77 n_candidates: i64,
78}
79
80// ===== 2-node joint selection =====================================
81// out_selection is a *i64 of length 2: out_selection[0] = index into
82// node_a's candidates; out_selection[1] = index into node_b's
83// candidates. -1 if no feasible pair found.
84//
85// Returns NX_SEL_JOINT_OK on success, error verdict otherwise.
86
87func nx_select_joint_2node(
88 node_a: *NxJointNode,
89 node_b: *NxJointNode,
90 probe: *NxProbeRecord,
91 inferred_tier: i64,
92 probe_ram_proxy: i64,
93 probe_isa_ext_mask: i64,
94 policy: *NxPolicy,
95 out_selection: *i64
96) -> i64 {
97 if (node_a as i64) == 0 { return NX_SEL_JOINT_BAD_INPUT }
98 if (node_b as i64) == 0 { return NX_SEL_JOINT_BAD_INPUT }
99 if (out_selection as i64) == 0 { return NX_SEL_JOINT_BAD_INPUT }
100 if node_a.n_candidates <= 0 { return NX_SEL_JOINT_BAD_INPUT }
101 if node_b.n_candidates <= 0 { return NX_SEL_JOINT_BAD_INPUT }
102
103 var best_a: i64 = -1
104 var best_b: i64 = -1
105 var best_total: i64 = NX_MAGIC_9223372036854775000
106
107 var i: i64 = 0
108 while i < node_a.n_candidates {
109 let a_addr: i64 = node_a.manifest_ptrs[i]
110 if a_addr == 0 { i = i + 1; continue }
111 let a: *NxManifest = a_addr as *NxManifest
112
113 // Filter a against device.
114 let a_fits: i64 = nx_select_variant_fits(a, probe, inferred_tier,
115 probe_ram_proxy, probe_isa_ext_mask)
116 if a_fits != 1 { i = i + 1; continue }
117
118 let a_score: i64 = nx_select_score(a, policy)
119
120 var j: i64 = 0
121 while j < node_b.n_candidates {
122 let b_addr: i64 = node_b.manifest_ptrs[j]
123 if b_addr == 0 { j = j + 1; continue }
124 let b: *NxManifest = b_addr as *NxManifest
125
126 let b_fits: i64 = nx_select_variant_fits(b, probe, inferred_tier,
127 probe_ram_proxy, probe_isa_ext_mask)
128 if b_fits != 1 { j = j + 1; continue }
129
130 // Edge constraint: a's output must flow into b's input.
131 let compat: i64 = nx_layout_compatible(a.out_layout, b.in_layout)
132 if compat != 1 { j = j + 1; continue }
133
134 let b_score: i64 = nx_select_score(b, policy)
135 // V1 transfer cost: 0 when layouts match (already enforced
136 // by compat check). SA-6 will measure real transform
137 // bytes via nx_calibrate.mem_bw_mib_per_s.
138 let transfer_cost: i64 = 0
139 let total: i64 = a_score + b_score + transfer_cost
140
141 if total < best_total {
142 best_total = total
143 best_a = i
144 best_b = j
145 }
146 j = j + 1
147 }
148 i = i + 1
149 }
150
151 if best_a < 0 {
152 out_selection[0] = -1
153 out_selection[1] = -1
154 return NX_SEL_JOINT_NO_FEASIBLE_PAIR
155 }
156 out_selection[0] = best_a
157 out_selection[1] = best_b
158 return NX_SEL_JOINT_OK
159}
160
161// ===== Node construction helper ==================================
162func nx_joint_node_new(variant_class: i64, manifest_ptrs: *i64,
163 n_candidates: i64) -> *NxJointNode {
164 let n: *NxJointNode = (sys_mmap(32)) as *NxJointNode
165 n.variant_class = variant_class
166 n.manifest_ptrs = manifest_ptrs
167 n.n_candidates = n_candidates
168 return n
169}
170
171// ===== N-node linear chain selector (SA-5 remainder) =============
172//
173// Exhaustive depth-first enumeration over a LINEAR DAG (1 -> 2 -> 3
174// -> ... -> N). Edge (depth-1, depth) constrains
175// out_layout(prev) compat in_layout(curr). Picks the argmin of the
176// total cost across all complete assignments.
177//
178// Implementation: iterative DFS with an explicit stack (no
179// recursion). Per-depth state lives in two *i64 arrays:
180// - assignment[depth]: candidate index currently committed at depth
181// - next_idx[depth]: next candidate index to TRY at depth
182// Stack pointer is `depth`; depth == -1 means "all combinations
183// exhausted". Max N is bounded by NX_SEL_JOINT_CHAIN_MAX so the
184// scratch buffers stay statically sized.
185//
186// `nodes_ptrs` is *i64 holding (i64-cast) pointers to NxJointNode.
187// `out_selection` is *i64 of length n_nodes that the caller pre-
188// allocates; selector writes the chosen candidate index per node.
189
190const NX_SEL_JOINT_CHAIN_MAX: i64 = 32 // upper bound on N
191
192func nx_select_joint_chain(
193 nodes_ptrs: *i64, n_nodes: i64,
194 probe: *NxProbeRecord,
195 inferred_tier: i64,
196 probe_ram_proxy: i64,
197 probe_isa_ext_mask: i64,
198 policy: *NxPolicy,
199 out_selection: *i64
200) -> i64 {
201 if (nodes_ptrs as i64) == 0 { return NX_SEL_JOINT_BAD_INPUT }
202 if (probe as i64) == 0 { return NX_SEL_JOINT_BAD_INPUT }
203 if (policy as i64) == 0 { return NX_SEL_JOINT_BAD_INPUT }
204 if (out_selection as i64) == 0 { return NX_SEL_JOINT_BAD_INPUT }
205 if n_nodes <= 0 { return NX_SEL_JOINT_BAD_INPUT }
206 if n_nodes > NX_SEL_JOINT_CHAIN_MAX { return NX_SEL_JOINT_BAD_INPUT }
207
208 // Degenerate single-node case: fall back to single-class argmin.
209 if n_nodes == 1 {
210 let node0_addr: i64 = nodes_ptrs[0]
211 if node0_addr == 0 { return NX_SEL_JOINT_BAD_INPUT }
212 let node0: *NxJointNode = node0_addr as *NxJointNode
213 let pick: i64 = nx_select(node0.manifest_ptrs, node0.n_candidates,
214 probe, inferred_tier,
215 probe_ram_proxy, probe_isa_ext_mask,
216 policy)
217 if pick < 0 {
218 out_selection[0] = -1
219 return NX_SEL_JOINT_NO_FEASIBLE_PAIR
220 }
221 out_selection[0] = pick
222 return NX_SEL_JOINT_OK
223 }
224
225 // ----- Scratch state (statically sized) -----
226 let assignment: *i64 = (sys_mmap(NX_SEL_JOINT_CHAIN_MAX * 8)) as *i64
227 let next_idx: *i64 = (sys_mmap(NX_SEL_JOINT_CHAIN_MAX * 8)) as *i64
228 let best_assign: *i64 = (sys_mmap(NX_SEL_JOINT_CHAIN_MAX * 8)) as *i64
229 let partial_score: *i64 = (sys_mmap(NX_SEL_JOINT_CHAIN_MAX * 8)) as *i64
230 // Initialize.
231 var k: i64 = 0
232 while k < n_nodes {
233 assignment[k] = -1
234 next_idx[k] = 0
235 best_assign[k] = -1
236 partial_score[k] = 0
237 k = k + 1
238 }
239 var best_score: i64 = NX_MAGIC_9223372036854775000
240 var depth: i64 = 0
241 next_idx[0] = 0
242
243 // ----- Iterative DFS -----
244 while depth >= 0 {
245 if depth == n_nodes {
246 // Complete assignment: partial_score[n_nodes-1] is the
247 // running total. Compare with best.
248 let total: i64 = partial_score[n_nodes - 1]
249 if total < best_score {
250 best_score = total
251 var c: i64 = 0
252 while c < n_nodes {
253 best_assign[c] = assignment[c]
254 c = c + 1
255 }
256 }
257 // Backtrack one level.
258 depth = depth - 1
259 next_idx[depth] = next_idx[depth] + 1
260 continue
261 }
262 // Get this depth's candidate ring.
263 let node_addr: i64 = nodes_ptrs[depth]
264 if node_addr == 0 {
265 // Missing node pointer -- abort.
266 return NX_SEL_JOINT_BAD_INPUT
267 }
268 let node: *NxJointNode = node_addr as *NxJointNode
269 let try_idx: i64 = next_idx[depth]
270 if try_idx >= node.n_candidates {
271 // Exhausted this depth -- backtrack.
272 depth = depth - 1
273 if depth >= 0 {
274 next_idx[depth] = next_idx[depth] + 1
275 }
276 continue
277 }
278 let v_addr: i64 = node.manifest_ptrs[try_idx]
279 if v_addr == 0 {
280 next_idx[depth] = next_idx[depth] + 1
281 continue
282 }
283 let v: *NxManifest = v_addr as *NxManifest
284 // Filter: device fit.
285 let fits: i64 = nx_select_variant_fits(v, probe, inferred_tier,
286 probe_ram_proxy, probe_isa_ext_mask)
287 if fits != 1 {
288 next_idx[depth] = next_idx[depth] + 1
289 continue
290 }
291 // Filter: layout compat with predecessor's out_layout
292 // (assignment[depth-1]).
293 if depth > 0 {
294 let prev_addr: i64 = nodes_ptrs[depth - 1]
295 let prev_node: *NxJointNode = prev_addr as *NxJointNode
296 let prev_pick_idx: i64 = assignment[depth - 1]
297 let prev_v_addr: i64 = prev_node.manifest_ptrs[prev_pick_idx]
298 let prev_v: *NxManifest = prev_v_addr as *NxManifest
299 let compat: i64 = nx_layout_compatible(prev_v.out_layout, v.in_layout)
300 if compat != 1 {
301 next_idx[depth] = next_idx[depth] + 1
302 continue
303 }
304 }
305 // Accept candidate; compute running partial score.
306 assignment[depth] = try_idx
307 let v_score: i64 = nx_select_score(v, policy)
308 var running: i64 = v_score
309 if depth > 0 {
310 running = partial_score[depth - 1] + v_score
311 }
312 partial_score[depth] = running
313 // Prune: if running already worse than best_score, backtrack.
314 if running >= best_score {
315 next_idx[depth] = next_idx[depth] + 1
316 continue
317 }
318 // Descend.
319 depth = depth + 1
320 if depth < n_nodes {
321 next_idx[depth] = 0
322 }
323 }
324
325 // ----- Result -----
326 if best_assign[0] < 0 {
327 var z: i64 = 0
328 while z < n_nodes {
329 out_selection[z] = -1
330 z = z + 1
331 }
332 return NX_SEL_JOINT_NO_FEASIBLE_PAIR
333 }
334 var w: i64 = 0
335 while w < n_nodes {
336 out_selection[w] = best_assign[w]
337 w = w + 1
338 }
339 return NX_SEL_JOINT_OK
340}