OpenMP畢設論文

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

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

3、，平均情況進行總體分析。最后對快速排序，基于歸并的快速排序，雙倍快速排序舉例進行程序編碼，通過實踐編程來加深對本課題知識的掌握。關鍵字：openmp，并行程序，多線程共享，庫函數(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技術的現(xiàn)狀與發(fā)展趨勢 1 1.2.1并行發(fā)展史1 1.2.2openmp技術的現(xiàn)狀概述 3 1.2.3openmp技術的發(fā)展方向 4 1.3openmp技術的的優(yōu)缺點 4 1.4本論文研究的內(nèi)容 6第二章openmp技術的基本原理 7 2.1引言 7 2.2openmp技術的基本概念7 2.2.1執(zhí)行模式7 2.2.2openmp的編程要素82.3openmp的編譯系統(tǒng)8 2.3.1編譯系統(tǒng)8 2.3.2目標語言 10 2.3.3openmp編譯器結(jié)構122.4小結(jié)16第三章openm

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

34、等等。由于源語言程序中許多代碼功能可能反復出現(xiàn)，因此可以先構建出具有這些常用功能的運行庫，以此減輕編譯時的負擔。如果語義差距可以量化的話，圖2.3表示了編譯系統(tǒng)采用運行庫和不采用運行庫時的編譯難度差別。 圖2.3運行系統(tǒng)庫函數(shù)的語義作用從圖2.3可以看出，運行系統(tǒng)的庫函數(shù)相當于是目標語言的語義擴展，其功能強弱，直接影響到對源語言進行彌補語義差距的難度，因此設計一定的運行庫將有利于簡化編譯器設計。雖然大多數(shù)編譯原理的課程重點都在講述源語言到目標語言的語義差距的消除，并講述了實現(xiàn)上述功能所需的詞法分析、語法分析、中間代碼生成和最終輸出目標代碼，但是實際應用中的編譯器，大多都是以帶有運行庫這種形式來

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

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

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

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

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

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

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

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

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

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

45、認的形式化系統(tǒng)來描述編程語言的語義，所以對中間代碼的生成工作仍需要在一定程度上憑借經(jīng)驗來完成。如果采用語法制導翻譯的編譯器，通常做法是將產(chǎn)生中間代碼的工作交給語義過程來完成。每當一個語義過程被執(zhí)行以便對相應的語法結(jié)構進行語義分析時，它就根據(jù)此語法結(jié)構的語義，并結(jié)合在分析時獲得的語義信息，產(chǎn)生相應的中間代碼。目前常見的中間代碼形式有逆波蘭表示、三元式、四元式以及樹形結(jié)構等等。因為樹形的ast保留了源代碼的語法層次結(jié)構，作為中間表示在源代碼變換上具有優(yōu)勢。這種先將源程序翻譯為某種形式的中間代碼，然后再將其翻譯為目標代碼的方法，可以使編譯程序前后兩部分功能更加單一，邏輯結(jié)構更加清晰，從而使得編譯程序

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

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

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

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

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

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

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

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

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