多核软件设计实验报告.doc

多核软件设计实验手册多核软件设计实验手册（2015年4月版）郑重声明：1、实验手册中的所有实验均有本人独立编码、调试和测试。2、实验手册中给出的实验数据和结果完全由本人所完成的程序给出。3、本人了解：不按照前两条要求所完成的实验报告已经构成了抄袭或造假行为，本人将承担相应的不良后果。姓名： （签名） 学号： 提交日期： 总成绩： 本课程以设计竞赛方式评分，执行速度排名与分数的比例如下表。执行速度排名分数前15%100%前4015%80%前8540%70%最后15%60%题号总分程序执行时间(s)排名分数比例得分测试员签名120230330报告20总分1. Eratosthenes筛法（20分）Eratosthenes筛法（Eratosthenes，约公元前274194年）是一种求素数的古老方法，虽然没有实际的使用价值，但是其筛法的思想和方法却是后续数域筛法的基础。算法1.1 Eratosthenes筛法输入,: 最小的n个素数输出：到之间的所有素数内部变量：char A:;1. 初始化A的所有元素设置为02. i从1到n循环2.1 2.2 循环2.2.1 如果,则转至2，否则Aj=1, j+=2.3 输出所有满足Aj=0的j下述100以内的所有素数可以作为起始的素数集合。2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97本题使用的软硬件平台CPUCache操作系统编译器型号核数主频L1L2L3版本优化参数Intel(R) Xeon(R) CPU E5-2620121.2G64K256K15MRed Hat Enterprise Linux Server release 6.4icpc 14.0.2O21.设计一个串行程序226以内的所有素数，其中在225,226以内的素数有 1894120 个，这个串行程序的执行时间是 0.818 秒。2. 【区间大小的优化】原始算法中筛的区间大小为:，实际上当比较大时可能会超过内存上界，因此筛的区间往往取一个固定值B。由于筛的过程中要频繁访问这个区间，因此B的大小往往与Cache容量有关，请测试B不同大小时的性能差异。表1-1 不同筛区间大小对性能的影响B程序执行时间（秒）4K0.00016K0.00064K0.000256K0.0011M0.0042M0.013你的测试结果说明B为 4K 时程序性能最优。你所使用的CPU的一级Cache和二级Cache容量分别是 64K和256K 。3. 【对固定区间的算法优化】在新算法中筛的区间大小是:，实际上对于素数p，如果，则p在此区间中必然没有整倍数，因此可以减少算法1.1中的素数数量。使用此方法优化后，请重新测试不同区间大小下的算法性能。表1-2 修改参与筛的素数集合后不同筛区间大小对性能的影响B程序执行时间（秒）4K0.00016K0.00064K0.000256K0.0011M0.0042M0.013你的测试结果说明B为 4K 时程序性能最优。如果与测试2有差异，请说明原因。答：没有什么区别。4. 【并行化】如果有T个线程可以同时执行，请考虑以下两种并行化策略：策略1：每个线程分别共享一个区间，分别处理,中的一个子集，然后再将各个线程得到的筛结果合并；策略2：将筛区间分成T个不同的部分，每个线程处理一个部分；你认为策略 2 可能会更好，理由是 适合我的代码结构 。按照你选择的策略设计并实现一个并行化的筛法程序，调整参与计算线程的数量T，比较执行时间：表1-3 不同线程数的程序执行时间线程数T程序执行时间（秒）115.47829.23346.18467.29688.564你的测试结果说明T为 4 时性能最好，此时的筛区间大小是 2, 230 。你使用的处理器核数是 12 。5. 【总结】请根据上述程序生成232以内的素数，其中231,232以内的素数有 98182656 个，记录各个版本的程序运行时间，填写下表。表1-4程序执行时间对比版本产生226以内素数需要的时间（秒）产生232以内素数需要的时间（秒）加速比加速比最优配置原始程序0.81867.22111固定区间大小0.40235.3322.031.90针对固定区间的优化0.18915.2134.324.41并行化0.0665.87512.3911.442. 矩阵乘法（30分）在Linux/Windows平台上实现单精度浮点的矩阵乘法：本题使用的软硬件平台CPUCache操作系统编译器型号核数主频L1L2L3版本优化参数Intel(R) Xeon(R) CPU E5-2620121.2G64K256K15MRed Hat Enterprise Linux Server release 6.4icpc 14.0.2O21. 【基准程序】输入矩阵A，B，由随机函数产生， 使用串行程序产生正确结果C0该程序的执行时间为 N=4096时， 串行程序时间为588911毫秒 。2. 【多线程并行化】使用并行方法计算矩阵乘法结果C。程序的输入命令行：Matrix_mul N Thread_num参数：N: 矩阵大小Thread_num：线程个数输出格式：Check Result: ffffT=tttt(ms)说明：ffff: 和串行结果的误差tttt: 程序执行所需要的时间，以毫秒为单位计算结果和计算时间表2-1 并行矩阵乘法Thread_numN误差计算时间15120405 ms1102402993 ms12048046122 ms140960588911 ms240960205936 ms440960132576 ms840960111219 ms124096078697 ms244096095204 ms请根据上述实验结果，画出两个图。其中图1的X轴为N，Y轴为Thread_num为1时的计算时间，图2的X轴为Thread_num，Y轴为N为4096时的计算时间。图1 matrix维数与计算时间表图2 线程数与计算时间表如果你的CPU为多核处理器，你是否观察到计算加速了？如果观察到计算加速的话，你的处理器核数是 12核 ，图2中Thread_num为 12 时，计算性能最好，其加速比是 7.48 。（加速比=多线程执行时间/单线程执行时间）3.【矩阵分块计算】每个浮点数占4字节空间，L1 Cache容量是 64 KB，可以放置一个mm的矩阵小块，其中m= 128 。将整个矩阵分解为这样的小块，每次完成一对小块的计算，以提高Cache的命中率。提示：图中n=N/m计算次序为A11*B11, A11*B12, A11*B1n,，由于反复使用A11，因此可以提高Cache的命中率。设置N为4096，Thread_num为1、2、4和8，重复上述实验，填写下表。表2-2 分块的并行矩阵乘法Thread_numN误差计算时间140961807.30112586 ms240961256.3360856 ms440961566.6339179 ms840961876.5819526 ms1240961536.2516800 ms1640961656.7518630 ms2440961876.2323967 ms在最优的线程数下Thread_num=12，调整m的大小，重复上述实验，填写下表。表2-3 分块大小对性能的影响mN误差计算时间m/48,0006875.38159103 msm/28,0006432.23113075 msm8,0006314.6593513 ms2m8,0006988.5672658 ms4m8,0006322.25207195 ms与理论最优值相比，分块大小最好的性能是 2m=256 。与表2-1的结果相比，加速比可以达到 (588911/16800)=35.05 。4.【使用SSE指令加速】使用SSE指令可以一次完成4个浮点乘法操作和加法操作，但是需要将存储器中的内容进行混洗。下图给出了44的矩阵乘法操作示意图。结合上述矩阵分块策略，在最优的线程数下，最优的分块数下，使用SSE指令加速矩阵乘法操作，执行时间为 12680 ms（N=4096） ，误差为 1626.39 。与最初的串行计算相比，加速比达到 (588911/16800)=46.44 。讨论：是否可以先将B矩阵先整体转置，然后再使用SIMD指令完成计算？如果可以的话，请编程实现，并与前面的方法进行比较。答：根据转置矩阵的定义，可以先将B矩阵转置，然后再使用SIMD指令完成计算。核心代码如下：inline float rowMultiplyLineSSE(float row,float line,int N,int thread_num=1) _m128 t1,t2,sum;sum=_mm_setzero_ps();/zero clearingfloat result=0.0;float result_sum4=0;for(int i=0;iN;i+=4) t1=_mm_loadu_ps(row+i);t2=_mm_loadu_ps(line+i);t1=_mm_mul_ps(t1,t2);sum=_mm_add_ps(sum,t1);_mm_store_ps(result_sum,sum);result=result_sum0+result_sum1+result_sum2+result_sum3;return result;函数参数float line指的是BT的行，即矩阵B的列。5.【使用GPU/MIC】进行矩阵乘法本题使用的GPU/MIC平台GPU/MICCache操作系统编译器型号核数主频L1L2L3版本优化参数Intel Xeon Phi Coprocessor 5110P601.05G64K512K*60无Red Hat Enterprise Linux Server release 6.4icpc 14.0.2O26.【对比】画出以上串行、并行、分块+并行、分块+并行+SSE和GPU/MIC等五种实现策略在N=8000的情况下的程序执行时间对比图。在上述矩阵乘法中总共需要 8000*8000*8000*2 = 1024G 次浮点乘法和加法操作。比较上述5种算法的计算性能（单位GFlops/s）优化方法时间（s）性能（GFlops/s）串行15360.67并行321.33.18分块并行72.6514.09分块并行SSE36.5328.03MIC10.3698.847.“分而治之”的矩阵乘法Strassen给出了一个减少矩阵乘法计算量的方法。按照以下方式计算：P1=(A11+A22)(B11+B22)P2=(A21+A22)B11P3=A11 (B12-B22)P4=A22(B21-B11)P5=(A11+A12) B22P6=(A21-A11)(B11+B12)P7=(A12-A22)(B21+B22)C11=P1+P4-P5+P7C12=P3+P5C21=P2+P4C22=P1+P3-P2+P6可否使用这个方法进一步提高矩阵乘法的性能？如果可以，请说明你的方案以及实现效果。答：矩阵相乘的时间消耗主要花在浮点数的相乘。Strassen矩阵乘法就是采用了分为治之的运算思想，对于二阶矩阵乘法（可扩展到阶，但Strassen矩阵乘法要求是的幂）将上面的8次矩阵相乘变成了7次乘法，最终达到降低复杂度为O( nlg7 ) = O( n2.81 )。Strassen矩阵乘法具体实现时采用矩阵分块递归实现， 可提高矩阵乘法的性能。下图可看出随着n的变大，Strassen算法比通用矩阵相乘算法变得更有效率。3. 整数排序（30分）仔细阅读论文：1 Jatin Chhugani, William Macy, Efficient Implementation of Sorting on MultiCore SIMD CPU Architecture PVLDB 08, August 23-28, 2008, Auckland, New Zealand2 Nadathur Satish,etc., Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort, SIGMOD10, 2010本题使用的软硬件平台CPUCache操作系统编译器型号核数主频L1L2L3版本优化参数Intel(R) Xeon(R) CPU E5-2620121.2G64K256K15MRed Hat Enterprise Linux Server release 6.4icpc 14.0.2O21. 产生长度为400MB的32位随机整数数组，使用C语言中quicksort()函数进行排序，获得排序时间为 22352 毫秒；2. 未优化的串行基数排序花费时间 12635ms （NUM=100M） 。按照论文所述的针对Cache优化的基数排序方法，实现并行排序。针对你所用处理器的参数讨论缓冲大小B和基数大小D。答：使用的平台硬件L1 Cache容量是64KB，可以容纳16K个32bit的整数。因此，缓冲区的大小应该设置为B=64KB，以提高cache的命中率，提高排序的速度。因为十进制整数，所以基数大小D=10。针对上述排序方法，线程数为8的情况下，测量得到的排序时间为 4231 毫秒。3. 未优化的串行二路归并花费时间 15869ms （NUM=100M） 。按照论文所述的针对SIMD指令和Cache容量的多路Merge排序方法，实现并行排序。线程数为8的情况下，测量得到的排序时间为 5741 毫秒。4. 使用GPU或者MIC进行并行排序实验。本题使用的GPU/MIC平台GPU/MICCache操作系统编译器型号核数主频L1L2L3版本优化参数Intel Xeon Phi Coprocesso