並行處理計算機系統

parallel computer system

並行處理計算機

並行處理計算機主要指以下兩種類型的計算機：①能同時執行多條指令或同時處理多個數據項的單中央處理器計算機；②多處理機系統。

並行處理計算機的結構特點

隨着電子器件的發展 ，計算機的處理能力有顯著提高。但是，僅僅依靠器件的進展而達到的速度提高，遠不能滿足現代科學、技術、工程和其他許多領域對高速運算能力的需要。這就要求人們改進計算機結構，採用各種並行處理技術，以便大幅度地提高處理速度和解題能力。

並行處理計算機的結構特點主要表現在兩個方面：①在單處理機內廣泛採用各種並行措施；②由單處理機發展成各種不同耦合度的多處理機系統。並行處理的主要目的是提高系統的處理能力。有些類型的並行處理計算機系統（如多處理機系統）還可以提高系統的可靠性。由於器件的發展，並行處理計算機系統具有較好的性能價格比，而且還有進一步提高的趨勢。

並行處理計算機的結構主要有流水線方式 、多功能部件方式 、陣列方式、多處理機方式和數據流方式。

將指令的執行過程分解為若干段，每段進行一部分處理。一條指令順序流過所有段即執行完畢獲得結果。當本條指令在本段已被處理完畢而進入下段時，下條指令即可流入本段。因此，在整個流水線上可以同時處理若干條指令。若各段的執行時間均為一個時鐘節拍，則在正常情況下每拍可以輸出一個結果，即完成一條指令。這就可加快處理機的速度。

程序中相鄰指令的相關性會影響流水線處理機效率的發揮。例如，條件轉移指令在上條指令執行完以前，有時不能確定後繼指令；又如本條指令需要用上條指令的結果作為操作數等，都將中斷流水線而使效率下降。

一台處理機具有多個功能部件。各功能部件可以並行地處理數據，因而處理機可以使用不同的功能部件並行執行幾條指令，以提高處理速度。如有的計算機具有浮點加、定點加、浮點乘、浮點除、邏輯操作、移位等多個對不同數據進行處理的功能部件。一些流水線向量機也含有多個功能部件。程序在執行中因對各部件的需求不平衡，各功能部件不可能全部處於忙碌狀態。指令間的相關性也影響機器的效率，如本條指令所需的功能部件尚在執行其他指令；又如本條指令所需操作數恰為尚未執行完畢的指令的結果等。

一台處理機由多個相同的處理部件和一個統一的控制器組成。這個控制器解釋指令並傳送操作命令至全部處理部件。各處理部件按照控制器的命令同時進行完全相同的操作。陣列處理機又可分為浮點陣列處理機和位片式陣列處理機兩類。

ILLIAC-Ⅳ機屬於浮點陣列處理機，包括64個完全相同的處理部件(PU)和一個公共的控制部件(CU)。每個處理部件包括一個能執行64位浮點操作的處理單元(PE)和一個容量為2k字的存儲器(PM)。64個處理部件排列成8×8陣列。每個處理部件與四鄰處理部件均有直接數據通路。

多處理機系統能提高系統的性能和可靠性。它是多指令流多數據流處理機。根據系統中各處理機的耦合程度，多處理機系統可分為兩類。①非直接耦合的多處理機系統：系統中各處理機均有主存儲器。各處理機由各自的操作系統進行管理，它們通過共享的輸入輸出系統進行通信。②直接耦合的多處理機系統：系統中各處理機共享主存儲器，並受統一的操作系統管理。多處理機系統一般指直接耦合這一類。

在直接耦合多處理機系統中，實現處理機與存儲器、處理機與處理機之間連接的互連網絡十分重要。互連網絡有三種主要形式。

①　總線結構：總線結構是多處理機系統中最為簡單的網絡結構。實際的多處理機系統的互連網絡，往往是在總線結構的基礎上發展起來的（圖3）。

②　交叉開關結構：交叉開關由縱橫開關陣列組成，將橫向的處理機與縱向的存儲器模塊連接起來（圖4）。

③　多端口存儲器結構：把交叉開關結構中的各交叉點上的開關移到相應存儲器的接口內部，形成多端口存儲器結構。

數據流處理機是受到人們重視的高度並行的處理機。它雖保留了存儲程序的做法，但在主要原理上已與諾依曼計算機結構不同。它不按程序計數器指出的指令順序執行程序，只要所需操作數全部具備，指令即可被執行,亦即程序的執行不是由控制流驅動,而是由數據流驅動。

數據流處理機是以語言為基礎的處理機。它使用數據流程序圖作為用户語言與計算機結構之間的接口。數據流程序圖用能動框表示 。每個能動框有多個域 ，分別存放操作碼、操作數和目標地址。數據流程序以能動框集合的方式保存在能動存儲器中。當某條指令可以執行時，相應的能動框地址便被送入指令排隊器。讀取部件則按地址從存儲器中取出該能動框，形成操作包，送至操作部件進行處理，產生結果包。修改部件根據結果包的目標地址將結果數據送至規定的能動框作為操作數，並將具備操作數的指令的地址送至指令排隊器。指令排隊器中的指令均具備執行條件，因而只需增加部件數量或增強部件流水程度 ， 就可以高速並行執行。此外，還可將多個指令處理單元連接成數據流多處理機系統，進一步提高處理能力。

並行算法和並行語言

提高並行處理效率的關鍵之一是並行算法。算法須適應計算機的結構。如果一種算法所表達出來的並行度與計算機的並行度基本一致，便能提高計算機的解題效率。

在向量計算機中，提高並行度的主要問題在於把可並行處理的操作數用向量表示。許多常用的數值計算法，如數列求和、矩陣乘、高斯消元、快速傅里葉變換等，已成功地在向量計算機上實現了並行處理。較為通行的並行語言基本上是FORTRAN語言的擴展。

在多處理機系統中，提高程序並行性的關鍵，是把任務分解成足夠多的可同時操作的進程。在程序語言中，還須擴充能明確表達進程併發性的語句，以便程序運行時能為相應的控制機構提供控制和管理手段，其中包括並行任務的派生、通信和調度。ADA 語言為描述多處理機並行程序結構提供了必要的語句。為適應數據流計算機而出現的若干數據流語言如Id語言和VAL語言已經在試用。 其重要特點是把數組看成是值而不是目標。用數據流語言編寫的程序能夠自然地表達出最大的運算並行性。

對於並行處理系統的分類，最廣泛使用的是根據計算機系統中數據流和指令流的多倍性將計算機系統分為四類： ^[1] 

（1）單指令單數據流計算機系統

單指令單數據流計算機系統，Single Instruction Single Data , SISD計算機系統，在SISD計算機系統中，單一處理器執行單一的指令流以實現對保存在單一可訪問存儲器內的數據操作。SISD計算機的典型例子就是單處理器系統，在這種計算機系統中沒有並行處理方式。

（2）單指令多數據流計算機系統

單指令多數據流計算機系統，Single Instruction Multiple Data , SIMD計算機系統，在SIMD計算機系統中，單一指令可以同步控制多個處理不見，每個處理不見都有一個相關的數據存儲器，所以一條指令可以在不同的數據組上完成相同的操作。SIMD計算機

（3）多指令單數據流計算機系統

多指令單數據流計算機系統，Multiple Instruction Single Data , MISD計算機系統可以實現對順序數據進行多個處理器的操作。每個處理器執行不同的指令序列。在實際系統中還沒有完全的MISD計算機出現。

（4）多指令多數據流計算機系統

多指令多數據流計算機系統，Multiple Instruction Multiple Data , MIMD計算機系統，在MIMD計算機系統中，多個處理器並行處理完成不同的指令序列，對不同的數據進行加工操作。MIMD計算機實際上就是多處理器並行系統。在MIMD的組織下，各個處理器是通用的，每個處理器都能處理所有數據並完成相應數據運算的指令。MIMD系統還可以按照各處理器的通信方式進一步進行劃分，如果各處理器共享一個存儲器，則每個處理器存取共享存儲器中的程序和數據，並經由次存儲器相互通信。這種結構的系統最普遍的形式就是SMP系統。SMP通過共享總線或其他方式互連實現多個處理器共享單一存儲器或存儲器組。在SMP存儲系統中，存儲器接口性能對各個處理單元基本上相同，也就是説，對共享存儲的獲取事件各個處理單元基本一致。一羣獨立的處理機或SMP可以由各計算機之間通信鏈路或其他固定路徑，甚至是網絡設備進行互連，從而形成機羣系統。NUMA系統則對其內部的存儲器實現了不同速度的讀/寫，使得存取時間與處理單元訪問的位置相關。

隨着計算機技術的發展和硬件成本的下降，設計人員已經越來越多地尋求實現並行的方式，其中，多處理器並行系統能夠極大地提高計算機系統的性能。在並行處理系統中，個處理單元可以並行執行，平衡輸入的工作負載。目前最普遍採用的並行多處理器組織方式有對稱多處理機（SMP）、機羣系統（Cluster）以及非均勻存儲器（NUMA）三種。SMP採用多個相同或相似的處理器組成，以總線形式或開關陣列互連形成多處理機計算系統，是通常意義上的多處理器計算機。在SMP系統中，最重要的問題就是存儲一致性，每個處理器均具有獨立的存儲即高速緩衝存儲器Cache，當某一行數據出現在不同處理器的Cache中時，如果對一個Cache內容進行修改，那麼其他Cache以及主存中內容也應得到更新。這一問題及時由Cache一致性協議所解決的。機羣系統分是由一組完整的計算機互連形成的，作為統一的計算資源一起進行數據處理，整個機羣外部可以看作是一台機羣進行處理。NUMA系統通過共享存儲器的方式實現多處理機並行工作。NUMA最主要的特點就是系統內某個處理器對存儲字存取時間是隨存儲器字位置而變化。