向量流水線計算機(jī)技術(shù)

1、n向量處理機(jī)結(jié)構(gòu)目前已成為解決數(shù)值計算問題的一種最重向量處理機(jī)結(jié)構(gòu)目前已成為解決數(shù)值計算問題的一種最重要的高性能結(jié)構(gòu)。要的高性能結(jié)構(gòu)。n向量處理機(jī)的性能價格比是很引人注目的，因為與相同價向量處理機(jī)的性能價格比是很引人注目的，因為與相同價格的串行處理機(jī)相比，它們的向量運算吞吐量要高出格的串行處理機(jī)相比，它們的向量運算吞吐量要高出12個數(shù)量級。但是，這種吞吐量提高只是對特定結(jié)構(gòu)問題而個數(shù)量級。但是，這種吞吐量提高只是對特定結(jié)構(gòu)問題而言，也就是說，局限于那些可以轉(zhuǎn)化為向量運算的問題。言，也就是說，局限于那些可以轉(zhuǎn)化為向量運算的問題。第六章第六章 向量流水線技術(shù)向量流水線技術(shù)( (P347)P347)

2、前言前言n本章任務(wù)了解本章任務(wù)了解向量處理機(jī)特點、一般結(jié)構(gòu)向量處理機(jī)特點、一般結(jié)構(gòu)，n并掌握并掌握提高向量處理機(jī)性能方法提高向量處理機(jī)性能方法。6.1 特點特點 多數(shù)為巨型機(jī)多數(shù)為巨型機(jī)，絕大多數(shù)向量處理機(jī)都采用流水線結(jié)構(gòu)。當(dāng)絕大多數(shù)向量處理機(jī)都采用流水線結(jié)構(gòu)。當(dāng)一條流水線不能達(dá)到所要求性能時，設(shè)計者往往采用一條流水線不能達(dá)到所要求性能時，設(shè)計者往往采用多條單功多條單功能流水線。能流水線。第六章第六章 向量流水線技術(shù)向量流水線技術(shù)-向量處理機(jī)的結(jié)構(gòu)為實現(xiàn)向量化處理，向量處理機(jī)操作部件一般采用流水線結(jié)為實現(xiàn)向量化處理，向量處理機(jī)操作部件一般采用流水線結(jié)構(gòu)。下面是典型的向量加法器結(jié)構(gòu)：構(gòu)。下面是典

3、型的向量加法器結(jié)構(gòu)：n向量處理機(jī)設(shè)計中要解決兩個問題：向量處理機(jī)設(shè)計中要解決兩個問題：（1）設(shè)法維持連續(xù)數(shù)據(jù)流（提供連續(xù)的）設(shè)法維持連續(xù)數(shù)據(jù)流（提供連續(xù)的A和和B）。）。 （2）設(shè)法降低對存儲器壓力。）設(shè)法降低對存儲器壓力。n向量處理機(jī)一般采取以下技術(shù)措施：向量處理機(jī)一般采取以下技術(shù)措施： （1）用多獨立存儲器模塊達(dá)到需要帶寬。例）用多獨立存儲器模塊達(dá)到需要帶寬。例STAR-100，32體。體。 （2）增設(shè)高速中間存儲器）增設(shè)高速中間存儲器向量寄存器。向量寄存器。n根據(jù)采用技術(shù)措施不同，向量處理機(jī)分為兩種不根據(jù)采用技術(shù)措施不同，向量處理機(jī)分為兩種不同結(jié)構(gòu)：同結(jié)構(gòu)： （1）存儲器）存儲器存儲器結(jié)

4、構(gòu)存儲器結(jié)構(gòu)（2）寄存器）寄存器寄存器結(jié)構(gòu)寄存器結(jié)構(gòu)第一節(jié)第一節(jié)向量處理機(jī)的結(jié)構(gòu)向量處理機(jī)的結(jié)構(gòu)n（1）存儲器）存儲器存儲器結(jié)構(gòu)存儲器結(jié)構(gòu)第一節(jié)第一節(jié)向量處理機(jī)的結(jié)構(gòu)向量處理機(jī)的結(jié)構(gòu)主存儲器由多個存儲器模塊構(gòu)成。流水線運算器與主存儲器系主存儲器由多個存儲器模塊構(gòu)成。流水線運算器與主存儲器系統(tǒng)間有三條相互獨立的數(shù)據(jù)通路，各數(shù)據(jù)通路可同時工作。統(tǒng)間有三條相互獨立的數(shù)據(jù)通路，各數(shù)據(jù)通路可同時工作。第一節(jié)第一節(jié)向量處理機(jī)的結(jié)構(gòu)向量處理機(jī)的結(jié)構(gòu)n假設(shè)一個存儲周期占兩個處理機(jī)周期。假設(shè)一個存儲周期占兩個處理機(jī)周期。n下圖是計算下圖是計算C=AB最理想方法。最理想方法。第一節(jié)向量處理機(jī)的結(jié)構(gòu)典型系統(tǒng)：典型系

5、統(tǒng)：CDC的的STAR-100，1973年完成。年完成。主要技術(shù)參數(shù)：主要技術(shù)參數(shù)：主頻：主頻：40ns；字長：；字長：64位；主存容量：位；主存容量：100萬字，磁芯存儲器，萬字，磁芯存儲器，32體，存儲周期為體，存儲周期為1.28微妙，每個體的數(shù)據(jù)寬度為微妙，每個體的數(shù)據(jù)寬度為8個字，個字，STAR-100存儲系統(tǒng)的頻帶寬度為：存儲系統(tǒng)的頻帶寬度為：（32*8）/1.28微妙微妙=2*字字/秒秒 n使主存有較高帶寬的另一種方法是由一級或多級中間存儲使主存有較高帶寬的另一種方法是由一級或多級中間存儲器形成一個層次結(jié)構(gòu)存儲器系統(tǒng)，其中帶寬最高的這級存器形成一個層次結(jié)構(gòu)存儲器系統(tǒng)，其中帶寬最高的

6、這級存儲器安排在距處理器最近位置。即寄存器一寄存器結(jié)構(gòu)。儲器安排在距處理器最近位置。即寄存器一寄存器結(jié)構(gòu)。nCRAY-1是世界上第一臺向量流水處理巨型機(jī)。是世界上第一臺向量流水處理巨型機(jī)。是美國是美國Cray公司于公司于1976年提供產(chǎn)品。運算速度達(dá)億次秒以上年提供產(chǎn)品。運算速度達(dá)億次秒以上巨型機(jī)。速度這么高的一個原因是它采用了層次結(jié)構(gòu)的存巨型機(jī)。速度這么高的一個原因是它采用了層次結(jié)構(gòu)的存儲器系統(tǒng)。儲器系統(tǒng)。第一節(jié)第一節(jié)向量處理機(jī)的結(jié)構(gòu)向量處理機(jī)的結(jié)構(gòu)（2）寄存器）寄存器-寄存器結(jié)構(gòu)寄存器結(jié)構(gòu)簡化的簡化的Cray-l的框圖：主存與流水結(jié)構(gòu)運算器間有一級或兩級中間的框圖：主存與流水結(jié)構(gòu)運算器間有

7、一級或兩級中間存儲器。存儲器。中間存儲器與中間存儲器與CACHE比特點：不透明；訪問快；支持新數(shù)據(jù)結(jié)構(gòu)比特點：不透明；訪問快；支持新數(shù)據(jù)結(jié)構(gòu)（3）兩種結(jié)構(gòu)的簡單比較：）兩種結(jié)構(gòu)的簡單比較：n第一種結(jié)構(gòu)是依靠主存來保證流水線所需的操作數(shù)。因此第一種結(jié)構(gòu)是依靠主存來保證流水線所需的操作數(shù)。因此主存必須具有至少和運算器所要求帶寬一樣高的帶寬。這主存必須具有至少和運算器所要求帶寬一樣高的帶寬。這就要求主存或者存取速度足夠快，或者分為多個獨立的存就要求主存或者存取速度足夠快，或者分為多個獨立的存儲模塊，或者兩者都具備，因為運算器要求的最大帶寬非儲模塊，或者兩者都具備，因為運算器要求的最大帶寬非常高。常高

8、。n第二種結(jié)構(gòu)是通過容量比主存小得多的中間存儲器即寄存第二種結(jié)構(gòu)是通過容量比主存小得多的中間存儲器即寄存器來保證很高的帶寬。這樣，低速存取主存就不會妨礙流器來保證很高的帶寬。這樣，低速存取主存就不會妨礙流水結(jié)構(gòu)運算器連續(xù)運行。第二種結(jié)構(gòu)的另一好處是流水結(jié)水結(jié)構(gòu)運算器連續(xù)運行。第二種結(jié)構(gòu)的另一好處是流水結(jié)構(gòu)運算器可以重疊進(jìn)行，因為構(gòu)運算器可以重疊進(jìn)行，因為高速寄存器帶寬足以滿足幾高速寄存器帶寬足以滿足幾個流水結(jié)構(gòu)運算部件的帶寬要求個流水結(jié)構(gòu)運算部件的帶寬要求。第一節(jié)向量處理機(jī)的結(jié)構(gòu)6.2 典型工作方式典型工作方式 CRAY-1是世界上第一臺向量流水處理巨型機(jī)。是世界上第一臺向量流水處理巨型機(jī)。(

9、1) CRAY-1技術(shù)術(shù)語技術(shù)術(shù)語 向量寄存器組向量寄存器組V0，V1，V7。 分量計數(shù)器分量計數(shù)器 鏈接方式鏈接方式(P370) 啟動、輸出延遲（各啟動、輸出延遲（各1拍）。拍）。D=A*（BC）向量長度）向量長度=64，B和和C已取至已取至V0和和 V1，V3AV2 V0V1V4 V2*V3n第一、二條指令既無寄存器沖第一、二條指令既無寄存器沖突，也無功能部件沖突，可并突，也無功能部件沖突，可并行執(zhí)行。行執(zhí)行。第三條與第一、二條指令均存在第三條與第一、二條指令均存在先寫后讀的相關(guān)沖突，先寫后讀的相關(guān)沖突，可將第可將第三條與第一、二條指令鏈接三條與第一、二條指令鏈接。由于同步的要求，數(shù)據(jù)進(jìn)入

10、和流出每個由于同步的要求，數(shù)據(jù)進(jìn)入和流出每個功能部件，包括訪存都需要功能部件，包括訪存都需要1拍時間。拍時間。(2) 鏈接技術(shù)（鏈接技術(shù)（369）前一條指令結(jié)果不必送回存儲器直接作為后一條指令的操作數(shù)，甚至可在前前一條指令結(jié)果不必送回存儲器直接作為后一條指令的操作數(shù)，甚至可在前一條指令完成之前就使用其結(jié)果。一條指令完成之前就使用其結(jié)果。若采用鏈接技術(shù)，則執(zhí)行時間為：若采用鏈接技術(shù)，則執(zhí)行時間為： （1 61）（）（17 1）（）（Nl）= N16拍拍若這三條指令全部用串行方法，則執(zhí)行時間為：若這三條指令全部用串行方法，則執(zhí)行時間為： (161)N1(16十十1)N1(171)N1= 3N 22

11、拍拍若前兩條指令并行執(zhí)行，第三條指令串行執(zhí)行，則執(zhí)行時間為：若前兩條指令并行執(zhí)行，第三條指令串行執(zhí)行，則執(zhí)行時間為：（1 61） N1（ 17 l） N1= 2N 15拍拍假設(shè)向量長度為假設(shè)向量長度為N，分析：1. 實現(xiàn)鏈接除了無向量寄存器使用沖突和無功能部件使用沖突外，還有時間時間上的要求，只有當(dāng)前一條指令的第一個結(jié)果分量送入結(jié)果向量寄存器的那一個時鐘周期方可鏈接，若錯過該時刻就不能進(jìn)行鏈接，只有當(dāng)前一條向量指令全部執(zhí)行完畢，釋放向量寄存器資源后才能執(zhí)行后面指令。2. 另外，當(dāng)一條向量指令的兩個源操作數(shù)分別是兩條先行指令的結(jié)果寄存器時，要求先行的兩條指令產(chǎn)生運算結(jié)果的時間必須相等，即要求有關(guān)

12、功能部件的延遲時間相等延遲時間相等，此外還要求這兩條向量指令的向向量長度必須相等量長度必須相等，否則也不能鏈接。功能部件沖突功能部件沖突 指令運算符號相同；指令運算符號相同；Vi變量沖突變量沖突 指令中使用的指令中使用的Vi變量相同，具體有變量相同，具體有3種形式，種形式， 即左同名、右同名、上右下左同名。即左同名、右同名、上右下左同名。沖突：沖突： A=B+C A=B+C A=B+C A=D*E D=B*E B=D*E相關(guān)：相關(guān)： A=B+C D=A*E(4) CRAY-1分析指令的分析指令的3條策略條策略無相關(guān)，無沖突無相關(guān)，無沖突 同時啟動；同時啟動；有相關(guān)，無沖突有相關(guān)，無沖突 鏈接啟

13、動；鏈接啟動； 有沖突有沖突 順序執(zhí)行；順序執(zhí)行；（鏈接：鏈接：前條指令結(jié)果不必送回存儲器直接作為后條指令操作數(shù)，甚至可在前條指令結(jié)果不必送回存儲器直接作為后條指令操作數(shù)，甚至可在前條指令完成之前就使用其結(jié)果）前條指令完成之前就使用其結(jié)果）(5)計算向量程序執(zhí)行時間工具計算向量程序執(zhí)行時間工具 多流水線時空圖多流水線時空圖（結(jié)合（結(jié)合P3P39191題題6.66.6實例學(xué)習(xí)實例學(xué)習(xí) ）(3) 沖突及其分類沖突及其分類6.3 6.3 向量處理機(jī)的性能評價（向量處理機(jī)的性能評價（P386P386）一共有一共有4 4個性能指標(biāo)：個性能指標(biāo)：TvpTvp、R R、n n1/21/2、n nv v。6.

14、3.1 6.3.1 向量指令處理時間向量指令處理時間TvpTvp6.3.1.1 6.3.1.1 單條向量指令執(zhí)行時間（第單條向量指令執(zhí)行時間（第9 9行開始）行開始）TvpTvp = Ts + = Ts + TvfTvf + ( n - 1 ) + ( n - 1 ) TcTc其中：其中： TvpTvp 一條向量指令執(zhí)行總時間一條向量指令執(zhí)行總時間Ts Ts 配套標(biāo)量指令的折算時間配套標(biāo)量指令的折算時間TvfTvf 流水線流過時間，即流水線流過時間，即計算第一個分量所需時間計算第一個分量所需時間n n 向量中包含的向量中包含的分量數(shù)分量數(shù)TcTc 流水線流水線“瓶頸瓶頸”段段時間，時間， Tc

15、Tc = max = maxtiti （注：該公式僅比標(biāo)量流水線時間公式（注：該公式僅比標(biāo)量流水線時間公式TkTk = ( k + n - 1 ) = ( k + n - 1 ) maxmaxtiti 多了一項多了一項“輔助標(biāo)量指令折算時間輔助標(biāo)量指令折算時間”TsTs而已，參見而已，參見P286P286公公式式5.22 5.22 ）6.3.1.2 6.3.1.2 不使用鏈接技術(shù)的指令組時間（第不使用鏈接技術(shù)的指令組時間（第1818行開始）行開始）指令之間不論是存在沖突還是相關(guān)關(guān)系，都不能編入同一編隊。指令之間不論是存在沖突還是相關(guān)關(guān)系，都不能編入同一編隊。（編隊：幾條能在一個時鐘內(nèi)一起開始執(zhí)

16、行的向量指令稱為一個編隊）（編隊：幾條能在一個時鐘內(nèi)一起開始執(zhí)行的向量指令稱為一個編隊）例例6.4-6.5 6.4-6.5 對下列指令組編隊，并求對下列指令組編隊，并求出每個出每個編隊的開始、獲得第一個分量編隊的開始、獲得第一個分量結(jié)果、獲得最后一個分量結(jié)果的時間（參見結(jié)果、獲得最后一個分量結(jié)果的時間（參見P387P387表表6.46.4，但是與下面推導(dǎo)數(shù)，但是與下面推導(dǎo)數(shù)據(jù)有出入）據(jù)有出入）LV LV V1V1，RxRxMULTSV V2MULTSV V2，F(xiàn)0F0，V1V1LV LV V3V3，RyRyADDV ADDV V4V4,V2,V2,V3V3SV Ry,SV Ry,V4V4編隊：

17、由于指令編隊：由于指令1 1與與2 2之間關(guān)于之間關(guān)于V1V1相關(guān)、指令相關(guān)、指令3 3與與4 4之間關(guān)于之間關(guān)于V3V3相關(guān)、指令相關(guān)、指令4 4與與5 5之間關(guān)于之間關(guān)于V4V4相關(guān)，所以它們必須分在不同的編隊。結(jié)果如下相關(guān)，所以它們必須分在不同的編隊。結(jié)果如下編隊編隊1 1：指令：指令1 1編隊編隊2 2：指令：指令2 2、指令、指令3 3編隊編隊3 3：指令：指令4 4編隊編隊4 4：指令：指令5 5不使用鏈接技術(shù)的時空圖與各編隊時間不使用鏈接技術(shù)的時空圖與各編隊時間訪存訪存1212段段 指令指令1 1 指令指令3 3 指令指令5 5乘法乘法7 7段段 指令指令2 2加法加法6 6段段

18、 指令指令4 4 12 n-1 12 n-1 6 n-1 12 n-1 12 n-1 12 n-1 6 n-1 12 n-1 時間時間6.3.1.3 6.3.1.3 使用鏈接技術(shù)的指令組時間（使用鏈接技術(shù)的指令組時間（P388P388第第1313行開始）行開始）指令之間只有存在沖突關(guān)系時，才不能編入同一編隊。相關(guān)指令可通過鏈接指令之間只有存在沖突關(guān)系時，才不能編入同一編隊。相關(guān)指令可通過鏈接技術(shù)編入同一編隊。技術(shù)編入同一編隊。例例6.7 6.7 指令組同例指令組同例6.46.4，因使用鏈接技術(shù)，編隊結(jié)果與之不同。即指令，因使用鏈接技術(shù)，編隊結(jié)果與之不同。即指令1 1與與2 2鏈接在同一編隊，指

19、令鏈接在同一編隊，指令3 3與與1 1沖突要分開，指令沖突要分開，指令3 3與與4 4鏈接在同一編隊，指令鏈接在同一編隊，指令5 5與與3 3沖突要分開。結(jié)果如下沖突要分開。結(jié)果如下LV V1LV V1，RxRxMULTSV V2MULTSV V2，F(xiàn)0F0，V1V1編隊編隊1 1：指令：指令1 1、指令、指令2 2LV V3LV V3，RyRyADDV V4,V2,V3ADDV V4,V2,V3編隊編隊2 2：指令：指令3 3、指令、指令4 4SV Ry,V4SV Ry,V4編隊編隊3 3：指令：指令5 5使用鏈接技術(shù)的時空圖與各編隊時間（設(shè)使用鏈接技術(shù)的時空圖與各編隊時間（設(shè)n 64n 6

20、4，即不分段。），即不分段。）訪存訪存1212段段 指令指令1 1 指令指令3 3 指令指令5 5乘法乘法7 7段段 指令指令2 2加法加法6 6段段 指令指令4 4 12 7 n-1 12 6 n-1 12 n-1 12 7 n-1 12 6 n-1 12 n-1 時間時間總時間總時間 = 3n + 46= 3n + 466.3.1.4 6.3.1.4 考慮分段開采的指令組時間（考慮分段開采的指令組時間（P387P387倒數(shù)倒數(shù)第第1515行開始）行開始）說明：當(dāng)向量長度超過寄存器組長度時，需要采用分段開采的算法，每段長說明：當(dāng)向量長度超過寄存器組長度時，需要采用分段開采的算法，每段長度等于

21、寄存器組長度。指令組執(zhí)行總時間如下度等于寄存器組長度。指令組執(zhí)行總時間如下其中：其中： TnTn 指令組執(zhí)行總時間指令組執(zhí)行總時間n n 向量中包含的向量中包含的分量數(shù)分量數(shù)MVL MVL 寄存器組長度寄存器組長度(CRRY-1(CRRY-1為為6464）TloopTloop 配套標(biāo)量指令的折算時間，即前面公式中的配套標(biāo)量指令的折算時間，即前面公式中的TsTstartTstart 流水線流過時間，即前面公式中的流水線流過時間，即前面公式中的TvfTchimeTchime 編隊數(shù)編隊數(shù)（注：這是一個近似公式；注：這是一個近似公式；CRAY-1CRAY-1機(jī)器的機(jī)器的TloopTloop = 15

22、 = 15）chimestartloopnTnTTMVLnT例例6.7 6.7 指令組同例指令組同例6.46.4，因使用鏈接技術(shù)，編隊結(jié)果與之不同。即指令，因使用鏈接技術(shù)，編隊結(jié)果與之不同。即指令1 1與與2 2鏈接在同一編隊，指令鏈接在同一編隊，指令3 3與與1 1沖突要分開，指令沖突要分開，指令3 3與與4 4鏈接在同一編隊，指令鏈接在同一編隊，指令5 5與與3 3沖突要分開。結(jié)果如下沖突要分開。結(jié)果如下LV V1LV V1，RxRxMULTSV V2MULTSV V2，F(xiàn)0F0，V1V1編隊編隊1 1：指令：指令1 1、指令、指令2 2LV V3LV V3，RyRyADDV V4,V2,

23、V3ADDV V4,V2,V3編隊編隊2 2：指令：指令3 3、指令、指令4 4SV Ry,V4SV Ry,V4編隊編隊3 3：指令：指令5 5不論向量長度是否大于寄存器組長度，均可代入分段開采時間公式，計算指不論向量長度是否大于寄存器組長度，均可代入分段開采時間公式，計算指令組執(zhí)行總時間。此處令組執(zhí)行總時間。此處TchimeTchime = 3 = 3，Tloop = 15Tloop = 15，TstartTstart = 12+7+12+6+12 = 12+7+12+6+12 = 49= 49，MVL=64MVL=64。注意公式法得數(shù)與圖解法的得數(shù)不完全相同。注意公式法得數(shù)與圖解法的得數(shù)不完全相同。6443643491564nnnnnTnTTMVLnTchimestartloopnR表示當(dāng)向量長度為無窮大時的向量流水線的最大性能，單位為MFLOPS。6.3.2 最大性能R它是向量流水線性能達(dá)到R的1/2時對應(yīng)的向量長度。6.3.3 半性能向量長度n1/2它表示