向量流水處理機(jī)

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

循環(huán)程序用C語言為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)計算第1個分量：

t(1)

＝b(1)＋c(1)

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

T(2)

＝b(2)＋c(2)

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

……計算第N個分量：

t(N)

＝b(N)＋c(N)

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

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

:

dN＝aN×（bN＋cN）

k1

k2

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

K＝B＋C

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

VADD B，C，K

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

n=k*m+r

其中：m為每組長度，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)一次，組間切換時發(fā)生相關(guān)一次。主要優(yōu)點：減少訪問主存儲器的次數(shù)

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

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

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

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

(6級)地址加

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

(1級)1計數(shù)

(3級)整數(shù)加

(3級)浮點倒數(shù)(14級)浮點乘

(7級)浮點加

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

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

V1，V2，V3

；V1←V2＋V3MULV

V4，V1，V5

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

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

解：用下面3條向量指令可完成上述運算：

LV

V3，M(A)

；V3←A

ADDV

V2，V0，V1

；V2←V0＋V1

MULV

V４，V2，V3

；V４←V2×V3第1、2條指令無向量寄存器使用沖突，也無功能部件使用沖突，因而可以并行執(zhí)行。第3條指令與第1、2條指令均存在先寫后讀相關(guān)沖突，因而可將第3條指令與第1、2條指令鏈接執(zhí)行。由于同步的要求，數(shù)據(jù)進(jìn)入、流出每個功能部件，包括訪問儲存器，都需1個時鐘周期時間。29訪存與浮點加并行，再與浮點乘鏈接LD V3，AADDV V2，V0，V1MULV V4，V2，V3V0V4V1V2V3132456132456浮點加浮點乘DBC訪存存儲器A并行和鏈接操作圖132467530浮點加訪存浮點乘6543216543217654321啟動流出啟動第一個結(jié)果流出1234567891011121314151617一個數(shù)據(jù)處理時間17第一，二條指令并行與第三條鏈接························31若三條指令串行執(zhí)行，即每次只有前條指令結(jié)束，才執(zhí)行后繼指令，那么三條指令執(zhí)行的總時間為：[(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三、分段開采技術(shù)處理長向量的程序結(jié)構(gòu)稱為向量循環(huán)。當(dāng)向量的長度大于向量寄存器的長度時，必須把長向量分成長度固定的段。分段開采技術(shù)一次處理一個向量段。將長向量分段成循環(huán)是系統(tǒng)硬件和軟件控制完成的，程序員看不到這種向量分段為循環(huán)的過程，即對程序員是透明的。每經(jīng)過一次循環(huán)，就處理長向量的一個段。一般在進(jìn)入循環(huán)以前，根據(jù)向量長度計算出循環(huán)計數(shù)值。33例：A和B為長度N的向量。

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

a[i]=5*b(i)+c;當(dāng)向量長度N為64或更小時，計算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è)置向量長度

4：Vo

B

將B向量讀入向量寄存器

5：V1

S1

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

6：V2

S2＋V1C和5

B(x)相加

7：A

V2

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

在進(jìn)入循環(huán)前，把N除以64，確定循環(huán)次數(shù)。 如果有余數(shù)，則在第一次循環(huán)中首先計算。第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è)置向量長度for(i=0;i>=N/64;i++){

4：Vo

B

將B向量讀入向量寄存器

5：V1

S1

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

6：V2

S2＋V1C和5

B(x)相加

7：A

V2

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

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

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

36加速向量歸約操作應(yīng)用舉例：實現(xiàn)方法一：（正常方法）(1)C=A×B；--流水（向量）操作(2)對C進(jìn)行遞歸折疊求和。--串行（循環(huán)）操作實現(xiàn)方法二：（加速方法）(1)C=V3×V4--流水（向量）操作(2)V0=V0+C--歸約操作37歸約實現(xiàn)方法：（V0←V0+C)(1)置V0各分量為0，V0和C的計數(shù)器C0、C1均為0；(2)計數(shù)器C0在t8之前保持為0，C1在每個時鐘周期后加1，直到第一個結(jié)果分量出來。（8個時鐘周期）（3）計數(shù)器C0在t8之后每個時鐘周期加1，直到等于向量計算長度為止。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個分量為C0至C63之和。39向量化編譯技術(shù)

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