并行計算課程報告

并行計算與多核多線程技術(shù)課程報告專業(yè) _班級 _學(xué)號 _姓名 _成績 _年 月 日課程報告要求手寫內(nèi)容：設(shè)計目的、意義，設(shè)計分析，方案分析，功能模塊實現(xiàn)，最終結(jié)果分析，設(shè)計體會等。允許打印內(nèi)容：設(shè)計原理圖等圖形、圖片，電路圖，源程序。硬件類的設(shè)計，要有最終設(shè)計的照片圖；軟件類設(shè)計，要有各個功能模塊實現(xiàn)的界面圖、輸入輸出界面圖等。評 價理論基礎(chǔ)實踐效果（正確度/加速比）難度工作量獨(dú)立性班級_ 學(xué)號_ 姓名_ 算法名稱_目 錄1. 設(shè)計目的、意義（功能描述） .12. 方案分析（解決方案） .13. 設(shè)計分析 .13.1 串行算法設(shè)計 .13.2 并行算法設(shè)計 .13.3 理論加速比分析 .24. 功能模塊實現(xiàn)與最終結(jié)果分析 .24.1 基于 OpenMP 的并行算法實現(xiàn) .24.1.1 主要功能模塊與實現(xiàn)方法 .24.1.2 實驗加速比分析 .24.2 基于 MPI 的并行算法實現(xiàn) .24.2.1 主要功能模塊與實現(xiàn)方法 .24.2.2 實驗加速比分析 .24.3 基于 Java 的并行算法實現(xiàn) .34.3.1 主要功能模塊與實現(xiàn)方法 .34.3.2 實驗加速比分析 .34.4 基于 Windows API 的并行算法實現(xiàn) .34.4.1 主要功能模塊與實現(xiàn)方法 .34.4.2 實驗加速比分析 .34.5 基于.net 的并行算法實現(xiàn) .34.5.1 主要功能模塊與實現(xiàn)方法 .34.5.2 實驗加速比分析 .34.6 基于 Linux 的并行算法實現(xiàn)（選作） .44.6.1 主要功能模塊與實現(xiàn)方法 .44.6.2 實驗加速比分析 .44.7 基于 Hadoop/MapReduce 的并行算法實現(xiàn)（選作） .44.7.1 主要功能模塊與實現(xiàn)方法 .44.7.2 實驗加速比分析 .44.8 并行計算技術(shù)在實際系統(tǒng)中的應(yīng)用 .44.8.1 主要功能模塊與實現(xiàn)方法 .44.8.2 實驗加速比分析 .55. 設(shè)計體會 .5班級_ 學(xué)號_ 姓名_ 算法名稱_6. 附錄 .66.1 基于 MPI 的并行程序設(shè)計 .66.1.1 代碼及注釋 .66.1.2 執(zhí)行結(jié)果截圖 .66.1.3 遇到的問題及解決方案 .66.2 基于 MPI 的并行程序設(shè)計 .76.1.1 代碼及注釋 .76.2.2 執(zhí)行結(jié)果截圖 .76.2.3 遇到的問題及解決方案 .76.3 基于 Java 的并行程序設(shè)計 .86.3.1 代碼及注釋 .86.3.2 執(zhí)行結(jié)果截圖 .86.3.3 遇到的問題及解決方案 .96.4 基于 Windows API 的并行程序設(shè)計 .96.4.1 代碼及注釋 .96.4.2 執(zhí)行結(jié)果截圖 .106.4.3 遇到的問題及解決方案 .106.5 基于.net 的并行程序設(shè)計 .116.5.1 代碼及注釋 .116.5.2 執(zhí)行結(jié)果截圖 .116.5.3 遇到的問題及解決方案 .116.6 基于 Linux 的并行程序設(shè)計（選作） .126.6.1 代碼及注釋 .126.6.2 執(zhí)行結(jié)果截圖 .126.6.3 遇到的問題及解決方案 .136.7 基于 Hadoop/MapReduce 的并行程序設(shè)計（選作） .136.7.1 代碼及注釋 .136.7.2 執(zhí)行結(jié)果截圖 .146.7.3 遇到的問題及解決方案 .146.8 并行計算技術(shù)在實際應(yīng)用系統(tǒng)的應(yīng)用 .156.8.1 代碼及注釋 .156.8.2 執(zhí)行結(jié)果截圖 .156.8.3 遇到的問題及解決方案 .15班級_ 學(xué)號_ 姓名_ 算法名稱_11. 設(shè)計目的、意義（功能描述）并行計算或稱平行計算是相對于串行計算來說的。它是一種一次可執(zhí)行多個指令的算法，目的是提高計算速度，及通過擴(kuò)大問題求解規(guī)模，解決大型而復(fù)雜的計算問題。所謂并行計算可分為時間上的并行和空間上的并行。 時間上的并行就是指流水線技術(shù)，而空間上的并行則是指用多個處理器并發(fā)的執(zhí)行計算。為了縮短程序的運(yùn)行時間，我們采用了并行技術(shù)實現(xiàn)枚舉排序。2. 方案分析（解決方案）將要排序的數(shù)組分為多個部分放入不同的線程中，運(yùn)用多線程技術(shù)實現(xiàn)并行計算，最后在用多路歸并將排序的數(shù)組歸并到一起。歸并算法采用的是串行。3. 設(shè)計分析3.1 串行算法設(shè)計枚舉排序（Enumeration Sort）是一種最簡單的排序算法，通常也稱為秩排序（Rank Sort） 。該算法的具體思想是（假設(shè)按關(guān)鍵字遞增排序） ，對每一個待排序的元素統(tǒng)計小于它的所有元素的個數(shù)，從而得到該元素最終處于序列中的位置。假定待排序的 n 個數(shù)存在a1an中。首先將 a1與 a2an比較，記錄比其小的數(shù)的個數(shù)，令其為 k，a1 就被存入有序的數(shù)組 b1bn的 bk+1位置上；然后將 a2與 a1，a3an比較，記錄比其小的數(shù)的個數(shù)，依此類推。這樣的比較操作共 n(n-1)次，所以串行秩排序的時間復(fù)雜度為O（n 2） 。算法 枚舉排序串行算法輸入：a1an輸出：b1bnBeginfor i=1 to n do(1) k=1(2) for j=1 to n doif aiaj thenk=k+1end ifend for(3) bk= aiend forEnd3.2 并行算法設(shè)計算法的并行化算法比較的簡單,將隨機(jī)數(shù)分成兩個部分，對每一部分進(jìn)行排序.算法 枚舉排序并行算法輸入：a1an輸出：b1bn班級_ 學(xué)號_ 姓名_ 算法名稱_2Beginfor i=1 to n do(1) k=1(2) for j=1 to n doif aiaj thenk=k+1end ifend for(3) bk= aiend forEnd假定待排序的 n 個數(shù)存在 a1an/2中。首先將 a1與 a2an/2比較，記錄比其小的數(shù)的個數(shù)，令其為 k，a1 就被存入有序的數(shù)組 b1bn/2的 bk+1位置上；然后將 a2與a1，a3an/2比較，記錄比其小的數(shù)的個數(shù)，依此類推。這樣的比較操作共(n/2)(n-1)/2)次，所以串行秩排序的時間復(fù)雜度為 O（(n/2） 2） 。3.3 理論加速比分析在串行秩排序的時間復(fù)雜度為 O（n 2）, 并行算法的復(fù)雜度為 O（(n/2 ）2） 。所以理論加速比在 1 到 4 之間；4. 功能模塊實現(xiàn)與最終結(jié)果分析4.1 基于 OpenMP 的并行算法實現(xiàn)4.1.1 主要功能模塊與實現(xiàn)方法主函數(shù)模塊：主函數(shù)模塊：實現(xiàn)隨機(jī)數(shù)的產(chǎn)生，對數(shù)組空間的分配以及對并行串行函數(shù)的調(diào)用；并行排序模塊：對無序數(shù)組進(jìn)行秩排序，并且在 for 循環(huán)中 parallel 和 for 指令聯(lián)合使用，并行化的語句緊跟在編譯指導(dǎo)語后面，編譯指導(dǎo)語的功能區(qū)域一直延伸到外層 for 循環(huán)結(jié)束后，并且并行化作用于外部循環(huán)；串行排序模塊：利用兩個 for 循環(huán)對每一個待排序的元素統(tǒng)計小于它的所有元素的個數(shù)，從而得到該元素最終處于序列中的位置。4.1.2 實驗加速比分析實驗加速比在 1.7 到 2.5 之間，數(shù)值越大，越能體現(xiàn)加速比；4.2 基于 MPI 的并行算法實現(xiàn)4.2.1 主要功能模塊與實現(xiàn)方法主函數(shù)模塊：運(yùn)用 MPI_Init()函數(shù)實現(xiàn)了 mpi 執(zhí)行環(huán)境的初始化；MPI_Comm_rank()函數(shù)識別各個進(jìn)程；MPI_Comm_size()函數(shù)識別該進(jìn)程中的進(jìn)程數(shù)；用一對多群集通信函數(shù) MPI_Bcast()將待排序序列長度廣播給各個進(jìn)程；rand（）函數(shù)產(chǎn)生隨機(jī)數(shù)，對數(shù)組空間的分配，和在各個處理器間劃分任務(wù)；并行排序模塊：對無序數(shù)組進(jìn)行秩排序，將待排序序列的長度 DataSize，該處理器要排序班級_ 學(xué)號_ 姓名_ 算法名稱_3的序列長度 MyLength 和總處理器個數(shù)以及處理器 ID 傳參給 CountRank（）函數(shù)實現(xiàn)每個處理器的排序；4.2.2 實驗加速比分析實驗加速比在 1.5 到 2.0 之間,數(shù)值越大越能體現(xiàn)加速比.4.3 基于 Java 的并行算法實現(xiàn)4.3.1 主要功能模塊與實現(xiàn)方法在程序中創(chuàng)建了三個類，并在 liuhongling 類中調(diào)用其余類中的方法實現(xiàn)多線程，創(chuàng)建自己的 Thread 類的子類，并且在 chuanxing 和 bingxing 中重新定義了 run()方法來完成并行和串行排序；在 liuhongling 類中用 start()方法啟動線程，使之從新建狀態(tài)轉(zhuǎn)入就緒狀態(tài)并進(jìn)入就緒隊列排隊；第二個線程等待調(diào)用 join()方法的線程結(jié)束，再繼續(xù)執(zhí)行。4.3.2 實驗加速比分析實驗加速比在 2.5 到 3.0 之間；4.4 基于 Windows API 的并行算法實現(xiàn)4.4.1 主要功能模塊與實現(xiàn)方法主函數(shù)模塊：用動態(tài)分配實現(xiàn)對排序數(shù)組的空間分配；rand()函數(shù)實現(xiàn)隨機(jī)數(shù)的產(chǎn)生；CreateThread()函數(shù)創(chuàng)建進(jìn)程，WaitForMultipleObjects()函數(shù)來監(jiān)測對象；歸并模塊：將兩個已排序的數(shù)組歸并到一起； 4.4.2 實驗加速比分析實驗加速比在 1.8 到 2.5 之間,數(shù)值越大越能體現(xiàn)加速比.4.5 基于.net 的并行算法實現(xiàn)4.5.1 主要功能模塊與實現(xiàn)方法開啟進(jìn)程模塊：這里我們用定義了一個 ThreadStart 類型的委托,這個委托制定了線程需要執(zhí)行的方法：work.bingxing 在這個方法里實現(xiàn)了枚舉排序的并行算法4.5.2 實驗加速比分析實驗加速比在 3.5 到 5.0 之間；4.6 基于 Linux 的并行算法實現(xiàn)（選作）4.6.1 主要功能模塊與實現(xiàn)方法班級_ 學(xué)號_ 姓名_ 算法名稱_44.6.2 實驗加速比分析4.7 基于 Hadoop/MapReduce 的并行算法實現(xiàn)（選作）4.7.1 主要功能模塊與實現(xiàn)方法4.7.2 實驗加速比分析4.8 并行計算技術(shù)在實際系統(tǒng)中的應(yīng)用4.8.1 主要功能模塊與實現(xiàn)方法4.8.2 實驗加速比分析5. 設(shè)計體會班級_ 學(xué)號_ 姓名_ 算法名稱_5班級_ 學(xué)號_ 姓名_ 算法名稱_66. 附錄6.1 基于 OpenMP 的并行程序設(shè)計6.1.1 代碼及注釋#include “stdafx.h“#include #include #include #include using namespace std;int chuanxing(int *in, int *out, int size) int lhl_i, lhl_j, lhl_k; clock_t t3, t4; t3 = clock(); for (lhl_i = 0; lhl_iinlhl_j) lhl_k+;/記錄比自己小的數(shù)的個