作业要求

完成以下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$17274666
$10^6$12072122480669
$10^7$12.115(s)21.205(s)47776635
$10^8$123.900(s)213.568(s)48.183(s)66.593(s)

结果比较(临湖草堂)

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

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

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

# 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$时,此时采用并行算法可以显著的降低程序运行时间.

并行代码与核心思想

并行核心代码如下

此处内容需要评论回复后(审核通过)方可阅读。

归并排序是一个自顶向下的分治算法,但自顶向下不好并行,所以采用自底向上的思想,先归并小区间,然后逐步增大归并区间长度.则同一层中的归并过程就可以并行了!

程序源码

此处内容需要评论回复后(审核通过)方可阅读。

Bucket Sort

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

问题规模每线程桶数线程数时间(ms)线程数时间(ms)线程数时间(ms)线程数时间(ms)
$10^4$1018284865
$10^6$101148291470656
$10^7$1011.533(s)291546436533
$10^8$100113.084(s)27.935(s)45.320(s)64.463(s)

结果比较(临湖草堂)

问题规模每线程桶数线程数时间(ms)线程数时间(ms)线程数时间(ms)线程数时间(ms)
$10^6$1011.8716e-0121.2269e-0138.3193e-0248.4673e-02
$10^7$100011.0209e+0027.0260e-013=5.7771e-0145.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$,此时采用并行算法可以显著的降低程序运行时间.

并行核心代码

此处内容需要评论回复后(审核通过)方可阅读。

程序的其他部分也存在很多循环,但由于其中的部分数值无法原子更新导致循环无法并行化.

程序源码

此处内容需要评论回复后(审核通过)方可阅读。

最后修改:2020 年 10 月 24 日 02 : 04 PM
如果觉得我的文章对你有用,请随意赞赏