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

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

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

    對(duì)于計(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ī)，是單指令流對(duì)單數(shù)據(jù)流進(jìn)行操作。

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

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

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

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

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

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

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

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

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

Pram。

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

    對(duì)于同一求解問(wèn)題，在以上三種計(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ù)交換是通過(guò)互聯(lián)網(wǎng)絡(luò)進(jìn)行的。

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

  

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

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

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

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

   1．一維線性連接

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

    

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

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

 

 3．超立方連接

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

 4．樹形連接方式   

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

 

 

5．洗牌—交換連接方式   

    洗牌—交換是一類非常有用的互連結(jié)構(gòu)。對(duì)于n=2 -1個(gè)處理器i將它們按0，1，2， 2 一1編號(hào)，設(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ù)。