nx_latency_metric_test.nx source

1// nx_latency_metric_test.nx -- proves the HONEST latency-metric organ and uses it 2// to race three divider TOPOLOGIES at W=16: radix-2 (W stages), radix-4 (W/2 3// stages), and the scalar-equivalent Newton-Raphson reciprocal structure 4// (~log W iterations of multiply-heavy work). 5// 6// WHAT THIS PROVES (FAIL LOUD on every leg): 7// (1) The organ's UNIT metric matches the functional sim's implicit depth-1 8// model: on a tiny hand-built chain whose longest path is known by hand, 9// nx_lat_unit returns exactly that hand-counted op-depth. 10// (2) The HONEST metric does NOT treat a multiplier as depth-1: a single MUL 11// cell costs 2*ceil(log2 W) gate levels, an ADD costs ceil(log2 W), a 12// boolean costs 1 -- asserted directly against nx_lat_kind_weight, and 13// asserted on a one-MUL chain whose honest depth > its unit depth. 14// (3) THE RACE, told HONESTLY across WIDTH -- the trap, and where it flips. The 15// SAME Newton topology is measured with a DEEP multiplier (the real 16// nx_mul_wide 32-bit-limb schoolbook) and a SHALLOW one (single-cell Wallace 17// model, 2*logW), at W=16 and W=64. The MEASURED honest critical paths are: 18// W=16: radix-2=181 radix-4=139 Newton-deep=363 Newton-shallow=166 19// W=64: radix-2=967 radix-4=743 Newton-deep=709 Newton-shallow=320 20// So, honestly: 21// - At SMALL width (W=16) the multiplicative method does NOT pay off: 22// radix-4 wins; the DEEP-multiplier Newton is the WORST (363); and even 23// the SHALLOW-multiplier Newton (166) still loses to radix-4 (139). The 24// naive "log(W) multiplies beats W subtracts" LATENCY claim is FALSE here. 25// - At LARGE width (W=64) the log(W) FRONTIER appears: BOTH Newton variants 26// beat BOTH radix dividers (320 and 709 vs 743 and 967), because the radix 27// dividers' stage count grows linearly in W while Newton's iteration count 28// grows only ~log W. Ordering: shallow-Newton < deep-Newton < r4 < r2. 29// - THE CROSSOVER is the headline: the SAME shallow-multiplier Newton goes 30// from LOSING to radix-4 at W=16 to BEATING it at W=64. That measured sign- 31// flip IS the multiplicative-divider latency win -- and the honest metric 32// refuses to award it at a width where it is not real. 33// Invariant independent of width + multiplier: radix-4 (W/2 stages) always 34// beats radix-2 (W stages). All orderings are ASSERTED, not assumed. 35// 36// Known-answer lines (printed for the gate): four honest critical paths at W=16, 37// then at W=64, then the kind-weight spot-checks. exit 0 iff all asserts hold. 38// 39// HONESTY SCOPE: the Newton network here is the algorithm's STRUCTURAL skeleton 40// (the exact operator dependency chain of nx_alu_divider_newton.nx: normalize -> 41// minimax linear seed -> ITERS x (dn*x ; 2F^2-dn*x ; x*t ; >>2W) -> N*x ; >>shift 42// -> O(1) correction), built from the SAME proven cell-builders + the proven 43// nx_mul_wide_synth, so its CRITICAL PATH is the honest scalar-equivalent of the 44// Newton datapath. It is a LATENCY measurement of the topology, not a re-proof of 45// Newton's arithmetic (that is nx_alu_divider_newton's job + the gate-divider 46// milestone). The latency metric is the gate-LEVEL logic-depth model documented in 47// nx_latency_metric.nx -- relative operator depth sized by W, not silicon ns. 48 49import "nx_latency_metric.nx" 50import "nx_alu_divider_r4.nx" // pulls in nx_alu_divider (radix-2) + the sim 51import "nx_mul_wide.nx" // proven 64x64->128 multiplier, for the Newton products 52import "nx_newton_struct.nx" // the shared Newton structure (DRY: also used by nx_div_pick) 53 54func _emit_num(v: i64) -> i64 { 55 let b: *u8 = sys_mmap(28); var n: i64 = v; if n < 0 { n = 0 - n } 56 let t2: *u8 = sys_mmap(28); var t: i64 = 0 57 if n == 0 { t2[0] = 48; t = 1 } 58 while n > 0 { t2[t] = 48 + (n % 10); n = n / 10; t = t + 1 } 59 var i: i64 = 0; while i < t { b[i] = t2[t - 1 - i]; i = i + 1 } 60 b[t] = 32; sys_write(1, b, t + 1); return 0 61} 62func _nl() -> i64 { let z: *u8 = sys_mmap(2); z[0] = 10; sys_write(1, z, 1); return 0 } 63 64// Build a fresh, empty NxGsim with `ninputs` primary-input nets. Generous caps. 65func _mk_gsim(ninputs: i64) -> *NxGsim { 66 let vals: *i64 = sys_mmap(4096 * 8) as *i64 67 let cells: *NxGsimCell = sys_mmap(4096 * 48) as *NxGsimCell 68 let g: *NxGsim = sys_mmap(64) as *NxGsim 69 g.vals = vals; g.n_nets = ninputs; g.cells = cells; g.n_cells = 0 70 return g 71} 72 73// allocate a per-net depth scratch buffer sized for the biggest network we build. 74func _mk_depth() -> *i64 { return sys_mmap(8192 * 8) as *i64 } 75 76// Measure the four honest critical-path depths at width W (Newton uses `iters` 77// iterations + KCORR=2). Writes [hr2, hr4, hnewton_deepmul, hnewton_shallowmul] 78// into out[0..3]. Builds fresh networks each call (no cross-contamination). 79func _measure(W: i64, iters: i64, depth: *i64, out: *i64) -> i64 { 80 let ro: *i64 = sys_mmap(8) as *i64 81 82 let g2: *NxGsim = _mk_gsim(2) 83 ro[0] = 0 84 let q2: i64 = nx_div_synth(g2, 0, 1, W, ro) // radix-2 (W stages) 85 out[0] = nx_lat_honest(g2, depth, W) 86 87 let g4: *NxGsim = _mk_gsim(2) 88 ro[0] = 0 89 let q4: i64 = nx_div_synth_r4(g4, 0, 1, W, ro) // radix-4 (W/2 stages) 90 out[1] = nx_lat_honest(g4, depth, W) 91 92 let gnd: *NxGsim = _mk_gsim(2) // Newton, DEEP multiplier 93 let qnd: i64 = nx_newton_struct(gnd, 0, 1, W, iters, 2, 1) 94 out[2] = nx_lat_honest(gnd, depth, W) 95 96 let gns: *NxGsim = _mk_gsim(2) // Newton, SHALLOW multiplier 97 let qns: i64 = nx_newton_struct(gns, 0, 1, W, iters, 2, 0) 98 out[3] = nx_lat_honest(gns, depth, W) 99 return 0 100} 101 102func main() -> i64 { 103 let W: i64 = 16 104 let depth: *i64 = _mk_depth() 105 106 // ===== (1) UNIT metric == hand-counted depth on a known tiny chain ========== 107 // chain: in0 -AND-> n2 -ADD-> n3 -XOR-> n4 ; longest path = 3 non-const cells. 108 let gt: *NxGsim = _mk_gsim(2) 109 let h2: i64 = div_op2(gt, NX_GATE_KIND_AND, 0, 1) // net2 110 let h3: i64 = div_op2(gt, NX_GATE_KIND_ADD, h2, 1) // net3 111 let h4: i64 = div_op2(gt, NX_GATE_KIND_XOR, h3, 1) // net4 112 let u_tiny: i64 = nx_lat_unit(gt, depth) 113 // honest depth of the SAME chain: AND(1) + ADD(logW=4) + XOR(1) = 6 114 let h_tiny: i64 = nx_lat_honest(gt, depth, W) 115 116 // ===== (2) kind-weight spot checks (HONEST != depth-1 for a multiplier) ===== 117 let lg: i64 = nx_lat_log2_ceil(W) // 4 at W=16 118 let w_and: i64 = nx_lat_kind_weight(NX_GATE_KIND_AND, W) // 1 119 let w_add: i64 = nx_lat_kind_weight(NX_GATE_KIND_ADD, W) // lg = 4 120 let w_mul: i64 = nx_lat_kind_weight(NX_GATE_KIND_MUL, W) // 2*lg = 8 121 let w_con: i64 = nx_lat_kind_weight(NX_GATE_KIND_CONST, W) // 0 122 123 // ===== THE RACE, swept across width to find the honest crossover ============ 124 // Small width: a divider's W (or W/2) stages are few, so the Newton structure's 125 // fixed serial overhead (seed + iters + correction tail, all multiply-bearing) 126 // does NOT pay off. Large width: the radix dividers' stage count grows linearly 127 // in W while Newton's iteration count grows only ~log W, so Newton wins. The 128 // honest metric must show BOTH regimes. Newton iters per the proven scaling 129 // (ceil(log2(W/4))+1): W=16 -> 3, W=64 -> 5. 130 let s16: *i64 = sys_mmap(4 * 8) as *i64 131 let s64: *i64 = sys_mmap(4 * 8) as *i64 132 _measure(16, 3, depth, s16) 133 _measure(64, 5, depth, s64) 134 135 _emit_num(s16[0]); _emit_num(s16[1]); _emit_num(s16[2]); _emit_num(s16[3]); _nl() 136 _emit_num(s64[0]); _emit_num(s64[1]); _emit_num(s64[2]); _emit_num(s64[3]); _nl() 137 _emit_num(u_tiny); _emit_num(h_tiny); _emit_num(lg) 138 _emit_num(w_and); _emit_num(w_add); _emit_num(w_mul); _emit_num(w_con); _nl() 139 140 // ===== ASSERTIONS (FAIL LOUD) =============================================== 141 // (1) UNIT metric == hand-counted op-depth (the depth-1 model the sim uses) 142 if u_tiny != 3 { sys_exit(1); return 1 } 143 // (2) HONEST depth of that SAME chain: AND(1) + ADD(logW=4) + XOR(1) = 6 > 3. 144 // Same topology, bigger honest number -> the depth-1 model UNDER-counts latency. 145 if h_tiny != 6 { sys_exit(2); return 2 } 146 if h_tiny <= u_tiny { sys_exit(3); return 3 } 147 148 // (2) HONEST weights: a MUL is NOT depth-1, it is the deepest operator 149 if lg != 4 { sys_exit(4); return 4 } 150 if w_and != 1 { sys_exit(5); return 5 } 151 if w_add != 4 { sys_exit(6); return 6 } 152 if w_mul != 8 { sys_exit(7); return 7 } // 2*log2(16) -- the trap, refuted 153 if w_con != 0 { sys_exit(8); return 8 } 154 if w_mul <= w_add { sys_exit(9); return 9 } // multiplier strictly deeper than adder 155 if w_add <= w_and { sys_exit(10); return 10 } // adder strictly deeper than a boolean 156 157 // sanity: every measured depth is positive (networks were actually built) 158 var ii: i64 = 0 159 while ii < 4 { 160 if s16[ii] <= 0 { sys_exit(11); return 11 } 161 if s64[ii] <= 0 { sys_exit(12); return 12 } 162 ii = ii + 1 163 } 164 165 // Invariant at EVERY width, independent of multiplier model: radix-4 (W/2 166 // stages) strictly beats radix-2 (W stages) on the honest critical path. 167 if s16[1] >= s16[0] { sys_exit(13); return 13 } 168 if s64[1] >= s64[0] { sys_exit(14); return 14 } 169 170 // Multiplier depth ALWAYS matters: the shallow (single-cell Wallace) Newton is 171 // strictly cheaper than the deep (limb-schoolbook) Newton at both widths -- the 172 // SAME topology, differing ONLY in the multiplier model. If these were equal, 173 // the metric would be blind to the one thing that decides the race. 174 if s16[3] >= s16[2] { sys_exit(15); return 15 } 175 if s64[3] >= s64[2] { sys_exit(16); return 16 } 176 177 // ---- SMALL WIDTH (W=16): log(W) does NOT pay off; radix-4 is the winner. ---- 178 // The Newton structure's fixed serial overhead (seed + 3 iters + extract + 2 179 // correction stages, every one bearing a deep MUL) is too much when the divider 180 // has only 8 (radix-4) / 16 (radix-2) stages. 181 // (a) DEEP-multiplier Newton is the WORST of the three -- the naive "log(W) 182 // multiplies beats W subtracts" LATENCY claim is FALSE here. Assert it. 183 if s16[2] <= s16[0] { sys_exit(17); return 17 } // deep Newton worse than radix-2 184 if s16[2] <= s16[1] { sys_exit(18); return 18 } // deep Newton worse than radix-4 185 // (b) even the SHALLOW-multiplier Newton LOSES to radix-4 at W=16. 186 if s16[3] <= s16[1] { sys_exit(19); return 19 } // shallow Newton loses to radix-4 187 188 // ---- LARGE WIDTH (W=64): the log(W) FRONTIER appears -- Newton WINS. -------- 189 // radix-2 has 64 stages, radix-4 has 32, while Newton still has only ~5 190 // iterations, so the multiplicative method crosses over. The honest ordering is 191 // shallow-Newton < deep-Newton < radix-4 < radix-2. 192 if s64[3] >= s64[1] { sys_exit(20); return 20 } // shallow Newton beats radix-4 193 if s64[3] >= s64[0] { sys_exit(21); return 21 } // ... and radix-2 194 if s64[2] >= s64[1] { sys_exit(22); return 22 } // EVEN the DEEP Newton beats radix-4 @64 195 if s64[2] >= s64[0] { sys_exit(23); return 23 } // ... and radix-2 196 197 // ---- THE CROSSOVER is the headline (the real log(W) frontier) -------------- 198 // The SAME shallow-multiplier Newton topology goes from LOSING to radix-4 at 199 // W=16 to BEATING it at W=64. That sign-flip, measured on the honest metric, IS 200 // the multiplicative-divider latency win -- and the metric refuses to award it 201 // at a width where it is not real. Re-assert the flip explicitly. 202 if s16[3] <= s16[1] { sys_exit(24); return 24 } // @16: Newton ABOVE radix-4 (loses) 203 if s64[3] >= s64[1] { sys_exit(25); return 25 } // @64: Newton BELOW radix-4 (wins) 204 205 sys_exit(0); return 0 206}