一．并行計(jì)算機(jī)的基本概念

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

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

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

 si(single instruction stream)     單指令流;

 mi(multiple instruction stream)   多指令流。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Pram。

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

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

    ti≥t2≥t3

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

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

  

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

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

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

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

   1．一維線性連接

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

    

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

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

 

 3．超立方連接

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

 4．樹形連接方式   

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

 

 

5．洗牌—交換連接方式   

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

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

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

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

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