向量流水與向量處理機(jī)學(xué)習(xí)教案

1、向量向量(xingling)流水與向量流水與向量(xingling)處處理機(jī)理機(jī)第一頁(yè)，共48頁(yè)。第1頁(yè)/共48頁(yè)第二頁(yè)，共48頁(yè)。 1.向量流水的概念 向量中各元素之間有固定的位置或者聯(lián)系，在運(yùn)算時(shí)各元素相互獨(dú)立或關(guān)系很少。向量運(yùn)算時(shí)各元素一般進(jìn)行相同的操作。這樣，只要能從存儲(chǔ)器中不斷(bdun)地取出這些元素，就能進(jìn)行流水處理，發(fā)揮流水線(xiàn)的效能。 這樣，把向量數(shù)據(jù)表示與流水線(xiàn)技術(shù)結(jié)合起來(lái)，就構(gòu)成向量流水處理機(jī)，簡(jiǎn)稱(chēng)為向量流水機(jī)或向量處理機(jī)（Vector Processor）。第2頁(yè)/共48頁(yè)第三頁(yè)，共48頁(yè)。 2.向量(xingling)流水處理的主要特點(diǎn) 一條向量(xingling)指令

2、相當(dāng)于一個(gè)標(biāo)量循環(huán)。這樣，可降低對(duì)指令訪(fǎng)問(wèn)速度（帶寬）的要求，還可消除標(biāo)量機(jī)中由于循環(huán)而引起的控制（資源）相關(guān)。 每一個(gè)結(jié)果元素僅與參加運(yùn)算的元素有關(guān)，與上一次運(yùn)算的值無(wú)關(guān)，因此向量(xingling)流水線(xiàn)可以有較大的深度。 若要訪(fǎng)問(wèn)的向量(xingling)元素相鄰，可存儲(chǔ)到多體交叉存儲(chǔ)器中，以提高訪(fǎng)存速度。 在一般向量(xingling)流水機(jī)中，允許訪(fǎng)問(wèn)存儲(chǔ)器與有效地址的計(jì)算流水化，在高檔向量(xingling)流水機(jī)中還允許多個(gè)向量(xingling)操作同時(shí)進(jìn)行，即多向量(xingling)并行操作。第3頁(yè)/共48頁(yè)第四頁(yè)，共48頁(yè)。 1.向量處理機(jī)的類(lèi)型 向量元素及其處理的結(jié)果元

3、素可存放在存儲(chǔ)器中，也可存放在寄存器堆中，故可分為兩種類(lèi)型：存儲(chǔ)器-存儲(chǔ)器型和寄存器-寄存器型。 早期的向量處理機(jī)多屬于存儲(chǔ)器-存儲(chǔ)器型，比如TI公司(n s)的ASC機(jī)，CDC公司(n s)的STAR100以及CYBER-205和ETA-10等。 第4頁(yè)/共48頁(yè)第五頁(yè)，共48頁(yè)。 2.向量處理機(jī)的基本組成 1976年美國(guó)CRAY公司推出寄存器-寄存器結(jié)構(gòu)(jigu)的向量機(jī)，易操作，速度快，指令系統(tǒng)簡(jiǎn)潔，因而很快成為向量處理機(jī)的主流機(jī)型。比如CRAY公司的Y-MP和C-90，日本Fujitsu公司的VP2000、VPP300/500，以及我國(guó)的YH等。 向量機(jī)的基本結(jié)構(gòu)(jigu)如圖5.

4、1所示，由一個(gè)標(biāo)量流水部件和一個(gè)向量流水部件組成。其中標(biāo)量流水部件是為實(shí)現(xiàn)向量中的標(biāo)量運(yùn)算而設(shè)置的，包括標(biāo)量功能部件和若干個(gè)標(biāo)量寄存器。向量流水部件主要用于向量運(yùn)算，包括向量功能部件、向量存取部件、向量寄存器以及向量控制器等。第5頁(yè)/共48頁(yè)第六頁(yè)，共48頁(yè)。圖5.1 向量處理機(jī)基本系統(tǒng)結(jié)構(gòu) 第6頁(yè)/共48頁(yè)第七頁(yè)，共48頁(yè)。3.向量運(yùn)算 【例5.1】設(shè)有長(zhǎng)度同為64的兩個(gè)向量X和Y，其地址分別由寄存器Rx和Ry表示(biosh)，通過(guò)分析Y=aX+Y，來(lái)說(shuō)明向量運(yùn)算過(guò)程，其中a 為標(biāo)量。 解：根據(jù)題意a為標(biāo)量，每一個(gè)向量元素占8個(gè)字節(jié)單元，在標(biāo)量計(jì)算機(jī)中通過(guò)循環(huán)程序?qū)崿F(xiàn)向量運(yùn)算，程序如下：

5、LD F0，a， ；標(biāo)量a送入寄存器F0 ADDI R4，Rx，#512 ；向量元素的末地址送入R4 LOOP：LD F2，0(Rx) ；取向量元素X(i) MULD F2，F(xiàn)0，F(xiàn)2 ；F2aX(i) LD F4，0(Ry) ；取向量元素Y(i) ADDD F4，F(xiàn)2，F(xiàn)4 ；F4aX(i)+ Y(i) SD 0(Ry)，F(xiàn)4 ；存結(jié)果元素 ADDI Rx，Rx，#8 ；修改向量X元素的下標(biāo) ADDI Ry，Ry，#8 ；修改向量Y元素的下標(biāo) SUB R10，R4，Rx ；R10(R4)-(Rx) BNZ R10，LOOP ；若沒(méi)有結(jié)束轉(zhuǎn)移到LOOP第7頁(yè)/共48頁(yè)第八頁(yè)，共48頁(yè)。 在向量

6、機(jī)上使用(shyng)向量機(jī)指令編程如下，其中Rx和Ry表示向量寄存器： LD F0，a ；標(biāo)量a送入寄存器F0 LV V1，Rx ；取向量X MULTV V2，F(xiàn)0，V1 ；V2aX LV V3，Ry ；取向量Y ADDV V4，V2，V3 ；V4aX+ Y SV Ry，V4 ；存結(jié)果 通過(guò)對(duì)上述程序進(jìn)行分析可以看出，在標(biāo)量機(jī)上進(jìn)行運(yùn)算共執(zhí)行964+2=578條指令，其中還包含大量的延遲等待。而在向量機(jī)上進(jìn)行運(yùn)算，僅需要6條向量指令。第8頁(yè)/共48頁(yè)第九頁(yè)，共48頁(yè)。 在向量流水過(guò)程中也存在啟動(dòng)時(shí)間Tst，相當(dāng)于標(biāo)量流水線(xiàn)中填入時(shí)間，以設(shè)置向量操作所涉及到的參數(shù)，比如設(shè)置向量長(zhǎng)度等。啟動(dòng)后結(jié)

7、果連續(xù)輸出，每輸出一個(gè)結(jié)果的時(shí)間稱(chēng)為結(jié)果流出時(shí)間，可用Ir表示(biosh)。若設(shè)向量長(zhǎng)度為n，則一條向量指令執(zhí)行時(shí)間可表示(biosh)如下： Tvp=Tst+nIr （5.1） 【例5.2】在一個(gè)向量乘法流水線(xiàn)中，向量啟動(dòng)時(shí)間為10個(gè)時(shí)鐘周期，啟動(dòng)后1個(gè)時(shí)鐘周期流出一個(gè)結(jié)果，若向量長(zhǎng)度為64，試求產(chǎn)生每一個(gè)結(jié)果向量元素所用的平均時(shí)間。 解：根據(jù)題意，Tst=10，Ir=1，n=64，則產(chǎn)生每一個(gè)結(jié)果向量元素的平均時(shí)間Tav為：Tav= = = = 1.16 TvpnTst+nIrn10+64164第9頁(yè)/共48頁(yè)第十頁(yè)，共48頁(yè)。 可以看出，對(duì)于運(yùn)算速度較慢的向量流水操作，啟動(dòng)時(shí)間影響不大

8、；對(duì)于速度較快向量流水操作，啟動(dòng)時(shí)間會(huì)產(chǎn)生較大的影響。 對(duì)于寄存器-寄存器型向量處理機(jī)來(lái)說(shuō)，向量啟動(dòng)時(shí)間主要取決于功能部件流水線(xiàn)的深度(shnd)，結(jié)果流出時(shí)間取決于向量功能部件以多快的頻率接收數(shù)據(jù)。當(dāng)向量較長(zhǎng)時(shí)，啟動(dòng)穩(wěn)定后的結(jié)果流出時(shí)間可視為1。第10頁(yè)/共48頁(yè)第十一頁(yè)，共48頁(yè)。 1.向量操作(cozu)長(zhǎng)度控制（1）向量寄存器長(zhǎng)度 在寄存器-寄存器型向量處理機(jī)中向量由向量寄存器存儲(chǔ)，向量寄存器的個(gè)數(shù)稱(chēng)為向量寄存器長(zhǎng)度，可用N來(lái)表示。比如，CRAY-1的向量寄存器長(zhǎng)度為64。（2）向量長(zhǎng)度與向量長(zhǎng)度寄存器 在實(shí)際運(yùn)算中向量長(zhǎng)度n不一定正好等于向量寄存器的長(zhǎng)度，可能小于也可能大于向量寄存器

9、的長(zhǎng)度。因此，需用向量長(zhǎng)度寄存器存放向量長(zhǎng)度。 （3）向量操作(cozu)長(zhǎng)度控制 這里仍以Y=aX+Y為例來(lái)說(shuō)明。設(shè)向量長(zhǎng)度為n，F(xiàn)ORTRAN程序如下： DO 10 I=1，n 10 Y(I)= a*X(I)+Y(I) 其中向量長(zhǎng)度依賴(lài)于n，往往是一個(gè)過(guò)程參數(shù)，為此需設(shè)置一個(gè)向量長(zhǎng)度寄存器VL，向量寄存器的長(zhǎng)度用MVL表示。第11頁(yè)/共48頁(yè)第十二頁(yè)，共48頁(yè)。 當(dāng)向量長(zhǎng)度小于向量寄存器的長(zhǎng)度時(shí)，直接存入向量寄存器，其長(zhǎng)度存入向量長(zhǎng)度寄存器中。如果向量長(zhǎng)度大于向量寄存器的長(zhǎng)度時(shí)，須分段存儲(chǔ)和運(yùn)算。向量長(zhǎng)度寄存器的值等于向量寄存器長(zhǎng)度MVL。采用分段技術(shù)后，上述程序可修改成如下形式(xngs

10、h)： LOW=1 VL=(n MOD MVL) ；取向量的零頭 DO 20 J=0，(N/MVL) ；確定外循環(huán)次數(shù) DO 10 I=LOW，LOW+VL-1 ；按長(zhǎng)度VL操作 Y(I)= a*X(I)+Y(I) ；運(yùn)算 10 CONTINUE LOW=LOW+VL ；指向下一次開(kāi)始運(yùn)算的向量 VL=MVL ；修改向量長(zhǎng)度寄存器的值 20 CONTINUE 在上述分段運(yùn)算中，第一次運(yùn)算的長(zhǎng)度為（n MOD MVL），以后各次的長(zhǎng)度為MVL，循環(huán)次數(shù)為(N/MVL)+1。第12頁(yè)/共48頁(yè)第十三頁(yè)，共48頁(yè)。 2.向量訪(fǎng)問(wèn)(fngwn)步長(zhǎng)與跨步訪(fǎng)問(wèn)(fngwn) 目前，存儲(chǔ)器一般采用一維地址

11、，若存儲(chǔ)二維或者多維數(shù)組時(shí)，須將其元素映象到一維地址空間中。常以行或列為主來(lái)存儲(chǔ)各個(gè)元素。對(duì)于以行為主的存儲(chǔ)方式，當(dāng)按行訪(fǎng)問(wèn)(fngwn)時(shí)各行元素地址相鄰；按列訪(fǎng)問(wèn)(fngwn)時(shí)，各列中相鄰元素不再相鄰。這個(gè)間隔稱(chēng)為跨步，這時(shí)的訪(fǎng)問(wèn)(fngwn)稱(chēng)為跨步訪(fǎng)問(wèn)(fngwn)。例如，設(shè)有100100的數(shù)組A和B，求C=AB。設(shè)計(jì) FORTRAN循環(huán)程序如下： DO 10 I=1，100 DO 10 J=1，100 C(I，J)=0.0 DO 10 K=1，100 10 A(I，J)= C(I，J)+ A(I，K)*B(K，J)第13頁(yè)/共48頁(yè)第十四頁(yè)，共48頁(yè)。 按照K循環(huán)讀取存儲(chǔ)器中的數(shù)據(jù)

12、時(shí)，數(shù)組A的元素按行存儲(chǔ)，按行讀取，數(shù)據(jù)地址連續(xù)；數(shù)組B的元素按行存儲(chǔ)，按列讀取，地址不連續(xù)，跨步為100。 但是向量元素讀出存入向量寄存器之后，邏輯上連續(xù)。如果向量處理機(jī)能支持對(duì)向量元素的跨步訪(fǎng)問(wèn)，稱(chēng)為支持完全一維數(shù)據(jù)顯式訪(fǎng)問(wèn)。它能以行、列甚至對(duì)角線(xiàn)的方向訪(fǎng)問(wèn)數(shù)組元素。上述CRAY-1巨型機(jī)就屬于這種類(lèi)型。而CYBER-205采用存儲(chǔ)器-存儲(chǔ)器結(jié)構(gòu)，不支持這種完全一維數(shù)據(jù)顯式訪(fǎng)問(wèn)。 通常，向量處理機(jī)要有一個(gè)專(zhuān)用地址流部件，來(lái)進(jìn)行這種跨步向量元素的訪(fǎng)問(wèn)，甚至支持子矩陣訪(fǎng)問(wèn)、上下三角形和平行四邊形訪(fǎng)問(wèn)。 3. 多體交叉存儲(chǔ)器的使用 為提高(t go)訪(fǎng)存速率，大多數(shù)計(jì)算機(jī)采用低位地址交叉多體存儲(chǔ)

13、器。當(dāng)向量機(jī)支持跨步訪(fǎng)問(wèn)時(shí)，可能出現(xiàn)對(duì)同一存儲(chǔ)體訪(fǎng)問(wèn)的時(shí)間間隔小于存儲(chǔ)器的訪(fǎng)問(wèn)周期，從而出現(xiàn)沖突。 設(shè)某處理機(jī)有16個(gè)存儲(chǔ)體，訪(fǎng)問(wèn)時(shí)間為12個(gè)時(shí)鐘周期，共有64個(gè)向量元素?？绮綖?時(shí)，共需12+64=76個(gè)時(shí)鐘周期；若跨步為16的整倍數(shù)，每個(gè)元素的讀寫(xiě)時(shí)間為12個(gè)時(shí)鐘周期，訪(fǎng)問(wèn)64個(gè)元素的時(shí)間為6412=768個(gè)時(shí)鐘周期。為了訪(fǎng)存不沖突，跨步應(yīng)當(dāng)與存儲(chǔ)體數(shù)互質(zhì)，比如存儲(chǔ)體數(shù)為17，跨步為16。第14頁(yè)/共48頁(yè)第十五頁(yè)，共48頁(yè)。第15頁(yè)/共48頁(yè)第十六頁(yè)，共48頁(yè)。 在向量機(jī)中各種運(yùn)算(yn sun)可采用不同的加工方式，主要有三種，即橫向加工、縱向加工和縱橫向加工。設(shè)有長(zhǎng)度為n的三個(gè)向量A

14、、B和C，以求D=A(B+C)為例，說(shuō)明向量處理的方法。 1.橫向加工 橫向加工是一種最普通的加工方式，它是按照向量的順序計(jì)算，即 D1=A1(B1+C1) D2=A2(B2+C2) Dn=An(Bn+Cn) 這種方法是逐個(gè)計(jì)算D的n個(gè)分量。先計(jì)算K1(B1+C1)，然后計(jì)算D1A1K1。這樣共出現(xiàn)n次數(shù)據(jù)相關(guān)和2n次功能部件的切換，不適合向量流水處理。第16頁(yè)/共48頁(yè)第十七頁(yè)，共48頁(yè)。 2.縱向加工 也稱(chēng)為垂直加工法，它是先進(jìn)行所有縱向B+C的操作，中間結(jié)果暫存到中間向量K中，然后(rnhu)再進(jìn)行所有縱向乘法操作AK，如圖5.2所示。 用向量指令的形式表示，形式如下： K=B+C D=

15、KA 采用這種方法，數(shù)據(jù)相關(guān)僅在向量指令間發(fā)生一次，流水線(xiàn)功能部件的切換也僅有一次。但是需要使用一個(gè)(y )中間向量K。圖5.2 縱向加工方法 第17頁(yè)/共48頁(yè)第十八頁(yè)，共48頁(yè)。 3.縱橫向加工 當(dāng)參加運(yùn)算的向量長(zhǎng)度n大于向量寄存器的長(zhǎng)度N時(shí)，需要(xyo)分段進(jìn)行，這樣就產(chǎn)生了縱橫向加工方式。段內(nèi)縱向加工，段間橫向加工，表示如下： 第一段計(jì)算： K1N=B1N+C1N D1N= K1NA1N 第二段計(jì)算： KN+12N=BN+12N+CN+12N DN+12N= KN+12NAN+12N 顯然每一段兩條向量指令、一次數(shù)據(jù)相關(guān)和兩次流水線(xiàn)功能部件切換，中間向量寄存器長(zhǎng)度為N。第18頁(yè)/共4

16、8頁(yè)第十九頁(yè)，共48頁(yè)。 在向量處理機(jī)中一般(ybn)都采用多個(gè)獨(dú)立的功能部件，以完成不同的操作。例如CRAY-1巨型機(jī)設(shè)有4組12個(gè)單功能流水部件，其中第一組是向量操作部件，包括向量加、移位和邏輯運(yùn)算三個(gè)部分；第二組是浮點(diǎn)運(yùn)算部件，包括浮點(diǎn)加、乘法運(yùn)算和迭代求倒數(shù)三個(gè)部分；第三組是標(biāo)量功能部件，包括標(biāo)量加、移位、邏輯運(yùn)算和數(shù)“1”/計(jì)數(shù)四個(gè)部分；第四組是地址運(yùn)算部件，包括整數(shù)加和整數(shù)乘兩個(gè)部分。其邏輯組成如圖5.3所示。第19頁(yè)/共48頁(yè)第二十頁(yè)，共48頁(yè)。 1.多功能部件(bjin)的并行操作 圖5.3 CRAY-1處理機(jī)結(jié)構(gòu)示意圖 第20頁(yè)/共48頁(yè)第二十一頁(yè)，共48頁(yè)。 圖5.3中，各

17、個(gè)功能(gngnng)部件相互獨(dú)立，只要滿(mǎn)足一定的約束條件就能并行工作，即不存在向量寄存器使用沖突，不存在功能(gngnng)部件使用沖突。（1）向量寄存器使用沖突 例如： V5V1+V2 V4V2V3 這兩條向量指令都使用向量寄存器V2作為源操作向量，因此兩條指令不能同時(shí)執(zhí)行。類(lèi)似地，還有結(jié)果向量寄存器沖突。第21頁(yè)/共48頁(yè)第二十二頁(yè)，共48頁(yè)。 （2）功能部件使用沖突 例如： V1V2+V3 V4V5+V6 兩條指令都要使用浮點(diǎn)加法器，因此誰(shuí)也不能執(zhí)行。 理想情況下，若有M個(gè)相互獨(dú)立的功能部件，應(yīng)當(dāng)使系統(tǒng)速度提高M(jìn)倍。但是由于存在可能出現(xiàn)的沖突，使得能完全(wnqun)并行工作的功能部件

18、往往小于M。 2.向量鏈接技術(shù) （1）向量鏈接技術(shù)的概念 在向量操作中也可象標(biāo)量機(jī)中使用定向傳送技術(shù)那樣來(lái)提高執(zhí)行部件的速度，稱(chēng)為向量鏈接技術(shù)。設(shè)有如下指令序列： ADDV V1，V2，V3 ；V1V2+V3 MULTV V4，V1，V5 ；V4V1V5第22頁(yè)/共48頁(yè)第二十三頁(yè)，共48頁(yè)。 第一條加法結(jié)果存入V1，后一條使用V1作為源操作向量，即先寫(xiě)后讀數(shù)據(jù)相關(guān)。若寄存器V1在同一時(shí)鐘周期既接收加法運(yùn)算結(jié)果，又把這一結(jié)果送到乘法部件，就能使兩個(gè)部件鏈接(lin ji)起來(lái)工作，稱(chēng)為超級(jí)向量操作。充分流水狀態(tài)后，一個(gè)時(shí)鐘周期就可獲取兩個(gè)運(yùn)算結(jié)果。（2）向量鏈接(lin ji)技術(shù)的實(shí)現(xiàn) 需設(shè)

19、專(zhuān)門(mén)機(jī)制，檢測(cè)每一條向量指令能否與前一條指令鏈接(lin ji)操作。若能，則把前一條指令執(zhí)行的第一結(jié)果分量作為本指令的源操作數(shù)，并啟動(dòng)本指令。以D=A(B+C)為例： 第23頁(yè)/共48頁(yè)第二十四頁(yè)，共48頁(yè)。 設(shè)向量長(zhǎng)度n64，且向量B和C已經(jīng)取至向量寄存器V0和V1。這樣，可用三條指令完成： LD V3，A ；V3A ADDV V2，V0，V1 ；V2V0+V1 MULTV V4，V2，V3 ；V4V2V3 前二條指令沒(méi)有向量寄存器沖突，也沒(méi)有功能部件沖突，并行執(zhí)行。第三條指令與前兩條指令均存在先寫(xiě)后讀的數(shù)據(jù)(shj)相關(guān)，因此可與前兩條指令鏈接執(zhí)行，如圖5.4所示。第24頁(yè)/共48頁(yè)第二

20、十五頁(yè)，共48頁(yè)。 圖5.4 向量并行操作與鏈接 三條指令(zhlng)全部順序執(zhí)行，節(jié)拍數(shù)為： (1+6+1)+n-1+ (1+6+1)+n-1+ (1+7+1)+n-1=3n+22 前兩條指令(zhlng)并行執(zhí)行，再與第三條指令(zhlng)順序執(zhí)行，節(jié)拍數(shù)為： (1+6+1)+n-1+ (1+7+1)+n-1=2n+15 第25頁(yè)/共48頁(yè)第二十六頁(yè)，共48頁(yè)。 如果前兩條指令并行執(zhí)行，且與第三條指令鏈接，節(jié)拍數(shù)為： (1+6+1)+(1+7+1)+n-1=n+16 注意：實(shí)現(xiàn)鏈接除了上述約束條件之外還有時(shí)間上的要求，即在前一條指令的第一個(gè)結(jié)果分量送入結(jié)果向量寄存器的那一時(shí)鐘周期才能鏈

21、接，否則無(wú)法再鏈接。另外，兩條向量指令所處理(chl)的向量的長(zhǎng)度也必須相等。 3.加快條件語(yǔ)句執(zhí)行與稀疏矩陣的加速處理(chl)方法 （1）加快條件語(yǔ)句執(zhí)行 對(duì)于條件語(yǔ)句的執(zhí)行，可采用向量屏蔽技術(shù)，設(shè)有如下FORTRAN循環(huán)程序：DO 10 I=1，64 IF （A(I).NE.0） THEN A(I)=A(I)-B(I) ENDIF 10 CONTINUE第26頁(yè)/共48頁(yè)第二十七頁(yè)，共48頁(yè)。 采用向量屏蔽技術(shù)，使減法僅在A(I)0時(shí)執(zhí)行。在高檔向量機(jī)中設(shè)有屏蔽向量寄存器VM?？赏ㄟ^(guò)向量測(cè)試指令對(duì)向量A(I)進(jìn)行0測(cè)試，當(dāng)A(I)中某元素為0時(shí)，屏蔽向量寄存器的相應(yīng)位清0；而A(I)0時(shí)

22、，則將相應(yīng)位置1。這樣，對(duì)應(yīng)于屏蔽向量寄存器為1的位的元素可以參加運(yùn)算，為0的位的元素不能參加運(yùn)算。程序如下，設(shè)向量A和B的起始地址在寄存器Ra和Rb中。 LV V1，Ra ；將向量A裝入V1 LV V2，Rb ；將向量B裝入V2 LD F0，#0 ；F00 SENSV F0，V1 ；若V1(I)0時(shí)，VM(I)置1，否則清0 SUBV V1，V1，V2 ；在屏蔽向量的控制下進(jìn)行減法運(yùn)算 CVM ；將屏蔽向量寄存器置全1，即不再屏蔽 SV Ra，V1 ；存結(jié)果(ji gu) 其中SENSV是設(shè)置屏蔽向量的指令，SUBV是在屏蔽向量的控制下進(jìn)行減法運(yùn)算的指令；CVM是清除屏蔽向量寄存器的指令，將

23、VM的所有位置1，不再屏蔽。第27頁(yè)/共48頁(yè)第二十八頁(yè)，共48頁(yè)。 （2）稀疏矩陣的加速(ji s)處理方法 稀疏矩陣是包含大量0元素的矩陣，典型的稀疏矩陣求和運(yùn)算的程序如下： DO 10 I=1，n 10 A(K(I)=A(K(I)+B(M(I) 這里使用了指標(biāo)向量K和M指示A和B中的非零元素。在這一運(yùn)算中，要求A和B有相同的非零向量長(zhǎng)度n。此外，也可以使用位向量來(lái)指明其中的非零元素。 在向量處理機(jī)中支持這種稀疏矩陣運(yùn)算的基本結(jié)構(gòu)是使用指標(biāo)向量的散射-聚合(Scatter gather)操作，如圖5.5所示。其中聚合操作如圖5.5（a）所示，根據(jù)指標(biāo)向量的內(nèi)容選取向量元素，它的地址由基地址

24、加上指標(biāo)向量中給定的地址偏移量而形成。比如指標(biāo)向量寄存器I=1單元的內(nèi)容（偏移量）為4，與基地址100相加，再取稀疏向量104單元的600送入稠密向量寄存器I=1單元。聚合操作后得稠密向量。 若要恢復(fù)成稀疏向量，可使用散射操作，借助于同一指標(biāo)向量來(lái)完成，其過(guò)程如圖5.5（b）所示，與聚合操作正好相反。第28頁(yè)/共48頁(yè)第二十九頁(yè)，共48頁(yè)。圖5.5 向量的聚合與散射 第29頁(yè)/共48頁(yè)第三十頁(yè)，共48頁(yè)。 4.向量歸約操作的加速(ji s)方法 對(duì)于象一維數(shù)組那樣的向量歸約求值，結(jié)果是一個(gè)標(biāo)量值。對(duì)向量歸約（Reduction）操作往往難以向量化。但是，可根據(jù)運(yùn)算的類(lèi)型和過(guò)程進(jìn)行分解，找出向量

25、化的操作，分別處理。從而提高整體運(yùn)算的速度。下面以向量點(diǎn)積為例說(shuō)明： RED=0.0 DO 10 I=1，64 10 RED=RED+A(I)*B(I) 增加了一個(gè)乘積向量，這就使第一步運(yùn)算可以實(shí)現(xiàn)向量化；第二步進(jìn)行遞推歸約運(yùn)算。對(duì)于遞推規(guī)約運(yùn)算還可采用(ciyng)遞歸折疊法進(jìn)行： L=32 DO 30 J=1，6 DO 10 I=1，L 10 RED(I)=RED(I)+ RED(I+L) L=L/2 30 CONTINUE由于迭代層間數(shù)據(jù)相關(guān)，無(wú)法直接向量化。但是，可先進(jìn)行(jnxng)乘法運(yùn)算，再進(jìn)行(jnxng)歸約。使前者運(yùn)算向量化，程序如下： DO 10 I=1，6410 RED

26、(I)= A(I)*B(I) RED1=0.0 DO 20 I=1，6420 RED1=RED1+RED(I) 第30頁(yè)/共48頁(yè)第三十一頁(yè)，共48頁(yè)。 評(píng)價(jià)向量處理性能的參數(shù)主要有機(jī)器向量長(zhǎng)度、向量流水操作(cozu)時(shí)間Tvp、每一對(duì)元素的平均處理時(shí)間tvp、 向量流水線(xiàn)的最大性能R（漸近性能）、半性能向量長(zhǎng)度n1/2和向量與標(biāo)量的平衡點(diǎn)nv等。第31頁(yè)/共48頁(yè)第三十二頁(yè)，共48頁(yè)。 1.機(jī)器向量長(zhǎng)度與數(shù)據(jù)向量長(zhǎng)度機(jī)器向量長(zhǎng)度是指機(jī)器中向量寄存器的長(zhǎng)度，屬于固有(gyu)參數(shù)，可用N表示。 數(shù)據(jù)向量長(zhǎng)度是指用戶(hù)向量數(shù)據(jù)的長(zhǎng)度，可用n表示，不由機(jī)器決定。 2.向量流水處理時(shí)間與最大性能 在

27、向量機(jī)中，若執(zhí)行一個(gè)長(zhǎng)度為n的向量操作時(shí)間為T(mén)vp，用Ts表示流水線(xiàn)建立時(shí)間，包括向量起始地址的設(shè)置、計(jì)數(shù)器加1、條件轉(zhuǎn)移的判斷等，T1表示第一對(duì)向量元素通過(guò)流水線(xiàn)的時(shí)間，Tc為流水線(xiàn)的時(shí)鐘周期，則第32頁(yè)/共48頁(yè)第三十三頁(yè)，共48頁(yè)。R = Lim = （5.6）n1tvp1TCTvp=Ts+Tl+(n-1)Tc =sTc+lTc+(n-1)Tc =(s+l-1)Tc+nTc （5.2）其中s是建立(jinl)流水線(xiàn)的時(shí)鐘周期數(shù)，l為完成每一對(duì)向量元素操作所需要的子操作次數(shù)。若令To=(s+l-1)Tc 則Tvp=To+nTc （5.3） 每一對(duì)向量元素的平均執(zhí)行時(shí)間為： 其中R表示向量長(zhǎng)

28、度n趨于時(shí)，向量流水處理(chl)的最大性能，也稱(chēng)為漸近性能，常在評(píng)價(jià)峰值性能時(shí)使用，單位為MFLOPS，是評(píng)價(jià)向量流水線(xiàn)的一個(gè)重要的參數(shù)。 Lim tvp = Lim =TC （5.5）nnn(s+l-1)Tc+nTc tvp= （5.4）Tvp.n第33頁(yè)/共48頁(yè)第三十四頁(yè)，共48頁(yè)。 半性能長(zhǎng)度參數(shù)n1/2表示向量流水性能達(dá)到最大值的一半時(shí)的向量長(zhǎng)度，也是一個(gè)重要參數(shù)。為了解n1/2的含義，Tvp可表示如下： Tvp=(n1/2+n)Tc=(n1/2+n)/R （5.7） 與式5.2或5.3比較，可知n1/2=To/Tc=s+l -1。 （5.8） 3.標(biāo)量循環(huán)時(shí)間與最大性能 對(duì)于串行

29、工作的標(biāo)量機(jī)，完成同樣的工作需要的Tsp為： Tsp=Ts1+nlTcs=(s1+nl)Tcs 其中Ts1為標(biāo)量循環(huán)建立時(shí)間，Tcs為標(biāo)量部件的時(shí)鐘周期，s1是為建立標(biāo)量循環(huán)所需要的節(jié)拍數(shù)。對(duì)于n個(gè)元素對(duì)，它的平均執(zhí)行時(shí)間為： tsp=Tsp/n 當(dāng)n時(shí)，tsp=lTcs，R=1/lTcs。第34頁(yè)/共48頁(yè)第三十五頁(yè)，共48頁(yè)。 對(duì)于標(biāo)量循環(huán)和向量流水操作方式，其處理時(shí)間(shjin)與向量長(zhǎng)度的關(guān)系如圖5.6(a)所示，處理速率與向量長(zhǎng)度的關(guān)系如圖5.6(b)所示。 圖中nv表示向量流水方式的工作速度優(yōu)于標(biāo)量循環(huán)方式時(shí)所需要的向量長(zhǎng)度臨界值。第35頁(yè)/共48頁(yè)第三十六頁(yè)，共48頁(yè)。圖5.6

30、 標(biāo)量循環(huán)和向量流水操作中處理時(shí)間及處理速率與向量長(zhǎng)度的關(guān)系 第36頁(yè)/共48頁(yè)第三十七頁(yè)，共48頁(yè)。 在向量流水線(xiàn)的性能分析中，涉及三個(gè)重要的參數(shù)。 1.向量流水線(xiàn)的最大性能R 如式5.6所示，R表示向量長(zhǎng)度n趨于時(shí)，向量流水處理的最大性能，也稱(chēng)為漸近性能，常在評(píng)價(jià)峰值性能時(shí)使用，單位為MFLOPS。 2.半性能向量長(zhǎng)度n1/2 n1/2表示向量流水性能達(dá)到最大值的一半時(shí)的向量長(zhǎng)度，是評(píng)價(jià)向量流水線(xiàn)的建立時(shí)間對(duì)性能影響的參數(shù)，其含義如式5.8所示。 3.向量流水與標(biāo)量循環(huán)平衡點(diǎn)nv 如圖5.6(a)所示nv表示向量流水方式(fngsh)的工作速度優(yōu)于標(biāo)量循環(huán)方式(fngsh)時(shí)所需要的向量長(zhǎng)

31、度臨界值。當(dāng)向量長(zhǎng)度nnv時(shí)，向量流水方式(fngsh)的速度優(yōu)于標(biāo)量循環(huán)方式(fngsh)。第37頁(yè)/共48頁(yè)第三十八頁(yè)，共48頁(yè)。R = （5.9）1(1-)1/Rs+Rv= （5.10）11-0.9= 0.963。 6.50.97.5【例5.3】若某向量處理機(jī)執(zhí)行速率Rv=10MFLOPS，在標(biāo)量工作方式時(shí)的執(zhí)行速率Rs=1MFLOPS，設(shè)程序中可向量化的比例為，要求(yoqi)：推導(dǎo)該向量機(jī)執(zhí)行時(shí)平均速率R的公式；畫(huà)出在（0，1）范圍內(nèi)，R與的關(guān)系曲線(xiàn)；為使平均執(zhí)行速率R =7.5MFLOPS，應(yīng)取何值？假設(shè)Rs=1MFLOPS，=0.7，為使R=2MFLOPS，Rv應(yīng)為何值？解：（1

32、）平均速率R的公式為（2）在（0，1）范圍(fnwi)內(nèi)，R與的 關(guān)系圖如圖5.7所示。（3）把R =7.5代入式5.10，可求出：（4）把Rs=1、=0.7和R=2代入式5.9，可求出： Rv=3.5MFLOPS圖5.7 平均速率R與 的關(guān)系 第38頁(yè)/共48頁(yè)第三十九頁(yè)，共48頁(yè)。 為了在向量處理機(jī)上實(shí)現(xiàn)向量化運(yùn)算(yn sun)，必須要有相應(yīng)的向量化編譯程序，以便在源程序中找出可向量化的部分，按照向量化的語(yǔ)言進(jìn)行編譯。 1.向量運(yùn)算(yn sun)指令 設(shè)有如下FORTRAN語(yǔ)言程序： DO 10 I=1，N A(I)=B(I)+C(I) 10 CONTINUE 一條向量加法指令實(shí)現(xiàn)這一

33、循環(huán)程序的功能。指令如下： ADDV A(1:N)=B(1:N)+C(1:N) 2.向量化編譯技術(shù) 向量化編譯技術(shù)是在源程序中尋找可用向量指令替代的程序段，并用向量指令替代之。在簡(jiǎn)單可向量化的循環(huán)程序中不存在向量化障礙，比如數(shù)據(jù)相關(guān)、條件語(yǔ)句等，編譯比較容易。但是對(duì)于復(fù)雜程序，包含這些障礙時(shí)，需采取相應(yīng)的措施予以消除。比如對(duì)條件語(yǔ)句可使用相應(yīng)的控制向量及WHERE語(yǔ)句加以消除。例如： 第39頁(yè)/共48頁(yè)第四十頁(yè)，共48頁(yè)。 DO 20 I=1，N20 IF（L(I).NE.0） A(I)=A(I)+1使用(shyng)向量化指令，可寫(xiě)成：WHERE （L(I).NE.0） A(1:N)=A(1

34、:N)+1 ；轉(zhuǎn)換成WHERE結(jié)構(gòu) 3.向量化編譯優(yōu)化技術(shù)除一般向量化編譯外，也可采取優(yōu)化技術(shù)，比如公共子表達(dá)式消除、死代碼消除、常數(shù)調(diào)入、復(fù)制語(yǔ)句傳遞等；在循環(huán)體的優(yōu)化中，將固定表達(dá)式移出循環(huán)體以及歸約變量消除等。 此外還有一些特殊(tsh)的方法，比如向量寄存器優(yōu)化分配、流水鏈接和功能部件并行操作優(yōu)化、重排指令執(zhí)行的序列以減少功能部件切換的頻率等。 第40頁(yè)/共48頁(yè)第四十一頁(yè)，共48頁(yè)。圖5.8 向量機(jī)優(yōu)化編譯技術(shù) 目前，在大多數(shù)向量機(jī)中向量化編譯優(yōu)化技術(shù)可用圖5.8表示，包括通用優(yōu)化、向量寄存器使用(shyng)優(yōu)化、向量鏈接與流水線(xiàn)并行操作優(yōu)化以及標(biāo)量語(yǔ)句向量化等。第41頁(yè)/共48頁(yè)第四十二頁(yè)，共48頁(yè)。第42頁(yè)/共48頁(yè)第四十三頁(yè)，共48頁(yè)。 1.系統(tǒng)組成 多向量多處理機(jī)CRAY Y-MP 816的系統(tǒng)結(jié)構(gòu)如圖5.9所示。整個(gè)系統(tǒng)可配置1臺(tái)、2臺(tái)、4臺(tái)或8臺(tái)處理機(jī)，采用共享中央存儲(chǔ)器、I/O子系統(tǒng)、處理機(jī)之間的通信系統(tǒng)及實(shí)時(shí)鐘等，CPU時(shí)鐘周期為6nS。中央存儲(chǔ)器可分成256個(gè)交叉存儲(chǔ)體，總?cè)萘靠梢允?6128MW，最大1GB；固態(tài)存儲(chǔ)器的容量為32512MW，最大4GB。有四個(gè)存儲(chǔ)器端口，允許每個(gè)CPU同時(shí)執(zhí)行兩個(gè)標(biāo)量和向量取操作、一個(gè)存