参考英特尔多核平台编程优化大赛报告

英特尔多核平台编程优化大赛报告 英特尔多核平台编程优化大赛报告 代码优化前所需时间：4.765秒 代码优化后所需时间：0.25秒（保留小数点后7位精度） 前言 本次优化使用的CPU是Intel Xeon 5130 主频为2.0GHz 同Intel酷睿2一样是基于Core Microarchitecture 的双核处理器。本次优化在Intel的工具帮助下主要针对Core Microarchitecture 系列处理器进行优化。但是由于未知原因，Intel VTune Analyzers并不能在该系统下正常工作。所以，所有使用Intel VTune Analyzers的测试均使用另外一个奔腾D 820的系统测试。 第一章主要介绍了程序的串行优化。其中有关于Intel编译器使用，以及Intel Math Kernel Library使用，Intel VTune Analyzers使用的介绍。在借助Intel工具的帮助下，结合Intel Core Microarchitectured的特性。设计出了针对L1 Cache进行优化的，高效率的串行代码。程序的执行时间从优化前的4.765秒达到了优化后的0.765秒。 第二章主要介绍了程序的并行化。首先讨论了2种并行算法的优缺点。然后选择了适合本程序的并行算法进行优化。并且在最后分析了并行化时的性能瓶颈。通过并行化，程序达到了0.437秒。 第三章主要介绍了程序的汇编优化。首先介绍了计算的数学理论。然后介绍了汇编代码的编写。最后进行了性能分析。通过该步优化程序在保留小数点后7位精度的前提下达到了0.312秒的好成绩。并且在Intel酷睿2 E6600 上测试达到了0.25秒。 附录A 说明了本次报告的目录结构和优化方法。 附录B 列出了进行本次竞赛所参考的文献。 目录 一、串行优化. 4 1.1 代码的基本修改和优化. 4 1.2 基于Intel编译器的优化. 4 1.3 使用Intel VTune Analyzers进行性能分析. 8 1.3.1 Intel VTune Analyzers概述. 8 1.3.2 基于SAMPLING方式的分析. 9 1.3.3 对于本次程序的分析. 9 1.4 优化computePot函数. 10 1.5 使用Intel Math Kernel Library. 11 1.6 根据Cache大小优化Intel Math Kernel Library调用. 12 1.7 优化updatePositions函数. 13 1.8 其他优化以及性能分析. 14 二、并行优化. 17 2.1 并行优化概述. 17 2.2 优化方案一. 17 2.3 优化方案二. 17 2.4 并行实现. 18 2.5 性能分析. 20 三、汇编级优化. 23 3.1 优化目标. 23 3.2 数学理论. 23 3.3 汇编码实现. 25 3.4 性能分析. 28 3.5 总结. 29 附录A 目录结构和编译方法. 30 附录B 参考文献. 30 一、串行优化 1.1 代码的基本修改和优化 首先根据主办方的要求把代码的输出精度改为小数点后7位。 if (i%10 = 0) printf(%5d: Potential: %20.7fn, i, pot); 在进行任何优化前代码的执行时间是4.765秒。 接着把项目转换成使用Intel C+ Compiler，代码的执行时间是4.531秒。 然后执行最基本的优化，把代码中的pow函数优化成乘法。代码如下： distx = (r0j - r0i)*(r0j - r0i); disty = (r1j - r1i)*(r1j - r1i); distz = (r2j - r2i)*(r2j - r2i); 执行时间依然为4.531秒。说明Intel编译器已经将pow函数优化掉了。 1.2 基于Intel编译器的优化 这里介绍本程序中基于Intel编译器优化技术。其中有些优化参数是可以确定的，有些优化参数需要在程序的不同阶段反复调试以确定最优方案，而有些优化技术是在后面的优化中使用的。 编译器优化级别 Intel的编译器共有如下一些主要的优化级别： u /O1：实现最基本的优化 u /O2：基于代码速度实现常规优化，这个也是默认的优化级别 u /O3：在/O2的基础上实现进一步的优化，包括Cache预读，标量转换等等，但是在某些情况下反而会减慢代码的执行速度。 u /Ox：实现最大化的优化，包括自动内联函数的确定，全局优化，使用EBP作为通用寄存器等。 u /fast：等同于/O3, /Qipo, /Qprec-div-, and /QxP。 通过测试，目前选用/O3，但是随着代码的更改，需要重新测试，选择合适的优化级别。 针对特定处理器进行优化 Intel的编译器一共支持如下3种针对特定处理器的优化： u /G：使用这个优化选项，Intel将针对特定的CPU进行优化，但是其代码依然可以在所有的CPU上执行。 u /Qx：使用这个优化选项，Intel将针对特定的CPU进行优化，并且产生的代码无法使用在不兼容的CPU上。 u /Qax：使用这个优化选项，Intel将针对特定的CPU进行优化，并且产生多份代码，在运行时根据CPU类型自动选择最优的代码。 由于本程序只需要运行在基于Core Microarchitecture 的处理器上，而无需考虑兼容性。所以本程序选择/Qx选项。并且针对运行时的酷睿2处理器，选择/QxT。但是在进行VTune测试时，由于测试平台为奔腾D 820，所以暂时使用/QxP的参数。 使用IPO 使用/Qipo可以启用Intel编译器的过程间优化(Interprocedural Optimizations)。通过过程间优化，编译器可以通过使用寄存器优化函数调用、内联函数展开、过程间常数传递、跨多文件优化等方式进一步优化程序。 此外，Intel编译器支持多文件的过程间优化，而由于本程序只有一个文件，所以并不需要使用。 但是IPO优化却会对本程序的调试带来极大的麻烦。所以本程序开发时不使用IPO优化，只有在最后的版本中才尝试使用IPO优化能否提高效率。 使用GPO Intel编译器支持GPO(Profile-Guided Optimization)。GPO由一下三步组成。 第一步：使用/Qprof-gen编译程序，产生能记录运行细节的特殊程序。 第二步：运行第一步产生的程序，生成动态信息文件(.dyn)。 第三步，使用/Qprof-use，结合动态信息文件重新编译程序，产生更优化的程序。 通过使用GPO，Intel编译器可以更详细得了解程序的运行情况，从而根据实际情况产生更优化的代码。比如优化条件跳转，使得CPU分支预测的能力更准确，又如决定哪些函数需要内联，哪些不要内联等。 此外，基于GPO还有很多的工具方便用户开发程序。比如Code-Coverage Tool可以进行代码覆盖测试。 由于GPO收集的信息和特定的程序有关，而本程序一直在修改。所以本程序只在每个版本的最后部分使用GPO进行优化。 循环展开 循环展开(Loop Unrolling)通过在把循环语句中的内容展开从而使执行的代码速度更快。循环展开可以提高代码的并行程度，减少条件转移次数从而提高速度。另外，对于Pentium 4处理器，其分支预测功能可以精确得预测出16次迭代以内的循环，所以，如果能把循环展开到迭代次数在16次以内，对于特定的CPU可以提高分支预测准确度。 但是循环展开必须有一个度，并不是展开层数越多越好，展开层数多了，可能反而影响代码的执行速度。所以通常的做法是让编译器自己决定循环展开的层数。 Intel编译器对于循环展开有如下选项： u /Qunrolln：执行循环展开n层。 u /Qunroll：让Intel编译器自己决定循环展开的层数。 此外Intel编译器还提供在了程序中使用编译制导语句规定某个特定循环的展开次数。如下例指示for循环展开n层。 #pragma unroll(n) for(i=0;i10000;i+) 所以本程序使用/Qunroll参数，让Intel编译器自己决定使用循环展开的层数。但是在程序的最终优化时，如果发现Intel编译器的循环展开并不是最优的，则通过在特定循环前加上编译制导语句，使用最佳的循环展开层数。 浮点计算优化 Intel编译器提供了很多基于浮点数的优化参数，有提供精度的，也有提高速度的。对于本程序，主要使用如下优化参数。 u /fp: fast或/fp: fast=1：这两个参数的等价的，同时也是默认的参数。他告诉编译器进行快速浮点计算优化。 u /fp: fast=2：这个参数比/fp: fast=1提供更高的优化级别，同时也可能带来更大的精度损失。 本程序使用/fp: fast=2优化，但是如果发生精度问题，可以考虑使用/fp: fast=1。 自动并行化 Intel的编译器支持自动并行化(Auto-parallelization)。通过/Qparallel可以打开编译器的自动并行化，编译器会在分析了用户的串行程序后，自动选择可以并行的部分进行并行化。自动并行化的有点是方便，不需要用户懂得专业知识，不需要更改原来的串行程序。但是缺点也是显而易见的，由于编译器并不知道用户的程序逻辑，所以无法很好得进行并行化。在对本程序试用/Qparallel后发现，效果并不好。所以本程序不只用/Qparallel进行自动并行化。 使用OpenMP并行化 OpenMP是一种通用的并行程序设计语言，其通过在源代码中添加编译制导语句，提示编译器如何进行程序的并行化。OpenMP具有书写方便，不需要改变源代码结构等多种优点。Intel的编译器支持OpenMP。本次程序并不打算使用OpenMP进行并行化，而打算使用Windows Thread。但是由于本程序需要使用到Intel Math Kernel Library，而Intel Math Kernel Library中的代码支持OpenMP并行化。所以有必要使用一些基本的OpenMP设置函数。 需要使用OpenMP，需要在编译时加上/Qopenmp选项。并且在源代码中包含” omp.h”文件。 OpenMP提供了函数omp_set_num_threads(nthreads)设置OpenMP使用的线程数，由于其设置会影响到Intel Math Kernel Library，所以将其设置成1，禁止Intel Math Kernel Library的自动并行化。 向量化 Intel的编译器支持向量化(Vectorization)。可以把循环计算部分使用MMX，SSE，SSE2，SSE3，SSSE3等指令进行向量化，从而大大提高计算速度。这也是本程序串行化时的主要优化点。前面提到的针对处理器的/QaxT优化选项已经打开了向量化。将代码向量化还有许多需要注意的地方，具体的注意点和方法将在后面具体的代码中说明。这里先给出一些对向量化有用的编译制导语句以及选项。 u /Qrestrict选项：当Intel编译器遇到循环中使用指针时，由于多个指针可能指向同一个地址，所以其无法保证指针指向内容的唯一性。故Intel编译器无法确定循环内数据是否存在依赖性。这是可以通过使用/Qrestrict选项与restrict关键字，指示某个指针指向内容的唯一性。从而能解决数据依赖性不确定的问题。 u #pragma vector编译制导语句：该编译制导语句一共包含3个。#pragma vector always用于指示编译器忽略其他因素，进行向量化。#pragma vector aligned用于指示编译器进行向量化时使用对齐的数据读写方式。#pragma vector unaligned用于指示编译器进行向量化时使用不对齐的数据读写方式。由于在使用SSE类指令进行向量化时，需要同时处理多个数据，所以每次读写的数据长度很长，可以达到128bit。所以将要处理的数据按照128bit(16byte)对齐，使用对齐的读写指令是可以提高程序运行速度的。但是需要注意的是对于实际没有对齐的数据使用#pragma vector aligned会造成程序运行错误。 使用变量对齐指示 Intel编译器提供了_declspec(align(n)用于在定义变量时指定其需要进行n字节对齐。变量对齐对于向量化计算的读取速度有很大关系。对于向量化计算一般使用_declspec(align(16)进行对齐。另外也可以使用_declspec(align(64)指定变量对齐到Cache的行首。关于Cache的行对齐的详细讨论请见后文的分析。 数据预读 通常数据是放在内存中，当要计算时才读入CPU进行计算。由于内存到CPU的传输需要很长时间，所以CPU中有多级Cache机制。Intel编译器支持数据预读优化选项。通过/Qprefetch打开数据预读优化，编译器会在使用数据前先插入预读指令，让CPU先把数据预读到Cache中，从而加快数据的访问速度。该选项默认情况下是打开的。此外Intel还提供了数据预读的编译制导语句，通过使用#pragma prefetch语句，用户可以人为得在程序中增加数据预读指令。但是需要注意的是，数据预读指令并不是越多越好的。不恰当的数据预读指令会占用内存带宽，把有用的数据从Cache中挤出去，反而影响速度。并且Core Microarchitecture体系结构已经支持给予硬件的数据预读指令。所以本程序倾向于使用给予硬件的数据预读机制。而由于/Qprefetch默认的打开的，也没有必要特意关闭该选项，Intel编译器有能力判断哪些地方可以通过合适的数据访问模式激活硬件数据预读机制，哪些地方需要额外添加数据预读指令。 产生调试信息 通过使用/Zi选项产生调试信息以帮助调试。默认为关闭。在本程序的开发阶段，打开此选项。在开发完成后关闭此选项。 使用全局优化 通过使用/Og选项打开编译器的全局优化功能。改选项需要在本程序不同的开发阶段分别尝试是否打开以确定最优优化选项。 针对Windows程序优化 通过使用/GA选项可以打开Intel编译器的针对Windows程序优化的功能。其实通过打开/GA选项，Intel可以提高访问Windows下thread-local storage(TLS)变量的速度。TLS变量通过_declspec(thread)来定义。在本程序中，并不打算使用TLS变量。但还是打开/GA选项。 内联函数扩展 Intel编译器可以通过/Obn来定义内联函数的扩展级别。当n为0禁止用户定义的内核函数的扩展。当n为1时，根据用户定义的inline关键字进行扩展。当n为2时，根据Intel编译器的自动判断进行扩展。本次程序使用/Ob2选项。 FTZ与DAZ 在计算机内浮点数是由尾数和指数组成的。尾数通常被规范化成1,2)之间。但是当数字接近0时，由于其指数已经无法将尾数规范成1,2)之间，所以需要在尾数表示成0.0000xx的形式。这种表示形式称为不规范的形式。其会影响CPU的浮点计算速度。并且由于这种数非常接近0，所有有时将其表示成0并不会影响计算的结果。所以CPU的浮点控制器有2个用于控制对于不规范数处理的选项。FTZ用于将计算结果中的不规范数表示成0，DAZ用于在读入不规范数时将其表示成0。Intel编译器提供了内置的宏来方便用户设置这两个模式。这两个宏分别是_MM_SET_FLUSH_ZERO_MODE(_MM_FLUSH_ZERO_ON)和_MM_SET_DENORMALS_ZERO_MODE(_MM_DENORMALS_ZERO_ON)。用户在程序中设置了这两个模式将有助于提高浮点计算速度。但是实际上对于本程序，由于已经使用了/O3以及SSE指令集优化。所以Intel编译器已经设置好了FTZ模式，用户不必另外设置FTZ。并且由于本程序中所有的数都是计算得来的，所以只要计算时使用了FTZ，那读取数据时就不会碰到不规范的数据，所以用户也没必要设置DAZ。 编译器报告 编译器报告虽然不能直接提供优化，但是却可以让用户了解编译器处理程序的信息，给用户更改源代码提供了很多有用的信息。对于本程序，向量化是非常重要的一步，而编译器报告可以指出某个地方是由于什么原因造成没有向量化。所以本使用使用/Qvec-report3参数对向量优化进行报告。 使用Intel编译器函数进行精确时间测量 Intel编译器提供了许多特殊的函数。这类函数一般都对应一条或者几条汇编语言。其可以让用户以比汇编语言方便的方式写出性能接近汇编语言的代码。其中最主要的是对SIMD类指令的支持。当然其中还有很多其他功能的函数。比如_rdtsc()函数。 需要注意的是要使用这些函数必需打开/Oi选项。这个选项默认是打开的。 当程序需要进行精确时间测量，比如优化后需要知道某段特定的代码到底快了多少毫米时，使用Windows的时间函数已经无法满足精度要求。这是用户可以使用Intel VTune Analyzers进行测量（具体使用方法将在后面介绍）。其实CPU已经提供了一个特殊的机器指令rdtsc，使用这条指令可以读出CPU自从启动以来的时钟周期数。由于现在的CPU主频已经是上GHz了。所以，其计时精度可以达到纳秒级。Intel提供的_rdtsc()函数使得用户不必再使用汇编语言，可以像调用函数一样得到CPU的时钟周期数。例子代码如下： 注：以下代码摘自“Intel C+ Compiler Documentation” #include int main() _int64 start, stop, elaspe; int i; int arr10000; start= _rdtsc(); for(i=0; i10000; i+) arri=i; stop= _rdtsc(); elaspe = stop -start; printf(Processor cyclesn %I64un, elaspe); return 0; 优化结果 经过以上编译器选项的调整，程序的运行速度已经达到了2.25秒。 1.3 使用Intel VTune Analyzers进行性能分析 1.3.1 Intel VTune Analyzers概述 Intel VTune Analyzers用于监视程序或者系统的各种性能，从而为用户优化程序提供有价值的数据。同时Intel VTune Analyzers也能分析其收集的信息，给出用户优化程序的建议。Intel VTune Analyzers即支持本地的数据收集，也支持远程的数据收集。在本程序中，我们只需使用其本地数据收集功能。Intel VTune Analyzers共支持3种数据收集机制。每种机制都有其自己的适用范围，详细介绍如下： u SAMPLING：其通过使用CPU内部的监视功能来检测系统底层的各种性能事件。使用这个功能无需在执行代码中插入特定的指令，因此其几乎没有探针效应。其无法给出函数间的调用关系。但是可以把相应的事件关联到程序中某行源代码或者汇编代码上。该方法通常适用于对某段程序的微调或者针对特定性能事件的调整上。 u CALL GRAPH：其通过在程序中插入特殊的指令，来记录每个函数执行的时间。函数间的调用关系等。其有一定的探针效应。该方法通常用于对于整个比较庞大的程序，进行分析，找出其中具有性能瓶颈的函数。 u COUNTER MONITOR：其无需在程序内部插入特殊的指令，因此其几乎没有探针效应。该方法即无法显示函数间的调用关系，也没法把事件定位到具体的某行代码中。该方式是用于测试整个系统的某些性能，比如CPU占用率，内存带宽等。通常用于系统级的调试。 对于本程序。由于程序结构简单。无需进行函数间调用的分析。而主要需要进行基于特定代码的分析。特别是后期需要针对CPU内部的事件特性进行源代码级甚至是汇编级的调试。所以本次优化主要采用SAMPLING方式。 1.3.2基于SAMPLING方式的分析 原理：Intel的CPU有一组性能检测寄存器，由于记录各种影响性能的事件。程序首先通过编程设定需要检测的事件，并且设定触发中断的计数值。当CPU中被检测的事件达到预设的值后触发相应的中断。Intel VTune Analyzers中的SAMPLING就是使用CPU的性能检测功能帮助用户分析程序的性能。其中有关于内存访问的事件，分支预测的事件，指令执行的事件等等。由于不同的CPU支持不同的性能事件，所以在不同的CPU上使用VTune时，所能监视的事件并不相同。 使用注意事项：SAMPLING一共支持2种统计。一种是Event，其是直接测量得到的值。另外一种是Event Ratio，其是基于多个Event计算得到的，有时更有实际意义，更直观。需要注意的是，每个Event都有一个预设的值，当这个预设的值到了以后，CPU引起中断，VTune进行统计。而这个值的设置不能太大，否则统计到的事件不够多，无法分析。也不能太小，否则频繁引起中断，会加大探针效应。用户可以在每个Event上手工设置合适的Sample After值，也可以通过选项卡上的选项，让VTune先运行一遍程序，然后根据实际的事件数量来校准触发值。对于本程序，这点尤其需要引起注意。因为本程序优化到后面时间非常短，如果不校准触发值，分析的效果会不理想。需要注意的是Clockticks和Instructions Retired这两个最基本的事件，默认是不校准触发值的，我们需要把他们调整成自动校准。此外对于某个Event的发生，大部分的中断点并不是精确的。即真正发生该事件的指令在所记录事件指令的前几条。但是有一部分属于精确事件，引起这类事件的指令正好是发生中断的前一条。 1.3.3对于本次程序的分析 本程序首先使用VTune最基本的3个事件(Clockticks、Instructions Retired和CPI)进行程序耗时分析。其结果如图： 说明程序中耗时最长的是computePot函数。 1.4 优化computePot函数 在对computePot函数向量化前，我们可以注意到distx，disty，distz三个变量都是临时变量。先将这3个变量去掉，从而可以使得Intel编译器能够更灵活得进行中间结果优化。另外最完成循环的i虽然是从0开始的，但是实际0和1并不进行计算，所以把外层循环的i设置层从2开始。代码如下： for( i=2; iNPARTS; i+ ) for( j=0; ji-1; j+ ) dist = sqrt( (r0j - r0i)*(r0j - r0i) + (r1j - r1i)*(r1j - r1i) + (r2j - r2i)*(r2j - r2i) ); pot += 1.0 / dist; 此时编译器显示内层循环已经向量化了。但是这个绝非我们的目标。为了提高计算开根号倒数的速度，为了使用Intel Math Kernel Library，我们需要把开根号倒数的计算先存在一组向量中，再一同计算。既将dist变量变成，dist数组，然后再对dist数组统一计算，再求和。代码如下： for( i=2; iNPARTS; i+ ) for( j=0; ji-1; j+ ) distj = (r0j - r0i)*(r0j - r0i) + (r1j - r1i)*(r1j - r1i) + (r2j - r2i)*(r2j - r2i); for( j=0; ji-1; j+ ) distj = 1.0 / sqrt(distj); for( j=0; ji-1; j+ ) pot += distj; Intel编译器提示，内部的3个循环都进行了向量化。此时出现了令人惊喜的成绩。程序的执行时间突然降到了1.453秒。使用VTune进行分析，发现Intel编译器对于开根号倒数的计算自动调用了内部的向量化代码库。注意此时，还没有使用Intel Math Kernel Library，所以这个向量代码库是Intel编译器内置的，虽然效率没有使用Intel Math Kernel Library高，但是速度已经提高了很多。调用Intel编译器内置的向量库的结果如图： 1.5 使用Intel Math Kernel Library Intel Math Kernel Library中提供了一部分的向量函数(Vector Mathematical Functions)。这类函数提供了对于普通数学计算函数的快速的向量化计算。VML中有一个向量函数就是计算开根号倒数的。 Intel的VML库中提供了如下函数来计算整个向量中各个数的开根号倒数： vdInvSqrt( n, a, y ) 其中n表示计算的元素个数。a是指向输入计算数据数组的头指针。y是指向输出计算数据数组的头指针。其中a和y可以相同。 要使用该函数，首先需要在头文件中包含”mkl.h”，并且链接mkl_c.lib文件和libguide40.lib文件。 除了基本计算功能外，VML还提供了一个设置模式的函数，用于设置特定的计算模式： vmlSetMode ( mode ) 其中的mode是一个预定义宏。在我们的程序中，需要设置如下模式： VML_LA：VML的所有向量函数都提供了2个精度的版本。精度低的版本计算速度也相对比较快。本程序只需要保留小数点后7位精度。低精度的版本符合要求，所以设定VML使用低精度的版本。 VML_DOUBLE_CONSISTENT：该选项用于控制FPU的计算精度为double，其实由于我们这次使用的函数基本上是使用SSE2指令集进行计算的，和FPU没什么关系。但是也可能存在使用FPU的可能，所以设定VML使FPU的精度为double。 VML_ERRMODE_IGNORE：该选项用于关闭VML的错误处理功能，本程序不需要进行错误处理。 VML_NUM_THREADS_OMP_FIXED：VML函数都能使用OpenMP，根据特定的硬件环境进行并行化。而我们并不需要其进行并行化。所以使用该选项和前面提到的omp_set_num_threads(1)结合。关闭VML的自动并行化功能。 具体的代码如下： for( i=2; iNPARTS; i+ ) for( j=0; ji-1; j+ ) distj = (r0j - r0i)*(r0j - r0i) + (r1j - r1i)*(r1j - r1i) + (r2j - r2i)*(r2j - r2i); vdInvSqrt(i-1,dist,dist); for( j=0; ji-1; j+ ) pot += distj; 优化后出现了令人可惜可贺的成绩：0.796秒。 1.6 根据Cache大小优化Intel Math Kernel Library调用 在上面的程序中对于MKL函数的调用是每次内部循环都执行一次调用，我们知道每次执行函数的调用都是需要开销的，那是否有更优化的调用MKL方法那？下面这段话摘自Intel Math Kernel Library的说明文档上： There are two extreme cases: so-called short and long vectors (logarithmic scale is used to show both cases). For short vectors there are cycle organization and initialization overheads. The cost of such overheads is amortized with increasing vector length, and for vectors longer than a few dozens of elements the performance remains quite flat until the L2 cache size is exceeded with the length of the vector. 下面这副性能分析图片摘自Intel Math Kernel Library的网站上： 从这段文字和这副图片中，我们了解到对于MKL函数的调用时，所处理的向量不能太短，否则函数的建立时间开销将是非常大的，也不能太长，操作了L2 Cache，否则函数执行时访问内存的开销是很大的。并且通过图片了解到不合适的长度对于函数的性能将产生指数级影响。 根据理论计算：每次执行computePot函数，总共需要执行的计算量为(1+998)*998/2=498501个。每个double类型占用8个字节，所有总共需要占用的空间为498501*8=3988008byte=3894KB。而这次进行竞赛的测试平台的CPU的L2 Cache大小为2M，由于有2个线程同时计算，平均每个线程分到的L2 Cache为1M。由于L2 Cache可能还被其他数据占据。所以为了保证所计算的数据在L2 Cache中，最好每次计算的向量长度在512KB左右。故把整个computePot函数的计算量分成8份。每份计算量的中间结果向量长度为3894KB/8=486KB。 但是实际情况并非如此，进行这种优化后，程序的执行速度反而降低了。通过分析发现原来CPU中的L1 Cache大小为32KB。数组r有3000个元素，如果每次迭代都进行vdInvSqrt调用。那dist的长度为1000个元素左右。加起来正好可以全部在L1 Cache中。而如果合并起来调用vdInvSqrt，则由于vdInvSqrt过长。其L1 Cache中存放不下，需要存放在L2 Cache中，从而反而影响了速度。看来，对于本程序，不应该根据L2 Cache进行优化，而应该根据L1 Cache进行优化。但是对于只有几个或者几十个数据就调用MKL函数，其开销还是很大的。因此本程序使用了折中的方法，对于前面非常小的几十个数据，凑足1000个放在一起进行计算，而后面的数据还是按照原来的方式计算。具体实现的代码如下： for( i=2,k=0; i47; i+ ) for( j=0; ji-1; j+,k+ ) distk = (r0j - r0i)*(r0j - r0i) + (r1j - r1i)*(r1j - r1i) + (r2j - r2i)*(r2j - r2i); vdInvSqrt(k,dist,dist); for( j=0; jk; j+ ) pot += distj; for( i=47; iNPARTS; i+ ) for( j=0; ji-1; j+ ) distj = (r0j - r0i)*(r0j - r0i) + (r1j - r1i)*(r1j - r1i) + (r2j - r2i)*(r2j - r2i); vdInvSqrt(i-1,dist,dist); for( j=0; ji-1; j+ ) pot += distj; 通过该不优化，程序的性能略微有所提高，达到了0.781秒。 1.7 优化updatePositions函数 虽然updatePositions函数执行的时间非常短。但还是值得优化的。 首先进行的是基于数学的优化。我们发现在updatePositions和initPositions中，都有加0.5的计算。但是从后面的computePot的相减计算中发现，这个0.5是被抵消的，既不加0.5对结果没有影响。故去掉该加0.5的计算。另外updatePositions和initPositions中都有除以RAND_MAX的计算。而通过提取公因子的变换发现，如果此处不除以RAND_MAX而将最后的pot乘以RAND_MAX，则最后结果相同。故去掉该处的除以RAND_MAX的计算，而以在pot上一次乘以RAND_MAX为替换。具体代码如下： void initPositions() int i, j; for( i=0; iDIMS; i+ ) for( j=0; jNPARTS; j+ )