南開大學(xué) 并行程序設(shè)計 高斯消去法sse并行化

1、一 、請同學(xué)們在下列題目中任選一題，寫成期末論文。（一）并行算法研究類對某一問題，研究其并行算法的設(shè)計、實現(xiàn)，分析其性能，進行實驗驗證，撰寫研究論文。例如：1、對矩陣相乘問題，設(shè)計 pthread 多線程結(jié)合 SSE/AVX 的兩層并行算法，實現(xiàn)并行程序。討論算法層面不同策略對性能的影響，例如多個線程間不同的任務(wù)分配方式、不同的線程同步策略等，討論不同并行編程方法對性能的影響，例如 SSE/AVX的對齊和不對齊內(nèi)存訪問等等。對不同的矩陣

2、規(guī)模、不同的線程數(shù)測試程序性能，撰寫研究論文。2、對高斯消去法問題（其串行算法偽代碼示意如下面算法 1 所示），設(shè)計pthread 多線程結(jié)合 SSE/AVX 的兩層并行算法，實現(xiàn)并行程序。討論算法層面不同策略對性能的影響，例如多個線程間不同的任務(wù)分配方式、不同的線程同步策略等，討論不同并行編程方法對性能的影響，例如 SSE/AVX 的對齊和不對齊內(nèi)存訪問等等。對不同的矩陣規(guī)模、不同的線程數(shù)測試程序性能，撰寫研究論文。3、其他類似難度的

3、問題。（二）并行編程工具調(diào)研類對某種并行編程工具進行調(diào)研，選取某個問題（例如矩陣相乘問題），用這種編程工具編寫并行程序求解這個問題，進行實驗驗證，撰寫研究論文介紹這種并行編程工具的特色、基本編程（使用）方法、如何用它解決實際問題（以你選定的問題為例）。例如：1、C++、Java 等語言本身對并行編程提供的支持。2、Hadoop MapReduce 編程工具。3、其它并行編程工具。二、論文寫作要求（一）并行算法研究類1、論文應(yīng)詳細描述清楚

4、所研究的問題，并行算法的設(shè)計。2、鼓勵大家選擇課堂教學(xué)之外的問題，通過文獻調(diào)研，研究其并行求解方法，甚至有自己提出新的方法。3、最好能有求解一個問題的多種并行算法之間的對比分析。（二）并行編程工具調(diào)研類1、應(yīng)調(diào)研較新的工具，避免調(diào)研太“古老”的工具。2、不能只是工具相關(guān)資料的調(diào)研和文字的匯總、整理，重點仍是并行編程——用調(diào)研的工具編程解決一個具體問題。3、鼓勵大家進行不同并行編程工具間的對比，例如調(diào)研的工具與課堂講授的工具之間的對比。{

5、float tmp2 = matrix[i][k];for (int j = k + 1; j < N; j++){matrix[i][j] = matrix[i][j] - tmp2 * matrix[k][j];}matrix[i][k] = 0;}}return matrix;}這其中，內(nèi)嵌的第一個 for 循環(huán)的作用是把第 k 行的所有元素除以第一個非零元素，目的是第一個非零元為 1。而第二個內(nèi)嵌的 for 循環(huán)（當(dāng)然其中

6、還內(nèi)嵌了一個小的 for 循環(huán)）作用是從 k+1 行開始減去第 k 行乘以這一行行的第一個非零元，使得 k+1 行的第 k 列為 0。二、SSE/AVX 介紹ntel ICC 和開源的 GCC 編譯器支持的 SSE/AVX 指令的 C 接口聲明在 xmmintrin.h 和pmmintrin.h 頭文件中。其數(shù)據(jù)類型命名主要有__m128/__m256、__m128d/__m256i，默認為單精度（d 表示雙精度，i 表示整型）。其函

7、數(shù)的命名可大致分為 3 個使用“_”隔開的部分，3 個部分的含義如下。第一個部分為_mm 或_mm256。_mm 表示其為 SSE 指令，操作的向量長度為 64 位或128 位。_mm256 表示 AVX 指令，操作的向量長度為 256 位。本節(jié)只介紹 128 位的 SSE 指令和 256 位的 AVX 指令。第二個部分為操作函數(shù)名稱，如_add、_load、mul 等，一些函數(shù)操作會增加修飾符，如 loadu 表示不對齊到向量長度的存

8、儲器訪問。第三個部分為操作的對象名及數(shù)據(jù)類型，_ps 表示操作向量中所有的單精度數(shù)據(jù)；_pd表示操作向量中所有的雙精度數(shù)據(jù)；_pixx 表示操作向量中所有的 xx 位的有符號整型數(shù)據(jù)，向量寄存器長度為 64 位；_epixx 表示操作向量中所有的 xx 位的有符號整型數(shù)據(jù)，向量寄存器長度為 128 位；_epuxx 表示操作向量中所有的 xx 位的無符號整型數(shù)據(jù)，向量寄存器長度為 128 位；_ss 表示只操作向量中第一個單精度數(shù)據(jù)；s

9、i128 表示操作向量寄存器中的第一個 128 位有符號整型。3 個部分組合起來，就形成了一條向量函數(shù)，如_mm256_add_ps 表示使用 256 位向量寄存器執(zhí)行單精度浮點加法運算。由于使用指令級數(shù)據(jù)并行，因此其粒度非常小，需要使用細粒度的并行算法設(shè)計。SSE/AVX 指令集對分支的處理能力非常差，而從向量中抽取某些元素數(shù)據(jù)的代價又非常大，因此不適合含有復(fù)雜邏輯的運算?，F(xiàn)在對于接下來代碼中要用到的幾個 SSE 指令加以介紹：_mm

10、_loadu_ps 用于 packed 的加載（下面的都是用于 packed 的），不要求地址是 16字節(jié)對齊，對應(yīng)指令為 movups。_mm_sub_ps(__m128_A,__m128_B);返回一個__m128 的寄存器，僅將寄存器_A 和寄存器_B 最低對應(yīng)位置的 32bit 單精度浮點數(shù)相乘，其余位置取寄存器_A 中的數(shù)據(jù),例如_A=(_A0,_A1,_A2,_A3),_B=(_B0,_B1,_B2,_B3),則返回寄存器為