英特尔多核平台编程优化大赛报告
前言
本次優(yōu)化使用的CPU是Intel?Xeon?5130?主頻為2.0GHz?同Intel酷睿2一樣是基于Core?Microarchitecture?的雙核處理器。本次優(yōu)化在Intel的工具幫助下主要針對Core?Microarchitecture?系列處理器進行優(yōu)化。但是由于未知原因，Intel?VTune?Analyzers并不能在該系統(tǒng)下正常工作。所以，所有使用Intel?VTune?Analyzers的測試均使用另外一個奔騰D?820的系統(tǒng)測試。
第一章主要介紹了程序的串行優(yōu)化。其中有關(guān)于Intel編譯器使用，以及Intel?Math?Kernel?Library使用，Intel?VTune?Analyzers使用的介紹。在借助Intel工具的幫助下，結(jié)合Intel?Core?Microarchitectured的特性。設(shè)計出了針對L1?Cache進行優(yōu)化的，高效率的串行代碼。程序的執(zhí)行時間從優(yōu)化前的4.765秒達到了優(yōu)化后的0.765秒。
第二章主要介紹了程序的并行化。首先討論了2種并行算法的優(yōu)缺點。然后選擇了適合本程序的并行算法進行優(yōu)化。并且在最后分析了并行化時的性能瓶頸。通過并行化，程序達到了0.437秒。
第三章主要介紹了程序的匯編優(yōu)化。首先介紹了計算的數(shù)學(xué)理論。然后介紹了匯編代碼的編寫。最后進行了性能分析。通過該步優(yōu)化程序在保留小數(shù)點后7位精度的前提下達到了0.312秒的好成績。并且在Intel酷睿2?E6600?上測試達到了0.25秒。
附錄A?說明了本次報告的目錄結(jié)構(gòu)和優(yōu)化方法。
附錄B?列出了進行本次競賽所參考的文獻。
?
目錄
一、串行優(yōu)化
1.1?代碼的基本修改和優(yōu)化
1.2?基于Intel編譯器的優(yōu)化
1.3?使用Intel?VTune?Analyzers進行性能分析
1.3.1?Intel?VTune?Analyzers概述
1.3.2?基于SAMPLING方式的分析
1.3.3?對于本次程序的分析
1.4?優(yōu)化computePot函數(shù)
1.5?使用Intel?Math?Kernel?Library
1.6?根據(jù)Cache大小優(yōu)化Intel?Math?Kernel?Library調(diào)用
1.7?優(yōu)化updatePositions函數(shù)
1.8?其他優(yōu)化以及性能分析
二、并行優(yōu)化
2.1?并行優(yōu)化概述
2.2?優(yōu)化方案一
2.3?優(yōu)化方案二
2.4?并行實現(xiàn)
2.5?性能分析
三、匯編級優(yōu)化
3.1?優(yōu)化目標(biāo)
3.2?數(shù)學(xué)理論
3.3?匯編碼實現(xiàn)
3.4?性能分析
3.5?總結(jié)
附錄A?目錄結(jié)構(gòu)和編譯方法
附錄B?參考文獻
一、串行優(yōu)化
1.1?代碼的基本修改和優(yōu)化
首先根據(jù)主辦方的要求把代碼的輸出精度改為小數(shù)點后7位。
| if?(i%10?==?0)?printf("%5d:?Potential:?%20.7f/n",?i,?pot); |
在進行任何優(yōu)化前代碼的執(zhí)行時間是4.765秒。
接著把項目轉(zhuǎn)換成使用Intel?C++?Compiler，代碼的執(zhí)行時間是4.531秒。
然后執(zhí)行最基本的優(yōu)化，把代碼中的pow函數(shù)優(yōu)化成乘法。代碼如下：
?
| distx?=?(r[0][j]?-?r[0][i])*(r[0][j]?-?r[0][i]); disty?=?(r[1][j]?-?r[1][i])*(r[1][j]?-?r[1][i]); distz?=?(r[2][j]?-?r[2][i])*(r[2][j]?-?r[2][i]); |
執(zhí)行時間依然為4.531秒。說明Intel編譯器已經(jīng)將pow函數(shù)優(yōu)化掉了。
1.2?基于Intel編譯器的優(yōu)化
這里介紹本程序中基于Intel編譯器優(yōu)化技術(shù)。其中有些優(yōu)化參數(shù)是可以確定的，有些優(yōu)化參數(shù)需要在程序的不同階段反復(fù)調(diào)試以確定最優(yōu)方案，而有些優(yōu)化技術(shù)是在后面的優(yōu)化中使用的。
編譯器優(yōu)化級別
Intel的編譯器共有如下一些主要的優(yōu)化級別：
u???????/O1：實現(xiàn)最基本的優(yōu)化
u???????/O2：基于代碼速度實現(xiàn)常規(guī)優(yōu)化，這個也是默認的優(yōu)化級別
u???????/O3：在/O2的基礎(chǔ)上實現(xiàn)進一步的優(yōu)化，包括Cache預(yù)讀，標(biāo)量轉(zhuǎn)換等等，但是在某些情況下反而會減慢代碼的執(zhí)行速度。
u???????/Ox：實現(xiàn)最大化的優(yōu)化，包括自動內(nèi)聯(lián)函數(shù)的確定，全局優(yōu)化，使用EBP作為通用寄存器等。
u???????/fast：等同于/O3,?/Qipo,?/Qprec-div-,?and?/QxP。
通過測試，目前選用/O3，但是隨著代碼的更改，需要重新測試，選擇合適的優(yōu)化級別。
針對特定處理器進行優(yōu)化
Intel的編譯器一共支持如下3種針對特定處理器的優(yōu)化：
u???????/G：使用這個優(yōu)化選項，Intel將針對特定的CPU進行優(yōu)化，但是其代碼依然可以在所有的CPU上執(zhí)行。
u???????/Qx：使用這個優(yōu)化選項，Intel將針對特定的CPU進行優(yōu)化，并且產(chǎn)生的代碼無法使用在不兼容的CPU上。
u???????/Qax：使用這個優(yōu)化選項，Intel將針對特定的CPU進行優(yōu)化，并且產(chǎn)生多份代碼，在運行時根據(jù)CPU類型自動選擇最優(yōu)的代碼。
由于本程序只需要運行在基于Core?Microarchitecture?的處理器上，而無需考慮兼容性。所以本程序選擇/Qx選項。并且針對運行時的酷睿2處理器，選擇/QxT。但是在進行VTune測試時，由于測試平臺為奔騰D?820，所以暫時使用/QxP的參數(shù)。
使用IPO
使用/Qipo可以啟用Intel編譯器的過程間優(yōu)化(Interprocedural?Optimizations)。通過過程間優(yōu)化，編譯器可以通過使用寄存器優(yōu)化函數(shù)調(diào)用、內(nèi)聯(lián)函數(shù)展開、過程間常數(shù)傳遞、跨多文件優(yōu)化等方式進一步優(yōu)化程序。
此外，Intel編譯器支持多文件的過程間優(yōu)化，而由于本程序只有一個文件，所以并不需要使用。
但是IPO優(yōu)化卻會對本程序的調(diào)試帶來極大的麻煩。所以本程序開發(fā)時不使用IPO優(yōu)化，只有在最后的版本中才嘗試使用IPO優(yōu)化能否提高效率。
使用GPO
Intel編譯器支持GPO(Profile-Guided?Optimization)。GPO由一下三步組成。
第一步：使用/Qprof-gen編譯程序，產(chǎn)生能記錄運行細節(jié)的特殊程序。
第二步：運行第一步產(chǎn)生的程序，生成動態(tài)信息文件(.dyn)。
第三步，使用/Qprof-use，結(jié)合動態(tài)信息文件重新編譯程序，產(chǎn)生更優(yōu)化的程序。
通過使用GPO，Intel編譯器可以更詳細得了解程序的運行情況，從而根據(jù)實際情況產(chǎn)生更優(yōu)化的代碼。比如優(yōu)化條件跳轉(zhuǎn)，使得CPU分支預(yù)測的能力更準確，又如決定哪些函數(shù)需要內(nèi)聯(lián)，哪些不要內(nèi)聯(lián)等。
此外，基于GPO還有很多的工具方便用戶開發(fā)程序。比如Code-Coverage?Tool可以進行代碼覆蓋測試。
由于GPO收集的信息和特定的程序有關(guān)，而本程序一直在修改。所以本程序只在每個版本的最后部分使用GPO進行優(yōu)化。
循環(huán)展開
循環(huán)展開(Loop?Unrolling)通過在把循環(huán)語句中的內(nèi)容展開從而使執(zhí)行的代碼速度更快。循環(huán)展開可以提高代碼的并行程度，減少條件轉(zhuǎn)移次數(shù)從而提高速度。另外，對于Pentium?4處理器，其分支預(yù)測功能可以精確得預(yù)測出16次迭代以內(nèi)的循環(huán)，所以，如果能把循環(huán)展開到迭代次數(shù)在16次以內(nèi)，對于特定的CPU可以提高分支預(yù)測準確度。
但是循環(huán)展開必須有一個度，并不是展開層數(shù)越多越好，展開層數(shù)多了，可能反而影響代碼的執(zhí)行速度。所以通常的做法是讓編譯器自己決定循環(huán)展開的層數(shù)。
Intel編譯器對于循環(huán)展開有如下選項：
u???????/Qunrolln：執(zhí)行循環(huán)展開n層。
u???????/Qunroll：讓Intel編譯器自己決定循環(huán)展開的層數(shù)。
此外Intel編譯器還提供在了程序中使用編譯制導(dǎo)語句規(guī)定某個特定循環(huán)的展開次數(shù)。如下例指示for循環(huán)展開n層。
?
| #pragma?unroll(n) for(i=0;i<10000;i++){……} |
所以本程序使用/Qunroll參數(shù)，讓Intel編譯器自己決定使用循環(huán)展開的層數(shù)。但是在程序的最終優(yōu)化時，如果發(fā)現(xiàn)Intel編譯器的循環(huán)展開并不是最優(yōu)的，則通過在特定循環(huán)前加上編譯制導(dǎo)語句，使用最佳的循環(huán)展開層數(shù)。
浮點計算優(yōu)化
Intel編譯器提供了很多基于浮點數(shù)的優(yōu)化參數(shù)，有提供精度的，也有提高速度的。對于本程序，主要使用如下優(yōu)化參數(shù)。
u???????/fp:?fast或/fp:?fast=1：這兩個參數(shù)的等價的，同時也是默認的參數(shù)。他告訴編譯器進行快速浮點計算優(yōu)化。
u???????/fp:?fast=2：這個參數(shù)比/fp:?fast=1提供更高的優(yōu)化級別，同時也可能帶來更大的精度損失。
本程序使用/fp:?fast=2優(yōu)化，但是如果發(fā)生精度問題，可以考慮使用/fp:?fast=1。
自動并行化
Intel的編譯器支持自動并行化(Auto-parallelization)。通過/Qparallel可以打開編譯器的自動并行化，編譯器會在分析了用戶的串行程序后，自動選擇可以并行的部分進行并行化。自動并行化的有點是方便，不需要用戶懂得專業(yè)知識，不需要更改原來的串行程序。但是缺點也是顯而易見的，由于編譯器并不知道用戶的程序邏輯，所以無法很好得進行并行化。在對本程序試用/Qparallel后發(fā)現(xiàn)，效果并不好。所以本程序不只用/Qparallel進行自動并行化。
使用OpenMP并行化
OpenMP是一種通用的并行程序設(shè)計語言，其通過在源代碼中添加編譯制導(dǎo)語句，提示編譯器如何進行程序的并行化。OpenMP具有書寫方便，不需要改變源代碼結(jié)構(gòu)等多種優(yōu)點。Intel的編譯器支持OpenMP。本次程序并不打算使用OpenMP進行并行化，而打算使用Windows?Thread。但是由于本程序需要使用到Intel?Math?Kernel?Library，而Intel?Math?Kernel?Library中的代碼支持OpenMP并行化。所以有必要使用一些基本的OpenMP設(shè)置函數(shù)。
需要使用OpenMP，需要在編譯時加上/Qopenmp選項。并且在源代碼中包含”?omp.h”文件。
OpenMP提供了函數(shù)omp_set_num_threads(nthreads)設(shè)置OpenMP使用的線程數(shù)，由于其設(shè)置會影響到Intel?Math?Kernel?Library，所以將其設(shè)置成1，禁止Intel?Math?Kernel?Library的自動并行化。
向量化
Intel的編譯器支持向量化(Vectorization)。可以把循環(huán)計算部分使用MMX，SSE，SSE2，SSE3，SSSE3等指令進行向量化，從而大大提高計算速度。這也是本程序串行化時的主要優(yōu)化點。前面提到的針對處理器的/QaxT優(yōu)化選項已經(jīng)打開了向量化。將代碼向量化還有許多需要注意的地方，具體的注意點和方法將在后面具體的代碼中說明。這里先給出一些對向量化有用的編譯制導(dǎo)語句以及選項。
u???????/Qrestrict選項：當(dāng)Intel編譯器遇到循環(huán)中使用指針時，由于多個指針可能指向同一個地址，所以其無法保證指針指向內(nèi)容的唯一性。故Intel編譯器無法確定循環(huán)內(nèi)數(shù)據(jù)是否存在依賴性。這是可以通過使用/Qrestrict選項與restrict關(guān)鍵字，指示某個指針指向內(nèi)容的唯一性。從而能解決數(shù)據(jù)依賴性不確定的問題。
u???????#pragma?vector編譯制導(dǎo)語句：該編譯制導(dǎo)語句一共包含3個。#pragma?vector?always用于指示編譯器忽略其他因素，進行向量化。#pragma?vector?aligned用于指示編譯器進行向量化時使用對齊的數(shù)據(jù)讀寫方式。#pragma?vector?unaligned用于指示編譯器進行向量化時使用不對齊的數(shù)據(jù)讀寫方式。由于在使用SSE類指令進行向量化時，需要同時處理多個數(shù)據(jù)，所以每次讀寫的數(shù)據(jù)長度很長，可以達到128bit。所以將要處理的數(shù)據(jù)按照128bit(16byte)對齊，使用對齊的讀寫指令是可以提高程序運行速度的。但是需要注意的是對于實際沒有對齊的數(shù)據(jù)使用#pragma?vector?aligned會造成程序運行錯誤。
使用變量對齊指示
Intel編譯器提供了__declspec(align(n))用于在定義變量時指定其需要進行n字節(jié)對齊。變量對齊對于向量化計算的讀取速度有很大關(guān)系。對于向量化計算一般使用__declspec(align(16))進行對齊。另外也可以使用__declspec(align(64))指定變量對齊到Cache的行首。關(guān)于Cache的行對齊的詳細討論請見后文的分析。
數(shù)據(jù)預(yù)讀
通常數(shù)據(jù)是放在內(nèi)存中，當(dāng)要計算時才讀入CPU進行計算。由于內(nèi)存到CPU的傳輸需要很長時間，所以CPU中有多級Cache機制。Intel編譯器支持數(shù)據(jù)預(yù)讀優(yōu)化選項。通過/Qprefetch打開數(shù)據(jù)預(yù)讀優(yōu)化，編譯器會在使用數(shù)據(jù)前先插入預(yù)讀指令，讓CPU先把數(shù)據(jù)預(yù)讀到Cache中，從而加快數(shù)據(jù)的訪問速度。該選項默認情況下是打開的。此外Intel還提供了數(shù)據(jù)預(yù)讀的編譯制導(dǎo)語句，通過使用#pragma?prefetch語句，用戶可以人為得在程序中增加數(shù)據(jù)預(yù)讀指令。但是需要注意的是，數(shù)據(jù)預(yù)讀指令并不是越多越好的。不恰當(dāng)?shù)臄?shù)據(jù)預(yù)讀指令會占用內(nèi)存帶寬，把有用的數(shù)據(jù)從Cache中擠出去，反而影響速度。并且Core?Microarchitecture體系結(jié)構(gòu)已經(jīng)支持給予硬件的數(shù)據(jù)預(yù)讀指令。所以本程序傾向于使用給予硬件的數(shù)據(jù)預(yù)讀機制。而由于/Qprefetch默認的打開的，也沒有必要特意關(guān)閉該選項，Intel編譯器有能力判斷哪些地方可以通過合適的數(shù)據(jù)訪問模式激活硬件數(shù)據(jù)預(yù)讀機制，哪些地方需要額外添加數(shù)據(jù)預(yù)讀指令。
產(chǎn)生調(diào)試信息
通過使用/Zi選項產(chǎn)生調(diào)試信息以幫助調(diào)試。默認為關(guān)閉。在本程序的開發(fā)階段，打開此選項。在開發(fā)完成后關(guān)閉此選項。
使用全局優(yōu)化
通過使用/Og選項打開編譯器的全局優(yōu)化功能。改選項需要在本程序不同的開發(fā)階段分別嘗試是否打開以確定最優(yōu)優(yōu)化選項。
針對Windows程序優(yōu)化
通過使用/GA選項可以打開Intel編譯器的針對Windows程序優(yōu)化的功能。其實通過打開/GA選項，Intel可以提高訪問Windows下thread-local?storage(TLS)變量的速度。TLS變量通過__declspec(thread)來定義。在本程序中，并不打算使用TLS變量。但還是打開/GA選項。
?
內(nèi)聯(lián)函數(shù)擴展
Intel編譯器可以通過/Obn來定義內(nèi)聯(lián)函數(shù)的擴展級別。當(dāng)n為0禁止用戶定義的內(nèi)核函數(shù)的擴展。當(dāng)n為1時，根據(jù)用戶定義的inline關(guān)鍵字進行擴展。當(dāng)n為2時，根據(jù)Intel編譯器的自動判斷進行擴展。本次程序使用/Ob2選項。
FTZ與DAZ
在計算機內(nèi)浮點數(shù)是由尾數(shù)和指數(shù)組成的。尾數(shù)通常被規(guī)范化成[1,2)之間。但是當(dāng)數(shù)字接近0時，由于其指數(shù)已經(jīng)無法將尾數(shù)規(guī)范成[1,2)之間，所以需要在尾數(shù)表示成0.0000xx的形式。這種表示形式稱為不規(guī)范的形式。其會影響CPU的浮點計算速度。并且由于這種數(shù)非常接近0，所有有時將其表示成0并不會影響計算的結(jié)果。所以CPU的浮點控制器有2個用于控制對于不規(guī)范數(shù)處理的選項。FTZ用于將計算結(jié)果中的不規(guī)范數(shù)表示成0，DAZ用于在讀入不規(guī)范數(shù)時將其表示成0。Intel編譯器提供了內(nèi)置的宏來方便用戶設(shè)置這兩個模式。這兩個宏分別是_MM_SET_FLUSH_ZERO_MODE(_MM_FLUSH_ZERO_ON)和_MM_SET_DENORMALS_ZERO_MODE(_MM_DENORMALS_ZERO_ON)。用戶在程序中設(shè)置了這兩個模式將有助于提高浮點計算速度。但是實際上對于本程序，由于已經(jīng)使用了/O3以及SSE指令集優(yōu)化。所以Intel編譯器已經(jīng)設(shè)置好了FTZ模式，用戶不必另外設(shè)置FTZ。并且由于本程序中所有的數(shù)都是計算得來的，所以只要計算時使用了FTZ，那讀取數(shù)據(jù)時就不會碰到不規(guī)范的數(shù)據(jù)，所以用戶也沒必要設(shè)置DAZ。
?
?
編譯器報告
編譯器報告雖然不能直接提供優(yōu)化，但是卻可以讓用戶了解編譯器處理程序的信息，給用戶更改源代碼提供了很多有用的信息。對于本程序，向量化是非常重要的一步，而編譯器報告可以指出某個地方是由于什么原因造成沒有向量化。所以本使用使用/Qvec-report3參數(shù)對向量優(yōu)化進行報告。
使用Intel編譯器函數(shù)進行精確時間測量
Intel編譯器提供了許多特殊的函數(shù)。這類函數(shù)一般都對應(yīng)一條或者幾條匯編語言。其可以讓用戶以比匯編語言方便的方式寫出性能接近匯編語言的代碼。其中最主要的是對SIMD類指令的支持。當(dāng)然其中還有很多其他功能的函數(shù)。比如_rdtsc()函數(shù)。
需要注意的是要使用這些函數(shù)必需打開/Oi選項。這個選項默認是打開的。
當(dāng)程序需要進行精確時間測量，比如優(yōu)化后需要知道某段特定的代碼到底快了多少毫米時，使用Windows的時間函數(shù)已經(jīng)無法滿足精度要求。這是用戶可以使用Intel?VTune?Analyzers進行測量（具體使用方法將在后面介紹）。其實CPU已經(jīng)提供了一個特殊的機器指令rdtsc，使用這條指令可以讀出CPU自從啟動以來的時鐘周期數(shù)。由于現(xiàn)在的CPU主頻已經(jīng)是上GHz了。所以，其計時精度可以達到納秒級。Intel提供的_rdtsc()函數(shù)使得用戶不必再使用匯編語言，可以像調(diào)用函數(shù)一樣得到CPU的時鐘周期數(shù)。例子代碼如下：
注：以下代碼摘自“Intel?C++?Compiler?Documentation”
?
| #include?<stdio.h> int?main() { ?__int64?start,?stop,?elaspe; ?int?i; ?int?arr[10000]; ?start=?_rdtsc();? ?for(i=0;?i<10000;?i++) ?{ ????arr[i]=i; ?} ?stop=?_rdtsc(); ?elaspe?=?stop?-start; ?printf("Processor?cycles/n?%I64u/n",?elaspe); ?return?0; } |
優(yōu)化結(jié)果
經(jīng)過以上編譯器選項的調(diào)整，程序的運行速度已經(jīng)達到了2.25秒。
1.3?使用Intel?VTune?Analyzers進行性能分析
1.3.1?Intel?VTune?Analyzers概述
Intel?VTune?Analyzers用于監(jiān)視程序或者系統(tǒng)的各種性能，從而為用戶優(yōu)化程序提供有價值的數(shù)據(jù)。同時Intel?VTune?Analyzers也能分析其收集的信息，給出用戶優(yōu)化程序的建議。Intel?VTune?Analyzers即支持本地的數(shù)據(jù)收集，也支持遠程的數(shù)據(jù)收集。在本程序中，我們只需使用其本地數(shù)據(jù)收集功能。Intel?VTune?Analyzers共支持3種數(shù)據(jù)收集機制。每種機制都有其自己的適用范圍，詳細介紹如下：
u???????SAMPLING：其通過使用CPU內(nèi)部的監(jiān)視功能來檢測系統(tǒng)底層的各種性能事件。使用這個功能無需在執(zhí)行代碼中插入特定的指令，因此其幾乎沒有探針效應(yīng)。其無法給出函數(shù)間的調(diào)用關(guān)系。但是可以把相應(yīng)的事件關(guān)聯(lián)到程序中某行源代碼或者匯編代碼上。該方法通常適用于對某段程序的微調(diào)或者針對特定性能事件的調(diào)整上。
u???????CALL?GRAPH：其通過在程序中插入特殊的指令，來記錄每個函數(shù)執(zhí)行的時間。函數(shù)間的調(diào)用關(guān)系等。其有一定的探針效應(yīng)。該方法通常用于對于整個比較龐大的程序，進行分析，找出其中具有性能瓶頸的函數(shù)。
u???????COUNTER?MONITOR：其無需在程序內(nèi)部插入特殊的指令，因此其幾乎沒有探針效應(yīng)。該方法即無法顯示函數(shù)間的調(diào)用關(guān)系，也沒法把事件定位到具體的某行代碼中。該方式是用于測試整個系統(tǒng)的某些性能，比如CPU占用率，內(nèi)存帶寬等。通常用于系統(tǒng)級的調(diào)試。
對于本程序。由于程序結(jié)構(gòu)簡單。無需進行函數(shù)間調(diào)用的分析。而主要需要進行基于特定代碼的分析。特別是后期需要針對CPU內(nèi)部的事件特性進行源代碼級甚至是匯編級的調(diào)試。所以本次優(yōu)化主要采用SAMPLING方式。
1.3.2基于SAMPLING方式的分析
原理：Intel的CPU有一組性能檢測寄存器，由于記錄各種影響性能的事件。程序首先通過編程設(shè)定需要檢測的事件，并且設(shè)定觸發(fā)中斷的計數(shù)值。當(dāng)CPU中被檢測的事件達到預(yù)設(shè)的值后觸發(fā)相應(yīng)的中斷。Intel?VTune?Analyzers中的SAMPLING就是使用CPU的性能檢測功能幫助用戶分析程序的性能。其中有關(guān)于內(nèi)存訪問的事件，分支預(yù)測的事件，指令執(zhí)行的事件等等。由于不同的CPU支持不同的性能事件，所以在不同的CPU上使用VTune時，所能監(jiān)視的事件并不相同。
使用注意事項：SAMPLING一共支持2種統(tǒng)計。一種是Event，其是直接測量得到的值。另外一種是Event?Ratio，其是基于多個Event計算得到的，有時更有實際意義，更直觀。需要注意的是，每個Event都有一個預(yù)設(shè)的值，當(dāng)這個預(yù)設(shè)的值到了以后，CPU引起中斷，VTune進行統(tǒng)計。而這個值的設(shè)置不能太大，否則統(tǒng)計到的事件不夠多，無法分析。也不能太小，否則頻繁引起中斷，會加大探針效應(yīng)。用戶可以在每個Event上手工設(shè)置合適的Sample?After值，也可以通過選項卡上的選項，讓VTune先運行一遍程序，然后根據(jù)實際的事件數(shù)量來校準觸發(fā)值。對于本程序，這點尤其需要引起注意。因為本程序優(yōu)化到后面時間非常短，如果不校準觸發(fā)值，分析的效果會不理想。需要注意的是Clockticks和Instructions?Retired這兩個最基本的事件，默認是不校準觸發(fā)值的，我們需要把他們調(diào)整成自動校準。此外對于某個Event的發(fā)生，大部分的中斷點并不是精確的。即真正發(fā)生該事件的指令在所記錄事件指令的前幾條。但是有一部分屬于精確事件，引起這類事件的指令正好是發(fā)生中斷的前一條。
1.3.3對于本次程序的分析
本程序首先使用VTune最基本的3個事件(Clockticks、Instructions?Retired和CPI)進行程序耗時分析。其結(jié)果如圖：
說明程序中耗時最長的是computePot函數(shù)。
1.4?優(yōu)化computePot函數(shù)
在對computePot函數(shù)向量化前，我們可以注意到distx，disty，distz三個變量都是臨時變量。先將這3個變量去掉，從而可以使得Intel編譯器能夠更靈活得進行中間結(jié)果優(yōu)化。另外最完成循環(huán)的i雖然是從0開始的，但是實際0和1并不進行計算，所以把外層循環(huán)的i設(shè)置層從2開始。代碼如下：
?
| ???for(?i=2;?i<NPARTS;?i++?)?{ ??????for(?j=0;?j<i-1;?j++?)?{ ????????dist?=?sqrt(?(r[0][j]?-?r[0][i])*(r[0][j]?-?r[0][i])?+?(r[1][j]?-?r[1][i])*(r[1][j]?-?r[1][i])?+?(r[2][j]?-?r[2][i])*(r[2][j]?-?r[2][i])?); ????????pot?+=?1.0?/?dist; ??????} ???} |
此時編譯器顯示內(nèi)層循環(huán)已經(jīng)向量化了。但是這個絕非我們的目標(biāo)。為了提高計算開根號倒數(shù)的速度，為了使用Intel?Math?Kernel?Library，我們需要把開根號倒數(shù)的計算先存在一組向量中，再一同計算。既將dist變量變成，dist數(shù)組，然后再對dist數(shù)組統(tǒng)一計算，再求和。代碼如下：
?
| ???for(?i=2;?i<NPARTS;?i++?)?{ ??????for(?j=0;?j<i-1;?j++?)?{ ???????????dist[j]?=?(r[0][j]?-?r[0][i])*(r[0][j]?-?r[0][i])?+?(r[1][j]?-?r[1][i])*(r[1][j]?-?r[1][i])?+?(r[2][j]?-?r[2][i])*(r[2][j]?-?r[2][i]); ??????} ??????for(?j=0;?j<i-1;?j++?)?{ ??????????????dist[j]?=?1.0?/?sqrt(dist[j]); ??????} ??????for(?j=0;?j<i-1;?j++?)?{ ??????????????pot?+=?dist[j]; ??????} ???} |
Intel編譯器提示，內(nèi)部的3個循環(huán)都進行了向量化。此時出現(xiàn)了令人驚喜的成績。程序的執(zhí)行時間突然降到了1.453秒。使用VTune進行分析，發(fā)現(xiàn)Intel編譯器對于開根號倒數(shù)的計算自動調(diào)用了內(nèi)部的向量化代碼庫。注意此時，還沒有使用Intel?Math?Kernel?Library，所以這個向量代碼庫是Intel編譯器內(nèi)置的，雖然效率沒有使用Intel?Math?Kernel?Library高，但是速度已經(jīng)提高了很多。調(diào)用Intel編譯器內(nèi)置的向量庫的結(jié)果如圖：
1.5?使用Intel?Math?Kernel?Library
Intel?Math?Kernel?Library中提供了一部分的向量函數(shù)(Vector?Mathematical?Functions)。這類函數(shù)提供了對于普通數(shù)學(xué)計算函數(shù)的快速的向量化計算。VML中有一個向量函數(shù)就是計算開根號倒數(shù)的。
Intel的VML庫中提供了如下函數(shù)來計算整個向量中各個數(shù)的開根號倒數(shù)：
vdInvSqrt(?n,?a,?y?)
其中n表示計算的元素個數(shù)。a是指向輸入計算數(shù)據(jù)數(shù)組的頭指針。y是指向輸出計算數(shù)據(jù)數(shù)組的頭指針。其中a和y可以相同。
要使用該函數(shù)，首先需要在頭文件中包含”mkl.h”，并且鏈接mkl_c.lib文件和libguide40.lib文件。
除了基本計算功能外，VML還提供了一個設(shè)置模式的函數(shù)，用于設(shè)置特定的計算模式：
vmlSetMode?(?mode?)
其中的mode是一個預(yù)定義宏。在我們的程序中，需要設(shè)置如下模式：
VML_LA：VML的所有向量函數(shù)都提供了2個精度的版本。精度低的版本計算速度也相對比較快。本程序只需要保留小數(shù)點后7位精度。低精度的版本符合要求，所以設(shè)定VML使用低精度的版本。
VML_DOUBLE_CONSISTENT：該選項用于控制FPU的計算精度為double，其實由于我們這次使用的函數(shù)基本上是使用SSE2指令集進行計算的，和FPU沒什么關(guān)系。但是也可能存在使用FPU的可能，所以設(shè)定VML使FPU的精度為double。
VML_ERRMODE_IGNORE：該選項用于關(guān)閉VML的錯誤處理功能，本程序不需要進行錯誤處理。
VML_NUM_THREADS_OMP_FIXED：VML函數(shù)都能使用OpenMP，根據(jù)特定的硬件環(huán)境進行并行化。而我們并不需要其進行并行化。所以使用該選項和前面提到的omp_set_num_threads(1)結(jié)合。關(guān)閉VML的自動并行化功能。
具體的代碼如下：
?
| ???for(?i=2;?i<NPARTS;?i++?)?{ ??????for(?j=0;?j<i-1;?j++?)?{ ???????????dist[j]?=?(r[0][j]?-?r[0][i])*(r[0][j]?-?r[0][i])?+?(r[1][j]?-?r[1][i])*(r[1][j]?-?r[1][i])?+?(r[2][j]?-?r[2][i])*(r[2][j]?-?r[2][i]); ??????} ????????vdInvSqrt(i-1,dist,dist); ??????for(?j=0;?j<i-1;?j++?)?{ ??????????????pot?+=?dist[j]; ??????} ???} |
優(yōu)化后出現(xiàn)了令人可惜可賀的成績：0.796秒。
1.6?根據(jù)Cache大小優(yōu)化Intel?Math?Kernel?Library調(diào)用
在上面的程序中對于MKL函數(shù)的調(diào)用是每次內(nèi)部循環(huán)都執(zhí)行一次調(diào)用，我們知道每次執(zhí)行函數(shù)的調(diào)用都是需要開銷的，那是否有更優(yōu)化的調(diào)用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的網(wǎng)站上：
從這段文字和這副圖片中，我們了解到對于MKL函數(shù)的調(diào)用時，所處理的向量不能太短，否則函數(shù)的建立時間開銷將是非常大的，也不能太長，操作了L2?Cache，否則函數(shù)執(zhí)行時訪問內(nèi)存的開銷是很大的。并且通過圖片了解到不合適的長度對于函數(shù)的性能將產(chǎn)生指數(shù)級影響。
根據(jù)理論計算：每次執(zhí)行computePot函數(shù)，總共需要執(zhí)行的計算量為(1+998)*998/2=498501個。每個double類型占用8個字節(jié)，所有總共需要占用的空間為498501*8=3988008byte=3894KB。而這次進行競賽的測試平臺的CPU的L2?Cache大小為2M，由于有2個線程同時計算，平均每個線程分到的L2?Cache為1M。由于L2?Cache可能還被其他數(shù)據(jù)占據(jù)。所以為了保證所計算的數(shù)據(jù)在L2?Cache中，最好每次計算的向量長度在512KB左右。故把整個computePot函數(shù)的計算量分成8份。每份計算量的中間結(jié)果向量長度為3894KB/8=486KB。
但是實際情況并非如此，進行這種優(yōu)化后，程序的執(zhí)行速度反而降低了。通過分析發(fā)現(xiàn)原來CPU中的L1?Cache大小為32KB。數(shù)組r有3000個元素，如果每次迭代都進行vdInvSqrt調(diào)用。那dist的長度為1000個元素左右。加起來正好可以全部在L1?Cache中。而如果合并起來調(diào)用vdInvSqrt，則由于vdInvSqrt過長。其L1?Cache中存放不下，需要存放在L2?Cache中，從而反而影響了速度。看來，對于本程序，不應(yīng)該根據(jù)L2?Cache進行優(yōu)化，而應(yīng)該根據(jù)L1?Cache進行優(yōu)化。但是對于只有幾個或者幾十個數(shù)據(jù)就調(diào)用MKL函數(shù)，其開銷還是很大的。因此本程序使用了折中的方法，對于前面非常小的幾十個數(shù)據(jù)，湊足1000個放在一起進行計算，而后面的數(shù)據(jù)還是按照原來的方式計算。具體實現(xiàn)的代碼如下：
?
| ???for(?i=2,k=0;?i<47;?i++?)?{ ??????for(?j=0;?j<i-1;?j++,k++?)?{ ?????????dist[k]?=?(r[0][j]?-?r[0][i])*(r[0][j]?-?r[0][i])?+?(r[1][j]?-?r[1][i])*(r[1][j]?-?r[1][i])?+?(r[2][j]?-?r[2][i])*(r[2][j]?-?r[2][i]); ??????} ???} ???vdInvSqrt(k,dist,dist); ???for(?j=0;?j<k;?j++?)?{ ??????pot?+=?dist[j]; ???} ???for(?i=47;?i<NPARTS;?i++?)?{ ??????for(?j=0;?j<i-1;?j++?)?{ ?????????dist[j]?=?(r[0][j]?-?r[0][i])*(r[0][j]?-?r[0][i])?+?(r[1][j]?-?r[1][i])*(r[1][j]?-?r[1][i])?+?(r[2][j]?-?r[2][i])*(r[2][j]?-?r[2][i]); ??????} ??????vdInvSqrt(i-1,dist,dist); ??????for(?j=0;?j<i-1;?j++?)?{ ?????????pot?+=?dist[j]; ??????} ???} |
通過該不優(yōu)化，程序的性能略微有所提高，達到了0.781秒。
1.7?優(yōu)化updatePositions函數(shù)
雖然updatePositions函數(shù)執(zhí)行的時間非常短。但還是值得優(yōu)化的。
首先進行的是基于數(shù)學(xué)的優(yōu)化。我們發(fā)現(xiàn)在updatePositions和initPositions中，都有加0.5的計算。但是從后面的computePot的相減計算中發(fā)現(xiàn)，這個0.5是被抵消的，既不加0.5對結(jié)果沒有影響。故去掉該加0.5的計算。另外updatePositions和initPositions中都有除以RAND_MAX的計算。而通過提取公因子的變換發(fā)現(xiàn)，如果此處不除以RAND_MAX而將最后的pot乘以RAND_MAX，則最后結(jié)果相同。故去掉該處的除以RAND_MAX的計算，而以在pot上一次乘以RAND_MAX為替換。具體代碼如下：
?
| void?initPositions()?{ ???int?i,?j; ? ???for(?i=0;?i<DIMS;?i++?) ??????for(?j=0;?j<NPARTS;?j++?) ?????????r[i][j]?=?(double)?rand(); } void?updatePositions()?{ ???int?i,?j; ? ???for(?i=0;?i<DIMS;?i++?) ??????for(?j=0;?j<NPARTS;?j++?) ?????????r[i][j]?-=?(double)?rand(); } 在main函數(shù)中： ??????pot?=?0.0; ??????computePot(); ??????pot*=(double)RAND_MAX; ??????if?(i%10?==?0)?printf("%5d:?Potential:?%20.7f/n",?i,?pot); ? |
其次需要進行updatePositions內(nèi)rand函數(shù)的優(yōu)化。雖然rand函數(shù)本身的執(zhí)行時間非常短，但是其頻繁得進行調(diào)用卻影響了性能。通過查找Microsoft?Visual?Studio?.NET?2005中提供的源代碼。將其中的rand函數(shù)提取出來，進行必要的修改，并且加上inline屬性。從而加快程序的調(diào)用速度。具體代碼如下：
?
| int?holdrand=1; inline?int?myrand?(){ ????????return(?((holdrand?=?holdrand?*?214013L+?2531011L)?>>?16)?&?0x7fff?); } ? |
經(jīng)過上述優(yōu)化，代碼的執(zhí)行速度已經(jīng)達到了0.765秒。
1.8?其他優(yōu)化以及性能分析
至此，該程序串行優(yōu)化部分已經(jīng)一本完成。但是還有一點細小的地方需要優(yōu)化。
變量對齊對于數(shù)據(jù)讀取速度是非常重要的。尤其是使用SIMD指令集進行優(yōu)化后，對于對齊的變量，可以使用對齊的讀寫指令提高速度。一般對于SIMD指令需要進行16字節(jié)對齊。但是對于本程序，由于后面要進行多線程優(yōu)化，而多線程執(zhí)行時基于Cache?Line的共享沖突會對讀寫造成很大的損失。故本程序使用64字節(jié)對齊。代碼如下：
?
| __declspec(align(64))?int?holdrand=1; __declspec(align(64))?double?r[DIMS][NPARTS]; __declspec(align(64))?double?pot; __declspec(align(64))?double?dist[1048]; |
在computePot函數(shù)的第一次迭代中。有一處進行pot累加的地方，使用了k變量作為循環(huán)條件。但是其實該變量的確切值是可以計算出來的。通過計算出該變量的確切值，可以讓Intel編譯器在編譯時就知道循環(huán)的次數(shù)，從而有助于優(yōu)化。具體代碼如下（注意1035這個值）：
?
| ???for(?i=2,k=0;?i<47;?i++?)?{ ??????for(?j=0;?j<i-1;?j++,k++?)?{ ?????????dist[k]?=?(r[0][j]?-?r[0][i])*(r[0][j]?-?r[0][i])?+?(r[1][j]?-?r[1][i])*(r[1][j]?-?r[1][i])?+?(r[2][j]?-?r[2][i])*(r[2][j]?-?r[2][i]); ??????} ???} ???vdInvSqrt(k,dist,dist); ???for(?j=0;?j<1035;?j++?)?{ ??????pot?+=?dist[j]; ???} |
此外再調(diào)整以下編譯器的某些優(yōu)化參數(shù)，選擇合適的使用。比如使用哪個編譯級別，是否打開全局優(yōu)化，使用IPO，使用GPO等。
至此本程序的串行優(yōu)化全部完成。使用Intel?VTune?Analyzers的分析結(jié)果為：
?
| Full?Name | CPI | Clockticks?events | Clockticks?% |
| void?updatePositions(void) | 3.214080375 | 8274621 | 0.287907869 |
| int?computePot(void) | 1.294881302 | 926757552 | 32.24568138 |
| mkl_vml_core_t7_vml_dInvSqrt_50 | 0.91981472 | 1925228486 | 66.9865643 |
（注：此分析數(shù)據(jù)是在奔騰D?820上測得）
從以上數(shù)據(jù)上表明updatePositions函數(shù)說執(zhí)行的事件非常短，低于1%，computePot函數(shù)的執(zhí)行時間在三分之一左右。mkl_vml_core_t7_vml_dInvSqrt_50的執(zhí)行時間在三分之二左右。這些數(shù)據(jù)對下面一步并行化采用的策略是非常重要的。
?
二、并行優(yōu)化
2.1?并行優(yōu)化概述
在進行本程序的并行優(yōu)化前先談?wù)劜⑿袃?yōu)化需要注意的問題。在并行優(yōu)化中經(jīng)常用到數(shù)據(jù)重復(fù)和計算重復(fù)的方法。所謂數(shù)據(jù)重復(fù)，就是為了保證多個線程能同時進行計算，就把數(shù)據(jù)復(fù)制多份來提高并行度。所謂計算重復(fù)，就是有時使用計算換通信的方法，提高并行度。
在對本程序進行優(yōu)化前需要注意的是。測試平臺使用的是基于Core?Microarchitecture結(jié)構(gòu)的。這個結(jié)構(gòu)的雙核CPU是共享L2?Cache的。但是當(dāng)數(shù)據(jù)在一個核中進行修改，另外一個核去讀他時，需要消耗幾十個時鐘周期的延遲。其代價的非常高的。這里需要注意的是，數(shù)據(jù)在Cache中是按行進行存放的，也就是說，CPU看待數(shù)據(jù)有沒有被修改過是根據(jù)Cache?Line的。所以2個分別被不同的核修改的數(shù)據(jù)如果存在于同一行Cache中，訪問時的效率就會非常低。也就是發(fā)生了共享沖突。所以在分配變量時要盡量把不同性質(zhì)的變量分配到不同的Cache?Line中。我們的測試平臺的L1?Cache和L2?Cache都是每行64byte的。所以前一章中的變量對齊都使用了64byte對齊。同樣，在程序并行化時也需要考慮這種情況。
2.2?優(yōu)化方案一
此方案使用數(shù)據(jù)重復(fù)的方法。程序可以定義2個r數(shù)組。以及2個pot數(shù)組。通過定義2個r數(shù)組，使得主線程可以在從線程使用一個r數(shù)組計算時同時更新第二個r數(shù)組。即主線程先更新r數(shù)組，然后主線程和從線程同時開始計算。但是從線程的計算量比主線程大一點。這樣當(dāng)主線程計算完后，可以繼續(xù)更新第二個r數(shù)組，而此時從線程還在計算原來r數(shù)組的內(nèi)容。當(dāng)主線程更新完第二個r數(shù)組時，從線程正好完成前面的計算，并和主線程一同計算第二個r數(shù)組，依次類推。同時2個pot數(shù)組，一個給主線程計算每步的中間結(jié)果，另一個給從線程計算每步的中間結(jié)果。等計算結(jié)束后，再將其結(jié)果相加，打印。
優(yōu)點：使用該方法的優(yōu)點是顯而易見的，理論上線程可以做到完全同步。
缺點：使用該方法的缺點是，從線程每次計算需要從主線程計算好的r數(shù)組中讀取內(nèi)容，由于是2個核，所以其訪問延遲非常大。此外使用2個數(shù)值，每次迭代都需要將指針指向使用的數(shù)組，增加了程序的設(shè)計難度。同時計算任務(wù)分配的調(diào)優(yōu)也是非常繁瑣的。
由于在前一章中，我們發(fā)現(xiàn)updatePositions函數(shù)所花費的時間非常短。所以做到線程間的完全平衡意義并不大。
2.3?優(yōu)化方案二
在前一個方案中，我們提到了線程的完全平衡的算法。同時我們發(fā)現(xiàn)完全平衡的意義不大。因此我們設(shè)計適合本程序的更優(yōu)的方案。既然updatePositions函數(shù)所花費的時間非常短。那2個線程同時執(zhí)行updatePositions造成的額外開銷也是可以忽略的。本方案使用了數(shù)據(jù)重復(fù)和計算重復(fù)的方法。同樣使用2個r數(shù)組，但是2個線程同時進行重復(fù)計算，并且2個線程分區(qū)完成不同的迭代步驟的computePot計算。即主線程完成整個r數(shù)組的更新，但是只計算其中的奇數(shù)次迭代。從線程同樣完成整個r數(shù)組的更新，但是只進行偶數(shù)次迭代。并且同樣使用了一個pot數(shù)組，2個線程分別將自己的計算結(jié)果先存儲到pot數(shù)組中。等最后同步的時候再打印。
優(yōu)點：使用該方案，程序的設(shè)計相對來說比較簡單，負載均衡的調(diào)整也很容易。程序只需要很少的同步操作（在本程序中，只使用了2次同步）。并且重要的是。由于2個線程都在各自的CPU上使用各自的數(shù)據(jù)進行計算，所以最大化得避免了共享沖突的發(fā)生。同時也保留了前一章優(yōu)化中針對L1?Cache的命中率。
缺點：該方案的缺點是存在重復(fù)計算。但是通過前面VTune的測試，已經(jīng)發(fā)現(xiàn)其重復(fù)計算量非常小，可以忽略。
2.4?并行實現(xiàn)
本程序使用方案二進行并行化。首先將所有需要計算的數(shù)據(jù)和函數(shù)都復(fù)制2份，代碼如下：
?
| int?computePot1(void); void?initPositions1(void); void?updatePositions1(void); int?computePot2(void); void?initPositions2(void); void?updatePositions2(void); __declspec(align(64))?int?holdrand1=1; __declspec(align(64))?double?r1[DIMS][NPARTS]; __declspec(align(64))?double?pot1; __declspec(align(64))?double?dist1[1048]; __declspec(align(64))?int?holdrand2=1; __declspec(align(64))?double?r2[DIMS][NPARTS]; __declspec(align(64))?double?pot2; __declspec(align(64))?double?dist2[1048]; __declspec(align(64))?double?potfinal[264]; ? |
其中的potfinal數(shù)組記錄每次迭代的計算結(jié)果，用于最后的數(shù)組。
在主函數(shù)的并行中。我們發(fā)現(xiàn)由于偶數(shù)次迭代比奇數(shù)次迭代需要多算一次。故本程序的偶數(shù)次迭代在進行到快完成前先釋放一個同步鎖。使得主線程可以先輸出一部分數(shù)據(jù)。而從線程在執(zhí)行完所有的偶數(shù)次迭代后再釋放一個同步鎖，使主線程輸出剩余的數(shù)據(jù)。由于輸出數(shù)據(jù)也有一點的耗時。所以使用這種方法可以提高一點并行度。另外在本代碼中使用了SetThreadAffinityMask分別設(shè)置不同的線程對應(yīng)各自的CPU，以防止線程在不同的CPU中切換從而影響L1?Cache命中率。具體代碼如下：
?
| DWORD?WINAPI?mythread(?void?*myarg?){ ?????int?i; ?????SetThreadAffinityMask(GetCurrentThread(),?2); ?????initPositions2(); ?????updatePositions2(); ?????for(i=0;i<=190;i+=2){ ????????pot2?=?0.0; ????????computePot2(); ????????pot2*=(double)RAND_MAX; ????????potfinal[i]=pot2; ????????updatePositions2(); ????????updatePositions2(); ?????} ?????ReleaseSemaphore(semmiddle,?1,?NULL); ?????for(i=192;i<=NITER;i+=2){ ????????pot2?=?0.0; ????????computePot2(); ????????pot2*=(double)RAND_MAX; ????????potfinal[i]=pot2; ????????updatePositions2(); ???????updatePositions2(); ?????} ?????ReleaseSemaphore(semafter,?1,?NULL); ?????return?0; }//從線程 |
?
| int?main()?{ ???int?i; ???int?myarg=0; ???clock_t?start,?stop; ???omp_set_num_threads(1); ???vmlSetMode(VML_LA); ???vmlSetMode(VML_DOUBLE_CONSISTENT); ???vmlSetMode(VML_ERRMODE_IGNORE); ???vmlSetMode(VML_NUM_THREADS_OMP_FIXED); ???semmiddle?=?CreateSemaphore(NULL,?0,?1,?NULL); ???semafter?=?CreateSemaphore(NULL,?0,?1,?NULL); ???CreateThread(0,?8*1024,?mythread,?(void?*)&myarg,?0,?NULL); ???SetThreadAffinityMask(GetCurrentThread(),?1); ???initPositions1(); ???start=clock(); ???for(i=1;i<NITER;i+=2){ ????????pot1?=?0.0; ????????updatePositions1(); ????????updatePositions1(); ????????computePot1(); ????????pot1*=(double)RAND_MAX; ????????potfinal[i]=pot1; ???} ???WaitForSingleObject(semmiddle,?INFINITE); ???for(i=0;i<=190;i+=10) ????????printf("%5d:?Potential:?%20.7f/n",?i,?potfinal[i]); ???WaitForSingleObject(semafter?,?INFINITE); ???i=200; ???printf("%5d:?Potential:?%20.7f/n",?i,?potfinal[i]); ???stop=clock(); ???printf?("Seconds?=?%10.9f/n",(double)(stop-start)/?CLOCKS_PER_SEC); }//主線程 |
2.5?性能分析
并行化后的性能并不沒有像理論中這么高只有0.437秒。于是我們開始查找原因。通過使用Intel?Threading?Checker我們發(fā)現(xiàn)，VML庫中存在著訪問沖突。圖片如下：
?
當(dāng)然這個錯誤有可能是Intel?Threading?Checker的誤報。因為程序每次執(zhí)行都沒有發(fā)現(xiàn)不正確的結(jié)果，并且VML函數(shù)的文檔上說明是線程安全性的。
由于兼容性原因，本系統(tǒng)無法使用Intel?VTune?Analyzers進行每個函數(shù)的耗時分析。于是使用Intel編譯器提供的內(nèi)置函數(shù)_rdtsc()記錄不同部分所花費的CPU時鐘周期。結(jié)果發(fā)現(xiàn)VML函數(shù)的總執(zhí)行時間大概增加了0.088秒左右。說明VML函數(shù)在用戶使用Windows?Thread函數(shù)并行化訪問時，其同步開銷可能有一定的影響。
?
三、匯編級優(yōu)化
3.1?優(yōu)化目標(biāo)
本程序主要的執(zhí)行時間在computePot函數(shù)與VML庫中。對于computePot函數(shù)，通過查看Intel編譯器產(chǎn)生的匯編碼發(fā)現(xiàn)其已經(jīng)很優(yōu)了。而對于VML函數(shù)由于其需要滿足通用性，所以本程序應(yīng)該可以設(shè)計出最適合本程序的計算函數(shù)來。
3.2?數(shù)學(xué)理論
Intel的CPU支持的SSE2指令中，有2條是用于計算雙精度浮點的開根號倒數(shù)的。sqrtpd指令可以同時計算2個double型的開根號，其吞吐率為28個時鐘周期。divpd指令用于計算2個數(shù)的除法，即用于計算倒數(shù)，其吞出率為17個時鐘周期。由此可以計算出，如果當(dāng)當(dāng)使用這2條指令計算雙精度數(shù)的開根號倒數(shù)，那即使使用匯編語言，忽略其他開銷。計算每個元素的時鐘周期也有(17+28)/2=22.5。而Intel的VML庫計算每個元素的只需要10多個時鐘周期，說明其肯定是通過其他快速的數(shù)學(xué)計算方法得到的。所以要優(yōu)化vdInvSqrt函數(shù)，關(guān)鍵是找到更快速的數(shù)學(xué)計算方法。在Quake?3在源代碼中有如下一段具有傳奇色彩的代碼：
?
| float?InvSqrt(float?x){ ???????float?xhalf?=?0.5f*x; ???????int?i?=?*(int*)&x;?//?get?bits?for?floating?value ???????i?=?0x5f3759df?-?(i>>1);?//?gives?initial?guess?y0 ???????x?=?*(float*)&i;?//?convert?bits?back?to?float ???????x?=?x*(1.5f-xhalf*x*x);?//?Newton?step,?repeating?increases?accuracy ???????return?x; } |
（注：以上代碼的注釋摘自CHRIS?LOMONT的《FAST?INVERSE?SQUARE?ROOT》文章中）
在上面的代碼中最后一條是典型的牛頓迭代，可以根據(jù)精度要求進行多次迭代。這段代碼神奇的地方在于初始值的估算上，只用了減法和移位2個簡單的操作，達到了非常接近的估算值。我們稱0x5f3759df為幻數(shù)(magic?number)。CHRIS?LOMONT在他的《FAST?INVERSE?SQUARE?ROOT》文章中給出了對于這個幻數(shù)的解釋和計算方法。并且計算出了理論上最優(yōu)的適用于double類型的幻數(shù)為0x5fe6ec85e7de30da。說們我們的代碼中可以使用該方法進行計算，示例代碼如下：
?
| double?myinvsqrt?(double?x) { ?????double?xhalf?=?0.5*x; ?????__int64?i?=?*(__int64*)&x; ?????i?=?0x5fe6ec85e7de30da?-?(i>>1); ?????x?=?*(double*)&i; ?????x?=?x*(1.5-xhalf*x*x); ?????x?=?x*(1.5-xhalf*x*x); ?????x?=?x*(1.5-xhalf*x*x); ?????x?=?x*(1.5-xhalf*x*x); ?????return?x; } |
但是不幸的是，根據(jù)調(diào)試，需要達到比賽要求的小數(shù)點后7位精度，必需進行4此牛頓迭代也行。而4此牛頓迭代的計算量使得這個方法對于Intel的VML函數(shù)來說毫無優(yōu)勢可言。那能否降低牛頓迭代的次數(shù)那？
我們發(fā)現(xiàn)如果以上代碼只進行3次牛頓迭代，那誤差只有小數(shù)點最后的1，2位。CHRIS?LOMONT在他的文中提到他說計算出來的理論最優(yōu)值，而這個幻數(shù)只是在線性估計時是最優(yōu)的。在多次牛頓迭代中，這個值并不是最優(yōu)的。CHRIS?LOMONT并沒有給出對于多次牛頓迭代最優(yōu)幻數(shù)的計算方法，他在文章中對于float類型的實際最優(yōu)值也是窮舉得到的。我們同樣在理論最優(yōu)值0x5fe6ec85e7de30da的基礎(chǔ)上進行了一定的窮舉操作，發(fā)現(xiàn)的確有更優(yōu)的幻數(shù)。但是即使使用了更優(yōu)的幻數(shù)，還是無法在3次牛頓迭代基礎(chǔ)上達到精度要求。但是我們發(fā)現(xiàn)所有的數(shù)值都偏小。于是我們可以在三次牛頓迭代后再乘一個比1大一點點的偏移量。從而能做到3次牛頓迭代就能達到精度要求。示例代碼如下：
?
| double?myinvsqrt?(double?x) { ?????double?xhalf?=?0.5*x; ?????__int64?i?=?*(__int64*)&x; ?????i?=?newmagicnum?-?(i>>1); ?????x?=?*(double*)&i; ?????x?=?x*(1.5-xhalf*x*x); ?????x?=?x*(1.5-xhalf*x*x); ?????x?=?x*(1.5-xhalf*x*x); ?????x?=?x*offset ?????return?x; } |
由于時間原因，這里并沒有對newmagicnum和offset進行詳細的計算與統(tǒng)計。只給出一個對于本程序相對較優(yōu)的newmagicnum值0x5fe6d250b0000000。
在上面的代碼中只進行了3次牛頓迭代。對于Intel的VML來說也沒有什么優(yōu)勢可言。那能不能再減少一次牛頓迭代，只進行2次迭代就達到精度要求那？
我們知道要進行2次牛頓迭代就達到精度要求就必須對其初始值的估計更加準確。而使用上面的方法估計的初始值已經(jīng)無法滿足該準確性。這是通過查找《Intel?64?and?IA-32?Architectures?Optimization?Reference?Manual》，我們發(fā)現(xiàn)SSE指令集中有一條RSQRTPS的指令用于同時計算四個單精度浮點數(shù)的開根號倒數(shù)，而其在Core?Microarchitecture上的延遲為3個周期，吞吐率為2個周期。也就是說我們可以在極短的時間內(nèi)就算出單精度類型的開根號倒數(shù)值（看來在現(xiàn)在的CPU上，當(dāng)初Quake?3那段具有傳奇色彩的代碼已經(jīng)沒有用了）。于是我們想到了先使用單精度類型精度初值估算，然后再使用牛頓迭代。實驗結(jié)果表明該方法只需要進行2次牛頓迭代就能滿足小數(shù)點后7位的精度要求。示例代碼如下：
?
| double?myinvsqrt?(double?x) { ?????double?xhalf?=?0.5*x; ?????float?xf=(float)x; ?????__asm{ ?????????movss?xmm1,xf; ?????????rsqrtss?xmm1,xmm1; ?????????movss?xf,xmm1; ?????} ?????x=(double)xf; ?????x?=?x*(1.5-xhalf*x*x); ?????x?=?x*(1.5-xhalf*x*x); ?????return?x; } |
不幸的是由于該代碼涉及到了復(fù)雜的算法以及類型轉(zhuǎn)換，Intel的編譯器并無法將其很好的并行化。所以只有依靠手工使用匯編語言將其優(yōu)化。
3.3?匯編碼實現(xiàn)
在實現(xiàn)匯編碼前先要將原來的代碼進行優(yōu)化，將牛頓迭代中的減法變成加法，代碼如下：
?
| double?myinvsqrt?(double?x) { ?????double?xhalf?=?-0.5*x; ?????float?xf=(float)x; ?????__asm{ ?????????movss?xmm1,xf; ?????????rsqrtss?xmm1,xmm1; ?????????movss?xf,xmm1; ?????} ?????x=(double)xf; ?????x?=?x*(1.5+xhalf*x*x); ?????x?=?x*(1.5+xhalf*x*x); ?????return?x; } |
進行這種轉(zhuǎn)變是一點都不影響計算結(jié)果的。但是確可以提高計算速度。這是因為，如果執(zhí)行的是減法，匯編語言的減法指令會將結(jié)果存在原來存放被減數(shù)（即1.5）的寄存器中。從而覆蓋掉了原來的常數(shù)1.5，使得每次計算必須重新讀入該參數(shù)。而優(yōu)化成加法后則沒有這個問題。
下面列出了本次匯編語言優(yōu)化時使用的主要的匯編指令及其延遲，吞吐率和使用的計算部件。這些數(shù)據(jù)對優(yōu)化匯編代碼有幫助。
| 指令名 | 延遲 | 吞吐率 | 計算部件 |
| movapd | 1 | 0.33 | FP_MOVE |
| cvtpd2ps | 4 | 1 | FP_ADD,MMX_SHFT |
| cvtps2pd | 2 | 2 | FP_ADD,MMX_SHFT,MMX_ALU |
| shufps | 2 | 1 | MMX_SHFT |
| rsqrtps | 3 | 2 | MMX_MISC |
| mulpd | 5 | 1 | FP_MUL |
| addpd | 3 | 1 | FP_ADD |
（注：以上數(shù)據(jù)摘自《Intel?64?and?IA-32?Architectures?Optimization?Reference?Manual》）
在進行優(yōu)化前，還有一點需要注意的是。rsqrtps函數(shù)是4個元素一算的，所以本程序使用4個元素作為一次計算單元來向量化。而用戶輸入的數(shù)據(jù)并不可能是正好4個元素。對于Intel編譯器以及VML函數(shù)庫來所，其使用的解決方法稱為”?Strip-mining?and?Cleanup”。即先按照4個數(shù)據(jù)一組進行計算。對于剩下的個別數(shù)據(jù)再進行單獨計算。這對于通用化的程序來說是必須的。但是在我們的程序中，多計算幾個并不會影響結(jié)果。而對于單獨幾個的數(shù)據(jù)如果另外處理不但會增加程序設(shè)計的復(fù)雜性，而且性能也可能會降低。所以本程序使用過渡計算的方法。即對于需要計算的數(shù)據(jù)中不足4個的，補滿4個將其后面的數(shù)據(jù)計算掉。但是此時需要注意，由于dist變量是全局變量，默認的值為全0。如果過渡計算遇到0的值，速度可能會受到影響。所以本程序需要在一開始，將會被過渡計算使用到，但是從來不會被初始化的存儲單元，初始化成1。具體代碼如下：
?
| void?myinvsqrt?(double?*start,double?*end) { ?????__asm{ ?????????mov?esi,start; ?????????mov?edi,end; ?????????test?edi,0x0000001f; ?????????jz?myalign; ?????????and?edi,0xffffffe0; ?????????add?edi,32; myalign: myagain: ?????????movapd?xmm0,[esi]; ?????????movapd?xmm3,[esi+16]; ?????????cvtpd2ps?xmm6,xmm0; ?????????cvtpd2ps?xmm7,xmm3; ?????????shufps?xmm6,xmm7,01000100b; ?????????rsqrtps?xmm6,xmm6; ?????????cvtps2pd?xmm1,xmm6; ?????????shufps?xmm6,xmm6,01001110b; ?????????cvtps2pd?xmm4,xmm6; ?????????mulpd?xmm0,mulcc; ?????????mulpd?xmm3,mulcc; ? ?????????movapd?xmm2,xmm1; ?????????movapd?xmm5,xmm4; ?????????mulpd?xmm1,xmm1; ?????????mulpd?xmm4,xmm4; ?????????mulpd?xmm1,xmm0; ?????????mulpd?xmm4,xmm3; ?????????addpd?xmm1,addcc; ?????????addpd?xmm4,addcc; ?????????mulpd?xmm1,xmm2; ?????????mulpd?xmm4,xmm5;//前半段 |
?
?
| ?????????movapd?xmm2,xmm1; ?????????movapd?xmm5,xmm4; ?????????mulpd?xmm1,xmm1; ?????????mulpd?xmm4,xmm4; ?????????mulpd?xmm1,xmm0; ?????????mulpd?xmm4,xmm3; ?????????addpd?xmm1,addcc; ?????????addpd?xmm4,addcc; ?????????mulpd?xmm1,xmm2; ?????????mulpd?xmm4,xmm5; ?????????movapd?[esi],xmm1; ?????????movapd?[esi+16],xmm4; ? ?????????add?esi,32; ?????????cmp?esi,edi; ?????????jne?myagain; ?????} } //后半段 ? myinvsqrt(dist1,dist1+k);?//調(diào)用方法 |
對于本函數(shù)的調(diào)用方法為分別傳入其需要計算數(shù)據(jù)的頭指針和尾指針。
3.4?性能分析
使用匯編語言優(yōu)化后，程序跑出了驚人的0.312秒的好成績。并且所有的輸出數(shù)據(jù)全部都滿足小數(shù)點后7位的精度要求。在使用Intel?Threading?Checker和Intel?Threading?Profiler分析程序時也得到了相對比較好的結(jié)果。如下圖：
?
在Intel?Threading?Checker的檢測中，沒有發(fā)現(xiàn)程序有任何沖突。在使用Intel?Threading?Profiler的分析中，表現(xiàn)出了程序良好的并行性。
最后，在另外一臺Intel酷睿2?E6600的機器上測試時，程序達到了0.25秒的好成績，并且所有數(shù)據(jù)輸出精度都達到了小數(shù)點后7位。
3.5?總結(jié)
在本次優(yōu)化比賽中。我花了幾個星期仔細鉆研Intel的工具使用方法，并且結(jié)合Intel的CPU特性對源代碼進行優(yōu)化。在經(jīng)過了漫長的調(diào)優(yōu)后，終于在保留小數(shù)點后7位精度的七位精度的情況下達到了0.25秒的成績。這里需要說明的是，在本程序的最后優(yōu)化時雖然沒有使用Intel的VML庫，但并不是意味著VML庫不好。VML庫的通用化和高效率是有目共睹的。而是由于VML庫是通用庫，其需要考慮很多情況，而針對本程序自己設(shè)計的計算函數(shù)卻不用考慮各自情況。所以設(shè)計有針對性的函數(shù)才能提高速度。當(dāng)然要設(shè)計這種函數(shù)對用戶的要求太高，需要了解數(shù)學(xué)理論，匯編語言，以及優(yōu)化的方法。所以對于一般的用戶還是使用VML庫比較好。
最后需要說明的是，由于本次競賽的時間有限。很多地方都沒有得到更好的優(yōu)化。比如那段匯編語言就能針對Intel?CPU的指令延遲特性進一步優(yōu)化。如果大賽能給出更多的時間，那有可能可以優(yōu)化得更好。
?
?
附錄A?目錄結(jié)構(gòu)和編譯方法
本報告壓縮文件的根目錄下分別有version1，version2，version3三個目錄，分別對應(yīng)第一，第二，第三章中的，串行優(yōu)化，并行優(yōu)化，匯編優(yōu)化三個不同階段的版本。其中version3是最終版。
在每個version目錄下，有Microsoft?Visual?Studio的項目文件，可以使用Microsoft?Visual?Studio直接打開。在對應(yīng)的Release目錄下有已經(jīng)編譯好的可執(zhí)行文件。程序的優(yōu)化選項可以在Microsoft?Visual?Studio中看到，具體的解釋可以在第一章中查找。
此外，在壓縮文件的根目錄下有最終板的可執(zhí)行文件potential_serial(final).exe方便進行測試。
?
附錄B?參考文獻
Intel?C++?Compiler?Documentation
Intel?MKL?Reference?Manual
Intel?MKL?Technical?User?Notes
Getting?Started?Guide?for?Intel?MKL
Getting?Started?with?the?VTune?Performance?Analyzer
VTune?Performance?Environment?Help
Intel?Thread?Profiler?for?Windows
Intel?Thread?Checker?for?Windows
Intel?64?and?IA-32?Architectures?Software?Developer’s?Manual?Volume?1?Basic?Architecture
Intel?64?and?IA-32?Architectures?Software?Developer’s?Manual?Volume?2A?Instruction?Set?Reference,?A-M
Intel?64?and?IA-32?Architectures?Software?Developer’s?Manual?Volume?2B?Instruction?Set?Reference,?N-Z
Intel?64?and?IA-32?Architectures?Software?Developer’s?Manual?Volume?3A?System?Programming?Guide
Intel?64?and?IA-32?Architectures?Software?Developer’s?Manual?Volume?3B?System?Programming?Guide
Intel?64?and?IA-32?Architectures?Optimization?Reference?Manual
Using?Spin-Loops?on?Intel?Pentium?4?Processor?and?Intel?Xeon?Processor
FAST?INVERSE?SQUARE?ROOT????CHRIS?LOMONT
總結(jié)
以上是生活随笔為你收集整理的英特尔多核平台编程优化大赛报告的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 预编码的基本原理
- 下一篇： 使用ESP32读取数字硅麦的数据