並行編譯器

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

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

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

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

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

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

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

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

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

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

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

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

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

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

交互窗口模塊完成程序相關圖（PDG）的顯示和修改以及轉換過程的顯示和人工干預。

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

知識庫管理模塊提供程序相關圖優化所需的只是及其相應的管理。

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