並行編譯器

一旦一個程式以某種高級語言書寫完成後，在正式運行前，必須將此程式轉換成實際機器能夠理解的機器語言（指令集）。此過程就是編譯（Compile），而編譯器實際上就是實現此轉換的一種語言處理程式。編譯過程可分為：①詞法分析；②語法分析；③中間代碼產生；④代碼最佳化；⑤代碼生成等幾個階段。上述幾個階段或多或少都是順序執行的。而並行化編譯面臨的任務是：給定一個在單處理機上運行較長的串列程式和一台具有多個處理器可同時工作的並行計算機，目的是將串列程式分解成若干個能並行執行或至少能重疊執行的代碼段，使其在並行機上能較快地運行。所以並行編譯器主要工作就是尋找代碼的並行性，然後將其調度在並行機上高速正確地執行。

基本介紹

• 中文名：並行編譯器
• 外文名：Parallel compilers
• 主要工作：將代碼在並行機上高速正確的執行
• 包括：程式分析及最佳化和並行代碼生成
• 舉例：智慧型並行編譯器

並行編譯器的結構

除了一般編譯器的功能以外，為了實現程式的並行化，並行編譯器通常包括程式分析、程式最佳化和並行代碼生成三個部分，其結構如圖所示。

程式分析

要將程式並行化，並行編譯器就必須識別程式中哪些部分是可以並行的，然後將那些可以並行的部分變換為並行執行的程式。這個變換必須是等價的，而其中最基本的前提是要保持程式中固有的數據依賴關係不變。為此，並行編譯器需要對源程式進行數據依賴關係分析、控制依賴關係分析以及數據流分析。程式分析就是承擔這類工作的，是各種並行最佳化的基礎。對於不同的並行體系結構，程式中所開發的並行粒度也有所不同，因此程式分析的級別也不一樣。例如，對於超標量機而言，通常僅需要做一般的數據流分析。而對於提供指令級並行的超長指令字機器、向量機或並行機而言，還要做數據依賴關係分析和控制依賴關係分析，並且分析的範圍也隨並行粒度的變化而變化。例如，小粒度並行往往是循環級並行，因此分析對象一般是循環。而大粒度的並行是子程式級並行，所以還要分析子程式之間的關係。

程式最佳化

這裡所說的最佳化是指以儘可能利用並行硬體能力為目的的各種程式變換。程式最佳化就是要縮短程式的執行時間，通常主要是通過開發程式的並行性、減少指令的長度、減少訪問存儲器的次數等手段來縮短程式執行時間。利用並行硬體能力的最佳化主要包括：利用向量流水線的向量化、利用多處理機結構的並行化、針對分散式存儲器結構的數據分布、計算分布、數據局部化、通信最佳化，以及其他與機器相關的最佳化，如用於減少流水部件或存儲器訪問延遲的指令調度、針對超長指令字結構的指令歸併等等。在實際的並行編譯器中，各種最佳化是分散在不同層次的多遍處理之中進行的，並非是集中在同一遍中進行的。例如，通常向量化、並行化為單獨的一遍，且多為源程式到源程式的變換。其他的最佳化則可能發生在中間代碼生成階段或者目標代碼生成階段。

並行代碼生成

並行代碼生成就是將源程式的代碼轉換成可以並行執行的代碼，它是通過將一種表示形式轉換為另一種表示形式來實現的。這裡的表示形式可以是原始碼，也可以是中間代碼或者目標代碼。並行代碼生成既包括源程式中的並行語法、語義的分析處理，也包括與體系結構相關的目標代碼生成。對於不同的語言和不同的計算機結構，並行代碼生成所做的工作也有所不同。對於向量處理機，它包括並行循環的疊代劃分，以及處理機的調度和同步庫子程式調用的插入。對於分散式存儲器大規模並行機，則還包括數據與計算的分布、分布數組的地址計算、通信所需要的訊息傳遞庫子程式調用的插入等等。最後，生成的並行目標代碼將與並行庫連線在一起而成為一個可以並行執行的檔案。

編譯及其並行化

下圖示出了編譯器將一個高級語言的代碼段翻譯成彙編語言形式的機器目標代碼的過程。最右邊還給出了經過簡單最佳化後使用較少指令的目標代碼。

事實上，最左邊的原始碼經過詞法分析器首先被分解成一些原子目標（即tokens），再把它們分類為操作符、常數、分隔設定、標誌符等；然後經過語法分析器，分析程式的文法結構、檢查錯誤，最後轉換成類似於下圖的語法分析樹；產生中間代碼是為了便於移植和最佳化，中間代碼和彙編語言的主要區別是，前者不必為每種操作之輸入和輸出指定實際的暫存器和存儲器位置；最佳化的目的是使程式運行得較快和使用較少的存儲器，其主要方法重排編譯後的代碼（即所謂代碼移動），它是建立在流分析的基礎上的，是程式向量化和並行化的關鍵。

一般而言，有兩種並行化代碼段的方法：SIMDizing（即向量化，Vectorizing）和MIMDizing（即並行化Parallelizing）。如下圖所示，代碼段的程式流圖被分成幾個不同的計算調度單元。此時，DO循環可被分布成三個不同的相互獨立的循環，它們分別標誌為“向量”、“向量”和“遞歸”：其中前兩個循環執行簡單的、相同的和獨立的算術運算，因此每個循環都可用一條向量指令代替之，從而達到向量化；後一個循環涉及到遞歸，是彼此相關的，所以無法向量化，但可將代碼分成可供MIMD多處理機執行的幾個任務，每個處理器負責循環的若干次疊代，各處理器之間再施行必要的同步就可達到並行化。

下面結合一段具體的程式代碼，分別給出相應的向量化和並行化的結果，以期讀者對兩種並行化方法有個感性認識。

智慧型並行編譯器的總體結構

本次介紹的智慧型並行編譯器，其功能是將FORTRAN 77源程式轉換為並行FORTRAN程式。該系統設計的目標是：

①充分挖掘順序程式的並行性，特別是循環，過程調用的並行性。

②充分挖掘大粒度的並行性，尤其是循環之間、過程調用之間的並行性。

③儘可能做到系統易於擴展。

系統的總體結構如圖所示：

其中，並行編譯器中控模組實現對模組的控制與管理，已完成將順序程式向並行程式的轉換，其輸入為順序FORTRAN 77源程式，輸出為並行FORTRAN程式段。

互動視窗模組完成程式相關圖（PDG）的顯示和修改以及轉換過程的顯示和人工干預。

方法庫管理模組提供程式相關檢測方法及其管理。

知識庫管理模組提供程式相關圖最佳化所需的只是及其相應的管理。

程式表示、控制流分析、相關分析、最佳化處理、並行劃分和程式重構這6個模組，是實現順序程式向並行程式轉換中各階段的主要功能塊。