一．并行計算機的基本概念

    隨著計算機應用范圍的迅速擴大，使用計算機解決的問題規模也越來越大，因此對計算機運算速度的要求也越來越高。不斷改進元器件的制造工藝，提高硬件速度是提高計算機運算速度的重要途徑之一。近十年來流行的典型微處理器芯片已從最初的8085沿8086，80186，80286，80386一直發展到今天的80586，每一新產品的推出都伴隨著一次速度的升級。除了提高元器件的速度外，改進系統結構也是提高計算機速度的重要途徑之一。特別是在元器件速度達到極限(比如光速)時，后者將更為重要。

    傳統的計算機是串行結構的，每一時刻只能按一條命令指令對一個數據進行操作。為了克服這種傳統結構對提高運算速度的限制，從60年代起開始將并行處理技術引入計算機的結構設計中，利用其對計算機系統結構進行改進。所謂并行處理就是把一個傳統串行處理的任務分解開來，并將其分配給多個處理器同時處理，即在同一時間間隔內增加計算機的操作數量。為并行處理所設計的計算機稱為并行計算機。  

    對于計算機，存在著幾種不同的分類方法，目前大家普遍遵循的是flynn分類法，它首先按指令流的重數將機器分為二類：

 si(single instruction stream)     單指令流;

 mi(multiple instruction stream)   多指令流。

其次，按數據流的重數加以區分：

 sd(single data stream)      單數據流； 

 md(multiple data stream)    多數據流。

這樣，就有4種可能的組合，即sisd，simd，misd，mimd。 

    sisd計算機代表如今使用的大多數串行計算機，是單指令流對單數據流進行操作。

    simd計算機是所謂的陣列機，它有許多個處理單元(Pe)，由同一個控制部件管理，所有Pe都接收控制部件發送的相同指令，對來自不同數據流的數據集合序列進行操作。

    misd計算機從概念上講，則有多個Pe，接收不同的指令，對相同數據進行操作，一般認為misd機目前尚無實際代表，此類結構很少受到人們的注意。

    mimd計算機包括多處理機和多計算機兩類，它們都由可各自執行自己程序的多處理器組成。其中，多處理機以各處理器共享公共存儲器為特征，而多計算機以各處理器經通信鏈路傳遞信息為特征．它們與simd計算機的根本區別在于，simd機中每．臺處理器只能執行中央處理器的指令，而mimd機中每臺處理器僅接受中央處理器分給它的任務，它執行自己的

指令，所以可達到指令、任務并行。

    根據flynn分類法，通用的并行計算機分為simd機和mimd機兩大類，它們是并行算法的物質基礎。對于并行算法的設計者而言，不能僅局限于某種具體的并行機而設計并行算法，而必須從算法的角度，將各種并行機的基本特征加以理想化，抽象出所謂的并行計算機模型，然后在此基礎上研究和設計各種有效的并行算法。由flynn分類法，可將并行計算機分為兩大類，這兩大類也確定了兩大類并行計算模型，即simd和mimd兩類并行計算模型。這兩大類還可進一步細分，simd模型可細分為基于共享存儲的simd模型和基于互連網絡的

simd模型;mimd模型主要可細分為基于共享存儲的mimd模型和基于異步通信的互連網絡模型。

    simd共享存儲模型是假定有有限或無限個功能相同的處理器，每個處理器擁有簡單的

算術運算和邏輯判斷能力，在理想的情況下假定存在一個容量無限大的共享存儲器，在任何時刻，任意一個處理器均可通過共享存儲器的共享單元同其它任何處理器互相交換數據。由于實際情況是共享存儲器的容量是有限的，因此在同一時刻，當多個處理器訪問同一單元時就會發生沖突。根據模型解決沖突的能力，simd共享存儲模型又可進一步分為    (1)不容許同時讀和同時寫。即每次只允許一個處理器讀和寫一個共享單元，這種模型筒記為simd-erew Pram。

    (2)容許同時讀，但不容許同時寫。即每次允許多個處理器同時讀一個共享單元的內容，但每次只允許一個處理器向某個共享單元寫內容，這種計算模型簡記為simd-crew

Pram。

    (3)允許同時讀和寫。即每次容許任意多個處理同時讀和同時寫同一個共享存儲單元，這種計算模型簡記為simd-crcw Pram。

    對于同一求解問題，在以上三種計算模型上設計的并行算法通常是不同的。算法的運算時間也不相同，記三種算法的計算時間為t１，t2，t3，它們滿足下面關系：

    ti≥t2≥t3

    在simd互連網絡模型中，每個處理器在控制器控制下或處于活動狀態，或處于不活動狀態。活動狀態的處理器都執行相同的指令，處理器之間的數據交換是通過互聯網絡進行的。

根據互連網絡的連接方式，simd互連網絡模型又分為兩類。一類是處理器—處理器之間直接互連(稱為閨房式)，如圖9．1所示；另一類是處理器—存儲器之間直接互連(稱為舞廳式)，如下圖所示。從算法設計者來講，這二類無本質差別。因此，以后僅討論閨房式這一類。 

  

 在共享存儲的mimd計算模型中，所有的處理器共享一個公共的存儲器；每個處理器各自完成自己的任務，各處理器之間的通信是通過共享存儲器中的全局變量來實現的。在這種模型上開發的算法稱之為異步并行算法。   

    在基于互連網絡的mimd計算模型中，處理器之間不存在共享存儲器，每個處理器從各自存儲器中存取指令和數據。各處理器之間用通信網絡以信息方式交換數據。在此模型上設計的算法稱為分布式算法。   

 二．并行機的結構  

在基于互連網絡的模型中，由于數據分布存儲，信息通過互連網絡進行傳遞，因此算法與處理器互聯的拓撲結構緊密相關，下面列舉一些常用的互連網絡的拓撲結構。

   1．一維線性連接

 此連接方式是所有并行機中處理器之間一種最簡單的互連方式。其中每個處理器只與其左右近鄰相連(頭尾處理器除外)，如圖所示。

    

  2．二維網孔連接

    在此連接方式中處理器之間按二維陣列形式排列，每個處理器僅與四個相鄰處理器(若有的話)互連，如圖所示。二維網孔連接有二個重要的變種，在這二個變種中，邊界處理器也有線相連接。

 

 3．超立方連接

 對于n＝2 個處理器，可將其組織成一個k—維超立方連接。首先，處理器按0，1，2 -1依次編號，然后，處理器之間按下述方式連接：處理器i與處理器j有線連接當且僅當i與j的二進制表示中僅一位不同。上圖給出了k＝4的四維超立方連接方式。

 4．樹形連接方式   

 樹形連接方式是利用二叉樹這種常用的數據結構組織而成的。對于一棵有d級<編號由根至葉為0到d一1)的滿二叉樹，每個結點表示一個處理器，因此，對于一個具有d級的樹形連接方式，共有n=2 一1個處理器組成。在此結構中，處理器的工作方式通常是：葉子結點對數據進行計算，而內部結點僅負責葉子結點間的通信及簡單的邏輯運算。下圖給出了d＝4的樹形連接結構。  

 

 

5．洗牌—交換連接方式   

    洗牌—交換是一類非常有用的互連結構。對于n=2 -1個處理器i將它們按0，1，2， 2 一1編號，設處理器i的二進制表示為i ,i , i ,i .

下面定義洗牌與交換二個連接函數：

sh(i i …i )=i i …i i

ex(i i …i )=i i i …i

其中 ＝１－i 。在此連接方式中，處理器i與二進制表示為i i …i i i 或i i i …i 的處理器相連。上圖示出了n＝2 的洗牌—交換連接結構，其中實線表示ex函數，虛線表示sh函數。