異構計算

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

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

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

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

1、異構計算系統。

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

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

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

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

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型）構成一個異構計算系統，並假設mimd機、simd機以及工作站執行相匹配子任務的加速比分別為36、24和10，則在該異構計算系統上執行同樣任務所需時間就變為

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。

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

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

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

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

網絡異構計算系統主要由一組異構計算機、一個連接所有機器的高速網絡和一個並行編程環境所組成。邏輯上這種系統可分為三個層次：網絡層、通信層和處理層。

網絡層主要用來連接在不同地點的計算機，計算站a和計算站b，並考慮其中消息傳遞的路由選擇、網絡流優化和網絡排隊理論等問題，這與傳統的計算機網絡設計類似。

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

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

異構計算處理過程本質上可分為三個階段：並行性檢測階段、並行性特徵（類型）析取階段以及任務的映射和調度階段。並行性檢測不是異構計算特有的，同構計算也需要經歷這一階段。可用並行和分佈計算中的常規方法加以處理。並行性特徵析取階段是異構計算特有的，這一階段的主要工作是估計應用中每個任務的計算類型參數，包括映射及對任務間通信代價的考慮。任務映射和調度階段（也稱為資源分配階段）主要確定每個任務（或子任務）應映射哪台機器上執行以及何時開始執行。

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

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

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

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

第三階段根據前兩個階段結果，給出各子任務到各機器的映射和符合任務dag圖偏序關係的調度。映射和調度可以是靜態或動態的，動態調度需根據機器負載和網絡狀態信息進行。

第四階段為執行。

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

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

Fusion開發者峯會如火如荼地舉行之際，AMD宣佈與高等院校聯合，面向開發人員出版一本新書：《OpenCL異構計算》(Heterogeneous Computing with OpenCL)。

該書將由荷蘭愛思唯爾出版集團(Elsevier)旗下的Morgan Kaufmann負責出版發行。全書328頁，中文版共277頁，提供了OpenCL體驗的第一手資料，詳盡闡述了多核心處理器、GPU圖形核心、APU融合處理器等多種設備的架構，以及基礎性並行算法等API，並且提供了OpenCL在進行圖像處理、Web插件、隨機數生成、視頻處理等各方面強大能力的詳細實力。

這本書由AMD與美國東北大學的多位專業人士聯合撰寫，包括：

－ AMD OpenCL架構師Benedict Gaster

－ AMD技術骨幹Lee Howes

－ 東北大學計算機架構研究實驗室(NUCAR)主管、信息安全保障研究院(IIA)聯合主管、工程學院副院長David R. Kaeli

－ 東北大學電氣與計算機工程系博士研究生Perhaad Mistry

－ 東北大學電氣與計算機工程系博士研究生Dana Schaa

《OpenCL異構計算》於2012八月份出版發行，提供紙質和電子版兩種格式，售價69.95美元。

同時《OpenCL異構計算》已被張雲泉，張先軼，龍國平，姚繼峯譯為中文版，並由清華大學出版社出版，定價76.00元。