計算機系統(tǒng)結構.ppt

1、計算機系統(tǒng)結構,主講 蔡啟先,第6章 并行計算機,并行處理機（Parallel Processor）和向量處理機同屬于SIMD（單指令流多數(shù)據(jù)流）計算機。但是向量處理機主要通過時間重疊來實現(xiàn)并行處理，而并行處理機主要通過資源重復來實現(xiàn)并行處理。,第 6 章 并 行 計 算 機,6.1 陣列處理機,6.3 相聯(lián)處理器,6.7 超長指令字處理機,第 6 章 并 行 計 算 機,6.4 脈動陣列機,6.6 超標量流水線和超級流水線,6.5 互聯(lián)網(wǎng)絡,6.2 陣列機中并行存儲器的無沖突訪問,6.1 陣列處理機,6.1.1 SIMD計算機的基本概念和模型 6.1.2 陣列處理機的特點,6.1.1 SIM

2、D計算機的基本概念和模型,并行處理機是指重復設置多個同樣的處理單元PE（Processing Element），按照一定的方式相互連接，在統(tǒng)一的控制部件CU（Control Unit）作用下，各自對分配來的數(shù)據(jù)并行地完成同一條指令所規(guī)定的操作。由于并行處理機的多個處理單元通常構成陣列，故又稱陣列處理機（Array Processor）。陣列處理機是操作級并行的SIMD計算機。,6.1.1 SIMD計算機的基本概念和模型,SIMD計算機(Single instruction stream multiple data stream computer) 單一控制部件控制下的多處理單元(PE Proc

3、essing Elements)構成的陣列,M=(N,C,I,M,R) N：機器處理單元PE數(shù)目 C：控制部件CU直接執(zhí)行的指令集 I：CU廣播至所有PE進行并行執(zhí)行的指令集 M：屏蔽方案集 R：數(shù)據(jù)尋徑功能集,SIMD計算機的操作模型,由于存儲器的組成方式不同， SIMD計算機有兩種結構 1。分布式存儲器結構 2。共享存儲器結構,1。分布式存儲器結構,PE各帶有只能被本處理器訪問的本地存儲器LM（Local Memory），控制部件內有存放程序和數(shù)據(jù)的主存儲器，整個系統(tǒng)在統(tǒng)一的陣列控制部件作用下并行操作，運行用戶程序和部分系統(tǒng)程序。,在執(zhí)行主存儲器中的用戶程序時，所有指令由控制部件譯碼，把只

4、適合串行處理的標量或控制類指令留給控制部件自己執(zhí)行，而把適合于并行處理的向量類指令“播送”給各個PE，控制處于“活躍”的PE并行執(zhí)行。,這種結構要求能把數(shù)據(jù)合理地與分配到各個PE的LM中，運算中，PE間可通過互聯(lián)網(wǎng)絡ICN（Interconnection Network）來交換數(shù)據(jù)。 典型機型有：ILLIAC 4、MPP、DAP、CM-2、MP-1、DAP600系列等,具有分布式存貯器的陣列處理機結構,2。共享存儲器結構,共享的多體并行存儲器SM(Share Memory)通過對準網(wǎng)絡與各處理單元PE相連,6.1.2 陣列處理機的特點,1. 適合高速數(shù)值計算 如有限差分、矩陣、信號處理、線性規(guī)

5、劃 2. 對向量所包含的各個分量同時進行計算。 利用資源重復，而不是時間重疊。有效率問題。 3. 利用互聯(lián)網(wǎng)絡連接PE。 互聯(lián)網(wǎng)絡的構型可能限定解題方法，是設計重點 4. 有效速度取決于向量運算速度、標量運算速度和編譯過程的開銷 5. 基本上是一臺向量處理專用計算機，其結構與所采用的并行算法密切相關,陣列處理機實質上是由 專門對付數(shù)組運算的處理單元陣列組成的處理機， 專門從事處理單元陣列的控制及標量處理的處理機和 專門從事系統(tǒng)輸入輸出及操作系統(tǒng)管理的處理機 組成的一個異構型處理機系統(tǒng)。,6.2 陣列機中并行存儲器的無沖突訪問,在共享存儲器結構 的陣列機中，存儲器頻帶要與多個處理單元的速率匹配，

6、必須采取多體并行存儲器。同時還要保證在各種訪問模式下，實現(xiàn)無沖突地訪問。 以一位數(shù)組為例（分體數(shù)m=4）。 按圖中安排，每次訪問相連的m個元素，不會有訪存沖突。,若按2變址，即同時訪問奇數(shù)或偶數(shù)下標的元素時，則因訪存沖突，存儲器頻帶下降一半。 一般，并行存儲的分體數(shù)m應取成質數(shù)，只要變址跳距與m互質，不會有訪存沖突。 例如取m=3.,對于多位數(shù)組，問題可能復雜一些，下面以二維數(shù)組來討論。 如果設m=n=4, 一個44 的二維數(shù)組直接按行存貯，如圖：,雖然，同時訪問某一行、主對角線或次對角線上的所有元素時，都可以做到無沖突地訪問，但要同時訪問某一列的各元素時，由于它們集中存放在同一存貯分體內，會

7、產(chǎn)生訪存沖突，所以每次只能順序訪問其中的一個元素，致使實際頻寬降低成 1/4。,為了能實現(xiàn)按行或按列并行訪問， 采用錯位存放的方案 (m=n=4, 1=2=1),假設在nn的二維數(shù)組中，同一列兩個相鄰元素在并行存貯器中錯開的地址距離為1，而同一行兩個相鄰元素在并行存貯器中錯開的距離為2，當m取成22p+1(p為任意正整數(shù))時，實現(xiàn)無沖突訪問的充分條件就是讓1=2p, 2=1。,下圖 就是對 44 的二維數(shù)組按上述規(guī)則存貯的一種方案。其中 p=1, m=5, 1=2,2=1。,6.3 相 聯(lián) 處 理 器,6.3.1 相聯(lián)處理機和相聯(lián)存儲器,6.3.2 相聯(lián)存儲器的基本組成和工作原理,6.3.3

8、相聯(lián)檢索算法,問題的提出：多體并行存儲器要解決的是加速向處理器提供指令流和數(shù)據(jù)流的速度，如果存儲器本身具有一定的信息處理功能，有意識地提供處理器所需要的數(shù)據(jù)的話，則可望更進一步提高并行訪存的性能。 相聯(lián)存儲器：一種帶信號處理功能的存儲器，它可以按所給信息內容的部分或全部特征作為檢索項(即關鍵字項)，去檢索存儲器， ，將內容與該特征相符的所有存儲單元一次性找出來。,6.3.1 相聯(lián)處理機和相聯(lián)存儲器,相聯(lián)處理機： 以相聯(lián)存儲器為核心，配上必要的中央處理部件、指令存儲器、控制器和I/O接口，就構成一臺以存儲器并行操作為特征的相聯(lián)處理機（Associative Processor）。,相 聯(lián) 處 理

9、 機,以相聯(lián)存儲器為核心，配置必要的中央處理部件、指令存儲器、控制器和I/O接口，構成以存儲器并行操作為特征的相聯(lián)處理機 （Associative Processor）。,6.3.2 相聯(lián)存儲器的基本組成和工作原理,n字m位的相聯(lián)存儲器位陣列,陣列中的每個位單元Bij是一個與比較邏輯門和讀寫控制電路相連的觸發(fā)器,相 聯(lián) 處 理 機 的 位 單 元,相聯(lián)處理機的特點,基于存儲器并行操作的SIMD處理機。 不是按地址順序訪存，而是按所存信息的特征如關鍵字比較而實現(xiàn)并行地訪存。,（2）來自控制器的一條命令能對多個數(shù)據(jù)同時執(zhí)行算邏運算，因為相聯(lián)存儲器具有處理單元，整體速度很高。,（3）適于大量數(shù)組進行

10、高速運算處理。,（4）主要問題是硬件成本高。,6.3.3 相聯(lián)檢索算法,從相聯(lián)存儲器的組成可以看出，其實現(xiàn)的只是一種全等比較操作，實際上還可以有多種比較查找操作，例舉幾個。,1) 全等查找算法 2) 最大值查找算法 3) 幅值比較查找算法 4）其他算法,1) 全等查找算法,所謂全等查找，是指找出與比較數(shù)寄存器CR未屏蔽的那部分內容完全相同的全部字單元。因此，只要將比較查找的內容裝入比較數(shù)寄存器CR中，然后對屏蔽寄存器MR中為“1”的那些位片段，逐位地進行相聯(lián)查找即可。凡出現(xiàn)與比較數(shù)寄存器內容不相等，即當CRj=1而Bij=0 或 CRj=0 而Bij=1 時，查找產(chǎn)生的信號將字選擇寄存器的WS

11、Ri置成“0”。這樣，只要等各位片逐一查找比較完畢之后，字選擇寄存器WSR中標志位仍為 1 的那些存貯單元就是全等查找的響應單元，其內容必定與比較數(shù)完全相等。由于全等查找比較簡單，如采用全并行方式工作的相聯(lián)存貯器，硬件保證位片間同時操作，將使查找速度有顯著提高。,2)最大值查找算法,所謂最大值查找，是要找出存貯器中所存的最大數(shù)及存放此最大數(shù)的所有單元，相同的最大值完全可能有多個。與全等查找算法類似，同樣可以事先設置好屏蔽寄存器和字選擇寄存器的初始狀態(tài)來控制位向和字向的哪些部分參與查找。 首先，將字選擇寄存器置成全“1”， 比較數(shù)寄存器CR置初始值為全“1”， 屏蔽寄存器的最高位置為“1”、 其

12、余位置為“0”。 然后， 進行比較， 看是否有單元響應。 這時只是檢查各待查單元的最高位是否為 1。,若有響應，表明最大值的最高位為 1，讓所有未響應單元產(chǎn)生信號， 將字選擇寄存器的對應位WSRi都置成“0”，使其不再繼續(xù)參與下一位片的查找；如沒有一個響應，表明最大值的最高位為 0， 因此只要將比較數(shù)寄存器的該位改置為“0”， 并維持字選擇寄存器中的內容不變即可。,下一步， 將屏蔽寄存器的次高位置為“1”， 其余位置為“0”， 再進行類似的比較及處理。 這樣，自左到右逐位比較處理完畢， 其比較數(shù)寄存器中保留的內容就是要找的最大值，而字選擇寄存器中的狀態(tài)就是存放此最大值所在存貯單元的位置。,3)

13、幅值比較查找算法,幅值比較查找是指在給定某比較數(shù)后，要分別找出存貯器中內容大于、等于、小于該比較數(shù)的單元位置，也就是將存貯器的單元按給定幅值進行比較， 將其分成 3 類。為此，可對每個單元設置一個三位的標志位XYZ。 查找開始前，設各單元的標志位XYZ為 100，表示“未定”狀態(tài)。然后自左至右逐位查找， 結果可能會出現(xiàn)下面 3 種狀況：,(1) CRj=0, Bij=1。這表示i單元第j位的值大于比較數(shù)第j位的值， 可以置標志位XYZ為 010，此后，該i單元不再參與比較；,(2) CRj=1, Bij=0。這表示i單元第j位的值小于比較數(shù)第j位的值，可以置標志位XYZ為 001，此后，該i單

14、元也不再參與比較； ,(3) CRj=Bij。這表示i單元的第j位的值等于比較數(shù)第j位的值，讓標志位維持 100 不變，之后，該i單元仍繼續(xù)參與下一個位片的比較。 ,如果將所有單元從最高位到最低位全部查找一遍，根據(jù)各個單元標志位XYZ的狀態(tài)就能知道哪些單元的內容等于比較數(shù)， 哪些大于比較數(shù)， 哪些小于比較數(shù)。 這樣， 按幅值分類的工作也就完成了。,6.3.4 相聯(lián)處理機結構舉例,1） PEPE系統(tǒng),2. STARAN系統(tǒng),相聯(lián)陣列模塊的結構,6.4 脈 動 陣 列 機,6.4.1 脈動陣列機的結構原理,6.4.2 通用脈動陣列機的發(fā)展,6.4.1 脈動陣列機的結構原理,脈動陣列結構由一些處理單

15、元PE構成的陣列。每個PE的內部結構相同，一般由運算部件加上若干鎖存器構成。 陣列內所有處理單元的數(shù)據(jù)鎖存器受同一時鐘控制，運算時數(shù)據(jù)在陣列結構的各個處理單元之間沿著各自的方向同步向前推進。 陣列內部的各個單元只接收前一組處理單元傳來的數(shù)據(jù)，并向后一組處理單元發(fā)送數(shù)據(jù)。,這樣，預先確定的數(shù)據(jù)流動模式使數(shù)據(jù)從流進處理單元陣列到流出處理單元陣列的過程中完成所有對它應做的處理，無需再重新輸入這些數(shù)據(jù) ，且只有陣列的“邊界”處理單元才和存儲器或I/O接口進行通信，由此實現(xiàn)在不增加陣列機輸入、輸出速率的條件下，提高陣列機的處理速度。,脈動陣列互聯(lián)構形,脈 動 陣 列 機 的 特 點,（1）結構簡單、規(guī)整

16、，可擴充性好，非常適合VLSI實現(xiàn)。 （2） PE間數(shù)據(jù)通信距離短，規(guī)則，便于數(shù)據(jù)流、控制流、同步控制等設計。 （3）脈動陣列中所有PE同時計算，計算并行性極高。 （4）輸入數(shù)據(jù)被多個PE重復使用，大大減輕陣列與外界的通信。 （5）脈動陣列構型與特定計算任務和算法密切相關，限制了應用范圍。,6.4.2 脈動陣列機的發(fā)展,近年來人們研究了一些措施來改進脈動陣列結構，增強其通用性。 一種方法是增設附加硬件，通過可編程開關改變陣列的拓撲結構和互連方式，即經(jīng)程序重新配置陣列結構，以適應新的算法。美國Purdue大學的可重構高度并行計算機CHiP就是典型的例子。,第二種方法是改善處理單元的結構，增強處理

17、單元的功能。如卡內基-梅隆大學的WARP計算機的每個處理單元都有自己的程序存儲器和微操作控制部分，程序存儲器裝的都是同一組微程序。這樣就可以根據(jù)需要，用軟件把不同的算法映像到固定的陣列結構上。依賴于面向并行運算所采用的程序語言、操作系統(tǒng)、編譯程序和軟件開發(fā)工具的設計，WARP機可用于信號、圖像和視覺處理，具有較好的通用性和靈活性。,第三種方法是探討與問題大小無關的脈動處理方法，尋求發(fā)展適合一類計算問題的通用算法和相應的設置方案。比如VLSI運算系統(tǒng)的分割矩陣算法，使它們能夠解決不同大小規(guī)模的問題。 目前比較誘人的很有前景的一種方法是可重構脈動陣列，它采用現(xiàn)代FPGA（現(xiàn)場可編程門陣列）技術，既

18、可以實現(xiàn)PE單元的結構重構，比如將加法器重構為乘法器，實現(xiàn)矩陣運算的快速轉換；又可以實現(xiàn)陣列拓撲和互連方式的重組。近年來出現(xiàn)的動態(tài)可重構技術，能在計算機工作中重構處理器硬件，更深一步推動了脈動處理機的通用性研究。,6.5 互聯(lián)網(wǎng)絡,6.5.1 靜態(tài)互聯(lián)網(wǎng)絡 6.5.2 動態(tài)互聯(lián)網(wǎng)絡 6.5.3 互聯(lián)網(wǎng)絡的通信問題,6.5 互聯(lián)網(wǎng)絡,互聯(lián)網(wǎng)絡（interconnection network ）是一種由開關元件按照一定的拓撲結構和控制方式構成的網(wǎng)絡，用來實現(xiàn)計算機系統(tǒng)內部多個處理器或多個功能部件之間的相互連接。 互聯(lián)網(wǎng)絡是計算機并行系統(tǒng)的核心組成部分，它確定了點到點及系統(tǒng)整體的傳輸帶寬，很大程度上

19、影響系統(tǒng)的性能和成本。,6.5.1 靜態(tài)互聯(lián)網(wǎng)絡,構成互聯(lián)網(wǎng)絡的基本要素包括網(wǎng)絡拓撲結構、數(shù)據(jù)交換方式和控制方式等 并行計算機系統(tǒng)的互聯(lián)網(wǎng)絡由開關元件和鏈路構成，互聯(lián)網(wǎng)絡在功能部件之間的連接關系稱為互聯(lián)網(wǎng)絡的拓撲結構，它可用有向圖或無向圖來表示。圖中的結點表示開關元件或者功能部件。圖中的邊對應于單向或雙向的通信鏈路。從網(wǎng)絡的某個結點到另一個結點之間的一系列鏈路構成一條傳輸數(shù)據(jù)通路。 互聯(lián)網(wǎng)絡的拓撲結構根據(jù)其連接的時間特性分為靜態(tài)網(wǎng)絡(Static network)和動態(tài)網(wǎng)絡(Dynamic network)兩類。,1. 描述靜態(tài)互聯(lián)網(wǎng)絡的參數(shù),靜態(tài)網(wǎng)絡由點到點直接相連而成，這種連結方式在程序執(zhí)

20、行過程中不會改變。結點包括1個功能部件和連接網(wǎng)絡的開關元件。結點之間的鏈路無源，不能重構。不直接相連結點之間的通信需要通過中間結點中轉。,描述靜態(tài)互聯(lián)網(wǎng)絡的參數(shù),（1）結點度：與結點相連接的邊（鏈路或通道）數(shù)，表示節(jié)點所需要的I/O端口數(shù)。一個網(wǎng)絡的度是這個網(wǎng)絡中各結點的度的最大值。結點度反映了網(wǎng)絡中結點之間的連接能力。 結點度 = 入度 + 出度 其中入度是進入結點的通道數(shù)，出度是從結點出來的通道數(shù)。 （2）距離：網(wǎng)絡中兩個結點之間的拓撲距離用這兩個結點之間相連的最少邊數(shù)表示。,描述靜態(tài)互聯(lián)網(wǎng)絡的參數(shù),（3）網(wǎng)絡直徑：網(wǎng)絡中任意兩個結點間距離的最大值，即最遠兩個結點之間的距離。 （4）網(wǎng)絡規(guī)

21、模：指網(wǎng)絡中的結點數(shù)，表示該網(wǎng)絡功能連結部件的多少。 （5）帶寬總和：指網(wǎng)絡中各鏈路的傳輸帶寬的總和，它代表了網(wǎng)絡在理想狀況下的傳輸能力，即每個結點的處理器同時與其它直接連接的結點進行通信時的網(wǎng)絡傳輸能力。 （6）對分(bisection)帶寬：將具有偶數(shù)個結點的互聯(lián)網(wǎng)絡分成相等的兩半時，對處在分界線上的鏈路帶寬求和，并求各種劃分方式下這個值的最小值。,2. 靜態(tài)互聯(lián)網(wǎng)絡的拓撲結構,靜態(tài)網(wǎng)絡的拓撲結構包括總線、環(huán)、二維網(wǎng)格和超立方體網(wǎng)絡等。,（1）總線 ：,（2）環(huán) ：,（3）二維網(wǎng)格型網(wǎng)絡 ：,（4）超立方體和帶環(huán)立方體網(wǎng)絡 ：,3. 選擇靜態(tài)互聯(lián)網(wǎng)絡的基本要求, 網(wǎng)絡的度要小，而且每個結點

22、的度最好相等，并與網(wǎng)絡中結點的數(shù)量無關。減少網(wǎng)絡的度可以降低結點的成本。 網(wǎng)絡直徑要小，并且當結點數(shù)增加時，網(wǎng)絡直徑增加的越少越好，以減少結點間通信引起的延時和系統(tǒng)開銷。網(wǎng)絡直徑和網(wǎng)絡的度相互關聯(lián)，二者之間需要有一個權衡。 網(wǎng)絡的對稱性要好。對稱的網(wǎng)絡使各結點之間以均勻分布的概率進行通信時，通過每個結點和每條鏈路的信息流量也是均勻的，以達到信息流量的均勻分布。避免了某些鏈路出現(xiàn)因為流量集中而超過鏈路的傳輸帶寬從而引起阻塞的現(xiàn)象。而且對稱性網(wǎng)絡實現(xiàn)和編程都較容易。,3. 選擇靜態(tài)互聯(lián)網(wǎng)絡的基本要求, 尋徑方便。網(wǎng)絡的結構要便于對各結點進行合理編址，以便實現(xiàn)高效的尋徑算法。通常一維網(wǎng)絡的結點采用一

23、維編址，多維網(wǎng)絡的結點則采用多維編址。為了實現(xiàn)網(wǎng)絡尋徑的方便，還要求網(wǎng)絡的結構具有規(guī)整性。 具有較高路徑冗余度，使系統(tǒng)在某些結點或鏈路出現(xiàn)故障時仍能繼續(xù)工作，從而滿足容錯性要求。通常對分帶寬小，意味著網(wǎng)絡中兩個結點之間可以選擇的連接通路就少。 伸縮性好。即要求網(wǎng)絡結點數(shù)能夠方便地增加或減少，特別是能夠構成結點數(shù)量很大的網(wǎng)絡。,例6.1 用度和直徑的乘積作為性能指標，分析環(huán)、二維網(wǎng)格和n維立方體這三種靜態(tài)網(wǎng)絡在結點數(shù)為4、16、64、256、1024和4096時的性能指標，指出那一種網(wǎng)絡是最好的拓撲結構。,解：顯然，度和直徑的乘積越小越好。 對環(huán)形網(wǎng)絡：直徑為N/2，度為2，度和直徑的乘積為N；

24、 對nn的二維網(wǎng)格：度為4（n2時），直徑為2(n-1)，度和直徑的乘積為8(n-1)； 對由N = 2n個結點構成的n-立方體結構：直徑為n，結點度為n，度和直徑的乘積為n2。,對題給的結點數(shù)N，三種網(wǎng)絡的度和直徑的乘積如表6-1所列。從表中可知，多維立方體網(wǎng)絡的度和直徑的乘積最小，應是最好的拓撲結構。,6.5.2 動態(tài)互聯(lián)網(wǎng)絡,簡單的動態(tài)互聯(lián)網(wǎng)絡的模型是一個具有N個輸入端和N個輸出端的開關網(wǎng)絡，網(wǎng)絡實現(xiàn)輸入端口到輸出端口的一對一的映像，其中每個輸入端是一個1到M的分路器，而每個輸出端是一個M到1的多路選擇器(1MN)。動態(tài)網(wǎng)絡的輸入端到輸出端有各種不同的連接方式，輸入端到輸出端之間的每一條

25、線路都按某種置換函數(shù)(又稱互聯(lián)函數(shù))進行連接，M條連接線路實現(xiàn)M個不同的置換函數(shù)。,1. 置換函數(shù),置換函數(shù)就是表示互聯(lián)網(wǎng)絡的出端號和入端號的一一對應關系。即：存在置換函數(shù)f，在它的作用下，輸入i應與輸出f(i)相連，0iN-1。每種互聯(lián)網(wǎng)絡可用一組置換函數(shù)來描述。 置換函數(shù)的表示有兩種方法。,（1）函數(shù)表示法,設x表示輸入端變量，則置換函數(shù)f(x)表示輸出端變量。x常用二進制形式來表示，寫成xn-1xn-2x1x0，置換函數(shù)則對應地表示為f(xn-1xn-2x1x0)，因此置換函數(shù)表示了二者之間在二進制編碼上的函數(shù)規(guī)律。,（2）輸入輸出對應表示法,如把置換函數(shù)表示為： 0 1 N-1 f(0

26、) f(1) f(N-1) 即，0變換為f(0)，, i變換為f(i)。 常用到的置換函數(shù)有：恒等置換、交換置換、方體置換、均勻洗牌置換、蝶式置換、位序顛倒置換、移數(shù)置換、加減2i置換等,（1）恒等置換,恒等置換是相同編號的輸入端和輸出端一一對應互連所實現(xiàn)的置換。恒等函數(shù)表達為：,（2）交換置換,交換置換是實現(xiàn)二進制地址編號中的第0位位值不同的輸入端和輸出端之間的連接。交換置換函數(shù)表達為：,（3）方體置換,方體置換是實現(xiàn)二進制地址編號中的第k位位值不同的輸入端和輸出端之間的連接。方體置換函數(shù)表達為： 一般它應有C0、C1、Cn-1等n個方體置換，以n=8為例，有：,（4）均勻洗牌置換,均勻洗牌

27、(Shuffle-Exchange)置換是將輸入端分成數(shù)目相同的兩半，前一半和后一半按序一個隔一個地從頭至尾依次與輸出端相連。其函數(shù)關系可表示為： 洗牌變換是將輸入端二進制地址循環(huán)左移一位即得到對應的輸出端二進制地址。,（4）均勻洗牌置換,第k個子洗牌：即最低k位循環(huán)左移一位。 第k個超洗牌：即最高k-1位循環(huán)左移一位。,逆均勻洗牌,是均勻洗牌的逆函數(shù)。其函數(shù)表達式為： 這說明逆均勻洗牌是將輸入端二進制地址循環(huán)右移一位即得到對應的輸出端二進制地址。,逆均勻洗牌,均勻洗牌與逆均勻洗牌是兩種十分有用的置換函數(shù)，以它們?yōu)榇淼逆溌放c以交換置換為代表的開關多級組合起來可構成網(wǎng)和逆網(wǎng)。洗牌函數(shù)在實現(xiàn)多項

28、式求值、矩陣轉置和FFT等并行計算及并行排序等方面得到了廣泛應用。,2. 交叉開關,一個mn的開關模塊具有m個輸入和n個輸出。開關模塊的每個輸入可與一個或多個輸出相連，容許一對一和一對多映射，但不容許多對一映射，因為輸出端將發(fā)生沖突。 只容許一對一映射的n個輸入n個輸出的開關單元，記做nn的交叉開關，其中，n是2的整數(shù)倍。常見的有2 2、 4 4、8 8等。一般nn交叉開關可實現(xiàn)n!種置換。,2. 交叉開關,交叉開關(crossbar)是一種單個結點的互聯(lián)網(wǎng)絡，采用無阻塞的開關網(wǎng)絡實現(xiàn)輸入端到輸出端的連接。但是在數(shù)據(jù)傳遞過程中仍然會有端口沖突的情況，因為可能有多個輸入端的數(shù)據(jù)分組轉發(fā)到同一個輸

29、出端。 在消息傳遞型的互聯(lián)網(wǎng)絡中，為解決端口沖突都設有分組緩存。分組緩存可以放在網(wǎng)絡的端口處，也可以放在交叉開關內部。根據(jù)分組緩存和交叉開關的連接關系，端口處的分組緩存可以分為輸入隊列和輸出隊列兩種排隊方式,2. 交叉開關,為了解決輸入隊列中數(shù)據(jù)分組之間的端口沖突現(xiàn)象，對于高速互聯(lián)網(wǎng)絡系統(tǒng)，常采用虛擬輸出隊列（VOQ）方式，即在輸入隊列中對不同去向的數(shù)據(jù)分組進行分類，分別用不同的隊列安排這些數(shù)據(jù)分組 輸出隊列方式和輸入隊列方式可以結合起來構成輸入與交叉開關隊列(CICQ)，并通過某種調度算法解決輸出端的沖突。,3. 多級網(wǎng)絡,交叉開關是一種單級互聯(lián)網(wǎng)絡，輸入端的數(shù)據(jù)經(jīng)過一個開關元件就被輸出。這

30、種網(wǎng)絡的設備量較大，解決的辦法是采用多級網(wǎng)絡，即用多個開關元件構成多級的開關陣列，降低互聯(lián)網(wǎng)絡的成本。在控制信號作用下，多級動態(tài)互聯(lián)網(wǎng)絡可以動態(tài)改變其互連函數(shù)。多級網(wǎng)絡的結構具有開關元件、級間互連模式和控制方式三要素。其中開關元件通常是一個端口數(shù)量較少的交叉開關，級間互連模式（InterStage Connection）就是一個開關級的輸出端與下一個開關級的輸入端之間的一個映像，即置換函數(shù)。不同的連接模式可以構成多種不同的多級網(wǎng)絡?？刂品绞揭话阌屑壙刂?、單元控制和部分級控制三種。 常用的多級動態(tài)互聯(lián)網(wǎng)絡有網(wǎng)、STARAN網(wǎng)、Delta網(wǎng)等。,6.5.3 互聯(lián)網(wǎng)絡的通信問題,互連網(wǎng)絡用來在多計算

31、機系統(tǒng)的處理結點之間傳遞消息?；ミB網(wǎng)絡的通信問題主要由網(wǎng)絡拓撲、尋徑算法和流控制進行描述。衡量互連網(wǎng)絡性能有兩個重要指標：傳輸時延（Transmission Latency）和吞吐量（Throughput）。,1. 傳輸時延與吞吐量,對一個消息來說，傳輸時延是指：從它在源結點進行發(fā)送初始化，到它在目的結點完整的被接收所耗費的時間。 對一個網(wǎng)絡來說，傳輸時延是指：在一定條件下發(fā)送消息的平均時延。 傳輸時延可用公式來表達： 其中，Ts稱為建立時延，Tn稱為網(wǎng)絡時延，Tb稱為阻塞時延。,1. 傳輸時延與吞吐量,建立時延Ts：一個消息在源結點和目的結點上裝配和分解、從存儲器拷貝到通信緩沖區(qū)以及正確性驗

32、證等所耗費的時間。它和機器本身的硬件、軟件技術有關。 網(wǎng)絡時延Tn：消息頭部從源結點進入網(wǎng)絡到消息的尾部到達目的結點的時間間隔。 阻塞時延Tb：消息傳遞過程中其它所有可能的時延（主要原因是資源沖突）。 所謂網(wǎng)絡的吞吐量，是指單位時間內網(wǎng)絡所能傳輸?shù)南?shù)目或長度。,2. 互聯(lián)網(wǎng)絡的尋徑方式和尋徑算法,互聯(lián)網(wǎng)絡的尋徑算法決定發(fā)送一個消息到其目的地所經(jīng)過的路徑。 這里所謂消息（Message），是指在多計算機系統(tǒng)的處理接點之間傳遞包含數(shù)據(jù)和同步消息的信息包。它是一種邏輯單位，可由任意數(shù)量的包構成。 包（Packet）是消息傳送的最小單位，包由片組成，一般含有頭片、若干數(shù)據(jù)片、順序號和尾片。包的長度

33、隨協(xié)議不同而有所區(qū)別，常為64-512位。片（Flit）是信息的基本單位，其長度固定，一般為8位。消息、包和片之間的相互關系如圖6-22所示。,2. 互聯(lián)網(wǎng)絡的尋徑方式和尋徑算法,通常在互聯(lián)網(wǎng)絡中，消息從結點A到結點B可以經(jīng)過幾條不同的路徑。尋徑算法就是要尋找從所發(fā)送的消息的源結點到目的結點的最短路徑或最適合的路徑。這種路徑的選擇可能一開始即有確定性算法，它只依賴于它所發(fā)送的消息的源結點和目的結點，也可能在信息行進中根據(jù)具體情況選擇合適的路徑。 有四種尋徑方式，即存儲轉發(fā)、虛擬直通、線路交換和Wormhole交換。,（1）存儲轉發(fā)（Store-and-Forward）,當一個消息到達中間結點A

34、時，A把整個消息放入其通信緩沖器中，然后在尋徑算法的控制下選擇下一個相鄰結點B，當從A到B的通道空閑并且B的通信緩沖器可用時，把消息從A發(fā)向B。 這種方式雖然簡單，但由于每個結點必須對整個消息進行緩沖，需要的緩沖器較大。而且網(wǎng)絡時延與發(fā)送消息所經(jīng)歷的結點數(shù)成正比，對結點數(shù)較多的網(wǎng)絡不利。,（2）虛擬直通（Virtual cut through）,采用這種方式，中間結點沒有必要等到整個消息全部被緩沖后再作出路由選擇。只要消息的目的信息域可用后，就可以作出路由選擇。但是當通向下一結點的通道忙或結點的緩沖器非空閑時，必須把整個消息緩沖起來，這時的處理和存儲轉發(fā)一樣。,（3）線路交換（Circuit

35、Switching）,在傳遞一個消息之前，就為它建立一條從源結點到目的結點的物理通道。在傳遞的全部過程中，線路的每一段都被占用，當消息的尾部經(jīng)過網(wǎng)絡后，整條物理鏈路才被釋放。這種方式雖然能保障消息傳遞過程中不會遇到?jīng)_突和阻塞，但由于物理通道不能共享，在傳輸過程中物理通道一直被占用，因而會影響或阻塞其它消息傳送，同時不能利用消息已經(jīng)過的通道資源，資源利用率低。此法適用于特別重要的消息傳遞。,（4）Wormhole交換（Wormhole Switching),這種方式首先把一個消息分成許多片，消息的頭片包含了這個消息的所有尋徑信息。尾片是一個其最后包含了消息結束符的片。中間的片均為數(shù)據(jù)片。片是最小

36、信息單位。每個結點上只需要緩沖一個片就能滿足要求。用一個頭片直接開辟一條從輸入鏈路到輸出鏈路的路徑的方法來進行操作。每個消息中的片以流水的方式在網(wǎng)絡中向前“蠕動”。每個片相當于Worm的一個節(jié)，“蠕動”以節(jié)為單位順序地向前爬行。 當消息的頭片到達一個結點A的尋徑器后，尋徑器根據(jù)頭片的尋徑信息立即做出路由選擇：, 如果所選擇的通道空閑而且所選擇的結點B的通信緩沖器可用，那么這個頭片就不必等待，直接通過結點A傳向下一個結點B；隨后的其它片跟著相應的向前“蠕動”一步。當消息的尾片向前“蠕動”一步后，它剛才所占用的結點就被放棄了。 如果所選擇的通道非空閑或者所選擇的結點的通信緩沖器非可用，那么這個頭片

37、就必須在此結點的通信緩沖器中等待，直到上述兩者都可用為止；其它片也在原來的結點上等待。此時，被阻塞的消息不從網(wǎng)絡中移去，片不放棄它所占有的結點和通道。這是Wormhole技術和其它流控制技術都不同的地方。,（4）Wormhole交換（Wormhole Switching),Wormhole交換的優(yōu)點是： 每個結點的緩沖器的需求量小，易于用VLSI實現(xiàn)。 較低的網(wǎng)絡傳輸延遲。 通道共享性好、利用率高。 易于實現(xiàn)一對多播送和廣播機制，允許尋徑器復制消息包的片并把它們從多個輸出通道輸出。,（4）Wormhole交換（Wormhole Switching),3. 互聯(lián)網(wǎng)絡的流控制,互聯(lián)網(wǎng)絡的流控制是指

38、當一個消息在網(wǎng)絡中沿著某條路徑傳送時，互連網(wǎng)絡如何來為它分配通道和緩沖器，并建立虛擬通道和防止死鎖。 虛擬通道是兩個結點間的邏輯鏈。它由源結點的片緩沖區(qū)、結點間的物理通道和接收結點的緩沖區(qū)組成。物理通道由所有虛擬通道分時共享。 死鎖往往發(fā)生在多條消息傳送過程中，因鏈路堵塞而相互等待的情況。 死鎖的解決辦法常利用虛擬通道，將通道相關圖中的環(huán)路變成螺旋線來避免死鎖。,6.6 超標量流水線和超級流水線,6.6.1 超標量處理機 6.6.2 超流水線處理機 6.6.3 超標量超流水線處理機,6.6.1 超標量處理機,1. 單發(fā)射和多發(fā)射 典型的標量流水線處理機把一條指令的執(zhí)行過程分解為取指令（IF）、

39、指令譯碼/讀寄存器操作數(shù)（ID）、執(zhí)行運算/形成有效地址（EX）、訪存/轉移完成（MEM）和寫回（WB）等5級流水線，每一級的執(zhí)行時間為一個基本時鐘周期。讓一條指令從譯碼段ID流動到執(zhí)行段EX的操作通常稱為發(fā)射指令。 單發(fā)射是指處理機在一個時鐘周期內只從存儲器取出一條指令進入指令流水線處理，5.2節(jié)介紹的就是單發(fā)射處理機。它的設計目標是每個時鐘周期平均執(zhí)行一條指令，即它的指令并行度ILP期望值是1。實際上由于數(shù)據(jù)相關、控制相關及資源沖突等原因，ILP只能接近于1。,在一個時鐘周期內能夠同時發(fā)射多條指令的處理機稱為超標量處理機。為了能夠支持同時發(fā)射多條指令，超標量處理機必須具有至少兩條及以上能夠

40、同時工作的指令流水線。具有多條能同時工作的流水線是所謂超標量的前提。 超標量處理機的典型結構是有多個操作部件，較大的寄存器堆和高速緩沖存儲器。一般擁有整數(shù)流水線、浮點數(shù)流水線、圖形處理流水線、存儲操作流水線等多條流水線。所有的指令首先要經(jīng)過指令部件中的若干個流水段，例如先完成取指令和指令譯碼，然后依據(jù)指令具體執(zhí)行內容而安排進入相應的操作部件。,在超標量處理機中同樣面臨著預測分析和處理指令之間的功能部件沖突、數(shù)據(jù)相關和控制相關問題。主要采用的技術有： （1）寄存器重命名技術 這種技術可以對所有寄存器進行重命名以及用虛寄存器以避免WAW和WAR冒險，即預測到要發(fā)射的指令中存在數(shù)據(jù)相關，就使用虛擬寄

41、存器組消除寄存器訪問中的名字相關。 （2）先行指令窗口技術 當出現(xiàn)數(shù)據(jù)相關、控制相關或功能部件沖突時，本次沒有能夠發(fā)射出去的指令必須保存下來，以便在下一個時鐘周期再發(fā)射。為了提高功能部件的利用率，往往要設置先行指令窗口。在該窗口中保存暫時還沒有送到操作部件中去執(zhí)行的指令。,（3）轉移預測技術 一般普遍采用基于Tournament算法的轉移預測器，這種方法的預測緩存包含8k個入口，每個入口由一個相關2-bit預測器（由轉移地址和全局地址的異或進行索引），不相關2-bit預測器（由轉移地址進行索引）及一個選擇器組成。 （4）通過Tomasulo算法實現(xiàn)動態(tài)存儲器地址的二義性消除。 （5）設置多個交

42、叉開關，通過控制開關通路，把幾個指令譯碼器的輸出分別送到多個操作部件中去執(zhí)行。因此，超標量處理機的控制邏輯比較復雜。,（6）要是指令流水線在一個周期內同時發(fā)射更多的指令，存儲器就需要在一個周期內為指令流水線提供多條指令。為此，可采用多體并行訪問存儲器或者單體多字存儲器。當然這需要優(yōu)化編譯器的配合。 如果一臺超標量處理機每個時鐘周期發(fā)射m條指令，則它的指令并行度ILP的期望值是m，實際上1ILPm。,IBM Power 5是目前較為先進的超標量處理機，其每周期最多發(fā)射4條指令，啟動執(zhí)行至多6條指令（對指令類型有嚴格限制，如最多2條load-store指令）；擁有大量的重命名寄存器，（88個定點寄

43、存器和88個浮點寄存器，支持超過200條正在執(zhí)行的指令，其中允許多達32條load指令和32條store指令）；應用了亂序執(zhí)行技術，其強大的轉移預測器，能夠動態(tài)消除存儲器二義性。,2. 超標量處理機的性能,在一臺每個時鐘周期發(fā)射m條指令的超標量處理機上執(zhí)行，所需要的時間為： 其中，第一項是第一批m條指令同時通過m條指令流水線所需要的執(zhí)行時間kt；第二項是其余N-m條指令分為(N-m)/m批通過指令流水線的時間，每隔t就有一批m條指令流出。,2. 超標量處理機的性能,因此，超標量處理機相對于單流水線普通標量處理機的加速比為： 當N時，在沒有相關和資源沖突的理想情況下，超標量處理機的最大加速比為

44、S(m)max=m,6.6.2 超流水線處理機,在一個基本時鐘周期內能夠發(fā)射多條指令的處理機稱為超流水線處理機，也有資料將流水線級數(shù)在8級及以上的流水線處理機稱為超流水線處理機。 超流水線處理機和超標量處理機雖然都是以單流水線處理機為基礎，但二者有很大不同，前者進一步提高時間重疊程度，以提高時間并行性來提高指令的平均執(zhí)行速度；而后者采用資源重復的途徑，以提高空間并行性來提高指令的平均執(zhí)行速度。,在一個時鐘周期內能夠同時發(fā)射多條指令的處理機稱為超標量處理機。為了能夠支持同時發(fā)射多條指令，超標量處理機必須具有至少兩條及以上能夠同時工作的指令流水線。具有多條能同時工作的流水線是所謂超標量的前提。 超

45、標量處理機的典型結構是有多個操作部件，較大的寄存器堆和高速緩沖存儲器。一般擁有整數(shù)流水線、浮點數(shù)流水線、圖形處理流水線、存儲操作流水線等多條流水線。所有的指令首先要經(jīng)過指令部件中的若干個流水段，例如先完成取指令和指令譯碼，然后依據(jù)指令具體執(zhí)行內容而安排進入相應的操作部件。,一臺并行度ILP為n的超流水線處理機，它在一個時間周期內能夠發(fā)射n條指令，但這n條指令不是同時發(fā)射的，而是每隔1/n個時鐘周期發(fā)射一條指令，實際上超流水線處理機的流水線周期為1/n個時鐘周期。因此，只要器件技術給以配合，可將處理器工作節(jié)奏加快，工作頻率將可能提升n倍?，F(xiàn)代Pentium 4的一條流水線多達31級超流水線，其主

46、頻高達3.8GHz。,超流水線處理機性能的簡單分析,在一臺n級超流水線處理機上，執(zhí)行N條沒有相關和資源沖突的指令所需要的時間為： 其中，k是指令流水線的功能段數(shù)，或為一條指令所需的時鐘周期數(shù)。流水線的實際級數(shù)為kn。t是一個周期的長度。式中的第一項是第一條指令通過指令流水線所需時間kt；第二項是其余N-1條指令分別同它前面一條指令相隔t/n連續(xù)流入流水線執(zhí)行完成所需的時間。,超流水線處理機性能的簡單分析,單流水線普通標量處理機連續(xù)執(zhí)行N條指令所用的時間為T(1)=(k+N-1)t，因此，超流水線處理機相對于單流水線普通標量處理機的加速比為： 當n時，在沒有相關和資源沖突的理想情況下，超流水線處

47、理機的最大加速比為 S(n)max=n,6.6.3 超標量超流水線處理機,為了進一步提高處理機的指令并行度，可以將超標量技術和超流水線技術結合起來構成超標量超流水線處理機(super pipelining super scalar processor) 例如，DEC公司的Alpha 21164就是一個典型的超標量超流水線處理機。它有3條不同的流水線：定點流水線、浮點流水線、存儲操作流水線。所有的指令首先要經(jīng)過指令部件中的4個流水段。定點執(zhí)行部件有3個流水段，因此定點指令需要經(jīng)過7個流水段。浮點執(zhí)行部件有5個流水段，因而浮點指令需要經(jīng)過9個流水段。存儲操作則劃分為12個流水段。這3條流水線的平均

48、級數(shù)kn=8級，每條流水線在每個時鐘周期內可同時發(fā)射2條指令。,超標量超流水線處理機性能的簡單分析,在一臺能同時發(fā)射m條指令，且指令流水線為kn級的超標量超流水線處理機上，連續(xù)執(zhí)行n條沒有相關和資源沖突的指令所需要的時間為：,超標量超流水線處理機性能的簡單分析,因此，超標量超流水線處理機相對于單流水線普通標量處理機的加速比為： 當N時，在沒有相關和資源沖突的理想情況下，超標量超流水線處理機的最大加速比為 S(m,n)max=mn,結合圖6-12可得出以下結論：,（1）超標量處理機的相對性能最高，其次是超標量超流水線處理機，超流水線處理機的相對性能最低。主要有三方面原因：超標量處理機在每個時鐘周

49、期的開始就同時發(fā)射多條指令，而超流水線處理機則要把一個時鐘周期平均分成多個流水線周期，每個流水線周期發(fā)射一條指令，指令之間的啟動延時比超標量處理機大；條件轉移造成的損失，超流水線處理機比超標量處理機大；在指令執(zhí)行過程中的每一個功能段，超標量處理機都設置有多個相同的操作部件，而超流水線處理機只是把同一條指令執(zhí)行部件分解為多個流水級。因此，超標量處理機指令執(zhí)行部件的沖突比超流水線處理機小。,（2）當橫坐標表示的設計指令級并行度較小時，處理機實際指令并行度提高較快。但當設計指令級并行度進一步增加時，處理機實際指令并行度提高變緩，且越來越慢。因此實際設計超標量、超流水線或超標量超流水線處理機的指令并行

50、度應適當，否則花費大量硬件代價，而可能得不到指令并行度的期望值。 （3）一個特定程序由于受到本身的數(shù)據(jù)相關、控制相關等限制，其指令并行度的最大值是確定的。這個最大值由程序自身的語義決定，與這個程序運行于哪一種處理機無關。因此圖中的三條曲線對于某一特定程序，會收攏于同一個點上。當然對不同程序，其收攏點位置是不同的。,并非流水線級數(shù)越多會越好，也并非處理機工作頻率越高越好。例如Pentium4的深度流水線和極高的主頻并沒有帶來所期望的高性能和高效率，迫使Intel不得不放棄從這一途徑來提高處理器性能，轉而開發(fā)多核處理器和超線程技術，開創(chuàng)了處理器的多核時代和深化了線程級并行技術，使處理機性能邁上一個

51、新的臺階。,6.7 超長指令字處理機,超長指令字VLIW (Very Long Instruction Word)結構是水平微碼和超標量處理兩種技術相結合而產(chǎn)生的，VLIW處理機的機器指令字長度高達數(shù)百位。很多現(xiàn)代處理器都應用了VLIW方式，如Intel和HP的IA-64結構、IBM的Tree-VLIW結構等。,超長指令字處理機的工作原理,超長指令字處理機的工作原理,VLIW處理機的一個超長指令字包含多個操作字段，每個字段可與相應的功能部件對應。這些操作字段包括可并行執(zhí)行的多個運算器控制指令字段、若干個訪存儲器控制指令字段和其它操作控制字段。各運算部件和共享的大容量寄存器堆直接相連，以便提供運

52、算所需要的操作數(shù)或存放運算結果，對數(shù)據(jù)的讀寫操作也可以通過存儲器指令字段對指定存儲模塊中的存儲單元進行。結合網(wǎng)則提供了各個部件之間的數(shù)據(jù)鏈路。,VLIW的實現(xiàn)是由編譯器將多條可以同時發(fā)送的標準指令捆綁在一條超長指令字中，并基于多個可以同時執(zhí)行的功能部件的支持，所以處理器在一個時鐘周期內可以發(fā)射超長指令字中的多條指令，實現(xiàn)多條指令的并行執(zhí)行。,VLIW方式具有下述主要特征： （1）依靠編譯組裝超長指令。VLIW方式是在編譯時發(fā)現(xiàn)和利用程序的并行運算可能性。編譯從原程序中抽出可能的并行運算組裝成一條超長指令，可以得到接近VLIW處理機中并行運算器數(shù)目的并行度。但VLIW方式的并行度依賴于編譯的并行化能力及程序本身的并行化程度。 （2）硬件結構簡單。由于指令的并行調度由編譯完成，運行時無須檢驗，因此VLIW方式簡化了控制電路，使得它的結構簡單，芯片制造成本低，能耗小。 （