“計(jì)算機(jī)組成原理”電子教案(第9章)

計(jì)算機(jī)組成原理2第9章并行計(jì)算機(jī)系統(tǒng)9.1并行性的概念9.2向量處理機(jī)9.3陣列處理機(jī)9.4多處理機(jī)系統(tǒng)9.5機(jī)群系統(tǒng)9.6網(wǎng)格計(jì)算3計(jì)算機(jī)系統(tǒng)性能和容量的快速增長(zhǎng)，除了歸功于底層VLSI技術(shù)的發(fā)展之外，另一個(gè)重要因素在于計(jì)算機(jī)體系結(jié)構(gòu)的不斷改進(jìn)，而并行性則是其中的一個(gè)主要方面49.1并行性的概念9.1.1并行性分類9.1.2提高并行性的技術(shù)途徑9.1.3并行性的發(fā)展9.1.4并行計(jì)算機(jī)體系結(jié)構(gòu)分類5所謂并行性，是指計(jì)算機(jī)系統(tǒng)具有可以同時(shí)進(jìn)行運(yùn)算或操作的特性它包括同時(shí)性與并發(fā)性兩種含義同時(shí)性（Simultaneity）是指兩個(gè)或兩個(gè)以上的事件在同一時(shí)刻發(fā)生并發(fā)性（Concurrency）是指兩個(gè)或兩個(gè)以上的事件在同一時(shí)間間隔內(nèi)發(fā)生所謂并行計(jì)算（ParallelComputing）是指通過(guò)網(wǎng)絡(luò)相互連接的兩個(gè)以上的處理機(jī)相互協(xié)調(diào)工作，同時(shí)計(jì)算同一個(gè)任務(wù)的不同部分從而提高問(wèn)題求解速度，或者求解單機(jī)無(wú)法解決的大規(guī)模問(wèn)題6并行計(jì)算的目的⑴提高速度對(duì)于一個(gè)固定規(guī)模的問(wèn)題，采用并行計(jì)算技術(shù)可以使求解時(shí)間更少現(xiàn)在的微型機(jī)也開始借助于流水線技術(shù)、多核技術(shù)等并行計(jì)算技術(shù)來(lái)提高系統(tǒng)的速度⑵擴(kuò)大問(wèn)題求解規(guī)模由于器件本身的限制，任何單處理器的速度不能超過(guò)某個(gè)上限要突破這個(gè)上限，必須采用并行計(jì)算技術(shù)7并行計(jì)算的應(yīng)用領(lǐng)域主要包括： ⑴科學(xué)和工程計(jì)算 ⑵商業(yè)計(jì)算8⑴科學(xué)和工程計(jì)算在計(jì)算領(lǐng)域，計(jì)算機(jī)被用來(lái)模擬那些要么不可能、要么需花費(fèi)很大代價(jià)才能觀測(cè)到的物理現(xiàn)象并行體系結(jié)構(gòu)已經(jīng)成為科學(xué)計(jì)算的中流砥柱物理、化學(xué)、材料科學(xué)、生物學(xué)、天文學(xué)、地球物理等科學(xué)領(lǐng)域的研究都離不開并行計(jì)算對(duì)物理現(xiàn)象建模的工具也被應(yīng)用到工程應(yīng)用中如石油（油藏模擬）、汽車（碰撞模擬、牽引分析、燃料效益）、航空（氣流分析、引擎效率、結(jié)構(gòu)力學(xué)、電磁學(xué)）、制藥學(xué)（分子建模）等9⑵商業(yè)計(jì)算商業(yè)計(jì)算在高端領(lǐng)域也要借助于并行體系結(jié)構(gòu)早在20世紀(jì)60年代中期，多處理器就在商業(yè)計(jì)算的高端市場(chǎng)上嶄露頭角在這個(gè)領(lǐng)域，計(jì)算機(jī)系統(tǒng)的速度和容量直接反映了系統(tǒng)能夠支持的商業(yè)規(guī)模109.1.1并行性分類計(jì)算機(jī)系統(tǒng)中的并行性有不同的等級(jí)從處理數(shù)據(jù)的角度看，并行性等級(jí)從低到高可分為：⑴字串位串同時(shí)只對(duì)一個(gè)字的一位進(jìn)行處理這是最基本的串處理方式，不存在并行性⑵字串位并同時(shí)對(duì)一個(gè)字的全部位進(jìn)行處理，不同字之間是串行的這里已開始出現(xiàn)并行性11⑶字并位串同時(shí)對(duì)許多字的一位進(jìn)行處理這種方式有較高的并行性⑷全并行同時(shí)對(duì)許多字的全部位進(jìn)行處理這是最高一級(jí)的并行性12從執(zhí)行程序的角度看，并行性等級(jí)從低到高可分為：⑴指令內(nèi)部并行一條指令執(zhí)行時(shí)各微操作之間并行。⑵指令級(jí)并行并行執(zhí)行兩條或多條指令⑶任務(wù)級(jí)或過(guò)程級(jí)并行并行執(zhí)行兩個(gè)以上過(guò)程或任務(wù)（程序段）⑷作業(yè)或程序級(jí)并行并行執(zhí)行兩個(gè)以上作業(yè)或程序13并行處理著重挖掘計(jì)算過(guò)程中的并行事件，使并行性達(dá)到較高的級(jí)別并行處理是體系結(jié)構(gòu)、硬件、軟件、算法、語(yǔ)言等多方面綜合研究的領(lǐng)域149.1.2提高并行性的技術(shù)途徑計(jì)算機(jī)系統(tǒng)中提高并行性的措施多種多樣，就其基本思想而言，可歸納成如下四條途徑： 1．時(shí)間重疊 2．資源重復(fù) 3．資源重復(fù)+時(shí)間重疊 4．資源共享151．時(shí)間重疊即時(shí)間并行在并行性概念中引入時(shí)間因素，多個(gè)處理過(guò)程在時(shí)間上相互錯(cuò)開，輪流重疊地使用同一套硬件設(shè)備的各個(gè)部分，以加快硬件周轉(zhuǎn)時(shí)間而贏得速度162．資源重復(fù)即空間并行在并行性概念中引入空間因素，采用以數(shù)量取勝的原則，通過(guò)重復(fù)設(shè)置硬件資源，大幅度提高計(jì)算機(jī)系統(tǒng)的性能隨著硬件價(jià)格的降低，這種方式在單處理機(jī)中廣泛應(yīng)用，而多處理機(jī)本身就是實(shí)施資源重復(fù)原理的結(jié)果173．資源重復(fù)+時(shí)間重疊在計(jì)算機(jī)系統(tǒng)中同時(shí)運(yùn)用空間并行和時(shí)間并行技術(shù)這種方式在計(jì)算機(jī)系統(tǒng)中應(yīng)用廣泛，成為主流的并行技術(shù)184．資源共享這是一種軟件方法，它使多個(gè)任務(wù)按一定時(shí)間順序輪流使用同一套硬件設(shè)備例如多道程序、分時(shí)系統(tǒng)就是遵循資源共享原理而產(chǎn)生的資源共享既降低了成本，又提高了計(jì)算機(jī)設(shè)備的利用率199.1.3并行性的發(fā)展1．單機(jī)系統(tǒng)并行性發(fā)展2．多機(jī)系統(tǒng)并行性發(fā)展201．單機(jī)系統(tǒng)并行性發(fā)展在發(fā)展高性能單處理機(jī)過(guò)程中，起著主導(dǎo)作用的是時(shí)間并行技術(shù)實(shí)現(xiàn)時(shí)間并行的物質(zhì)基礎(chǔ)是部件功能專用化把一件工作按功能分割為若干個(gè)相互聯(lián)系的部分，把每一部分指定給專門的部件完成然后按時(shí)間重疊原理把各部分執(zhí)行過(guò)程在時(shí)間上重疊起來(lái)，使所有部件依次分工完成一組同樣的工作21在單處理機(jī)中，空間并行技術(shù)的運(yùn)用也已經(jīng)十分普遍多體交叉存儲(chǔ)器和多操作部件都是空間并行技術(shù)成功應(yīng)用的結(jié)構(gòu)形式在多操作部件處理機(jī)中，通用部件被分解成若干個(gè)專用的操作部件如加法部件、乘法部件、除法部件、邏輯運(yùn)算部件等一條指令所需的操作部件只要空閑，就可以開始執(zhí)行這條指令這是指令級(jí)并行22在單處理機(jī)中，資源共享概念的實(shí)質(zhì)就是用單處理機(jī)模擬多處理機(jī)的功能，形成所謂的“虛擬機(jī)（VirtualMachine，VM）”的概念例如在分時(shí)系統(tǒng)中，在多終端情況下，每個(gè)終端上的用戶都感覺(jué)自己好像獨(dú)立擁有一臺(tái)處理機(jī)一樣232．多機(jī)系統(tǒng)并行性發(fā)展多機(jī)系統(tǒng)也遵循時(shí)間重疊、資源重復(fù)、資源共享原理，向三種不同的多處理機(jī)方向發(fā)展，但在采取的技術(shù)措施上與單處理機(jī)系統(tǒng)有些差別為了反映多機(jī)系統(tǒng)各機(jī)器之間物理連接的緊密程度及交互能力的強(qiáng)弱，我們引入“耦合度”這個(gè)術(shù)語(yǔ)按照耦合度的不同，可將多機(jī)系統(tǒng)分為緊耦合系統(tǒng)和松耦合系統(tǒng)兩大類緊耦合系統(tǒng)又稱直接耦合系統(tǒng)指計(jì)算機(jī)間物理連接的頻帶較高，一般通過(guò)總線或高速開關(guān)實(shí)現(xiàn)計(jì)算機(jī)間的互連，可以共享主存由于具有較高的信息傳輸率，因而可以快速并行處理作業(yè)或任務(wù)24松耦合系統(tǒng)又稱間接耦合系統(tǒng)一般通過(guò)通道或通信線路實(shí)現(xiàn)計(jì)算機(jī)間的互連，可以共享外存設(shè)備（磁盤、磁帶等）機(jī)器之間的相互作用是在文件或數(shù)據(jù)集一級(jí)上進(jìn)行的松耦合系統(tǒng)表現(xiàn)為兩種形式：一種是多臺(tái)計(jì)算機(jī)和共享外存設(shè)備連接不同機(jī)器之間實(shí)現(xiàn)功能上的分工（功能專用化）機(jī)器處理的結(jié)果以文件或數(shù)據(jù)集的形式送到共享外存設(shè)備，供其他機(jī)器繼續(xù)處理另一種是計(jì)算機(jī)網(wǎng)絡(luò)通過(guò)通信線路連接，以求得更大范圍的資源共享25多處理機(jī)中為了實(shí)現(xiàn)時(shí)間重疊，將處理機(jī)功能分散給各臺(tái)專用處理機(jī)去完成，即功能專用化，各處理機(jī)之間則按時(shí)間重疊原理工作機(jī)器間的耦合程度逐漸加強(qiáng)，從而發(fā)展成為異構(gòu)型多處理機(jī)系統(tǒng)通過(guò)設(shè)置多臺(tái)相同類型的計(jì)算機(jī)而構(gòu)成的容錯(cuò)系統(tǒng)，可使系統(tǒng)工作的可靠性在處理機(jī)一級(jí)得到提高隨著硬件價(jià)格的降低，人們追求的目標(biāo)是通過(guò)多處理機(jī)的并行處理來(lái)提高整個(gè)系統(tǒng)的速度，因此對(duì)計(jì)算機(jī)間互連網(wǎng)絡(luò)的性能提出了更高的要求高帶寬、低延遲、低開銷的機(jī)間互連網(wǎng)絡(luò)，是高效實(shí)現(xiàn)任務(wù)級(jí)并行處理的前提條件為了使并行處理的任務(wù)能夠在處理機(jī)間隨機(jī)地進(jìn)行調(diào)度，就必須使各處理機(jī)具有同等的功能，從而成為同構(gòu)型多處理機(jī)系統(tǒng)269.1.4并行計(jì)算機(jī)體系結(jié)構(gòu)分類根據(jù)指令流和數(shù)據(jù)流的不同，通常把計(jì)算機(jī)系統(tǒng)分為四類：?jiǎn)沃噶盍鲉螖?shù)據(jù)流SISD、單指令流多數(shù)據(jù)流SIMD、多指令流單數(shù)據(jù)流MISD、多指令流多數(shù)據(jù)流MIMD并行計(jì)算機(jī)系統(tǒng)除了少量早期、專用的SIMD系統(tǒng)之外，絕大部分為MIMD系統(tǒng)MIMD型并行計(jì)算機(jī)采用的技術(shù)包括共享地址空間（SharedAddressSpace）和非連接地址空間（DisjointAddressSpace）兩種279.2向量處理機(jī)向量處理的基本概念289.2.1向量處理的基本概念向量處理機(jī)是指令級(jí)并行的計(jì)算機(jī)能較好地發(fā)揮流水線技術(shù)的特性，達(dá)到較高的計(jì)算速度新型的向量流水處理機(jī)采用了多處理機(jī)的體系結(jié)構(gòu) 1．向量處理

291．向量處理從數(shù)學(xué)的概念上講，標(biāo)量（Scalar）是指單個(gè)量向量（Vector）是指一組標(biāo)量例如，有一個(gè)數(shù)組A=(a1,a2,a3,…,an)，其中括號(hào)內(nèi)的每一個(gè)元素ai就是一個(gè)標(biāo)量而A則稱為向量它由一組標(biāo)量組成30【例9-1】用標(biāo)量處理機(jī)和向量處理機(jī)處理以下的向量求解問(wèn)題： Y＝a×X＋Y 其中a為標(biāo)量，X和Y為向量，初始值放在存儲(chǔ)器中31⑴用標(biāo)量處理機(jī)來(lái)處理其本質(zhì)是一個(gè)循環(huán)，計(jì)算過(guò)程如下：用標(biāo)量指令對(duì)向量中的每個(gè)元素進(jìn)行一次乘、加、存儲(chǔ)操作為了實(shí)現(xiàn)循環(huán)操作，每次都必須指明對(duì)X和Y中元素位置的下標(biāo)變量加1，并使操作次數(shù)每次減1，以判斷循環(huán)是否結(jié)束現(xiàn)假定X和Y向量的首元素讀出后放到寄存器RX和RY中，當(dāng)向量元素長(zhǎng)度為64時(shí)，循環(huán)程序段如下：LD F0,a ;標(biāo)量a裝入寄存器F0ADD R4,Rx,#512 ;向量元素的末地址裝入寄存器R4LOOP: LD F2,M(Rx) ;取向量元素X(i)MUL F2,F0,F2 ;a與X(i)相乘LD F4,M(Ry) ;取向量元素Y(i)ADD F4,F2,F4 ;aX(i)與Y(i)相加SD M(Ry),F4 ;存儲(chǔ)結(jié)果向量元素ADD Rx,Rx,#8 ;X向量元素下標(biāo)加1ADD Ry,Ry,#8 ;Y向量元素下標(biāo)加1SUB R20,R4,Rx ;(R4)-(Rx)→R20，計(jì)算是否到界限值BNZ R20,LOOP ;若循環(huán)未結(jié)束，轉(zhuǎn)LOOP32⑵用向量處理機(jī)處理使用向量指令一條向量指令可以一次完成X或Y向量中所有元素的處理因此完成同樣操作的程序段如下：LD F0,a ;標(biāo)量a裝入F0LV V1,M(X) ;向量X裝入V1向量寄存器（LV為向量取指令）MULV V2,F0,V1 ;向量X與標(biāo)量a相乘（MULV為向量乘指令）LV V3,M(Y) ;向量Y裝入V3向量寄存器ADDV V4,V2,V3 ;向量加aX＋Y（ADDV為向量加指令）SV M(Y),V4 ;存儲(chǔ)結(jié)果向量（SV為向量存指令）33對(duì)上述兩段標(biāo)量處理機(jī)、向量處理機(jī)程序簡(jiǎn)單比較可知：向量處理機(jī)只需執(zhí)行6條指令，而標(biāo)量處理機(jī)共需執(zhí)行9×64＋2＝578條指令這是因?yàn)橄蛄恐噶钍菍?duì)向量中的64個(gè)元素一次性進(jìn)行操作，而且沒(méi)有標(biāo)量循環(huán)中對(duì)元素下標(biāo)變量加1和判斷循環(huán)是否結(jié)束的最后4條指令34一條向量指令可以處理N個(gè)或N對(duì)操作數(shù)把這N個(gè)互相獨(dú)立的數(shù)稱為向量對(duì)這樣一組數(shù)的運(yùn)算稱為向量處理因此，向量指令的處理效率要比標(biāo)量指令的處理效率高得多35【例9-2】用高級(jí)語(yǔ)言和向量加法指令分別計(jì)算以下表達(dá)式：

ci＝ai＋5＋bi i＝10,11,12,…,1000【解】 ⑴用高級(jí)語(yǔ)言實(shí)現(xiàn)的代碼如下（以C語(yǔ)言為例）：for(i=10;i<=1000;i++)

c[i]=a[i+5]+b[i]; ⑵在具有向量數(shù)據(jù)表示的機(jī)器中，可用一條向量加法指令實(shí)現(xiàn)： C(10:1000)=A(10+5:1000+5)+B(10:1000)顯然，對(duì)參加運(yùn)算的每個(gè)向量都需指明其基地址、位移量和向量長(zhǎng)度因此，向量加法指令的格式可采用如下形式：向量加A向量參數(shù)B向量參數(shù)C向量參數(shù)369.3陣列處理機(jī)9.3.1陣列處理機(jī)的操作模型和特點(diǎn)379.3.1陣列處理機(jī)的操作模型和特點(diǎn)1.陣列處理機(jī)的操作模型2.陣列處理機(jī)的特點(diǎn)381.陣列處理機(jī)的操作模型陣列處理機(jī)又稱并行處理機(jī)主要技術(shù)手段是采用硬件資源重復(fù)的方法來(lái)實(shí)現(xiàn)并行性屬于SIMD結(jié)構(gòu)計(jì)算機(jī)單指令流多數(shù)據(jù)流SIMD計(jì)算機(jī)用一個(gè)控制部件同時(shí)管理多個(gè)處理單元所有處理單元均收到從控制部件廣播來(lái)的同一條指令，但是操作的對(duì)象卻是不同的數(shù)據(jù)392.陣列處理機(jī)的特點(diǎn)向量流水處理機(jī)和陣列處理機(jī)都能對(duì)大量數(shù)據(jù)進(jìn)行向量處理，但它們之間存在很大的區(qū)別，陣列處理機(jī)有著向量處理機(jī)所不具備的特點(diǎn)：⑴陣列機(jī)是以單指令流多數(shù)據(jù)流方式工作的⑵陣列機(jī)采用資源重復(fù)方法引入空間因素在系統(tǒng)中設(shè)置多個(gè)相同的處理單元來(lái)實(shí)現(xiàn)并行性利用并行性中的同時(shí)性，所有處理單元必須同時(shí)進(jìn)行相同的操作40⑶陣列機(jī)是以某一類算法（如圖像處理）為背景的專用計(jì)算機(jī)由于陣列機(jī)中通常都采用簡(jiǎn)單、規(guī)整的互連網(wǎng)絡(luò)來(lái)實(shí)現(xiàn)處理單元間的連接操作，從而限定了其所適用的求解算法類別⑷陣列機(jī)的研究必須與并行算法的研究密切結(jié)合以使其求解算法的適應(yīng)性更強(qiáng)一些，應(yīng)用面更廣一些⑸從處理單元來(lái)看，由于結(jié)構(gòu)都相同，因而可將陣列機(jī)看成是一個(gè)同構(gòu)型并行機(jī)但其控制器實(shí)質(zhì)上是一個(gè)標(biāo)量處理機(jī)而為了完成I/O操作及操作系統(tǒng)管理，尚需一個(gè)前端機(jī)因此，實(shí)際的陣列機(jī)系統(tǒng)是由上述三部分構(gòu)成的一個(gè)異構(gòu)型多處理機(jī)系統(tǒng)419.4多處理機(jī)系統(tǒng)9.4.1多處理機(jī)系統(tǒng)的特點(diǎn)和分類42隨著集成電路技術(shù)的不斷發(fā)展，基于微處理器的多處理機(jī)并行系統(tǒng)由于其突出的性價(jià)比而逐漸成為高性能計(jì)算機(jī)的主流439.4.1多處理機(jī)系統(tǒng)的特點(diǎn)和分類1.多處理機(jī)系統(tǒng)的特點(diǎn)2.多處理機(jī)系統(tǒng)的分類441.多處理機(jī)系統(tǒng)的特點(diǎn)多處理機(jī)的體系結(jié)構(gòu)由若干臺(tái)獨(dú)立的計(jì)算機(jī)組成，每臺(tái)計(jì)算機(jī)能夠獨(dú)立執(zhí)行自己的程序在多處理機(jī)系統(tǒng)中，處理機(jī)與處理機(jī)之間通過(guò)互連網(wǎng)絡(luò)進(jìn)行連接，從而實(shí)現(xiàn)程序之間的數(shù)據(jù)交換和同步多處理機(jī)屬于MIMD計(jì)算機(jī)，與屬于SIMD計(jì)算機(jī)的陣列處理機(jī)相比有很大的差別，其本質(zhì)差別在于并行性等級(jí)不同：多處理機(jī)要實(shí)現(xiàn)任務(wù)或作業(yè)一級(jí)的并行陣列處理機(jī)只實(shí)現(xiàn)指令一級(jí)的并行452.多處理機(jī)系統(tǒng)的分類按多處理機(jī)各機(jī)器之間物理連接的緊密程度與交互作用能力的強(qiáng)弱來(lái)分，多處理機(jī)可分為緊耦合系統(tǒng)和松耦合系統(tǒng)兩大類在緊耦合多處理機(jī)系統(tǒng)中，處理機(jī)間物理連接的頻帶較高，一般是通過(guò)總線或高速開關(guān)實(shí)現(xiàn)互連，可以共享主存儲(chǔ)器由于具有較高的信息傳輸率，因而可以快速并行處理作業(yè)或任務(wù)松耦合多處理機(jī)系統(tǒng)由多臺(tái)獨(dú)立的計(jì)算機(jī)組成，一般通過(guò)通道或通信線路實(shí)現(xiàn)處理機(jī)間的互連，可以共享外存設(shè)備機(jī)器之間的相互作用是以較低頻帶在文件或數(shù)據(jù)集一級(jí)上進(jìn)行的46按處理機(jī)的結(jié)構(gòu)是否相同來(lái)分，如果每個(gè)處理機(jī)是同類型的，且完成同樣的功能，稱為同構(gòu)型多處理機(jī)系統(tǒng)如果多處理機(jī)是由多個(gè)不同類型，且擔(dān)負(fù)不同功能的處理機(jī)組成，則稱為異構(gòu)型多處理機(jī)系統(tǒng)479.5機(jī)群系統(tǒng)機(jī)群的定義489.5.1機(jī)群的定義機(jī)群系統(tǒng)（Cluster）的定義一組完整的計(jì)算機(jī)互連，它們作為一個(gè)統(tǒng)一的計(jì)算機(jī)資源一起工作，并能產(chǎn)生一臺(tái)機(jī)器的印象完整的計(jì)算機(jī)是指一臺(tái)計(jì)算機(jī)離開機(jī)群系統(tǒng)仍能運(yùn)行自己的任務(wù)機(jī)群系統(tǒng)中的每臺(tái)計(jì)算機(jī)一般稱為結(jié)點(diǎn)49機(jī)群是并行或分布計(jì)算機(jī)系統(tǒng)的一種類型是由一組完整的計(jì)算機(jī)（結(jié)點(diǎn)）通過(guò)高性能的網(wǎng)絡(luò)或局域網(wǎng)互連而成的系統(tǒng)作為一個(gè)單獨(dú)的統(tǒng)一計(jì)算資源來(lái)使用50首先，機(jī)群由完整的計(jì)算機(jī)（結(jié)點(diǎn)）互連而成機(jī)群的結(jié)點(diǎn)可以是一個(gè)工作站，或者是一臺(tái)個(gè)人計(jì)算機(jī)，但也可以是一臺(tái)規(guī)模相當(dāng)大的對(duì)稱多處理機(jī)SMP在機(jī)群的每個(gè)結(jié)點(diǎn)上除了有一臺(tái)或