第十四講向量流水處理機(jī)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)向量處理的基本概念向量流水處理機(jī)的結(jié)構(gòu)提高向量流水處理機(jī)性能的方法2向量處理的基本概念從數(shù)學(xué)的概念上講，標(biāo)量是指單個(gè)量，而向量是指一組標(biāo)量。例如，有一個(gè)數(shù)組A＝（a1，a2，a3，…，an），其中括號(hào)內(nèi)的每一個(gè)元素ai就是一個(gè)標(biāo)量。而A稱為向量，它由一組標(biāo)量組成。一條向量指令可以處理N個(gè)或N對(duì)操作數(shù)。我們把這N個(gè)互相獨(dú)立的數(shù)叫做向量，對(duì)這樣一組數(shù)的運(yùn)算叫做向量處理。因此，向量指令的處理效率要比標(biāo)量指令的處理效率高得多。3向量處理方式有三種處理方式：橫向處理方式，又稱為水平處理方式，橫向加工方式等。向量計(jì)算是按行的方式從左至右橫向地進(jìn)行。縱向處理方式，又稱為垂直處理方式，縱向加工方式等。向量計(jì)算是按列的方式自上而下縱向地進(jìn)行。縱橫處理方式，又稱為分組處理方式，縱橫向加工方式等。橫向處理和縱向處理相結(jié)合的方式。要根據(jù)向量運(yùn)算的特點(diǎn)和向量處理機(jī)的類(lèi)型選擇向量的處理方式。4向量處理方式例如：向量計(jì)算：A*(B+C)的

循環(huán)程序用C語(yǔ)言為for(i=1;i<=n;i++)

di=ai*(bi+ci)水平處理法(橫向)d1=a1*(b1+c1)d2=a2*(b2+c2)··dn=an*(bn+cn)5水平處理法假設(shè)中間結(jié)果為t(i)計(jì)算第1個(gè)分量：

t(1)

＝b(1)＋c(1)

d(1)＝a(1)×t(1)計(jì)算第2個(gè)分量：

T(2)

＝b(2)＋c(2)

d(2)＝a(2)×t(2)

……計(jì)算第N個(gè)分量：

t(N)

＝b(N)＋c(N)

d(N)＝a(N)×t(N)當(dāng)采用流水方式計(jì)算時(shí)，在每個(gè)向量加乘運(yùn)算中都會(huì)發(fā)生數(shù)據(jù)相關(guān)。而且當(dāng)使用靜態(tài)流水線時(shí)，還要進(jìn)行2次乘和加功能的轉(zhuǎn)移。這樣共出現(xiàn)N次相關(guān)，2N次功能轉(zhuǎn)換。因此，橫向處理方法不適合于向量流水處理。6縱向處理法向量計(jì)算是按列的方式自上而下縱向地進(jìn)行。即先是所有B和C向量元素對(duì)的相加運(yùn)算，中間結(jié)果暫存到k1～kN中；然后再縱向加工所有對(duì)應(yīng)元素的乘法運(yùn)算。

（b1＋c1）（b2＋c2）d1＝a1×d2＝a2×

:

dN＝aN×（bN＋cN）

k1

k2

kN7縱向處理法用向量指令形式來(lái)表示，則變成：

K＝B＋C

D＝K×A只需要兩條指令就能實(shí)現(xiàn)

VADD B，C，K

VMUL K，A，D顯然，當(dāng)采用流水方式計(jì)算時(shí)，數(shù)據(jù)相關(guān)在兩條向量指令間僅有1次，而流水線加、乘功能的切換只需1次。因此，縱向處理方法可獲得較高的吞吐率，適合于在向量處理機(jī)中應(yīng)用。8縱橫處理法當(dāng)向量長(zhǎng)度N大于向量寄存器長(zhǎng)度n時(shí)，需要分組處理。分成k組，組內(nèi)采用縱向處理方式，組間采用橫向處理方式。分組方法：

n=k*m+r

其中：m為每組長(zhǎng)度，r為第k+1組剩余分量

Bi+Ci

Ki(1到m)

Ki*Ai

Di(1到m)……

Bi+Ci

Ki(m+1到2m)

Ki*Ai

Di(m+1到2m)……9縱橫處理法每組用兩條向量指令，每組發(fā)生相關(guān)兩次，其中組內(nèi)發(fā)生數(shù)據(jù)相關(guān)一次，組間切換時(shí)發(fā)生相關(guān)一次。主要優(yōu)點(diǎn)：減少訪問(wèn)主存儲(chǔ)器的次數(shù)

例如：中間變量K不寫(xiě)入主存儲(chǔ)器10向量處理的基本概念向量流水處理機(jī)的結(jié)構(gòu)提高向量流水處理機(jī)性能的方法11基本結(jié)構(gòu)主存標(biāo)量寄存器標(biāo)量功能部件向量功能部件向量寄存器/向量緩沖器向量指令控制部件向量存取部件指令處理部件向量功能部件向量功能部件···控制部分：控制部件和緩沖部件（中間REG）標(biāo)量流水：功能部件和標(biāo)量寄存器(S)向量流水：功能、存取部件和寄存器(V、VM、VL)向量流水處理機(jī)的結(jié)構(gòu)12向量流水處理機(jī)的結(jié)構(gòu)按向量元素和結(jié)果存放分M-M和R-R兩類(lèi)。存儲(chǔ)器－存儲(chǔ)器結(jié)構(gòu)多個(gè)獨(dú)立的存儲(chǔ)器模塊并行工作處理機(jī)結(jié)構(gòu)簡(jiǎn)單對(duì)存儲(chǔ)系統(tǒng)的訪問(wèn)速度要求很高寄存器－寄存器結(jié)構(gòu)運(yùn)算通過(guò)向量寄存器進(jìn)行需要大量高速寄存器對(duì)存儲(chǔ)系統(tǒng)訪問(wèn)速度的要求降低13存儲(chǔ)器-存儲(chǔ)器結(jié)構(gòu)向量處理機(jī)的基本思想是把兩個(gè)向量的對(duì)應(yīng)分量進(jìn)行計(jì)算，產(chǎn)生一個(gè)結(jié)果向量。參加運(yùn)算的向量數(shù)據(jù)在存儲(chǔ)器中，運(yùn)算的結(jié)果也送到存儲(chǔ)器中，其結(jié)構(gòu)與數(shù)據(jù)流的示意圖如下圖所示。如果以向量加法為例子：C=A+BABC流水線運(yùn)算部件多端口存儲(chǔ)系統(tǒng)一種能實(shí)現(xiàn)兩個(gè)向量相加的流水結(jié)構(gòu)的加法器14加法流水線部件M1M2M6AB1234C=A+Ba1b1M3M4M5c1M7M8A、B、C的向量長(zhǎng)度為8，加法流水線分為4個(gè)功能段，主存儲(chǔ)器采取了8個(gè)存儲(chǔ)體多模塊存儲(chǔ)器系統(tǒng)的向量處理機(jī)15向量計(jì)算C=A+B的時(shí)空?qǐng)D假設(shè)一個(gè)存取周期等于兩個(gè)時(shí)鐘周期，并假設(shè)向量A、B、C各有8個(gè)，那么理想實(shí)現(xiàn)C＝A＋B向量計(jì)算的時(shí)空?qǐng)D如圖所示。為了不發(fā)生讀寫(xiě)沖突，各向量元素在存儲(chǔ)模塊中的位置是有意安排的。由于運(yùn)算流水線分為4段，因此輸入數(shù)據(jù)進(jìn)入流水線4個(gè)時(shí)鐘周期之后才能產(chǎn)生相應(yīng)的輸出值。當(dāng)數(shù)據(jù)充滿后，流水線就一直處于忙碌狀態(tài)。16功能部件4功能部件3功能部件2功能部件1存儲(chǔ)體M8存儲(chǔ)體M7存儲(chǔ)體M6存儲(chǔ)體M5存儲(chǔ)體M4存儲(chǔ)體M3存儲(chǔ)體M2存儲(chǔ)體M1

0123456789101112131415t12345678123456781234567812345678RB6RB6RA8RA8WC4WC4RB5RB5RA7RA7WC3WC3RB4RB4RA6RA6WC2WC2RB3RB3RA5RA5WC1WC1RB2RB2RA4RA4RB1RB1RA3RA3RA2RA2RA1RA1WC8WC8WC7WC7WC6WC6WC5WC5RB8RB8RB7RB7C=A+B向量處理時(shí)序圖17具有延遲緩沖器的向量流水線結(jié)構(gòu)

然而實(shí)際情況并非總和上述理想化的情況一樣。假如結(jié)果向量C的第一個(gè)元素C1不是存放在我們想存放的模塊M5而是在模塊M6，那么將出現(xiàn)存儲(chǔ)模塊的讀寫(xiě)沖突。為了消除爭(zhēng)用存儲(chǔ)器的現(xiàn)象，可在運(yùn)算流水線的輸入端和輸出端增加可變延遲緩沖器，如圖所示。

顯然，有了輸入輸出緩沖器，可以實(shí)現(xiàn)向量操作無(wú)沖突地進(jìn)行存儲(chǔ)系統(tǒng)可變延遲器流水處理部件可變延遲器先啟動(dòng)讀A，再啟動(dòng)讀B，A延遲2個(gè)時(shí)鐘進(jìn)入加法器18寄存器--寄存器結(jié)構(gòu)使主存有較高帶寬的另一種方法是由一級(jí)或多級(jí)中間存儲(chǔ)器形成一個(gè)層次結(jié)構(gòu)的存儲(chǔ)器系統(tǒng)，其中帶寬最高的這一級(jí)存儲(chǔ)器安排在離處理器最近的位置。當(dāng)處理器需要向量時(shí)，把向量從主存送到速度最快的這一級(jí)存儲(chǔ)器。反之，運(yùn)算結(jié)果也先送到速度最快的中間存儲(chǔ)器。由于中間級(jí)存儲(chǔ)器起著數(shù)據(jù)的中間存儲(chǔ)作用，功能上相當(dāng)于寄存器，因此稱為寄存器-寄存器型向量處理機(jī)。19主存儲(chǔ)器地址部件標(biāo)量部件浮點(diǎn)部件向量部件向量寄存器V0-V7標(biāo)量寄存器S0-S7地址寄存器A0-A7地址乘

(6級(jí))地址加

(2級(jí))移位(2~3級(jí))邏輯

(1級(jí))1計(jì)數(shù)

(3級(jí))整數(shù)加

(3級(jí))浮點(diǎn)倒數(shù)(14級(jí))浮點(diǎn)乘

(7級(jí))浮點(diǎn)加

(6級(jí))邏輯(2級(jí))位移(4級(jí))整數(shù)加

(3級(jí))Cray-1向量機(jī)結(jié)構(gòu)20對(duì)于向量運(yùn)算來(lái)說(shuō)，中間存儲(chǔ)器是8個(gè)向量寄存器(V)，每個(gè)向量寄存器有64個(gè)分量，每個(gè)分量為一個(gè)64位寄存器。執(zhí)行向量指令時(shí)，流水結(jié)構(gòu)運(yùn)算器在一個(gè)時(shí)鐘周期內(nèi)從兩個(gè)V寄存器得到一對(duì)操作數(shù)，完成某種操作后用一個(gè)時(shí)鐘周期時(shí)間把結(jié)果送入另一個(gè)V寄存器。注意，此處的向量運(yùn)算流水線是從向量寄存器而不是從主存儲(chǔ)器獲得數(shù)據(jù)。同樣，從流水線輸出的結(jié)果向量也是送回向量寄存器。而另一方面，主存儲(chǔ)器與V寄存器之間的數(shù)據(jù)傳送以成組傳送方式進(jìn)行。對(duì)標(biāo)量運(yùn)算來(lái)說(shuō)，有兩級(jí)中間存儲(chǔ)器。速度很快的一級(jí)是8個(gè)64位的S寄存器，它是標(biāo)量寄存器。主存與T寄存器之間以成組傳送方式進(jìn)行數(shù)據(jù)交換。21中間存儲(chǔ)器的優(yōu)點(diǎn)這種中間存儲(chǔ)器與Cache相比的一大優(yōu)點(diǎn)是速度快。因?yàn)镃RAY-1流水運(yùn)算器通過(guò)寄存器尋址方式訪問(wèn)中間存儲(chǔ)器，而訪問(wèn)Cache必須查Cache表，這需要較長(zhǎng)時(shí)間。22向量處理的基本概念向量流水處理機(jī)的結(jié)構(gòu)提高向量流水處理機(jī)性能的方法23提高向量流水處理機(jī)性能的方法一、多功能部件并行操作二、鏈接技術(shù)三、分段開(kāi)采技術(shù)四、向量遞歸技術(shù)24一、多功能部件并行操作對(duì)向量機(jī)中多個(gè)功能部件，使其能并行操作。并行操作條件：(1)不存在向量寄存器使用沖突不允許出現(xiàn)RAW、WAR、WAW、RAR相關(guān)。如：V4←V1+V2 V5←V1＋V2V5←V2×V3 V5←V3∧V4(2)不存在功能部件使用沖突每種功能部件一般只設(shè)置一個(gè)。如：V3←V1×V2V6←V4×V525二、鏈接技術(shù)利用向量指令間存在的先寫(xiě)后讀的數(shù)據(jù)相關(guān)性來(lái)加快向量指令序列執(zhí)行速度的技術(shù)稱為鏈接技術(shù)。實(shí)質(zhì)上，鏈接技術(shù)是標(biāo)量流水定向傳送方法在向量寄存器中的應(yīng)用。例如下面的向量加、向量乘操作：ADDV

V1，V2，V3

；V1←V2＋V3MULV

V4，V1，V5

；V4←V1×V526由于這兩條指令間對(duì)V1向量寄存器存在先寫(xiě)后讀相關(guān)，通常必須等加法指令做完后才可開(kāi)始乘法指令。但如果使向量寄存器V1在同一時(shí)鐘周期內(nèi)，既接收一個(gè)功能部件送來(lái)的運(yùn)算結(jié)果，又可把這一結(jié)果作為下一個(gè)向量指令運(yùn)算所需的源操作數(shù)傳送給另一個(gè)功能部件，那就可使這兩個(gè)部件鏈接起來(lái)進(jìn)行操作。通常把這種鏈接稱為超級(jí)向量操作。當(dāng)鏈接進(jìn)入充分流水操作狀態(tài)后，在1個(gè)時(shí)鐘周期就可同時(shí)獲取兩個(gè)操作結(jié)果。27鏈接條件：(1)不存在功能部件使用沖突；(2)共用向量寄存器中向量長(zhǎng)度、起始地址、偏移量、步長(zhǎng)均相等；(3)參與鏈接的先行指令產(chǎn)生結(jié)果周期相同；(4)只有在先行指令產(chǎn)生第一結(jié)果分量的那個(gè)時(shí)鐘方可鏈接，否則不行。適用情況：即第1條指令的結(jié)果，是第2條指令的操作數(shù)，這時(shí)，所得到的第1條指令的中間結(jié)果不必要等待全部向量元素都執(zhí)行完才進(jìn)行第二條指令的操作，可以將從一個(gè)流水線部件得到的結(jié)果直接送入下一個(gè)功能流水線部件的向量寄存器，形成兩條指令的鏈接注意：不同向量機(jī)對(duì)向量指令的鏈接方法有所不同28例：用鏈接技術(shù)進(jìn)行向量運(yùn)算：D＝A×(B＋C)

假設(shè)向量長(zhǎng)度≤64，且向量B、C已由存儲(chǔ)器取至V0和V1。

解：用下面3條向量指令可完成上述運(yùn)算：

LV

V3，M(A)

；V3←A

ADDV

V2，V0，V1

；V2←V0＋V1

MULV

V４，V2，V3

；V４←V2×V3第1、2條指令無(wú)向量寄存器使用沖突，也無(wú)功能部件使用沖突，因而可以并行執(zhí)行。第3條指令與第1、2條指令均存在先寫(xiě)后讀相關(guān)沖突，因而可將第3條指令與第1、2條指令鏈接執(zhí)行。由于同步的要求，數(shù)據(jù)進(jìn)入、流出每個(gè)功能部件，包括訪問(wèn)儲(chǔ)存器，都需1個(gè)時(shí)鐘周期時(shí)間。29訪存與浮點(diǎn)加并行，再與浮點(diǎn)乘鏈接LD V3，AADDV V2，V0，V1MULV V4，V2，V3V0V4V1V2V3132456132456浮點(diǎn)加浮點(diǎn)乘DBC訪存存儲(chǔ)器A并行和鏈接操作圖132467530浮點(diǎn)加訪存浮點(diǎn)乘6543216543217654321啟動(dòng)流出啟動(dòng)第一個(gè)結(jié)果流出1234567891011121314151617一個(gè)數(shù)據(jù)處理時(shí)間17第一，二條指令并行與第三條鏈接························31若三條指令串行執(zhí)行，即每次只有前條指令結(jié)束，才執(zhí)行后繼指令，那么三條指令執(zhí)行的總時(shí)間為：[(1+6+1)+N-1]+[(1+6+1)+N-1]+[(1+7+1)+N-1]=3N+22(拍)若第一、二條指令并行與第三條串行：

[(1+6+1)+N-1]+[(1+7+1)+N-1]=2N+15(拍)若第一，二條指令并行與第三條鏈接：

[(1+6+1)+(1+7+1)+(N-1)]=N+16(拍)可以看出采用并行與鏈接后，可以很有效的改善性能。32三、分段開(kāi)采技術(shù)處理長(zhǎng)向量的程序結(jié)構(gòu)稱為向量循環(huán)。當(dāng)向量的長(zhǎng)度大于向量寄存器的長(zhǎng)度時(shí)，必須把長(zhǎng)向量分成長(zhǎng)度固定的段。分段開(kāi)采技術(shù)一次處理一個(gè)向量段。將長(zhǎng)向量分段成循環(huán)是系統(tǒng)硬件和軟件控制完成的，程序員看不到這種向量分段為循環(huán)的過(guò)程，即對(duì)程序員是透明的。每經(jīng)過(guò)一次循環(huán)，就處理長(zhǎng)向量的一個(gè)段。一般在進(jìn)入循環(huán)以前，根據(jù)向量長(zhǎng)度計(jì)算出循環(huán)計(jì)數(shù)值。33例：A和B為長(zhǎng)度N的向量。

for(i=1;i<N;i++)

a[i]=5*b(i)+c;當(dāng)向量長(zhǎng)度N為64或更小時(shí)，計(jì)算A數(shù)組的7條指令序列是：

1：S1

5.0 在標(biāo)量寄存器內(nèi)設(shè)置常數(shù)

2：S2

C 將常數(shù)C裝入標(biāo)量寄存器

3：VL

N 在VL寄存器內(nèi)設(shè)置向量長(zhǎng)度

4：Vo

B

將B向量讀入向量寄存器

5：V1

S1

VoB數(shù)組的每個(gè)分量乘常數(shù)

6：V2

S2＋V1C和5

B(x)相加

7：A

V2

將結(jié)果向量存入A數(shù)組34當(dāng)N超過(guò)64時(shí)，要采用向量循環(huán)開(kāi)采技術(shù)。

在進(jìn)入循環(huán)前，把N除以64，確定循環(huán)次數(shù)。 如果有余數(shù)，則在第一次循環(huán)中首先計(jì)算。第4條到第7條指令組成循環(huán)

1：S1

5.0 在標(biāo)量寄存器內(nèi)設(shè)置常數(shù)

2：S2

C 將常數(shù)C裝入標(biāo)量寄存器

3：VL

N 在VL寄存器內(nèi)設(shè)置向量長(zhǎng)度f(wàn)or(i=0;i>=N/64;i++){

4：Vo

B

將B向量讀入向量寄存器

5：V1

S1

VoB數(shù)組的每個(gè)分量乘常數(shù)

6：V2

S2＋V1C和5

B(x)相加

7：A

V2

將結(jié)果向量存入A數(shù)組}35

前面所講的三種技術(shù)措施都是在單處理機(jī)結(jié)構(gòu)的向量計(jì)算機(jī)上實(shí)現(xiàn)的。為了更有效地提高向量處理性能，新型向量機(jī)采用了多處理機(jī)系統(tǒng)結(jié)構(gòu)。

在確定的應(yīng)用背景下，向量處理機(jī)系統(tǒng)性能應(yīng)該隨處理機(jī)數(shù)目的增加而線性地提高。但是系統(tǒng)規(guī)模的擴(kuò)展性不僅涉及CPU，還涉及存儲(chǔ)器和I／O資源，另外還要考慮價(jià)格和效率。因此，在系統(tǒng)設(shè)計(jì)時(shí)，力求做到處理速度、存儲(chǔ)容量和I／O吞吐能力三者之間的平衡。否則會(huì)出現(xiàn)瓶頸，整個(gè)系統(tǒng)的效率得不到發(fā)揮。采用多處理機(jī)系統(tǒng)結(jié)構(gòu)

36加速向量歸約操作應(yīng)用舉例：實(shí)現(xiàn)方法一：（正常方法）(1)C=A×B；--流水（向量）操作(2)對(duì)C進(jìn)行遞歸折疊求和。--串行（循環(huán)）操作實(shí)現(xiàn)方法二：（加速方法）(1)C=V3×V4--流水（向量）操作(2)V0=V0+C--歸約操作37歸約實(shí)現(xiàn)方法：（V0←V0+C)(1)置V0各分量為0，V0和C的計(jì)數(shù)器C0、C1均為0；(2)計(jì)數(shù)器C0在t8之前保持為0，C1在每個(gè)時(shí)鐘周期后加1，直到第一個(gè)結(jié)果分量出來(lái)。（8個(gè)時(shí)鐘周期）（3）計(jì)數(shù)器C0在t8之后每個(gè)時(shí)鐘周期加1，直到等于向量計(jì)算長(zhǎng)度為止。38V00,C0V00=C0V00,C1V01=C1V00,C7V07=C7V00,C8V08=C0+C8V01,C9V09=C1+C9V07,C15V015=C7+C15V048,C56V056=C0+C8+…+C56V049,C57V057=C1+C9+…+C57V055,C63V063=C7+C15+…+C63…………t0t8t16t63…結(jié)果：V0的最后8個(gè)分量為C0至C63之和。39向量化編譯技術(shù)

一、向量化基本功能1.并行性檢測(cè)是否可用向量表示。是否存在相關(guān)、條件語(yǔ)句、操作數(shù)的間接訪問(wèn)等。2.并行性表示與開(kāi)發(fā)用向量指令