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

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

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

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

 si(single instruction stream)     單指令流;

 mi(multiple instruction stream)   多指令流。

其次，按數(shù)據(jù)流的重數(shù)加以區(qū)分：

 sd(single data stream)      單數(shù)據(jù)流； 

 md(multiple data stream)    多數(shù)據(jù)流。

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

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

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

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

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

指令，所以可達到指令、任務(wù)并行。

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

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

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

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

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

Pram。

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

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

    ti≥t2≥t3

    在simd互連網(wǎng)絡(luò)模型中，每個處理器在控制器控制下或處于活動狀態(tài)，或處于不活動狀態(tài)。活動狀態(tài)的處理器都執(zhí)行相同的指令，處理器之間的數(shù)據(jù)交換是通過互聯(lián)網(wǎng)絡(luò)進行的。

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

  

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

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

 二．并行機的結(jié)構(gòu)  

在基于互連網(wǎng)絡(luò)的模型中，由于數(shù)據(jù)分布存儲，信息通過互連網(wǎng)絡(luò)進行傳遞，因此算法與處理器互聯(lián)的拓撲結(jié)構(gòu)緊密相關(guān)，下面列舉一些常用的互連網(wǎng)絡(luò)的拓撲結(jié)構(gòu)。

   1．一維線性連接

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

    

  2．二維網(wǎng)孔連接

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

 

 3．超立方連接

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

 4．樹形連接方式   

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

 

 

5．洗牌—交換連接方式   

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

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

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 的洗牌—交換連接結(jié)構(gòu)，其中實線表示ex函數(shù)，虛線表示sh函數(shù)。