【正文】 前有兩種提 議 :一個(gè)是 Intel 公司提出的任務(wù)隊(duì)列(work queues) ,另外一個(gè)是巴塞羅那的學(xué)者提出的線程組 (threadgroups)。 (3)MPI 和 OpenMP 的交互問(wèn)題 .隨著由共享存儲(chǔ)的并行機(jī)所組成的機(jī)群的流行 ,人們?cè)絹?lái)越多的重視在這些系統(tǒng)中同時(shí)使用 MPI 和 OpenMP,即 在并行機(jī)內(nèi)使用 OpenMP,在并行機(jī)之間使用。 技術(shù)的 的優(yōu)缺點(diǎn) OpenMP 具有良好的可移植性，支持 Fortran 和 C/C++編程語(yǔ)言，操作系統(tǒng)平臺(tái)方面則支持 UNIX 系統(tǒng)以及 Windows 系統(tǒng)。 南京郵電大學(xué) 2020 屆本科生畢業(yè)設(shè)計(jì)（論文） 5 2）方便性問(wèn)題 在多核編程時(shí)，要求計(jì)算均攤到各個(gè) CPU 核上去，所有的程序都需要并行化執(zhí)行，對(duì)計(jì)算的負(fù)載均衡有很高要求。 3）可 移植性問(wèn)題 目前各個(gè)主流操作系統(tǒng)的線程 API 互不兼容，缺乏事實(shí)上的統(tǒng)一規(guī)范，要滿足可移植性得自己寫一些代碼，將各種不同操作系統(tǒng)的 API 封裝成一套統(tǒng)一的接口?；蛘呤菍⒍嘀鳈C(jī)虛擬成一個(gè)共享內(nèi)存環(huán)境（ Intel 有 這樣的平臺(tái)），但這么做效率還不如混合編程，唯一的好處是編程人員可以不必額外學(xué)習(xí) MPI 編程。因此，只有在并行執(zhí)行代碼負(fù)擔(dān)足夠大，而引入 OpenMP 本身的開銷又足夠小時(shí)，引入并 行化操作才能提高程序執(zhí)行效率。 3） 線程同步帶來(lái)的開銷 南京郵電大學(xué) 2020 屆本科生畢業(yè)設(shè)計(jì)（論文） 6 線程之間存在同步開銷是多線程應(yīng)用程序的特點(diǎn)，在進(jìn)行同步時(shí)候必然會(huì)帶來(lái)一定的開銷。 本論文研究的內(nèi)容 OpenMP 是為編寫共享存儲(chǔ)環(huán)境下的并行程序而提供的一個(gè)應(yīng)用編程接口。 本論文首先對(duì) OpenMP 技術(shù)進(jìn)行介紹，接著對(duì)快速排序算法進(jìn)行分析，找出 算法中相互獨(dú)立的部分，然后用 OpenMP 寫出相應(yīng)的程序代碼。 本章 通過(guò) 介紹 OpenMP技術(shù)的基本原理 ， 進(jìn)行詳細(xì)分析。 forkjoin執(zhí)行模型在剛開始執(zhí)行的時(shí)候，只有一個(gè)稱為“主線程”的運(yùn)行線程存在。 南京郵電大學(xué) 2020 屆本科生畢業(yè)設(shè)計(jì)（論文） 8 OpenMP的編程者需要在可并行工作的代碼部分用制導(dǎo)指令向編譯器指出其并行屬性，而且這些并行區(qū)域可以出現(xiàn)嵌套的情況，如圖 。它們是編譯制導(dǎo)、 API函數(shù)集和環(huán)境變量。 并行域控制類指令用于指示編譯器產(chǎn)生多個(gè)線程以并發(fā)執(zhí)行任務(wù)，任務(wù)分擔(dān)類指令指示編譯器如何給各個(gè)并發(fā)線程分發(fā)任務(wù)，同步控制類指令指示編譯器協(xié)調(diào)并發(fā)線程之間的時(shí)間約束關(guān) 系，數(shù)據(jù)環(huán)境類指令處理并行域內(nèi)外的變量共享或私有屬性以及邊界上的數(shù)據(jù)傳送操作等 編譯 系統(tǒng) 一個(gè)可運(yùn)行的編譯系統(tǒng)不僅僅是一個(gè)編譯轉(zhuǎn)換程序，同時(shí)還是運(yùn)行環(huán)境的支撐系統(tǒng)。 圖 如果計(jì)算機(jī) A和計(jì)算機(jī) B屬于不同的體系結(jié)構(gòu)，那么這樣的編譯往往稱為交叉編譯。 南京郵電大學(xué) 2020 屆本科生畢業(yè)設(shè)計(jì)（論文） 10 圖 作用 從圖 ，運(yùn)行系統(tǒng)的庫(kù)函數(shù)相當(dāng)于是目標(biāo)語(yǔ)言的語(yǔ)義擴(kuò)展，其功能強(qiáng)弱，直接影響到對(duì)源語(yǔ)言進(jìn)行彌補(bǔ)語(yǔ)義差距的難度，因此設(shè)計(jì)一定的運(yùn)行庫(kù)將有利于簡(jiǎn)化編譯器設(shè)計(jì)。從源語(yǔ)言到目標(biāo)語(yǔ)言的編譯過(guò)程可以經(jīng)過(guò)多個(gè)中間語(yǔ)言的步驟來(lái)完成的，各個(gè)步驟可以集中處理本階段的問(wèn)題。此處如果有對(duì)外部的函數(shù)調(diào)用，則會(huì)預(yù)留未定義的地址以供最后一步鏈接階段來(lái)填寫。 OpenMP編譯也可以分成多個(gè)步驟，在各個(gè)步驟完成不同的編譯任務(wù)。第五種方式則將 C代碼編譯再進(jìn)一步劃分。這時(shí)候 C代碼的編譯可以借助于現(xiàn)有的多種編譯器。 狹義的 OpenMP編譯器的功能是將帶有 OpenMP編譯制導(dǎo)的 C代碼翻譯成標(biāo)準(zhǔn) C代碼，因此它和所有編譯器一樣具有相似的結(jié)構(gòu)，即有典型的八個(gè)部件構(gòu)成，它們分別是詞法分析、語(yǔ)法分析、語(yǔ)義分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成、信息表管理和錯(cuò)誤處理，構(gòu)成如圖 。 通常詞法掃描器的工作任務(wù)有：識(shí)別出源程序中的各個(gè)基本語(yǔ)法單位（通常稱為單詞或語(yǔ)法符號(hào)）；刪除無(wú)用的空白字符、回車字符以及其他與語(yǔ)言無(wú)直接關(guān)系的非實(shí)質(zhì)性字符；刪除注釋行；進(jìn)行詞法檢查并報(bào)告所發(fā)現(xiàn)的錯(cuò)誤。 南京郵電大學(xué) 2020 屆本科生畢業(yè)設(shè)計(jì)（論文） 13 OpenMP制導(dǎo)指令中的關(guān)鍵詞包括 pragma、 omp、 parallel等等，數(shù)量并不多，因此 OpenMP/C編譯器的詞法分析和普通 C語(yǔ)言的詞法分析大體相同。產(chǎn)生語(yǔ)法樹的過(guò)程可以大致分為自頂向下和自底向上兩大類。 對(duì) OpenMP/C程序代碼的分析工作，需要根據(jù) OpenMP的語(yǔ)法規(guī)則和 C語(yǔ)言的語(yǔ)法規(guī)則的相關(guān)文法描述來(lái)進(jìn)行。語(yǔ)法特征描述的是各個(gè)語(yǔ)法元素之間的連接形式或結(jié)構(gòu)，語(yǔ)義特征表征的是各個(gè)語(yǔ)法成分的含義和功能，包括這些語(yǔ)法元素的屬性或執(zhí)行時(shí)應(yīng)進(jìn)行的運(yùn)算或操作。如果使用 Yacc語(yǔ)法分析工具，可以方便地將語(yǔ)義動(dòng)作結(jié)合進(jìn)語(yǔ)法分析過(guò)程中。而此處說(shuō)的中間代碼指的是編譯器未輸出目標(biāo)代碼之前在內(nèi)部使用的一種源代碼的等價(jià)表示。每當(dāng)一個(gè)語(yǔ)義過(guò)程被執(zhí)行以便對(duì)相應(yīng)的語(yǔ)法結(jié)構(gòu)進(jìn)行語(yǔ)義分析時(shí)，它就根據(jù)此語(yǔ)法結(jié)構(gòu)的語(yǔ)義，并結(jié)合在分析時(shí)獲得的語(yǔ)義信息，產(chǎn)生相應(yīng)的中間代碼。通常將中間代碼的生成作為編譯器的前后端分界線，將中間代碼生成之前的部分稱為編譯器的前端（ Front End），中間代碼生成之后的部分稱為后端（ Back End），這兩部分可用圖 。根據(jù)目標(biāo)代碼的目標(biāo)期望不同，優(yōu)化方法也相應(yīng)不同，有的是以運(yùn)行時(shí)間為標(biāo)準(zhǔn)越快越好，有的是以存儲(chǔ)空間開銷為標(biāo)準(zhǔn)占用內(nèi)存越少越好。如果只是對(duì) OpenMP程序進(jìn)行源代碼到源代碼的變換，可以采用的編譯優(yōu)化技術(shù)并不多，很多傳統(tǒng)編譯器優(yōu)化技術(shù)（特別是體系結(jié)構(gòu)相關(guān)的優(yōu)化技術(shù)）并不能在這里應(yīng)用?？蚣鼙容^固定，它是用目標(biāo)代碼形式描述的，但是有某些待定部分，需要在生成具 體的目標(biāo)代碼時(shí)，根據(jù)各語(yǔ)法成分的確切形式和參數(shù)來(lái)確定的。例如為了生成可執(zhí)行文件時(shí)，代碼生成中的三個(gè)主要任務(wù)：指令選擇、寄存器分配和指派、指令排序，在源代碼轉(zhuǎn)換工作中都不存在。 南京郵電大學(xué) 2020 屆本科生畢業(yè)設(shè)計(jì)（論文） 16 錯(cuò)誤處理 由于編程人員不可避免的會(huì)寫出有錯(cuò)誤的代碼，一個(gè)可用的編譯器必須能夠發(fā)現(xiàn)大 多數(shù)常見錯(cuò)誤，并能準(zhǔn)確地報(bào)告出錯(cuò)誤在源代碼中的位置，否則就沒(méi)有使用價(jià)值。其中詞法分析中要注意 OpenMP與 C語(yǔ)言共用關(guān)鍵字的區(qū)分，語(yǔ)法分析程序需要能在 C語(yǔ)法基礎(chǔ)之上識(shí)別 OpenMP制 導(dǎo)指令的語(yǔ)法，中間代碼選取 AST以便保留源代碼的語(yǔ)法層次結(jié)構(gòu)，目標(biāo)代碼生成中需要翻譯 OpenMP的并行語(yǔ)義。在 計(jì)算機(jī)上實(shí)現(xiàn)時(shí)，一個(gè)精心編制的快速排序版本比其他任何排序方法要快很多。最后進(jìn)行程序編碼，通過(guò)實(shí)踐來(lái)加深對(duì)本課題的掌握。排序算法也用在處理文字?jǐn)?shù)據(jù)以及產(chǎn)生人類可讀的輸出結(jié)果。然而，假設(shè)以下的數(shù)對(duì)將要以他們的第一個(gè)數(shù)字來(lái)排序。然而，要記住這種次序通常牽涉到額外的空間負(fù)擔(dān)。 第二趟把第三個(gè)數(shù)據(jù)與前兩個(gè)數(shù)從后向前掃描，把第三個(gè)數(shù)按大小插入到有序表中；依次進(jìn)行下去，進(jìn)行了 (n1)趟掃描以后就完成了整個(gè)排序過(guò)程。然后比較第 2個(gè)數(shù)和第 3個(gè)數(shù)，將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。 選擇排序是不穩(wěn)定的排序方法。該趟排序從當(dāng)前無(wú)序區(qū)中選出關(guān)鍵字最小的記錄 R[k]，將它與無(wú)序區(qū)的第 1個(gè)記錄R交換，使 R[1..i]和 R分別變?yōu)橛涗泜€(gè)數(shù)增加 1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少 1個(gè)的新無(wú)序區(qū)。 一直較好的增量序列是 2^k1,2^(k1)1,.....7,3,1,這樣可使 Shell排序時(shí)間復(fù)雜度達(dá)到 O(N^) 五 歸并排序 歸并排序（ MERGE SORT）是又一類不同的排序方法，合并的含義就 是將兩個(gè)或兩個(gè)以上的有序數(shù)據(jù)序列合并成一個(gè)新的有序數(shù)據(jù)序列，因此它又叫歸并算法。 堆排序借助最大值堆來(lái)實(shí)現(xiàn)，第 i次從堆頂移除最大值放到數(shù)組的倒數(shù)第 i個(gè)位置，然后shiftDown到倒數(shù)第 i+1個(gè)位置 ,一共執(zhí)行 N此調(diào)整，即完成排序。 比如知道待排序列在 [0,M）內(nèi)，那么可以分配 M個(gè)桶，第 I個(gè)桶記錄 I的出現(xiàn)情況，最后根據(jù)每個(gè)桶收到的位置信息把數(shù)據(jù)輸出成有序的形式。 排序時(shí)，分 6次完成，每次按第 i個(gè)排序碼來(lái)排。 2）鏈?zhǔn)酱鎯?chǔ)：每個(gè)桶通過(guò)一個(gè)靜態(tài)隊(duì)列來(lái)跟蹤。 3）根據(jù)樞紐元素最后確定的位置，把數(shù)組分成三部分，左邊的，右邊的，樞紐元素自己，對(duì)左邊的，右邊的分別遞歸調(diào)用快速排序算法即可。它采用了分治的思想：先保證列表的前半部分都小于后半部分，然后分別對(duì)前半部分和后半部分排序，這樣整個(gè)列表就有序了。由 C. A. R. Hoare在 1962年提出。 一趟 快速 排序 的算法是： 1）設(shè)置兩個(gè) 變量 i、 j， 排序 開始的時(shí)候： i=0， j=N1； 2）以第一個(gè) 數(shù)組 元素作為關(guān)鍵數(shù)據(jù)，賦值給 key，即 key=A[0]； 3）從 j 開始向前搜索，即由后開始向前搜索（ j ），找到第一個(gè)小于 key的值 A[j]， A[i]與 A[j]交換； 4）從 i 開始向后搜索，即由前開始向后搜索（ i ++ ），找到第一個(gè)大于 key的 A[i]， A[i]與 A[j]交換； 5）重復(fù)第 5 步，直到 I=J； (3,4 步是在程序中沒(méi)找到時(shí)候 j=j1， i=i+1，直至找到為止。 A[0] A[1] A[2] A[3] A[4] A[5] A[6] 49 38 65 97 76 13 27 進(jìn)行第一次交換后： 27 38 65 97 76 13 49 ( 按照算法的第三步從后面開始找，此時(shí) :J=6） 進(jìn)行第二次交換后： 27 38 49 97 76 13 65 ( 按照算法的第四步從前面開始找 key 的值， 6549,兩者交換，此時(shí)：I=2 ) 進(jìn)行第三次交換后： 27 38 13 97 76 49 65 ( 按照算法的第五步將又一次執(zhí)行算法的第三步從后開始找 進(jìn)行第四次交換后： 27 38 13 49 76 97 65 ( 按照算法的第四步從前面開始找大于 key 的值， 9749，兩者交換，此時(shí)： I=3,J=5 ) 此時(shí)再執(zhí)行第三步的時(shí)候就發(fā)現(xiàn) I=J=3，從而結(jié)束一趟快速排序，那么經(jīng)過(guò)一趟快速排序之后的結(jié)果是： 27 38 13 49 76 97 65，即所有大于 key49的數(shù)全部在 49 的后面，所有小于 key（ 49）的數(shù)全部在 key（ 49）的前面。一種比較常見的優(yōu)化方法是隨機(jī)化算法，即隨機(jī)選取一個(gè)元素作為主元。一位前輩做出了一個(gè)精辟的總結(jié)：“隨機(jī)化快速排序可以滿足一個(gè)人一輩子的人品需求。 平衡快排（ Balanced Quicksort）： 每次盡可能地選擇一個(gè)能夠代表中值的元南京郵電大學(xué) 2020 屆本科生畢業(yè)設(shè)計(jì)（論文） 24 素作為關(guān)鍵數(shù)據(jù)，然后遵循普通快排的原則進(jìn)行比較、替換和遞歸。 外部快排（ External Quicksort）： 與普通快排不同的是，關(guān)鍵數(shù)據(jù)是一段 buffer，首先將之前和之后的 M/2個(gè)元素讀入 buffer并對(duì)該 buffer中的這些元素進(jìn)行排序，然后從被排序數(shù)組的開頭（或者結(jié)尾）讀入下一個(gè)元素，假如這個(gè)元素小于 buffer中最小的元素，把它寫到最開頭的空位上；假如這個(gè)元素大于 buffer中最大 的元素，則寫到最后的空位上；否則把 buffer中最大或者最小的元素寫入數(shù)組，并把這個(gè)元素放在 buffer里。 三路基數(shù)快排 （ Threeway Radix Quicksort，也稱作 Multikey Quicksort、Multikey Quicksort）：結(jié)合了基數(shù)排序（ radix sort，如一般的字符串比較排序就是基數(shù)排序）和快排的特點(diǎn)，是字符串排序中比較高效的算法。 特性 空間效率 ： 由于快速排 序是遞歸的 ， 需要借助一個(gè)遞歸工作棧來(lái)保存每一層遞歸調(diào)用的必要信息 。 時(shí)間效率 ： 快速排序的運(yùn)行時(shí)間與劃分是否對(duì)稱有關(guān)， 而后者又與具體使用的劃分算法有關(guān)。也就是說(shuō)快速排序的排序?qū)ο笫亲x入內(nèi)存的數(shù)據(jù)。 注意： 這里為方便起見，我們假設(shè)算法 Quick_Sort 的范圍閾值為 1（即一直將線性表分解到只剩一個(gè)元素），這對(duì)該 算法復(fù)雜性 的分析沒(méi)有本質(zhì)的影響。因此對(duì)各種 pivot 選擇法 而言，最壞情況和最好情況都是相同的。 這個(gè)最壞情況運(yùn)行時(shí)間與 插入排序 是一樣的。于是有： T(n） ≤22c(n1)+θ（ n） ≤2 只要 c 足夠大，上面的第二個(gè)小于等于號(hào)就可以成立。 最好情況 如果每次劃分過(guò)程產(chǎn)生的區(qū)間大小都為 n/2，則快速 排序 法運(yùn)行就快得多了。我們可以得到遞歸式： T(n)=T(n/10)+T(9n/10)+θ（ n),T(1)=θ（ 1) (4) 請(qǐng)注意該樹的每一層都有代價(jià) n，直到在深度 log10n=θ（ logn）處達(dá)到邊界條件，以后各層代價(jià)至多為 n。其原因在于，任何一種按常數(shù)比例進(jìn)行劃分所產(chǎn)生的遞歸樹的深度都為 θ（ nlogn），其中每一層的代價(jià)為 O(n），因而不管常數(shù)比例是什么，總的運(yùn)行時(shí)間都為 θ（ nlogn），只不過(guò)其中隱含的常數(shù)因子有