Skip to main content

linkcell/
pair_wide.rs

1//! AVX2 and NEON pair tiles.
2//!
3//! Each kernel screens with the expanded distance and the same margin as
4//! the AVX-512 tile. A lane inside the margin is kept. A lane in the
5//! margin band is decided by the direct formula. The stored squared
6//! distance is always that direct formula, with a separate multiply and
7//! add. FMA stays inside the screen.
8//!
9//! An 8-wide target block is two AVX2 vectors or four NEON vectors, low
10//! lanes first, so the hit order matches the scalar walk and the AVX-512 tile.
11
12use super::{Block, Scratch, TileCols, CULL_RUNS};
13
14/// `(dx * dx + dy * dy) + dz * dz`, the scalar tile's association.
15#[inline(always)]
16fn direct_scalar(dx: f64, dy: f64, dz: f64) -> f64 {
17    (dx * dx + dy * dy) + dz * dz
18}
19
20/// # Safety
21/// `block` indexes every column of `c`. `scratch` has room for every
22/// pair in the block plus [`super::STORE_SLACK`] slots.
23#[cfg(target_arch = "x86_64")]
24#[target_feature(enable = "avx2,fma")]
25#[inline(never)]
26pub(super) unsafe fn avx2_scan(
27    c: TileCols,
28    cut2: f64,
29    margin: f64,
30    block: &Block,
31    scratch: &mut Scratch,
32) {
33    use std::arch::x86_64::{
34        _mm256_add_pd, _mm256_cmp_pd, _mm256_fmadd_pd, _mm256_loadu_pd, _mm256_max_pd,
35        _mm256_movemask_pd, _mm256_mul_pd, _mm256_set1_pd, _mm256_setzero_pd, _mm256_storeu_pd,
36        _mm256_sub_pd, _CMP_LT_OQ,
37    };
38    debug_assert!(std::is_x86_feature_detected!("avx2") && std::is_x86_feature_detected!("fma"));
39    let atom_p = scratch.atom.as_mut_ptr();
40    let js_p = scratch.js.as_mut_ptr();
41    let d2_p = scratch.d2.as_mut_ptr();
42    let mut n = scratch.js.len();
43    let [sx, sy, sz] = block.shift;
44    let [ox, oy, oz] = block.delta;
45    let cut_lo = cut2 - margin;
46    let cut_hi = cut2 + margin;
47    let j_hi = block.j_hi;
48    let nvec = (j_hi - block.j_lo + 7) / 8;
49    let do_cull = !block.tri && c.cull && nvec >= CULL_RUNS;
50
51    macro_rules! push_scalar {
52        ($iu:expr, $j:expr, $px:expr, $py:expr, $pz:expr) => {{
53            let j = $j;
54            let dx = *c.x.add(j) - $px;
55            let dy = *c.y.add(j) - $py;
56            let dz = *c.z.add(j) - $pz;
57            let d2 = direct_scalar(dx, dy, dz);
58            if d2 < cut2 {
59                atom_p.add(n).write($iu);
60                js_p.add(n).write(*c.id.add(j));
61                d2_p.add(n).write(d2);
62                n += 1;
63            }
64        }};
65    }
66    // Four targets at `slot`. The screen is three FMAs. A block that is
67    // entirely inside the margin stores the direct squared distance.
68    macro_rules! push4 {
69        ($s:expr, $slot:expr, $iu:expr, $ax:expr, $ay:expr, $az:expr, $thr:expr, $pp:expr, $px:expr, $py:expr, $pz:expr) => {{
70            let slot = $slot;
71            let jx = _mm256_loadu_pd(c.rx.add(slot));
72            let jy = _mm256_loadu_pd(c.ry.add(slot));
73            let jz = _mm256_loadu_pd(c.rz.add(slot));
74            let jr = _mm256_loadu_pd(c.r2.add(slot));
75            let t = _mm256_fmadd_pd(
76                jz,
77                $az,
78                _mm256_fmadd_pd(jy, $ay, _mm256_fmadd_pd(jx, $ax, jr)),
79            );
80            let hi = _mm256_movemask_pd(_mm256_cmp_pd(t, _mm256_set1_pd($thr), _CMP_LT_OQ));
81            if hi != 0 {
82                let exp = _mm256_add_pd(t, _mm256_set1_pd($pp));
83                let lo =
84                    _mm256_movemask_pd(_mm256_cmp_pd(exp, _mm256_set1_pd(cut_lo), _CMP_LT_OQ)) & hi;
85                if lo == hi {
86                    let dx = _mm256_sub_pd(_mm256_loadu_pd(c.x.add(slot)), _mm256_set1_pd($px));
87                    let dy = _mm256_sub_pd(_mm256_loadu_pd(c.y.add(slot)), _mm256_set1_pd($py));
88                    let dz = _mm256_sub_pd(_mm256_loadu_pd(c.z.add(slot)), _mm256_set1_pd($pz));
89                    let d2v = _mm256_add_pd(
90                        _mm256_add_pd(_mm256_mul_pd(dx, dx), _mm256_mul_pd(dy, dy)),
91                        _mm256_mul_pd(dz, dz),
92                    );
93                    let mut lane = [0.0f64; 4];
94                    _mm256_storeu_pd(lane.as_mut_ptr(), d2v);
95                    let mut bits = lo as u32;
96                    while bits != 0 {
97                        let k = bits.trailing_zeros() as usize;
98                        bits &= bits - 1;
99                        atom_p.add(n).write($iu);
100                        js_p.add(n).write(*c.id.add(slot + k));
101                        d2_p.add(n).write(lane[k]);
102                        n += 1;
103                    }
104                } else {
105                    let mut bits = hi as u32;
106                    while bits != 0 {
107                        let k = bits.trailing_zeros() as usize;
108                        bits &= bits - 1;
109                        push_scalar!($iu, slot + k, $px, $py, $pz);
110                    }
111                }
112            }
113        }};
114    }
115    macro_rules! one_block {
116        ($slot:expr, $iu:expr, $ax:expr, $ay:expr, $az:expr, $thr:expr, $pp:expr, $px:expr, $py:expr, $pz:expr) => {{
117            let slot = $slot;
118            let left = (j_hi - slot).min(8);
119            let mut off = 0usize;
120            while off + 4 <= left {
121                push4!(0, slot + off, $iu, $ax, $ay, $az, $thr, $pp, $px, $py, $pz);
122                off += 4;
123            }
124            while off < left {
125                push_scalar!($iu, slot + off, $px, $py, $pz);
126                off += 1;
127            }
128        }};
129    }
130
131    for s in block.i_lo..block.i_hi {
132        let px_rel = *c.rx.add(s) + ox;
133        let py_rel = *c.ry.add(s) + oy;
134        let pz_rel = *c.rz.add(s) + oz;
135        let pp = px_rel * px_rel + py_rel * py_rel + pz_rel * pz_rel;
136        let ax = _mm256_set1_pd(-2.0 * px_rel);
137        let ay = _mm256_set1_pd(-2.0 * py_rel);
138        let az = _mm256_set1_pd(-2.0 * pz_rel);
139        let thr = cut_hi - pp;
140        let px = *c.x.add(s) - sx;
141        let py = *c.y.add(s) - sy;
142        let pz = *c.z.add(s) - sz;
143        let iu = *c.id.add(s);
144        if do_cull {
145            // Four box-runs at a time. A run that can hold a pair is
146            // visited at once, in slot order. Nothing is buffered.
147            let g = block.ig + (s - block.i_lo) / 4;
148            let blo = [
149                _mm256_set1_pd(*c.gb[0].add(g) + ox),
150                _mm256_set1_pd(*c.gb[1].add(g) + oy),
151                _mm256_set1_pd(*c.gb[2].add(g) + oz),
152            ];
153            let bhi = [
154                _mm256_set1_pd(*c.gb[3].add(g) + ox),
155                _mm256_set1_pd(*c.gb[4].add(g) + oy),
156                _mm256_set1_pd(*c.gb[5].add(g) + oz),
157            ];
158            let zero = _mm256_setzero_pd();
159            let cut = _mm256_set1_pd(cut2 + 2.0 * margin);
160            let mut m0 = 0usize;
161            while m0 < nvec {
162                let v = block.jv + m0;
163                let lanes = (nvec - m0).min(4);
164                let mut box_d2 = zero;
165                for axis in 0..3 {
166                    let gap = _mm256_max_pd(
167                        _mm256_max_pd(
168                            _mm256_sub_pd(_mm256_loadu_pd(c.vb[axis].add(v)), bhi[axis]),
169                            _mm256_sub_pd(blo[axis], _mm256_loadu_pd(c.vb[3 + axis].add(v))),
170                        ),
171                        zero,
172                    );
173                    box_d2 = _mm256_fmadd_pd(gap, gap, box_d2);
174                }
175                let mut near = _mm256_movemask_pd(_mm256_cmp_pd(box_d2, cut, _CMP_LT_OQ)) as u32;
176                let valid = (1u32 << lanes) - 1;
177                near &= valid;
178                #[cfg(test)]
179                super::CULL_SKIPS.fetch_add(
180                    (valid & !near).count_ones() as usize,
181                    std::sync::atomic::Ordering::Relaxed,
182                );
183                while near != 0 {
184                    let lane = near.trailing_zeros() as usize;
185                    near &= near - 1;
186                    let slot = block.j_lo + 8 * (m0 + lane);
187                    one_block!(slot, iu, ax, ay, az, thr, pp, px, py, pz);
188                }
189                m0 += 4;
190            }
191        } else {
192            let start = if block.tri { s + 1 } else { block.j_lo };
193            let mut slot = start;
194            while slot < j_hi {
195                one_block!(slot, iu, ax, ay, az, thr, pp, px, py, pz);
196                slot += 8;
197            }
198        }
199    }
200    scratch.finish(n);
201}
202
203/// # Safety
204/// `block` indexes every column of `c`. `scratch` has room for every
205/// pair in the block plus [`super::STORE_SLACK`] slots.
206#[cfg(target_arch = "aarch64")]
207#[target_feature(enable = "neon")]
208#[inline(never)]
209pub(super) unsafe fn neon_scan(
210    c: TileCols,
211    cut2: f64,
212    margin: f64,
213    block: &Block,
214    scratch: &mut Scratch,
215) {
216    use std::arch::aarch64::{
217        vaddq_f64, vcltq_f64, vdupq_n_f64, vfmaq_f64, vgetq_lane_f64, vgetq_lane_u64, vld1q_f64,
218        vmulq_f64, vsubq_f64,
219    };
220    let atom_p = scratch.atom.as_mut_ptr();
221    let js_p = scratch.js.as_mut_ptr();
222    let d2_p = scratch.d2.as_mut_ptr();
223    let mut n = scratch.js.len();
224    let [sx, sy, sz] = block.shift;
225    let [ox, oy, oz] = block.delta;
226    let cut_lo = cut2 - margin;
227    let cut_hi = cut2 + margin;
228    let j_hi = block.j_hi;
229    let nvec = (j_hi - block.j_lo + 7) / 8;
230    let do_cull = !block.tri && c.cull && nvec >= CULL_RUNS;
231
232    macro_rules! push_scalar {
233        ($iu:expr, $j:expr, $px:expr, $py:expr, $pz:expr) => {{
234            let j = $j;
235            let dx = *c.x.add(j) - $px;
236            let dy = *c.y.add(j) - $py;
237            let dz = *c.z.add(j) - $pz;
238            let d2 = direct_scalar(dx, dy, dz);
239            if d2 < cut2 {
240                atom_p.add(n).write($iu);
241                js_p.add(n).write(*c.id.add(j));
242                d2_p.add(n).write(d2);
243                n += 1;
244            }
245        }};
246    }
247    macro_rules! push2 {
248        ($slot:expr, $iu:expr, $ax:expr, $ay:expr, $az:expr, $thr:expr, $ppv:expr, $bx:expr, $by:expr, $bz:expr, $px:expr, $py:expr, $pz:expr) => {{
249            let slot = $slot;
250            let jx = vld1q_f64(c.rx.add(slot));
251            let jy = vld1q_f64(c.ry.add(slot));
252            let jz = vld1q_f64(c.rz.add(slot));
253            let jr = vld1q_f64(c.r2.add(slot));
254            let t = vfmaq_f64(vfmaq_f64(vfmaq_f64(jr, jx, $ax), jy, $ay), jz, $az);
255            let hi = vcltq_f64(t, $thr);
256            let h0 = vgetq_lane_u64(hi, 0) != 0;
257            let h1 = vgetq_lane_u64(hi, 1) != 0;
258            if h0 || h1 {
259                let exp = vaddq_f64(t, $ppv);
260                let lo = vcltq_f64(exp, vdupq_n_f64(cut_lo));
261                let l0 = h0 && vgetq_lane_u64(lo, 0) != 0;
262                let l1 = h1 && vgetq_lane_u64(lo, 1) != 0;
263                if h0 == l0 && h1 == l1 {
264                    let dx = vsubq_f64(vld1q_f64(c.x.add(slot)), $bx);
265                    let dy = vsubq_f64(vld1q_f64(c.y.add(slot)), $by);
266                    let dz = vsubq_f64(vld1q_f64(c.z.add(slot)), $bz);
267                    let d2v = vaddq_f64(
268                        vaddq_f64(vmulq_f64(dx, dx), vmulq_f64(dy, dy)),
269                        vmulq_f64(dz, dz),
270                    );
271                    if h0 {
272                        atom_p.add(n).write($iu);
273                        js_p.add(n).write(*c.id.add(slot));
274                        d2_p.add(n).write(vgetq_lane_f64(d2v, 0));
275                        n += 1;
276                    }
277                    if h1 {
278                        atom_p.add(n).write($iu);
279                        js_p.add(n).write(*c.id.add(slot + 1));
280                        d2_p.add(n).write(vgetq_lane_f64(d2v, 1));
281                        n += 1;
282                    }
283                } else {
284                    if h0 {
285                        push_scalar!($iu, slot, $px, $py, $pz);
286                    }
287                    if h1 {
288                        push_scalar!($iu, slot + 1, $px, $py, $pz);
289                    }
290                }
291            }
292        }};
293    }
294
295    for s in block.i_lo..block.i_hi {
296        let px_rel = *c.rx.add(s) + ox;
297        let py_rel = *c.ry.add(s) + oy;
298        let pz_rel = *c.rz.add(s) + oz;
299        let pp = px_rel * px_rel + py_rel * py_rel + pz_rel * pz_rel;
300        let ax = vdupq_n_f64(-2.0 * px_rel);
301        let ay = vdupq_n_f64(-2.0 * py_rel);
302        let az = vdupq_n_f64(-2.0 * pz_rel);
303        let thr = vdupq_n_f64(cut_hi - pp);
304        let ppv = vdupq_n_f64(pp);
305        let px = *c.x.add(s) - sx;
306        let py = *c.y.add(s) - sy;
307        let pz = *c.z.add(s) - sz;
308        let iu = *c.id.add(s);
309        let bx = vdupq_n_f64(px);
310        let by = vdupq_n_f64(py);
311        let bz = vdupq_n_f64(pz);
312        macro_rules! one_block {
313            ($slot:expr) => {{
314                let slot = $slot;
315                let left = (j_hi - slot).min(8);
316                let mut off = 0usize;
317                while off + 2 <= left {
318                    push2!(slot + off, iu, ax, ay, az, thr, ppv, bx, by, bz, px, py, pz);
319                    off += 2;
320                }
321                if off < left {
322                    push_scalar!(iu, slot + off, px, py, pz);
323                }
324            }};
325        }
326        if do_cull {
327            use std::arch::aarch64::{
328                vcltq_f64, vdupq_n_f64, vfmaq_f64, vgetq_lane_u64, vld1q_f64, vmaxq_f64, vsubq_f64,
329            };
330            let g = block.ig + (s - block.i_lo) / 4;
331            let blo = [
332                vdupq_n_f64(*c.gb[0].add(g) + ox),
333                vdupq_n_f64(*c.gb[1].add(g) + oy),
334                vdupq_n_f64(*c.gb[2].add(g) + oz),
335            ];
336            let bhi = [
337                vdupq_n_f64(*c.gb[3].add(g) + ox),
338                vdupq_n_f64(*c.gb[4].add(g) + oy),
339                vdupq_n_f64(*c.gb[5].add(g) + oz),
340            ];
341            let zero = vdupq_n_f64(0.0);
342            let cut = vdupq_n_f64(cut2 + 2.0 * margin);
343            let mut m0 = 0usize;
344            while m0 < nvec {
345                let v = block.jv + m0;
346                let lanes = (nvec - m0).min(2);
347                let mut box_d2 = zero;
348                for axis in 0..3 {
349                    let gap = vmaxq_f64(
350                        vmaxq_f64(
351                            vsubq_f64(vld1q_f64(c.vb[axis].add(v)), bhi[axis]),
352                            vsubq_f64(blo[axis], vld1q_f64(c.vb[3 + axis].add(v))),
353                        ),
354                        zero,
355                    );
356                    box_d2 = vfmaq_f64(box_d2, gap, gap);
357                }
358                let near = vcltq_f64(box_d2, cut);
359                let n0 = lanes >= 1 && vgetq_lane_u64(near, 0) != 0;
360                let n1 = lanes >= 2 && vgetq_lane_u64(near, 1) != 0;
361                #[cfg(test)]
362                {
363                    let mut skipped = 0usize;
364                    if lanes >= 1 && !n0 {
365                        skipped += 1;
366                    }
367                    if lanes >= 2 && !n1 {
368                        skipped += 1;
369                    }
370                    super::CULL_SKIPS.fetch_add(skipped, std::sync::atomic::Ordering::Relaxed);
371                }
372                if n0 {
373                    one_block!(block.j_lo + 8 * m0);
374                }
375                if n1 {
376                    one_block!(block.j_lo + 8 * (m0 + 1));
377                }
378                m0 += 2;
379            }
380        } else {
381            let start = if block.tri { s + 1 } else { block.j_lo };
382            let mut slot = start;
383            while slot < j_hi {
384                one_block!(slot);
385                slot += 8;
386            }
387        }
388    }
389    scratch.finish(n);
390}