cache-oblivious 复现程序

目录

环境:AMD EPYC 9754 (2 vCPUs, KVM),Linux 6.8.0-90-generic,GCC 13.3.0,Python 3.12 / matplotlib 3.11.2(.algo-fix/mplenv)。所有指标均为确定性模拟的精确 LRU 缓存行传输次数与索引映射轨迹,与时钟无关,重复运行输出逐字节一致。

文件 内容 命令
lru_cache.h \(O(1)\) 精确全相联 LRU 缓存行模拟器(开放寻址哈希 + 双向链表) 头文件
co_bench.c 15 节点 vEB 轨迹、矩阵转置(\(512\times 512\))、矩阵乘法(\(128\times 128\))、静态查找树(\(N=2^{20}-1\),\(20{,}000\) 次查询)的多尺度 LRU 模拟与验证 gcc -O2 -Wall -Wextra -o co_bench co_bench.c -lm && ./co_bench > results/sim.txt && rm -f co_bench
draw_figures.py 生成 ../veb-layout.svg、../recursive-matmul-zorder.svg、../funnel-sort.svg python3 draw_figures.py
plot_misses.py 由 results/sim.txt 生成 ../co-misses.svg python3 plot_misses.py results/sim.txt
run.sh 一键编译、O2 与 ASan/UBSan 交叉验证并重绘全部图表 sh run.sh
results/sim.txt 完整模拟与 15 节点轨迹输出 运行产物

ASan/UBSan 完整检查通过:gcc -O1 -g -Wall -Wextra -fsanitize=address,undefined -fno-sanitize-recover=all -o co_bench_asan co_bench.c -lm && ./co_bench_asan 与 -O2 输出逐字节一致,无任何内存或未定义行为错误。

源码下载

本文相关源码已整理,共 5 个文件。

打开下载目录 →


By .