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

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

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

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

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

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)嵌的第一個(gè) for 循環(huán)的作用是把第 k 行的所有元素除以第一個(gè)非零元素，目的是第一個(gè)非零元為 1。而第二個(gè)內(nèi)嵌的 for 循環(huán)（當(dāng)然其中

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

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

8、儲(chǔ)器訪問(wèn)。第三個(gè)部分為操作的對(duì)象名及數(shù)據(jù)類(lèi)型，_ps 表示操作向量中所有的單精度數(shù)據(jù)；_pd表示操作向量中所有的雙精度數(shù)據(jù)；_pixx 表示操作向量中所有的 xx 位的有符號(hào)整型數(shù)據(jù)，向量寄存器長(zhǎng)度為 64 位；_epixx 表示操作向量中所有的 xx 位的有符號(hào)整型數(shù)據(jù)，向量寄存器長(zhǎng)度為 128 位；_epuxx 表示操作向量中所有的 xx 位的無(wú)符號(hào)整型數(shù)據(jù)，向量寄存器長(zhǎng)度為 128 位；_ss 表示只操作向量中第一個(gè)單精度數(shù)據(jù)；s

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

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