Loading... ## 作业要求 完成以下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 日 02 : 04 PM © 禁止转载 赞赏 如果觉得我的文章对你有用，请随意赞赏 ×Close 赞赏作者 扫一扫支付 支付宝支付 微信支付
