SISD演算法

㈠ 處理機和CPU

處理器=cpu,處理機不是cpu
處理機 處理機
計算機系統中存儲程序和數據，並按照程序規定的步驟執行指令的部件。程序是描述處理機完成某項任務的指令序列。指令則是處理機能直接解釋、執行的信息單位。處理機包括中央處理器，主存儲器,輸入-輸出介面。處理機加接外圍設備就構成完整的計算機系統（見圖單指令流單數據流處理機系統）。
處理機的處理能力有多種指標和參數。通常用每秒最快執行的百萬條指令數(MIPS)來度量。對具有向量處理能力的處理機，則用每秒最多能給出的百萬個浮點處理結果數（MFLOPS）來度量。此外，還常用處理數據率(PDR)來評價處理機的處理能力。處理數據率(PDR)的定義是執行每條指令傳送的平均位數與指令處理平均速率的乘積。在早期的計算機中，處理機的結構是以運算器為中心的，大多採用串列工作方式。數據的輸入－輸出(I／O)傳送都要經過運算器。隨著固態電子器件替代真空電子器件,中央處理器(CPU)的數據處理能力大為提高。機電式外圍設備的數據傳送速度已無法與它相比。因而輸入－輸出操作的傳輸控制部件從中央處理器分離出來成為介面部件、通道或直接存儲器存取（DMA）部件,並且出現了中斷系統的設計技術，從而有效地增強了處理機的處理能力。同時，處理機結構轉變成為以主存儲器為中心。之後，又出現了互連處理機各部件的匯流排結構。隨著微電子技術的進步和計算機系統結構的發展，已能用大規模集成電路構成不同結構的和適應不同用途的處理機，如陣列處理機、向量處理機、數組處理機、資料庫處理機、輸入－輸出處理機和將整個處理機製作在幾個矽片上的微處理器等。
處理機操作 處理機的操作是首先將用戶程序和數據通過輸入－輸出設備輸入到主存儲器（主存）或輔助存儲器。中央處理器從主存取出指令，完成對指令的解釋，執行控制操作；若是運算型指令，還須從主存取出數據，由運算器完成運算。結果通常暫存在運算器或送回主存。
處理機執行程序過程涉及輸入-輸出操作、主存-輔存的信息交換，這些都要經過輸入、輸出介面部件。處理機與外界的這種信息交換有三種方式。①中斷方式：即程序I／O。每傳送一個位組（如一個字或位元組）產生一次中斷,由CPU執行相應的中斷程序完成。這種方式主要用於慢速輸入-輸出設備。②直接存儲器存取(DMA)方式:在硬體線路控制下直接在快速輸入-輸出設備和主存之間完成一條輸入－輸出指令規定的信息量交換。③通道控制方式：各通道各有自己的通道程序,實現輸入-輸出指令規定的主存和輸入-輸出設備之間的信息交換。
處理機分類 從系統結構角度，按處理機執行的指令流和與指令流相關的數據流的關系，有單指令流單數據流（SISD）處理機、單指令流多數據流（SIMD）處理機和多指令流多數據流（MIMD）處理機。SISD處理機的程序是按單一指令序列執行的，操作數據亦按對應的指令確定的單一順序逐個處理。大多數處理機都屬於這一類。SIMD和MIMD處理機又稱並行處理機。並行處理機的目的在於提高處理機的數據處理能力。SIMD處理機以處理向量數據為主，故又稱向量處理機。其中以單個指令執行部件和多個相同的運算處理器構成的處理機稱為陣列（式）處理機,如美國的伊利阿克ILLIAC-Ⅳ。以生產流水線方式組織指令部件(稱先行控制)和運算功能部件的SIMD處理機，稱為流水線處理機，如中國1983年研製成功的「銀河」計算機的處理機。聯想處理機則是採用按內容檢索的聯想存儲器為主要特徵的SIMD處理機。至於MIMD處理機，實際上是多處理機系統，它是多個相同的處理機通過公共主存儲器相互耦合構成有多重處理能力的系統。
處理機又可根據在計算機系統中的功能來分類。一般情況下，處理機的指令系統可以反映出處理機功能的強弱和它的適用范圍。通用中央處理器具有很強的指令功能，適用於科學計算、數據處理、商業應用、事務管理各個領域或某一個和某幾個領域。某些處理機的指令系統只有局部的功能,往往以其用途來命名。①輸入-輸出處理機：解釋和執行輸入-輸出指令,具有一定的字元處理能力,它完成輸入-輸出操作和設備控制操作。②通信控制處理機：在計算機網中實現各個處理機之間的通信並協調它們的操作。③支持和維護處理機：具有系統控制台功能，能實現系統維護和故障診斷。④數組處理機：結構上適合於數組和矩陣運算尤其是信號處理演算法運算，與前置處理機或主機配接後可大大增強系統的向量處理能力。此外還有：具有資料庫管理功能的資料庫處理機；實現虛擬存儲器頁面調度的處理機等。

㈡ 異構計算的異構計算

在異構計算系統上進行的並行計算通常稱為異構計算。人們已從不同角度對異構計算進行定義，綜合起來我們給出如下定義：異構計算是一種特殊形式的並行和分布式計算，它或是用能同時支持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為同類同型多機方式，因此可看成是同類異型多機方式中的特例。異類混合多機方式中所使用的多機，它們的結構則屬不同類型。 網路異構計算系統主要由一組異構計算機、一個連接所有機器的高速網路和一個並行編程環境所組成。邏輯上這種系統可分為三個層次：網路層、通信層和處理層。如圖1所示。
網路層主要用來連接在不同地點的計算機，如圖1中的計算站a和計算站b，並考慮其中消息傳遞的路由選擇、網路流優化和網路排隊理論等問題，這與傳統的計算機網路設計類似。
通信層工作於網路層之上，主要為系統中各種不同的計算機提供能夠相互通信的機制。通信工具軟體應提供使眾多異構計算機集合可視為是一個單一的系統映像、單個虛擬異構並行機的機制。這將方便用戶編程。這種通信工具通常提供一組原語來提供各種通信。典型流行的通信工具是pvm（並行虛擬機）和mpi（消息傳遞標准介面）。
處理層主要用來管理異構機器組並保證任務的高效執行。它所提供的主要服務包括編程環境和語言支持、應用任務的類型分析和任務劃分、任務的映射與調度以及負載平衡等。 異構計算處理過程本質上可分為三個階段：並行性檢測階段、並行性特徵（類型）析取階段以及任務的映射和調度階段。並行性檢測不是異構計算特有的，同構計算也需要經歷這一階段。可用並行和分布計算中的常規方法加以處理。並行性特徵析取階段是異構計算特有的，這一階段的主要工作是估計應用中每個任務的計算類型參數，包括映射及對任務間通信代價的考慮。任務映射和調度階段（也稱為資源分配階段）主要確定每個任務（或子任務）應映射哪台機器上執行以及何時開始執行。
從用戶來看，上述的非同步計算處理過程可用兩種方法來實現。第一種是用戶指導法，即由用戶用顯式的編譯器命令指導編譯器完成對應用代碼類型分析及有關任務的分解等工作，這是一種顯式開發異構性和並行性方法，較易於實現，但對用戶有一定要求，需將異構計算思想融入用戶程序中。另一種是編譯器指導法，需將異構思想融入編譯器中，然後由具有「異構智力」的編譯器自動完成應用代碼類型分析、任務分解、任務映射及調度等工作，即實現自動異構計算。這是一種隱式開發異構性和並行性方法，是異構計算追求的終極目標，但難度很大，對編譯器要求很高。
自動異構計算的概念性模型如圖2所示。首先對兩個對象進行分析，一是異構計算系統中的機器集，二是求解的應用程序。為了獲取最好的執行效果，對它們不但進行定性分析，還需進行相應的定量分析。
整個異構計算處理過程可分為以下四個階段：第一階段主要是對各台機器進行計算特徵的分類，得出異構計算系統所能完成的計算類型；按代碼塊統計應用對計算特徵的需求並加以分類；用基準程序測試各機器的性能參數，包括速度參數及機器間通信性能參數，生成對應的兩個機器速度性能矩陣和通信帶寬矩陣。將程序按計算類型分類劃分；估算各子任務的計算量和子任務間通信量，生成相應的任務dag圖。dag圖中結點上的數值表示子任務計算量，弧上的數值表示兩結點間通信量。
第二階段主要是根據dag和速度性能矩陣計算出每個子任務在各台機器上的執行時間，生成時間性能矩陣；根據通信性能矩陣和子任務的通信量計算各子任務間的通信時間，生成通信時間矩陣。
第三階段根據前兩個階段結果，給出各子任務到各機器的映射和符合任務dag圖偏序關系的調度。映射和調度可以是靜態或動態的，動態調度需根據機器負載和網路狀態信息進行。
第四階段為執行。 異構計算的應用范圍很廣，幾乎所有涉及巨大挑戰性問題的求解都可用異構計算進行經濟有效的求解。典型的應用包括圖像理解、質點示蹤、聲束形成、氣候建模、湍流對流混合模擬以及多媒體查詢等。這些應用中通常都含有多種不同的計算類型的需求，因此很適合於用異構計算來進行求解。
1、未來應重點開展異構混合多機方式的網路異構計算的研究，它代表著發展趨向，且較經濟有效；2、自動異構計算是長期追求目標，在現階段宜採用用戶指導方法來進行研究和開發；3、應盡量利用現有成熟工具如pvm和mpi來開展異構計算的研究和開發；4、應注意開展異構計算的理論分析和建模、性能估計模型、有關軟體工具以及異構計算中任務映射和調度演算法等方面的研究；5、應研究如何使異構計算系統具有良好的單一系統映像。