異構(gòu)計(jì)算

概念：

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

　　概括來說，理想的異構(gòu)計(jì)算具有如下的一些要素：

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

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

原理：

　　1、異構(gòu)計(jì)算系統(tǒng)。

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

　　2、異構(gòu)計(jì)算的基本工作原理。

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

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

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

　　故相應(yīng)的加速比為sv=ts/tv=ts/0.3ts=3.33

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

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

　　其中tc為機(jī)器間交互開銷時(shí)間，假設(shè)需2%ts時(shí)間，則thet=0.06ts，從而相應(yīng)的加速比為shet=ts/0.06ts=16.67。

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

分類：

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

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

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

層次結(jié)構(gòu)：

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

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

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

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

主要問題：

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

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

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

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

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

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

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

應(yīng)用與研究：

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

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