向量流水技術.ppt

2020/4/26,1,3.6向量流水技術,（第3章續(xù)）,2020/4/26,2,向量處理機是具有向量數(shù)據(jù)表示和向量指令系統(tǒng)的處理機。向量處理機是解決數(shù)值計算問題的一種高性能計算機。向量處理機屬大型或巨型機，也可以用微機加一臺向量協(xié)處理器組成。向量處理機一般都采用流水線結構，通常有多條并行工作的流水線。必須把要解決的問題轉化為向量運算，才能發(fā)揮向量處理機的效率。,2020/4/26,3,3.6.1向量流水機的基本系統(tǒng)結構,1.標量流水線的局限性處理機不具有向量數(shù)據(jù)表示，僅對標量數(shù)據(jù)進行流水處理。向量的處理通過標量循環(huán)程序完成。所以，(1)流水線工作的時鐘周期不可能取得很短。(2)取指令及譯碼的速率受限。即在一個時鐘周期內最多只能啟動一條指令，通常稱為Flynn瓶頸。2.向量流水線處理機具有向量數(shù)據(jù)表示，可通過向量指令對向量中的各元素進行流水處理。,2020/4/26,4,3.6.1.1向量流水處理的主要特點,(1)在向量操作中，每個當前結果向量元素的計算與以前結果向量元素的計算是相互獨立的，有利于發(fā)揮流水線的性能，允許向量流水線有較深的深度。(2)一條向量指令相當于一個標量循環(huán)，可降低對指令訪問帶寬的要求，也消除了由循環(huán)轉移可能引起的控制相關。(3)若向量指令所要訪問的向量元素均相鄰，則可利用多模塊、交叉存取的方法加快向量元素的存取速度，減少訪存等待時間的開銷。,2020/4/26,5,在對相同數(shù)量的數(shù)據(jù)項進行操作時，向量操作要比一串標量指令操作更快。向量流水機可使訪存和有效地址計算流水化。高檔的向量機允許多個向量操作同時進行，從而可開發(fā)對不同元素進行多個向量操作的并行性。,2020/4/26,6,3.6.1.2向量機的基本系統(tǒng)結構,向量機系統(tǒng)結構的分類存儲器存儲器工作方式向量機向量操作的源向量和目的向量都取自或存放到主存中。寄存器寄存器工作方式向量機向量操作的源向量和目的向量都取自或存放到向量寄存器中。,2020/4/26,7,典型的向量機基本系統(tǒng)結構,向量機主要由標量流水部件和向量流水部件組成，包含了向量功能部件、向量取存部件、向量寄存器或向量緩沖部件、標量寄存器、標量處理部件以及向量控制器等部件。,2020/4/26,8,向量處理機的典型結構圖,2020/4/26,9,例：一個典型向量求解問題：YaXY其中X和Y為向量，初始值存放在存儲器中，a為標量。采用雙精度運算時的算法：a乘X后再加Y。,2020/4/26,10,若用標量機運算，需要用標量指令對向量中的每個元素進行一次乘、加和存儲操作，并且為了實現(xiàn)循環(huán)操作，每次必須要指明對X和Y中元素位置的下標變量進行增量，并使操作次數(shù)每次減1，以判別循環(huán)是否結束。設X和Y向量的首地址分別存放在Rx和Ry中，當向量元素長度為64時，用標量機處理的循環(huán)程序段為：,2020/4/26,11,LDF0，a；標量a裝入F0ADDIR4，Rx，#512；將向量元素的末地址裝；入R4中LOOP：LDF2，0(Rx)；取向量元素X(i)MULDF2，F(xiàn)0，F(xiàn)2；a與X(i)相乘LDF4，0(Ry)；取向量元素Y(i)ADDDF4，F(xiàn)2，F(xiàn)4；aX(i)與Y(i)相加SD0(Ry)，F(xiàn)4；存結果向量元素ADDIRx，Rx，#8；增量向量元素X下標ADDIRy，Ry，#8；增量向量元素Y下標SUBR20，R4，Rx；R4RxR20，計算是；否到達限界值BNZR20，LOOP；若循環(huán)未結束，轉LOOP,2020/4/26,12,用向量機完成同樣操作：LDF0，a；標量a裝入F0LVV1，Rx；裝入向量X，LV為向量取指令MULTVV2，F(xiàn)0，V1；向量X與標量a相乘LVV3，Ry；裝入向量YADDVV4，V2，V3；向量加aXYSVRy，V4；存結果向量，SV為向量存指令,2020/4/26,13,因為向量指令是對64個元素進行操作，且沒有對元素下標變量增量和判循環(huán)是否結束的指令，所以向量機只需執(zhí)行6條指令即可完成操作，從而大大降低了對指令帶寬的要求。,2020/4/26,14,標量機與向量機計算YaXY的比較,2020/4/26,15,3.6.1.3向量啟動時間和啟動率,一條向量指令執(zhí)行所需時間Tvp：TvpTstnIrTst：向量流水線的啟動時間，包括流水線固有的延遲時間，用于設置為完成向量操作所需的相應參數(shù)(如向量長度等)。n：向量中元素長度Ir：啟動率，表示向量流水線填滿后，每流出一個結果所需時間。,2020/4/26,16,例：一個向量乘法流水部件的啟動時間為l0個時鐘周期。啟動后的啟動率為1。對于長度為64的向量乘法，產生每個向量元素結果所需時鐘周期數(shù)為：對于運行速度較慢的向量流水操作，啟動時間的大小對它的影響不大，但對于啟動率為1的高速向量流水操作，啟動時間的增加就將使性能受到較大影響。,2020/4/26,17,寄存器寄存器工作方式的影響因素,向量功能部件流水線的深度流水線的啟動時間主要取決于功能部件流水線的深度。因為這是獲取第一個流水結果所需的時間。向量功能部件接收一個操作數(shù)的頻率流水線的啟動率主要取決于相應的向量功能部件接收一個操作數(shù)的頻率。當流水線處于充分流水狀態(tài)時，就能在每個時鐘周期開始時立即對一個新操作數(shù)進行運算，從而可使啟動率達到1。,2020/4/26,18,3.6.2向量操作長度控制和向量訪問步長,1.向量操作長度控制實際程序中的向量長度往往并不與向量機的自然向量長度相同。自然向量長度：向量寄存器型的向量機中，每個向量寄存器可存放的向量元素個數(shù)。,2020/4/26,19,程序中一個具體的向量操作長度在編譯時經常是未知的，因為在一個代碼段中可能需要不同的向量長度。例如求解單精度向量循環(huán)SAXPY的代碼段為：for(i=0;in;i+)Yia*XiYi;,2020/4/26,20,可見向量操作長度依賴于n值，而這個n值通常在編譯時無法知道，往往要在運行時才可確定，而且這個長度也可能是過程的參數(shù)，因此在執(zhí)行時很易改變。解決方法：采用一個向量長度寄存器，存放某一代碼段操作的長度，由它來控制向量操作的長度以及向量的裝載和存儲。,2020/4/26,21,在向量長度寄存器中存放的向量長度值不能超過向量寄存器的長度(MVL)。向量長度小于向量寄存器長度時，均可放入向量寄存器。向量長度大于向量寄存器長度時，需將向量長度按向量寄存器長度分段，分段后的向量長度即是每次向量操作的長度，它必須等于或小于向量寄存器長度。,2020/4/26,22,采用分段技術后，SAXPY循環(huán)可寫成如下形式：low0;VLn%MVL;*找出零頭長度值for(j0;jn/MVL;j+)*外循環(huán)for(ilow;ilowVL;i+)*以長度VL操作Yia*XiYi;*主要操作lowlowVL;*下一向量的開始VLMVL;*將長度值恢復成MVL;經分段處理后，第一段長度為nmodMVL，而以后各段的長度均為MVL。,2020/4/26,23,2.向量訪問步長,存儲器是一維線性空間，當需要在其中存放二維或多維數(shù)組時，必須將其各元素映射到一維線性空間中。以行為主的存儲方式：當按行進行元素訪問時，要訪問的元素的地址是相鄰連續(xù)的。當按列進行元素訪問時，要訪問的元素的地址是不連續(xù)的，需要采用向量跨步方式進行訪問。,2020/4/26,24,例：元素為100100的ABC矩陣乘法的程序段為：for(i0;i100;i+)for(j0;j1億次/秒主存系統(tǒng)模31體交叉訪問，存儲周期400nsI/O通道20個，接外圍系統(tǒng),2020/4/26,63,（3）中央處理機結構三部分組成：Regs、流水部件和指令緩沖部件操作寄存器和后援寄存器兩組向量寄存器：（8x64x64b)x2V,V向量長度寄存器：VL（7b，128,即最多可傳64對向量元素）向量控制寄存器VM(64b),VM(64b)（屏蔽寄存器，用于向量的測試、歸并、壓縮和還原）標量寄存器S(8x64b)和標量后援寄存器T(64x64b)M地址寄存器A(8x24b)和地址后援寄存器B(64x64b),2020/4/26,64,功能部件18個獨立的專用功能部件一組地址部件-24b的短整運算AA（1）,AM（3）一組標量部件-64b整數(shù)和邏輯運算對S運算SA（1）,SS左右移位（1）,SLg（0）,SP計數(shù)（1，2）二組浮點部件-向量、標量運算（分別與V,V接）FA（5）,FM（6）,FR倒數(shù)近似值（6）二組向量部件-64位的非浮點數(shù)向量運算（V,V）VA（1）,VS左右移位（3，2）,VLg（1）,2020/4/26,65,VV寄存器與功能部件的使用,向量功能部件，浮點功能部件,Vk,Vj,Vi,向量功能部件，浮點功能部件,Vk,Vj,Vi,2020/4/26,66,指令控制部件程序字計數(shù)器P(24b)指令緩沖站IB(4個站x16x16b)指令字緩沖寄存器BIP(16b)下一指令字寄存器NIP(16b)現(xiàn)行指令字寄存器CIP(16b)低部指令字寄存器LIP(16b)指令流出控制部件IC4類向量指令格式與Cray-1相似，但訪存流水m=16,2020/4/26,67,向量與標量性能的平衡,實際的應用問題中通常既有向量計算又有標量計算，而且兩類計算有一定的比例向量平衡點(vectorbalancepoint)：為了使向量硬件設備和標量硬件設備的利用率相等，一個程序中向量代碼所占的百分比。關鍵問題是：希望向量硬件和標量硬件都能夠充分利用，不要空閑。,2020/4/26,68,例如：一個系統(tǒng)的向量運算速度為90Mflops，標量運算速度為10Mfolps。如果程序的90是向量運算，10是標量運算。則向量平衡點為0.9。硬件利用率最高。向量處理機的向量平衡點必須與用戶程序的向量化程度相匹配。IBM向量計算機的設計思想與上述方法不同，它維持較低的向量與標量比例，定在35的范圍之間。這種做法能夠適應通用應用問題對標量和向量處理要求。,2020/4/26,69,2020/4/26,70,3.6.4.2鏈接技術,鏈接特性：當相鄰兩條指令存在先寫后讀相關時，只要前一條指令的結果向量的第一個元素產生并存入結果向量寄存器，就可以將它作為下一條指令的源操作數(shù)，啟動下一條指令的運算，從而將兩個或兩個以上的功能部件鏈接起來。,2020/4/26,71,鏈接技術：當從一個流水線部件得到的結果直接送入另一個功能流水線的操作數(shù)寄存器時所發(fā)生的連接過程。換句話說，中間結果不必送回存儲器或寄存器，并在向量操作完成以前就使用它。,2020/4/26,72,在寄存器寄存器系統(tǒng)結構中，所有的向量操作數(shù)在把它們送入流水線之前，都要預先裝入向量寄存器中。中間和最后結果(流水線輸出)在把它們存入主存儲器以前，也要把它們裝入向量寄存器中。,2020/4/26,73,鏈接技術是利用向量指令間存在的先寫后讀的數(shù)據(jù)相關性來加快向量指令序列執(zhí)行速度的技術。鏈接技術的實質是標量流水定向傳送方法在向量寄存器中的應用。,2020/4/26,74,當發(fā)出向量指令時，所要求的功能流水線和操作數(shù)寄存器便要預定若干個時鐘周期，其值取決于向量長度。使用同一組功能部件或操作數(shù)寄存器的后繼向量指令在預定被釋放之前是不能發(fā)出的。兩個或更多的向量指令如果是不相關的，便可以同時使用不同功能流水線和不同的向量寄存器。這種并發(fā)的指令能以相繼的時鐘周期發(fā)出。,2020/4/26,75,結果寄存器可能成為后繼指令的操作數(shù)寄存器。在Cray1中，這種技術稱為兩條流水線的鏈接(chaining)。鏈接是從流水線的內部定向概念發(fā)展而來的。鏈接允許當?shù)谝粋€結果剛剛可用時就馬上發(fā)出相繼的操作。當然，所需要的功能流水線和操作數(shù)寄存器必須恰當?shù)仡A定，否則，鏈接操作就不得不掛起直到所需要的資源變?yōu)榭捎脼橹埂?2020/4/26,76,功能部件和操作數(shù)寄存器的預定（沖突）,2020/4/26,77,例：向量加和向量乘的操作ADDVV1，V2，V3；V1V2V3MULTVV4，V1，V5；V4V1V5這兩條指令間對V1向量寄存器存在先寫后讀相關，如果使向量寄存器V1在同一時鐘周期內，既接收一個功能部件送來的運算結果，又可把這一結果作為下一個向量指令運算所需的源操作數(shù)送給另一個功能部件，就可使這兩個部件鏈接起來進行操作。通常把這種鏈接稱為超級向量操作。當鏈接進入充分流水操作狀態(tài)后，在一個時鐘周期內就可同時獲取兩個操作結果。,2020/4/26,78,例：以下4條向量指令序列鏈接在一起執(zhí)行一種復合的功能：V0存儲器；讀存儲器V2V0+V1；向量加V3V2A3；右移V5V3V4；求邏輯積下圖給出的圖解說明表示把存儲器讀流水線、向量加流水線、向量移位流水線和向量邏輯乘流水線鏈接成一個較長的流水線。寄存器A3的內容決定移位計數(shù)值。,2020/4/26,79,2020/4/26,80,時間特征,2020/4/26,81,2020/4/26,82,例：要進行向量運算DA(BC)設向量長度64，且B和C已由存儲器取至V0和V1，則完成運算的向量指令為：LDV3，A；V3AADDVV2，V0，V1；V2V0V1MULTVV4，V2，V3；V4V2V3第一、二條指令因既無向量寄存器使用沖突，也無功能部件使用沖突，因而可并行執(zhí)行。第三條指令與第一、二條指令均存在先寫后讀相關沖突，因而可將第三條指令與第一、二條指令鏈接執(zhí)行。,2020/4/26,83,2020/4/26,84,采用并行和鏈接加速技術后，當被加工向量長度為N時，執(zhí)行所需時間為：(161)(171)(N1)17N1N16拍若這三條指令全部用串行方法則所需時間為：(161)N1(161)N1(171)N13N22拍若前兩條指令并行執(zhí)行，第三條指令串行執(zhí)行，則所需時間為：(161)N1(171)N12N15拍注意：由于同步的要求，數(shù)據(jù)進入和流出每個功能部件，包括訪存都需要1拍時間。,2020/4/26,85,實現(xiàn)鏈接的時間上的要求：只有當前一指令的第一個結果分量送入結果向量寄存器的那一個時鐘周期方可鏈接，若錯過該時刻就無法進行鏈接，只有等前一向量指令全部執(zhí)行完畢，釋放向量寄存器資源后才能執(zhí)行后面指令。在上面的例子中，當一條向量指令的兩個源操作數(shù)分別是兩條先行指令的結果寄存器時，要求先行的兩條指令產生運算結果的時間必須相等，即要求有關功能部件的延遲時間相等(如上例中的訪存和浮點加功能部件延時均為6個時間單位)。進行鏈接的向量指令的向量長度必須相等，否則就不可能鏈接。,2020/4/26,86,例：在CRAY1機中，浮點功能部件中各功能段的執(zhí)行時間為：浮點加法：6拍；浮點乘法：7拍；求倒數(shù)：14拍；存儲器存/?。?拍；啟動功能部件：1拍；打入結果：1拍。分析任務數(shù)為50時，下列指令段的完成時間：V0存儲器V3V1V2V4V0V3V0V4V5,2020/4/26,87,分析：與無功能和寄存器沖突，可并行。與先寫后讀數(shù)據(jù)相關，可以鏈接。與有功能沖突，必須在與執(zhí)行完后，才能啟動，即只能串行工作。V0存儲器V3V1V2V4V0V3V0V4V5執(zhí)行時間：(161)(171)(501)(161)(501)123拍,并行,鏈接,串行,2020/4/26,88,例：分析在CRAY1機中，任務數(shù)為50時，下列指令段的完成時間。V0存儲器V1V2V3V6V4V5分析：三條指令均無功能沖突，可采用全并行的方式，指令段的完成時間為：(171)(501)58拍,2020/4/26,89,例：分析在CRAY1機中，任務數(shù)為50時，下列指令段的完成時間，設浮點求倒數(shù)的執(zhí)行時間為14拍。V2V0V1V3存儲器V4V2V3V51/V4分析：與無功能和寄存器沖突，可并行。與節(jié)拍不一致，不能與、鏈接，只能串行執(zhí)行。與先寫后讀數(shù)據(jù)相關，可以鏈接。執(zhí)行時間：(171)(501)(161)(1141)(501)131拍,并行,鏈接,串行,2020/4/26,90,3.6.5向量處理性能的評估參數(shù)和方法,衡量向量處理機的性能主要是向量指令的處理時間Tvp、向量長度為無窮大時的向量處理機的最大性能R、半性能向量長度n1/2和向量方式的工作速度優(yōu)于標量串行方式工作時所需的向量長度臨界值nv等。下面討論這些參數(shù)。,2020/4/26,91,在向量處理機上，執(zhí)行一條向量長度為n的向量指令的時間Tvp可表示為：TvpTsTvf(n-1)Tc其中，Ts為向量流水線的建立時間，它包括向量起始地址的設置、計數(shù)器加1，條件轉移指令執(zhí)行等。Tvf為向量流水線的流過時間，它是一條指令從開始譯碼到流過流水線得到第一個結果的時間。Tc為流水線“瓶頸”段的執(zhí)行時間。,1.向量指令的處理時間Tvp,2020/4/26,92,如果不存在“瓶頸”流水段，每段的執(zhí)行時間都等于一個時鐘周期，則上式也可以寫成：Tvpse(n-1)其中，s為向量流水線建立時間所需的時鐘周期數(shù)，e為向量流水線流過時間所需的時鐘周期數(shù)，n為向量長度，為時鐘周期。,2020/4/26,93,向量編隊,一組向量操作的執(zhí)行時間主要取決于下面三個因素：向量的長度、向量操作之間是否存在流水功能部件的沖突和數(shù)據(jù)的相關性。1）能在一個時鐘周期內一起開始執(zhí)行的向量指令稱為一個編隊。（一定不存在流水功能部件的沖突和數(shù)據(jù)的相關性RAW除外）2）有沖突和相關的指令分在不同的編隊。3）一個編隊的運行時間為隊中耗時最長的指令運行時間,2020/4/26,94,例3.6.5.1：假設每種流水功能部件只有一個，則下面一組向量操作能分成4個編隊：LVV1，Rx；取向量xMULTSVV2，F(xiàn)0，V1；向量和標量相乘LVV3，Ry；取向量YADDVV4，V2，V3；加法SVRy，V4；存結果第一條指令LV為第一個編隊。MULTSV指令因為與第一條LV指令相關，它們不能在同一個編隊中。,2020/4/26,95,MULTSV指令和第二條LV指令之間不存在功能部件沖突和數(shù)據(jù)相關，所以這兩條指令為第二個編隊。ADDV指令與第二條LV指令數(shù)據(jù)相關，所以ADD為第三個編隊。SV指令與ADDV指令數(shù)據(jù)相關，所以它為第四個編隊。所以這一組向量操作劃分為以下四個編隊:1LV2MULTSVLV3ADDV4SV,2020/4/26,96,一個編隊計算一個元素的執(zhí)行時間記為Tchime，它與向量長度無關（1拍）。因此，一組由m個編隊組成的向量操作的執(zhí)行時間為m個Tchime。如果向量長度為n，則整個程序的向量操作的執(zhí)行時間為mn個時鐘周期。上述例子中，因為整個程序分為4個編隊，所以要花費4個Tchime。,2020/4/26,97,除了上述向量操作的真正執(zhí)行時間外，還需要考慮向量的啟動時間Tstart，Tstart是向量操作流水線的延遲，它等于流水功能部件的流水段數(shù)，也即流水線的深度。它和上述的向量流水線的流過時間幾乎相等。,2020/4/26,98,例3.6.5.2：假設一臺向量處理機中功能部件的啟動開銷為：取數(shù)和存數(shù)部件為12個時鐘周期、乘法部件為7個時鐘周期、加法部件為6個時鐘周期。則例6.5.1中每個編隊的開始時間、獲得第一個結果元素的時間和獲得最后一個結果元素的時間如下表所示。（未考慮鏈接情況）,2020/4/26,99,如果向量長度n為64，則得到一個結果元素的平均時間為：4+(41/64)=4.64個時鐘周期。,2020/4/26,100,程序段的執(zhí)行時間,考慮向量長度大于向量寄存器長度時，則需要分段開采。分段開采的開銷由執(zhí)行標量代碼的開銷Tloop和每個編隊的向量啟動開銷Tstart組成。所以向量長度為n的向量操作（程序段）的整個執(zhí)行時間為：,2020/4/26,101,為了簡單起見，我們把Tloop看作是一個常數(shù)，Cray1機器的Tloop約等于15。下面我們用例子來說明Tn和Tstart的計算。,2020/4/26,102,例3.6.5.3：在一臺向量處理機上實現(xiàn)ABs操作，其中A和B是長度為200的向量，s是一個標量。向量寄存器長度為64。各功能部件的啟動時間見本PPT50。求總的執(zhí)行時間。,2020/4/26,103,解：因為向量長度超過了向量寄存器的長度，所以要采取分段開采方法。每次循環(huán)主要由下面3條向量指令組成:LVV1，RbMULTSVV2，V1，F(xiàn)0（s已預存入F0）SVRa，V23條指令相關，m=3;n=200n/64=4（取整，零頭算1組）,2020/4/26,104,Tn=4(15+Tstart)+32001=660+4Tstart又3組串行工作，Tstart=7(load)+7(mul)+6(store)=20Tn=660+80=740節(jié)拍一個結果元素的平均執(zhí)行時間(包括啟動開銷)為740/200=3.7。下面討論編隊中考慮鏈接的情況,2020/4/26,105,例3.6.5.4：在某臺向量處理機上執(zhí)行DAXPY(Double-Precisiona*XplusY)代碼，即完成YaX+Y,其中X和Y是向量，最初存放在內存。a是一個標量。它們的向量指令如下：(MVL=64)LVV1，Rx；12MULTSVV2，F(xiàn)0，V1；7LVV3，Ry；12ADDVV4，V2，V3；6SVRy，V4；12解：這5條向量指令分成3個編隊，并且前兩個編隊中每兩條指令組成一條鏈。,202