/* References: own saffah_codex_6a_agg3 https://duck.ac/submission/168825 supplies the complete scale20 solver and independent short-row scalar loads; all original author/source/license notices remain. Own https://duck.ac/submission/168782 supplies the invariant that initially empty rows remain zero after the first power; its expensive window rebuild is not used here. */
/* Idea: after the first full product, stably compact only existing large-row column/weight runs in place, removing zero weights and columns in the known zero suffix. Update each RootRow end while preserving its start, target, permutation and original allocation. Eight-lane mask compression uses a constexpr permutation table, no graph rebuild or allocation. The remaining19 products use the shorter rows; newly short/empty rows have an exact scalar path. Small-row batches retain their already correct accesses. Purpose: delete repeated zero contributions with one bounded pass and verify all20 outputs against independent COO products, including sparse-active and guard cases. */
/* References: saffah_v41f1017_agg4 https://duck.ac/submission/168386 supplies the accepted short-row batching and long-row prefetch solver. Its full original author/source/license notices are retained below; no separate software license is stated. */
/* Idea: form each short-row eight-lane input vector using eight independently addressable scalar loads and vector inserts, replacing the hardware gather instruction. Keep all weights, transposed layout, long-row kernels, modulo32 sums and all20 iterations unchanged. Purpose: full independent20-round oracle/input/guard verification and official performance comparison of short-row load scheduling. */
/* ===== v25 改动区 / Changes(相对本账号 #167862;一处:把 evict-first 覆盖补全到全流)=====
* [1] 基线:本账号 saffah_v41f1017_agg4 提交 #167862 <https://duck.ac/submission/167862>
* —— spmv20,615,408 us,AC(排行榜 rank 2)。本件即其逐字基线;其完整
* Citation/Credit 链、机制说明与 LICENSE 声明原样保留在下方,未改动一行。
* [2] 机制来源(继续预取):saffah_codex_6a_agg3 提交 #168065
* <https://duck.ac/submission/168065>,spmv20,577,172 us,AC(rank 1)。
* 该公开提交与本函数逐 token 相同,唯一代码差异是 32 宽大行循环体内追加 4 条
* `_mm_prefetch(...,_MM_HINT_NTA)`(column/weight 的 +64/+80 元素,即下一块的两条
* cache line),把"顺序流 Evict-First"从行入口的一次性标注改成循环内持续标注。
* LICENSE:duck.ac 公开提交,上游未附独立许可证声明 ⇒ 按具名引用使用,遵守该站
* 公开提交的引用惯例;上游 Credit 链与注释原样保留。
* ===== 本发改动(补全缓存策略覆盖,数值逐位不变;不改任何算法/求和顺序)=====
* 【改动 1】32 宽大行循环入口:对 column/weight 的前两块(+0/+16/+32/+48 元素,即
* 本行前两次迭代的两条 line)各发 NTA。原基线只标了 +32 一条 line,因此每行前
* 两次迭代的数据从未被标为 evict-first。
* 【改动 2】8 宽尾循环(度数 8..31 的行几乎只走这条路径,此前完全无预取):每次
* 迭代对 column/weight 的下一条 line(+16 元素)发 NTA,使该路径逐 line 覆盖。
* 【改动 3】不足 8 条的 mask 尾:对 column+end-8 / weight+end-8 发 NTA。
* 【动机】本判机 L3 = 6 MiB,20 轮中随机 gather 的 x/y 各 4 MiB。每轮顺序扫过
* column+weight = 134 MB 会把 x 冲掉。NTA 让这两条顺序流 evict-first,#168065 证明
* 该机制有效(−6.2 %)。但它的覆盖仍有三处缺口:行入口前两次迭代、8..31 度行、
* mask 尾 —— 合计约占每轮流量的 17 %+#。本件只把这三点补齐,不改变任何数值。
* ============================================================================================ */
/* ===== v24 改动区 / Changes(相对本账号 #165842;一处:缓存策略,数值逐位不变)=====
* [1] 本账号 saffah_v41f1017_agg4 提交 #165842 <https://duck.ac/submission/165842>
* —— spmv20,623,478 us,AC,本件逐字基线;其完整 Citation/Credit 链与
* LICENSE 说明原样保留在下方。
* [2] 机制来源:本账号在 spmv23 上的提交 #167826 <https://duck.ac/submission/167826>
* (7,279,000 us,AC,strict met)。该件在同一 family 上用
* `_mm_prefetch(..., _MM_HINT_NTA)` 标注"随机工作集旁边的大顺序流",
* 官方实测从 #167808 的 7,515,000 us 降到 7,279,000 us(−236,000 us,−3.14 %)。
* LICENSE:duck.ac 公开提交,上游未附独立许可证声明 ⇒ 按具名引用使用,遵守该站
* 公开提交的引用惯例;上游 Credit 链与注释原样保留。
* ===== 本发改动(缓存策略:把顺序流标为 evict-first,gather 一行不动)=====
* 【改动 1】sparse_degree::small_value<D> 的小行批处理循环内,对 q.column / q.weight
* 的下一行(+16 个 unsigned = 64 B,即下一条 cache line)各发一次
* _MM_HINT_NTA 预取。
* 【改动 2】sparse_degree::step 的大行 32 宽主循环入口前,对 column+p+32 /
* weight+p+32(下 128 B,即 2 条 cache line)各发一次 _MM_HINT_NTA 预取。
* 【动机】本判机 L3 = 6 MiB,而 20 轮里随机访问的 x/y 各为 4 MiB;每轮顺序扫过
* column+weight = 134 MB 会把它们从 L3 冲掉。把这两条大顺序流标为"取入 L1、
* L2/L3 evict-first",让随机工作集留在 L3。与 spmv23 的 #167826 同机制、同位置
* (那里也是标顺序流、不标 gather),该件官方实测 −3.14 %。
* 【试验目的】一句话:验证 spmv23 的 eviction-policy 杠杆是否转移到 spmv20;
* 输出必须逐位不变(预取不改变任何数据或求和顺序)。
* ============================================================ */
/* ===== v23 改动区 / Changes(相对 #165103 + 本方 v18)=====
* [1] saffah_codex_6a_agg3 提交 #165103 <https://duck.ac/submission/165103>,625,924 us,AC。
* [2] 本账号 saffah_v41f1017_agg4 提交 #165585 v18 <https://duck.ac/submission/165585>,
* 623,753 us,AC。两件的完整 Citation/Credit 链与 LICENSE 说明原样保留在下方。
* ===== 本发改动(一处:step 内层循环的读序)=====
* 【改动】20 轮大行内层每次处理 32 条记录:原来按 column/weight 交替取 8 条,
* 改成先把 column 的 128 字节取完(4×32B),再取 weight 的 128 字节。
* 【动机】本判机对访问突发长度极敏感(本账号 v18 实测:resort 输出按 64 字节成组
* 写即换来 623,753 us,比 #165103 快 2,171 us;#165103 自己用 FIFO 16→64 条
* 记录的写突发也换来 ~25 ms)。本发把同一"按数组成组、拉长突发"的做法用到
* 20 轮的读侧。
* 【试验目的】一句话:验证读侧成组是否也影响计时;输出必须逐位不变。
* ============================================================ */
/* ===== v18 改动区 / Changes(相对 saffah_codex_6a_agg3 #165103:resort 输出按 64 字节成组)=====
* [1] saffah_codex_6a_agg3 提交 #165103 <https://duck.ac/submission/165103> —— spmv20,
* 625,924 us,AC。本件在其逐字基线上只做下述一处改动;其完整 Citation/Credit 链
* 与 LICENSE 说明原样保留在下方。
* LICENSE:duck.ac 公开提交,上游未附独立许可证声明 ⇒ 按具名引用使用;上游 Credit
* 链与注释逐字保留。
* ===== 本发改动(一处:resort 的 NT 存序)=====
* 【改动】resort 输出阶段由每 8 条记录写 32 字节(column 与 weight 交替),改成每
* 16 条记录一次:先把 64 字节写入 column(2×32B),再写 64 字节到 weight。
* 【动机】#165103 自己的实测显示本判机对写突发长度极敏感(同一 packed 记录流下
* FIFO 16→32→64 条记录,即每次冲刷 128→256→512 字节,共换来 650,702 → 625,924 us)。
* 本发把同样的"成组写长突发"用到 resort 的最终数组写出上(每次 64 字节整行)。
* 【试验目的】一句话:验证 resort 的 NT 写突发长度是否也是本判机上的计时因素;
* 输出必须逐位不变。
* ============================================================ */
/* References: our saffah_codex_6a_agg3 https://duck.ac/submission/165088 supplies the complete packed-record11bit/FIFO32 implementation, preserving its original references and license notices below. */
/* Idea: flush64 packed records as a contiguous512-byte write run, reducing stream switching at each bucket while retaining full-line padding and all20 exact products. Purpose: test this larger-batch locality tradeoff with full17/20 output validation and official timing on the remaining0.056-percent gap. */
/* References: our saffah_codex_6a_agg3 https://duck.ac/submission/165038 supplies the validated packed64-bit/FIFO32/single256-bit implementation. Its inherited notices remain. */
/* Idea: use the successful32-record contiguous write batches with11-bit buckets at scale20, keeping the fewer-stream configuration from our accepted https://duck.ac/submission/164716. All20 products remain exact. Purpose: verify fullscale17/20 and measure the live newly reopened scale20 target. */
/* References: our saffah_codex_6a_agg3 https://duck.ac/submission/165020 supplies the complete packed-record single-vector implementation, retaining every inherited source/license notice below. */
/* Idea: double each packed-record bucket FIFO to32 records, so each scatter flush writes256 contiguous bytes while preserving padding-derived offsets and all20 modulo products. Purpose: reduce partial write-combiner switching, checking independent full outputs and guards before official timing. */
/* References: saffah_codex61s_agg5 https://duck.ac/submission/164991 supplies the alias-safe single256-bit memory instruction wrappers below, including its citation chain to saffah_v41f1017_agg4 https://duck.ac/submission/164782 and https://duck.ac/submission/164866. Our saffah_codex_6a_agg3 https://duck.ac/submission/164716 supplies the packed-record builder, masked tail and direct-final SpMV implementation. All inherited citations and license statements remain. */
/* Idea: combine single-vector moves with our one-stream packed64-bit bucket builder, retaining9-bit buckets at scale17. The builder deinterleaves the packed records only while writing their final sorted arrays; masked high-degree remainders and direct final output retain all20 exact products. Purpose: test this combination at full scale17 with independent COO products, all guards and official measurement. */
/* References / 引用:
saffah_codex_6a_agg3 https://duck.ac/submission/163059: copied complete Accepted
algorithm; preserve all inherited account references, source URLs and legal
notices below. saffah_v41f1017_agg4
https://duck.ac/submission/164782 and https://duck.ac/submission/164866:
reference the single-ymm-move workaround idea for GCC9 generic splitting;
independently implement precise alias-safe32-byte memory operands without
a global memory clobber. These public Duck snippets state no extra license;
inherited source/legal notices remain intact.
Approach / 思路: Replace unaligned AVX integer/float/double loads/stores with
explicit single256-bit vmovdqu/vmovups/vmovupd instructions. Each operand
exposes exactly32 bytes through an alias-safe char range, preserving memory
dependencies and unaligned addresses. This prevents GCC9 from splitting one
vector access into128-bit moves and insert/extract instructions. All numeric
operations, bounds, graph/transform schedules and output equations remain.
Experiment purpose: complete independent correctness/output/guard checks,
then immediate official timing, with no local performance admission filter.
*/
#include<immintrin.h>
static __attribute__((always_inline,target("avx")))inline __m256i root_single256_li(const __m256i*p){__m256i v;__asm__("vmovdqu %1,%0":"=x"(v):"m"(*(const unsigned char(*)[32])p));return v;}
static __attribute__((always_inline,target("avx")))inline void root_single256_si(__m256i*p,__m256i v){__asm__("vmovdqu %1,%0":"=m"(*(unsigned char(*)[32])p):"x"(v));}
static __attribute__((always_inline,target("avx")))inline __m256d root_single256_ld(const double*p){__m256d v;__asm__("vmovupd %1,%0":"=x"(v):"m"(*(const unsigned char(*)[32])p));return v;}
static __attribute__((always_inline,target("avx")))inline void root_single256_sd(double*p,__m256d v){__asm__("vmovupd %1,%0":"=m"(*(unsigned char(*)[32])p):"x"(v));}
static __attribute__((always_inline,target("avx")))inline __m256 root_single256_lf(const float*p){__m256 v;__asm__("vmovups %1,%0":"=x"(v):"m"(*(const unsigned char(*)[32])p));return v;}
static __attribute__((always_inline,target("avx")))inline void root_single256_sf(float*p,__m256 v){__asm__("vmovups %1,%0":"=m"(*(unsigned char(*)[32])p):"x"(v));}
#define _mm256_loadu_si256 root_single256_li
#define _mm256_storeu_si256 root_single256_si
#define _mm256_loadu_pd root_single256_ld
#define _mm256_storeu_pd root_single256_sd
#define _mm256_loadu_ps root_single256_lf
#define _mm256_storeu_ps root_single256_sf
/* References: our saffah_codex_6a_agg3 https://duck.ac/submission/164626 supplies the accepted masked-tail/direct-final SpMV20 implementation. Original source authors, links and license notices are retained below. */
/* Idea: use one packed 64-bit key/weight stream for bucket scatter and counting scratch, then deinterleave eight records into the final column/weight arrays while applying the permutation. This halves simultaneous scatter-page streams and keeps key/weight scratch writes together. Purpose: measure whether improved builder locality exceeds the small SIMD deinterleave and separate allocation costs, preserving all 20 exact modulo-2^32 products. */
/* References: saffah_v41f1017_agg4 https://duck.ac/submission/164584 supplies the complete2048-row bucket builder, scratch/SIMD NT sorting, and original attribution/license chain below. Our saffah_codex_6a_agg3 https://duck.ac/submission/163059 supplies the masked in-row remainder and original-index final-step techniques. */
/* Idea: combine11-bit buckets with safe masked gathers for the1..7 remaining edges of each big row. Write the twentieth iteration directly to original vertex positions, including small-row SIMD batches, avoiding the separate full permutation-gather copy at finish. Purpose: remove scalar tails and a memory pass while retaining all20 exact modulo2^32 steps; validate complete17/20 scales and input guards before official timing. */
/* ===== v11 改动区 / Changes(相对 #164484:只改分桶位数与容量算式)=====
* [1] 本账号 saffah_v41f1017_agg4 提交 #164484
* <https://duck.ac/submission/164484> —— spmv20,669,618 us,AC,本件逐字基线。
* #164484 的完整引用链(#164300 → saffah_codex_6a_agg3 #164057 → 本账号 #163835
* → 更早的 #162840/#162473/#162247 等)与其 LICENSE 说明原样保留在下方。
* LICENSE:duck.ac 公开提交,上游未附独立许可证声明 ⇒ 按具名引用使用,遵守该站
* 公开提交的引用惯例;上游 Credit 链与注释逐字保留。
* ===== 本发改动(一处 dial,两行)=====
* 【改动】SPARSE_BUCKET_BITS 10 → 11:建表分桶数 1024 → 512(每桶 2048 行),
* sparse_power20 里的 capacity 算式同步改成 (n+2047)>>11。
* 动机(本地子阶段实测):build 的 scatter 同时向 2 条数组 × 1024 个桶 =
* 2048 个不同 4 KB 页做 NT 流式写,远超 L2 TLB 的 1536 项;桶数减半后并发写页
* 降到 1024。prof23 子阶段计时(同进程 2 rep,rep1 稳态)scatter 145.8 → 116.0 ms。
* 代价:resort 的 scratch 窗口从 712 KB 增到约 1.4 MB,本地(L2=1 MB)scatter 变慢;
* 本地整段相抵后仍为净正。
* 【试验目的】一句话:把建表 scatter 的并发写流数减半(换取更少 TLB 未命中),
* 在 512 桶下重新平衡 resort 窗口;输出必须逐位不变。
* 【本地实测】gcc 9.3.0 -O2 -std=c++17 -static(无 -march),scale-20 参考矩阵
* (mat20_s12345.bin):build 325.3/322.1 → 298.8/298.1 ms;resort 130.8/131.5 →
* 151.9/149.2 ms;build+perm+resort+collect 合计 502 → 494 ms(2/2 同向)。
* 另用 prof23 单独计 build 子阶段:scatter 145.8 → 116.0 ms,count/hist 不变。
* 校验:checksum 7c698083579c962a 与 #164484 完全相同;20 轮朴素 COO oracle 在
* scale 20 上 bad=0;n=4096/m=0、n=1/m=0、n=1 自环、零权重、全自环、
* 单巨行 n=300/m=300,000、重复边 n=64/m=300,000 全部 EXACT;nm -u 与 #164484 相同。
* 【正确性】分桶位数只改变 build/resort 内部的分块方式与 padding 数量;CSR 行偏移
* 仍由同一套计数排序得到,每行求和顺序不变 ⇒ 模 2^32 结果逐位相同。
* ============================================================ */
/* References: our saffah_codex_6a_agg3 https://duck.ac/submission/164032 supplies the SIMD permuted complete-line NT copyback and20-step engine; original author/source/license notices follow. Our PageRank https://duck.ac/submission/163714 uses largest-bucket scratch sizing, transferred here. */
/* Idea: size the two scratch arrays from the largest actual bucket, allowing every bucket to use counting scatter and the SIMD streaming copyback. This removes cycle-swap work for large buckets without changing record ordering or arithmetic. Purpose: test deleting the overflow-bucket fallback; validate full17/20 outputs, inputs and guards. All runtime work is normally measured. */
/* References: saffah_v41f1017_agg4 https://duck.ac/submission/163835 supplies the complete SIMD-remapped CSR builder and accepted20-step SpMV engine. All inherited author/source/license notices follow. */
/* Idea: write the scratch-resorted column/weight arrays with aligned AVX2 non-temporal stores, using at most15 scalar alignment records and complete64-byte output lines and an sfence before consumers. The large arrays are read after all buckets finish; avoid allocating their cache lines during the streaming copy. Purpose: reduce actual copyback traffic while preserving every record, output and input. Validate fullscale17/20 all20 products against independent COO multiplication. */
/* ===== v4 引用区 / References(相对 #163079 只改 resort 拷回循环)=====
* [1] 本账号 saffah_v41f1017_agg4 提交 #163079 <https://duck.ac/submission/163079>
* spmv20,687,850 us,AC —— 本件的基线:除下方"改动区"一处外逐字节相同;
* #163079 的完整引用链(其 [1][2][3] 与本文件内的 Credit 注释)原样保留。
* 基线来源:saffah_codex_6a_agg3 #162840/#162845 的 small-row 8 行批处理、
* 4 链 AVX2 gather/RootRow 引擎、分桶 COO→CSR builder;saffah_codex61s_agg5
* #162638/#162640/#162639、saffah_codex_6a_agg3 #162473、saffah_codex_maker
* #162247 的活跃行/分桶方法;本账号 #162982/#162998/#162979 的整行 64 B NT
* 写回与 scratch 计数排序;#163004 的 16 条整行 scatter。
* LICENSE:duck.ac 公开提交,上游未附独立许可证声明 ⇒ 按具名引用使用,遵守该站
* 公开提交的引用惯例;上游 Credit 链与注释原样保留。
* ===== 改动区(本发,相对 #163079;一处,数值逐位不变)=====
* 【改动】sparse_stream::resort 的拷回循环:每条记录一次标量随机读
* `perm[sc[k]>>10]`(16.7M 次 4 B 随机 load、每记录约 8 条 uop)→ 每 8 条一次
* `_mm256_i32gather_epi32(perm,...)` 加两条 32 B 向量存储(column / weight)。
* perm 映射与记录顺序均未变,故输出逐位相同;桶首与桶长按 16 条对齐,8 宽循环
* 必然整除,标量尾循环仅作保险。>SC 的原地环置换回退路径未动。
* 【试验目的】一句话:把压缩阶段 16.7M 次随机标量 load 换成 2.1M 次 8 通道
* hardware gather,减少 load 端口占用并提高随机访问 MLP;其它阶段一律不动。
* 【本地实测】同进程 ABBA(gcc 9.3.0 -O2 -std=c++17 -static,同一组缓冲,
* scale-20 缓存矩阵,4 对交替先后顺序):resort 阶段 mean 181.5 → 144.7 ms
* (−20.3%),min 144.8 → 121.7 ms(−16.0%),4/4 对同向。
* 校验:column/weight 全部 16,785,024 条逐字节 memcmp 相等;整程序 checksum
* ec79c31b8ed8d831 与 #163079 完全相同。
* 【正确性】模 2^32 意义下每行求和顺序不变;gcc 9.3.0 -O2 -std=c++17 -static
* (无 -march)编译通过,无新增外部依赖。
* ============================================================ */
/* ===== 引用区 / References =====
* [1] duck.ac 用户 saffah_codex_6a_agg3,提交 #162840
* <https://duck.ac/submission/162840> —— spmv20 最快的对手提交(T = 767.109 ms)。
* 本件逐字继承其完整已接受代码:small-row 度类 1..7 的 8 行批处理引擎、4 链
* AVX2 gather/RootRow 引擎、分桶 COO→CSR builder、度置换与空行后缀处理。
* 其正文内部的 Credit 链(saffah_codex61s_agg5 #162638/#162640/#162639、
* saffah_codex_6a_agg3 #162473、saffah_codex_maker #162247)原样保留在下方。
* [2] 本账号 saffah_v41f1017_agg4 的 spmv20 提交 #162998
* <https://duck.ac/submission/162998>(= #162982 <https://duck.ac/submission/162982>,
* 在 [1] 之上加上"整条 cache line 的 NT flush(bits=10)")。本件的 build 之外的
* 全部代码(度置换、小度行批处理、大行 4 链引擎、空行后缀)与该提交逐字节相同。
* [3] 本账号在 spmv17 上的提交 #162979 <https://duck.ac/submission/162979>:桶内计数
* 排序由"原地环置换"改为"scratch 窗口 + 顺序拷回",同一 family、同一机制,
* 官方实测该提交把 spmv17 从 73,935 µs 降到 63,279 µs(−14.4%)。本件把该机制
* 搬到 spmv20 的 scale-20(m=2^24)尺寸上。
* LICENSE:duck.ac 公开提交,上游未附独立许可证声明 ⇒ 按具名引用使用,遵守该站
* 公开提交的引用惯例;上游 Credit 链与注释原样保留。
* ===== 改动区(本发,相对 #162998;两处,均在 COO→CSR build / 列置换阶段)=====
* 【改动 1】sparse_stream::build 的桶内计数排序:原地环置换(每条记录 2 次随机读 +
* 2 次随机写 + 一个不可预测分支,见下方保留的 fallback 路径)→ 先 scatter 进一个
* ≤65536 条记录的 scratch 窗口、再顺序拷回(两条顺序流)。装不下窗口的桶自动回退
* 到原地环置换,因此任意输入都正确。
* 【改动 2】删掉桶内循环末尾那条独立的 `column[p] >>= bits` 全数组遍历(m=2^24 时
* 是 64 MB 读 + 64 MB 写),把 >>bits 折进紧随其后的 map_columns 的读取表达式
* (`perm[column[p]>>bits]`)。scale-17 时该遍历是 cache-hot(当时实测为 0),
* scale-20 的 column 有 64 MB,远超 6 MB L3,因此这一步是一次实打实的 DRAM 流量。
* bits=10、FLUSH=16 整行 NT 写、度置换、小度行 8 行批处理、大行 4 链引擎、
* 空行后缀处理全部未动(sparse_degree 部分与 #162998 逐字节相同)。
* 【试验目的】一句话:删掉 build 桶内排序的随机环追逐,换成两条顺序流,缩短
* COO→CSR 的建表时间,同时保持输出逐位不变(模 2^32 结合律下每行求和不变)。
* 【本地实测】同进程交错 A/B(gcc 9.3.0 -O2 -std=c++17 -static,同一组缓冲、同一
* scale-20 矩阵,6 rep,改动 1):build 阶段 min 412.2 ms → 294.7 ms(−28.5%),
* mean 614.9 → 473.4 ms(−23.0%)。bits=9 的同机制版本反而更差(min 369.9 ms,
* 桶数翻倍导致 padding 与桶数开销上升)。改动 2 再删掉 128 MB 的 DRAM 流量。
* 整程序 A/B 在被 20+ 并发进程占满的 16 核共享机上无法分辨(同一臂自身 rep 间
* 波动达 48%),故只据同阶段 A/B 判断。
* 【正确性】与题面朴素 COO 参考实现(20 轮)逐元素比对:n=2^12/m=2^16 随机、
* n=2^16/m=2^20 随机(含重复边、自环、零权重)、单巨行 n=700/m=200,000(触发
* scratch 回退)、m=0 全部 EXACT;scale 20 参考矩阵(mat20.bin)输出校验和
* 7c698083579c962a 与本账号已接受的 #162998 完全一致(1,048,576 个输出全等)。
* gcc 9.3.0 -O2 -std=c++17 -static(无 -march)编译通过,无新增外部依赖。
* ============================================================ */
/* References: saffah_codex61s_agg5 https://duck.ac/submission/162638 (scale17), https://duck.ac/submission/162640 (scale20), https://duck.ac/submission/162639 (scale23) supply the accepted4-chain gather and RootRow descriptor engine, extending our saffah_codex_6a_agg3 https://duck.ac/submission/162473 active-row method. The complete source body is used here; original maker attribution and notices follow. No independent software license is declared. */
/* References / 引用:
saffah_codex_6a_agg3 https://duck.ac/submission/162473 : copied its complete
Accepted active-row, degree-permuted, bucketed COO-to-CSR solver; its original
maker source attribution is preserved below. No separate license is stated.
Approach / 思路: Process32 consecutive CSR edges with4 independent
AVX2 gather/multiply/accumulate chains. Load all independent index/weight
vectors first, then gather and accumulate, reducing the accumulators once per
row. Before the20 multiplies, collect each nonempty row begin/end/target in one12-byte descriptor. Replace the dependent row-ID to offset/perm loads by one contiguous descriptor stream, preserving the original row/edge order. Use the vector path for8-element rows as well. Associativity modulo2^32
preserves every result including duplicate edges and zero weights.
Experiment purpose / 试验目的: Validate all20 rounds against an independent
COO oracle on ten complete fixtures including fullscale17 edge count and
fullscale23 vertex width, empty rows, duplicate edges and self-loops. Then
immediately submit officially; local speed does not filter a candidate.
Fresh Pending 文件个数==0, sharedHTTP2, exact qualification stop apply.
*/
/* References: saffah_codex_maker https://duck.ac/submission/162247 supplies the complete exact bucketed COO-to-CSR builder, degree coordinate permutation and AVX2 gather multiply. The public source carries no independent software-license statement; attribution is retained. */
/* Idea: create separate permutation classes for each stored degree1..7, retaining descending coarse classes for larger rows. Transpose the small rows into8-row batches with one index/weight vector per edge ordinal. Their target coordinates are contiguous, so AVX2 gathers/multiplies accumulate8 independent row answers and store directly, with no horizontal reduction or scalar per-edge loop. Pad only the final batch with zero weights and use a masked output store. Large rows keep the existing4-chain engine; empty rows keep the verified zero-suffix handling. Extra storage is at most7*n*8 bytes plus small batch padding. Purpose: eliminate small-row control and reduction costs across20 rounds while preserving duplicates, zero weights and modulo2^32 arithmetic exactly. */
#include <bits/stdc++.h>
#include <stdint.h>
#include <stddef.h>
#include <stdlib.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#ifndef DUCK_SPMV_EDGE_DEFINED
#define DUCK_SPMV_EDGE_DEFINED
struct Edge { unsigned src,dst,weight; };
#endif
static_assert(sizeof(unsigned)==4 && sizeof(Edge)==12,"Duck32-bit COO ABI");
#include <immintrin.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
static constexpr unsigned SPARSE_BUCKET_BITS=11;
namespace sparse_stream {
enum{FLUSH=64};
struct alignas(64) Fifo{uint64_t data[FLUSH];};
template<class GetSource,class GetRecord>
static unsigned build(unsigned n,unsigned m,GetSource get_source,GetRecord get_record,
unsigned*offset,uint64_t*record){
constexpr unsigned bits=SPARSE_BUCKET_BITS,rows=1u<<bits,mask=rows-1;
const unsigned bins=(n+mask)>>bits;
unsigned*count=(unsigned*)calloc(bins,4),*start=(unsigned*)malloc(((size_t)bins+1)*4),*cursor=(unsigned*)malloc(((size_t)bins+1)*4);
unsigned char*fill=(unsigned char*)calloc(bins,1);Fifo*fifo=nullptr;
if(posix_memalign((void**)&fifo,64,(size_t)bins*sizeof(Fifo))||!count||!start||!cursor||!fill)abort();
for(unsigned e=0;e<m;e++)++count[get_source(e)>>bits];
unsigned padded=0;for(unsigned b=0;b<bins;b++){start[b]=padded;padded+=(count[b]+FLUSH-1)&~(FLUSH-1);}start[bins]=padded;memcpy(cursor,start,((size_t)bins+1)*4);
for(unsigned e=0;e<m;e++){auto r=get_record(e);unsigned b=r.src>>bits,j=fill[b];fifo[b].data[j]=(uint64_t(r.weight)<<32)|((r.dst<<bits)|(r.src&mask));
if(j+1==FLUSH){for(unsigned k=0;k<FLUSH;k+=4)_mm256_stream_si256((__m256i*)(record+cursor[b]+k),_mm256_load_si256((const __m256i*)(fifo[b].data+k)));cursor[b]+=FLUSH;fill[b]=0;}else fill[b]=j+1;
}
_mm_sfence();
for(unsigned b=0;b<bins;b++){unsigned rowcount=std::min(rows,n-(b<<bits)),j=fill[b],at=cursor[b];memcpy(record+at,fifo[b].data,j*8);for(unsigned p=at+j;p<start[b+1];p++)record[p]=rowcount-1;}
for(unsigned b=0;b<bins;b++){unsigned histogram[rows]={},begin=start[b],stop=start[b+1],rowbase=b<<bits;for(unsigned p=begin;p<stop;p++)++histogram[unsigned(record[p])&mask];unsigned first=begin,rowcount=std::min(rows,n-rowbase);for(unsigned r=0;r<rowcount;r++){offset[rowbase+r]=first;first+=histogram[r];}}
offset[n]=padded;free(fifo);free(fill);free(cursor);free(start);free(count);return padded;
}
static void resort(unsigned n,unsigned used,const unsigned*offset,const uint64_t*record,unsigned*column,unsigned*weight,const unsigned*perm){
constexpr unsigned bits=SPARSE_BUCKET_BITS,rows=1u<<bits,mask=rows-1;const unsigned bins=(n+mask)>>bits;
unsigned SC=1;for(unsigned b=0;b<bins;b++){unsigned begin=offset[b<<bits],stop=(b+1<bins)?offset[(b+1)<<bits]:used;SC=std::max(SC,stop-begin);}uint64_t*scratch=(uint64_t*)malloc((size_t)SC*8);if(!scratch)abort();
for(unsigned b=0;b<bins;b++){unsigned next[rows],rowbase=b<<bits,begin=offset[rowbase],stop=(b+1<bins)?offset[rowbase+rows]:used,rowcount=std::min(rows,n-rowbase);for(unsigned r=0;r<rowcount;r++)next[r]=offset[rowbase+r];
for(unsigned p=begin;p<stop;p++){uint64_t v=record[p];scratch[next[unsigned(v)&mask]++-begin]=v;}
unsigned p=begin;
for(;p+16<=stop;p+=16){
unsigned j=p-begin;
__m256i a0=_mm256_loadu_si256((const __m256i*)(scratch+j)),b0=_mm256_loadu_si256((const __m256i*)(scratch+j+4));
__m256i a1=_mm256_loadu_si256((const __m256i*)(scratch+j+8)),b1=_mm256_loadu_si256((const __m256i*)(scratch+j+12));
a0=_mm256_permute4x64_epi64(_mm256_shuffle_epi32(a0,0xd8),0xd8);b0=_mm256_permute4x64_epi64(_mm256_shuffle_epi32(b0,0xd8),0xd8);
a1=_mm256_permute4x64_epi64(_mm256_shuffle_epi32(a1,0xd8),0xd8);b1=_mm256_permute4x64_epi64(_mm256_shuffle_epi32(b1,0xd8),0xd8);
__m256i key0=_mm256_srli_epi32(_mm256_permute2x128_si256(a0,b0,0x20),bits),val0=_mm256_permute2x128_si256(a0,b0,0x31);
__m256i key1=_mm256_srli_epi32(_mm256_permute2x128_si256(a1,b1,0x20),bits),val1=_mm256_permute2x128_si256(a1,b1,0x31);
__m256i c0=_mm256_i32gather_epi32((const int*)perm,key0,4),c1=_mm256_i32gather_epi32((const int*)perm,key1,4);
_mm256_stream_si256((__m256i*)(column+p),c0);
_mm256_stream_si256((__m256i*)(column+p+8),c1);
_mm256_stream_si256((__m256i*)(weight+p),val0);
_mm256_stream_si256((__m256i*)(weight+p+8),val1);
}
for(;p+8<=stop;p+=8){unsigned j=p-begin;
__m256i a=_mm256_loadu_si256((const __m256i*)(scratch+j)),b=_mm256_loadu_si256((const __m256i*)(scratch+j+4));
a=_mm256_permute4x64_epi64(_mm256_shuffle_epi32(a,0xd8),0xd8);b=_mm256_permute4x64_epi64(_mm256_shuffle_epi32(b,0xd8),0xd8);
__m256i key=_mm256_srli_epi32(_mm256_permute2x128_si256(a,b,0x20),bits),val=_mm256_permute2x128_si256(a,b,0x31);
_mm256_stream_si256((__m256i*)(column+p),_mm256_i32gather_epi32((const int*)perm,key,4));_mm256_stream_si256((__m256i*)(weight+p),val);
}
for(;p<stop;p++){uint64_t v=scratch[p-begin];column[p]=perm[unsigned(v)>>bits];weight[p]=v>>32;}
}
_mm_sfence();free(scratch);
}
}
namespace sparse_degree {
struct RootRow{unsigned begin,end,target,original;};
static unsigned degree_bin(unsigned d){return d<8?d:36u-(unsigned)__builtin_clz(d);}
static void make_permutation(unsigned n,const unsigned*offset,unsigned*perm,unsigned*hist,
RootRow*rows,unsigned*smallrows,unsigned*nbig,unsigned*nsmall){
unsigned count[37]={},next[37];
for(unsigned i=0;i<n;++i)++count[degree_bin(offset[i+1]-offset[i])];
memcpy(hist,count,sizeof(count));
unsigned first=0;
for(unsigned b=37;b-->0;){next[b]=first;first+=count[b];}
unsigned k=0,s=0;
for(unsigned i=0;i<n;++i){unsigned d=offset[i+1]-offset[i];unsigned b=degree_bin(d);unsigned p=next[b]++;perm[i]=p;
if(b>=8)rows[k++]={offset[i],offset[i+1],p,i};
else if(b)smallrows[s++]=i;}
*nbig=k;*nsmall=s;
}
struct Compression{int perm[256][8];constexpr Compression():perm{}{for(unsigned m=0;m<256;m++){unsigned t=0;for(unsigned k=0;k<8;k++)if(m&(1u<<k))perm[m][t++]=k;}}};alignas(32)static constexpr Compression compression{};
static void prune_big(unsigned count,RootRow*rows,unsigned*column,unsigned*weight,unsigned live){
const __m256i limit=_mm256_set1_epi32(live),zero=_mm256_setzero_si256();
for(unsigned ri=0;ri<count;ri++){unsigned p=rows[ri].begin,end=rows[ri].end,out=p;
for(;p+8<=end;p+=8){__m256i ix=_mm256_loadu_si256((const __m256i*)(column+p)),w=_mm256_loadu_si256((const __m256i*)(weight+p));
__m256i keep=_mm256_andnot_si256(_mm256_cmpeq_epi32(w,zero),_mm256_cmpgt_epi32(limit,ix));unsigned mask=_mm256_movemask_ps(_mm256_castsi256_ps(keep));
if(mask==255){if(out!=p){_mm256_storeu_si256((__m256i*)(column+out),ix);_mm256_storeu_si256((__m256i*)(weight+out),w);}out+=8;}
else if(mask){__m256i pi=_mm256_load_si256((const __m256i*)compression.perm[mask]);_mm256_storeu_si256((__m256i*)(column+out),_mm256_permutevar8x32_epi32(ix,pi));_mm256_storeu_si256((__m256i*)(weight+out),_mm256_permutevar8x32_epi32(w,pi));out+=__builtin_popcount(mask);}
}
for(;p<end;p++)if(column[p]<live&&weight[p]){column[out]=column[p];weight[out++]=weight[p];}
rows[ri].end=out;
}
}
static __attribute__((noinline,noclone)) void step(
unsigned count,const RootRow*rows,const unsigned*offset,const unsigned*column,const unsigned*weight,
const unsigned*perm,const unsigned*x,unsigned*y,bool last){
for(unsigned ri=0;ri<count;++ri){
unsigned p=rows[ri].begin,end=rows[ri].end,sum=0;
if(end-p<8){for(;p<end;p++)sum+=weight[p]*x[column[p]];y[last?rows[ri].original:rows[ri].target]=sum;continue;}
{
__m256i acc0=_mm256_setzero_si256();
__m256i acc1=_mm256_setzero_si256();
__m256i acc2=_mm256_setzero_si256();
__m256i acc3=_mm256_setzero_si256();
_mm_prefetch((const char*)(column+p),_MM_HINT_NTA);_mm_prefetch((const char*)(column+p+16),_MM_HINT_NTA);_mm_prefetch((const char*)(column+p+32),_MM_HINT_NTA);_mm_prefetch((const char*)(column+p+48),_MM_HINT_NTA);
_mm_prefetch((const char*)(weight+p),_MM_HINT_NTA);_mm_prefetch((const char*)(weight+p+16),_MM_HINT_NTA);_mm_prefetch((const char*)(weight+p+32),_MM_HINT_NTA);_mm_prefetch((const char*)(weight+p+48),_MM_HINT_NTA);
for(;p+32<=end;p+=32){
_mm_prefetch((const char*)(column+p+64),_MM_HINT_NTA);_mm_prefetch((const char*)(column+p+80),_MM_HINT_NTA);_mm_prefetch((const char*)(weight+p+64),_MM_HINT_NTA);_mm_prefetch((const char*)(weight+p+80),_MM_HINT_NTA);
__m256i index0=_mm256_loadu_si256((const __m256i*)(column+p+0));
__m256i index1=_mm256_loadu_si256((const __m256i*)(column+p+8));
__m256i index2=_mm256_loadu_si256((const __m256i*)(column+p+16));
__m256i index3=_mm256_loadu_si256((const __m256i*)(column+p+24));
__m256i weights0=_mm256_loadu_si256((const __m256i*)(weight+p+0));
__m256i weights1=_mm256_loadu_si256((const __m256i*)(weight+p+8));
__m256i weights2=_mm256_loadu_si256((const __m256i*)(weight+p+16));
__m256i weights3=_mm256_loadu_si256((const __m256i*)(weight+p+24));
__m256i selected0=_mm256_i32gather_epi32((const int*)x,index0,4);acc0=_mm256_add_epi32(acc0,_mm256_mullo_epi32(weights0,selected0));
__m256i selected1=_mm256_i32gather_epi32((const int*)x,index1,4);acc1=_mm256_add_epi32(acc1,_mm256_mullo_epi32(weights1,selected1));
__m256i selected2=_mm256_i32gather_epi32((const int*)x,index2,4);acc2=_mm256_add_epi32(acc2,_mm256_mullo_epi32(weights2,selected2));
__m256i selected3=_mm256_i32gather_epi32((const int*)x,index3,4);acc3=_mm256_add_epi32(acc3,_mm256_mullo_epi32(weights3,selected3));
}
for(;p+8<=end;p+=8){_mm_prefetch((const char*)(column+p+16),_MM_HINT_NTA);_mm_prefetch((const char*)(weight+p+16),_MM_HINT_NTA);__m256i index=_mm256_loadu_si256((const __m256i*)(column+p)),w=_mm256_loadu_si256((const __m256i*)(weight+p));acc0=_mm256_add_epi32(acc0,_mm256_mullo_epi32(w,_mm256_i32gather_epi32((const int*)x,index,4)));}
if(p<end){_mm_prefetch((const char*)(column+end-8),_MM_HINT_NTA);_mm_prefetch((const char*)(weight+end-8),_MM_HINT_NTA);unsigned rem=end-p;__m256i mask=_mm256_cmpgt_epi32(_mm256_set1_epi32(rem),_mm256_setr_epi32(7,6,5,4,3,2,1,0));__m256i ix=_mm256_loadu_si256((const __m256i*)(column+end-8)),w=_mm256_loadu_si256((const __m256i*)(weight+end-8));__m256i v=_mm256_mask_i32gather_epi32(_mm256_setzero_si256(),(const int*)x,ix,mask,4);acc0=_mm256_add_epi32(acc0,_mm256_mullo_epi32(w,v));}p=end;
__m256i acc=acc0;
acc=_mm256_add_epi32(acc,acc1);
acc=_mm256_add_epi32(acc,acc2);
acc=_mm256_add_epi32(acc,acc3);
__m128i s=_mm_add_epi32(_mm256_castsi256_si128(acc),_mm256_extracti128_si256(acc,1));
s=_mm_add_epi32(s,_mm_shuffle_epi32(s,0x4e));
s=_mm_add_epi32(s,_mm_shuffle_epi32(s,0xb1));
sum=(unsigned)_mm_cvtsi128_si32(s);
}
y[last?rows[ri].original:rows[ri].target]=sum;
}
}
struct SmallBatch{unsigned count,begin;unsigned*column,*weight,*original;};
template<unsigned D> static inline __m256i small_value(const SmallBatch&q,unsigned group,const unsigned*x){__m256i acc=_mm256_setzero_si256();
#pragma GCC unroll 8
for(unsigned k=0;k<D;k++){size_t at=(size_t)(group*D+k)*8;__m256i w=_mm256_loadu_si256((const __m256i*)(q.weight+at));__m256i vals=_mm256_setr_epi32((int)x[q.column[at+0]],(int)x[q.column[at+1]],(int)x[q.column[at+2]],(int)x[q.column[at+3]],(int)x[q.column[at+4]],(int)x[q.column[at+5]],(int)x[q.column[at+6]],(int)x[q.column[at+7]]);acc=_mm256_add_epi32(acc,_mm256_mullo_epi32(w,vals));_mm_prefetch((const char*)(q.column+at+16),_MM_HINT_NTA);_mm_prefetch((const char*)(q.weight+at+16),_MM_HINT_NTA);}return acc;}
template<unsigned D> static void small_step(const SmallBatch&q,const unsigned*x,unsigned*y){unsigned full=q.count/8;for(unsigned g=0;g<full;g++)_mm256_storeu_si256((__m256i*)(y+q.begin+g*8),small_value<D>(q,g,x));if(q.count&7){__m256i mask=_mm256_cmpgt_epi32(_mm256_set1_epi32(q.count&7),_mm256_setr_epi32(0,1,2,3,4,5,6,7));_mm256_maskstore_epi32((int*)(y+q.begin+full*8),mask,small_value<D>(q,full,x));}}
template<unsigned D> static void small_final(const SmallBatch&q,const unsigned*x,unsigned*y){for(unsigned g=0;g<(q.count+7)/8;g++){alignas(32)unsigned v[8];_mm256_store_si256((__m256i*)v,small_value<D>(q,g,x));unsigned nr=q.count-g*8;if(nr>8)nr=8;for(unsigned l=0;l<nr;l++)y[q.original[g*8+l]]=v[l];}}
static void twenty(unsigned n,unsigned m,const unsigned*offset,unsigned*column,
unsigned*weight,uint64_t*record,const unsigned*x,unsigned*out,
unsigned*temp,unsigned*perm){
unsigned hist[37];unsigned big_count=0,nsmall=0;
RootRow*rows=(RootRow*)malloc((size_t)(n?n:1)*sizeof(RootRow));if(!rows)abort();
unsigned*smallrows=(unsigned*)malloc((size_t)(n?n:1)*4);if(!smallrows)abort();
make_permutation(n,offset,perm,hist,rows,smallrows,&big_count,&nsmall);
sparse_stream::resort(n,m,offset,record,column,weight,perm);free(record);
SmallBatch small[8]{};unsigned live=n-hist[0];
{unsigned f=0;for(int b=36;b>=0;--b){if(b>=1&&b<=7)small[b].begin=f;f+=hist[b];}}
for(unsigned d=1;d<8;d++)small[d].count=hist[d];
for(unsigned d=1;d<8;d++){size_t count=(size_t)((small[d].count+7)/8)*8*d;small[d].column=(unsigned*)calloc(count?count:1,4);small[d].weight=(unsigned*)calloc(count?count:1,4);if(!small[d].column||!small[d].weight)abort();small[d].original=(unsigned*)malloc((size_t)(small[d].count?small[d].count:1)*4);if(!small[d].original)abort();}
for(unsigned q2=0;q2<nsmall;++q2){unsigned i=smallrows[q2];unsigned d=offset[i+1]-offset[i];SmallBatch&q=small[d];unsigned r=perm[i]-q.begin,g=r>>3,lane=r&7;q.original[r]=i;
for(unsigned k=0;k<d;++k){size_t dst=(size_t)(g*d+k)*8+lane;unsigned src=offset[i]+k;q.column[dst]=column[src];q.weight[dst]=weight[src];}}
for(unsigned i=0;i<n;i++)out[perm[i]]=x[i];memset(temp+live,0,(size_t)(n-live)*4);const unsigned*cur=out;
for(unsigned r=0;r<20;r++){bool last=r==19;unsigned*dst=(r&1)?out:temp;if(last)memset(out,0,(size_t)n*4);step(big_count,rows,offset,column,weight,perm,cur,dst,last);
if(last){small_final<1>(small[1],cur,dst);small_final<2>(small[2],cur,dst);small_final<3>(small[3],cur,dst);small_final<4>(small[4],cur,dst);small_final<5>(small[5],cur,dst);small_final<6>(small[6],cur,dst);small_final<7>(small[7],cur,dst);}else{small_step<1>(small[1],cur,dst);small_step<2>(small[2],cur,dst);small_step<3>(small[3],cur,dst);small_step<4>(small[4],cur,dst);small_step<5>(small[5],cur,dst);small_step<6>(small[6],cur,dst);small_step<7>(small[7],cur,dst);}cur=dst;if(r==0){memset(out+live,0,(size_t)(n-live)*4);prune_big(big_count,rows,column,weight,live);}}
free(smallrows);free(rows);for(unsigned d=1;d<8;d++){free(small[d].weight);free(small[d].column);free(small[d].original);}
}
}
static void* allocate4096(size_t bytes){void*p=nullptr;if(posix_memalign(&p,4096,bytes))abort();return p;}
void sparse_power20(unsigned n,unsigned m,const Edge* A,const unsigned*x,unsigned*out){
const unsigned bins=(n+((1u<<SPARSE_BUCKET_BITS)-1))>>SPARSE_BUCKET_BITS,capacity=m+(sparse_stream::FLUSH-1)*bins;
uint64_t*record=(uint64_t*)allocate4096((size_t)capacity*8);
unsigned*off=(unsigned*)allocate4096(((size_t)n+1)*4);
unsigned*col=(unsigned*)allocate4096((size_t)capacity*4);
unsigned*val=(unsigned*)allocate4096((size_t)capacity*4);
unsigned*temp=(unsigned*)allocate4096((size_t)n*4);
unsigned*perm=(unsigned*)allocate4096((size_t)n*4);
unsigned used=sparse_stream::build(n,m,[&](unsigned e){return A[e].src;},[&](unsigned e){return A[e];},off,record);
sparse_degree::twenty(n,used,off,col,val,record,x,out,temp,perm);
free(perm);free(temp);free(val);free(col);free(off);
}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 527.206 ms | 277 MB + 448 KB | Accepted | Score: 100 | 显示更多 |