異構計算

概念：

　　在異構計算系統(tǒng)上進行的并行計算通常稱為異構計算。人們已從不同角度對異構計算進行定義，綜合起來我們給出如下定義：異構計算是一種特殊形式的并行和分布式計算，它或是用能同時支持simd方式和mimd方式的單個獨立計算機，或是用由高速網(wǎng)絡互連的一組獨立計算機來完成計算任務。它能協(xié)調(diào)地使用性能、結(jié)構各異地機器以滿足不同的計算需求，并使代碼（或代碼段）能以獲取最大總體性能方式來執(zhí)行。

　　概括來說，理想的異構計算具有如下的一些要素：

　　（1）它所使用的計算資源具有多種類型的計算能力，如simd、mimd、向量、標量、專用等；（2）它需要識別計算任務中各子任務的并行性需求類型；（3）它需要使具有不同計算類型的計算資源能相互協(xié)調(diào)運行；（4）它既要開發(fā)應用問題中的并行性，更要開發(fā)應用問題中的異構性，即追求計算資源所具有的計算類型與它所執(zhí)行的任務（或子任務）類型之間的匹配性；（5）它追求的最終目標是使計算任務的執(zhí)行具有最短時間。

　　可見，異構計算技術是一種使計算任務的并行性類型（代碼類型）與機器能有效支持的計算類型（即機器能力）最相匹配、最能充分利用各種計算資源的并行和分布計算技術。

原理：

　　1、異構計算系統(tǒng)。

　　它主要由以下三部分組成：（1）一組異構機器。（2）將各異構機器連接起來的高速網(wǎng)絡。它可以是商品化網(wǎng)絡，也可以是用戶專門設計的。（3）相應的異構計算支撐軟件。

　　2、異構計算的基本工作原理。

　　異構計算需求在析取計算任務并行性類型基礎上，將具有相同類型的代碼段劃分到同一子任務中，然后根據(jù)不同并行性類型將各子任務分配到最適合執(zhí)行它的計算資源上加以執(zhí)行，達到使計算任務總的執(zhí)行時間為最小。下面通過一個簡單例子來說明異構計算的基本工作原理。

　　假設在某一基準串行計算機上執(zhí)行某一給定計算任務的時間為ts，其中向量、mimd、simd以及sisd各類子任務所占執(zhí)行時間的百分比分別為30%、36%、24%和10%。假設某向量機執(zhí)行上述各類子任務相對于基準串行機的加速比分別為30、2、8和1.25，則在該向量機上執(zhí)行此任務所需的總時間為

　　tv=30%ts/30+36%ts/2+24%ts/8+10%ts/1.25=0.30ts，

　　故相應的加速比為sv=ts/tv=ts/0.3ts=3.33

　　若上述向量機與其他的mimd機、simd機以及一臺高性能工作站（sisd型）構成一個異構計算系統(tǒng)，并假設mimd機、simd機以及工作站執(zhí)行相匹配子任務的加速比分別為36、24和10，則在該異構計算系統(tǒng)上執(zhí)行同樣任務所需時間就變?yōu)?/p>

　　thet=30%ts/30+36%ts/36+24%ts/24+10%ts/10+tc

　　其中tc為機器間交互開銷時間，假設需2%ts時間，則thet=0.06ts，從而相應的加速比為shet=ts/0.06ts=16.67。

　　由上例可見，異構計算系統(tǒng)可比同構計算系統(tǒng)獲取高得多的加速比。這主要是因為同構計算系統(tǒng)中的加速比只是靠并行性開發(fā)獲取的，而異構計算系統(tǒng)中的加速比除了并行性之外，更主要的是靠開發(fā)異構性獲得的（即不同類型子任務與相應類型的計算資源相匹配），盡管此時會有相應的交互開銷。交互開銷越小，異構計算的優(yōu)越性就越加明顯。

分類：

　　異構計算按以何種形式來提供計算類型多樣性，可分為系統(tǒng)異構計算（shc-system heterogeneous computing）和網(wǎng)絡異構計算（nhc-network heterogeneous computing）兩大類。shc以單機多處理器形式提供多種計算類型，而nhc則以網(wǎng)絡連接的多計算機形式提供多種計算類型。

　　根據(jù)異構性實現(xiàn)方式不同，即是空間異構性還是時間異構性，shc和nhc各自又可進一步分為兩類。shc分為單機多計算方式和單機混合計算方式兩大類，前者在同一時刻允許以多種計算方式執(zhí)行任務，后者在同一時刻只允許以一種計算方式執(zhí)行任務，但在不同時刻計算可從一種方式自動切換到另一種方式，如simd和mimd方式間的切換。前者的實例有美國hughes研究實驗室和mit共同研制的圖像理解系統(tǒng)結(jié)構（iua），它是多層異構系統(tǒng)結(jié)構，按圖像理解層次要求設計每一層，低層是simd位串網(wǎng)絡（4096），用來處理像素級操作（如圖像增強），中層是由64個數(shù)字信號處理（dsp）芯片構成的，以spmd或mimd（中粒度）方式執(zhí)行模式分類等操作，頂層是一個通用mimd（粗粒度）機器，完成場景和動作分析等知識處理操作。后者的實例為美國普渡大學研制的pasm系統(tǒng)原型，由16個pe（處理單元）組成的系統(tǒng)，它們可動態(tài)地加以劃分以形成各種大小的獨立的混合方式子機器，執(zhí)行方式可按需要在simd和mimd之間自動切換。

　　nhc可進一步分為同類異型多機方式和異類混合多機方式兩類。同類異型多機方式中所使用的多機，它們的結(jié)構屬同一類，即支持同一種并行性類型（如simd、mimd、向量等類型之一），但型號可能不同，因此性能可以各有差異。通常的now或cow為同類同型多機方式，因此可看成是同類異型多機方式中的特例。異類混合多機方式中所使用的多機，它們的結(jié)構則屬不同類型。

層次結(jié)構：

　　網(wǎng)絡異構計算系統(tǒng)主要由一組異構計算機、一個連接所有機器的高速網(wǎng)絡和一個并行編程環(huán)境所組成。邏輯上這種系統(tǒng)可分為三個層次：網(wǎng)絡層、通信層和處理層。如圖1所示。

　　網(wǎng)絡層主要用來連接在不同地點的計算機，如圖1中的計算站a和計算站b，并考慮其中消息傳遞的路由選擇、網(wǎng)絡流優(yōu)化和網(wǎng)絡排隊理論等問題，這與傳統(tǒng)的計算機網(wǎng)絡設計類似。

　　通信層工作于網(wǎng)絡層之上，主要為系統(tǒng)中各種不同的計算機提供能夠相互通信的機制。通信工具軟件應提供使眾多異構計算機集合可視為是一個單一的系統(tǒng)映像、單個虛擬異構并行機的機制。這將方便用戶編程。這種通信工具通常提供一組原語來提供各種通信。典型流行的通信工具是pvm（并行虛擬機）和mpi（消息傳遞標準接口）。

　　處理層主要用來管理異構機器組并保證任務的高效執(zhí)行。它所提供的主要服務包括編程環(huán)境和語言支持、應用任務的類型分析和任務劃分、任務的映射與調(diào)度以及負載平衡等。

主要問題：

　　異構計算處理過程本質(zhì)上可分為三個階段：并行性檢測階段、并行性特征（類型）析取階段以及任務的映射和調(diào)度階段。并行性檢測不是異構計算特有的，同構計算也需要經(jīng)歷這一階段?？捎貌⑿泻头植加嬎阒械某Ｒ?guī)方法加以處理。并行性特征析取階段是異構計算特有的，這一階段的主要工作是估計應用中每個任務的計算類型參數(shù)，包括映射及對任務間通信代價的考慮。任務映射和調(diào)度階段（也稱為資源分配階段）主要確定每個任務（或子任務）應映射哪臺機器上執(zhí)行以及何時開始執(zhí)行。

　　從用戶來看，上述的異步計算處理過程可用兩種方法來實現(xiàn)。第一種是用戶指導法，即由用戶用顯式的編譯器命令指導編譯器完成對應用代碼類型分析及有關任務的分解等工作，這是一種顯式開發(fā)異構性和并行性方法，較易于實現(xiàn)，但對用戶有一定要求，需將異構計算思想融入用戶程序中。另一種是編譯器指導法，需將異構思想融入編譯器中，然后由具有“異構智力”的編譯器自動完成應用代碼類型分析、任務分解、任務映射及調(diào)度等工作，即實現(xiàn)自動異構計算。這是一種隱式開發(fā)異構性和并行性方法，是異構計算追求的終極目標，但難度很大，對編譯器要求很高。

　　自動異構計算的概念性模型如圖2所示。首先對兩個對象進行分析，一是異構計算系統(tǒng)中的機器集，二是求解的應用程序。為了獲取最好的執(zhí)行效果，對它們不但進行定性分析，還需進行相應的定量分析。

　　整個異構計算處理過程可分為以下四個階段：第一階段主要是對各臺機器進行計算特征的分類，得出異構計算系統(tǒng)所能完成的計算類型；按代碼塊統(tǒng)計應用對計算特征的需求并加以分類；用基準程序測試各機器的性能參數(shù)，包括速度參數(shù)及機器間通信性能參數(shù)，生成對應的兩個機器速度性能矩陣和通信帶寬矩陣。將程序按計算類型分類劃分；估算各子任務的計算量和子任務間通信量，生成相應的任務dag圖。dag圖中結(jié)點上的數(shù)值表示子任務計算量，弧上的數(shù)值表示兩結(jié)點間通信量。

　　第二階段主要是根據(jù)dag和速度性能矩陣計算出每個子任務在各臺機器上的執(zhí)行時間，生成時間性能矩陣；根據(jù)通信性能矩陣和子任務的通信量計算各子任務間的通信時間，生成通信時間矩陣。

　　第三階段根據(jù)前兩個階段結(jié)果，給出各子任務到各機器的映射和符合任務dag圖偏序關系的調(diào)度。映射和調(diào)度可以是靜態(tài)或動態(tài)的，動態(tài)調(diào)度需根據(jù)機器負載和網(wǎng)絡狀態(tài)信息進行。

　　第四階段為執(zhí)行。

應用與研究：

　　異構計算的應用范圍很廣，幾乎所有涉及巨大挑戰(zhàn)性問題的求解都可用異構計算進行經(jīng)濟有效的求解。典型的應用包括圖像理解、質(zhì)點示蹤、聲束形成、氣候建模、湍流對流混合模擬以及多媒體查詢等。這些應用中通常都含有多種不同的計算類型的需求，因此很適合于用異構計算來進行求解。

　　1、未來應重點開展異構混合多機方式的網(wǎng)絡異構計算的研究，它代表著發(fā)展趨向，且較經(jīng)濟有效；2、自動異構計算是長期追求目標，在現(xiàn)階段宜采用用戶指導方法來進行研究和開發(fā)；3、應盡量利用現(xiàn)有成熟工具如pvm和mpi來開展異構計算的研究和開發(fā)；4、應注意開展異構計算的理論分析和建模、性能估計模型、有關軟件工具以及異構計算中任務映射和調(diào)度算法等方面的研究；5、應研究如何使異構計算系統(tǒng)具有良好的單一系統(tǒng)映像。