OpenMP畢設(shè)論文

1、xxxx大學(xué) 畢 業(yè) 設(shè) 計(jì)（論 文）題 目基于openmp的快速排序算法分析與程序設(shè)計(jì)專(zhuān) 業(yè)學(xué)生姓名班級(jí)學(xué)號(hào)指導(dǎo)教師評(píng)閱教師指導(dǎo)單位 日期： 年 月 日至 年 月 日畢業(yè)設(shè)計(jì)（論文）原創(chuàng)性聲明本人鄭重聲明：所提交的畢業(yè)設(shè)計(jì)（論文），是本人在導(dǎo)師指導(dǎo)下，獨(dú)立進(jìn)行研究工作所取得的成果。除文中已注明引用的內(nèi)容外，本畢業(yè)設(shè)計(jì)（論文）不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫(xiě)過(guò)的作品成果。對(duì)本研究做出過(guò)重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明并表示了謝意。 論文作者簽名： 日期： 年 月 日 摘 要openmp是一種面向共享內(nèi)存以及分布式共享內(nèi)存的多處理器多線(xiàn)程并行編程語(yǔ)言。具有良好的可移植性，支持

2、fortran和c/c+編程語(yǔ)言，操作系統(tǒng)平臺(tái)方面則支持unix系統(tǒng)以及windows系統(tǒng)。openmp的重要性在于它能夠?yàn)榫帉?xiě)多線(xiàn)程程序提供一種簡(jiǎn)單的方法，而無(wú)需程序員進(jìn)行復(fù)雜的線(xiàn)程創(chuàng)建、同步、負(fù)載平衡和銷(xiāo)毀工作。而快速排序（quicksort）是對(duì)冒泡排序的一種改進(jìn)，它采用了分治的思想，是所有排序算法中最高效，應(yīng)用最廣泛的一種。本文將對(duì)openmp的快速排序算法進(jìn)行分析并設(shè)計(jì)程序。論文根據(jù)執(zhí)行模式和三個(gè)基本要素分析了openmp技術(shù)的基本原理，并詳細(xì)講解了它的優(yōu)缺點(diǎn)，闡述其發(fā)展趨勢(shì)。接著列舉了主要的幾個(gè)排序算法進(jìn)行比較說(shuō)明，以便能更好地了解其性能特點(diǎn)。對(duì)快速排序算法分別從最好情況，最壞情況

3、，平均情況進(jìn)行總體分析。最后對(duì)快速排序，基于歸并的快速排序，雙倍快速排序舉例進(jìn)行程序編碼，通過(guò)實(shí)踐編程來(lái)加深對(duì)本課題知識(shí)的掌握。關(guān)鍵字：openmp，并行程序，多線(xiàn)程共享，庫(kù)函數(shù)，編譯系統(tǒng)，快速排序。abstractopenmp for shared memory and distributed shared memory multi-processor, multi-threaded parallel programming language. has good portability, support for fortran and c / c + + programming langua

4、ge，operating system platform support unix systems and windows systems. the openmp importance lies in its ability to provide a simple method for the preparation of a multithreaded program, without the need for programmers to create complex threads, synchronization, load balancing, and destruction. qu

5、ick sort (quicksort) is an improvement on the bubble sort, it uses the idea of partition, is the most efficient, the most widely used one among all the sorting algorithm. in this paper, openmp quick sort algorithm analysis and design process.according to the execution mode and three basic elements,

6、the paper analyzes the basic principles of openmp technology, and explain in detail the advantages and disadvantages of its development trend. goes on to list the main sorting algorithm compare instructions, in order to better understand its performance characteristics. from the best-case, worst-cas

7、e, average case, the overall analysis of the quick sort algorithm. finally, the quick sort, quick sort merge double quick sort example program code, programming practice to deepen the mastery of knowledge on the subject.keywords: openmp，parallel program, multi-threaded shared, library functions, com

8、pilation system, quick sort.目 錄第一章 緒論 11.1引言 11.2openmp技術(shù)的現(xiàn)狀與發(fā)展趨勢(shì) 1 1.2.1并行發(fā)展史1 1.2.2openmp技術(shù)的現(xiàn)狀概述 3 1.2.3openmp技術(shù)的發(fā)展方向 4 1.3openmp技術(shù)的的優(yōu)缺點(diǎn) 4 1.4本論文研究的內(nèi)容 6第二章openmp技術(shù)的基本原理 7 2.1引言 7 2.2openmp技術(shù)的基本概念7 2.2.1執(zhí)行模式7 2.2.2openmp的編程要素82.3openmp的編譯系統(tǒng)8 2.3.1編譯系統(tǒng)8 2.3.2目標(biāo)語(yǔ)言 10 2.3.3openmp編譯器結(jié)構(gòu)122.4小結(jié)16第三章openm

9、p的快速排序算法分析與程序設(shè)計(jì)173.1引言173.2排序算法的分析與比較17 3.2.1排序算法的概念 17 3.2.2排序算法的分類(lèi)比較 183.3快速排序算法分析21 3.3.1快速排序算法的介紹 22 3.3.2幾種值得一提的變種快速排序算法23 3.3.3快速排序算法的特性 24 3.3.4快速排序算法的性能分析 25 3.3.5快速排序算法的舉例分析 28結(jié)束語(yǔ) 36致謝 37參考文獻(xiàn) 38附錄a 39附錄b 39南京郵電大學(xué)2013屆本科生畢業(yè)設(shè)計(jì)（論文）第一章 緒論1.1引言進(jìn)入多核時(shí)代后，必須使用多線(xiàn)程編寫(xiě)程序才能讓各個(gè)cpu核得到利用。在單核時(shí)代，通常使用操作系統(tǒng)提供的ap

10、i來(lái)創(chuàng)建線(xiàn)程，然而，在多核系統(tǒng)中，情況發(fā)生了很大的變化，如果仍然使用操作系統(tǒng)api來(lái)創(chuàng)建線(xiàn)程會(huì)遇到一些問(wèn)題。這個(gè)時(shí)候就需要一種針對(duì)共享內(nèi)存的多線(xiàn)程編程技術(shù)openmp。它由一些具有國(guó)際影響力的大規(guī)模軟件和硬件廠(chǎng)商共同定義的標(biāo)準(zhǔn).它是一種編譯指導(dǎo)語(yǔ)句，指導(dǎo)多線(xiàn)程、共享內(nèi)存并行的應(yīng)用程序編程接口(api)openmp是一種面向共享內(nèi)存以及分布式共享內(nèi)存的多處理器多線(xiàn)程并行編程語(yǔ)言，openmp是一種能被用于顯示指導(dǎo)多線(xiàn)程、共享內(nèi)存并行的應(yīng)用程序編程接口。其規(guī)范由sgi發(fā)起.openmp具有良好的可移植性，支持多種編程語(yǔ)言。openmp能夠支持多種平臺(tái)，包括大多數(shù)的類(lèi)unix以及windowsnt系

11、統(tǒng).openmp最初是為了共享內(nèi)存多處理的系統(tǒng)結(jié)構(gòu)設(shè)計(jì)的并行編程方法，與通過(guò)消息傳遞進(jìn)行并行編程的模型有很大的區(qū)別。因?yàn)檫@是用來(lái)處理多處理器共享一個(gè)內(nèi)存設(shè)備這樣的情況的。多個(gè)處理器在訪(fǎng)問(wèn)內(nèi)存的時(shí)候使用的是相同的內(nèi)存編址空間。smp是一種共享內(nèi)存的體系結(jié)構(gòu)，同時(shí)分布式共享內(nèi)存的系統(tǒng)也屬于共享內(nèi)存多處理器結(jié)構(gòu)，分布式共享內(nèi)存將多機(jī)的內(nèi)存資源通過(guò)虛擬化的方式形成一個(gè)同意的內(nèi)存空間提供給多個(gè)機(jī)子上的處理器使用,openmp對(duì)這樣的機(jī)器也提供了一定的支持。這一章的目的是對(duì)openmp技術(shù)進(jìn)行簡(jiǎn)單的介紹，使讀者能夠?qū)penmp有一個(gè)大概的了解。本章簡(jiǎn)述了openmp技術(shù)的發(fā)展與現(xiàn)狀，并提及了它的優(yōu)缺點(diǎn)。

12、在說(shuō)明的過(guò)程中，也加入了一些個(gè)人的理解。 1.2openmp技術(shù)的現(xiàn)狀與發(fā)展趨勢(shì)1.2.1并行發(fā)展史從20世紀(jì)40年代開(kāi)始的現(xiàn)代計(jì)算機(jī)發(fā)展歷程可以分為兩個(gè)明顯的發(fā)展時(shí)代：串行計(jì)算時(shí)代、并行計(jì)算時(shí)代。每一個(gè)計(jì)算時(shí)代都從體系結(jié)構(gòu)發(fā)展開(kāi)始，接著是系統(tǒng)軟件（特別是編譯器與操作系統(tǒng)）、應(yīng)用軟件，最后隨著問(wèn)題求解環(huán)境的發(fā)展而達(dá)到頂峰。并行計(jì)算機(jī)是由一組處理單元組成的。這組處理單元通過(guò)相互之間的通信與協(xié)作，以更快的速度共同完成一項(xiàng)大規(guī)模的計(jì)算任務(wù)。因此，并行計(jì)算機(jī)的兩個(gè)最主要的組成部分是計(jì)算節(jié)點(diǎn)和節(jié)點(diǎn)間的通信與協(xié)作機(jī)制。并行計(jì)算機(jī)體系結(jié)構(gòu)的發(fā)展也主要體現(xiàn)在計(jì)算節(jié)點(diǎn)性能的提高以及節(jié)點(diǎn)間通信技術(shù)的改進(jìn)兩方面。節(jié)

13、點(diǎn)性能不斷進(jìn)步，20世紀(jì)60年代初期，由于晶體管以及磁芯存儲(chǔ)器的出現(xiàn)，處理單元變得越來(lái)越小，存儲(chǔ)器也更加小巧和廉價(jià)。這些技術(shù)發(fā)展的結(jié)果導(dǎo)致了并行計(jì)算機(jī)的出現(xiàn)。這一時(shí)期的并行計(jì)算機(jī)多是規(guī)模不大的共享存儲(chǔ)多處理器系統(tǒng)，即所謂大型主機(jī)。ibm360是這一時(shí)期的典型代表。到了20世紀(jì)60年代末期，同一個(gè)處理器開(kāi)始設(shè)置多個(gè)功能相同的功能單元，流水線(xiàn)技術(shù)也出現(xiàn)了。與單純提高時(shí)鐘頻率相比，這些并行特性在處理器內(nèi)部的應(yīng)用大大提高了并行計(jì)算機(jī)系統(tǒng)的性能。伊利諾依大學(xué)和burroughs公司此時(shí)開(kāi)始實(shí)施illiac計(jì)劃，研制一臺(tái)64顆cpu的simd主機(jī)系統(tǒng)，它涉及到硬件技術(shù)、體系結(jié)構(gòu)、i/o設(shè)備、操作系統(tǒng)、程序

14、設(shè)計(jì)語(yǔ)言直至應(yīng)用程序在內(nèi)的眾多研究課題。不過(guò)，當(dāng)一臺(tái)規(guī)模大大縮小的原型系統(tǒng)（僅使用了16顆cpu）終于在1975年面世時(shí)，整個(gè)計(jì)算機(jī)界已經(jīng)發(fā)生了巨大變化。首先是存儲(chǔ)系統(tǒng)概念的革新，提出虛擬存儲(chǔ)和緩存的思想。其次是半導(dǎo)體存儲(chǔ)器開(kāi)始代替磁芯存儲(chǔ)器。最初，半導(dǎo)體存儲(chǔ)器只是在某些機(jī)器中被用作緩存，而cdc7600則率先全面采用這種體積更小、速度更快、可以直接尋址的半導(dǎo)體存儲(chǔ)器，磁芯存儲(chǔ)器從此退出了歷史舞臺(tái)。與此同時(shí)，集成電路也出現(xiàn)了，并迅速應(yīng)用到計(jì)算機(jī)中。元器件技術(shù)的這兩大革命性突破，使得illiac的設(shè)計(jì)者們?cè)诘讓佑布约安⑿畜w系結(jié)構(gòu)方面提出的種種改進(jìn)都大為遜色。處理器高速發(fā)展1976年cray-1

15、問(wèn)世以后，向量計(jì)算機(jī)從此牢牢地控制著整個(gè)高性能計(jì)算機(jī)市場(chǎng)15年。cray-1對(duì)所使用的邏輯電路進(jìn)行了精心的設(shè)計(jì)，采用了我們?nèi)缃穹Q(chēng)為risc的精簡(jiǎn)指令集，還引入了向量寄存器，以完成向量運(yùn)算。這一系列技術(shù)手段的使用，使cray-1的主頻達(dá)到了80mhz。微處理器隨著機(jī)器的字長(zhǎng)從4位、8位、16位一直增加到32位，其性能也隨之顯著提高。從20世紀(jì)80年代開(kāi)始，微處理器技術(shù)一直在高速前進(jìn)。稍后又出現(xiàn)了非常適合于smp方式的總線(xiàn)協(xié)議。而伯克利加州大學(xué)則對(duì)總線(xiàn)協(xié)議進(jìn)行了擴(kuò)展，提出了cache一致性問(wèn)題的處理方案。從此，c.mmp開(kāi)創(chuàng)出的共享存儲(chǔ)多處理器之路越走越寬?，F(xiàn)在，這種體系結(jié)構(gòu)已經(jīng)基本上統(tǒng)治了服務(wù)器

16、和桌面工作站市場(chǎng)。通信機(jī)制穩(wěn)步前進(jìn)，同一時(shí)期，基于消息傳遞機(jī)制的并行計(jì)算機(jī)也開(kāi)始不斷涌現(xiàn)。20世紀(jì)80年代中期，加州理工學(xué)院成功地將64個(gè)i8086/i8087處理器通過(guò)超立方體互連結(jié)構(gòu)連結(jié)起來(lái)。此后，便先后出現(xiàn)了intelipsc系列、inmostransputer系列，intelparagon以及ibmsp的前身vulcan等基于消息傳遞機(jī)制的并行計(jì)算機(jī)。20世紀(jì)80年代末到90年代初，共享存儲(chǔ)器方式的大規(guī)模并行計(jì)算機(jī)又獲得了新的發(fā)展。ibm將大量早期risc微處理器通過(guò)蝶形互連網(wǎng)絡(luò)連結(jié)起來(lái)。人們開(kāi)始考慮如何才能在實(shí)現(xiàn)共享存儲(chǔ)器緩存一致的同時(shí)，使系統(tǒng)具有一定的可擴(kuò)展性。20世紀(jì)90年代初期

17、，斯坦福大學(xué)提出了dash計(jì)劃，它通過(guò)維護(hù)一個(gè)保存有每一緩存塊位置信息的目錄結(jié)構(gòu)來(lái)實(shí)現(xiàn)分布式共享存儲(chǔ)器的緩存一致性。后來(lái)，ieee在此基礎(chǔ)上提出了緩存一致性協(xié)議的標(biāo)準(zhǔn)。20世紀(jì)90年代至今，主要的幾種體系結(jié)構(gòu)開(kāi)始走向融合。屬于數(shù)據(jù)并行類(lèi)型的cm-5除大量采用商品化的微處理器以外，也允許用戶(hù)層的程序傳遞一些簡(jiǎn)單的消息。crayt3d是一臺(tái)numa結(jié)構(gòu)的共享存儲(chǔ)型并行計(jì)算機(jī)，但是它也提供了全局同步機(jī)制、消息隊(duì)列機(jī)制，并采取了一些減少消息傳遞延遲的技術(shù)。隨著微處理器商品化、網(wǎng)絡(luò)設(shè)備的發(fā)展以及mpi/pvm等并行編程標(biāo)準(zhǔn)的發(fā)布，集群架構(gòu)的并行計(jì)算機(jī)出現(xiàn)開(kāi)始。ibmsp2系列集群系統(tǒng)就是其中的典型代表。

18、在這些系統(tǒng)中，各個(gè)節(jié)點(diǎn)采用的都是標(biāo)準(zhǔn)的商品化計(jì)算機(jī)，它們之間通過(guò)高速網(wǎng)絡(luò)連接起來(lái)。有限元并行計(jì)算的發(fā)展和現(xiàn)狀。目前，在計(jì)算力學(xué)領(lǐng)域內(nèi)，圍繞著基于變分原理的有限元法和基于邊界積分方程的邊界元法，以及基于現(xiàn)在問(wèn)世的各種并行計(jì)算機(jī)，逐漸形成了一個(gè)新的學(xué)科分支有限元并行計(jì)算。它是高效能的，使得許多現(xiàn)在應(yīng)用串行計(jì)算機(jī)和串行算法不能解決或求解不好的大型的、復(fù)雜的力學(xué)問(wèn)題能得到滿(mǎn)意的解答，故其發(fā)展速度十分驚人。在國(guó)際上已經(jīng)掀起了利用并行機(jī)進(jìn)行工程分析和研究的高潮。并行研究的意義重大，而openmp是一個(gè)支持共享存儲(chǔ)并行設(shè)計(jì)的庫(kù)，特別適宜多核cpu上的并行程序設(shè)計(jì)。1.2.2openmp技術(shù)的現(xiàn)狀概述open

19、mp是國(guó)際上繼mpi之后于i998年推出的工業(yè)標(biāo)準(zhǔn)。由dec、ibm、lntel、kuck&assiciates、sgi等公司共同定義。它解決了不同并行計(jì)算機(jī)系統(tǒng)上應(yīng)用系統(tǒng)難以移植的問(wèn)題，將可移植性帶到可縮放的、共享主存的程序設(shè)計(jì)之中。對(duì)不同的語(yǔ)言，有不同的openmp標(biāo)準(zhǔn)。openmp是一種面向共享內(nèi)存以及分布式共享內(nèi)存的多處理器多線(xiàn)程并行編程語(yǔ)言，openmp是一種能被用于顯示指導(dǎo)多線(xiàn)程、共享內(nèi)存并行的應(yīng)用程序編程接口.其規(guī)范由sgi發(fā)起.openmp具有良好的可移植性，支持多種編程語(yǔ)言.openmp能夠支持多種平臺(tái)，包括大多數(shù)的類(lèi)unix以及windowsnt系統(tǒng).openmp最初是為了

20、共享內(nèi)存多處理的系統(tǒng)結(jié)構(gòu)設(shè)計(jì)的并行編程方法，與通過(guò)消息傳遞進(jìn)行并行編程的模型有很大的區(qū)別.因?yàn)檫@是用來(lái)處理多處理器共享一個(gè)內(nèi)存設(shè)備這樣的情況的.多個(gè)處理器在訪(fǎng)問(wèn)內(nèi)存的時(shí)候使用的是相同的內(nèi)存編址空間.smp是一種共享內(nèi)存的體系結(jié)構(gòu)，同時(shí)分布式共享內(nèi)存的系統(tǒng)也屬于共享內(nèi)存多處理器結(jié)構(gòu)，分布式共享內(nèi)存將多機(jī)的內(nèi)存資源通過(guò)虛擬化的方式形成一個(gè)同意的內(nèi)存空間提供給多個(gè)機(jī)子上的處理器使用,openmp對(duì)這樣的機(jī)器也提供了一定的支持。openmp推出后，基本上每個(gè)包含共享體系結(jié)構(gòu)的并行計(jì)算機(jī)的推出，都配置了該語(yǔ)言，而且多家廠(chǎng)商針對(duì)自己的體系結(jié)構(gòu)特點(diǎn)還對(duì)openmp做了擴(kuò)充，例如：compaq公司擴(kuò)充了分布、

21、重分布、親緣性調(diào)度等指標(biāo) ，但最新的openmp20版本還是不包含分布等的描述，openmp是當(dāng)前和未來(lái)幾年最活躍的并行語(yǔ)言。1.2.3openmp技術(shù)的發(fā)展方向目前,關(guān)于openmp下一個(gè)版本openmp310人們還有很多提議。arb正在對(duì)這些提議進(jìn)行討論,決定哪些納入將來(lái)的openmp。它不僅取決于這些提議是否解決了那些急需解決的問(wèn)題,還在于這些提出的語(yǔ)言指導(dǎo)是否簡(jiǎn)單容易。而且不會(huì)給設(shè)計(jì)編譯器的程序員增加太多的工作.這些提議主要集中于以下幾個(gè)方面: (1)openmp最主要的并行來(lái)源是循環(huán)結(jié)構(gòu),但是它對(duì)于另外一種并行方式:任務(wù)并行,除了sec2tions指導(dǎo)外,沒(méi)有提供太多的支持。尤其是對(duì)

22、于動(dòng)態(tài)任務(wù)的派生和并行,以及嵌套并行,目前有兩種提議:一個(gè)是intel公司提出的任務(wù)隊(duì)列(work queues) ,另外一個(gè)是巴塞羅那的學(xué)者提出的線(xiàn)程組(threadgroups)。 (2)openmp變量的作用域(scope)問(wèn)題.在以往的openmp程序中,用戶(hù)必須指定一個(gè)變量是私有的還是共享的;在新的提議中,建議這個(gè)工作由編譯器自動(dòng)實(shí)現(xiàn)。即編譯器能夠決定哪些變量是私有的,哪些變量是共享的。 (3)mpi和openmp的交互問(wèn)題.隨著由共享存儲(chǔ)的并行機(jī)所組成的機(jī)群的流行,人們?cè)絹?lái)越多的重視在這些系統(tǒng)中同時(shí)使用mpi和openmp,即在并行機(jī)內(nèi)使用openmp,在并行機(jī)之間使用。隨著ope

23、nmp技術(shù)的發(fā)展，以上講到的幾個(gè)提議將會(huì)得到進(jìn)一步的實(shí)現(xiàn)。它能夠?yàn)榫帉?xiě)多線(xiàn)程程序提供一種簡(jiǎn)單的方法，而無(wú)需程序員進(jìn)行復(fù)雜的線(xiàn)程創(chuàng)建、同步、負(fù)載平衡和銷(xiāo)毀工作。在此基礎(chǔ)上，openmp將成為更加簡(jiǎn)潔方便的多線(xiàn)程并行編程語(yǔ)言。1.3openmp技術(shù)的的優(yōu)缺點(diǎn) openmp具有良好的可移植性，支持fortran和c/c+編程語(yǔ)言，操作系統(tǒng)平臺(tái)方面則支持unix系統(tǒng)以及windows系統(tǒng)。openmp的重要性在于，它能夠?yàn)榫帉?xiě)多線(xiàn)程程序提供一種簡(jiǎn)單的方法，而無(wú)需程序員進(jìn)行復(fù)雜的線(xiàn)程創(chuàng)建、同步、負(fù)載平衡和銷(xiāo)毀工作。 和api相比，openmp的優(yōu)點(diǎn)主要表現(xiàn)在成功解決了以下幾個(gè)問(wèn)題：1）cpu核數(shù)擴(kuò)展性問(wèn)

24、題多核編程需要考慮程序性能隨cpu核數(shù)的擴(kuò)展性，即硬件升級(jí)到更多核后，能夠不修改程序就讓程序性能增長(zhǎng)，這要求程序中創(chuàng)建的線(xiàn)程數(shù)量需要隨cpu核數(shù)變化，不能創(chuàng)建固定數(shù)量的線(xiàn)程，否則在cpu核數(shù)超過(guò)線(xiàn)程數(shù)量上的機(jī)器上運(yùn)行，將無(wú)法完全利用機(jī)器性能。雖然通過(guò)一定方法可以使用操作系統(tǒng)api創(chuàng)建可變化數(shù)量的線(xiàn)程，但是比較麻煩，但使用openmp就方便得多。2）方便性問(wèn)題在多核編程時(shí)，要求計(jì)算均攤到各個(gè)cpu核上去，所有的程序都需要并行化執(zhí)行，對(duì)計(jì)算的負(fù)載均衡有很高要求。這就要求在同一個(gè)函數(shù)內(nèi)或同一個(gè)循環(huán)中，可能也需要將計(jì)算分?jǐn)偟礁鱾€(gè)cpu核上，需要?jiǎng)?chuàng)建多個(gè)線(xiàn)程。操作系統(tǒng)api創(chuàng)建線(xiàn)程時(shí)，需要線(xiàn)程入口函數(shù)，

25、很難滿(mǎn)足這個(gè)需求，除非將一個(gè)函數(shù)內(nèi)的代碼手工拆成多個(gè)線(xiàn)程入口函數(shù)，這將大大增加程序員的工作量。使用openmp創(chuàng)建線(xiàn)程則不需要入口函數(shù)，非常方便，可以將同一函數(shù)內(nèi)的代碼分解成多個(gè)線(xiàn)程執(zhí)行，也可以將一個(gè)for循環(huán)分解成多個(gè)線(xiàn)程執(zhí)行。3）可移植性問(wèn)題目前各個(gè)主流操作系統(tǒng)的線(xiàn)程api互不兼容，缺乏事實(shí)上的統(tǒng)一規(guī)范，要滿(mǎn)足可移植性得自己寫(xiě)一些代碼，將各種不同操作系統(tǒng)的api封裝成一套統(tǒng)一的接口。而openmp是標(biāo)準(zhǔn)規(guī)范，所有支持它的編譯器都是執(zhí)行同一套標(biāo)準(zhǔn)，不存在可移植性問(wèn)題。openmp的缺點(diǎn)亦比較明顯，最大的缺點(diǎn)是只能在單臺(tái)主機(jī)上工作，不能用于多臺(tái)主機(jī)間的并行計(jì)算。如果要多主機(jī)聯(lián)網(wǎng)使用openmp

26、（比如在超級(jí)計(jì)算機(jī)上），那必須有額外的工具幫助，比如 mpi + openmp 混合編程。或者是將多主機(jī)虛擬成一個(gè)共享內(nèi)存環(huán)境（intel有這樣的平臺(tái)），但這么做效率還不如混合編程，唯一的好處是編程人員可以不必額外學(xué)習(xí)mpi編程。openmp的缺點(diǎn)在以下幾個(gè)有待解決的問(wèn)題上也可以看出。1）openmp本身的開(kāi)銷(xiāo)openmp獲得應(yīng)用程序多線(xiàn)程并行化的能力不是憑空而來(lái)的，它需要程序庫(kù)的支持，庫(kù)中代碼的運(yùn)行必然會(huì)帶來(lái)一定的開(kāi)銷(xiāo)。實(shí)際上并不是所有的代碼都需要并行化，有些代碼在并行化后的執(zhí)行效率反而不如串行時(shí)高，原因就是加上了并行化所帶來(lái)的開(kāi)銷(xiāo)后，代碼的執(zhí)行效率降低。因此，只有在并行執(zhí)行代碼負(fù)擔(dān)足夠大，

27、而引入openmp本身的開(kāi)銷(xiāo)又足夠小時(shí)，引入并行化操作才能提高程序執(zhí)行效率。2）負(fù)載均衡已知一個(gè)openmp應(yīng)用程序在執(zhí)行的過(guò)程中，有很多的同步點(diǎn)，線(xiàn)程只有在進(jìn)行同步之后才能繼續(xù)執(zhí)行下面的代碼。因此某一個(gè)線(xiàn)程在執(zhí)行到同步點(diǎn)之后，若沒(méi)有進(jìn)一步的工作需要完成，此線(xiàn)程只有等待其它線(xiàn)程執(zhí)行完畢后才能繼續(xù)執(zhí)行。此時(shí)，如果各個(gè)線(xiàn)程之間的負(fù)載不均衡，就有可能出現(xiàn)某些線(xiàn)程“空等”，而另外一些線(xiàn)程因負(fù)擔(dān)沉重，要很長(zhǎng)事件才能完成任務(wù)。3） 線(xiàn)程同步帶來(lái)的開(kāi)銷(xiāo)線(xiàn)程之間存在同步開(kāi)銷(xiāo)是多線(xiàn)程應(yīng)用程序的特點(diǎn)，在進(jìn)行同步時(shí)候必然會(huì)帶來(lái)一定的開(kāi)銷(xiāo)。很多情況下，不合適的同步機(jī)制或算法會(huì)使代碼的運(yùn)行效率下降?？梢钥闯?，openm

28、p是優(yōu)缺點(diǎn)共存的，還有很大的進(jìn)步發(fā)展空間。在未來(lái)的研究中，它的實(shí)用性還會(huì)進(jìn)一步提高。1.4本論文研究的內(nèi)容openmp是為編寫(xiě)共享存儲(chǔ)環(huán)境下的并行程序而提供的一個(gè)應(yīng)用編程接口。使用openmp，程序員無(wú)需了解如何創(chuàng)建、同步及銷(xiāo)毀線(xiàn)程的知識(shí)，甚至無(wú)需決定創(chuàng)建的線(xiàn)程數(shù)，即可輕松地線(xiàn)程化其應(yīng)用程序。openmp由編譯指令、函數(shù)庫(kù)及環(huán)境變量所組成。目前，絕大多數(shù)編譯器都支持openmp。本論文首先對(duì)openmp技術(shù)進(jìn)行介紹，接著對(duì)快速排序算法進(jìn)行分析，找出算法中相互獨(dú)立的部分，然后用openmp寫(xiě)出相應(yīng)的程序代碼。通過(guò)算法分析和程序設(shè)計(jì)加深對(duì)openmp快速排序算法的理解。 第二章 openmp技術(shù)的

29、基本原理2.1引言 可以說(shuō)openmp制導(dǎo)指令將c語(yǔ)言擴(kuò)展為一個(gè)并行語(yǔ)言，但openmp本身不是一種獨(dú)立的并行語(yǔ)言，而是為多處理器上編寫(xiě)并行程序而設(shè)計(jì)的、指導(dǎo)共享內(nèi)存、多線(xiàn)程并行的編譯制導(dǎo)指令和應(yīng)用程序編程接口（api），可在c/c+和fortran中應(yīng)用，并在串行代碼中以編譯器可識(shí)別的注釋形式出現(xiàn)。openmp標(biāo)準(zhǔn)是由一些具有國(guó)際影響力的軟件和硬件廠(chǎng)商共同定義和提出，是一種在共享存儲(chǔ)體系結(jié)構(gòu)的可移植編程模型，廣泛應(yīng)用與unix、linux、windows等多種平臺(tái)上。 本章通過(guò)介紹openmp技術(shù)的基本原理，進(jìn)行詳細(xì)分析。以達(dá)到對(duì)openmp技術(shù)進(jìn)一步了解的目的。2.2openmp技術(shù)的基本

30、概念 要掌握openmp技術(shù)，首先要了解openmp的執(zhí)行模式和三大要素。2.2.1執(zhí)行模式 openmp的執(zhí)行模型采用fork-join的形式，其中fork創(chuàng)建新線(xiàn)程或者喚醒已有線(xiàn)程；join即多線(xiàn)程的會(huì)合。fork-join執(zhí)行模型在剛開(kāi)始執(zhí)行的時(shí)候，只有一個(gè)稱(chēng)為“主線(xiàn)程”的運(yùn)行線(xiàn)程存在。主線(xiàn)程在運(yùn)行過(guò)程中，當(dāng)遇到需要進(jìn)行并行計(jì)算的時(shí)候，派生出線(xiàn)程來(lái)執(zhí)行并行任務(wù)。在并行執(zhí)行的時(shí)候，主線(xiàn)程和派生線(xiàn)程共同工作。在并行代碼執(zhí)行結(jié)束后，派生線(xiàn)程退出或者阻塞，不再工作，控制流程回到單獨(dú)的主線(xiàn)程中。openmp的編程者需要在可并行工作的代碼部分用制導(dǎo)指令向編譯器指出其并行屬性，而且這些并行區(qū)域可以出現(xiàn)

31、嵌套的情況，如圖 2.1所示。下面對(duì)術(shù)語(yǔ)并行域（paralle region）作如下定義：在成對(duì)的fork和join之間的區(qū)域，稱(chēng)為并行域，它既表示代碼也表示執(zhí)行時(shí)間區(qū)間。對(duì)openmp線(xiàn)程作如下定義：在openmp程序中用于完成計(jì)算任務(wù)的一個(gè)執(zhí)行流的執(zhí)行實(shí)體，可以是操作系統(tǒng)的線(xiàn)程也可以是操作系統(tǒng)上的進(jìn)程。2.2.2openmp的編程要素openmp編程模型以線(xiàn)程為基礎(chǔ)，通過(guò)編譯制導(dǎo)指令來(lái)顯式地指導(dǎo)并行化，openmp為編程人員提供了三種編程要素來(lái)實(shí)現(xiàn)對(duì)并行化的完善控制。它們是編譯制導(dǎo)、api函數(shù)集和環(huán)境變量。 編譯制導(dǎo)在c/c+程序中，openmp的所有編譯制導(dǎo)指令是以#pragma omp

32、開(kāi)始，后面跟具體的功能指令（或命令），其具有如下形式：#pragma omp 指令 子句, 子句 支持openmp的編譯器能識(shí)別、處理這些制導(dǎo)指令并實(shí)現(xiàn)其功能。其中指令或命令是可以單獨(dú)出現(xiàn)的，而子句則必須出現(xiàn)在制導(dǎo)指令之后。制導(dǎo)指令和子句按照功能可以大體上分成四類(lèi)： 1）并行域控制類(lèi)； 2）任務(wù)分擔(dān)類(lèi)； 3）同步控制類(lèi)； 4）數(shù)據(jù)環(huán)境類(lèi)。 并行域控制類(lèi)指令用于指示編譯器產(chǎn)生多個(gè)線(xiàn)程以并發(fā)執(zhí)行任務(wù)，任務(wù)分擔(dān)類(lèi)指令指示編譯器如何給各個(gè)并發(fā)線(xiàn)程分發(fā)任務(wù)，同步控制類(lèi)指令指示編譯器協(xié)調(diào)并發(fā)線(xiàn)程之間的時(shí)間約束關(guān)系，數(shù)據(jù)環(huán)境類(lèi)指令處理并行域內(nèi)外的變量共享或私有屬性以及邊界上的數(shù)據(jù)傳送操作等2.3openmp

33、的編譯系統(tǒng)一個(gè)可運(yùn)行的編譯系統(tǒng)不僅僅是一個(gè)編譯轉(zhuǎn)換程序，同時(shí)還是運(yùn)行環(huán)境的支撐系統(tǒng)。本節(jié)將根據(jù)分級(jí)編譯的思想，分析以標(biāo)準(zhǔn)c代碼作為openmp編譯目標(biāo)代碼的原因和優(yōu)勢(shì)。然后給出openmp編譯器通常具備的典型結(jié)構(gòu)和相關(guān)功能模塊的作用。2.3.1編譯系統(tǒng) 編譯系統(tǒng)包括編譯程序（編譯器）和運(yùn)行系統(tǒng)，如果推廣到一般情況，編譯和運(yùn)行并不需要在同一計(jì)算機(jī)上（可以是異構(gòu)的兩臺(tái)計(jì)算機(jī)），此時(shí)我們將源程序、目標(biāo)程序、編譯器、運(yùn)行系統(tǒng)等等要素統(tǒng)一地用圖2.2表示如下。 圖2.2編譯系統(tǒng)示意圖 如果計(jì)算機(jī)a和計(jì)算機(jī)b屬于不同的體系結(jié)構(gòu)，那么這樣的編譯往往稱(chēng)為交叉編譯。運(yùn)行系統(tǒng)主要包含運(yùn)行庫(kù)、環(huán)境變量和一些配置文件

34、等等。由于源語(yǔ)言程序中許多代碼功能可能反復(fù)出現(xiàn)，因此可以先構(gòu)建出具有這些常用功能的運(yùn)行庫(kù)，以此減輕編譯時(shí)的負(fù)擔(dān)。如果語(yǔ)義差距可以量化的話(huà)，圖2.3表示了編譯系統(tǒng)采用運(yùn)行庫(kù)和不采用運(yùn)行庫(kù)時(shí)的編譯難度差別。 圖2.3運(yùn)行系統(tǒng)庫(kù)函數(shù)的語(yǔ)義作用從圖2.3可以看出，運(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ì)。雖然大多數(shù)編譯原理的課程重點(diǎn)都在講述源語(yǔ)言到目標(biāo)語(yǔ)言的語(yǔ)義差距的消除，并講述了實(shí)現(xiàn)上述功能所需的詞法分析、語(yǔ)法分析、中間代碼生成和最終輸出目標(biāo)代碼，但是實(shí)際應(yīng)用中的編譯器，大多都是以帶有運(yùn)行庫(kù)這種形式來(lái)

35、實(shí)現(xiàn)的，因此庫(kù)的設(shè)計(jì)是可運(yùn)行的編譯系統(tǒng)的另一個(gè)重點(diǎn)。編譯器的設(shè)計(jì)必須和運(yùn)行庫(kù)的設(shè)計(jì)同時(shí)進(jìn)行，或者說(shuō)目標(biāo)語(yǔ)言和運(yùn)行庫(kù)功能直接影響編譯器的設(shè)計(jì)。2.3.2目標(biāo)語(yǔ)言 下面我們需要確定openmp編譯的目標(biāo)語(yǔ)言是什么。從源語(yǔ)言到目標(biāo)語(yǔ)言的編譯過(guò)程可以經(jīng)過(guò)多個(gè)中間語(yǔ)言的步驟來(lái)完成的，各個(gè)步驟可以集中處理本階段的問(wèn)題。比如gcc編譯器對(duì)c語(yǔ)言的編譯過(guò)程分為四步：1、預(yù)處理（preprocess）工作：處理宏定義，不管是由-d參數(shù)指定，還是在源碼內(nèi)部通過(guò)#define，或者使用了標(biāo)準(zhǔn)庫(kù)、擴(kuò)展庫(kù)中的宏，都會(huì)替換為定義的值。2、編譯（compile）階段：將源代碼（也就是預(yù)處理過(guò)的代碼）編譯為特定機(jī)器的匯編語(yǔ)言

36、。3、匯編（assemble）階段：將匯編源碼匯編為機(jī)器碼內(nèi)容。此處如果有對(duì)外部的函數(shù)調(diào)用，則會(huì)預(yù)留未定義的地址以供最后一步鏈接階段來(lái)填寫(xiě)。4、鏈接（link階段）：將鏈接對(duì)象文件鏈接為可執(zhí)行文件，此過(guò)程比較復(fù)雜，需要鏈接很多外部的庫(kù)文件，包括靜態(tài)的，動(dòng)態(tài)的。從大的步驟上看，可以說(shuō)第一步是將c語(yǔ)言程序編譯成匯編語(yǔ)言程序，然后再將匯編語(yǔ)言程序編譯成機(jī)器碼。這是一個(gè)典型的分級(jí)編譯的例子。openmp編譯也可以分成多個(gè)步驟，在各個(gè)步驟完成不同的編譯任務(wù)。我們將幾種可能的編譯實(shí)現(xiàn)方案用圖2.4表示。圖2.4多種實(shí)現(xiàn)方案示意前三種方式僅僅是在庫(kù)的功能強(qiáng)弱上有所不同，但是編譯目標(biāo)語(yǔ)言都是機(jī)器碼，也就是說(shuō)編

37、譯器需要跨越“openmp編譯制導(dǎo)+c語(yǔ)言”到機(jī)器碼的語(yǔ)義距離。第四種方式首先消除openmp編譯制導(dǎo)的語(yǔ)義差距輸出c代碼，然后再將c代碼編譯成機(jī)器碼，此時(shí)openmp制導(dǎo)指令的編譯和c語(yǔ)言的編譯任務(wù)各自獨(dú)立開(kāi)來(lái)。第五種方式則將c代碼編譯再進(jìn)一步劃分。后面兩種實(shí)現(xiàn)方案的安排有利于分析openmp編譯自身的問(wèn)題。本節(jié)主要討論openmp的編譯。常規(guī)c代碼的編譯已經(jīng)在編譯原理的課程中有詳細(xì)的論述，因此下面將著重第四、第五種實(shí)現(xiàn)方案。這時(shí)候c代碼的編譯可以借助于現(xiàn)有的多種編譯器。如果采用gcc作為其中的c語(yǔ)言編譯器的話(huà)其過(guò)程將是第五種方案（雖然gcc本身具備有openmp編譯能力，可通過(guò)命令行參數(shù)上

38、的編譯開(kāi)關(guān)“-fopenmp”打開(kāi)相應(yīng)的編譯能力），可用圖2.5描述其過(guò)程。圖2.5openmp編譯與c編譯任務(wù)劃分這樣一來(lái)，openmp編譯的目標(biāo)代碼為標(biāo)準(zhǔn)c代碼，這些c代碼再經(jīng)過(guò)c編譯器生成機(jī)器碼形式的可執(zhí)行文件，這個(gè)可執(zhí)行文件運(yùn)行中還需要openmp運(yùn)行庫(kù)等運(yùn)行環(huán)境的支持。此時(shí)openmp編譯稱(chēng)為狹義的openmp編譯。2.3.3openmp編譯器結(jié)構(gòu)狹義的openmp編譯器的功能是將帶有openmp編譯制導(dǎo)的c代碼翻譯成標(biāo)準(zhǔn)c代碼，因此它和所有編譯器一樣具有相似的結(jié)構(gòu)，即有典型的八個(gè)部件構(gòu)成，它們分別是詞法分析、語(yǔ)法分析、語(yǔ)義分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成、信息表管理和錯(cuò)誤

39、處理，構(gòu)成如圖2.6所示的系統(tǒng)。圖2.6編譯器通用結(jié)構(gòu)從邏輯上，上面的各個(gè)功能模塊完成了編譯過(guò)程中的一個(gè)步驟（phrase），每個(gè)步驟都將源程序從一種表示輸出為另一種表示。下面就這八個(gè)功能模塊和執(zhí)行流程分別進(jìn)行簡(jiǎn)單的分析討論。詞法分析程序詞法分析（lexicalanalysis）或掃描（scanning）是編譯器最前端的輸入模塊，它將源代碼文件中的一個(gè)長(zhǎng)長(zhǎng)的字符串，逐個(gè)識(shí)別為有意義的詞素（lexeme）或單詞符號(hào)，并轉(zhuǎn)變?yōu)楸阌趦?nèi)部處理的格式來(lái)保存。通常詞法掃描器的工作任務(wù)有：識(shí)別出源程序中的各個(gè)基本語(yǔ)法單位（通常稱(chēng)為單詞或語(yǔ)法符號(hào)）；刪除無(wú)用的空白字符、回車(chē)字符以及其他與語(yǔ)言無(wú)直接關(guān)系的非實(shí)質(zhì)

40、性字符；刪除注釋行；進(jìn)行詞法檢查并報(bào)告所發(fā)現(xiàn)的錯(cuò)誤。對(duì)于識(shí)別出來(lái)的單詞，可以用形如（class,value）的二元式來(lái)表示，其中class是一個(gè)整數(shù)代碼用來(lái)指示該單詞的類(lèi)別，value則是單詞的取值。由于openmp制導(dǎo)指令里面的關(guān)鍵詞（保留字）和c語(yǔ)言的關(guān)鍵詞有重疊的地方，比如“if”既是c語(yǔ)言條件語(yǔ)句中的關(guān)鍵字，又是openmp編譯制導(dǎo)中的條件子句的關(guān)鍵字。因此在詞法分析過(guò)程中，實(shí)際上要同時(shí)分析c語(yǔ)言單詞和openmp編譯制導(dǎo)的單詞，并進(jìn)行甄別。openmp制導(dǎo)指令中的關(guān)鍵詞包括pragma、omp、parallel等等，數(shù)量并不多，因此openmp/c編譯器的詞法分析和普通c語(yǔ)言的詞法分

41、析大體相同。語(yǔ)法分析程序語(yǔ)法分析（syntaxanalysis）或解析（parsing）程序需要借助于前面的詞法分析，將詞法分析輸出的內(nèi)部編碼格式表示的單詞序列嘗試構(gòu)建出一個(gè)符合語(yǔ)法規(guī)則的完整語(yǔ)法樹(shù)。如果無(wú)法成功建立起一個(gè)合法的語(yǔ)法樹(shù)，則由錯(cuò)誤處理模塊輸出相應(yīng)的語(yǔ)法錯(cuò)誤信息。這棵樹(shù)的葉子節(jié)點(diǎn)就是源程序中的各個(gè)單詞，中間的節(jié)點(diǎn)則是程序設(shè)計(jì)語(yǔ)言的相關(guān)語(yǔ)法構(gòu)造名。產(chǎn)生語(yǔ)法樹(shù)的過(guò)程可以大致分為自頂向下和自底向上兩大類(lèi)?，F(xiàn)有的最常用的兩種方法是分別屬于這兩大類(lèi)的遞歸下降法和算符優(yōu)先法。前者根據(jù)語(yǔ)言中各語(yǔ)法范疇有文法遞歸定義的特點(diǎn)，用一組相互遞歸的子程序來(lái)完成語(yǔ)法分析；后者則利用各個(gè)算符間的優(yōu)先關(guān)系和結(jié)合

42、規(guī)則來(lái)制導(dǎo)語(yǔ)法分析，因而特別適合于分析各種表達(dá)式。這兩種方法比較簡(jiǎn)單便于實(shí)現(xiàn)，許多編譯器都或多或少地采用過(guò)這兩種方法對(duì)于表達(dá)式可采用算符優(yōu)先分析法，對(duì)于語(yǔ)言的其他部分可以采用遞歸下降分析法。對(duì)openmp/c程序代碼的分析工作，需要根據(jù)openmp的語(yǔ)法規(guī)則和c語(yǔ)言的語(yǔ)法規(guī)則的相關(guān)文法描述來(lái)進(jìn)行。通常的編程語(yǔ)言可以用前后文無(wú)關(guān)文法（cfg）或與之等價(jià)的backs-naur范式（bnf）來(lái)描述，從而整個(gè)語(yǔ)法分析過(guò)程能夠按照此種描述機(jī)械地進(jìn)行，所以可以直接借用工具軟件來(lái)完成。對(duì)于前面提到的語(yǔ)法樹(shù)，可以真的用一個(gè)樹(shù)形結(jié)構(gòu)將所分析的語(yǔ)法成分表達(dá)出來(lái)，也可以是按照這個(gè)樹(shù)形的語(yǔ)法樹(shù)思路逐步進(jìn)行語(yǔ)法分析而不

43、用建立起整個(gè)語(yǔ)法樹(shù)。語(yǔ)義分析程序語(yǔ)義分析（semanticanalysis）是在前面進(jìn)行了語(yǔ)法分析后，接著需要對(duì)編程語(yǔ)言的第二個(gè)特征屬性語(yǔ)義特征進(jìn)行分析。語(yǔ)法特征描述的是各個(gè)語(yǔ)法元素之間的連接形式或結(jié)構(gòu)，語(yǔ)義特征表征的是各個(gè)語(yǔ)法成分的含義和功能，包括這些語(yǔ)法元素的屬性或執(zhí)行時(shí)應(yīng)進(jìn)行的運(yùn)算或操作。例如對(duì)openmp編譯制導(dǎo)指令行的語(yǔ)法分析結(jié)束后，只是獲得了相應(yīng)的元素類(lèi)型和排列順序，但是具體是需要生成并行域還是需要進(jìn)行同步操作，則是語(yǔ)義分析的范疇。由于至今還沒(méi)有找到一種公認(rèn)的方法來(lái)系統(tǒng)地描述編程語(yǔ)言的語(yǔ)義，實(shí)際上使用的方法是：采用一種半機(jī)械化的方法來(lái)解決語(yǔ)義分析方面的問(wèn)題。當(dāng)前主流的方法是一種稱(chēng)為

44、“語(yǔ)法制導(dǎo)翻譯”的方法，這種方法把編譯程序的語(yǔ)法分析和語(yǔ)義分析有機(jī)的結(jié)合起來(lái)同時(shí)完成。如果使用yacc語(yǔ)法分析工具，可以方便地將語(yǔ)義動(dòng)作結(jié)合進(jìn)語(yǔ)法分析過(guò)程中。openmp編譯過(guò)程中需要建立的ast中間表示就是在語(yǔ)法分析過(guò)程中結(jié)合語(yǔ)義動(dòng)作來(lái)建立的。中間代碼生成首先需要注意區(qū)分此處的中間代碼與前面的分級(jí)編譯中的“中間語(yǔ)言”的區(qū)別。雖然前面介紹的c語(yǔ)言和匯編語(yǔ)言從廣義上講也是某種形式的“中間代碼”，但是它們都是明確的可使用的真實(shí)語(yǔ)言并屬于編譯器的輸出目標(biāo)代碼。而此處說(shuō)的中間代碼指的是編譯器未輸出目標(biāo)代碼之前在內(nèi)部使用的一種源代碼的等價(jià)表示。中間代碼的生成是與語(yǔ)義分析緊密聯(lián)系的。但是由于迄今為止未有公

45、認(rèn)的形式化系統(tǒng)來(lái)描述編程語(yǔ)言的語(yǔ)義，所以對(duì)中間代碼的生成工作仍需要在一定程度上憑借經(jīng)驗(yàn)來(lái)完成。如果采用語(yǔ)法制導(dǎo)翻譯的編譯器，通常做法是將產(chǎn)生中間代碼的工作交給語(yǔ)義過(guò)程來(lái)完成。每當(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)的中間代碼。目前常見(jiàn)的中間代碼形式有逆波蘭表示、三元式、四元式以及樹(shù)形結(jié)構(gòu)等等。因?yàn)闃?shù)形的ast保留了源代碼的語(yǔ)法層次結(jié)構(gòu)，作為中間表示在源代碼變換上具有優(yōu)勢(shì)。這種先將源程序翻譯為某種形式的中間代碼，然后再將其翻譯為目標(biāo)代碼的方法，可以使編譯程序前后兩部分功能更加單一，邏輯結(jié)構(gòu)更加清晰，從而使得編譯程序

46、更易于編寫(xiě)與調(diào)整，也為代碼優(yōu)化和編譯器移植創(chuàng)造了條件。通常將中間代碼的生成作為編譯器的前后端分界線(xiàn)，將中間代碼生成之前的部分稱(chēng)為編譯器的前端（frontend），中間代碼生成之后的部分稱(chēng)為后端（backend），這兩部分可用圖2.7表示。前端需要將源程序分解為多個(gè)獨(dú)立的組成要素，并在這些要素上重建語(yǔ)法結(jié)構(gòu)并輸出其中間表示，其間收集的有關(guān)信息需要存放到符號(hào)表中。后端根據(jù)中間表示和符號(hào)表來(lái)構(gòu)造和輸出目標(biāo)代碼。圖2.7編譯器前后端劃分代碼優(yōu)化程序代碼優(yōu)化是為了提供更高質(zhì)量目標(biāo)代碼，該工作常常在中間代碼生成和目標(biāo)代碼輸出之間插入一個(gè)代碼優(yōu)化處理的階段來(lái)實(shí)現(xiàn)。根據(jù)目標(biāo)代碼的目標(biāo)期望不同，優(yōu)化方法也相應(yīng)不

47、同，有的是以運(yùn)行時(shí)間為標(biāo)準(zhǔn)越快越好，有的是以存儲(chǔ)空間開(kāi)銷(xiāo)為標(biāo)準(zhǔn)占用內(nèi)存越少越好。優(yōu)化工作可以分為與機(jī)器體系結(jié)構(gòu)相關(guān)的優(yōu)化和與機(jī)器體系結(jié)構(gòu)無(wú)關(guān)的優(yōu)化。進(jìn)行代碼優(yōu)化的代價(jià)是增加了編譯程序本身的時(shí)間復(fù)雜度和降低可靠性（系統(tǒng)可靠性隨復(fù)雜度上升而下降）。對(duì)速度的優(yōu)化目標(biāo)可能會(huì)不利于存儲(chǔ)空間的優(yōu)化目標(biāo)，因此對(duì)各項(xiàng)優(yōu)化目標(biāo)應(yīng)當(dāng)進(jìn)行權(quán)衡。如果只是對(duì)openmp程序進(jìn)行源代碼到源代碼的變換，可以采用的編譯優(yōu)化技術(shù)并不多，很多傳統(tǒng)編譯器優(yōu)化技術(shù)（特別是體系結(jié)構(gòu)相關(guān)的優(yōu)化技術(shù)）并不能在這里應(yīng)用。但是對(duì)于運(yùn)行環(huán)境，其可優(yōu)化的地方就較多，例如對(duì)于numa架構(gòu)的機(jī)器，openmp線(xiàn)程的數(shù)據(jù)分配以及線(xiàn)程對(duì)處理器核的綁定等等

48、，都是當(dāng)前性能優(yōu)化的熱點(diǎn)。目標(biāo)代碼生成目標(biāo)代碼的生成是以語(yǔ)義分析（也可能加上優(yōu)化處理）產(chǎn)生的中間代碼作為輸入的，它將中間代碼翻譯為最終形式的目標(biāo)代碼。這個(gè)翻譯轉(zhuǎn)換過(guò)程，需要確定源語(yǔ)言的的各種語(yǔ)法成分（或中間代碼的各種結(jié)構(gòu)）對(duì)應(yīng)的目標(biāo)代碼結(jié)構(gòu)，該結(jié)構(gòu)稱(chēng)為“框架”?？蚣鼙容^固定，它是用目標(biāo)代碼形式描述的，但是有某些待定部分，需要在生成具體的目標(biāo)代碼時(shí)，根據(jù)各語(yǔ)法成分的確切形式和參數(shù)來(lái)確定的。對(duì)框架代碼的要求做到：目標(biāo)代碼盡可能簡(jiǎn)潔、有較高的執(zhí)行效率。由于我們選定c語(yǔ)言為openmp編譯的目標(biāo)代碼，所以也要求相應(yīng)的c框架代碼要做到簡(jiǎn)潔和高效。狹義的openmp編譯只是源代碼級(jí)的變換，因此編譯原理課程

49、中講述的目標(biāo)代碼生成技術(shù)并不完全適用。例如為了生成可執(zhí)行文件時(shí)，代碼生成中的三個(gè)主要任務(wù)：指令選擇、寄存器分配和指派、指令排序，在源代碼轉(zhuǎn)換工作中都不存在。由于openmp并行語(yǔ)義是串行的c語(yǔ)言中沒(méi)有的特性，因此需要在目標(biāo)代碼產(chǎn)生過(guò)程中進(jìn)行翻譯變換，通過(guò)源代碼變換的同時(shí)結(jié)合底層的線(xiàn)程庫(kù)來(lái)實(shí)現(xiàn)openmp的并行語(yǔ)義，這是openmp編譯的翻譯變換重點(diǎn)所在。信息表管理程序在編譯過(guò)程中總是需要收集、記錄或查詢(xún)?cè)闯绦蛑谐霈F(xiàn)的各種量的有關(guān)屬性信息，因此編譯程序需要建立和維護(hù)多個(gè)不同用途的表格（例如常數(shù)表、變量名、循環(huán)層次等等），這些表格統(tǒng)稱(chēng)為符號(hào)表。在編譯過(guò)程中，造表和查表工作由一系列程序（或函數(shù)）來(lái)完

50、成，它們并不是獨(dú)立的存在而是安插在編譯程序的相關(guān)功能代碼中。錯(cuò)誤處理由于編程人員不可避免的會(huì)寫(xiě)出有錯(cuò)誤的代碼，一個(gè)可用的編譯器必須能夠發(fā)現(xiàn)大多數(shù)常見(jiàn)錯(cuò)誤，并能準(zhǔn)確地報(bào)告出錯(cuò)誤在源代碼中的位置，否則就沒(méi)有使用價(jià)值。由于編譯系統(tǒng)的各個(gè)部分都可能需要程序來(lái)診斷問(wèn)題，所以錯(cuò)誤處理代碼是廣泛分布于編譯器的各個(gè)角落，在需要的地方進(jìn)行檢查和診斷并報(bào)告錯(cuò)誤所在。2.4小結(jié)本章介紹了openmp編譯的基本原理。簡(jiǎn)單分析了相應(yīng)的編譯器的基本構(gòu)件：詞法分析模塊、語(yǔ)法分析模塊、語(yǔ)義分析模塊、中間代碼生成、代碼優(yōu)化模塊、目標(biāo)代碼生成以及符號(hào)表管理和錯(cuò)誤檢查。其中詞法分析中要注意openmp與c語(yǔ)言共用關(guān)鍵字的區(qū)分，語(yǔ)法

51、分析程序需要能在c語(yǔ)法基礎(chǔ)之上識(shí)別openmp制導(dǎo)指令的語(yǔ)法，中間代碼選取ast以便保留源代碼的語(yǔ)法層次結(jié)構(gòu)，目標(biāo)代碼生成中需要翻譯openmp的并行語(yǔ)義。通過(guò)簡(jiǎn)單的介紹，在復(fù)習(xí)編譯原理的基礎(chǔ)之上初步了解openmp編譯所涉及的幾個(gè)問(wèn)題，形成初步的概念。 第三章openmp的快速排序算法分析與程序設(shè)計(jì)3.1引言 快速排序算法比其他任何算法都要應(yīng)用廣泛，在排序算法中是最流行，最實(shí)用的。其原因是它易于實(shí)現(xiàn)，能夠很好地適用于不同的輸入數(shù)據(jù)，而且在很多場(chǎng)合它的消耗的資源比其他任何排序的方法都少。在計(jì)算機(jī)上實(shí)現(xiàn)時(shí)，一個(gè)精心編制的快速排序版本比其他任何排序方法要快很多?？焖倥判虮粡V泛用作庫(kù)排序工具，而且還

52、被應(yīng)用于其他意義重大的應(yīng)用中。 在第三章當(dāng)中，首先會(huì)列舉主要的幾個(gè)排序算法進(jìn)行比較說(shuō)明。然后再對(duì)快速排序算法進(jìn)行總體分析，以便能更好地了解其性能特點(diǎn)。最后進(jìn)行程序編碼，通過(guò)實(shí)踐來(lái)加深對(duì)本課題的掌握。3.2排序算法的分析與比較3.2.1排序算法的概念 在計(jì)算機(jī)科學(xué)與數(shù)學(xué)中，一個(gè)排序算法（sorting algorithm）是一種能將一串?dāng)?shù)據(jù)依照特定排序方式的一種算法。最常用到的排序方式是數(shù)值順序以及字典順序。有效的排序算法在一些算法（例如搜索算法與合并算法）中是重要的，如此這些算法才能得到正確解答。排序算法也用在處理文字?jǐn)?shù)據(jù)以及產(chǎn)生人類(lèi)可讀的輸出結(jié)果。基本上，排序算法的輸出必須遵守下列兩個(gè)原則：

53、1.輸出結(jié)果為遞增串行（遞增是針對(duì)所需的排序順序而言）2.輸出結(jié)果是原輸入的一種排列、或是重組排序(sorting) 是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)關(guān)鍵字有序的序列。穩(wěn)定度（穩(wěn)定性）一個(gè)排序算法是穩(wěn)定的，就是當(dāng)有兩個(gè)有相等關(guān)鍵的紀(jì)錄r和s，且在原本的列表中r出現(xiàn)在s之前，在排序過(guò)的列表中r也將會(huì)是在s之前。當(dāng)相等的元素是無(wú)法分辨的，比如像是整數(shù)，穩(wěn)定度并不是一個(gè)問(wèn)題。然而，假設(shè)以下的數(shù)對(duì)將要以他們的第一個(gè)數(shù)字來(lái)排序。（4,1）（3,1）（3,7）（5,6）在這個(gè)狀況下，有可能產(chǎn)生兩種不同的結(jié)果，一個(gè)是依照相等的鍵值維持相對(duì)的次序，

54、而另外一個(gè)則沒(méi)有：（3,1）（3,7）（4,1）（5,6） （維持次序)（3,7）（3,1）（4,1）（5,6） （次序被改變)不穩(wěn)定排序算法可能會(huì)在相等的鍵值中改變紀(jì)錄的相對(duì)次序，但是穩(wěn)定排序算法從來(lái)不會(huì)如此。不穩(wěn)定排序算法可以被特別地實(shí)現(xiàn)為穩(wěn)定。作這件事情的一個(gè)方式是人工擴(kuò)充鍵值的比較，如此在其他方面相同鍵值的兩個(gè)對(duì)象間之比較，就會(huì)被決定使用在原先數(shù)據(jù)次序中的條目，當(dāng)作一個(gè)同分決賽。然而，要記住這種次序通常牽涉到額外的空間負(fù)擔(dān)。3.2.2排序算法的分類(lèi)比較 排序算法有多個(gè)不同的類(lèi)型，接下來(lái)將舉出最主要的幾種算法，描述它們的特點(diǎn)進(jìn)行比較。一 直接插入排序：每次從無(wú)序表中取出第一個(gè)元素，把它插入到有序表的合適位置，使有序表仍然有序。 第一趟比較前兩個(gè)數(shù),然后把第二個(gè)數(shù)按大小插