1、第一章計算機系統結構的基本概念 從處理數據的角度看，并行級別有位串字串，位并字串，位片串字并，全并行。位串字串和位并字串基本上構成了SIMD。位片串字并的例子有：相聯處理機STARAN，MPP。全并行的例子有：陣列處理機ILLIAC IV。 從加工信息的角度看，并行級別有存儲器操作并行，處理器操作步驟并行，處理器操作并行，指令、任務、作業并行。 存儲器操作并行是指可以在一個存儲周期內并行讀出多個CPU字的，采用單體多字、多體單字或多體多字的交叉訪問主存系統，進而采用按內容訪問方式，位片串字并或全并行方式，在一個主存周期內實現對存儲器中大量字的高速并行操作。例子有并行存儲器系統，以相聯存儲器為核

2、心構成的相聯處理機。 處理器操作步驟并行是指在并行性概念中引入時間因素，讓多個處理過程在時間上錯開，輪流重復地執行使用同一套設備的各個部分，加快硬件周轉來贏得速度。例子有流水線處理機。 處理器操作并行是指一個指令部件同時控制多個處理單元，實現一條指令對多個數據的操作。擅長對向量、數組進行處理。例子有陣列處理機。 指令、任務、作業并行是指多個獨立的處理機分別執行各自的指令、任務、作業。例子有多處理機，計算機網絡，分布處理系統。 并行性的開發途徑有時間重疊(Time Interleaving)，資源重復(Resource Replication)，資源共享(Resource Sharing)。 時

3、間重疊是指在并行性概念中引入時間因素，讓多個處理過程在時間上錯開，輪流重復地執行使用同一套設備的各個部分，加快硬件周轉來贏得速度。例子有流水線處理機。 資源重復是指一個指令部件同時控制多個處理單元，實現一條指令對多個數據的操作。例子有陣列處理機，相聯處理機。 資源共享是指用軟件方法讓多個用戶按一定時間順序輪流使用同一套資源以提高資源的利用率，從而提高系統性能。例子有多處理機，計算機網絡，分布處理系統。 SISD:一個指令部件控制一個操作部件，實現一條指令對一個數據的操作。例子有傳統的單處理機 SIMD:一個指令部件同時控制多個處理單元，實現一條指令對多個數據的操作。例子有陣列處理機，相聯處理機

4、。 MIMD:多個獨立的處理機分別執行各自的指令、任務、作業，實現指令、任務、作業并行的多機系統，是多個SISD的集合，也稱多倍SISD系統(MSISD)。例子有多處理機，計算機網絡，分布處理系統。 exercises: 1.有一臺經解釋實現的計算機，可以按功能劃分成4級，每一級為了執行一條指令，需要下一級的N條指令來解釋。如果執行第1級的一條指令要Kns時間，那么執行第2、第3和第4級的一條指令各需要用多少時間？ 解答：執行第2、第3和第4級的一條指令各需要KNns、KN2ns、KN3ns的時間。1.有一個計算機系統可按功能分成4級，每級的指令互不相同，每一級的指令都比其下一級的指令在效能上

5、強M倍，即第i級的一條指令能完成第i-1級的M條指令的計算量。現若需第i級的N條指令解釋第i+1級的一條指令，而有一段第1級的程序需要運行Ks，問在第2、3和4級上一段等效程序各需要運行多長時間？ 答： 第2級上等效程序需運行：(N/M)*Ks。第3級上等效程序需運行：(N/M)*(N/M)*Ks。第4級上等效程序需運行：(N/M)*(N/M)*(N/M)*Ks。 note: 由題意可知：第i級的一條指令能完成第i-1級的M條指令的計算量。而現在第i級有N條指令解釋第i+1級的一條指令，那么，我們就可以用N/M來表示N/M 表示第i+1級需(N/M)條指令來完成第i級的計算量。所以，當有一段第

6、1級的程序需要運行Ks時，在第2級就需要(N/M)Ks，以此類推 2.硬件和軟件在什么意義上是等效的？在什么意義上又是不等效的？試舉例說明。 答：軟件和硬件在邏輯功能上是等效的，原理上，軟件的功能可用硬件或固件完成，硬件的功能也可用軟件模擬完成。但是實現的性能價格比，實現的難易程序不同。 在DOS操作系統時代，漢字系統是一個重要問題，早期的漢字系統的字庫和處理程序都固化在漢卡（硬件）上，而隨著CPU、硬盤、內存技術的不斷發展，UCDOS把漢字系統的所有組成部份做成一個軟件。 3.試以實例說明計算機系統結構、計算機組成與計算機實現之間的相互關系與影響。 答：計算機系統結構、計算機組成、計算機實現

7、互不相同，但又相互影響。 （1）計算機的系統結構相同，但可采用不同的組成。如IBM370系列有115、125、135、158、168等由低檔到高檔的多種型號機器。從匯編語言、機器語言程序設計者看到的概念性結構相同，均是由中央處理機/主存，通道、設備控制器，外設4級構成。其中，中央處理機都有相同的機器指令和匯編指令系統，只是指令的分析、執行在低檔機上采用順序進行，在高檔機上采用重疊、流水或其它并行處理方式。 （2）相同的組成可有多種不同的實現。如主存器件可用雙極型的，也可用MOS型的；可用VLSI單片，也可用多片小規模集成電路組搭。 （3）計算機的系統結構不同，會使采用的組成技術不同，反之組成也

8、會影響結構。如為實現A:=B+CD:=E*F,可采用面向寄存器的系統結構，也可采用面向主存的三地址尋址方式的系統結構。要提高運行速度，可讓相加與相乘并行，為此這兩種結構在組成上都要求設置獨立的加法器和乘法器。但對面向寄存器的系統結構還要求寄存器能同時被訪問，而對面向主存的三地址尋址方式的系統結構并無此要求，倒是要求能同時形成多個訪存操作數地址和能同時訪存。又如微程序控制是組成影響結構的典型。通過改變控制存儲器中的微程序，就可改變系統的機器指令，改變結構。如果沒有組成技術的進步，結構的進展是不可能的。 綜上所述，系統結構的設計必須結合應用考慮，為軟件和算法的實現提供更多更好的支持，同時要考慮可能

9、采用和準備采用的組成技術。應避免過多地或不合理地限制各種組成、實現技術的采用和發展，盡量做到既能方便地在低檔機上用簡單便宜的組成實現，又能在高檔機上用復雜較貴的組成實現，這樣，結構才有生命力；組成設計上面決定于結構，下面受限于實現技術。然而，它可與實現折衷權衡。例如，為達到速度要求，可用簡單的組成但卻是復雜的實現技術，也可用復雜的組成但卻是一般速度的實現技術。前者要求高性能的器件，后者可能造成組成設計復雜化和更多地采用專用芯片。 組成和實現的權衡取決于性能價格比等因素；結構、組成和實現所包含的具體內容隨不同時期及不同的計算機系統會有差異。軟件的硬化和硬件的軟件都反映了這一事實。VLSI的發展更

10、使結構組成和實現融為一體，難以分開。 4.什么是透明性概念？對計算機系統結構，下列哪些是透明的？哪些是不透明的？ 存儲器的模m交叉存取；浮點數據表示；I/O系統是采用通道方式還是外圍處理機方式；數據總線寬度；字符行運算指令；陣列運算部件；通道是采用結合型還是獨立型；PDP-11系列的單總線結構；訪問方式保護；程序性中斷；串行、重疊還是流水控制方式；堆棧指令；存儲器最小編址單位；Cache存儲器。 答：透明指的是客觀存在的事物或屬性從某個角度看不到。 透明的有：存儲器的模m交叉存取；數據總線寬度；陣列運算部件；通道是采用結合型還是獨立型；PDP-11系列的單總線結構串行、重疊還是流水控制方式；C

11、ache存儲器。 不透明的有：浮點數據表示；I/O系統是采用通道方式還是外圍處理機方式；字符行運算指令；訪問方式保護；程序性中斷；堆棧指令；存儲器最小編址單位。 5.從機器（匯編）語言程序員看，以下哪些是透明的？ 指令地址寄存器；指令緩沖器；時標發生器；條件寄存器；乘法器；主存地址寄存器；磁盤外設；先行進位鏈；移位器；通用寄存器；中斷字寄存器。 答：透明的有：指令緩沖器、時標發生器、乘法器、先進先出鏈、移位器、主存地址寄存器。 6.下列哪些對系統程序員是透明的？哪些對應用程序員是透明的？ 系列機各檔不同的數據通路寬度；虛擬存儲器；Cache存儲器；程序狀態字；“啟動I/O”指令；“執行”指令；

12、指令緩沖寄存器。 答：對系統程序員透明的有：系列機各檔不同的數據通路寬度；Cache存儲器；指令緩沖寄存器； 對應用程序員透明的有：系列機各檔不同的數據通路寬度；Cache存儲器；指令緩沖寄存器；虛擬存儲器；程序狀態字；“啟動I/O”指令。 note:系列機各檔不同的數據通路寬度、Cache存貯器、指令緩沖寄存器屬于計算機組成，對系統和程序員和應用程序員都是透明的。 虛擬存貯器、程序狀態字、“啟動I/O”指令，對系統程序員是不透明的，而對應用程序員卻是透明的。“執行”指令則對系統程序員和應用程序員都是不透明的。 7.想在系列機中發展一種新型號機器，你認為下列哪些設想是可以考慮的，哪些則不行的？

13、為什么？ 新增加字符數據類型和若干條字符處理指令，以支持事務處理程序的編譯。 （2）為增強中斷處理功能，將中斷分級由原來的4級增加到5級，并重新調整中斷響應的優先次序。 （3）在CPU和主存之間增設Cache存儲器，以克服因主存訪問速率過低而造成的系統性能瓶頸。 （4）為解決計算誤差較大，將機器中浮點數的下溢處理方法由原來的恒置“1”法，改為用ROM存取下溢處理結果的查表舍入法。 （5）為增加尋址靈活性和減少平均指令字長，將原等長操作碼指令改為有3類不同碼長的擴展操作碼；將源操作數尋址方式由操作碼指明改成如VAX-11那種設尋址方式位字段指明。 （6）將CPU與主存間的數據通路寬度由16位擴展

14、成32位，以加快主機內部信息的傳送。 （7）為減少公用總路線的使用沖突，將單總線改為雙總線。 （8）把原0號通用寄存器改作堆棧指示器。 答：可以考慮的有：1,3,4,6,7。不可以考慮的有：2,5,8。 原則是看改進后能否保持軟件的可移植性。 P.S.為了能使軟件長期穩定，就要在相當長的時期里保證系統結構基本不變，因此在確定系列結構時要非常慎重。其中最主要是確定好系列機的指令系統、數據表示及概念性結構。既要考慮滿足應用的各種需要和發展，又要考慮能方便地采用從低速到高速的各種組成的實現技術，即使用復雜、昂貴的組成實現時，也還能充分發揮該實現方法所帶來的好處。 8.并行處理計算機除分布處理、MPP

15、和機群系統外，有哪4種基本結構？列舉它們各自要解決的主要問題。 答：除了分布處理，MPP和機群系統外，并行處理計算機按其基本結構特征可分為流水線計算機，陣列處理機，多處理機和數據流計算機四種不同的結構。 流水線計算機主要通過時間重疊，讓多個部件在時間上交劃重疊地并行招待運算和處理，以實現時間上的并行。它主要應解決：擁塞控制，沖突防止，流水線調度等問題。 陣列處理機主要通過資源重復實現空間上的并行。它主要應解決：處理單元靈活、規律的互連模式和互連網絡設計，數據在存儲器中的分布算法等問題。 多處理機主要通過資源共享，讓一組計算機在統一的操作系統全盤控制下，實現軟件和硬件各級上的相互作用，達到時間和

16、空間上的異 步并行。它主要應解決：處理機間互連等硬件結構，進程間的同上步和通訊，多處理機調度等問題。 數據流計算機設有共享變量的概念，指令執行順序只受指令中數據的相關性制約。數據是以表示某一操作數或參數已準備就緒的數據令牌直接在指令之間傳遞。它主要應解決：研究合適的硬件組織和結構，高效執行的數據流語言等問題。 9.計算機系統的3T性能目標是什么？ 答：計算機系統的3T性能目標是 1TFLOPS計算能力,1TBYTE主存容量 和 1TBYTES的I/O帶寬第二章數據表示與指令系統 1.尾數的rm進制數位m和尾數的二進制數位m的關系 存在m=m/log2(rm)這種關系是因為，在機器中，一個rm進

17、制的數位是用log2(rm)個機器數位來表示的。 假設rm=8，尾數為20，則m=2,八進制數20轉換成二進制數為10000，其二進制數位，即機器數位m=5。2=5/log2(8)。 note:這里的等號并不表示純粹數學意義上的“等于”。 2.可表示的尾數個數公式 rmm(rm-1)/rm。 對于rm進制的數來說，每個數位均可以有0到rm-1，即rm個碼。 m個rm進制數位共有rmm種編碼。但課本中討論的是規格化數，即尾數的小數點后第一個數位不為零的數，所以，應該去掉小數點后第一個數位是0的那些非規格化的數。顯然，非規格化數的個數占了全部尾數編碼總數的1/rm的比例，所以可表示的浮點數規格化的

18、尾數個數應該是：rmm（1-1/rm)。 exercises: 1.某模型時機共有7種指令，各指令使用頻率分別為0.35，0.25，0.20，0.10，0.05，0.03，0.02，有8個通用數據寄存器和2個變址寄存器。 （1） 要求操作碼的平均長最短，請設計操作碼的編碼，并計算所設計操作碼的平均長。（4分） （2） 設計8位長度的寄存器寄存器型指令3種，16位長度的寄存器存儲器變址尋址方式指令4條，變址范圍不小于正、負127。請寫出指令格式，并給出各字段的長度和操作碼編碼。（6分） 解答： (1)全Huffman編碼的平均碼長是可用的二進制位編碼中平均碼長最短的編碼。 全Huffman編碼的

19、平均碼長=2*(0.35+0.25+0.20)+3*0.10+4*0.05+5*(0.02+0.03)=2.35 (2) 由于有8個通用數據寄存器和2個變址寄存器，所以通用寄存器用3位表示，變址寄存器用1位表示,8位的寄存器-寄存器型指令，3個操作碼編碼為00、01、10，16位的寄存器-存儲器變址尋址方式指令， 4個操作碼編碼為1100、1101、1110、1111，2位 3位 3位OP R1 R2操作碼 寄存器1 寄存器24位 3位 1位 8位OP R1 X d操作碼 寄存器1 變址寄存器 相對位移 主存邏輯地址1.數據結構和機器的數據表示之間是什么關系？確定和引入數據表示的基本原則是什么

20、？ 答：數據表示是能由硬件直接識別和引用的數據類型。數據結構反映各種數據元素或信息單元之間的結構關系。 數據結構要通過軟件映象變換成機器所具有的各種數據表示實現，所以數據表示是數據結構的組成元素。不同的數據表示可為數據結構的實現提供不同的支持，表現在實現效率和方便性不同。數據表示和數據結構是軟件、硬件的交界面。 除基本數據表示不可少外，高級數據表示的引入遵循以下原則： （1）看系統的效率有否提高，是否養活了實現時間和存儲空間。 （2）看引入這種數據表示后，其通用性和利用率是否高。 2.標志符數據表示與描述符數據表示有何區別？描述符數據表示與向量數據表示對向量數據結構所提供的支持有什么不同？ 答

21、：標志符數據表示與描述符數據表示的差別是標志符與每個數據相連，合存于同一存儲單元，描述單個數據的類型特性;描述符是與數據分開存放，用于描述向量、數組等成塊數據的特征。 描述符數據表示為向量、數組的的實現提供了支持，有利于簡化高級語言程序編譯中的代碼生成，可以比變址法更快地形成數據元素的地址。但描述符數據表示并不支持向量、數組數據結構的高效實現。而在有向量、數組數據表示的向量處理機上，硬件上設置有豐富的賂量或陣列運算指令，配有流水或陣列方式處理的高速運算器，不僅能快速形成向量、數組的元素地址，更重要的是便于實現把向量各元素成塊預取到中央處理機，用一條向量、數組指令流水或同時對整個向量、數組高速處

22、理如讓硬件越界判斷與元素運算并行。這些比起用與向量、陣列無關的機器語言和數據表示串行實現要高效的多。 3.堆棧型機器與通用寄存器型機器的主要區別是什么？堆棧型機器系統結構為程序調用的哪些操作提供了支持？ 答：通用寄存器型機器對堆棧數據結構實現的支持是較差的。表現在：(1)堆棧操作的指令少，功能單一；(2)堆棧在存儲器內，訪問堆棧速度低；(3)堆棧通常只用于保存于程序調用時的返回地址，少量用堆棧實現程序間的參數傳遞。 而堆棧型機器則不同，表現在：(1)有高速寄存器組成的硬件堆棧，并與主存中堆棧區在邏輯上組成整體，使堆棧的訪問速度是寄存器的，容量是主存的；(2)豐富的堆棧指令可對堆棧中的數據進行各

23、種運算和處理；(3)有力地支持高級語言的編譯；(4)有力地支持子程序的嵌套和遞歸調用。 堆棧型機器系統結構有力地支持子程序的嵌套和遞歸調用。在程序調用時將返回地址、條件碼、關鍵寄存器的內容等全部壓入堆棧，待子程序返回時，再從堆棧中彈出。 4.設某機階值6位、尾數48位，階符和數符不在其內，當尾數分別以2、8、16為基時，在非負階、正尾數、規格化數情況下，求出其最小階、最大階、階的個數、最小尾數值、最大尾數值、可表示的最小值和最大值及可表示的規格化數的總個數。 解：依題意知：p=6 m=48 rm=2, 8, 16，m=m/log2(rm)，列下表： p=6,m=48,rm=2(m=48)p=6

24、,m=48,rm=8(m=16)p=6,m=48,rm=16(m=12)最小階(非負階，最小為0)000最大階(2p-1)26-126-126-1最小尾數值(rm(-1)1/21/81/16最大尾數值(1-rm(-m)1-2(-48)1-8(-16)，即(1-2(-48)1-16(-12)，即(1-2(-48)可表示的最小值1/21/81/16可表示的最大值263*(1-2(-48)863*(1-8(-16)1663*(1-16(-12)階的個數(2p)262626可表示的尾數的個數248*(2-1)/2816*(8-1)/81612*(16-1)/16可表示的規格化數的個數26*248*(2

25、-1)/226*816*(8-1)/826*1612*(16-1)/16note:可表示的最小值=rm(最小階)*最小尾數值=rm0*rm(-1)=rm(-1); 可表示的最大值=rm(最大階)*最大尾數值=rm(2p-1)*(1-rm(-m); 可表示的尾數的個數=rmm*(rm-1)/rm; 可表示的規格化數的個數=階的個數*尾數的個數=2p*rmm*(rm-1)/rm。 5.（1）浮點數系統使用的階基rp=2,階值位數p=2,尾數基值rm=10，以rm為基的尾數位數m=1,按照使用的倍數來說，等價于m=4, 試計算在非負階、正尾數、規格化情況下的最小尾數值、最大尾數值、最大階值、可表示的

26、最小值和最大值及可表示數的個數。 （2）對于rp=2,p=2,rm=4,m=2,重復以上計算。 解：依題意列下表： p=2,rm=10,m=1p=2,rm=4,m=2最小尾數值10-1=0.14-1=0.25最大尾數值1-10-1=0.91-4-2=15/16最大階值2p-1=33可表示的最小值0.10.25可表示的最大值103*0.9=90043*15/16=60可表示數的個數3648題中“按照使用的倍數來說，等價于m=4,” 這個m=4,因為2310=fbyte 通道極限流量應大于或等于設備對通道要求的流量fbyte。 如果字節多路通道上所掛設備臺數為m,設備的速率為fi，為了不丟失信息，

27、應滿足： 1/(TS+TD)=m*fi fi也就是設備發出字節傳送請求間隔時間(500s)的倒數，所以： m=1/(TS+TD)*f)=500/(9.8+0.2)=50(臺) (2)設備B,C,E,F可以掛在此通道上，設備A,D則不能。 剖析： 思路一：從傳送字節速率上入手。 AF是高速設備，應掛接在選擇通道上，選擇通道的極限流量為： fmax.select=N/(TS+N*TD)=1/(TS/N)+TD)=1/(9.8/1024)+0.2)=1/0.21(約) 通道上所掛設備的最大速率fi.max應小于或等于通道的極限流量。 由表3-5可得出 設備ABCDEF傳送速率(B/s)1/0.21/

28、0.251/0.51/0.191/0.41/0.21所以，B、C、E、F可掛在該通道上。A、D不能。 思路二：從傳送字節時間上入手。 對于高速設備，由于一次傳送字節數不少于1024byte 該通道一次傳送數據的時間為9.8s+10240.2s214.6s 由表3-5可得出每臺設備發送1024字節的時間間隔分別為: 設備ABCDEF傳送時間(s)204.8256512194.56409.6215.04為使數據不丟失，B、C、E、F可掛在該通道上。A、D不能。 6.某字節多路通道連接6臺外設，某數據傳送速率分別如表中所列。 設備123456傳送速率(KB/s)5015100254020(1)計算所

29、有設備都工作時的通道實際最大流量： (2)如果設計的通道工作周期使通道極限流量恰好與通道最大流量相等，以滿足流量設計的基本要求，同時讓速率越高的設備被響應的優先級越高。當6臺設備同時發出請求開始，畫出此通道在數據傳送期內響應和處理各外設請求的時間示意圖。由此你發現了什么問題? (3)在(2)的基礎上，在哪臺設備內設置多少個字節的緩沖器就可以避免設備信息丟失?那么，這是否說書中關于流量設計的基本要求是沒有必要的了呢?為什么? 解： (1)實際最大流量50+15+l00+25+40+20250KB/S。 (2)通道響應和處理各設備請求的時間示意圖 由此發現由于高速設備的響應優先級高，使低速設備2造

30、成數據丟失。 (3)在2中各設兩個字節的緩沖區即可。這并不說明流量設計的基本條件是不必要的，因為若基本條件不滿足，無論設備優先級如何確定總有設備的信息會丟失。 剖析： (2)由各設備的傳送字節速率可解其連續發出傳送請求的時間間隔分別為： 設備123456發申請間隔(s)2067(約)104025507.通道型I/O系統由一個字節多路通道A(其中包括兩個子通道Al和A2)，兩個數組多路通道B1和B2及一個選擇通道C構成，各通道所接設備和設備的數據傳送速率如表所示。 (1)分別求出各通道應具有多大設計流量才不會丟失信息； (2)設I/O系統流量占主存流量的1/2時才算流量平衡，則主存流量應達到多少

31、? 通道號所接設備的數據傳送速率(KB/s)字節多路通道子通道A150 35 20 20 50 35 20 20子通道A250 35 20 20 50 35 20 20數組多路通道B1500 400 350 250數組多路通道B2500 400 350 250選擇通道C500 400 350 250解： (1)要不丟失信息，各通道需要達到的流量：字節多路通道子通道A1:0.25KB/S;字節多路通道子通道A2:0.25KB/S;數組多路通道B1:500KB/s;數組多路通道B2:500KB/s;選擇通道C:500KB/s。 (2)主存流量應達到4MB/S。 剖析: (1)設備要求字節多路通道或

32、其子通道的實際最大流量，是該通道所接各設備的字節傳送速率之和; 設備要求數組多路通道或選擇通道的實際最大流量，是該通道所接各設備的字節傳送速率中的最大者。 (2)I/O系統中，各種通道和子通道可以并行工作，因此，I/O系統的最大流量應等于各通道最大流量之和。第四章存儲體系 解決Cache的透明性所帶來的問題，和中央處理機寫Cache，使主存內容跟不上Cache內對應內容的變化造成的不一致的問題的關鍵是選擇好更新主存內容的算法，一般有兩種寫直達法(存直達法)和寫回法(即抵觸修改法)兩種。 寫直達法，又稱存直達法，是指在CPU對Cache進行寫操作時，如果命中Cache，不僅將數據寫入Cache，而且寫入主存，使兩者的對應內容統一起來，這樣，當Cache中的塊被替換時，就不必再花時間寫回主存了。 寫回法，又稱抵觸修改法，是指在CPU對Cache進行寫操作時，如果命中Cache，就只將數據寫入Cache，而暫時不寫入