單元iv非數(shù)值并行算法mpi編程實(shí)現(xiàn)

《單元iv非數(shù)值并行算法mpi編程實(shí)現(xiàn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、單元IV非數(shù)值并行算法MPI編程實(shí)現(xiàn)第十三章排序第十四章串匹配第十五章圖論第十六章組合優(yōu)化第十七章計(jì)算幾何這一單元主要介紹典型的非數(shù)值并行算法的MPI編程實(shí)現(xiàn)，包括排序（第十三章）、串匹配（第十四章）、圖論（第十五章）、組合優(yōu)化（第十六章）和計(jì)算幾何（第十七章）等。本單元的第十三章介紹并行排序算法及其MPI編程實(shí)現(xiàn)，包括枚舉排序、快速排序和正則采樣并行排序（PSRS）等；第十四章介紹并行串匹配算法及其MPI編程實(shí)現(xiàn)，包括并行KMP串匹配、并行隨機(jī)串匹配和并行近似串匹配等；第十五章介紹圖論并行算法及其MPI編程實(shí)現(xiàn)，包括使用矩陣乘求傳遞閉包、頂點(diǎn)倒塌法求連通分量、Di

2、jkstra單源最短路徑算法和Sollin最小生成樹算法等；第十六章介紹組合優(yōu)化算法及其MPI編程實(shí)現(xiàn)，包括八皇后問題、SAT問題、裝箱問題、背包問題和TSP問題等；第十七章介紹計(jì)算機(jī)幾何算法及其MPI編程實(shí)現(xiàn)，包括包含問題、相交問題和凸殼問題等。為了壓縮篇幅，第十三章只給出了PSRS算法的MPI源程序，第十四章只給出了KMP串匹配并行算法的MPI源程序，第十五章只給出了連通分量并行算法的MPI源程序，第十六章只給出了八皇后問題并行算法的MPI源程序，其余者均放在隨書的光盤中，也可從中國科學(xué)技術(shù)大學(xué)國家高性能計(jì)算中心（合肥）的網(wǎng)站http://www.nhpcc.u

3、stc.edu.cn下載。11.6第十三章排序排序是數(shù)據(jù)處理中經(jīng)常使用的一種重要運(yùn)算，如何進(jìn)行排序，特別是如何進(jìn)行高效的排序，是計(jì)算機(jī)應(yīng)用中的重要課題。排序的對(duì)象一般是一組記錄組成的文件，而記錄則是由若干數(shù)據(jù)項(xiàng)組成，其中的一項(xiàng)可用來標(biāo)志一個(gè)記錄，稱為關(guān)鍵字項(xiàng)，該數(shù)據(jù)項(xiàng)的值稱為關(guān)鍵字。所謂排序，就是要整理文件中的記錄，使得它按關(guān)鍵字遞增（或遞減）的次序排列起來。若給定的文件含有n個(gè)記錄｛R1，R2，…，Rn｝，它們的關(guān)鍵字分別為｛K1，K2，…，Kn｝，要把這n個(gè)記錄重新排列成為｛Ri1，Ri2，…，Rin｝，使得｛Ki1≥Ki2≥…≥Kin｝（或｛Ki1≤Ki2≤…

4、≤Kin｝）。本章主要介紹了枚舉排序、快速排序、PSRS排序算法以及它們的MPI編程實(shí)現(xiàn)。1.1枚舉排序1.1.1枚舉排序及其串行算法枚舉排序（EnumerationSort）是一種最簡(jiǎn)單的排序算法，通常也稱為秩排序（RankSort）。該算法的具體思想是（假設(shè)按關(guān)鍵字遞增排序），對(duì)每一個(gè)待排序的元素統(tǒng)計(jì)小于它的所有元素的個(gè)數(shù)，從而得到該元素最終處于序列中的位置。假定待排序的n個(gè)數(shù)存在a[1]…a[n]中。首先將a[1]與a[2]…a[n]比較，記錄比其小的數(shù)的個(gè)數(shù)，令其為k，a[1]就被存入有序的數(shù)組b[1]…b[n]的b[k+1]位置上；然后將a[2]與a[1]

5、，a[3]…a[n]比較，記錄比其小的數(shù)的個(gè)數(shù)，依此類推。這樣的比較操作共n(n-1)次，所以串行秩排序的時(shí)間復(fù)雜度為O（n2）。算法13.1枚舉排序串行算法輸入：a[1]…a[n]輸出：b[1]…b[n]Beginfori=1tondo(1)k=1(2)forj=1tondoifa[i]>a[j]thenk=k+1endifendfor(3)b[k]=a[i]endforEnd1.1.2枚舉排序的并行算法對(duì)該算法的并行化是很簡(jiǎn)單的，假設(shè)對(duì)一個(gè)長為n的輸入序列使用n個(gè)處理器進(jìn)行排序，只需是每個(gè)處理器負(fù)責(zé)完成對(duì)其中一個(gè)元素的定位，然后將所有的定位信息集中到主進(jìn)程中，由

6、主進(jìn)程負(fù)責(zé)完成所有元素的最終排位。該并行算法描述如下：算法13.2枚舉排序并行算法輸入：無序數(shù)組a[1]…a[n]6輸出：有序數(shù)組b[1]…b[n]Begin(1)P0播送a[1]…a[n]給所有Pi(2)forallPiwhere1≤i≤npara-do(2.1)k=1(2.2)forj=1tondoif(a[i]>a[j])or(a[i]=a[j]andi>j)thenk=k+1endifendfor(3)P0收集k并按序定位End在該并行算法中，使用了n個(gè)處理器，由于每個(gè)處理器定位一個(gè)元素，所以步驟⑵的時(shí)間復(fù)雜度為O（n）；步驟⑶中主進(jìn)程完成的數(shù)組元素重定位操

7、作的時(shí)間復(fù)雜度為O（n），通信復(fù)雜度分別為O（n）；同時(shí)⑴中的通信復(fù)雜度為O（n2）；所以總的計(jì)算復(fù)雜度為O（n），總的通信復(fù)雜度為O（n2）。MPI源程序請(qǐng)參見所附光盤。1.1快速排序1.1.1快速排序及其串行算法快速排序（QuickSort）是一種最基本的排序算法，它的基本思想是：在當(dāng)前無序區(qū)R[1，n]中取一個(gè)記錄作為比較的“基準(zhǔn)”（一般取第一個(gè)、最后一個(gè)或中間位置的元素），用此基準(zhǔn)將當(dāng)前的無序區(qū)R[1，n]劃分成左右兩個(gè)無序的子區(qū)R[1，i-1]和R[i，n](1≤i≤n)，且左邊的無序子區(qū)中記錄的所有關(guān)鍵字均小于等于基準(zhǔn)的關(guān)鍵字，右邊的無序子區(qū)中記錄的