新工科建設·計算機類系列教材

免費提供編譯原理16目錄第一章概述第二章形式語言理論基礎第三章自動機理論基礎第四章詞法分析第五章語法分析—自頂向下分析方法第六章語法分析—自底向上分析方法第七章語義分析及中間代碼的生成第八章代碼優化第九章目標代碼的生成第十章符號表和出錯處理第十一章

面向對象語言的編譯第十二章并行編譯技術第十三章

軟件構造22024/11/63學習目標學習編譯程序的概念工作過程、體系結構語言與編譯程序的關系了解開發技術12并行編譯技術Parallelcompilationtechnology重點：編譯程序的概念、編譯程序的結構難點：編譯程序的開發技術

目錄12.1并行計算機及其編譯系統簡介12.2并行程序設計模型12.3并行編譯系統的構造12.4自動并行化技術研究現狀12.5本章小結412.1并行計算機及其

編譯系統簡介5為實現高性能并行計算，并行系統通常采用兩種形式：

①程序設計人員編寫常規的串行應用程序，由編譯器將其轉換為并行目標代碼執行。

②按照某種并行語法規范編寫相應的并行程序，由并行語言編譯器將其編譯轉換為并行目標代碼執行。本章在介紹并行編譯系統之前，先給出并行計算相關技術的一些介紹，然后再針對不同體系結構的目標機器介紹并行編譯系統實現的分類及結構。12.1.1并行計算相關技術簡介6并行性：在同一時刻或同一時間間隔內完成兩種或兩種以上的任務。并行性有兩種含義：同時性和并發性。并行粒度：衡量軟件進程所含計算量的尺度，一般用細、中、粗粒度來描述。時延：機器各子系統間通信開銷的時間量度，如存儲時延和同步時延。

并行處理技術通過處理開發過程中的并行事件，使并行性達到較高水平，涉及并行結構、并行軟件和并行算法等多個方面，這些方面相互聯系，互為條件，互為保證。12.1.1并行計算相關技術簡介7并行等級的分類：?

從計算機信息加工的步驟和階段的角度看：

存儲器操作并行

處理器操作步驟并行

處理器操作并行

指令、任務、作業并行?從開發程序的大小和并行粒度的角度看：

作業級

任務級

例行程序或子程序級

循環和迭代級

語句和指令級粗粒度中粒度細粒度通信需求與調度開銷并行程度12.1.1并行計算相關技術簡介8并行處理：并行處理指的是在并行計算機上實現并行計算。

并行體系結構（基礎）并行軟件系統并行程序設計向量計算機共享存儲器并行計算機分布存儲器并行計算機并行系統軟件并行應用軟件并行體系結構并行系統軟件并行程序設計語言并行算法12.1.2并行編譯系統的分類及結構9并行編譯系統的分類：

?不具有自動并行化功能的系統

?具有自動并行化功能的系統并行編譯系統的結構向量編譯技術并行編譯技術

并行運行庫技術并行編譯技術程序并行化技術依賴關系分析技術體系結構內在特性1012.1.2并行編譯系統的分類及結構并行編譯技術可按以下兩種方法來分類：1112.2并行程序設計模型

如同匯編程序員必須熟悉機器指令集一樣，在了解并行體系結構的基礎上才能更好地理解和掌握并行程序設計模型以及并行編譯系統。本節簡要介紹并行計算機體系結構的三種類型以及相應并行編譯系統需要解決的問題。12.2.1并行體系結構分類及并行程序設計

并行計算機體系結構大致可分為向量計算機、共享存儲器多處理機以及分布式存儲器并行計算機三類。12不同體系結構不同程序并行設計方法12.2.2并行程序設計模型

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

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

代碼向量化：把標量程序由一種可向量化循環完成的操作變換成向量操作。?

代碼并行化：將串行程序的可并行化部分展開成多線程，以同時供多臺處理機并行執行，其目的是減少總的執行時間。12.3.4并行代碼生成23

并行代碼生成：將優化后的中間形式的代碼轉換成可執行的具體的機器目標代碼。并行語義的識別和處理向量化編譯器的并行代碼生成

?

向量循環的組織：并行編譯器自動尋找并向量化源程序中的循環。

?

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

?

流水線調度：重排代碼序列，優化向量操作指令，提高功能部件的執行效率。

12.3.4并行代碼生成24共享存儲器多處理機的并行代碼生成

?預編譯器：處理并行語言、并行制導命令的語法語義分析，實現并行制導命令功能的程序改寫和并行庫調用。

?棧式存儲分配：實現程序副本的可再入，每個任務調用時獲得自己的私有變量空間。分布存儲器大規模并行機的并行代碼生成

?

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

?

任務劃分：將源程序任務劃分為可并行的子任務，并分配到多個處理機上執行。

?

同步與通信：處理并行任務之間的數據交換，包括確定同步與通信點、插入并行庫子程序調用以及通信優化

12.4自動并行化技術研究現狀

自動并行編譯系統研究的難點主要有以下幾個方面：25①程序并行性的挖掘②合理的數據分布③通信優化

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

將Fortran77代碼變換成Fortran90代碼，開發循環級的并行性4.FORGE90系統

根據用戶的提示進行并行化作業，用戶根據系統分析所得到的信息進行理解和判斷5.CAPTools系統

將串行Fortran77程序并行化，產生插入了通信調用的并行程序12.4.1比較典型的自動并行化系統簡介276.SUIF系統

自動生成并行源程序代碼，涵蓋相關性分析、指針分析、分塊、預取、程序變換、過程間分析等技術7.FPT(Fortran-PTranslator)

將Fortran-P程序轉換為MPP系統上高效運行的并行程序8.PTRAN系統

自動并行化串行Fortran程序，開發循環級和任務級并行性9.AFT系統

自動分析標準Fortran程序，改寫為并行向量程序10.KD-PASTE系統

提高YH仿真系列機的運行效率，產生兩種并行代碼形式12.4.1比較典型的自動并行化系統簡介28并行化系統挑戰?早期系統：如KAP和VAST，面臨過程調用語句和符號量的問題，限制了并行化能力。?后期系統：如AFT和SUIF，采用新技術提高了并行化能力，但仍有程序的自動并行化效果與手工并行化有差距。?交互式系統：如FORGE90和CAPTools，允許用戶參與并行化過程，提高了并行化效果，但自動并行化能力有限。2912.4.2自動并行化編譯系統發展簡介1.

向量并行?

向量運算硬件最早出現在向量機，現在大部分處理器都已集成SIMD擴展。?

SIMD擴展指令能夠實現向量并行，是目前程序并行的重要方式之一。2.核級并行?

核級并行指在同一結點內共享存儲系統的多個計算單元之間的并行。?

OpenMP是實現核級并行的主要并行編程模型和工業標準。3.結點級并行?

結點級并行的主要特征是計算節點之間不共享存儲系統，必須通過互聯網絡進行通信和數據傳輸。?

分布式存儲結構上實現結點