第二章 程序和網(wǎng)絡(luò)特性程序行為的基本特征：計算粒度程序劃分條件軟件與硬件的匹配程序流機制并行性的編譯支持主要互連網(wǎng)絡(luò)：靜態(tài)/動態(tài)互連網(wǎng)絡(luò)網(wǎng)絡(luò)復雜性通信帶寬數(shù)據(jù)尋徑功能2．1并行性條件并行處理的三個關(guān)鍵領(lǐng)域（H.T.Kung,1991）并行計算的計算模型并行系統(tǒng)結(jié)構(gòu)中的處理機間的通信將并行系統(tǒng)加入通用計算環(huán)境的系統(tǒng)集成并行性形式的依賴：（時間、空間、性能、價格因素之間的折中）并行性級別計算粒度時間與空間復雜性通信時延調(diào)度策略負載平衡2．1．1．相關(guān)性通常相關(guān)性有數(shù)據(jù)相關(guān)、控制相關(guān)、資源相關(guān)等。通過相關(guān)圖來觀察可并行化和向量化的地方。相關(guān)性有：l局部相關(guān)：數(shù)據(jù)相關(guān)、存儲器相關(guān)、寄存器相關(guān)、…l全局相關(guān)：數(shù)據(jù)相關(guān)、轉(zhuǎn)移相關(guān)、中斷相關(guān)、…例：（數(shù)據(jù)相關(guān)）定義五種數(shù)據(jù)相關(guān)：（1） 流相關(guān)：如果從S1到S2存在執(zhí)行通路，而且如果S1至少有一個輸出可供S2用作輸入，則S2與S1流相關(guān)。表示為S1→S2.（2） 反相關(guān)：如果在程序次序中S2緊接S1，而且如果S2的輸出與S1的輸入重疊，則S2與S1反相關(guān)。表示為S1→S2。（3） 輸出相關(guān)：如果兩條語句能產(chǎn)生同一輸出變量，則它們是輸出相關(guān)。表示為S1→S2。（4） I/O相關(guān)：讀與寫都是I/O語句。(5）未知相關(guān)：下列情況，兩條語句之間的相關(guān)關(guān)系不能確定l變量下標就是它本身（間接尋址）；l下標不包括循環(huán)指標變量；l帶有不同循環(huán)變量系數(shù)的下標的變量不止一次地出現(xiàn)；l下標在循環(huán)指標變量中是非線性的。S1：LoadR1，A /R1←Memory（A）/S2：AddR2，R1 /R2←（R1）+（R2）/S3：MoveR1，R3 /R1←（R3）/S4：StoreB，R1 /Memory（B）←（R1）/上面四條語句中包含有相關(guān)關(guān)系：lS2與S1是流相關(guān)：變量A通過寄存器R1傳送。lS3與S2是反相關(guān)：寄存器R1的內(nèi)容存在潛在的沖突。lS3與S1是輸出相關(guān)：它們二者都要修改同一個寄存器R1。但是S2與S4無關(guān)。（圖2-1b）控制相關(guān)：語句執(zhí)行次序在運行前不能確定的情況。例如條件轉(zhuǎn)移語句?？刂葡嚓P(guān)常使正在開發(fā)的并行性中止，因此要使用編譯技術(shù)來克服控制相關(guān)。資源相關(guān)：與并行事件利用整數(shù)部件、浮點部件、寄存器、存儲器等共享資源時發(fā)生的沖突有關(guān)。如ALU相關(guān)、存儲器相關(guān)等等。

Bernstein條件（1966）：檢測程序的并行性設(shè)有兩個進程（進程的定義：與不同處理級別上的程序段抽象相對應(yīng)的軟件實體）P1和P2，它們的輸入集合分別為I1和I2，輸出集合分別為O1和O2。如果這兩個進程不相關(guān)（流不相關(guān)、反不相關(guān)、輸出不相關(guān)…），那么它們就能并行運行，表示為P1∥P2。形式化表示：

I1∩O2=φ I2∩O1=φ O1∩O2=φ

例：（用Bernstein條件來檢測程序的并行性）設(shè)五條語句，每條語句只需要一步（即不考慮流水線）。P1： C=D*EP2： M=G+CP3： A=B+CP4： C=L+MP5： F=G/E（圖2-2）圖2-2a表示它們的數(shù)據(jù)相關(guān)和資源相關(guān)。圖2-2b表示順序執(zhí)行（需五步）。圖2-2c表示并行執(zhí)行（兩個加法器，需三步）。按Bernstein條件，兩兩成對。有10對（P1P2，P1P3，P1P4，P1P5，P2P3，P2P4，P2P5，P3P4，P3P5，P4P5）要進行并行性檢測。檢測結(jié)果：P1P2（C流相關(guān)），P1P3（C流相關(guān)），P1P4（C輸出相關(guān)），P1∥P5，P2∥P3，P2P4（C流相關(guān)），P2∥P5，P3P4（C流相關(guān)），P3∥P5，P4∥P5。無資源沖突可并行執(zhí)行。有五對P1∥P5，P2∥P3，P2∥P5，P3∥P5，P4∥P5。但具有傳遞并行性只有P2∥P3∥P5，而P1與P4會引起傳遞相關(guān)。一般地說并行性關(guān)系有：l可交換性：

Pi∥Pj隱含著Pj∥Pi。l傳遞性： 只有P2∥P3∥P5有傳遞性。有不能傳遞的，即Pi∥Pj和Pj∥Pk但不一定保證Pi∥Pk。l結(jié)合性：

Pi∥Pj∥Pk隱含（Pi∥Pj）∥Pk=Pi∥（Pj∥Pk）。2．1．2硬件和軟件并行性（1） 硬件并行性：l機器結(jié)構(gòu)和硬件多樣性所決定的并行性類型；它是價格和性能折衷的函數(shù)；是同時可執(zhí)行操作的資源利用方式。l處理機并行性描述的一種方法：每個機器周期執(zhí)行的指令數(shù)表示。某處理機每個機器周期發(fā)出k條指令，稱k發(fā)射處理機（RISC結(jié)構(gòu)中單發(fā)射與多發(fā)射概念源于此）。2） 軟件并行性：這類并行性是由程序的控制和數(shù)據(jù)的相關(guān)性決定的。常用程序分布圖或程序流圖表示。它是算法、程序設(shè)計風格和編譯器優(yōu)化的函數(shù)。（3）硬件并行性與軟件并行性之間的失配：舉例：l8條指令（4條加載，4條運算操作）。軟件并行性：用三個周期完成，平均軟件并行性為8/3=2.67條指令/周期。（圖2-3a）硬件并行性：設(shè)一臺2發(fā)射處理機（可同時執(zhí)行一次加載或?qū)懭?，一次運算操作），用七個周期完成，平均硬件并行性為8/7=1.14條指令/周期。（圖2-3b）此例說明硬件并行性與軟件并行性之間的失配。

（4）一種雙處理機解決方案（圖2-4）l 增加4條處理機間通信（共享存儲器方式）必須用的指令，所以是12條指令用六個周期完成，平均硬件并行性為12/6=2.00條指令/周期。l 實現(xiàn)了硬件并行性與軟件并行性的一種匹配。2．2程序的劃分和調(diào)度討論內(nèi)容：計算程序的基本定義程序的并行性級別通信時延及調(diào)度

2．2．1顆粒規(guī)模和時延1。粒度（顆粒規(guī)模）衡量軟件進程所含計算量的尺度最簡單的度量方法：一個顆粒（程序段）中的指令條數(shù)。（其實計算量≠指令條數(shù)。例如循環(huán)程序）

2。粒度的規(guī)模決定了并行處理的基本程序段3。時延：機器各子系統(tǒng)之間通信開銷的時間度量同步時延：兩臺PE為了達到互相同步所需時間4。并行性程度（級別）與粒度規(guī)模的關(guān)系（圖2-5）

以程序員和編譯器設(shè)計者來“觀察”（1）指令級（<20條指令，可在2~nK條之間）——細粒度優(yōu)點“可比較充分地反映豐富的并行性開發(fā)方法：借助編譯器自動檢測并行性（程序員檢測很“乏味”），并將源代碼變成運行時系統(tǒng)能識別的并行形式。（2）循環(huán)級（<500條指令）——細粒度迭代循環(huán)操作，不相關(guān)，適合并行。循環(huán)級并行性是在并行或向量計算機上運行的最優(yōu)程序結(jié)構(gòu)，遞歸循環(huán)，并行相當困難（3）過程級（<2K條指令）——中粒度檢測困難：與任務(wù)、過程、子程序、協(xié)同程序，相關(guān)分析，以及歷史狀況有關(guān)特別：程序員開發(fā)這級并行性需要重新設(shè)計程序，且需要編譯器的支持。

（4）子程序級（<nK條指令）——中、粗粒度多道程序設(shè)計（作業(yè)步可能重疊或跨越不同的作業(yè)）并行性是由算法設(shè)計者或程序員來開發(fā)的，尚未有編譯器的支持。消息傳遞型多處理機系統(tǒng)上實現(xiàn)（5）作業(yè)或程序級（>nK條指令）——粗粒度獨立作業(yè)的并行執(zhí)行這級并行性開發(fā)是可行的，一般由加載程序或操作系統(tǒng)來處理。小結(jié)：細粒度并行性（指令級、循環(huán)級）借助并行化或向量化編譯器開發(fā)；中粒度并行性（任務(wù)級、作業(yè)步級）要求程序員并借助編譯器一起開發(fā)；粗粒度并行性（程序級）主要取決于高效的操作系統(tǒng)和所用算法的效率。一般說：粒度愈細，并行性潛力愈大；通信和調(diào)度的開銷也愈大。

5。通信時延：平衡粒度與時延，得到好的系統(tǒng)性能（1）由機器系統(tǒng)結(jié)構(gòu)、實現(xiàn)技術(shù)、通信方式?jīng)Q定（2）時延是機器規(guī)?？蓴U展性的一個限制因素。例如：存儲器容量的增加使存儲器時延也增加，為了不超過容許值，存儲器的容量就不能無限增加。（3）一般：n個通信任務(wù)互相通信，它們之間需要n(n-1)/2條通信鏈路，所以復雜性是平方關(guān)系增長。限制了PE使用的數(shù)量規(guī)模（4）通信模式是由所用的算法和系統(tǒng)結(jié)構(gòu)決定，有置換、廣播、選播、會議通信模式。在粒度和并行性二者之間折衷選擇。（5）通信涉及的問題：減少時延；降低復雜性；防止死鎖；通信模式中阻塞最小化；并行性與通信開銷的折衷

2．2．2粒度的組合和調(diào)度并行程序設(shè)計中二個基本問題：1。如何將一個程序劃分為并行分支、程序模塊、微任務(wù)或顆粒，以便獲得盡可能短的運行時間2。在計算中最佳的并行粒度為多大？程序劃分與算法設(shè)計者、程序員、編譯器、操作系統(tǒng)支持有關(guān)。對時間復雜性：計算開銷+通信開銷（包括存儲器延遲）。

一種粒度組合方法（Kruatrachue&Lewis1988）圖2-6所示引進概念結(jié)點（相當于程序中的計算單元）粒度：執(zhí)行結(jié)點中全部操作所需的基本機器周期數(shù)二組變量：(n,s)表示在結(jié)點中

n——結(jié)點名；s——結(jié)點粒度 (v,d)表示在結(jié)點邊上

v——源結(jié)點（輸出）到目的結(jié)點（輸入）的變量

d——源結(jié)點到目的結(jié)點間延遲這種組合：細粒度（17）圖（a）到粗粒度（5）圖（b）

粒度組合的一般原則：（并行性與調(diào)度/通信開銷之間的折中）先細粒度獲得較高并行度；后分析加大粒度，可能消除一些結(jié)點間的調(diào)度開銷單個粗粒度結(jié)點中的全部細粒度操作分配到同一處理機執(zhí)行細粒度的延遲（同一處理機）可忽略；主要延遲反映在處理機間延遲圖2-7是形象地給出二種多處理機的調(diào)度方案

2．2．3靜態(tài)多處理機調(diào)度由來：粒度組合方法不一定能得到一種好的調(diào)度方案最好的方法是動態(tài)多處理機調(diào)度，但這是一個NP難