# distspmv_balanced

**Repository Path**: qmsg/distspmv_balanced

## Basic Information

- **Project Name**: distspmv_balanced
- **Description**: 分布式稀疏矩阵-向量乘法（SpMV）负载均衡算法的复现实现。
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2026-05-15
- **Last Updated**: 2026-05-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# DistSpMV_Balanced

分布式稀疏矩阵-向量乘法（SpMV）负载均衡算法的复现实现。

基于论文 "Balancing Computation and Communication in Distributed Sparse Matrix-Vector Multiplication" (CCGrid 2023)，在图划分重排序基础上，通过扩展对角块和远程矩阵非零元均衡切分，同时优化通信量与计算负载均衡。

## 环境依赖

- Linux / WSL
- OpenMPI、GCC、OpenMP、METIS

```bash
sudo apt install libopenmpi-dev openmpi-bin libmetis-dev
```

## 编译与运行

```bash
make              # 编译主程序 distspmv_balanced
make bench        # 编译基线对比二进制 (benchmark/naive, reordered, ablation)
```

运行方式：

```bash
# 主程序（论文完整算法）
mpirun -np <进程数> ./distspmv_balanced <矩阵.mtx> <线程数>

# 正确性测试
bash test/run_test.sh [进程数] [线程数] [矩阵名]

# 性能对比（6种方法横向对比）
bash benchmark/run_benchmark.sh [进程数] [线程数] [矩阵名]

# benchmark 二进制也可以直接运行
mpirun -np <进程数> benchmark/naive     <矩阵.mtx> <线程数>
mpirun -np <进程数> benchmark/reordered <矩阵.mtx> <线程数>
mpirun -np <进程数> benchmark/ablation  <矩阵.mtx> <线程数> [--no-metis] [--no-dedup] [--no-nnz-balance]
```

参数说明：
- `进程数`：默认 2，`线程数`：默认 1
- `矩阵名`：可选，默认 `lp_pilot4`，传入 `cant` 则路径为 `test/cant/cant.mtx`

## 时间测量

输出两段时间，与论文测量方式对应：

| 指标 | 测量范围 | 对应论文 |
|------|----------|----------|
| Preprocessing time | 矩阵广播后 → SpMV 循环前（METIS + 重排 + 对角扩展 + 通信计划） | Figure 7 预处理开销 |
| Avg time per iteration | 50 次 SpMV 迭代的平均（含通信+计算），`MPI_Barrier` 同步后取 `spmv_end` | Section IV-A 执行时间 |

迭代次数通过 `include/config.h` 中 `#define ITERATIONS 50` 统一控制，修改后需 `make clean && make` 重新编译。

## 算法流程

```
原始稀疏矩阵 (MTX格式)
    ↓
Step 1: METIS图划分 + 重排序
    ↓
Step 2: 对角块扩展 (Algorithm 1)
    ↓
Step 3: flag去重 + Alltoallv交换列索引 + Isend/Irecv交换值 (Algorithm 2+3)
    ↓
Step 4: nnz均衡的单循环OpenMP并行SpMV (Algorithm 4)
    ↓
结果收集 + 验证
```

## 项目结构

```
distspmv_balanced/
├── Makefile                       # 编译配置 (mpicc + METIS/OpenMP)
├── include/                       # 头文件
│   ├── config.h                  # 迭代次数等编译期配置
│   ├── csr.h                      # CSR稀疏矩阵数据结构定义
│   ├── mm_reader.h                # Matrix Market (.mtx) 文件读取
│   ├── metis_wrapper.h            # METIS图划分 + 矩阵重排序
│   ├── partition.h                # 对角块扩展与本地/远程分离
│   ├── comm.h                     # MPI通信计划 (infocount/index + Isend/Irecv缓冲区)
│   └── spmv.h                     # 并行SpMV计算 (Algorithm 4)
├── src/                           # 论文复现源码
│   ├── main.c                     # 主流程: 读取→重排→扩展→通信→SpMV→验证
│   ├── csr.c                      # CSR格式构造与转换 (csr_from_coo)
│   ├── mm_reader.c                # Matrix Market解析, 对称补全, 重复合并
│   ├── metis_wrapper.c            # METIS_PartGraphKway调用 + 按分区重排行列
│   ├── partition.c                # Algorithm 1: 对角块初始化与右边界扩展
│   ├── comm.c                     # Algorithm 2+3: flag去重 + Alltoallv交换索引 + Isend/Irecv交换值
│   └── spmv.c                     # Algorithm 4: 单循环SpMV (x预展开, nnz均衡二分查找)
├── benchmark/                     # 性能对比与ablation
│   ├── main_naive.c               # DistSpMV: 朴素分布式SpMV (无重排序/去重/均衡)
│   ├── main_reordered.c           # DistSpMV_Reordered: 仅METIS重排序, 无对角扩展
│   ├── main_balanced_ablation.c   # 完整算法独立实现, 支持 --no-* 三种消融开关
│   └── run_benchmark.sh           # 自动化对比脚本 (6种方法×指定矩阵)
└── test/
    ├── run_test.sh                # 正确性测试脚本 (mpirun + 参数检查)
    └── lp_pilot4/                 # 测试矩阵: 410×1123, nnz=5264 (线性规划)
```

## 性能对比

`make bench` 编译三个二进制：

| 二进制 | 说明 |
|:---|:---|
| `benchmark/naive` | 朴素分布式SpMV：行均分，无重排序 |
| `benchmark/reordered` | 仅METIS重排序，均匀列划分 |
| `benchmark/ablation` | 完整算法，支持开关切换 |

Ablation flags（`benchmark/ablation`）：

| Flag | 效果 |
|:---|:---|
| `--no-metis` | 均匀分块替代METIS图划分 |
| `--no-dedup` | 通信不去重 |
| `--no-nnz-balance` | 远程按行均分而非nnz均衡 |

```bash
bash benchmark/run_benchmark.sh              # 2p x 1t, lp_pilot4
bash benchmark/run_benchmark.sh 4 2           # 4p x 2t, lp_pilot4
bash benchmark/run_benchmark.sh 4 2 cant      # 4p x 2t, test/cant/cant.mtx
```

## 添加测试矩阵

从 [SuiteSparse Matrix Collection](https://sparse.tamu.edu/) 下载矩阵，解压到 `test/<矩阵名>/` 目录。使用方式：

```bash
# 方式一：第三个参数直接指定矩阵名
bash test/run_test.sh 2 1 cant
bash benchmark/run_benchmark.sh 4 2 cant

# 方式二：修改脚本中的 MATRIX 变量
# 编辑 test/run_test.sh 或 benchmark/run_benchmark.sh
MATRIX="test/your_matrix/your_matrix.mtx"
```

支持 Matrix Market (.mtx) 格式：

```
%%MatrixMarket matrix coordinate real general
M N NNZ
row col value ...
```

- 行列索引从1开始，自动转换0起始
- 支持对称矩阵自动补全、重复元素合并求和