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

2019 年 04 月 09 日

2011 次浏览

2419字数

作业要求

完成以下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$时,本机上的对比数据

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

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