編譯原理討論課報(bào)告

1、燕山大學(xué) 編譯原理課程討論課報(bào)告 題目：編譯技術(shù)的過去現(xiàn)在未來（第 12組） 學(xué) 院信息學(xué)院 年級專業(yè) 學(xué)生姓名 12計(jì)算機(jī)科學(xué)與技術(shù) 朱禹銘 應(yīng)用2班、 所完成工作量 20 張浩楠 應(yīng)用2班、 所完成工作量 20 王毅龍 應(yīng)用2班 所完成工作量 15 史萬春 應(yīng)用2班 所完成工作量 15 甄曉德 應(yīng)用2班 所完成工作量 10 張政 應(yīng)用2班 所完成工作量 10 池辰 應(yīng)用2班 所完成工作量 10 指導(dǎo)教師 報(bào)告日 張世輝 期2014 年 11 月 20 日 我們的討論課的題目是 編譯技術(shù)的過去、現(xiàn)在和將來。 其中又有3個(gè)小 題目分別是(1)早期的編譯技術(shù)(2)目前流行的編譯技術(shù)(3)未來的編

2、譯技 術(shù)。接下來我們的報(bào)告也將分為這三方面進(jìn)行。 一、編譯技術(shù)的過去 編譯技術(shù)的過去主要分成三部分，首先是編譯技術(shù)出現(xiàn)的必要性，幾種 當(dāng)時(shí)的編譯原理和編譯器的發(fā)展。我們將編譯器的發(fā)展作為了主要部分。并 且附加上國內(nèi)的編譯器發(fā)展。 1. 編譯技術(shù)出現(xiàn)的必要性 在20世紀(jì)40年代，由于馮諾伊曼在存儲-程序計(jì)算機(jī)方面的先鋒作用， 編寫一串代碼或程序已成必要，這樣計(jì)算機(jī)就可以執(zhí)行所需的計(jì)算。開始時(shí)， 這些程序都是用機(jī)器語言(machine Ianguage )編寫的。機(jī)器語言就是表示 機(jī)器實(shí)際操作的數(shù)字代碼，例如： C7 06 0000 0002表示在IBM PC上使用的 In tel 8x86 處理

3、器將數(shù)字2移至地址0 0 0 0(16進(jìn)制)的指令。 但編寫這樣的代碼是十分費(fèi)時(shí)和乏味的，這種代碼形式很快就被匯編語 言(assembly Ianguage )代替了。在匯編語言中，都是以符號形式給出指 令和存儲地址的。例如，匯編語言指令MOVX,2就與前面的機(jī)器指令等價(jià)(假 設(shè)符號存儲地址X是0 0 0 0)。匯編程序(assembler )將匯編語言的符 號代碼和存儲地址翻譯成與機(jī)器語言相對應(yīng)的數(shù)字代碼。 匯編語言大大提高了編程的速度和準(zhǔn)確度，人們至今仍在使用著它，在 編碼需要極快的速度和極高的簡潔程度時(shí)尤為如此。但是，匯編語言也有許 多缺點(diǎn)：編寫起來也不容易，閱讀和理解很難；而且匯編語言

4、的編寫嚴(yán)格依 賴于特定的機(jī)器，所以為一臺計(jì)算機(jī)編寫的代碼在應(yīng)用于另一臺計(jì)算機(jī)時(shí)必 須完全重寫。 發(fā)展編程技術(shù)的下一個(gè)重要步驟就是以一個(gè)更類似于數(shù)學(xué)定義或自然語 言的簡潔形式來編寫程序的操作，它應(yīng)與任何機(jī)器都無關(guān)，而且也可由一個(gè) 程序翻譯為可執(zhí)行的代碼。例如，前面的匯編語言代碼可以寫成一個(gè)簡潔的 與機(jī)器無關(guān)的形式x = 2。 第一個(gè)編譯程序的出現(xiàn)是在20世紀(jì)50年代早期，很難講出確切的時(shí)間，因?yàn)楫?dāng)初大 量的實(shí)驗(yàn)和實(shí)現(xiàn)工作是由不同的小組獨(dú)立完成的，多數(shù)早期的編譯工作是將算術(shù)公式翻譯 成機(jī)器代碼。用現(xiàn)在的標(biāo)準(zhǔn)來衡量，當(dāng)時(shí)的編譯程序能完成的工作十分初步，如只允許簡 單的單目運(yùn)算，數(shù)據(jù)元素的命名方式有很

5、多限制。然而它們奠定了對高級語言編譯系統(tǒng)的 研究和開發(fā)的基礎(chǔ)。20世紀(jì)50年代中期出現(xiàn)了 FORTRAIN批高級語言，相應(yīng)的一批 編譯系統(tǒng)開發(fā)成功。隨著編譯技術(shù)的發(fā)展和社會對編譯程序需求的不斷增長，20世纟己50 年代末有人開始研究編譯程序的自動生成工具，提出并研制編譯程序的編譯程序。它的 功能是以任一語言的詞法規(guī)則、語法規(guī)則和語義解釋出發(fā)，自動產(chǎn)生該語言的編譯程序。 20世紀(jì)60年代起，不斷有人使用自展技術(shù)來構(gòu)造編譯程序。自展的主要特征是用 被編譯的語言來書寫該語言自身的編譯程序。 1971年，PASCAL勺編譯程序用自展技術(shù)生成后，其影響就越來越大。在70年代后 期和80年代早期，大量的項(xiàng)

6、目都貫注于編譯器其它部分的生成自動化，這其中就包括 了代碼生成。這些嘗試并未取得多少成功，這大概是因?yàn)椴僮魈珡?fù)雜而人們又對其不甚了 解。 2. 幾種當(dāng)時(shí)流行的編譯語言 1）Fortra n 語言 Fortra n源自于“公式翻譯”（英語：FormulaTra nslation ）的縮寫，是一種編程語 言。它是世界上最早出現(xiàn)的計(jì)算機(jī)高級程序設(shè)計(jì)語言，廣泛應(yīng)用于科學(xué)和工程計(jì)算領(lǐng)域。 FORTRAN言以其特有的功能在數(shù)值、科學(xué)和工程計(jì)算領(lǐng)域發(fā)揮著重要作用。Fortran 90 之前的版本是人們所知曉的FORTRAN全部字母大寫），從Fortran 90以及以后的版本都 寫成Fortran （僅有第一

7、個(gè)字母大寫）。 Fortra n語言的最大特性是接近數(shù)學(xué)公式的自然描述，在計(jì)算機(jī)里具有很高的執(zhí)行效 率。易學(xué)，語法嚴(yán)謹(jǐn)。可以直接對矩陣和復(fù)數(shù)進(jìn)行運(yùn)算，這一點(diǎn)類似MATLAB自誕生以來 廣泛地應(yīng)用于數(shù)值計(jì)算領(lǐng)域，積累了大量高效而可靠的源程序。很多專用的大型數(shù)值運(yùn)算 計(jì)算機(jī)針對Fortran做了優(yōu)化。廣泛地應(yīng)用于并行計(jì)算和高性能計(jì)算領(lǐng)域。Fortran 90 ， Fortran 95，F(xiàn)ortran 2003的相繼推出使Fortran語言具備了現(xiàn)代高級編程語言的一些特 性。 2）Pascal 語言 Pascal是一種計(jì)算機(jī)通用的高級程序設(shè)計(jì)語言。它由瑞士Niklaus Wirth教授于 六十年代末

8、設(shè)計(jì)并創(chuàng)立。 以法國數(shù)學(xué)家命名的Pascal語言現(xiàn)已成為使用最廣泛的基于 DOS勺語言之一，其主 要特點(diǎn)有：嚴(yán)格的結(jié)構(gòu)化形式；豐富完備的數(shù)據(jù)類型；運(yùn)行效率高；查錯(cuò)能力強(qiáng)。 正因?yàn)樯鲜鎏攸c(diǎn)，Pascal語言可以被方便地用于描述各種算法與數(shù)據(jù)結(jié)構(gòu)。尤其是對 于程序設(shè)計(jì)的初學(xué)者，Pascal語言有益于培養(yǎng)良好的程序設(shè)計(jì)風(fēng)格和習(xí)慣。IOI（國際奧林 匹克信息學(xué)競賽）把Pascal語言作為三種程序設(shè)計(jì)語言之一，NOI（全國奧林匹克信息學(xué) 競賽）把Pascal語言定為唯一提倡的程序設(shè)計(jì)語言，在大學(xué)中Pascal語言也常常被用作 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的教學(xué)語言。 在PascaI問世以來的三十余年間，先后產(chǎn)生了

9、適合于不同機(jī)型的各種各樣版本。其 中影響最大的莫過于Turbo Pascal系列軟件。它是由美國Borland公司設(shè)計(jì)、研制的一 種適用于微機(jī)的Pascal編譯系統(tǒng)。該編譯系統(tǒng)由1983年推出1.0版本發(fā)展到1992年推 出的7.0版本，其版本不斷更新，而功能更趨完善。 3. 編譯器的發(fā)展 1.編譯器的發(fā)展 編譯器就是將“高級語言”翻譯為“機(jī)器語言(低級語言)”的程序。一個(gè)現(xiàn)代編譯 器的主要工作流程：源代碼(sourcecode)預(yù)處理(preprocessor) 編譯器(compiler) 匯編程序(assembler)目標(biāo)代碼(object code)鏈接器(Linker)可執(zhí)行程序 (e

10、xecutables)。編譯器將源程序(Source program)作為輸入，翻譯產(chǎn)生使用目標(biāo)語言 (TargetIanguage ) 的等價(jià)程序。源代碼一般為高級語 言 (High-levelIanguage), 如 Pascal、CC C+ C# Java 等，而目標(biāo)語言則是匯 編語言或目標(biāo)機(jī)器的目標(biāo)代碼 (Object code)，有時(shí)也稱作機(jī)器代碼(Machine code)。 Chomsky的研究導(dǎo)致了根據(jù)語言文法的難易程度以及識別它們所需要的算法來對語 言分類。正如現(xiàn)在所稱的 Chomsky架構(gòu)(Chomsky Hierarchy )，它包括了文法的四個(gè)層 次：0型文法、1型文法

11、、2型文法和3型文法，且其中的每一個(gè)都是其前者的特殊情況。 2型文法(或上下文無關(guān)文法)被證明是程序設(shè)計(jì)語言中最有用的，而且今天它已代表著 程序設(shè)計(jì)語言結(jié)構(gòu)的標(biāo)準(zhǔn)方式。分析問題(parsingproblem，用于上下文無關(guān)文法識別 的有效算法)的研究是在60年代和70年代，它相當(dāng)完善的解決了這個(gè)問題?，F(xiàn)在它已是 編譯原理中的一個(gè)標(biāo)準(zhǔn)部分 有限狀態(tài)自動機(jī)(Finite Automaton)和正則表達(dá)式(Regular Expression )同上 下文無關(guān)文法緊密相關(guān)，它們與 Chomsky的 3型文法相對應(yīng)。對它們的研究與 Chomsky的 研究幾乎同時(shí)開始，并且引出了表示程序設(shè)計(jì)語言的單詞的

12、符號方式。 人們接著又深化了生成有效目標(biāo)代碼的方法，這就是最初的編譯器，它們被一直使用 至今。人們通常將其稱為優(yōu)化技術(shù)(OptimizationTech nique)，但因其從未真正地得 到過被優(yōu)化了的目標(biāo)代碼而僅僅改進(jìn)了它的有效性，因此實(shí)際上應(yīng)稱作代碼改進(jìn)技術(shù) (Code Improvement Technique )。 當(dāng)分析問題變得好懂起來時(shí)，人們就在開發(fā)程序上花費(fèi)了很大的功夫來研究這一部 分的編譯器自動構(gòu)造。這些程序最初被稱為編譯器的編譯器( Compiler-compiler )，但 更確切地應(yīng)稱為分析程序生成器(Parser Generator)，這是因?yàn)樗鼈儍H僅能夠自動處 理編譯

13、的一部分。這些程序中最著名的是Yacc (Yet Another Compiler-compiler )， 它是由Steve Johnson在1975年為Unix系統(tǒng)編寫的。類似的，有限狀態(tài)自動機(jī)的研究 也發(fā)展了一種稱為掃描程序生成器(Scanner Generator )的工具，Lex (與Yacc同時(shí)， 由Mike Lesk為Unix系統(tǒng)開發(fā))是這其中的佼佼者。 在70年代后期和80年代早期，大量的項(xiàng)目都貫注于編譯器其它部分的生成自動化， 這其中就包括了代碼生成。這些嘗試并未取得多少成功，這大概是因?yàn)椴僮魈珡?fù)雜而人們 又對其不甚了解。編譯器設(shè)計(jì)最近的發(fā)展包括：首先，編譯器包括了更加復(fù)雜算法

14、的應(yīng)用 程序它用于推斷或簡化程序中的信息；這又與更為復(fù)雜的程序設(shè)計(jì)語言的發(fā)展結(jié)合在一 起。其中典型的有用于函數(shù)語言編譯的 Hin dley-Mil ner 類型檢查的統(tǒng)一算法。其次，編 譯器已越來越成為基于窗口的交互開發(fā)環(huán)境(In teractive Developme nt En viro nment， ID E)的一部分，它包括了編輯器、連接程序、調(diào)試程序以及項(xiàng)目管理程序。這樣的 IDE 標(biāo)準(zhǔn)并沒有多少，但是對標(biāo)準(zhǔn)的窗口環(huán)境進(jìn)行開發(fā)已成為方向。另一方面，盡管近年來在 編譯原理領(lǐng)域進(jìn)行了大量的研究，但是基本的編譯器設(shè)計(jì)原理在近20年中都沒有多大的 改變，它現(xiàn)在正迅速地成為計(jì)算機(jī)科學(xué)課程中的中

15、心環(huán)節(jié)。 在九十年代，作為GNI項(xiàng)目或其它開放源代碼項(xiàng)目標(biāo)一部分，許多免費(fèi)編譯器和編譯 器開發(fā)工具被開發(fā)出來。這些工具可用來編譯所有的計(jì)算機(jī)程序語言。它們中的一些項(xiàng)目 被認(rèn)為是高質(zhì)量的，而且對現(xiàn)代編譯理論感興趣的人可以很容易的得到它們的免費(fèi)源代 碼。 大約在1999年，SGI公布了他們的一個(gè)工業(yè)化的并行化優(yōu)化編譯器 Pro64的源代碼， 后被全世界多個(gè)編譯器研究小組用來做研究平臺，并命名為 Open64 Open64的設(shè)計(jì)結(jié)構(gòu) 好，分析優(yōu)化全面，是編譯器高級研究的理想平臺。 2.國內(nèi)編譯器的研發(fā)歷史 早在60年代初期，董韞美院士和楊芙清院士就分別在中科院和北大領(lǐng)導(dǎo)研究組開發(fā) 編譯器，那時(shí)面向的

16、高級語言是 ALGO和 FORTRAN目標(biāo)機(jī)是國產(chǎn)機(jī)。 在改革開放前，由于國家需要，中科院、國防科大、江南計(jì)算所、北大等單位一直在 研制國產(chǎn)計(jì)算機(jī)，包括大型機(jī)和高性能計(jì)算機(jī)(如向量機(jī)、并行機(jī))，相應(yīng)的也在研制高 級語言編譯器。中科院計(jì)算所以董韞美院士領(lǐng)導(dǎo)的研究組先后開發(fā)了119機(jī)、109機(jī)的 類ALGO語言編譯器BCY國防科大開發(fā)了向量編譯器和向量識別器。 70年代中科院計(jì)算所張兆慶教授研究組(以后稱 ACTGrouP開始在國產(chǎn)機(jī)上研制 FORTRA語言編譯器，先后參與了眾多的院級和國家級科研攻關(guān)項(xiàng)目，主持開發(fā)了013， 757, KJ8920等國產(chǎn)大型機(jī)系統(tǒng)中的FORTRA語言編譯器，所研制

17、的編譯器支持了數(shù)百萬 行應(yīng)用軟件的運(yùn)行。 90年代以來ACTGroup承擔(dān)科學(xué)院重大項(xiàng)目，國家攻關(guān)項(xiàng)目，863項(xiàng)目，以及國際合 作項(xiàng)目，先后開發(fā)了共享內(nèi)存多處理機(jī)的并行識別器，分布式內(nèi)存多處理機(jī)的并行識別 器，SIMD芯片和VLIW芯片的并行優(yōu)化C編譯器。將編譯技術(shù)與圖形學(xué)結(jié)合，ACTGroup 還推出了集成化、可視化的并行編程環(huán)境。ACTGroup在先進(jìn)編譯技術(shù)和并行編程環(huán)境方面 的研究工作獲國內(nèi)外專家高度評價(jià)，國際著名學(xué)者評價(jià)此研究組居編譯領(lǐng)域的世界先進(jìn)行 列。 (2)目前流行的編譯技術(shù) 當(dāng)今的編譯技術(shù)飛速發(fā)展，出現(xiàn)越來越多的編譯技術(shù)，并且在實(shí)際應(yīng)用 越來越廣泛。接下來這樣介紹幾種流行的編

18、譯技術(shù)。 1）并行編譯技術(shù) 為了提高計(jì)算機(jī)體系結(jié)構(gòu)的性能滿足超大規(guī)模計(jì)算的日益增長的需求近 幾年并行機(jī)及多處理機(jī)的發(fā)展極其迅速而用戶在這類計(jì)算機(jī)上能獲得的實(shí)際 運(yùn)行速度在相當(dāng)程度上還取決于并行程序設(shè)計(jì)和并行編譯技術(shù)的水平。因此 并行編譯系統(tǒng)已成為現(xiàn)代高性能計(jì)算機(jī)系統(tǒng)中一個(gè)重要的部分。目前處理并 行編譯技術(shù)有以下兩種方法。1利用重構(gòu)技術(shù)將串行程序并行化。 將已有的串 行語言編寫的程序經(jīng)過相關(guān)分析分解成可并行的成分分配到多CPU或多處理 機(jī)上運(yùn)行這種技術(shù)在國內(nèi)已有 FORTRA語言和C語言的并行重構(gòu)處理系統(tǒng)。2 直接編寫并行程序。編寫并行程序要比編寫串行程序的要求高編程者自己必 須知道程序各模塊之

19、間的邏輯結(jié)構(gòu)關(guān)系及調(diào)用關(guān)系以確定哪些模塊可以并行 執(zhí)行。這種直接編寫的并行程序要比利用重構(gòu)技術(shù)改寫的并行程序效率咼。 并行編譯技術(shù)是針對并行機(jī)和并行程序的，是一種實(shí)現(xiàn)多個(gè)處理機(jī)同時(shí)執(zhí)行一個(gè)程序 的技術(shù)。不同的并行程序設(shè)計(jì)技術(shù)要用不同的并行編譯技術(shù)來支持。可以把并行編譯技術(shù) 分成串行程序并行化技術(shù)，并行語言處理技術(shù)，并行程序組織技術(shù)三個(gè)方面。 并行編譯系統(tǒng)的功能 并行編譯系統(tǒng)的功能是將并行源程序轉(zhuǎn)換為并行目標(biāo)代碼?？煞譃橐韵聝深?1. 不具有自動并行功能的系統(tǒng) 2. 具有自動并行化功能的系統(tǒng) 并行編譯系統(tǒng)的結(jié)構(gòu) 串行源程序 并行化工具 向量編譯系統(tǒng)包括向量化工具和向量編譯器。并行編譯系統(tǒng)包括并行

20、化工具，并行編 譯系統(tǒng)和并行運(yùn)行庫等，其結(jié)構(gòu)如下圖所示。 并行化工具可以獨(dú)立于 并行編譯器的，也可以是 嵌入并行編譯器的。 并行運(yùn)行庫 并行源程序 并行源程序 國內(nèi)的并行編譯技術(shù) 90年代以來，國內(nèi)主要以研制并行機(jī)為主，相應(yīng)的并行編譯器研制也在國內(nèi)開展起 來。代表性的成果有：上海復(fù)旦大學(xué)朱傳琪教授研究組研制的面向共享存儲并行機(jī)的并行 優(yōu)化編譯器AFT達(dá)到世界領(lǐng)先水平。清華大學(xué)湯志忠教授研究組在軟流水優(yōu)化技術(shù)上做了 很優(yōu)秀的研究工作。清華大學(xué)鄭緯民教授研究組開發(fā)了交互式并行化系 統(tǒng) TIPSExplorer，北京大學(xué)許卓群教授、李曉明教授研究組在HPF( High Performanee For

21、tran )編譯器方面做了多年工作，取得很好的研究成果。此外，國防科大、江南計(jì)算 所等單位也都有從事并行編譯技術(shù)研究。隨著芯片研制，國內(nèi)還有若干單位也在開展基于 GCC生成面向特定芯片的編譯器工作。 自動并行編譯為并行化現(xiàn)有的串行程序及編寫新的并行程序提供了重要的支持，因此 20多年來一直受到重視。近幾年來，自動并行編譯技術(shù)的研究進(jìn)展，包括在依賴關(guān)系分析， 程序變換，數(shù)據(jù)分布和重分布及調(diào)度等方面的進(jìn)展，將自動并行編譯進(jìn)一步推向了實(shí)用化。 該文介紹了自動并行編譯技術(shù)的最新進(jìn)展，并提出了進(jìn)一步的研究所要解決的問題。 自動并行編譯為充分發(fā)揮并行計(jì)算環(huán)境不斷增強(qiáng)的計(jì)算能力提供了一條重要的途徑I 它有以

22、下優(yōu)點(diǎn)： 1. 在缺乏被普遍接受的并行程序設(shè)計(jì)語言的情況下，自動并行化工具能有效地解決代 碼的可重用和可移植問題； 2. 解決了用一種語言難以顯式地表達(dá)從指令層到任務(wù)層各個(gè)層次的并行性，并進(jìn)行基 于體系結(jié)構(gòu)的優(yōu)化問題。 3. 自動并行化工具為大量存在于應(yīng)用領(lǐng)域的，并經(jīng)過長時(shí)間的設(shè)計(jì)，使用和測試的成 熟大型串行應(yīng)用程序的并行化提供了唯一可行的選擇。 自90年代以來，對自動并行編譯技術(shù)的研究有了很大的進(jìn)展，產(chǎn)生了一批有代表性 的自動并行化系統(tǒng)，國外的有SUIF, polaris;國內(nèi)的有JAPS,FAT通過對這些系統(tǒng)的開發(fā)， 人們提出了很多實(shí)用技術(shù)，涵蓋了數(shù)據(jù)依賴關(guān)系分析，程序變換L數(shù)據(jù)分布及調(diào)度

23、等方面的 內(nèi)容,下面依次對這些技術(shù)作簡要的介紹 依賴關(guān)系分析 循環(huán)體中的依賴關(guān)系分析和過程間依賴關(guān)系分析的質(zhì)量決定了數(shù)據(jù)并行性和任務(wù)并 行性的開發(fā)程度，多年來,它們一直是研究的熱點(diǎn)，近幾年的研究成果更是進(jìn)一步地推動了 自動并行的實(shí)用化指針分析是對c,c+程序并行化不可缺少的工作 循環(huán)體中的依賴關(guān)系分析 循環(huán)占用了串行程序的絕大部分執(zhí)行時(shí)間，因此，對循環(huán)體的依賴關(guān)系分析一直是最 受關(guān)注的.早期的工作主要集中于數(shù)組是線性下標(biāo)的精確方法和運(yùn)行速度足夠快的近似方 法,分析也都是靜態(tài)的因此，在大多數(shù)情況下只能得到保守的結(jié)果.omega test使用整數(shù)規(guī) 劃,綜合得到了速度快且精確的結(jié)果.range t

24、est突破了線性下標(biāo)的限制.RPT和LROT依賴 于輸入.靜態(tài)所不能確定依賴關(guān)系的循環(huán)進(jìn)行了動態(tài)并行化. 另外需要進(jìn)一步研究的問題 開發(fā)通用的編譯器研究平臺，編譯技術(shù)如果脫離了編譯器是沒有意義的，為了使新的 編譯技術(shù)能容易地集成于編譯器上，以便測試和評價(jià)其性能，從而提高編譯器技術(shù)的研究 質(zhì)量及加快研究的進(jìn)展，需要可靠的模塊 B獨(dú)立的編譯器平臺。 1. 收集大量的與實(shí)際應(yīng)用有關(guān)的測試程序，測試編譯技術(shù)離不開測試程序，能夠很好 地刻畫實(shí)際程序性質(zhì)的測試程序?qū)ν七M(jìn)編譯器技術(shù)的發(fā)展具有不可取代的作用。 2. 開發(fā)高效的編譯算法，為了將編譯器的運(yùn)行時(shí)間限制在可接受的范圍內(nèi)，包括依賴 關(guān)系分析問題，多種循

25、環(huán)重構(gòu)技術(shù)的選擇使用和組合問題，數(shù)據(jù)分布的選擇，通信的優(yōu)化, 任務(wù)粒度的動態(tài)控制等問題，都需要更高效的算法處理?？梢钥紤]采用并行算法 3. 開發(fā)自適應(yīng)代碼的產(chǎn)生算法，由于運(yùn)行系統(tǒng)的變化性和程序?qū)斎氲囊蕾?，為了?高加速比，需要開發(fā)產(chǎn)生自動適應(yīng)系統(tǒng)變化和程序輸入的代碼的算法，包括運(yùn)行時(shí)刻的依 賴關(guān)系分析問題，運(yùn)行時(shí)的數(shù)據(jù)分布和動態(tài)調(diào)度的算法。 2）動態(tài)編譯技術(shù) 動態(tài)編譯即運(yùn)行時(shí)編譯運(yùn)行時(shí)的程序變換。由于下述原因面向?qū)ο笳Z 言和技術(shù)在當(dāng)代軟件開發(fā)中的使用已導(dǎo)致較大程度的延遲綁定限制了可供靜 態(tài)編譯器分析的范圍分別編譯和共享庫編譯器不一定能夠看見所有的代碼 有些信息如運(yùn)行時(shí)常量值信息在編譯時(shí)是不能

26、確定的運(yùn)行環(huán)境是不斷變化 的。動態(tài)編譯優(yōu)化利用在運(yùn)行時(shí)提供的信息對程序提供更完全的優(yōu)化。因此 利用動態(tài)編譯技術(shù)可大大擴(kuò)大優(yōu)化范圍從而能夠產(chǎn)生更有效的代碼。目前對 動態(tài)編譯的研究主要集中在3個(gè)方面運(yùn)行時(shí)特定化根據(jù)運(yùn)行時(shí)常量將程序 代碼特定化然后在其中做各種優(yōu)化工作。如常量傳播、循環(huán)展開Justi ntim e編譯主要針對Java程序進(jìn)行的運(yùn)行時(shí)編譯并根據(jù) profiling 收集到的prof ile信息進(jìn)行自適應(yīng)的優(yōu)化動態(tài)的二進(jìn)制代碼轉(zhuǎn)換和優(yōu)化將針對一種體系 結(jié)構(gòu)產(chǎn)生的目標(biāo)碼直接移植到與之不同的另一類體系結(jié)構(gòu)上運(yùn)行。當(dāng)前編譯 器技術(shù)的限制是已有的技術(shù)都已經(jīng)達(dá)到相當(dāng)成熟的階段在此基礎(chǔ)上有重大突 破

27、比較難?，F(xiàn)在的發(fā)展只是各種技術(shù)的綜合或者是針對十分具體的現(xiàn)象進(jìn)行 專門的優(yōu)化達(dá)到加速某種算法模式的目的 3）交叉編譯技術(shù) 一個(gè)高級語言往往需要在不同的目標(biāo)機(jī)上實(shí)現(xiàn)這就提出了如何把已在某 機(jī)器上實(shí)現(xiàn)的一個(gè)高級語言的編譯程序移植到另一個(gè)目標(biāo)機(jī)上的問題。通常 把某個(gè)機(jī)器稱為宿主機(jī)上已有的軟件移植到另一臺器稱為目標(biāo)機(jī)上的過程稱 為移植在移植過程中也常會用到交叉編譯的技術(shù)。由于目標(biāo)機(jī)的指令系統(tǒng)與 宿主機(jī)的指令系統(tǒng)不同編譯程序在宿主機(jī)A上運(yùn)行將應(yīng)用程序的源程序生成 目標(biāo)機(jī)B的代碼這種編譯技術(shù)稱為交叉編譯技術(shù)。嵌入式系統(tǒng)中的應(yīng)用程序 正是借助這樣的編譯程序生成的近年來嵌入式應(yīng)用的迅速增長推動了交叉編 譯技術(shù)

28、的發(fā)展。 編譯技術(shù)的應(yīng)用 1）編譯技術(shù)在反病毒方面的應(yīng)用 被病毒感染的網(wǎng)頁類文件經(jīng)過詞法分析和語法分析就可得到一有限自動機(jī)軟件即虛 擬機(jī)此種方式的查病毒虛擬機(jī)不同于以前虛擬機(jī)查毒方式以前查殺病毒時(shí)的環(huán)境就像一 個(gè)高級機(jī)械手打開、定位、查殺而此種方式則是類似一個(gè)智能探測器打開、分析、查殺。 2）基于編譯技術(shù)的可信賴計(jì)算方法 從源數(shù)據(jù)流區(qū)分部分項(xiàng)逐一調(diào)入表達(dá)式的字符串形式進(jìn)行語法檢查、拼成單詞、生成 逆波蘭式和逆波蘭式的翻譯4個(gè)階段進(jìn)行處理為BS體系結(jié)構(gòu)下的工程招投標(biāo)雙方的標(biāo)底 和標(biāo)書搭建了清單審驗(yàn)的平臺 3）基于編譯技術(shù)的協(xié)議解析方法 基于編譯技術(shù)的協(xié)議解析方法用形式化描述的方法對協(xié)議進(jìn)行描述實(shí)

29、現(xiàn)了與協(xié)議無 關(guān)的協(xié)議解析和處理從而避免了針對不同通信協(xié)議均要編寫相應(yīng)的解析和處理程序使協(xié) 議的解析和處理具有更好的靈活性和普適性。 （3）未來的編譯技術(shù) 未來的編譯技術(shù)向多核和多線程架構(gòu)演變，并且軟件系統(tǒng)正在日益復(fù)雜 化，使解決程序缺陷和安全攻擊問題變得更為迫切。 1. 多核處理器將迅速發(fā)展，異構(gòu)多核處理器也會大量出現(xiàn)并應(yīng)用于越來越多的領(lǐng)域。 從消費(fèi)類電子產(chǎn)品到超級計(jì)算機(jī)，都可能成為異構(gòu)多核處理器大顯身手的用武之地 但是異構(gòu)多核處理器是開發(fā)芯片內(nèi)并行的微處理器，這類處理器的出現(xiàn)并不會引起編 譯技術(shù)中重大的技術(shù)變革，只是給已有的編譯優(yōu)化技術(shù)提出了一些新的約束條件。面向這 些新的約束條件，需要對

30、已有的編譯優(yōu)化技術(shù)在原有的基礎(chǔ)上進(jìn)行進(jìn)一步的研究。 對于異構(gòu)多核體系結(jié)構(gòu)，編譯系統(tǒng)面臨的挑戰(zhàn)仍然圍繞著并行這一主題，從核內(nèi)的指 令級和向量級并行到核之間的線程級和任務(wù)級并行，需要解決的基本問題仍然相同。但是, 在高度集成的過程中，它同時(shí)還允許更緊密的協(xié)同工作、更大和更靈活的交互操作。在開 發(fā)其性能潛力的過程中，需要多種編譯優(yōu)化技術(shù)相互配合。 2. 編譯器將在提升程序的安全性和可靠性方面越來越重要。最近幾年，產(chǎn)品級的編譯 器都沒有理由不提供這些安全保證，至少也應(yīng)該為那些對安全敏感的軟件提供特殊的安全 選項(xiàng)支持。此外，這些支持支持也可以利用一個(gè)相比機(jī)器碼生成更強(qiáng)大的安全和可靠性技 術(shù)保證的強(qiáng)類型虛

31、擬機(jī)來實(shí)現(xiàn)。 1 ）多核處理器編程 -Cost of programming multicore processors 異構(gòu)多核處理器的結(jié)構(gòu)特點(diǎn) 異構(gòu)多核處理器正是針對特定領(lǐng)域問題的特殊性進(jìn)行了處理器核心的異構(gòu)設(shè)計(jì)，即 將典型工作負(fù)載中不同類型的操作進(jìn)行區(qū)分，分別用不同的處理器核來處理，以期獲得整 體上的高性能。 因此，異構(gòu)多核處理器的 結(jié)構(gòu)特征是：片內(nèi)的多個(gè)處理器核按適用性分成多類（通 常是2類）：一類執(zhí)行控制密集的操作；另一類執(zhí)行計(jì)算密集的操作。當(dāng)然，每個(gè)處理器 核并不是僅能執(zhí)行計(jì)算或控制操作，而只是對其中一類操作更適合而已。例如，面向控制 密集操作的處理器核肯定也需要一定的數(shù)值計(jì)算能力，

32、而處理數(shù)據(jù)密集操作的處理器核也 需要能夠完成簡單的控制操作。 面向異構(gòu)多核處理器的編譯技術(shù) 目前，微處理器性能的充分發(fā)揮，越來越依賴于編譯器，異構(gòu)多核處理器更是如此。 對于異構(gòu)多核處理器而言，由于不同結(jié)構(gòu)的處理器核的指令集不同，需要生成在不同處理 器核上執(zhí)行的不同的執(zhí)行碼，因此編譯過程更加復(fù)雜，同時(shí)，為了獲得高性能，對編譯優(yōu) 化技術(shù)的要求也更高。 編譯的一般流程 面向異構(gòu)多核處理器的編譯過程，一般要經(jīng)過如下若干步驟。 1代碼劃分 要把用高級語言編寫的程序編譯成可在異構(gòu)多核處理器上運(yùn)行的執(zhí)行代碼，首先要區(qū) 分哪些代碼在哪類處理器上運(yùn)行。如果這部分工作由編譯器自動完成，往往困難較大，并 且性能低。

33、解決的辦法通常是在源代碼中添加指導(dǎo)語句，以便區(qū)分哪些源代碼所描述的操 作在哪類處理器上運(yùn)行。編譯過程中的代碼劃分工作就是要識別這些指導(dǎo)語句，將在不同 目標(biāo)處理器核上執(zhí)行的代碼分離開，分別進(jìn)行編譯。 2. 分別編譯 這一步工作就是針對需要在不同類型的處理器核上執(zhí)行的代碼，分別調(diào)用面向目標(biāo)處 理器核的編譯器，將其編譯成執(zhí)行代碼。因此，在這一步可能要調(diào)用多個(gè)編譯器。 3. 執(zhí)行代碼的組織 這一步需要解決的問題是，采用什么方式將要在不同處理器核上執(zhí)行的目標(biāo)代碼組織 成一個(gè)操作系統(tǒng)環(huán)境下的運(yùn)行實(shí)體（可執(zhí)行程序）。通常的做法是：運(yùn)行實(shí)體在通用的標(biāo) 量處理器上加載執(zhí)行，而將要在從處理器上執(zhí)行的目標(biāo)碼作為該執(zhí)

34、行實(shí)體（可執(zhí)行程序） 的數(shù)據(jù)段中的一部分或者作為該執(zhí)行實(shí)體運(yùn)行時(shí)讀取的數(shù)據(jù)文件。 經(jīng)過以上3步，就完成了用戶代碼到執(zhí)行程序的編譯過程。在運(yùn)行過程中多個(gè)處理器 核之間的協(xié)同常常還需要運(yùn)行時(shí)系統(tǒng)提供支持。 向異構(gòu)多核處理器的關(guān)鍵編譯技術(shù)有以下幾個(gè)方面。 1.面向SIMD結(jié)構(gòu)的編譯 SIMM構(gòu)是能充分利用處理器上大量的功能部件進(jìn)行大規(guī)模數(shù)據(jù)并行計(jì)算的典型結(jié) 構(gòu)。面向這種結(jié)構(gòu)，通常采用自動向量化編譯技術(shù)。自動向量化是自動并行化的一種，盡 管自動并行化相當(dāng)困難，但僅僅面向程序中進(jìn)行數(shù)據(jù)密集計(jì)算的循環(huán)來進(jìn)行自動向量化是 可行的。早在向量并行計(jì)算機(jī)為主流并行計(jì)算系統(tǒng)的時(shí)代，就已經(jīng)開始了對自動向量化技 術(shù)的研

35、究，如今已經(jīng)有了相當(dāng)多的積累。采用SIMD結(jié)構(gòu)的異構(gòu)多核處理器的出現(xiàn)，又進(jìn) 一步推動了自動向量化編譯技術(shù)研究的發(fā)展。 2 通信調(diào)度 異構(gòu)多核處理器芯片內(nèi)的通信包含多個(gè)層次：單個(gè)從處理器內(nèi)多個(gè)ALU15之間的數(shù)據(jù) 傳遞、多個(gè)從處理器核之間的數(shù)據(jù)傳遞以及整個(gè)芯片內(nèi)多個(gè)處理器核之間的數(shù)據(jù)傳遞。 為了最大限度地開發(fā)異構(gòu)多核處理器的并行性能，這些通信往往都暴露給編譯器，由 編譯器根據(jù)對程序行為的分析來控制這些數(shù)據(jù)傳遞。 異構(gòu)多核處理器中，多個(gè)從處理器核之間的通信以及整個(gè)芯片內(nèi)多個(gè)處理器核心之間 的通信也有多種實(shí)現(xiàn)結(jié)構(gòu)，面向特定的通信實(shí)現(xiàn)結(jié)構(gòu)在編譯時(shí)進(jìn)行優(yōu)化是異構(gòu)多核處理器 編譯優(yōu)化技術(shù)的重要方面。 3

36、片上多處理器訪存調(diào)度 處理器和存儲器的速度差距一直是計(jì)算機(jī)系統(tǒng)的性能瓶頸，異構(gòu)多核處理器也是如 此。進(jìn)行訪存調(diào)度來優(yōu)化存儲訪問的局部性一直是編譯優(yōu)化研究的重點(diǎn)內(nèi)容之一。 異構(gòu)多核處理器存儲層次設(shè)計(jì)的趨勢是各個(gè)存儲層次的管理越來越多地暴露給軟件 （主要是編譯器），如軟件管理的緩存、軟件管理的便簽式存儲器（Scratch Pad Memory 以及軟件可見的存儲體分配等等。 2.復(fù)雜軟件系統(tǒng)的安全性和可靠性-Security and reliability of complex software systems 檢查程序中的編碼缺陷一直都是編譯器的一項(xiàng)重要任務(wù)。在幫助程序編寫方面，高級 語言既能簡化計(jì)算的表達(dá)方式，也能幫助識別各種常見的編程錯(cuò)誤，包括使用未聲明的變 量，以及通過日益復(fù)雜的類型檢查機(jī)制能檢測的各種語義錯(cuò)誤。但要希望編譯器幫助避免 錯(cuò)誤的運(yùn)行結(jié)果以及各種安全隱患，我們還能而且必須在程序分析方面