系統(tǒng)結(jié)構(gòu)重點

1.1.1計算機(jī)系統(tǒng)的層次結(jié)構(gòu)微程序機(jī)器級傳統(tǒng)機(jī)器語言機(jī)器級操作系統(tǒng)機(jī)器級匯編語言機(jī)器級高級語言機(jī)器級應(yīng)用語言機(jī)器級

從計算機(jī)語言的角度，可將通用計算機(jī)系統(tǒng)劃分成多級層次結(jié)構(gòu)，每一層以一種不同的語言為特征。

按由低層到高層的順序，各層分別是：1.低層機(jī)器級對高層機(jī)器級的支持

各層機(jī)器級語言的功能是依靠下一層機(jī)器級的支持才能實現(xiàn)的，而且，這種支持要滿足透明性要求。

透明性：從計算機(jī)系統(tǒng)的某一層的使用者角度看，只需通過該層的語言就可以使用機(jī)器，而不必關(guān)心其下層的機(jī)器級是如何工作和如何實現(xiàn)對上層的支持的。

計算機(jī)系統(tǒng)的“透明”是看不到的意思，即對某一層的使用者來說，他看不到該層以下各層的機(jī)器屬性。1.發(fā)展計算機(jī)系統(tǒng)并行性的技術(shù)途徑

可以通過3類技術(shù)途徑來提高計算機(jī)系統(tǒng)的并行性，這就是時間重疊、資源重復(fù)和資源共享。

時間重疊是在并行性概念中引入時間因素，讓多個處理過程在處理時間上錯開，輪流重疊地使用同一套硬件設(shè)備的各個部件，提高多個處理過程的并發(fā)性。

資源重復(fù)是在并行性概念中引入空間因素，通過重復(fù)設(shè)置硬件資源分別同時用于多個處理過程，實現(xiàn)多個處理過程的同時性。

資源共享是利用軟件方法讓多個任務(wù)按一定順序輪流使用一套資源，通過提高系統(tǒng)資源利用率來提高系統(tǒng)的性能和效率。

3.計算機(jī)系統(tǒng)結(jié)構(gòu)的分類

指令流：是指機(jī)器執(zhí)行的指令序列。數(shù)據(jù)流：是指由指令流調(diào)用的數(shù)據(jù)序列，包括輸入數(shù)據(jù)和中間結(jié)果。多倍性:是指在系統(tǒng)最受限制的部件上，同時處于同一執(zhí)行階段的指令或數(shù)據(jù)的最大可能個數(shù)。Flynn按指令流和數(shù)據(jù)流的多倍性對計算機(jī)系統(tǒng)結(jié)構(gòu)進(jìn)行分類:單指令流單數(shù)據(jù)流（SISD）體系結(jié)構(gòu)

單指令流多數(shù)據(jù)流（SIMD）體系結(jié)構(gòu)

多指令流單數(shù)據(jù)流（MISD）體系結(jié)構(gòu)

多指令流多數(shù)據(jù)流（MIMD）體系結(jié)構(gòu)浮點數(shù)的機(jī)器字的格式為：

mfefem1位1位q位p位

其中mf為尾數(shù)符號位，ef為階碼的符號位。

mfefe(q)m(p)浮點數(shù)在數(shù)據(jù)存儲單元中的存放方式mf:尾數(shù)符號ef:階碼符號e:階碼長度m:尾數(shù)的值。尾數(shù)用原碼、純小數(shù)表示，階碼用移碼、整數(shù)表示。浮點數(shù)的表示范圍定義為：P=23,q=7,rm=re=2,浮點數(shù)N的表示范圍：絕對值不能無窮接近0值，即存在截止區(qū)(dead-zone),也叫下溢區(qū)十進(jìn)制數(shù)0.1的16位多種表示方式尾數(shù)的值階符階碼尾符尾數(shù)rm=2010101100,1100,1100,1100rm=40111001,10,01,10,01,10,01,10rm=801110110,011,001,100,110,0rm=16100000001,1001,1001,1001(階碼的基)階碼位數(shù)+階碼值(-8~7)=階碼的移碼值(0~15)0.1(10)=0.1100110011001100(2)×2-3=0.121212(4)×4-1=0.63146314(8)×8-1=0.19999(16)×160浮點數(shù)的表數(shù)(representation)精度階碼(階碼的移碼),q=1,rm=21(1.1)0(1.0)-1(0.1)-2(0.0)尾數(shù)p=2rm=20.75(0.11)3/2?3/83/160.5(0.10)1??1/8-0.5(1.10)-1-1/2-1/4-1/8-0.75(1.11)-3/2-3/4-3/8-3/16(階碼的基)階碼位數(shù)+階碼值(-2~1)=階碼的移碼值(0~3)若有2個浮點數(shù)a1=1/2,b1=3/4,a1+b1=5/4，不在這個浮點數(shù)集里面，因此必須用靠近這個數(shù)的值表示，如1或者3/2。由此產(chǎn)生表數(shù)誤差。階碼尾數(shù)由于因此，能表示的絕對值最大的浮點可近似為：假設(shè)有2種浮點數(shù)表示方法F1和F2：F1:尾數(shù)的基為2，階碼的長度為q1；F2:尾數(shù)的基為，階碼的長度為q2，并設(shè)：；兩種浮點數(shù)表示方式的表示范圍為：尾數(shù)的基從2增加到，所能表示的階碼最大值就增加倍，而浮點數(shù)的表數(shù)范圍，是根據(jù)其階碼增加以2的指數(shù)增加:q1=7,rm1=2；q2=6,rm2=16；T=2128尾數(shù)的基與表數(shù)范圍2.2.1操作碼優(yōu)化設(shè)計1.操作碼優(yōu)化編碼的方法

定長（等長）編碼哈夫曼編碼擴(kuò)展編碼

操作碼編碼的方法有3種：

定長編碼:是指所有指令的操作碼長度都是相等的。如果需要編碼的操作碼有n個，那么，定長操作碼的位數(shù)最少需要|log2n|位。

使用哈夫曼算法構(gòu)造哈夫曼樹來進(jìn)行編碼。哈夫曼（Huffman）編碼

構(gòu)造哈夫曼樹的方法是：每次從結(jié)點集中選擇出2個頻度最小的結(jié)點，將其合并成頻度為這兩個頻度之和的父結(jié)點，若結(jié)點集不為空集，就將生成的新結(jié)點放到結(jié)點集中，繼續(xù)從這個新的結(jié)點集中選擇出2個頻度最小的結(jié)點生成其父結(jié)點，直至結(jié)點集成為一個空集，就生成了一棵哈夫曼樹。對每個結(jié)點的兩個分支分別用“0”和“1”標(biāo)識，從根結(jié)點到一個葉結(jié)點的路徑（由0和1組成的序列）就是這個葉結(jié)點的哈夫曼編碼。

限定使用少數(shù)幾種碼長，頻度高的碼點用短碼表示，頻度較低的碼點用長碼表示。特別需要指出的是，任何短碼都不能是任何長碼的前綴，即任何短碼都不能是任何長碼的前若干位，否則會造成解碼的不惟一性。因此，需要留下若干個短碼作為長碼的擴(kuò)展標(biāo)志，以便長碼在擴(kuò)展編碼時使用。

擴(kuò)展編碼一種稱為碼長表示法，用短橫線前后的數(shù)字分別表示短碼碼長和長碼碼長。另一種稱為碼點數(shù)表示法，用斜線前后的數(shù)字分別表示短碼碼點個數(shù)和長碼碼點個數(shù)。

擴(kuò)展編碼有2種表示方法：

2.操作碼優(yōu)化編碼的評價方法用平均碼長來評價編碼優(yōu)化的程度，平均碼長為：其中，pi是碼點i的使用頻度；li是碼點i

的編碼長度。也可以用位冗余量來衡量編碼優(yōu)化的程度，位冗余量為

：其中，H稱為信息熵，，表示用二進(jìn)制編碼表示n個碼點時，理論上的最短平均編碼長度。因此，任何實際編碼得出的平均碼長l都有l(wèi)>H，故有0<R<1。

3.2.2線性流水線的性能計算1.吞吐率

流水線的吞吐率是指流水線單位時間輸出結(jié)果的數(shù)量。（1）各段執(zhí)行時間相等的吞吐率若一條k段線性流水線，各段執(zhí)行時間相等，均為，當(dāng)有n個處理對象連續(xù)流入流水線時，流水線的工作過程可用時空圖表示為：nn-1……321S1nn-1……321S2nn-1……321S3nn-1……321S4時間空間

各段執(zhí)行時間均相等的流水線時空圖：

流水線的實際吞吐率為：

最大吞吐率為：最大吞吐率與實際吞葉率的關(guān)系是：只有當(dāng)n>>k時，即連續(xù)輸入流水線的處理對象數(shù)n遠(yuǎn)大于流水線的段數(shù)k時，實際吞吐率TP才接近于最大吞吐率TPmax。

（2）各段執(zhí)行時間不等的吞吐率若一條k段線性流水線，各段執(zhí)行時間,,…,不相等，那么，除第一個對象外，其余(n-1)個對象必須按瓶頸時間間隔max(,,…,)連續(xù)流入流水線。

消除流水線的瓶頸段，以提高流水線吞吐率的方法有兩種：①分離瓶頸段:把流水線中的瓶頸功能段分離成為幾個獨立的子功能段，消除各段執(zhí)行時間的“瓶頸”。②重復(fù)設(shè)置瓶頸段:如果瓶頸功能段由于實現(xiàn)技術(shù)等方面的原因難以分離成幾個獨立的子功能段，那么，可以采用重復(fù)設(shè)置瓶頸段，讓多個瓶頸段并行工作來消除瓶頸段原執(zhí)行時間的“瓶頸”。這兩種方法只要完全消除了“瓶頸”，提高吞吐率的程度是相同的。

2.加速比

流水線的加速比:是指使用順序處理方式處理一批對象所用的時間與流水線使用流水處理方式處理同一批對象所用的時間之比。（1）各段執(zhí)行時間相等的加速比一條各段執(zhí)行時間均為的k段線性流水線，若有n個對象連續(xù)流入，那么，流水線流水處理這n個對象所用的時間為。若順序處理這n個對象，則所用時間為。

實際加速比為:最大加速比為:（2）各段執(zhí)行時間不等的加速比當(dāng)流水線各功能段的執(zhí)行時間不相等時，一條k段線性流水線完成n個連續(xù)輸入的對象的實際加速比為

3.效率

流水線的效率:是指流水線的設(shè)備利用率。它是流水線各段的有效工作時間之和與流水線各段被占用時間（從第一個對象流入至最后一個對象流出）之和的比值。

可以由時空圖直觀地計算出流水線的效率為

（1）各段執(zhí)行時間相等的效率各段執(zhí)行時間相等的流水線效率為：最大效率為：（2）各段執(zhí)行時間不等的效率各段執(zhí)行時間不等的k段線性流水線連續(xù)輸入n個對象的流水線效率為：【例3.4】

有一個5段單功能非線性流水線，每一個功能段的執(zhí)行時間均為。處理對象在流水線中的處理過程由表3.1給出的預(yù)約表描述。預(yù)約表中的記號“

”表示處理對象在指定的時間（單位為）需要由相應(yīng)的段進(jìn)行處理。求流水線的最優(yōu)調(diào)度策略。若按此最優(yōu)調(diào)度策略連續(xù)輸入8個對象，計算流水線的實際吞吐率、加速比和效率。

表3.15段單功能非線性流水線的一種預(yù)約表

S5

S4

S3

S2

S1987654321時間段解按下述步驟先求出最優(yōu)調(diào)度策略，然后求實際吞吐率、加速比和效率。①由預(yù)約表得出禁止表F，禁止表是后續(xù)對象禁止流入流水線的時間間隔的集合。由表3.1給出的預(yù)約表可見，一個對象在1使用段S1后，在9將再次使用段S1。為避免后續(xù)對象同該對象發(fā)生爭用段S1的沖突，后續(xù)對象禁止流入的時間間隔為9-1=8

。同樣，為避免爭用段S2的禁止時間間隔為；為避免爭用段S3的禁止時間間隔為、

、；為避免爭用S4的禁止時間間隔為；為避免爭用S5的禁止時間間隔為。由此，可得出禁止表F={8,4,3,1}。②由禁止表得出初始沖突向量

C0=(10001101)。3-2=17-4=38-4=48-7=15-4=17-6=1③由初始沖突向量得出狀態(tài)有向圖。

初始狀態(tài)為C0=(10001101)，C0有4個后繼狀態(tài)：C1=SHR(2)(C0)∨C0=(00100011)∨(10001101)=(10101111)C2=SHR(5)(C0)∨

C0=(00000100)∨(10001101)=(10001101)=C0C3=SHR(6)(C0)∨

C0=(00000010)∨(10001101)=(10001111)C4=SHR(7)(C0)∨

C0=(00000001)∨(10001101)=(10001101)=C0

C1有2個后繼狀態(tài)：C5=SHR(5)(C1)∨

C0=(10001101)=C0C6=SHR(7)(C1)∨

C0=(10001101)=C0C3有3個后繼狀態(tài)

：

C7=SHR(5)(C3)∨

C0=(10001101)=C0C8=SHR(6)(C3)∨

C0=(10001111)=C3C9=SHR(7)(C3)∨

C0=(10001101)=C0（10001101）（10101111）（10001111）257756657C0C1C3④表3.2圖狀態(tài)有向圖的調(diào)度策略

(2+5)/2=3.55(7)(6)(6,7)(6,5)(5)(2,7)(2,5)平均時間間隔調(diào)度策略(2+7)/2=4.5(6+5)/2=5.5(6+7)/2=6.567⑤計算最優(yōu)調(diào)度策略的流水線吞吐率、加速比和效率。最優(yōu)調(diào)度策略（2,5）的平均時間間隔為3.5，可得出最優(yōu)調(diào)度策略的流水線最大吞吐率為：

TPmax=1/3.5=0.286/

按最優(yōu)調(diào)度策略流水處理8個對象所需時間為由于每一個對象的處理過程所需時間為9，所以，若按順序處理方式處理8個對象，所需時間為

可得出按最優(yōu)調(diào)度策略流水處理n=8個對象時，流水線的實際吞吐率、加速比和效率分別為【例3.6】

有一個5段單功能非線性流水線，每一個功能段的執(zhí)行時間均為，處理對象在流水線中的處理過程由例3.4中的表3.1給出的預(yù)約表描述。（1）求流水線的最優(yōu)調(diào)度策略和最大吞吐率。（2）若按最優(yōu)調(diào)度策略連續(xù)流入6個對象，計算流水線的實際吞吐率、加速比和效率。（3）畫出按最優(yōu)調(diào)度策略連續(xù)流入6個對象的時空圖，并由時空圖計算流水線的實際吞吐率、加速比和效率。

解（1）因為處理對象的預(yù)約表相同，所以，流水線的最優(yōu)調(diào)度策略即例3.4中求得的最優(yōu)調(diào)度策略(2,5)。流水線的最大吞吐率就是最優(yōu)調(diào)度策略的最大吞吐率，有TPmax=1/3.5。

（2）按最優(yōu)調(diào)度策略連續(xù)流入6個對象，流水線的實際吞吐率和加速比分別為:由表3.1給出的預(yù)約表可見，一個處理對象在流水線中被流水線5個段實際處理的時間之和為(2+2+3+2+2)=11，所以，流水線5個段處理6個對象的實際處理時間之和為6×11=66。流水線5個段共被占用的時間之和為5×25=125。因此，流水線的效率為

654635241321S1665544332211S2665565443343221121S3665544332211S4665544332211S52Δt5Δt2Δt5Δt2Δt9Δtt(Δt)例3.6的時空圖

由時空圖得出流水線的實際吞吐率、加速比和效率分別為：

3.4流水線的相關(guān)問題與相關(guān)處理流水線的相關(guān)問題分為局部相關(guān)和全局相關(guān)兩類。局部相關(guān)對程序執(zhí)行過程的影響較小，它僅涉及到相關(guān)指令前后的一條或幾條指令的執(zhí)行。全局相關(guān)是指影響整個程序執(zhí)行方向的相關(guān)，主要是轉(zhuǎn)移類指令和中斷引起的相關(guān)。3.4.1局部相關(guān)及處理

1.順序流動的“先寫后讀”相關(guān)及處理順序流動是指對象從流水線流出的次序同它們流入流水線的次序一樣。如果指令h寫入結(jié)果的目的地址同指令j讀取操作數(shù)的源地址是同一個存儲單元或寄存器，那么，稱這兩條指令有“先寫后讀”的要求。如果當(dāng)指令j到達(dá)讀段時，指令h還沒有到達(dá)寫段完成寫入操作，那么，指令j讀出的數(shù)據(jù)就是錯誤的，這就是“先寫后讀”相關(guān)。解決順序流動的“先寫后讀”相關(guān)的方法是：延遲、異步流動和建立相關(guān)通路。3.4.2全局相關(guān)及處理

由條件轉(zhuǎn)移或程序中斷引起的相關(guān)稱為全局相關(guān)。1.條件轉(zhuǎn)移的處理在遇到條件轉(zhuǎn)移指令時，為了使流水線不“斷流”，通常采用“猜測法”，即在條件轉(zhuǎn)移指令之后，選擇一個分支方向，讓后續(xù)指令進(jìn)入流水線執(zhí)行。假設(shè)在一般程序中條件轉(zhuǎn)移指令所占比例為p，轉(zhuǎn)移成功的概率為q，那么，對于一個由n條指令組成的程序在執(zhí)行過程中，由于條件轉(zhuǎn)移需要額外增加的執(zhí)行時間就是pqn(k-1)。包括條件轉(zhuǎn)移指令在內(nèi)的n條指令的總的執(zhí)行時間是可得出有條件轉(zhuǎn)移影響的流水線的吞吐率為

當(dāng)時，有條件轉(zhuǎn)移影響的流水線的最大吞吐率為由于條件轉(zhuǎn)移指令的影響，流水線吞吐率下降百分比為

由于條件轉(zhuǎn)移指令對流水線的性能影響很大，必須采取措施來減小這種影響?？梢圆扇〉拇胧┲饕幸韵聨追N。（1）延遲轉(zhuǎn)移技術(shù)（2）靜態(tài)轉(zhuǎn)移預(yù)測技術(shù)（3）動態(tài)轉(zhuǎn)移預(yù)測技術(shù)（4）提前形成條件碼2.中斷處理在順序處理方式中，CPU任何時間都只執(zhí)行一條指令，當(dāng)中斷發(fā)生時，被中斷執(zhí)行的那一條指令即是斷點指令，被中斷的指令的現(xiàn)場即是要保護(hù)的中斷現(xiàn)場。在指令流水線中，同時有多條指令被執(zhí)行，每一條指令在流水地執(zhí)行過程中都不斷地改變著現(xiàn)場。對此，有兩種處理方法。

（1）不精確斷點方法不精確斷點方法對中斷的處理是：凡是已經(jīng)進(jìn)入流水線的指令序列的指令都執(zhí)行完成，斷點指令就是該指令序列中最后進(jìn)入流水線的那條指令。實際上，提出中斷請求的指令可能并不是最后那條指令，所以稱其為不精確斷點法。這個方法只確定最后一條指令為斷點指令，只保存這一條指令的現(xiàn)場。（2）精確斷點方法精確斷點方法對中斷的處理是：對于在流水線中同時執(zhí)行的多條指令，由哪一條指令的程序性錯誤或故障發(fā)出的中斷申請，斷點指令就是這條指令。為了實現(xiàn)精確斷點法，需要把斷點指令之前尚在流水線中已完全執(zhí)行和部分執(zhí)行的指令的執(zhí)行結(jié)果都作為現(xiàn)場保存起來，為此，要設(shè)置一定數(shù)量的后援寄存器。3.4.3相關(guān)對流水線性能的影響

流水線處理對象之間的相關(guān)將導(dǎo)致流水線的性能下降。對于有相關(guān)問題的處理對象序列，可以用時空圖來表示流水處理過程和分析相關(guān)對流水線性能的影響。3.5多發(fā)射處理機(jī)及其性能

單發(fā)射是指處理機(jī)在一個時鐘周期（）只從存儲器取出一條指令（IF）、只對一條指令譯碼（ID）、只執(zhí)行一條指令（EX）和只寫回一個運算結(jié)果（WR），因此，平均一個時鐘周期只解釋一條指令。單發(fā)射處理機(jī)的指令級并行度ILP<1。多發(fā)射是指處理機(jī)在一個時鐘周期可發(fā)射多條指令。多發(fā)射處理機(jī)的指令級并行度ILP≥2。屬于多發(fā)射處理機(jī)范疇的處理機(jī)有：超標(biāo)量處理機(jī)、超流水處理機(jī)、超標(biāo)量超流水處理機(jī)和超長指令字處理機(jī)。3.5.1超標(biāo)量處理機(jī)及其性能計算

超標(biāo)量處理機(jī)是在單發(fā)射處理機(jī)的基礎(chǔ)上，采用資源重復(fù)的途徑來發(fā)展指令流水線的并行性，通過重復(fù)設(shè)置硬件資源來提高處理機(jī)的指令級并行度。1.超標(biāo)量處理機(jī)指令流水線的結(jié)構(gòu)

3.5.2超流水處理機(jī)及其性能計算

超流水處理機(jī)是在單發(fā)射處理機(jī)的基礎(chǔ)上，采用時間重疊的途徑來發(fā)展指令流水線的并行性，通過把單發(fā)射的指令流水線各功能段進(jìn)一步細(xì)分來提高處理機(jī)的指令級并行度。指令流水線平均執(zhí)行一條指令所需要的時間稱為流水線周期，單發(fā)射指令流水線的流水線周期就是時鐘周期，超流水指令流水線的流水線周期為/n，在沒有相關(guān)和段資源沖突的理想情況下，超流水處理機(jī)的指令級并行度ILP=n。3.5.5多發(fā)射處理機(jī)的性能比較機(jī)器類型單發(fā)射處理機(jī)超標(biāo)量處理機(jī)超流水處理機(jī)超標(biāo)量超流水處理機(jī)流水線周期1個時鐘周期1個時鐘周期1/n時鐘周期1/n時鐘周期同時發(fā)射指令條數(shù)1條m條1條m條指令發(fā)射等待時間1個時鐘周期1個時鐘周期1/n時鐘周期1/n時鐘周期指令級并行度ILP1mnm×n表3.64種不同類型處理機(jī)的性能比較【例3.12】

在向量流水處理機(jī)上，執(zhí)行下述3條向量指令來計算向量D=A×(B+C)，其中，結(jié)果向量D的元素di=ai×(bi+ci)，i=1，2，…，N。N為向量元素個數(shù)。①V3←存儲器 ；訪存取A送入向量寄存器V3②V2←V0+V1 ；B+C→K③V4←V2*V3 ；K*A→D設(shè)啟動存儲器、啟動乘/加流水線、數(shù)據(jù)打入寄存器各需時，向量加流水線完成一次加法需時6，訪存一次需時6，向量乘流水線完成一次乘法需時7。求出分別采用下列3種方式工作時，完成3條向量指令所需的時間。（1）3條指令依序串行。（2）指令①與指令②并行執(zhí)行完后，再執(zhí)行指令③。（3）采用指令鏈接技術(shù)解（1）計算3條向量指令各自單獨流水執(zhí)行時所需時間。向量指令V3←存儲器所需流水線建立的時間為啟動存儲器所需時鐘周期數(shù)，即有s1=1；訪存取向量A并打入向量寄存器V3中，以及流水操作打入A的第一個元素所需時鐘周期數(shù)為6+=7，即e1=7；完成向量A其余N-1個元素的打入所需時鐘周期數(shù)為(N-1)。因此，該向量指令單獨流水執(zhí)行所需時間向量指令V2←V0+V1單獨流水執(zhí)行所需時間向量指令V4←V2*V3單獨流水執(zhí)行所需時間因此，3條指令之間串行執(zhí)行，共需時間

（2）由于指令①和指令②同時并行，所需時間，然后執(zhí)行指令③，因此，共需時間（3）由于指令①與指令②之間既無向量流水線資源沖突（前者使用訪存流水線，后者使用向量加流水線，二者之間無資源沖突），又無向量寄存器的先寫后讀相關(guān)，因此，這2條指令是一個編隊，可以同時并行執(zhí)行。但是，指令③與指令①之間有寄存器V3的先寫后讀相關(guān)，與指令②之間有寄存器V2的先寫后讀相關(guān)，因此，指令③是另一個編隊?？梢栽诰庩犞g采用鏈接技術(shù)，即可把指令①和指令②同時并行的流水線流出的結(jié)果向量元素直接流入指令③的流水線。指令①流水線與指令②流水線同時并行執(zhí)行，流出第一對元素的時間為，因此，共需時間4.2.2低位交叉編址多體并行存儲器

1.交叉編址方式

由m個存儲體組成的多體并行存儲器，其存儲單元地址采用低位交叉編址的方法是：若每個存儲體的容量均為n個存儲字，則存儲單元地址的低log2m位稱為體號k，地址的高log2n位稱為體內(nèi)地址i。低位交叉編址的存儲單元地址A的計算公式為：A=m×i+k

若已知地址A，則可計算出該存儲單元所在存儲體的體號k=Amodm，以及體內(nèi)地址。

4.4.1Cache的地址映像與地址變換

1.全相聯(lián)地址映像及其地址變換

全相聯(lián)地址映像（Fully-AssociativeAddressMapping）是指主存中的任意一塊可以裝入到Cache中任意的塊位置上。全相聯(lián)映像的塊沖突概率最低，Cache空間利用率最高。全相聯(lián)映像的地址變換采用目錄表來實現(xiàn)，目錄表需存放在相聯(lián)存儲器中，目錄表的行數(shù)（即相聯(lián)存儲器的存儲單元數(shù)）是Cache的塊數(shù)。圖4.15全相聯(lián)映像地址變換

【例4.6】

在Cache存儲器中，Cache的容量是2C字節(jié)，主存是由m個存儲體組成的低位交叉編址并行存儲器，主存總?cè)萘渴?M字節(jié)，按存儲單元編址，每個存儲體的存儲單元是k字節(jié)。采用全相聯(lián)映像，用相聯(lián)目錄表實現(xiàn)地址變換。（1）寫出主存地址和Cache地址的格式，并指出各字段的長度。（2）求出目錄表的行數(shù)、相聯(lián)比較的位數(shù)和目錄表的寬度。解（1）采用全相聯(lián)映像時，主存地址和Cache地址都分為2個字段：塊號和塊內(nèi)地址，格式分別為：

塊號B塊內(nèi)地址W塊號b塊內(nèi)地址w主存地址Cache地址因為主存的容量是2M字節(jié)，存儲單元的存儲字長是k字節(jié)，故主存存儲單元數(shù)為2M/k，主存地址長度為Log2(2M/k)=M-log2k。因為Cache的容量是2C字節(jié)，存儲字長是k字節(jié)，故Cache存儲單元數(shù)為2C/k，Cache地址長度為log2(2C/k)=C-log2k。塊的大小為m個存儲字，故塊內(nèi)地址W和w的長度均為log2m。主存塊號B的長度為(M-log2k)-log2m=M-log2kmCache塊號b的長度為(C-log2k)-log2m=C-log2km

（2）相聯(lián)目錄表的行數(shù)是Cache的塊數(shù)。塊號b的長度為C-log2km，則Cache塊的塊數(shù)可表示為相聯(lián)比較位數(shù)=M-log2km（位）目錄表的寬度=(M-log2km)+(C-log2km)+1=M+C-2log2km+1（位）2.直接地址映像及其地址變換

直接地址映像（DirectAddressMapping）把主存空間按Cache的大小劃分為若干區(qū)，主存各區(qū)和Cache再劃分為若干塊，主存各區(qū)中的區(qū)內(nèi)塊號B只能裝入到與Cache塊號b相同的那個塊位置上。直接映像的塊沖突概率最高，Cache空間利用率最低。直接映像的地址變換采用區(qū)表來實現(xiàn)，區(qū)表存放在按地址訪問的物理Cache中。區(qū)表的行數(shù)是Cache的塊數(shù)。3.組相聯(lián)地址映像及其地址變換

組相聯(lián)映像把主存按Cache的容量分區(qū)，主存中的各區(qū)和Cache再按同樣大小劃分成數(shù)量相同的組，組內(nèi)按同樣的大小劃分成數(shù)量相同的塊，主存的組到Cache的組之間采用直接映像，兩個對應(yīng)組的塊之間采用全相聯(lián)映像。組相聯(lián)的地址變換采用塊表來實現(xiàn)。存儲塊表的存儲器可以采用按地址訪問的存儲器，也可以采用相聯(lián)訪問的存儲器，兩種存儲器中的塊表的結(jié)構(gòu)不同。【例4.7】

采用組相聯(lián)映像的Cache存儲器，Cache容量為1K字，要求Cache的每一塊在一個主存訪問周期能從主存取得。主存采用4個低位交叉編址的存儲體組成，主存容量為256K字。采用按地址訪問存儲器存放塊表來實現(xiàn)地址變換，并采用4個相等比較電路。請設(shè)計地址變換的塊表，求出該表的行數(shù)和容量。說明地址變換過程及每個比較電路進(jìn)行相等比較的位數(shù)。

解采用組相聯(lián)地址變換把主存地址變換為Cache地址時，需要把主存地址分為4個字段，把變換得到的Cache地址分為3個字段。為了確定塊表的結(jié)構(gòu)，首先需要確定各字段的長度。區(qū)號E組號G塊號B塊內(nèi)地址W主存地址組號g組號b塊內(nèi)地址wCache地址主存容量為256K字，即有存儲單元218個，故主存地址長度為18位。Cache容量為1K字，即有存儲單元210個，故Cache地址長度為10位。主存按Cache大小分區(qū)，即主存分為256K/1K=256區(qū)，故主存地址的區(qū)號E的長度為8位。地址變換的塊表采用4個相等比較電路，即一組分為4塊，故組內(nèi)塊號B和b的長度為2位。塊的大小由在一個主存訪問周期能從主存取得的信息量來確定。主存采用4個存儲體組成的并行存儲器，因此，一個主存訪問周期能從主存取得4個存儲字，故塊的大小為4個存儲字，即塊內(nèi)地址W和w的長度為2位。區(qū)內(nèi)組號G的長度=18-8-2-2=6位。組號g的長度=10-2-2=6位。塊表中的e是有效位，有效位e的長度為1位。塊表的行數(shù)為Cache的組數(shù)，即有26=64行。塊表的寬度=組內(nèi)塊數(shù)×(E的長度+B的長度+b的長度+e的長度)=4×(8+2+2+1)=52位塊表的容量=塊表行數(shù)×塊表寬度=64×52=3328位64行EBbeEBbeEBbeEBbe圖4.19例4.7的塊表結(jié)構(gòu)

用塊表進(jìn)行地址變換的過程是：用訪存的主存地址中的組號G字段作為塊表首地址的偏移量，找到塊表中的相應(yīng)行。讀出該行有效位e表示相應(yīng)主存塊有效的區(qū)號E和塊號B，與主存地址中的區(qū)號E字段和塊號B字段進(jìn)行比較。若比較結(jié)果是相等，則把從塊表中讀出的塊號b放入Cache地址的塊號b字段，并把訪存的主存地址中的組號G字段和塊內(nèi)地址W字段分別放入Cache地址的組號g字段和塊內(nèi)地址w字段，從而得出變換的Cache地址。每個比較電路進(jìn)行相等比較的位數(shù)為E的長度+B的長度=(8+2)位=10位5.蝶式置換蝶式置換（Butterfly）實現(xiàn)的互連是：把輸入端二進(jìn)制地址的最高位與最低位互換位置就是連接的輸出端的二進(jìn)制地址。蝶式置換的互連函數(shù)為

子蝶式置換實現(xiàn)的互連是：把輸入端二進(jìn)制地址的第k位與最低位互換位置就是連接的輸出端的二進(jìn)制地址。子蝶式置換的互連函數(shù)為

超蝶式置換實現(xiàn)的互連是：把輸入端二進(jìn)制地址的最高位與第n-k-1位互換位置就是連接的輸出端的二進(jìn)制地址。超蝶式置換的互連函數(shù)為顯然，下列等式成立

N=8的蝶式置換、子蝶式置換和超蝶式置換的互連函數(shù)分別為

（a）（b）（c）

圖5.5N=8的蝶式置換和位序顛倒置換

5.2.1互連網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)

互連網(wǎng)絡(luò)連接的拓?fù)浣Y(jié)構(gòu)可以用無向邊或有向邊連接有限個結(jié)點的圖來表示。1.網(wǎng)絡(luò)規(guī)模網(wǎng)絡(luò)規(guī)模是指網(wǎng)絡(luò)能連接的結(jié)點數(shù)。2.結(jié)點度一個結(jié)點射入或射出的邊數(shù)稱為這個結(jié)點的結(jié)點度。4.網(wǎng)絡(luò)直徑一個互連網(wǎng)絡(luò)中任意兩個結(jié)點之間距離的最大值稱為這個網(wǎng)絡(luò)的網(wǎng)絡(luò)直徑。2.Omega網(wǎng)絡(luò)Omega網(wǎng)絡(luò)的結(jié)構(gòu)特征是：①采用2×2的4功能開關(guān)，這4個功能為：直接、交叉、上播和下播。網(wǎng)絡(luò)輸入端數(shù)和輸出端數(shù)都為N，有個開關(guān)級，每級有N/2個開關(guān)，網(wǎng)絡(luò)開關(guān)數(shù)為。②網(wǎng)絡(luò)n個開關(guān)級從網(wǎng)絡(luò)輸入端到輸出端依次為。n+1個級間連接依次為，其中，都是均勻洗牌置換，是恒等置換。③開關(guān)采用單元控制方式。

圖5.19N=8的Omega網(wǎng)絡(luò)3.STARAN網(wǎng)絡(luò)

STARAN網(wǎng)絡(luò)的結(jié)構(gòu)特征是：①采用2×2的2功能開關(guān)，2個功能為直送和交叉。網(wǎng)絡(luò)輸入端數(shù)和輸出端數(shù)都為N，有個開關(guān)級，每級有N/2個開關(guān)，網(wǎng)絡(luò)開關(guān)數(shù)為。由于只使用2功能開關(guān)，級間連接都是置換連接，所以STARAN網(wǎng)絡(luò)實現(xiàn)的連接都是置換連接。②網(wǎng)絡(luò)n個開關(guān)級從網(wǎng)絡(luò)輸入端到輸出端依次為。n+1個級間連接依次為，其中，是恒等置換，都是逆洗牌置換。③開關(guān)有2種控制方式，一種為級控方式，另一種為組控方式。

圖5.23三級STARAN網(wǎng)絡(luò)

（1）級控方式及其實現(xiàn)的置換連接在級控方式下，需要n位二進(jìn)制信號作為網(wǎng)絡(luò)開關(guān)控制信號，若fi=0，則級所有開關(guān)為直送；若fi=1，則ki級所有開關(guān)為交叉。因此，STARAN網(wǎng)絡(luò)實現(xiàn)的置換連接可表示為：

當(dāng)fi=1時，有。因此，若級控信號F中只有fi=1，其他各位都為0時，STARAN網(wǎng)絡(luò)實現(xiàn)的置換連接為：

表5.2N=8的STARAN網(wǎng)絡(luò)在級控方式下實現(xiàn)的互連f2f1f0實現(xiàn)的互連函數(shù)表示000001010011100101110111表5.3N=8的STARAN網(wǎng)絡(luò)在級控方式下實現(xiàn)的分組交換置換f2f1f0連接的輸出端號序列實現(xiàn)的分組交換置換連接00001234567恒等001103254764組2元交換010230167454組2元交換+2組4元交換011321076542組4元交換100456701232組4元交換+1組8元交換101547610324組2元交換+2組4元交換+1組8元交換110674523014組2元交換+1組8元交換111765432101組8元交換（2）組控方式及其實現(xiàn)的置換連接

組控方式是指：將第i級的N/2個2*2的2功能開關(guān)分成i+1組，每組用一個位信號f控制該組開關(guān)的狀態(tài)。若f=0，則該組所有開關(guān)為直送；若f=1，則該組所有開關(guān)為交叉。對于級數(shù)是的網(wǎng)絡(luò)，從第0級至第n-1級各開關(guān)級所需的位信號數(shù)分別為1,2,n個，因此，共需n(n+1)/2個位信號組成組控信號F。對于N=8的網(wǎng)絡(luò)，需要6個位信號組成組控信號F，表示為。...表5.4N=8的STARAN網(wǎng)絡(luò)在組控方式下實現(xiàn)的移數(shù)置換循環(huán)左移1位：循環(huán)左移2位：循環(huán)左移4位：f23f22f21f12f11f0連接的輸出端號序列實現(xiàn)的移數(shù)置換連接00101112345670011110234567011110004567012300001112305674分組移數(shù)置換：分為2組，組內(nèi)循環(huán)左移1位00011023016745分組移數(shù)置換：分為2組，組內(nèi)循環(huán)左移2位00000110325476分組移數(shù)置換：分為4組，組內(nèi)循環(huán)左移1位00000001234567【例5.9】

對于的間接二進(jìn)制n方體網(wǎng)絡(luò)，要求同時實現(xiàn)如下連接：0→1，1→6，2→4，3→1，4→2，5→7，6→5，7→0（1）若單元控制采用上控法，網(wǎng)絡(luò)是否會發(fā)生阻塞？畫出網(wǎng)絡(luò)的開關(guān)狀態(tài)圖。（2）若單元控制采用輸入端與輸出端地址按位加的控制方法（T標(biāo)記尋徑），網(wǎng)絡(luò)是否會發(fā)生阻塞？畫出網(wǎng)絡(luò)的開關(guān)狀態(tài)圖。圖5.25三級間接二進(jìn)制n方體網(wǎng)絡(luò)的開關(guān)狀態(tài)圖5.Delta網(wǎng)絡(luò)

Delta網(wǎng)絡(luò)的結(jié)構(gòu)特征是：①的Delta網(wǎng)絡(luò)采用a×b的開關(guān)，有n個開關(guān)級，從網(wǎng)絡(luò)輸入端到輸出端依次為K1，K2，…，Kn。開關(guān)級Ki的開關(guān)數(shù)是，1

。開關(guān)級Ki的輸入端數(shù)是，輸出端數(shù)是。開關(guān)級K1的的開關(guān)數(shù)是個，故網(wǎng)絡(luò)的輸入端數(shù)是。開關(guān)級Kn的開關(guān)數(shù)是個，故網(wǎng)絡(luò)的輸出端數(shù)是。上控法指定由到達(dá)開關(guān)上輸入端的di

來決定開關(guān)的狀態(tài)。若di=0，則開關(guān)為直送狀態(tài)；若di=1，則開關(guān)為交叉狀態(tài)。下控法指定由到達(dá)開關(guān)下輸入端的di來決定開關(guān)的狀態(tài)，若di=0，則開關(guān)為交叉狀態(tài)；若di=1，則開關(guān)為直送狀態(tài)【例5.11】

對于的Benes二進(jìn)制置換網(wǎng)絡(luò)，要求同時實現(xiàn)如下連接：0→2，1→3，2→4，3→0，4→6，5→7，6→5，7→1若單元控制采用上控法，那么網(wǎng)絡(luò)是否會發(fā)生阻塞？畫出網(wǎng)絡(luò)的開關(guān)狀態(tài)圖。解根據(jù)8個輸入端的連接要求，用上控法確定的各開關(guān)的狀態(tài)要求分別如表5.9所示。由表5.9可見，8個輸入端的連接要求沒有發(fā)生開關(guān)狀態(tài)沖突，也沒有發(fā)生爭用開關(guān)輸出端的沖突，所以，網(wǎng)絡(luò)不會發(fā)生阻塞。網(wǎng)絡(luò)的開關(guān)狀態(tài)如圖5.30所示。

圖5.30Benes二進(jìn)制置換網(wǎng)絡(luò)的開關(guān)狀態(tài)圖5.5.2尋徑方法與多播通信

尋徑的基本操作就是監(jiān)控從輸入端口進(jìn)入的信包，并為每個信包選擇一個輸出端口。由一個高速互連網(wǎng)絡(luò)連接的多個處理器可以同時向互連網(wǎng)絡(luò)的多個輸入端口發(fā)送信包，因此，互連網(wǎng)絡(luò)的尋徑方法（算法）應(yīng)該盡可能簡單和快速，能為同時到達(dá)的輸入信包進(jìn)行尋徑。尋徑方法有算術(shù)尋徑法和查表尋徑法等方法。1.算術(shù)尋徑法對于具有規(guī)則的拓?fù)浣Y(jié)構(gòu)的互連網(wǎng)絡(luò)，可以應(yīng)用算術(shù)尋徑法，它具有簡單快速的優(yōu)點。例如，曾在多級互連網(wǎng)絡(luò)中討論的終端標(biāo)記尋徑法、上控法、下控法和T標(biāo)記尋徑法等方法。維序?qū)绞前淳W(wǎng)格網(wǎng)中結(jié)點的坐標(biāo)維的順序來選擇通信鏈路的尋徑方法。二維網(wǎng)格網(wǎng)中的維序?qū)椒Q為X-Y尋徑，超立方體網(wǎng)絡(luò)中的維序?qū)椒Q為E-立方尋徑。（1）X-Y尋徑法在二維網(wǎng)格網(wǎng)中，X-Y尋徑法規(guī)定：任何一個信包在網(wǎng)絡(luò)中任何一個結(jié)點中首先沿X維方向傳送，再沿Y維方向傳送。

【例5.12】

在一個的二維網(wǎng)格網(wǎng)中，用表示結(jié)點?，F(xiàn)有4個源—目的結(jié)點對同時有信包傳送要求：（2,1）→（7,6），（5,4）→（2,0），（0,7）→（4,2），（6,3）→（1,5）。說明采用X-Y尋徑算法時各自的傳送路徑。是否會發(fā)生信包爭用傳送鏈路或結(jié)點包緩沖區(qū)的沖突？解

4個信包在二維網(wǎng)格網(wǎng)上的傳送路徑如圖5.33所示。如果信包經(jīng)過一個結(jié)點的延時相等，皆為，那么，可以把這4個信包沿各自路徑依序經(jīng)過的結(jié)點順序表示在表5.10中。

表5.108×8二維網(wǎng)格網(wǎng)中4個信包依序傳送的結(jié)點序列

時間包1（2,1）（3,4）（4,1）（5,1）（6,1）（7,1）（7,2）（7,3）（7,4）（7,5）（7,6）包2（5,4）（4,4）（3,4）（2,4）（2,3）（2,2）（2,1）（2,0）包3（0,7）（1,7）（2,7）（3,7）（4,7）（4,6）（4,5）（4,4）（4,3）（4,2）包4（6,3）（5,3）（4,3）（3,3）（2,3）（1,3）（1,4）（1,5）（2）E-立方尋徑

在個結(jié)點的n方體網(wǎng)絡(luò)中，源結(jié)點S的地址為S=sn-1…s1s0，目的結(jié)點D的地址為D=dn-1…d1d0。從S到D的路徑中的任一中間結(jié)點V的地址為V=vn-1…v1v0。E-立方尋徑法規(guī)定：信包從當(dāng)前結(jié)點V沿n維維序的傳送由決定，若r1=1，則信包從當(dāng)前結(jié)點沿維i傳送一步到鄰接結(jié)點；若ri=0，則信包不沿維i傳送?！纠?.13】

在一個4維超立方體網(wǎng)絡(luò)中，信包從源結(jié)點S=0110傳送到目的結(jié)點D=1101，采用E-立方尋徑算法，說明信包的傳送路徑。解由S=0110和D=1101，得。第一步：i=0，由r0=1，信包從S傳送到結(jié)點，即從S沿維0傳送一步到結(jié)點v1=0111。

第二步：i=1，由r1=1，信包從V1傳送到結(jié)點，即從V1沿維1傳送一步到結(jié)點V2=0101。第三步：i=2，由r2=0，信包不沿維2傳送。第四步：i=3，由r3=1，信包從V2傳送到結(jié)點，即從V2沿維3傳送一步到結(jié)點V3=1101