平行策略

1第17章平行策略2效能改善的兩個基本技術•平行策略•和管線技術3平行電腦•多個硬體複本•可以同時運作•遍及電腦結構的各種階層內部•結構師會盡量把平行的基本技術運用在系統上，發展出完全由平行策略所控制的電腦結構，稱為平行電腦。4平行特性5微觀vs巨觀平行策略是如此地普遍，幾乎所有的電腦系統都具有某些型式的平行硬體，我們常使用微觀平行來描述：那些確實具備平行能力，但隱藏不易看見的結構。6微觀平行範例•ALU–執行整數算術–比如：32位元的互斥或閘運算•暫存器–通用暫存器可處理多重位元•實體記憶體–比如：64位元的字組記憶體系統•平行匯流排結構–典型32位元或64位元寬的匯流排7巨觀平行範例•多重相同處理器：–比如：雙處理器的PC–兩個平行CPU效能依賴作業系統–作業系統負責程式碼的最佳化控制•多重相異處理器：–特殊的協同處理器–比如，高速影像電腦可以連接四個顯示器，一個顯示器使用一個特殊的影像處理器，來進行控制。8對稱vs非對稱•對稱平行–多個相同元件同時存在的系統–比如，雙處理器PC•非對稱平行–多個同時運作、但功能各不相同的元件–比如，影像協同處理器和數學協同處理器都是非對稱平行。9細紋vs粗紋•細紋平行–以個別的指令或資料為單位–比如，影像處理器使用16個平行硬體單元，來更新16個位元組。•粗紋平行–以程式或大型區塊資料為單位–比如，雙處理器PC使用一個處理器來列印文件，另一個可能正在編輯電子郵件訊息。10顯性vs隱性•隱性平行–硬體會自動地處理平行策略，毋需任何程式設計師動手來啟始或控制。•顯性平行–需要程式設計師來控制每一個平行單元的執行動作，稱為顯性平行。11平行結構•系統最主要的特性就在於平行結構。•平行處理器數量應該達一定的規模–比如：具有32個或64000個處理器的電腦。–把二個處理器加入PC，雖然也是平行策略，但習慣上稱為雙處理器電腦。–加入四個處理器的PC，被稱為四處理器電腦。12平行結構分類(Flynn分類法)13SISD（單一指令單一資料流）•SISD描述無法支援巨集平行的結構–沒有平行的結構–又稱為順序結構、或單一處理器結構–傳統的范紐曼結構就是SISD•SISD最重要的特徵：–順序執行指令，一次只執行一個指令，每個指令只能處理單一資料項目。14SIMD（單一指令多重資料流）•SIMD每一個指令雖然只能指定單一運算動作（比如：整數加法），但可以要求多個資料項目同時動作。•SIMD電腦必須具有充足的硬體，才有能力同時處理多筆資料。15向量處理器•SIMD結構對某些數值需要相同的運算，有很好的工作效率。•SIMD結構又稱為向量處理器或陣列處理器。•SIMD結構常用於某些科學應用程式，處理向量數學、陣列計算或一組數值的浮點運算。16傳統電腦的正規化17向量電腦的正規化•如果陣列大小沒有超過平行硬體的大小，則底層硬體可以同時執行陣列上所有數值的算術運算。•如下：•V←V×Q;•如果陣列大小超過平行硬體的容量，就需要多個步驟才能完成運算動作。18影像處理器•典型的影像硬體使用順序位元組，來儲存螢幕每一個像素的數值。•如果想要移動一個正方形視窗，則軟體必須拷貝某個區域位置的等效視窗位元組到另一個位置，一次一個位置，慢慢移動整個視窗。•在SIMD結構中，程式設計師可以發佈一個複製命令，讓SIMD底層硬體會平行複製多重位元組，效率更快。19MIMD（多重指令多重資料流）•描述平行結構內的每一個處理器，可以在相同的時間，各自獨立地執行計算。•MIMD電腦允許程式設計師控制處理器，讓處理器各自執行獨立程式。20SMP（對稱多重處理器）•最知名的MIMD就是SMP電腦結構。•典型的SMP設計具有N個相同的處理器，具有相同的指令集、時脈速率、記憶體、以及外部設備，但可以各自執行程式。•比如：–CarnegieMellon大學的C.mmp原型機–Sequent公司（現為IBM所有）建立的SMP–Encore公司的MultimaxSMP21SMP架構圖22AMP（非對稱多重處理器）•另一種替代SMP設計的方法稱為AMP•AMP包含N個處理器，可在同一時間運作，但是不一定採用相同處理器。•AMP設計常用於特定的任務–比如，使用處理器來管理磁碟儲存設備。–使用處理器來最佳化影像的顯示任務。23AMP結構•AMP結構遵循主僕方法–主處理器：一個（或一組）處理器控制整體執行（負責最佳化整體控制）–僕處理器：引入其它的處理器，處理其它的輔助功能，像是算術計算或I/O。24AMP結構範例•數學協同處理器–快速計算浮點數的特殊晶片–浮點數計算速度遠比CPU快速•I/O處理器：–I/O使用一個專用的可程式處理器–可高速處理外部I/O（不影響CPU速度）–CPU會下載程式到I/O處理器–I/O處理器負責所有的I/O細節25I/O處理器•比如–IBM大型主機使用一種稱為通道的可程式I/O處理器。–CDC結構使用週邊處理器（簡稱PP）來處理I/O動作。26多重處理器結構的挑戰•多重處理器結構似乎比單一處理器結構有更好的效能。•不幸的是，有三個主要的挑戰：–通訊–協調–競爭27通訊•電腦的通訊機制：–處理數目龐大的處理器之間的通訊–負責處理器與其它元件之間的通訊•有可能造成通訊瓶頸。28協調•協調機制讓平行結構內部的處理器可以一起工作。•非對稱設計要使用主處理器，負責協調所有程序。•某些對稱設計可以使用主僕架構或者分散式協調機制。29競爭•當多個處理器同時存取一個資源時，稱為資源競爭。•資源競爭會造成平行結構相當大的挑戰，隨著處理器數目的增加，相關的競爭也會跟著增加。30多重處理器的效能瓶頸•在多重處理器環境下，最多只能有一個處理器執行作業系統，其它處理器必須等待。•記憶體競爭–同時存取記憶體必須使用多埠記憶體–多個處理器多個快取，可能出現快取不一致的問題。•I/O束縛–從I/O設備取出資料，耗費時間。–一味增強計算能力，也無法降低整體執行時間。31速度提昇比定義•速度提昇比=–其中，是單一處理器的執行時間–則是多重處理器的執行時間•理想情況：處理器數量與速度提昇呈現線性增加的現象。N11N32理想和實際的速度提昇比33速度提昇比的結論以一般的計算而言，把更多的處理器加入多重處理器系統，反而可能導致新的額外負荷，降低整體效能的表現。34對程式設計師的影響撰寫多重處理器的程式碼，當然會比單一處理器的程式碼要複雜。35鎖定的需求•假設雙處理器的環境下，使用一個共用變數x來儲存計數值，如下敘述：x=x+1•翻譯成等效的機器指令，如下：36平行存取的問題•如果有兩個處理器幾乎在同一時間都想遞增x，結果x數值可能遞增1，而不是遞增2。37硬體鎖定•多重處理器使用硬體提供鎖定功能：–將每一個共用變數加入一個鎖，確保其它處理器無法再對這個變數進行更改。–比如：變數x使用17號鎖，程式設計師要對變數x進行更新，必須先取得17號鎖。–一種互斥觀念。38硬體鎖定範例39平行電腦的規劃•隱性平行策略–會比顯性平行策略更容易規劃–相關的硬體會自動地複製相同的程式•顯性平行策略–程式設計師必須規劃每一個不同的硬體單元，啟動這些硬體。–程式碼必須使用鎖，來預防干擾。40平行電腦的規劃重點站在程式設計的觀點來看，規劃顯性平行系統會比規劃隱形平行系統要來得複雜。41對稱和非對稱多重處理器的規劃•多重處理器會帶給程式設計師困擾。•對稱多重處理器會比非對稱多重處理器更容易規劃程式，有四個主要的原因：–都是相同的處理器，具有相同的指令集。–都是對稱的設計。–都操作在相同的速度。–程式或資料數值容易移植。42平行備份硬體•備份硬體類似平行硬體•平行和備份硬體之間的差異在於：–備份硬體會執行相同的運算動作，應該會得到相同的資料。–平行硬體則執行不同的運算動作，得到的結果與其它硬體不一定有關。•備份硬體的重點在於：–驗證計算的正確性。–如果硬體錯誤，可使用備份硬體代替。43分散式電腦•緊密耦合結構–把所有的平行硬體單元都置放在相同的電腦內部•寬鬆耦合結構–分散式結構–通常必須藉由電腦網路，來進行與其它電腦的連繫，每一部電腦都可以獨立作業，進行彼此之間的溝通。44叢集電腦•分散式系統的特例就是網路叢集，或稱為叢集電腦。•叢集問題最好經得起分割，比如：–如果叢集具有N部電腦，資料會被分割成N部分，每個部分會送到其中一部電腦獨立運算；–等到所有電腦結束計算後，收集這些結果，並且產生最後的輸出。45網格計算•網格結構把問題分割成多個小塊，使用網際網路傳送到各個電腦，每個電腦各自執行，並傳回結果。•網格計算常用於大型的科學應用，有兩個原因：–網格可以降低科學應用的執行時間。–矩陣容易切割成多個小塊，利於計算。46結論•平行策略是最佳化效能的基本技術–顯性平行結構可讓程式設計師控制平行能力–隱性平行結構會自動處理平行策略•一般的傳統電腦屬於SISD結構•SIMD結構允許單一指令來處理陣列資料•MIMD結構–使用多個獨立處理器，同時執行不同的程式。–SMP（對稱多重處理器）–AMP（非對稱多重處理器）47結論(Cont.)•理論上，N個處理器執行速度應該N倍於單一處理器。•實際上，受限於記憶體競爭和通訊負荷等因素，因此加入過多的處理器，反而可能降低效能表現。•多重處理器必須使用鎖定觀念，來保證共用變數的互斥存取。