并行与分布式计算导论——作业(二)

博主： Rainshaw
发布时间：2019 年 04 月 09 日
1315 次浏览
暂无评论
2419字数
分类：并行与分布式计算导论 C++

## 作业要求

完成以下OpenMP程序,提交作业报告,并在报告的最后附源码,格式为PDF.
The Number of Inversion Pairs
Bucket Sort
报告的内容可以包括：
1.并行的核心代码或核心思想；
2.与参考串行/并行程序相比较,或使用不同的线程数量比较输出结果并简单分析；
3.使用OpenMP的心得或遇到的困难.

## The Number of Inversion Pairs

### 结果比较(本机8代标压酷睿i7-6核心)

| 问题规模 | 线程数 | 时间(ms) | 线程数 | 时间(ms) | 线程数 | 时间(ms) | 线程数 | 时间(ms) |
| :- | :- | :- | :- | :- | :- | :- | :- | :- |
| $10^4$ | 1 | 7 | 2 | 7 | 4 | 6 | 6 | 6 |
| $10^6$ | 1 | 207 | 2 | 122 | 4 | 80 | 6 | 69 |
| $10^7$ | 1 | 2.115(s) | 2 | 1.205(s) | 4 | 777 | 6 | 635 |
| $10^8$ | 1 | 23.900(s) | 2 | 13.568(s) | 4 | 8.183(s) | 6 | 6.593(s) |

### 结果比较(临湖草堂)

由于未知原因...在临湖草堂测试时,逆序对数量输出不对,故本程序不做参考

### 并附上问题规模为$10^7$时,本机上的对比数据

最后一项为使用临湖草堂示例代码给出的结果,以证明并行代码的结论是正确的.

```bash
# rainshaw @ gaoruixiaodeMacBook-Pro-15 in ~/Desktop/Code/CLionProjects/Parallel&DistributedProgramming/homework2/InversionPairs/cmake-build-debug [11:44:02] 
$ time ./InversionPairs 10000000 6
25009750388965
./InversionPairs 10000000 6  2.14s user 0.04s system 342% cpu 0.635 total

# rainshaw @ gaoruixiaodeMacBook-Pro-15 in ~/Desktop/Code/CLionProjects/Parallel&DistributedProgramming/homework2/InversionPairs/cmake-build-debug [11:44:17] 
$ time ./InversionPairs 10000000 4 
25009750388965
./InversionPairs 10000000 4  2.10s user 0.03s system 274% cpu 0.777 total

# rainshaw @ gaoruixiaodeMacBook-Pro-15 in ~/Desktop/Code/CLionProjects/Parallel&DistributedProgramming/homework2/InversionPairs/cmake-build-debug [11:44:32] 
$ time ./InversionPairs 10000000 2
25009750388965
./InversionPairs 10000000 2  2.08s user 0.03s system 174% cpu 1.205 total

# rainshaw @ gaoruixiaodeMacBook-Pro-15 in ~/Desktop/Code/CLionProjects/Parallel&DistributedProgramming/homework2/InversionPairs/cmake-build-debug [11:44:45] 
$ time ./InversionPairs 10000000 1
25009750388965
./InversionPairs 10000000 1  2.08s user 0.03s system 99% cpu 2.115 total

# rainshaw @ gaoruixiaodeMacBook-Pro-15 in ~/Desktop/Code/CLionProjects/Parallel&DistributedProgramming/homework2/InversionPairs/cmake-build-debug [11:44:58] 
$ time ./InversionPairs 10000000 1
25009750388965
./InversionPairs 10000000 1  2.16s user 0.02s system 99% cpu 2.194 total
```

从表中可以看出,当问题规模达到$10^6$时,此时采用并行算法可以显著的降低程序运行时间.

### 并行代码与核心思想

并行核心代码如下
<div class="hideContent">此处内容需要评论回复后（审核通过）方可阅读。</div>
归并排序是一个自顶向下的分治算法,但自顶向下不好并行,所以采用自底向上的思想,先归并小区间,然后逐步增大归并区间长度.则同一层中的归并过程就可以并行了!

### 程序源码
<div class="hideContent">此处内容需要评论回复后（审核通过）方可阅读。</div>

## Bucket Sort

### 结果比较(本机8代标压酷睿i7-6核心)

| 问题规模 | 每线程桶数 | 线程数 | 时间(ms) | 线程数 | 时间(ms) | 线程数 | 时间(ms) | 线程数 | 时间(ms) |
| :- | :- | :- | :- | :- | :- | :- | :- | :- | :- |
| $10^4$ | 10 | 1 | 8 | 2 | 8 | 4 | 8 | 6 | 5 |
| $10^6$ | 10 | 1 | 148 | 2 | 91 | 4 | 70 | 6 | 56 |
| $10^7$ | 10 | 1 | 1.533(s) | 2 | 915 | 4 | 643 | 6 | 533 |
| $10^8$ | 100 | 1 | 13.084(s) | 2 | 7.935(s) | 4 | 5.320(s) | 6 | 4.463(s) |

### 结果比较(临湖草堂)

| 问题规模 | 每线程桶数 | 线程数 | 时间(ms) | 线程数 | 时间(ms) | 线程数 | 时间(ms) | 线程数 | 时间(ms) |
| :- | :- | :- | :- | :- | :- | :- | :- | :- | :- |
| $10^6$ | 10 | 1 | 1.8716e-01 | 2 | 1.2269e-01 | 3 | 8.3193e-02 | 4 | 8.4673e-02 |
| $10^7$ | 1000 | 1 | 1.0209e+00 | 2 | 7.0260e-01 | 3 | =5.7771e-01 | 4 | 5.1213e-01 |

### 并附上4线程$dim=10^7,n_bucket=1000$时,临湖草堂上的对比数据

```
reference serial impl.  : time_cost=1.1017e+00                   res:The data is sorted.

reference parallel impl.: time_cost=4.4308e-01 speedup=2.487e+00 res:The data is sorted.

your impl.              : time_cost=5.1213e-01 speedup=2.151e+00 res:The data is sorted.
```

从两张表中可以看出,当问题规模较小时（小于$10^6$）,采用并行算法并没有明显的增益,而当数据规模较大时,例如$10^8$,此时采用并行算法可以显著的降低程序运行时间.

### 并行核心代码
<div class="hideContent">此处内容需要评论回复后（审核通过）方可阅读。</div>
程序的其他部分也存在很多循环,但由于其中的部分数值无法原子更新导致循环无法并行化.

### 程序源码
<div class="hideContent">此处内容需要评论回复后（审核通过）方可阅读。</div>

最后修改：2020 年 10 月 24 日