編譯原理簡明教程（第3版）-課件 第11、12章 面向?qū)ο笳Z言的編譯、并行編譯技術(shù)

新工科建設(shè)·計(jì)算機(jī)類系列教材

免費(fèi)提供編譯原理1學(xué)分：編譯原理簡明教程（第3版）馮秀芳

崔冬華

王會(huì)青

主編電子工業(yè)出版社

2024年出版課程教材6目錄第一章概述第二章形式語言理論基礎(chǔ)第三章自動(dòng)機(jī)理論基礎(chǔ)第四章詞法分析第五章語法分析—自頂向下分析方法第六章語法分析—自底向上分析方法第七章語義分析及中間代碼的生成第八章代碼優(yōu)化第九章目標(biāo)代碼的生成第十章符號(hào)表和出錯(cuò)處理第十一章面向?qū)ο笳Z言的編譯第十二章

并行編譯技術(shù)第十三章

軟件構(gòu)造32024/11/64學(xué)習(xí)目標(biāo)11面向?qū)ο笳Z言的編譯

了解和掌握面向?qū)ο蟮幕靖拍?、類和成員的屬性構(gòu)造以及面向?qū)ο缶幾g器的特性了解和掌握面向?qū)ο笳Z言的編譯了解和掌握面向?qū)ο蟮膭?dòng)態(tài)存儲(chǔ)分配

目錄11.1概述11.2面向?qū)ο笳Z言的語法結(jié)構(gòu)11.3面向?qū)ο蟮膭?dòng)態(tài)存儲(chǔ)分配511.1概述611.1.1面向?qū)ο笳Z言的基本特征對(duì)象之間通過消息相互通信封裝繼承多態(tài)性

11.1概述711.1.2類和成員的屬性構(gòu)造聲明類的文法規(guī)則：

(1)dec→classdec(2)classdec→classclass_id{memberspec}|classclass_id:class_id{memberspec}(3)memberspec→memberdecmemberspec|memberdec(4)memberdec→accessspec:typevar;|accessspec:funcdec;(5)accessspec→private|protected|public(6)type→comtype|classtype(7)classtype→ID(8)var→ID|ObjDef(9)funcdec→typeID(paramlist);|typeID(paramlist)funcbody;|ID(paramlist);|ID(paramlist)procbody;類名的屬性和結(jié)構(gòu)

8

類名的特有屬性包括種類、繼承鏈和類的成員集。(1)種類：種類屬性用于區(qū)分有效類、延遲類、繼承類、基類等。如果一個(gè)類定義的全部成員中至少有一個(gè)成員尚未被具體實(shí)現(xiàn)，該類就是一個(gè)不能用來創(chuàng)建對(duì)象的類，我們稱之為延遲類。如果一個(gè)類定義中的全部成員都已經(jīng)按照某種方式具體實(shí)現(xiàn)，該類就是一個(gè)可以用來創(chuàng)建對(duì)象的類，我們稱之為有效類。類名的屬性和結(jié)構(gòu)

9

類名的特有屬性包括種類、繼承鏈和類的成員集。(2)繼承鏈：對(duì)于繼承類來說，可以有若干個(gè)父類(被直接繼承的類)，并且它們?cè)陬惖亩x中的次序必須是嚴(yán)格確定的

。類名的屬性和結(jié)構(gòu)

10

這兩個(gè)成員集的具體實(shí)現(xiàn)有兩種方式：①這些成員(包括屬性和方法)名的符號(hào)表項(xiàng)與它們的類名的符號(hào)表項(xiàng)放在一張符號(hào)表中，而這兩個(gè)成員集中存放的是指向各自對(duì)應(yīng)的符號(hào)表項(xiàng)的指針；②每個(gè)類構(gòu)造兩張子符號(hào)表，即類的屬性成員符號(hào)表和類的方法成員符號(hào)表，這兩個(gè)成員集中存放這些成員名的符號(hào)表項(xiàng)。類名的特有屬性包括種類、繼承鏈和類的成員集。(3)類成員集：類具有屬性成員和方法成員，可以用兩張成員表來表示。類成員名的屬性及其結(jié)構(gòu)

11

類的定義中，屬性成員是某個(gè)類型的實(shí)例，這種屬性成員的類型有兩種方式：其一，定義該屬性成員的類型在包含該成員的類型之外的另一個(gè)類型中進(jìn)行定義；其二，定義該屬性成員的類型在包含該成員的類型之內(nèi)的一個(gè)嵌套的類型定義。如果屬性成員的類型嵌套定義在屬性成員所在的類中，屬性的結(jié)構(gòu)就會(huì)出現(xiàn)嵌套的情況，為了避免下推處理，當(dāng)一個(gè)類中有多個(gè)嵌套類型定義的屬性成員時(shí)，這些局部定義的類型名的符號(hào)表項(xiàng)可以組成一張符號(hào)表，類成員名的屬性及其結(jié)構(gòu)

12

類成員的特有屬性如下。①類成員的導(dǎo)入屬性。通常，類中的成員包括從父類繼承的成員和該類自定義的成員，當(dāng)從父類中繼承的成員被重定義或重命名時(shí)，需要給出相應(yīng)的標(biāo)志。類成員名的屬性及其結(jié)構(gòu)

13

②類成員的訪問權(quán)限屬性。類成員被外部對(duì)象訪問的權(quán)限有三種：類的公有成員、類的私有成員和類的保護(hù)成員。屬性和方法的私有性是由編譯器的類型檢查階段來保證的，在類的成員符號(hào)表項(xiàng)中，一個(gè)域用來指出該成員的訪問權(quán)限。類成員名的屬性及其結(jié)構(gòu)

14

③類成員的延遲屬性。如果一個(gè)類定義的全部成員中至少有一個(gè)成員尚未被具體實(shí)現(xiàn)，該類就是一個(gè)不能用來創(chuàng)建對(duì)象的類，我們稱之為延遲類，尚未被具體實(shí)現(xiàn)的成員，我們稱之為延遲成員。在成員符號(hào)表項(xiàng)中用一個(gè)域指出該成員是類的延遲成員，還是類的有效成員。11.1.3面向?qū)ο缶幾g程序的特點(diǎn)

15

詞法和語法分析

由于類本身是一種數(shù)據(jù)類型，它也作為符號(hào)表中的一個(gè)表項(xiàng)，但面向?qū)ο蠼＞哂休^高的抽象層次，其語義處理與語法分析的關(guān)系更密切，整個(gè)分析流程、編譯程序內(nèi)部數(shù)據(jù)結(jié)構(gòu)的組織和運(yùn)行時(shí)的環(huán)境都和傳統(tǒng)的編譯程序有一定差別。語義分析

由于類及其對(duì)象具有的封裝、繼承、多態(tài)性等語言特征，不僅使靜態(tài)語義分析更為復(fù)雜，也使運(yùn)行時(shí)環(huán)境更為復(fù)雜。

內(nèi)存管理

11.2面向?qū)ο笳Z言的語法結(jié)構(gòu)1611.2.1單一繼承

1．屬性編譯在僅支持單繼承的語言中，每個(gè)類最多只能繼承一個(gè)父類，子類不僅可以訪問該類中定義的新方法，還可以訪問父類中的方法?？梢圆捎孟旅鎯煞N方式處理。①簡單的前綴技術(shù)來處理。如果類B是由類A擴(kuò)展得到的，則將類B中從父類A繼承過來的屬性放在類B符號(hào)表的開始處，并保持這些屬性與類A符號(hào)表中相同的順序；而類B中定義的特有屬性放在繼承屬性的后面。②在符號(hào)表中，對(duì)子類進(jìn)行處理時(shí)，僅給出在子類中直接定義的屬性，而對(duì)父類中定義的成員，則通過在子類的符號(hào)表項(xiàng)中增加指向父類的指針來表示，當(dāng)需要對(duì)父類屬性進(jìn)行相關(guān)處理時(shí)，可根據(jù)此指針獲取父類的相關(guān)信息。11.2面向?qū)ο笳Z言的語法結(jié)構(gòu)1711.2.1單一繼承

2．方法編譯編譯一個(gè)方法類似于編譯一個(gè)過程：方法被轉(zhuǎn)換成駐存在指令空間中一個(gè)特定地址的機(jī)器代碼。在語義分析階段，每個(gè)對(duì)象的符號(hào)表項(xiàng)中有一個(gè)指向其類符號(hào)表的指針，每個(gè)類的符號(hào)表有一個(gè)指向其父類的指針和一張方法的鏈表，每一個(gè)方法都有一個(gè)地址。①對(duì)于靜態(tài)方法，一些面向?qū)ο笳Z言允許將方法聲明為靜態(tài)的，調(diào)用c.f(

)(其中c是類C的對(duì)象)時(shí)執(zhí)行的機(jī)器代碼取決于變量c的類型。

②對(duì)于動(dòng)態(tài)方法，如果類B中的方法f是從父類A中繼承的，且類B對(duì)方法f進(jìn)行了重載，則編譯期間，調(diào)用f時(shí)無法確定是類B的一個(gè)對(duì)象還是類A的一個(gè)對(duì)象。為了解決該問題，類符號(hào)表必須包含一個(gè)向量，該向量中每個(gè)方法名對(duì)應(yīng)一個(gè)方法實(shí)例。

11.2面向?qū)ο笳Z言的語法結(jié)構(gòu)1811.2.2多重繼承在支持多重繼承的語言中，一個(gè)類可以有多個(gè)直接父類。使用多重繼承的目的在于使一個(gè)對(duì)象同時(shí)具有多個(gè)對(duì)象的表達(dá)能力。

例如，假定有類M包含屬性m1、m2和方法f1、f2，類E包含屬性e1和方法f3、f4，類T繼承了類M和類E，但增加了屬性t1，并且重新定義了方法f2、f4，增加了方法f5。

11.2面向?qū)ο笳Z言的語法結(jié)構(gòu)1911.2.3多態(tài)性當(dāng)類B繼承類A并且該語言允許“類B的指針”類型的指針能夠賦值給一個(gè)“類A的指針”類型的變量時(shí)，那么該語言支持多態(tài)性。多態(tài)性的實(shí)現(xiàn)要求一種新的操作，即指針supertyping，它將指向子類B對(duì)象的指針轉(zhuǎn)換為指向其父類A對(duì)象的指針。假定類A有屬性a1、a2和方法f1、f2，類B是類A的子類，類B通過增加屬性b1和方法f3來擴(kuò)展A類，例如：ClassB*b=…;ClassA*a=b;在上面的語句中，第二行代碼被翻譯成ClassA*a=covert_ptr_to_B_to_ptr_to_A(b);11.2面向?qū)ο笳Z言的語法結(jié)構(gòu)2011.2.4動(dòng)態(tài)綁定

動(dòng)態(tài)綁定是語言處理多態(tài)的機(jī)制，類的成員函數(shù)的行為能根據(jù)調(diào)用它的對(duì)象類型自動(dòng)做出適應(yīng)性調(diào)整，而且調(diào)整發(fā)生在程序運(yùn)行時(shí)。假定類A包含屬性a1、a2和方法f1、f2，類B是類A的子類，類B增加屬性b1和方法f3，并重載類A中的方法f2。例如：

a:A；

b:B；a是多態(tài)引用，因而根據(jù)多態(tài)引用規(guī)則：a可引用類B的對(duì)象，對(duì)方法f2的動(dòng)態(tài)綁定情況如下：

a.f2(

)引用類A的對(duì)象時(shí)，綁定類A定義的方法f2；當(dāng)執(zhí)行a:=b之后，綁定類B重新定義的方法f2。

b.f2(

)只能綁定類B重新定義的方法f2。11.2面向?qū)ο笳Z言的語法結(jié)構(gòu)2111.2.4動(dòng)態(tài)綁定

Java語言包括了一種擴(kuò)展，這種擴(kuò)展由所謂的接口組成。接口與類相似，由許多方法說明組成，但接口只有常量和抽象的方法。接口不能像對(duì)象那樣實(shí)例化，但可以聲明接口類型的Java變量，并從它們的接口聲明中調(diào)用方法，該Java變量實(shí)質(zhì)上就是指向?qū)ο蟮闹羔?。編譯程序必須為類所實(shí)現(xiàn)的每一個(gè)接口建立單獨(dú)的符號(hào)表，每個(gè)符號(hào)表只包含該接口聲明中方法的入口，由入口引用對(duì)象類型的方法。

11.3面向?qū)ο蟮膭?dòng)態(tài)存儲(chǔ)分配2211.3.1對(duì)象的存儲(chǔ)區(qū)管理方式對(duì)象的存儲(chǔ)管理采用了3種模型：靜態(tài)存儲(chǔ)區(qū)管理、棧式存儲(chǔ)區(qū)管理、堆式存儲(chǔ)區(qū)管理。在靜態(tài)模型中，程序裝入或開始執(zhí)行時(shí)為所有對(duì)象一次分配所有空間，一個(gè)實(shí)體在整個(gè)軟件運(yùn)行過程中最多只能與一個(gè)運(yùn)行時(shí)對(duì)象聯(lián)系。在棧式模型中，一個(gè)實(shí)體在運(yùn)行時(shí)可以相繼與多個(gè)對(duì)象聯(lián)系，它以先進(jìn)后出的方式分配和釋放對(duì)象。在堆式模式中，存儲(chǔ)分配是完全動(dòng)態(tài)的，對(duì)象通過顯式的請(qǐng)求動(dòng)態(tài)創(chuàng)建，堆式模型最具有通用性，它是面向?qū)ο蟮挠?jì)算所需要的。11.3面向?qū)ο蟮膭?dòng)態(tài)存儲(chǔ)分配2311.3.2靜態(tài)模型和棧式模型廢棄單元的回收在靜態(tài)模型下，每個(gè)對(duì)象只與一個(gè)實(shí)體聯(lián)系，執(zhí)行時(shí)只要實(shí)體存在，就要保留對(duì)象的空間，因此一般情況下靜態(tài)模型不存在廢棄單元回收的問題，在棧式模型下，與某一實(shí)體聯(lián)系的對(duì)象可以在棧中分配。在分程序結(jié)構(gòu)的語言中，聲明實(shí)體的同時(shí)為對(duì)象分配空間，整個(gè)程序可以只使用一個(gè)棧。例如，每當(dāng)執(zhí)行一次函數(shù)調(diào)用時(shí)，就將該函數(shù)運(yùn)行所需的所有局部變量進(jìn)棧，在棧頂為該函數(shù)建立運(yùn)行的工作區(qū)，并且每當(dāng)一個(gè)函數(shù)執(zhí)行結(jié)束時(shí)，它在棧頂?shù)墓ぷ鲄^(qū)退棧，該函數(shù)運(yùn)行所占用的空間得到了釋放，釋放的空間回收后可提供給下次調(diào)用的函數(shù)使用。11.3面向?qū)ο蟮膭?dòng)態(tài)存儲(chǔ)分配2411.3.3堆式模型廢棄單元的回收

堆中分配且通過任何程序變量形成的指針鏈都無法到達(dá)的對(duì)象稱為不可到達(dá)的對(duì)象。不可到達(dá)的對(duì)象是廢棄單元，需要回收。廢棄單元的回收不是由編譯器完成的，而是由運(yùn)行時(shí)系統(tǒng)完成的，運(yùn)行時(shí)系統(tǒng)是與編譯好的代碼連接在一起的一些支持程序。廢棄單元回收技術(shù)主要有：標(biāo)記-清掃技術(shù)引用計(jì)數(shù)技術(shù)復(fù)制式收集分代收集11.3面向?qū)ο蟮膭?dòng)態(tài)存儲(chǔ)分配2511.3.3堆式模型廢棄單元的回收1、標(biāo)記-清掃技術(shù)實(shí)體和堆分配的對(duì)象構(gòu)成了一個(gè)有向圖，每一個(gè)實(shí)體是圖中的一個(gè)根。如果從某個(gè)根節(jié)點(diǎn)r出發(fā)，存在由有向邊r→…→n組成的一條路徑，則稱這個(gè)結(jié)點(diǎn)n是可到達(dá)的對(duì)象，圖搜索算法可以標(biāo)記出所有可到達(dá)的對(duì)象。2、引用計(jì)數(shù)技術(shù)每一個(gè)對(duì)象都設(shè)置了一個(gè)統(tǒng)計(jì)量，用于對(duì)該對(duì)象的引用進(jìn)行計(jì)數(shù)，該統(tǒng)計(jì)量稱為對(duì)象的引用計(jì)數(shù)。它與每個(gè)對(duì)象存儲(chǔ)在一起，當(dāng)該引用計(jì)數(shù)為0時(shí)，對(duì)象可以被回收。

引用計(jì)數(shù)技術(shù)實(shí)現(xiàn)簡單，但它存在兩個(gè)主要的問題。①無法回收構(gòu)成環(huán)的垃圾；②增加引用計(jì)數(shù)所需的操作代價(jià)(時(shí)間和空間)非常大。11.3面向?qū)ο蟮膭?dòng)態(tài)存儲(chǔ)分配2611.3.3堆式模型廢棄單元的回收

3、復(fù)制式收集堆中的可到達(dá)部分是一個(gè)有向圖，堆中的對(duì)象是圖中的結(jié)點(diǎn)，指針是圖中的邊，每一個(gè)原對(duì)象在圖中是一個(gè)根。復(fù)制式垃圾收集遍歷這個(gè)圖(稱為源空間)，并在堆的新區(qū)域(稱為目標(biāo)空間)建立一個(gè)同構(gòu)的副本。副本目標(biāo)空間是緊湊的，它占據(jù)連續(xù)的、不含碎片的存儲(chǔ)單元。原來指向源空間的所有的根在復(fù)制之后變成指向目標(biāo)空間副本，在此之后，整個(gè)源空間便成為不可達(dá)的。11.3面向?qū)ο蟮膭?dòng)態(tài)存儲(chǔ)分配2711.3.3堆式模型廢棄單元的回收

4、分代收集將堆劃分成若干“代”，最年輕的(即最近分配的)對(duì)象屬于G0代，所有屬于G1代的對(duì)象都比G0代的對(duì)象“老”，所有屬于G2代的對(duì)象都比G1代的對(duì)象“老”，依次類推。為了只收集G0代中的對(duì)象，回收器只需要從根結(jié)點(diǎn)開始進(jìn)行深度優(yōu)先標(biāo)記或?qū)挾葍?yōu)先復(fù)制。這些根不僅僅是原對(duì)象，其中還包括G1，G2，…中那些指向G0中對(duì)象的指針。為了避免在所有的G1，G2，…中搜索G0的各個(gè)根節(jié)點(diǎn)，讓編譯好的程序記住這種從老對(duì)象指向新對(duì)象的指針。

28總結(jié)

本章我們學(xué)習(xí)了面向?qū)ο笳Z言的編譯、面向?qū)ο蟮膭?dòng)態(tài)存儲(chǔ)分配等內(nèi)容。

下一章將學(xué)習(xí)編譯的其他新技術(shù)------并行編譯技術(shù)。THANKS29THANKS新工科建設(shè)·計(jì)算機(jī)類系列教材

免費(fèi)提供編譯原理306目錄第一章概述第二章形式語言理論基礎(chǔ)第三章自動(dòng)機(jī)理論基礎(chǔ)第四章詞法分析第五章語法分析—自頂向下分析方法第六章語法分析—自底向上分析方法第七章語義分析及中間代碼的生成第八章代碼優(yōu)化第九章目標(biāo)代碼的生成第十章符號(hào)表和出錯(cuò)處理第十一章

面向?qū)ο笳Z言的編譯第十二章并行編譯技術(shù)第十三章

軟件構(gòu)造312024/11/632學(xué)習(xí)目標(biāo)學(xué)習(xí)編譯程序的概念工作過程、體系結(jié)構(gòu)語言與編譯程序的關(guān)系了解開發(fā)技術(shù)12并行編譯技術(shù)Parallelcompilationtechnology重點(diǎn)：編譯程序的概念、編譯程序的結(jié)構(gòu)難點(diǎn)：編譯程序的開發(fā)技術(shù)

目錄12.1并行計(jì)算機(jī)及其編譯系統(tǒng)簡介12.2并行程序設(shè)計(jì)模型12.3并行編譯系統(tǒng)的構(gòu)造12.4自動(dòng)并行化技術(shù)研究現(xiàn)狀12.5本章小結(jié)3312.1并行計(jì)算機(jī)及其

編譯系統(tǒng)簡介34為實(shí)現(xiàn)高性能并行計(jì)算，并行系統(tǒng)通常采用兩種形式：

①程序設(shè)計(jì)人員編寫常規(guī)的串行應(yīng)用程序，由編譯器將其轉(zhuǎn)換為并行目標(biāo)代碼執(zhí)行。

②按照某種并行語法規(guī)范編寫相應(yīng)的并行程序，由并行語言編譯器將其編譯轉(zhuǎn)換為并行目標(biāo)代碼執(zhí)行。本章在介紹并行編譯系統(tǒng)之前，先給出并行計(jì)算相關(guān)技術(shù)的一些介紹，然后再針對(duì)不同體系結(jié)構(gòu)的目標(biāo)機(jī)器介紹并行編譯系統(tǒng)實(shí)現(xiàn)的分類及結(jié)構(gòu)。12.1.1并行計(jì)算相關(guān)技術(shù)簡介35并行性：在同一時(shí)刻或同一時(shí)間間隔內(nèi)完成兩種或兩種以上的任務(wù)。并行性有兩種含義：同時(shí)性和并發(fā)性。并行粒度：衡量軟件進(jìn)程所含計(jì)算量的尺度，一般用細(xì)、中、粗粒度來描述。時(shí)延：機(jī)器各子系統(tǒng)間通信開銷的時(shí)間量度，如存儲(chǔ)時(shí)延和同步時(shí)延。

并行處理技術(shù)通過處理開發(fā)過程中的并行事件，使并行性達(dá)到較高水平，涉及并行結(jié)構(gòu)、并行軟件和并行算法等多個(gè)方面，這些方面相互聯(lián)系，互為條件，互為保證。12.1.1并行計(jì)算相關(guān)技術(shù)簡介36并行等級(jí)的分類：?

從計(jì)算機(jī)信息加工的步驟和階段的角度看：

存儲(chǔ)器操作并行

處理器操作步驟并行

處理器操作并行

指令、任務(wù)、作業(yè)并行?從開發(fā)程序的大小和并行粒度的角度看：

作業(yè)級(jí)

任務(wù)級(jí)

例行程序或子程序級(jí)

循環(huán)和迭代級(jí)

語句和指令級(jí)粗粒度中粒度細(xì)粒度通信需求與調(diào)度開銷并行程度12.1.1并行計(jì)算相關(guān)技術(shù)簡介37并行處理：并行處理指的是在并行計(jì)算機(jī)上實(shí)現(xiàn)并行計(jì)算。

并行體系結(jié)構(gòu)（基礎(chǔ)）并行軟件系統(tǒng)并行程序設(shè)計(jì)向量計(jì)算機(jī)共享存儲(chǔ)器并行計(jì)算機(jī)分布存儲(chǔ)器并行計(jì)算機(jī)并行系統(tǒng)軟件并行應(yīng)用軟件并行體系結(jié)構(gòu)并行系統(tǒng)軟件并行程序設(shè)計(jì)語言并行算法12.1.2并行編譯系統(tǒng)的分類及結(jié)構(gòu)38并行編譯系統(tǒng)的分類：

?不具有自動(dòng)并行化功能的系統(tǒng)

?具有自動(dòng)并行化功能的系統(tǒng)并行編譯系統(tǒng)的結(jié)構(gòu)向量編譯技術(shù)并行編譯技術(shù)

并行運(yùn)行庫技術(shù)并行編譯技術(shù)程序并行化技術(shù)依賴關(guān)系分析技術(shù)體系結(jié)構(gòu)內(nèi)在特性3912.1.2并行編譯系統(tǒng)的分類及結(jié)構(gòu)并行編譯技術(shù)可按以下兩種方法來分類：4012.2并行程序設(shè)計(jì)模型

如同匯編程序員必須熟悉機(jī)器指令集一樣，在了解并行體系結(jié)構(gòu)的基礎(chǔ)上才能更好地理解和掌握并行程序設(shè)計(jì)模型以及并行編譯系統(tǒng)。本節(jié)簡要介紹并行計(jì)算機(jī)體系結(jié)構(gòu)的三種類型以及相應(yīng)并行編譯系統(tǒng)需要解決的問題。12.2.1并行體系結(jié)構(gòu)分類及并行程序設(shè)計(jì)

并行計(jì)算機(jī)體系結(jié)構(gòu)大致可分為向量計(jì)算機(jī)、共享存儲(chǔ)器多處理機(jī)以及分布式存儲(chǔ)器并行計(jì)算機(jī)三類。41不同體系結(jié)構(gòu)不同程序并行設(shè)計(jì)方法12.2.2并行程序設(shè)計(jì)模型

并行程序設(shè)計(jì)模型是指在特定計(jì)算機(jī)硬件體系結(jié)構(gòu)上實(shí)現(xiàn)并行算法的方式。421.數(shù)據(jù)并行模型?核心特征：以數(shù)據(jù)為中心，通過對(duì)數(shù)據(jù)的劃分和并行處理來解決問題。?編程方式：提供全局地址空間，編程者只需指明并行操作和對(duì)象，無需關(guān)心并行執(zhí)行的具體方式。?適用場(chǎng)景：適用于數(shù)據(jù)并行問題，如數(shù)組運(yùn)算。?實(shí)現(xiàn)方式：可以在SIMD(單指令流多數(shù)據(jù)流)計(jì)算模型和SPMD(單程序流多數(shù)據(jù)流)計(jì)算模型上實(shí)現(xiàn)。?優(yōu)勢(shì)：編程相對(duì)簡單，表達(dá)簡潔。?局限：僅適用于數(shù)據(jù)并行問題12.2.2并行程序設(shè)計(jì)模型432.消息傳遞模型?核心特征：用戶必須通過顯式發(fā)送和接收消息來實(shí)現(xiàn)處理機(jī)間的數(shù)據(jù)交換。?編程方式：每個(gè)并行實(shí)體有獨(dú)立地址空間，遠(yuǎn)程訪問必須通過顯式消息傳遞實(shí)現(xiàn)。?適用場(chǎng)景：適合開發(fā)大粒度的并行性，如分布式內(nèi)存的并行機(jī)。?實(shí)現(xiàn)方式：以消息傳遞庫的形式實(shí)現(xiàn)，用戶使用現(xiàn)有編程語言調(diào)用庫函數(shù)進(jìn)行消息傳遞。?優(yōu)勢(shì)：靈活，可以解決廣泛的問題。?局限：增加了編程者的負(fù)擔(dān)，編程級(jí)別較低。12.2.2并行程序設(shè)計(jì)模型443.共享存儲(chǔ)模型?核心特征：進(jìn)程通過讀/寫共享存儲(chǔ)器中的公共變量相互通信。?編程方式：具有單一全局名字空間，數(shù)據(jù)為所有處理機(jī)所共享，進(jìn)程間通信通過對(duì)全局變量的存取實(shí)現(xiàn)。?適用場(chǎng)景：適合多線程和異步處理。?實(shí)現(xiàn)方式：常用的共享存儲(chǔ)器編程標(biāo)準(zhǔn)包括線程庫標(biāo)準(zhǔn)和OpenMP標(biāo)準(zhǔn)。?優(yōu)勢(shì)：提供了簡單的編程模式。?局限：可擴(kuò)展性較差，存儲(chǔ)器帶寬可能成為瓶頸。12.2.2并行程序設(shè)計(jì)模型4512.3并行編譯系統(tǒng)的構(gòu)造46源代碼程序分析程序優(yōu)化并行代碼生成12.3.1并行編譯系統(tǒng)的構(gòu)造簡介4712.3.2程序分析程序分析是并行編譯系統(tǒng)的主要組成部分之一，目的是找出可以在不同節(jié)點(diǎn)上并行執(zhí)行的計(jì)算。程序分析是否深入透徹，直接關(guān)系到并行轉(zhuǎn)換后程序的執(zhí)行效率。48為保持程序語義所絕對(duì)需要的固有次序依賴關(guān)系數(shù)據(jù)依賴關(guān)系控制依賴關(guān)系數(shù)據(jù)依賴關(guān)系控制依賴關(guān)系12.3.2程序分析49依賴關(guān)系分析：分析計(jì)算程序中所有語句之間的依賴關(guān)系依賴關(guān)系的分析問題線性丟番圖方程的求解問題12.3.2程序分析50?

精確測(cè)試算法：實(shí)際求出方程組的整數(shù)通解，并檢查是否有滿足所有約束條件的解。適用于依賴關(guān)系存在時(shí)，可以給出相關(guān)迭代對(duì)集合和依賴距離向量，但不能處理復(fù)雜情況。?近似測(cè)試算法：檢查方程組是否有整數(shù)解，然后測(cè)試方程組滿足約束條件的實(shí)數(shù)解存在的某些必要條件。如果必要條件不滿足，則不存在依賴關(guān)系；否則，假設(shè)依賴關(guān)系存在。這種方法是保守的，可以保證程序的正確性，但可能因保守假設(shè)而損失一些并行性。依賴關(guān)系的測(cè)試：構(gòu)造依賴距離向量或依賴方向向量的全集。此全集可以表達(dá)對(duì)同一數(shù)組變量任意下標(biāo)引用對(duì)之間可能存在的依賴關(guān)系。12.3.3程序優(yōu)化程序優(yōu)化是指對(duì)解決同一問題的幾個(gè)不同的程序進(jìn)行比較、修改、調(diào)整或重新編寫程序，把一般程序變換為語句最少、占用內(nèi)存最少、處理速度最快、外部設(shè)備分時(shí)使用效率最高的最優(yōu)程序。51?

代碼向量化：把標(biāo)量程序由一種可向量化循環(huán)完成的操作變換成向量操作。?

代碼并行化：將串行程序的可并行化部分展開成多線程，以同時(shí)供多臺(tái)處理機(jī)并行執(zhí)行，其目的是減少總的執(zhí)行時(shí)間。12.3.4并行代碼生成52

并行代碼生成：將優(yōu)化后的中間形式的代碼轉(zhuǎn)換成可執(zhí)行的具體的機(jī)器目標(biāo)代碼。并行語義的識(shí)別和處理向量化編譯器的并行代碼生成

?

向量循環(huán)的組織：并行編譯器自動(dòng)尋找并向量化源程序中的循環(huán)。

?

寄存器分配：減少不必要的訪存操作，加快程序執(zhí)行速度。

?

流水線調(diào)度：重排代碼序列，優(yōu)化向量操作指令，提高功能部件的執(zhí)行效率。

12.3.4并行代碼生成53共享存儲(chǔ)器多處理機(jī)的并行代碼生成

?預(yù)編譯器：處理并行語言、并行制導(dǎo)命令的語法語義分析，實(shí)現(xiàn)并行制導(dǎo)命令功能的程序改寫和并行庫調(diào)用。

?棧式存儲(chǔ)分配：實(shí)現(xiàn)程序副本的可再入，每個(gè)任務(wù)調(diào)用時(shí)獲得自己的私有變量空間。分布存儲(chǔ)器大規(guī)模并行機(jī)的并行代碼生成

?

數(shù)據(jù)分布：提高數(shù)據(jù)局部性和并行性，減少通訊開銷。

?

任務(wù)劃分：將源程序任務(wù)劃分為可并行的子任務(wù)，并分配到多個(gè)處理機(jī)上執(zhí)行。

?

同步與通信：處理并行任務(wù)之間的數(shù)據(jù)交換，包括確定同步與通信點(diǎn)、插入并行庫子程序調(diào)用以及通信優(yōu)化

12.4自動(dòng)并行化技術(shù)研究現(xiàn)狀

自動(dòng)并行編譯系統(tǒng)研究的難點(diǎn)主要有以下幾個(gè)方面：54①程序并行性的挖掘②合理的數(shù)據(jù)分布③通信優(yōu)化

本節(jié)介紹幾個(gè)典型的自動(dòng)并行化系統(tǒng)以及自動(dòng)并行化編譯的近期發(fā)展。12.4.1比較典型的自動(dòng)并行化系統(tǒng)簡介551.VAST系統(tǒng)-循環(huán)以外部分的檢查-循環(huán)并行部分和循環(huán)以外并行部分向大粒度并行塊的合并-微任務(wù)偽指令的插入2.KAP系統(tǒng)-循環(huán)結(jié)構(gòu)變換-增大并行粒度-降低同步頻度和過程的分支-過程的在線展開-并行循環(huán)和循環(huán)以外并行部分的檢查-微任務(wù)偽指令的插入3.PFC(ParallelFortranConverter)

將Fortran77代碼變換成Fort