262 lines
7.4 KiB
Markdown
262 lines
7.4 KiB
Markdown
# Prime Number MPI Program - Bottleneck and Scalability Analysis
|
||
|
||
## 程序瓶颈分析
|
||
|
||
### 1. **算法瓶颈：低效的素数检测算法**
|
||
|
||
**问题：** 程序使用最简单的试除法检测素数，时间复杂度为 O(n²)
|
||
|
||
```cpp
|
||
for ( j = 2; j < i; j++ ) // 对每个数字i，需要检查i-2次
|
||
{
|
||
if ( i % j == 0 )
|
||
{
|
||
prime = 0;
|
||
break;
|
||
}
|
||
}
|
||
```
|
||
|
||
**影响：**
|
||
- 检测数字 2：需要 0 次除法
|
||
- 检测数字 100,000：需要 99,998 次除法
|
||
- 检测数字 1,000,000：需要 999,998 次除法
|
||
|
||
**改进建议：**
|
||
- 只检查到 √i 而不是 i-1，可将复杂度降至 O(n√n)
|
||
- 使用埃拉托斯特尼筛法（Sieve of Eratosthenes）
|
||
- 使用更高效的算法如米勒-拉宾素性测试
|
||
|
||
---
|
||
|
||
### 2. **负载均衡瓶颈：进程间计算成本不均**
|
||
|
||
**问题表现：**
|
||
|
||
从性能测试结果可以看到：
|
||
|
||
| N值 | 进程数 | 时间(秒) | 加速比 | 效率 |
|
||
|-------|--------|----------|--------|--------|
|
||
| 100K | 1 | 1.23 | 1.00x | 100% |
|
||
| 100K | 2 | 1.32 | 0.96x | 48% |
|
||
| 100K | 4 | 0.67 | 1.88x | 47% |
|
||
| 100K | 6 | 0.68 | 1.85x | 30% |
|
||
| 100K | 8 | 0.37 | 3.38x | 42% |
|
||
|
||
**关键问题：**
|
||
- 2个进程时，加速比 < 1（比单进程还慢！）
|
||
- 4个进程时，加速比仅 1.88x（理想应该是 4x）
|
||
- 6个进程时，效率仅 30%（理想应该是 100%）
|
||
- 8个进程时，效率仅 42%
|
||
|
||
**根本原因：**
|
||
|
||
虽然程序使用循环分配策略让各进程检查相近数量的数字：
|
||
|
||
```
|
||
P=4时：
|
||
- 进程0: 2, 6, 10, 14, ..., 99998 (25000个数字)
|
||
- 进程1: 3, 7, 11, 15, ..., 99999 (25000个数字)
|
||
- 进程2: 4, 8, 12, 16, ..., 100000 (25000个数字)
|
||
- 进程3: 5, 9, 13, 17, ..., 99997 (24999个数字)
|
||
```
|
||
|
||
**但是！** 数字大小不同，检测成本差异巨大：
|
||
|
||
- 进程0检测的数字：2, 6, 10, 14, ... (小数字，检测快)
|
||
- 进程3检测的数字：5, 9, 13, 17, ... (大数字，检测慢)
|
||
|
||
**计算成本分析：**
|
||
|
||
虽然各进程检查的数字数量相近，但：
|
||
- 检测小数字（如2, 3, 4）只需要很少的除法运算
|
||
- 检测大数字（如99997, 99998, 99999）需要大量除法运算
|
||
|
||
这导致：
|
||
- **进程0**：检测的数字最小，总计算成本最低
|
||
- **进程P-1**：检测的数字最大，总计算成本最高
|
||
|
||
**实际负载分布（N=100000, P=4）：**
|
||
|
||
```
|
||
进程0: 检测 [2, 6, 10, ..., 99998] → 平均数字大小 ≈ 50000
|
||
进程1: 检测 [3, 7, 11, ..., 99999] → 平均数字大小 ≈ 50001
|
||
进程2: 检测 [4, 8, 12, ..., 100000] → 平均数字大小 ≈ 50002
|
||
进程3: 检测 [5, 9, 13, ..., 99997] → 平均数字大小 ≈ 50001
|
||
```
|
||
|
||
虽然平均数字大小相近，但大数字的检测成本远高于小数字！
|
||
|
||
---
|
||
|
||
### 3. **通信瓶颈：MPI_Reduce的开销**
|
||
|
||
**问题：** 每个进程计算完成后需要调用 `MPI_Reduce` 汇总结果
|
||
|
||
```cpp
|
||
MPI_Reduce(&total_part, &total, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);
|
||
```
|
||
|
||
**影响：**
|
||
- 当进程数增加时，通信延迟增加
|
||
- 对于小规模问题（如N=100000），通信开销占比显著
|
||
|
||
---
|
||
|
||
### 4. **同步瓶颈：进程间相互等待**
|
||
|
||
**问题：** 由于负载不均衡，快的进程需要等待慢的进程完成
|
||
|
||
**表现：**
|
||
- 进程0（检测小数字）很快完成
|
||
- 进程P-1（检测大数字）很慢才完成
|
||
- 所有进程必须等待最慢的进程完成才能调用 MPI_Reduce
|
||
|
||
---
|
||
|
||
## 加速比问题分析
|
||
|
||
### 问题1：2个进程时加速比 < 1
|
||
|
||
**现象：** 使用2个进程比单进程还慢
|
||
|
||
**原因：**
|
||
1. **通信开销 > 并行收益**：当N=100000时，问题规模较小，MPI通信和同步的开销超过了并行计算的收益
|
||
2. **负载不均衡**：2个进程时，进程0检测偶数位置数字，进程1检测奇数位置数字，但奇数位置的平均数字更大，检测成本更高
|
||
3. **缓存效应**：单进程可能有更好的缓存局部性
|
||
|
||
### 问题2：效率随进程数增加而下降
|
||
|
||
**现象：**
|
||
- 4进程：效率 47%
|
||
- 6进程：效率 30%
|
||
- 8进程：效率 42%
|
||
|
||
**原因：**
|
||
1. **Amdahl定律**：程序中存在串行部分（MPI初始化、Reduce汇总、结果打印），限制了最大加速比
|
||
2. **通信开销增加**：进程数越多，通信和同步开销越大
|
||
3. **负载不均衡加剧**：进程数越多，进程间的计算成本差异越明显
|
||
|
||
### 问题3：6进程效率异常低（30%）
|
||
|
||
**可能原因：**
|
||
1. **NUMA效应**：6个进程可能跨越不同的CPU socket，导致跨socket通信开销增加
|
||
2. **线程调度**：操作系统调度6个进程到不同核心可能产生额外的上下文切换开销
|
||
3. **内存带宽竞争**：6个进程同时访问内存可能导致带宽饱和
|
||
|
||
---
|
||
|
||
## 改进建议
|
||
|
||
### 1. **改进素数检测算法**
|
||
|
||
```cpp
|
||
// 改进：只检查到√i
|
||
int is_prime(int n) {
|
||
if (n < 2) return 0;
|
||
if (n == 2) return 1;
|
||
if (n % 2 == 0) return 0;
|
||
|
||
for (int j = 3; j * j <= n; j += 2) {
|
||
if (n % j == 0) return 0;
|
||
}
|
||
return 1;
|
||
}
|
||
```
|
||
|
||
**预期效果：** 将算法复杂度从 O(n²) 降至 O(n√n)，可提速约 √n 倍
|
||
|
||
### 2. **改进负载均衡策略**
|
||
|
||
**方案A：块分配（Block Distribution）**
|
||
|
||
```cpp
|
||
// 将数字范围分成P个连续的块
|
||
int block_size = (n - 1) / p;
|
||
int start = 2 + id * block_size;
|
||
int end = (id == p - 1) ? n : 2 + (id + 1) * block_size - 1;
|
||
|
||
for (int i = start; i <= end; i++) {
|
||
// 检测i是否为素数
|
||
}
|
||
```
|
||
|
||
**优点：** 每个进程处理连续的数字范围，减少缓存失效
|
||
**缺点：** 仍然存在负载不均衡（后面的进程处理更大的数字）
|
||
|
||
**方案B：动态负载均衡**
|
||
|
||
```cpp
|
||
// 使用任务队列，进程完成一个任务后领取下一个
|
||
int current = 2;
|
||
#pragma omp critical
|
||
{
|
||
current = next_number++;
|
||
}
|
||
if (current <= n) {
|
||
// 检测current是否为素数
|
||
}
|
||
```
|
||
|
||
**优点：** 自动实现负载均衡
|
||
**缺点：** 需要同步机制，可能增加开销
|
||
|
||
**方案C：反向分配**
|
||
|
||
```cpp
|
||
// 让进程0处理大数字，进程P-1处理小数字
|
||
for (int i = n - id; i >= 2; i -= p) {
|
||
// 检测i是否为素数
|
||
}
|
||
```
|
||
|
||
**优点：** 简单，部分缓解负载不均衡
|
||
**缺点：** 不能完全解决问题
|
||
|
||
### 3. **减少通信开销**
|
||
|
||
```cpp
|
||
// 使用非阻塞通信
|
||
MPI_Ireduce(&total_part, &total, 1, MPI_INT, MPI_SUM, 0,
|
||
MPI_COMM_WORLD, &request);
|
||
// 在等待通信完成的同时做其他工作
|
||
MPI_Wait(&request, MPI_STATUS_IGNORE);
|
||
```
|
||
|
||
### 4. **优化数据局部性**
|
||
|
||
```cpp
|
||
// 预分配缓存，避免频繁分配
|
||
int* primes = (int*)malloc((n - 1) * sizeof(int));
|
||
int prime_count = 0;
|
||
|
||
// 批量处理，提高缓存命中率
|
||
for (int i = start; i <= end; i++) {
|
||
if (is_prime(i)) {
|
||
primes[prime_count++] = i;
|
||
}
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
## 总结
|
||
|
||
### 主要瓶颈：
|
||
1. **算法瓶颈**：O(n²)的素数检测算法效率低下
|
||
2. **负载均衡瓶颈**：进程间计算成本严重不均
|
||
3. **通信瓶颈**：MPI_Reduce的同步开销
|
||
4. **同步瓶颈**：快进程等待慢进程
|
||
|
||
### 加速比问题：
|
||
1. **小规模问题**：通信开销 > 并行收益
|
||
2. **负载不均衡**：导致效率随进程数增加而下降
|
||
3. **Amdahl定律**：串行部分限制了最大加速比
|
||
|
||
### 优先改进项：
|
||
1. **改进算法**：将试除法优化到√n（最优先）
|
||
2. **改进负载分配**：使用块分配或动态分配
|
||
3. **减少通信**：使用非阻塞通信或减少通信频率
|
||
|
||
通过这些改进，预期可以将加速比从当前的 3.38x（8进程）提升到接近理想的 6-7x。
|