高級計算機體系結構試卷作業授課教師陳文智作者姓名21321240陳英芝 21321191楊誼 21321284柴一平 21321189張翔提交日期2014年01月06日2013-2014學年秋冬學期高級計算機體系結構試卷學號____________姓名____________分數____________一、選擇題（共10題，每題2分，共20分）1、根據指令流和數據流的多倍性可以將計算機體系結構分為四大類。其中以陣列處理機和向量處理機為代表的是（），以多機計算機系統為代表的是（）。SISD，SIMDB.SIMD，MIMDC.MISD，MIMDD.MIMD，SIMD2、在流水線中，利用簡單硬件技術“轉發（Forwarding）”可以解決一些數據冒險問題，從而減少流水線停頓，但是并非所有數據冒險都可以通過轉發方式處理。下列指令序列中，不能利用轉發技術完全消除停頓的是（）。A.DADDR1，R2，R3 B.LDR1，0(R2)DSUBR4，R1，R5 DSUBR4，R1，R5C.DADDR1，R2，R3 D.LDR4，0(R1)LDR4，0(R1) DADDR1，R2，R33、下列語句間存在的指令間相關性有_______、_______，在基本流水線（MIPS）中會產生競爭的有_______、_______。DADDIU R1,R3,#-8BNE R1,R2,LOOPSUB R4,R4,#8A、RAW，WAR；RAW，WAR B、真相關，反相關；RAW，轉移C、真相關，控制相關；RAW，轉移 D、RAW，WAW；RAW，WAW4、下列哪個選項正確包含了記分牌全部限制因素：①指令間可用并行數少②積分卡的項數有限③功能單元數目和類型④存在反相關和輸出相關⑤未能利用轉發⑥無法解決RAWA.①②③④⑥ B.②③⑤⑥ C.①②③④⑤ D.①③④⑤⑥5、Tomasulo's硬件調度算法有兩個主要優點，一是_______競爭檢測邏輯，二是消除了_______競爭的阻塞。A、集中，WAW和WAR B、分散，WAW和WARC、集中，WAW和RAW D、分散，WAW和RAR

6、通過硬件動態預測轉移指令的行為可以減少轉移代價，2位轉移預測緩沖器是硬件動態預測技術之一。假設2位轉移預測緩沖器的初始值為0，某循環體共循環10次，若該循環體只在前9次循環實際轉移，最后1次實際不轉移，則2位預測緩沖器的命中率為（）。若該循環體在第一次循環實際轉移，且實際轉移行為間隔變換一次，則2位預測緩沖器的命中率為（）。A.90%，50% B.70%，20%C.70%，50% D.90%，20%7、多發射處理器的目標是允許在一個時鐘周期內發射多條指令。兩種基本的多發射技術有（），（）。其中（）每時鐘周期發射固定數目的指令，（）主要采用硬件檢測競爭。A、多處理器，超標量；超標量，多處理器

B、VLIW，超標量；VLIW，超標量C、超標量，VLIW；超標量，VLIW

D、超標量，VLIW；VLIW，超標量8、以下說法正確的是：=1\*GB3①集中式共享存儲器系統結構所有的處理器訪問存儲器的時間不一致=2\*GB3②在分布式共享存儲（DSM）系統中，任何一個處理器都能夠通過引用地址的方式訪問任意節點上的存儲器=3\*GB3③在消息傳遞多處理器系統中，不同處理器中相同的物理地址分別指向兩個不同存儲器中的不同位置=4\*GB3④NUMA（非均勻存儲器訪問）的訪問時間取決于數據字在存儲器中的位置A.=1\*GB3①=2\*GB3② B.=1\*GB3①=2\*GB3②=3\*GB3③=4\*GB3④ C.=2\*GB3②=3\*GB3③=4\*GB3④ D.=1\*GB3①=3\*GB3③=4\*GB3④9、出現多處理機cache不一致的原因有：共享可寫的數據、進程遷移和I/O傳輸。有以下兩個不同處理器的程序T1和T2共享同一個可寫的數據，T1與T2分別使用緩存cache-1和cache-2，且采用寫回式寫回緩存。內存與緩存的初始值如下表所示。這兩個進程按下表順序執行之后，內存中保存的數據為（）。ProgramT1ProgramT2Cache-1Cache-2內存初始值程序執行順序STX,1STY,10LDY,R1STY’,R1LDX,R2STX’,R2X=Y=X=X’=Y=Y’=X=0Y=5X’=Y’=T1完成程序執行Cache-1寫回XT2執行結束Cache-2寫回X’與Y’Cache-1寫回YA. X=1，Y=10，X’=1，Y’=5 B.X=0，Y=10，X’=1，Y’=5C.X=1，Y=5，X’=1，Y’=10 D.X=0，Y=5，X’=1，Y’=510、在基于目錄的cache一致性協議中，已知數據塊可能處于以下3種狀態：共享（shared）、未緩存（uncached）、獨占（exclusive）。則在數據塊處于共享狀態時可能的目錄請求有：=1\*GB3①讀缺失=2\*GB3②寫缺失=3\*GB3③數據寫回A．=1\*GB3①=2\*GB3②=3\*GB3③ B.=1\*GB3①=2\*GB3② C.=2\*GB3②=3\*GB3③ D.=1\*GB3①=3\*GB3③二、簡答題（共5題，每題4分，共20分）1、簡述流水線的三類冒險，并指出數據冒險有哪幾類，以及解決數據冒險的方法。2、簡述分支延時槽的原理，并根據分支延時槽的原理優化下述代碼。ADDR1，R2，R3DelayslotIfR2=0thenDelayslot3、簡述硬件投機機制的原理和ROB的作用，并指出ROB與普通的tomasulo算法中的保留站（reservationstations）的功能區別。4、簡述tomosulo算法和記分牌算法的異同。5、試解釋并行性的含義。三、計算題（共2題，每題10分，共20分）（1）概述Amadahl定律（2）假定指令中的FP（浮點）運算頻率=25%，FP平均CPI=5.0，平均非FP的CPI=2.33，FPSQR（浮點開方）運算頻率5%，FPSQR的平均CPI=20，假定有兩種方法提高性能，分別是： a.將FP中FPSQR的CPI減少到2 b.將FP的CPI減少到2.5，試計算這兩種方案的CPI，并計算出較好的方法的加速比，結果保留兩位有效數字。（3）現有100個處理器，為了達到50倍的加速比，試計算所需要的并行度,結果保留四位有效數字。2、設指令間的相關性參數如下表，假定采用一個標準5級整數流水線，這些功能單元被完全流水化或復制。試分析計算下列問題：（1）

計算該循環在未進行任何調度時迭代一次需多少時鐘。（2）

采用軟件流水方式編譯優化下列循環，使其循環內的競爭最少。（3）

計算優化后該循環迭代一次需多少時鐘。前操作指令后繼相關指令延遲時鐘FPALU

操作FPALU

操作3FPALU

操作Store(雙字)2Load(雙字)FPALU

操作1Load(雙字)Store(雙字)0LOOP：

L.D

F0，0(R1)ADD.D

F4，F0，F2S.D

0(R1)，F4DADDUI

R1，R1，#-8BNEZ

R1，LOOP四、分析題（共3題，共40分。第1題15分，第2題10分，第3題15分）1、（m,n）相關分支預測器利用最近執行的m個分支的行為從2m個預測器中作出選擇，這些預測器都是n位預測器。現有一個（2,2）相關分支預測器共8K位。（1）在該相關分支預測器中有多少項？（2）畫出這個相關預測器的硬件框圖。（3）假設全局轉移緩存和每個轉移預測器的初始值都為0，a初始值為1，利用上述（2,2）相關分支預測器，下列程序連續執行5次時命中率是多少？Reg[R1]=a;Reg[R1]=a;BNEZ R1，L1;DADD R1，R0，#1;L1: DADDR3，R1，#-1; BNEZ R3，L2; DADDR1，R0，#2L2：…if(a==0) a=1;if(a==1) a=2;2、假設浮點功能單元的延遲為：加法為2個時鐘周期、乘法為6個時鐘周期、除法為12個時鐘周期。通過基于Tomasulo動態調度的硬件投機技術，使用下面代碼段，寫出當DIV.D指令做好提交準備時的狀態表。L.DL.D F6,32(R2)L.D F2,44(R3)MUL.D F0,F2,F4SUB.D F8,F2,F6DIV.D F10,F0,F6ADD.D F6,F8,F2重排序緩沖器項目繁忙指令狀態目的地值123456FP寄存器狀態字段F0F1F2F3F4F5F6F7F8F10ROB#繁忙3、根據下表指令序列，結合snooping協議cache塊的狀態轉移圖，假設緩存寫回方式采用寫回式。請正確填寫下面流程表，若內存有多個數據，例如內存中A1=10,A2=15則表格填寫方式為Addr：A1、A2，Value：10、15。snooping協議cache塊狀態轉移圖注意：假設初始Cache的狀態為Invalid，且A1與A2映射到同一Cache塊，A1!=A2P1P2BUSMEMstepStatAddrValueStatAddrValueStatProcAddrValueAddrvalueP2:Write20toA1P1:Write40toA2P2:ReadA2P1:Write30toA2P1:Write50toA12013-2014學年秋冬學期高級計算機體系結構試卷分析選擇題1、B。SIMD計算機屬于并行結構計算機，一條指令可以同時對多個數據進行運算。SIMD計算機由單一的指令部件控制，按照同一指令流的要求，為多個處理單元分配各不相同的數據并進行處理。SIMD計算機以陣列處理機和向量處理機為代表。MIMD計算機屬于并行結構計算機，多個處理單元根據不同的控制流程執行不同的操作，處理不同的數據。MIMD計算機是能夠實現指令、數據作業、任務等各級全面并行計算的多機處理系統。2、B。本題考查對forwarding技術的理解。Forwarding技術是解決流水線中的部分數據冒險問題的重要硬件技術，但由于load指令只有在MEM周期結束之后才能得到數據，所以即使利用轉發也需要一個停頓之后才能得到數據。本題中B選項中LD與DSUB存在數據相關，且不能利用轉發技術完全消除停頓。A,C選項都能利用轉發技術消除停頓，而D選項不存在數據相關。答案選B。3、C。DADDIU R1,R3,#-8①BNE R1,R2,LOOP②SUB R4,R4,#8③①②之間存在真相關，產生RAW競爭。②存在控制相關，產生轉移競爭。4、C。5、B。相較簡單的方案而言，Tomasulo方案有兩個優勢：1）冒險檢測邏輯的分散；2）消除可能產生的WAW和WAR冒險的停頓。第一個優勢源于分布式保留站和CDB的使用，第二個優勢（消除WAR和WAW）是利用保留站來重命名寄存器，并在操作數可用時，立即將其存儲在保留站中。6、C。本題考查對2位轉移預測緩沖器的理解。2位預測器只有在連續預測錯誤兩次之后才會修改預測方向。當循環體在前9次實際轉移，最后一次實際不轉移時：預測器開始預測不轉移，前兩次都預測失敗，連續失敗兩次后，2位預測器預測轉移，所以3~9次預測成功，第10次實際不轉移，預測錯誤，故命中率為70%。當循環體第一次實際轉移且實際轉移行為間隔變換一次時：預測器每兩次命中一次，故命中率為50%。答案選C。7、B。多發射技術有superscalar超標量方法和VLIW超長指令字。超標量主要采用硬件檢測競爭，VLIM采用編譯構成可并行執行的指令包，每個周期始終發射固定數目的指令。8、C。現有的MIMD機器根據存儲器組織方式可以分為兩類：集中式共享存儲器系統結構和分布式存儲器系統結構。集中式共享存儲器結構只有單一存儲器結構，對每個處理器而言都是對等的，每個處理器訪問的時間都相同，所以也被稱為對稱（共享存儲器）多處理器系統（SMP）或均勻存儲器訪問（UMA）。分布式存儲器多處理器系統的每個節點包含處理器、存儲器、輸入輸出系統和互聯網絡的接口。 根據處理器間傳遞數據所用的方法，有兩種不同的系統結構。分布式共享存儲器系統（DSM）和消息傳遞多處理器系統。DSM將物理上分離的存儲器作為邏輯上共享的地址空間進行尋址，所以任何一個處理器都能夠通過引用地址的方式訪問任意節點上的存儲器，但是其訪問時間取決于數據字在存儲器中的位置，所以也被稱為NUMA（非均勻存儲器訪問）。消息傳遞多處理器系統的地址空間由多個私有的地址空間組成，這些私有地址空間在邏輯上是分散的，并且不能被遠程處理器尋址。9、A。本題考察共享可寫數據時引起的cache不一致，寫回式和回寫式兩種緩存寫入方式的理解。采用寫回式緩存時緩存更新的數據不會立即反應到內存中。本題中，T1完成程序執行時cache1中的X=1，Y=10。Cache1寫回X后，內存中的X=1。T2執行結束時cache2中的X=1，X’=1，Y=5，Y’=5。Cache2寫回X’與Y’后內存中X=1，Y=5，X’=1，Y’=5。Cache1寫回Y后內存中X=1，Y=10，X’=1，Y’=5。故答案為A。10、B。簡答題1、流水線的三類冒險分別是：（1）結構冒險：當硬件在指令重疊執行中不能支持指令所有可能的組合時發生資源冒險。（2）數據冒險：在同時執行的指令中，一條指令依賴于前一條指令的數據而得不到時發生的冒險。（3）控制冒險：流水線中的轉移指令或其他改寫PC的指令造成的冒險。其中有3類數據冒險：RAW（寫后讀）：指令j試圖在指令i寫一個數據之前讀取它，這時j會讀到錯誤的值，RAW對應于數據的真相關；WAW（寫后寫）：指令j試圖在指令i寫一個數據之前寫該數據，留下的值將會是指令i的結果，WAW對應于輸出相關，只在特定類型的流水線中才發生；WAR（讀后寫）：指令j試圖在指令i讀一個數據之前寫該數據，這時指令i會錯誤的讀出新值，WAR對應于反相關，不會發生在靜態流水線之中。解決數據冒險的方法有：雙跳（doublebump）；停頓（stall）；轉發（forwarding）；指令重排序（instructionreorder）。2、分支延時槽的原理：引入分支延遲槽的目的主要是為了提高流水線的效率。流水線中，分支指令執行時因為確定下一條指令的目標地址一般要到第ID級以后，在目標確定前流水線的取指級是不能工作的，即整個流水線就“浪費”（阻塞）了一個時間片，為了利用這個時間片，在體系結構的層面上規定跳轉指令后面的一個時間片為分支延遲槽（branchdelayslot）。位于分支延遲槽中的指令總是被執行，與分支發生與否沒有關系。這樣就有效利用了一個時間片，消除了流水線的一個“氣泡”。調整后的代碼：ADDR1，R2，ADDR1，R2，R33、（1）硬件投機機制的原理：基于硬件的投機技術實質上是綜合了下述三種技術的一種集成技術：=1\*GB3①應用動態轉移預測技術選擇投機指令=2\*GB3②應用投機技術達到在控制相關性消除以前就執行指令=3\*GB3③應用動態調度技術來調度程序基本塊的不同組合。實際上就是動態投機與動態調度相結合的一種技術。（2）ROB的作用：重構序緩存（ROB）相當于一個額外的虛擬存儲器，相當于tomasulo算法中的保留站、loadbuffer和storebuffer等的功能。重構序緩存在指令完成操作之后直到交付這段時間里保存該指令的結果，作為其他指令操作數的源。（3）ROB與RS的區別：在tomasulo算法中，當指令完成寫結果的操作后，所有的后繼指令都將從寄存器文件中讀取結果。而在推測技術中，只有在指令提交之后寄存器文件才會被更新，即在指令執行到指令提交這段時間之內，由ROB提供操作數。4、（1）核心思想相同之處：兩者消除RAW競爭的思想相同。Tomasulo方法采用了記分牌方法的動態調度的核心思想，多條指令處于發射狀態，等待條件成熟，可以不按順序執行。（2）核心思想不同之處：Tomasulo方法通過寄存器換名過程可以消除WAR和WAW競爭。記分牌方法能檢測WAR和WAW競爭，一旦檢測到存在WAR和WAW競爭，通過插入停頓周期來解決這一競爭。所以，記分牌方法不能消除WAR和WAW競爭。（3）檢測競爭和控制指令執行方式的不同：Tomasulo方法檢測競爭和控制指令執行兩方面功能是通過分布在每一功能單元的保留站來進行的，因此Tomasulo方法是一種分布式方法。記分牌方法的上述功能是通過統一的記分牌來實現的，因此記分牌方法是一種集中式方法。（4）寫結果的方法不同：Tomasulo方法直接將功能單元輸出的結果送往需要該結果的所有保留站，而不必經過寄存器這一中間環節。記分牌方法是將結果寫入寄存器,因而可能造成等待這一結果的指令都出現停頓現象，之后，所有相關指令的功能單元在讀FP寄存器時又可能出現競爭現象。5、并行性是指計算機系統具有可以同時進行運算或操作的特性，在同一時間完成兩種或兩種以上工作。它包括同時性與并發性兩種含義。同時性指兩個或兩個以上事件在同一時刻發生。并發性指兩個或兩個以上事件在同一時間間隔發生。是通過對有限物理資源強制行駛多用戶共享以提高效率。三、計算題1、1）Amdahal定律定義了使用某一特定功能所獲得的加速比。加速比取決于下面兩個因素：原計算機計算時間中可升級部分所占的比例；通過升級執行模式得到的改進，也就是說在為整個程序使用這一執行模式時，任務的運行速度會提高多少倍。2）由公式CPIoriginal=i=1=(5x25%)+(2.33x75%)=3CPInewFPSQR=CPIorignal-5%x(CPIoldFPSQR-CPIwithnewFPSQRonly)=3.0-5%x(20-2)=2.1同理，計算出CPInewFP=(75%x2.33)+(25%x2.5)=2.375通過比較，第一種方案更優，加速比SpeedupnewFPSQR=CPIoriginal/CPInewFPSQR=3/2.1=1.42863）由加速比的公式得： 50 =1/(Fparallel/100+(1-Fparallel)) Fparallel≈0.98992、1)未調度時，迭代一次需10個時鐘。FDXMWFDSA1A2A3A4WFSDSSXMWFSSDXMWFSDXMWFF10cc2）軟件流水方式編譯優化后的循環代碼如下：#啟動代碼：L.DF0,0(R1)DADDUIR1,R1,#-8ADD.DF4,F0,F2L.DF0,0(R1)DADDUIR1,R1,#-8#循環代碼：loop:S.D F4,16(R1);存到M[i]ADD.D F4,F0,F2;M[i-1]LD F0,0(R1);取M[i-2]BNEZR1,loopDADDUIR1,R1,#-8#結束代碼：S.DF4,16(R1)ADD.DF4,F0,F2S.DF4,8(R1)3)軟件流水方式編譯優化之后，每迭代n次，啟動代碼和結束代碼各執行一次，loop代碼執行n次。其中：#啟動代碼：L.DF0,0(R1)1DADDUIR1,R1,#-82ADD.DF4,F0,F23L.DF0,0(R1)4DADDUIR1,R1,#-85每執行一次啟動代碼需要5個時鐘周期#循環代碼：loop:S.D 16(R1),F4;存到M[i]1ADD.D F4,F0,F2;M[i-1]2LDF0,0(R1);取M[i-2]3BNEZR1,loop4DADDUIR1,R1,#-85每執行一次循環代碼需要5個時鐘周期#結束代碼：ADD.DF4,F0,F21S.D16(R1),F42Stall3S.D8(R1),F44每執行一次結束代碼需要4個時鐘周期所以當迭代n次時，總共需要9+5n個時鐘周期。所以每迭代一次需要的時鐘周期數（9+5n）/n=5+9/n四、分析題1、本題要求對關聯預測器和2位預測器有較好的理解，能綜合運用關聯預測器與2位預測器的結合。（1）22*2*由分支選中的預測項數=8K，則由分支選中的預測項數=1K。（2）這個相關預測器的硬件框圖如下：1010每個BR指令的低位地址每個轉移預測器2位2位全局轉移歷史記錄：最后兩條指令的轉移情況本次BR的預測位為XX1K項（3）程序執行時的數據