高性能计算挑战——极限阶乘

本项目为C++小组课程作业，旨在实现多种高性能阶乘计算算法，并利用GPU加速技术进行性能优化。项目集成了自定义FFT实现、GNU多精度运算库(GMP)以及基于CUDA的CGBN库，提供了完整的性能测试与结果验证框架。

核心特性：

• 多算法实现：支持FFT乘法、分治法、素数摇摆法等多种阶乘计算算法
• CPU优化：基于GMP的高性能CPU实现，支持OpenMP多线程并行
• GPU加速：基于CGBN库的CUDA实现，支持大规模并行计算
• 完备测试：自动化测试脚本与结果验证机制

---

系统要求

硬件环境

• CPU：x86-64架构处理器，建议4核及以上
• 内存：最低8GB，建议16GB以上（计算大数阶乘时）
• GPU（可选）：NVIDIA GPU，计算能力≥7.0，显存≥4GB
• 存储：至少2GB可用磁盘空间

测试平台：

• Ubuntu 22.04 LTS
• Windows Subsystem for Linux 2 (WSL2) with Ubuntu

---

构建与安装

快速开始

# 克隆仓库
git clone https://gitee.com/lensit/cpp-factorial-hpc-lab.git
cd cpp-factorial-hpc-lab

# 安装依赖
make deps          # 安装GMP库
make cgbn          # 下载并配置CGBN库（需预先安装CUDA）

# 构建所有目标
make all

# 运行完整测试
./utilities/test.sh

构建选项

安装依赖项

# 安装GMP开发库（自动检测包管理器）
make deps

# 下载CGBN库到lib/目录
make cgbn
**注意**：执行前需确保`nvcc`可用，且CUDA环境变量已正确配置

清理构建

# 清理特定目标（如fft_v1）
make clean_fft_v1

# 清理所有构建产物
make clean all

选择性构建

项目默认构建所有算法实现。如需单独构建特定目标：

make fft_basic          # 构建基线FFT实现
make fft_v1             # 构建优化FFT版本
make gmp_prime_swing    # 构建GMP素数摇摆算法
make cgbn_improved      # 构建优化CGBN版本

构建目标说明：

目标名称	算法类型	执行环境	技术特点
fft_basic	FFT乘法	CPU	从零实现的基线FFT算法，用于复杂度验证
fft_v1	FFT乘法	CPU	优化的FFT实现（缓存优化、迭代结构、并行化）
gmp_split_recursive	分治法	CPU	GMP库实现的递归分割算法
gmp_split_recursive_thread	分治法	CPU	OpenMP多线程版本
gmp_prime_swing	素数摇摆法	CPU	GMP优化的素数筛法与 swing 乘积
gmp_mpz_fac_ui	标准库	CPU	GMP原生mpz_fac_ui函数基准
cgbn_simple	CGBN并行	GPU	最小化验证版本，API功能测试
cgbn_full	CGBN并行	GPU	完整功能CUDA实现，包含文件保存性能测试
cgbn_improved	CGBN并行	GPU	自适应素数参数优化，动态网格配置
validate	验证工具	CPU	结果一致性校验与数据验证

---

使用说明

基础用法

所有编译生成的可执行文件位于build/目录下，统一接口：

./build/<algorithm_name> <N>

其中<N>为待计算阶乘的非负整数，支持的最大值取决于算法实现与系统内存。

示例：

# 计算10000的阶乘
./build/gmp_mpz_fac_ui 10000

# 计算100004000的阶乘（默认测试规模）
./build/cgbn_improved 100004000

自动化测试

项目提供完整的测试脚本utilities/test.sh，支持批量测试与性能评估。

测试配置

编辑utilities/test.sh调整测试参数：

# 默认测试规模（可修改）
DEFAULT_ARGS="100004000"

# 跳过的程序黑名单（用空格分隔）
BLACKLIST=("cgbn_simple" "validate")

执行测试

# 赋予执行权限（首次使用）
chmod +x ./utilities/test.sh

# 运行完整测试套件
./utilities/test.sh

测试流程：

1. 遍历build/目录下所有可执行文件（排除黑名单）
2. 使用DEFAULT_ARGS作为输入参数执行
3. 记录执行时间、内存占用、标准输出
4. 生成测试报告test/report.txt
5. 自动调用validate工具进行结果一致性验证

---

验证机制

正确性保证：

• 所有算法实现均通过validate程序在相对应数量级上进行交叉验证
• 验证逻辑基于要求：总位数 + 末尾0个数 + 数位之和

性能指标收集：

• 执行时间（毫秒级精度，基于std::chrono::steady_clock）在output记录的标准输出文件中
• 峰值内存占用和运行时间（通过/usr/bin/time -v）在statistic记录的_perf文件中

---

目录结构

.
├── build/                    # 编译输出目录（自动生成）
├── lib/                      # 第三方库（CGBN、GMP）
├── reports/                  # 项目总结和报告
├── src/
│   ├── FFT/                  # FFT乘法实现
│   ├── GMP/                  # GMP-based algorithms
│   └── CGBN/                 # CUDA accelerated implementations
├── utilities/
│   └── test.sh              # 自动化测试脚本
│   └── validate.cpp          # 验证工具
├── Makefile                 # Build configuration
├── README.md                # This file
└── LICENSE                  # Project license

---

故障排除

常见问题

问题1：./utilities/test.sh权限被拒绝

• 解决：执行chmod +x ./utilities/test.sh

问题2：make cgbn_失败，提示nvcc: command not found

• 原因：CUDA Toolkit未安装或环境变量未配置
• 解决：确保nvcc在PATH中，或设置CUDA_HOME环境变量

问题3：make deps在WSL2中失败

• 解决：手动安装libgmp-dev：sudo apt-get install libgmp-dev

问题3：CGBN编译通过但运行时出现0

• 原因：计算规模超出CGBN规定
• 解决：降低输入规模，或修改CGBN参数

许可证

本项目遵循MIT License。第三方库（CGBN、GMP）受其各自许可证约束。

---

贡献指南

• 提交前请执行make clean_all && make all确保可构建性
• 新增算法需在makefile中添加对应编译用例
• 所有性能优化必须伴随正确性验证

---

文档维护：C++课程小组
最后更新：2025年12月16日