M. 真忙的管理员-MapReduce SpGEMM¶

分数：150 分

背景¶

公元 2147 年，人类在近地轨道和月面之间建立了多个 “星港” 中转站。货物在星港之间通过不同航线流转，航线会受到太阳风、碎片云和军用管制的影响，导致部分航线的可用性和成本剧烈变化。

你是小北，是「帝江号」的航线调度系统的管理员。为了在极短时间内重新规划路由，调度系统需要快速估计：

星港之间的两跳可达性强度（从 $A$ 经由中转站到 $B$ 的潜在效率）并为每个星港找出最值得优先保障的 $Top-K$ 目的星港

这个计算本质上是一个大规模稀疏矩阵乘法：

给定稀疏矩阵 $A$ （星港→中转可达强度）与 $B$ （中转→星港可达强度），计算：

$C = A \times B$

并对每一行（每个源星港）输出 $Top-K$ 的目的星港及分数。

题目¶

基于 MPI MapReduce 的稀疏矩阵乘法，用于计算 top-K 二跳可达性分数。输入为 $A$ （ $M \times K$ ）和 $B$ （ $K \times N$ ）两个矩阵的 COO 分片，程序先按共享键 $k$ 做一轮 shuffle 并完成外积累加，再按行 $i$ 做第二轮 shuffle 合并结果，最后为每个源行输出得分最高的 $K$ 个目标。

参赛者只需修改 src/spgemm_topk.cpp中的spgemm_topk 函数， I/O 和评测框架不要动。

构建¶

mkdir -p build && cd build
cmake ..
make -j

依赖： CMake >= 3.14 ， MPI 工具链（ OpenMPI 或 MPICH 均可）。

生成样例数据¶

python3 scripts/gen_coo.py --M 8 --K 6 --N 8 --densityA 0.2 --densityB 0.2 --parts 2 --seed 7 --out data

会在 data/A/part-00000..和data/B/part-00000..下写入 COO 格式文件，每行一条row col value 。

运行¶

mpirun -np 4 ./mr_spgemm_topk --A data/A --B data/B --topk 3 --out out.txt

--A、--B：单个 COO 文件，或包含part-* 文件的目录。
--topk ：每行保留几个目标。
--out ：输出文件，不指定则打印到 stdout 。

输出格式：

i j1:score1 j2:score2 ...

输入输出¶

输入¶

两份稀疏矩阵数据 $A$ : 维度 $M \times K$ COO: $(i, k, val)$ $B$ : 维度 $K \times N$ COO: $(k, j, val)$ 数据以多文件分片形式提供，便于 MapReduce / 并行读取：

data/A/part-00000
data/A/part-00001
...
data/B/part-00000
data/B/part-00001
...

每行格式：

row(int) col(int) value(fp32)

输出¶

要求输出每个 $i(0..M-1)$ 对应的 $Top-K$ 目的端 $j$ ，按分数降序：

i  j1:score1  j2:score2  ...  jK:scoreK

说明¶

分两趟 shuffle 是为了避免行被拆散：第一趟按 $k$ 分发做乘加，第二趟按 $i$ 归并到同一个 rank 再取 top-K 。
累加用 double 精度，输入也按 double 解析。

评测¶

环境： cr.hpc.lcpu.dev/hpcgame/mpi:latest
程序会被运行在三个节点 intel 8358 上，每个 16 进程、 50G 内存。

测试点与评分标准¶

Case	形状 M×K×N	density A/B	parts	nnz A	nnz B	TopK	分值	TRef
1 baseline	30K³	0.01 / 0.01	48	~1M	~1M	32	10	23
2 medium	50K³	0.005 / 0.005	48	~12.5M	~12.5M	32	15	29
3 large	100K³	0.0025 / 0.0025	240	~25M	~25M	32	15	62
4 dense	10K³	0.1 / 0.1	48	~10M	~10M	32	20	44
5 tall×wide	200K×50K×200K	0.002 / 0.002	240	~20M	~20M	32	20	75
6 skinny-inner	500K×10K×500K	0.0032 / 0.0032	240	~16M	~16M	32	20	300

Scoring¶

对每个测试用例 $i$

内存分数¶

$scoreMem_i = \min(1, MBudget_i / MPeak_i)$

正确性分数¶

$scoreConf_i = 0.6 \times nDCG_i + 0.4 \times Recall_i$

如果存在错误： $scoreConf_i = 0.5 \times nDCG_i + 0.3 \times Recall_i + 0.2 \times (1 - RelL1_i)$

时间分数¶

$scoreSpeed_i = \min(1, TRef_i / T_i)$

总分数¶

$score_i = S_i \times (0.2 \times scoreMem_i + 0.3 \times scoreConf_i + 0.5 \times scoreSpeed_i)$

其中：

$S_i$ ：该测试用例的满分
$MPeak_i$ ：该用例运行期间的峰值内存（全 rank 最大值）
$MBudget_i$ ：该用例内存上限
$T_i$ ：该用例实际时间
$TRef_i$ ：该用例参考时间

evaluator¶

符号

真实 Top-K ： $G_i = (j, s_{ij})$ ，按 $s_{ij}$ 降序
预测 Top-K ： $P_i = (j, \hat{s}_{ij})$ ，按 $\hat{s}_{ij}$ 降序

仅取前 $K$ 项参与评估

$Recall@K$ 命中率

$\text{Recall}_i = \frac{|\{j \in P_i\} \cap \{j \in G_i\}|}{\max(1, |G_i|)}$

$nDCG@K$ 排序质量

$\text{gain}(j) = \max(s_{ij}, 0)$

折损累计增益

$\text{DCG}_i = \sum_{r=1}^{K} \frac{\text{gain}(j_r)}{\log_2(r+1)}$

理想 DCG

$\text{IDCG}_i = \sum_{r=1}^{K} \frac{\text{gain}(j^*_r)}{\log_2(r+1)}$

其中 $j^*_r$ 是真值 $Top-K$ 的第 $r$ 个。

$\text{nDCG}_i = \begin{cases} 1, & \text{if } \text{IDCG}_i=0 \text{ and } \text{DCG}_i=0 \\ 0, & \text{if } \text{IDCG}_i=0 \text{ and } \text{DCG}_i>0 \\ \text{DCG}_i/\text{IDCG}_i, & \text{otherwise} \end{cases}$

RelL1 （相对 L1 误差）

$\text{RelL1}_i = \begin{cases} 0, & \text{if } \sum_{(j,s) \in G_i} |s| = 0 \\ \frac{\sum_{(j,\hat{s}) \in P_i} |\hat{s} - s_{ij}|}{\sum_{(j,s) \in G_i} |s|}, & \text{otherwise} \end{cases}$

（当 $j \notin G_i$ 时， $s_{ij} = 0$ ）

总体平均

$\overline{\text{Recall}} = \frac{1}{N} \sum_i \text{Recall}_i, \quad \overline{\text{nDCG}} = \frac{1}{N} \sum_i \text{nDCG}_i, \quad \overline{\text{RelL1}} = \frac{1}{N} \sum_i \text{RelL1}_i$

附件¶

handout-spgemm