并行計(jì)算課程報(bào)告

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