北京工業(yè)大學(xué) 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 復(fù)習(xí)

1、計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)概念點(diǎn),不含計(jì)算方法,僅有部分提示,整理內(nèi)容僅供參考計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)：指機(jī)器語(yǔ)言程序的設(shè)計(jì)者或是編譯程序設(shè)計(jì)者所看到的計(jì)算機(jī)系統(tǒng)的概念性結(jié)構(gòu)與功能特性。 透明性：一種本來(lái)存在，有差異的事物和屬性，從某種角度上看又好像不存在的現(xiàn)象，被稱為是“透明性”（ 例如，高級(jí)程序員看不到各種不同類型機(jī)器的差異性，就是一個(gè)明顯的例證。）計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) ：數(shù)據(jù)表示；寄存器定義；指令系統(tǒng)；中斷系統(tǒng)；存儲(chǔ)系統(tǒng)；輸入輸出結(jié)構(gòu)；機(jī)器工作狀態(tài)；信息保護(hù)計(jì)算機(jī)組成：數(shù)據(jù)通路的寬度；專用部件的設(shè)置；各功能部件；控制機(jī)構(gòu)的組成方式；緩沖技術(shù)；可靠性技術(shù)的采用和方式的選擇計(jì)算機(jī)實(shí)現(xiàn)：邏輯設(shè)計(jì)的物理實(shí)現(xiàn)FLYNN分類法

2、：?jiǎn)沃噶盍鲉螖?shù)據(jù)流( SISD ),傳統(tǒng)順序處理計(jì)算機(jī) 單指令流、多數(shù)據(jù)流(SIMD )結(jié)構(gòu) , 陣列處理機(jī)、并行處理機(jī) 多指令流、單數(shù)據(jù)流( MISD )結(jié)構(gòu), 如RISC機(jī)、向量機(jī) 多指令流、多數(shù)據(jù)流( MIMD )結(jié)構(gòu), 多處理機(jī)系統(tǒng)計(jì)算機(jī)系統(tǒng)的設(shè)計(jì)原則：1.加速那些使用頻率高的部件提高整個(gè)計(jì)算機(jī)性能; 2. Amdahl定律; 3.程序訪問(wèn)局部性原理 Amdahl定律：系統(tǒng)中某一部件由于采用某種改進(jìn)的執(zhí)行方式后，整個(gè)系統(tǒng)的性能提高了，其衡量指標(biāo)為加速比。Amdahl定律可表示為：加速比Sp = Te / T0改進(jìn)后時(shí)間T0= Te1 可改進(jìn)部分占比f(wàn)e + fe性能提高倍數(shù) re 整理

3、得Sp=11-fe+fe/reCPU性能指標(biāo): TCPU=IN*CPI*Tc=指令總數(shù)*執(zhí)行每條指令所需平均周期數(shù)*時(shí)鐘周期CPI=CPIi*IiINMIPS=INTe*106=時(shí)鐘頻率RcCPI*106MFLOPS=程序中的浮點(diǎn)操作次數(shù)IFN執(zhí)行時(shí)間Te*106計(jì)算機(jī)系統(tǒng)的層次結(jié)構(gòu)(會(huì)排序,注意23級(jí))性能評(píng)價(jià)結(jié)果數(shù)據(jù)的處理方法: 算術(shù)性能平均法;幾何.;調(diào)和.;軟件兼容性要求:繼承軟件資產(chǎn)，保證軟件向后兼容和向上兼容數(shù)據(jù)類型:基本數(shù)據(jù)類型(二進(jìn)制數(shù)位及位串、整數(shù)及自然數(shù)、實(shí)數(shù)（浮點(diǎn)數(shù)）、邏輯數(shù)、十進(jìn)制數(shù)、字符等。二進(jìn)制數(shù)位是信息存儲(chǔ)的最基本單位，0和1，長(zhǎng)度為8時(shí)，構(gòu)成字節(jié)。);結(jié)構(gòu)數(shù)據(jù)類

4、型(一組由相互有關(guān)的數(shù)據(jù)元素復(fù)合而成的數(shù)據(jù)類型，這些數(shù)據(jù)元素可以是基本數(shù)據(jù)類型中的元素，也可以是結(jié)構(gòu)化數(shù)據(jù)類型本身中的元素如向量、數(shù)組、字符串、堆棧、隊(duì)列等。結(jié)構(gòu)化的數(shù)據(jù)類型除了可由用戶定義外，還有一種是系統(tǒng)數(shù)據(jù)類型，它們通常是在操作系統(tǒng)中被使用的，如堆棧、隊(duì)列等。);抽象數(shù)據(jù)類型;訪問(wèn)指針.數(shù)據(jù)表示：指在計(jì)算機(jī)中能由硬件直接辯認(rèn),指令系統(tǒng)可以直接調(diào) 用的數(shù)據(jù)類型。(實(shí)質(zhì)上是一個(gè)軟硬件取舍的問(wèn)題)自定義數(shù)據(jù)表示：由數(shù)據(jù)本身來(lái)表明數(shù)據(jù)類型，使計(jì)算機(jī)內(nèi)的數(shù)據(jù)具有自定義能力。分類:帶標(biāo)志符的數(shù)據(jù)表示,數(shù)據(jù)描述符優(yōu)點(diǎn)1.簡(jiǎn)化了指令系統(tǒng)2.容易檢出程序編制中的錯(cuò)誤3.簡(jiǎn)化了編譯程序4.支持?jǐn)?shù)據(jù)庫(kù)系統(tǒng)5.

5、簡(jiǎn)化了程序設(shè)計(jì)6.便于軟件測(cè)試，支持應(yīng)用軟件開(kāi)發(fā) 缺點(diǎn)1.數(shù)據(jù)字長(zhǎng)增加2.降低了指令的微觀執(zhí)行速度3.與其他計(jì)算機(jī)的兼容性差，硬件復(fù)雜程序定位方式:直接;靜態(tài);動(dòng)態(tài)(優(yōu)點(diǎn)：在程序執(zhí)行時(shí)由硬件形成主存物理地址，主存利用率高，多個(gè)用戶可以共享同一個(gè)程序段，支持虛擬存儲(chǔ)器實(shí)現(xiàn)。缺點(diǎn)：需要硬件支持，實(shí)現(xiàn)的算法比較復(fù)雜。)RISC設(shè)計(jì)思想的起源1.20%-80%定律2.系統(tǒng)設(shè)計(jì)中硬件和軟件之間折衷3.VLSI工藝技術(shù)發(fā)展主要技術(shù):1.流水線結(jié)構(gòu)和指令調(diào)度2.寄存器窗口3.優(yōu)化編譯技術(shù)復(fù)雜指令集計(jì)算機(jī)CISC特點(diǎn):1.指令的控制執(zhí)行是采用微程序控制技術(shù)，有專用的寄存器。2.控制器十分復(fù)雜，占用了大量CPU

6、芯片面積，有些復(fù)雜指令用的很少，難以用優(yōu)化編譯生成高效目標(biāo)代碼。3.處理器的執(zhí)行效率不高。4.指令系統(tǒng)與軟件之間語(yǔ)義差別越來(lái)越大，軟件設(shè)計(jì)任務(wù)十分繁重，整個(gè)設(shè)計(jì)風(fēng)格不是十分經(jīng)濟(jì)有效的。RISC特點(diǎn)1.指令格式簡(jiǎn)單化、規(guī)整化（寄存器-寄存器型）2.基本是單周期操作（指令功能和執(zhí)行周期權(quán)衡選擇）3.分開(kāi)的存取指令數(shù)據(jù)，引入多級(jí)Cache 4.面向寄存器堆的結(jié)構(gòu) 5.充分提高流水線效率（用各種技術(shù)減少相關(guān)阻塞）6.采用硬邏輯控制方式（少數(shù)采用微程序設(shè)計(jì)）7.采用優(yōu)化編譯技術(shù)，很好地支持高級(jí)語(yǔ)言存儲(chǔ)系統(tǒng)的三個(gè)特性:局部性;一致性(在容量大的存儲(chǔ)器中，一定能找到上層存儲(chǔ)信息的副本);包含性(副本修改，以

7、保持同一信息的一致性);計(jì)算機(jī)存儲(chǔ)系統(tǒng)三個(gè)基本參數(shù): 存儲(chǔ)容量S(以字節(jié)數(shù)表示，單位為B、KB、MB、GB、TB等);存儲(chǔ)器速度T(存儲(chǔ)器訪問(wèn)周期，與命中率有關(guān));存儲(chǔ)器價(jià)格C(表示單位容量的平均價(jià)值單位為C/bit或C/KB)存儲(chǔ)層次結(jié)構(gòu)解決頻帶平衡的三種方法:1.多個(gè)存儲(chǔ)器并行工作，并用并行訪問(wèn)和交叉訪問(wèn)等方法 2.設(shè)置各種緩沖存儲(chǔ)器 3.采用Cache存儲(chǔ)系統(tǒng)。引入CACHE的目的: 提高CPU對(duì)存儲(chǔ)器的訪問(wèn)速度 特點(diǎn): 容量比較小但速度比主存高很多，接近于CPU的速度。地址映像是指某一數(shù)據(jù)在主存中的地址與在緩存中的地址兩者之間的關(guān)系。CACHE寫(xiě)操作的更新策略 全寫(xiě)法: Cache及主

8、存與內(nèi)容同時(shí)更新CACHE命中率的影響因素:CACHE容量,CACHE塊大小,地址映像方式LRU最近最少使用法:是依據(jù)各塊使用的情況，總是選擇那個(gè)最近最少使用的塊被替換。這種方法比較好的反映了程序局部性規(guī)律。因?yàn)樽罱钌偈褂玫膲K，很可能在將來(lái)的近期也很少使用，所以LRU法的命中率比較高。缺點(diǎn)：實(shí)現(xiàn)起來(lái)比較困難，它不但要記錄每塊使用次數(shù)的多少，而且要反映出近期使用的次數(shù)。 Cache系統(tǒng)的加速比 等效的訪問(wèn)周期為T(mén) Tc:Cache的訪問(wèn)周期Tm:主存儲(chǔ)器的訪問(wèn)周期;Hc:Cache命中率存儲(chǔ)系統(tǒng)的訪問(wèn)效率：指高一級(jí)存儲(chǔ)器的訪問(wèn)速度(容量小速度高的一級(jí))與系統(tǒng)等效的訪問(wèn)速度之比。存儲(chǔ)保護(hù):1.加

9、界保護(hù)法：在CPU中設(shè)置了多個(gè)界限寄存器，由系統(tǒng)軟件經(jīng)特權(quán)指令指定，禁止越界。(當(dāng)程序運(yùn)行過(guò)程中，每當(dāng)訪問(wèn)主存時(shí)，首先將訪問(wèn)地址與上下界寄存器進(jìn)行比較，如果在此區(qū)域之內(nèi)，則允許訪問(wèn)；如果不在此區(qū)域之內(nèi)，即小于上界，大于下界，即說(shuō)明出現(xiàn)了錯(cuò)誤，稱為越界錯(cuò)。這種保護(hù)方式是對(duì)存儲(chǔ)區(qū)的保護(hù)、運(yùn)用于段式管理.)2. 鍵保護(hù)方式: 每次訪問(wèn)主存，首先進(jìn)行鍵號(hào)比較，如果鍵號(hào)相等才允許訪問(wèn)。如同一把鑰匙開(kāi)一把鎖。存放鍵與程序鍵鍵號(hào)的分配，由操作系統(tǒng)完成 3. 環(huán)保護(hù)方式：將系統(tǒng)程序和各用戶程序按其功能的性質(zhì)和要求分為幾個(gè)級(jí)別，分別授予不同的權(quán)限，如系統(tǒng)程序?qū)Π踩囊蟊容^高，授權(quán)級(jí)別就比較高，用戶程序的級(jí)別就

10、可以低些流水線的基本結(jié)構(gòu)中的三大部分：鎖存器、時(shí)鐘、功能段（站）流水線特點(diǎn):1）流水一定重疊，比重疊更苛刻。2）一條流水線通常由多個(gè)流水段組成。3）每段有專用功能部件，各部件順序連接，不斷流.4）流水線有建立時(shí)間、滿載時(shí)間、排空時(shí)間.5）各段時(shí)間盡量短、一致，不一致時(shí)最慢子過(guò)程為瓶頸。6）給出的最大吞吐率等指標(biāo)，為滿負(fù)載最佳指標(biāo)。流水線的分級(jí)：1.按處理的級(jí)別分級(jí)(操作部件級(jí)-將復(fù)雜的算邏運(yùn)算組成流水工作方式；指令級(jí)-把一條指令解釋過(guò)程分成多個(gè)子過(guò)程;處理機(jī)級(jí)或宏流水線級(jí)-由兩個(gè)以上處理機(jī)串行地對(duì)同一數(shù)據(jù)流進(jìn)行處理，每個(gè)處理機(jī)完成某一專門(mén)任務(wù)，各個(gè)處理機(jī)所得到的結(jié)果需存放在與下一個(gè)處理機(jī)所共享

11、的存儲(chǔ)器中.) 2. 按功能分類(單功能流水線-只能實(shí)現(xiàn)一種固定的專門(mén)功能的流水線;多功能流水線-通過(guò)各站間的不同連接方式可以同時(shí)或不同時(shí)地實(shí)現(xiàn)多種功能的流水線)3. 按工作方式分類(靜態(tài)流水線-在同一時(shí)間內(nèi)各功能段只能按一種運(yùn)算（功能）的連接方式工作;動(dòng)態(tài)流水線-在同一時(shí)間內(nèi)各功能段允許按多種不同運(yùn)算（功能）的連接方式工作。) (靜態(tài)流水線僅當(dāng)指令都是同一類型時(shí)才能連續(xù)不斷地執(zhí)行。當(dāng)從一種功能方式變?yōu)榱硪环N功能方式時(shí)，必須先排空流水線，然后再切換成另一種功能進(jìn)行流水處理。)4. 按連接方式（流水線中是否有反饋回路）分類(線性流水線-從輸入到輸出，每個(gè)功能段只允許經(jīng)過(guò)一次，不存在反饋回路;非線

12、性流水線-存在反饋回路，從輸入到輸出過(guò)程中，某些功能段將數(shù)次通過(guò)流水線，這種流水線常用于進(jìn)行遞歸運(yùn)算)流水線性能指標(biāo):吞吐率Tp,加速比Sp,效率最大吞吐率：流水線達(dá)到穩(wěn)定狀態(tài)后可獲得的吞吐率。（1）TPmax=1/t（理想情況） （2）TPmax=1/ maxt1，t2，t3，t4流水線實(shí)際吞吐率m：指令流水線的段數(shù)；Dt0: 各段經(jīng)過(guò)的時(shí)間； n：指令條數(shù)。效率=n個(gè)任務(wù)實(shí)際占用的時(shí)空區(qū)m個(gè)段總得時(shí)空區(qū) 加速比Sp=T非流水T流水 對(duì)一個(gè)周期能發(fā)射多條指令計(jì)算機(jī)有超標(biāo)量、超流水、超長(zhǎng)指令字計(jì)算機(jī)，此外還有數(shù)據(jù)流計(jì)算機(jī)也屬于多發(fā)射結(jié)構(gòu)。 向量的處理方法:水平;垂直(適用于流水);分組縱橫向量

13、處理機(jī)的結(jié)構(gòu):由向量數(shù)據(jù)表示和流水線技術(shù)相結(jié)合構(gòu)成的向量流水處理機(jī)。并行性概念:在數(shù)值計(jì)算，數(shù)據(jù)處理，信息處理或人工智能求解過(guò)程中，可能存在某些能同時(shí)進(jìn)行運(yùn)算或操作的部分。在同一時(shí)刻或同一時(shí)間間隔內(nèi)完成多個(gè)性質(zhì)相同或不同的任務(wù)。并行性的開(kāi)發(fā)還可以按程序大小劃分不同粒度的開(kāi)發(fā)方式。并行粒度或顆粒規(guī)模- 衡量軟件進(jìn)程所含計(jì)算量的尺度。測(cè)量方法是數(shù)一下顆粒（程序段）中的指令數(shù)目。一般用細(xì)、中、粗來(lái)描述，決定并行處理的基本程序段。并行性粒度：每次并行處理的規(guī)模大小。用字母G表示 G=TW/TCTW：所有處理器進(jìn)行計(jì)算的時(shí)間總和；TC：所有處理器進(jìn)行通信的時(shí)間總和。（設(shè)系統(tǒng)共有P個(gè)處理器）;當(dāng)TC較大時(shí)

14、，通信量大，則G較小處理粒度較細(xì)。反之對(duì)于粗粒度的并行，通信量較小。粒度小結(jié):1.細(xì)粒度并行性常在指令級(jí)或循環(huán)級(jí)上借助于并行化或向量化編譯器來(lái)進(jìn)行開(kāi)發(fā)的。2.任務(wù)或作業(yè)步驟（過(guò)程級(jí)）中粒度并行性開(kāi)發(fā)需要程序員和編譯器的共同作用。3.開(kāi)發(fā)程序作業(yè)級(jí)的粗粒度并行性主要取決于高效的操作系統(tǒng)和所用算法的效率。4.共享變量通信常用于支持中、細(xì)粒度計(jì)算。消息傳遞型多計(jì)算機(jī)用于中粒度和粗粒度的計(jì)算。通常情況下，粒度越細(xì)，并行性潛力越大，通信和調(diào)度的開(kāi)銷也越大。細(xì)粒度能提供較高的并行度，但與粗粒度計(jì)算相比，其通信開(kāi)銷也較大。大規(guī)模并行性通常是在細(xì)粒度級(jí)上開(kāi)發(fā)。如：SIMD或MIMD計(jì)算機(jī)上開(kāi)發(fā)的數(shù)據(jù)并行性。陣

15、列處理機(jī)分類根據(jù)存貯器采用的組成方式不同分成兩種基本構(gòu)成。(1)分布存貯的陣列處理機(jī):各個(gè)處理單元設(shè)有局部存貯器存放分布式數(shù)據(jù)，只能被本處理單元直接訪問(wèn)。此種局部存貯器稱為處理單元存貯器PEM。在控制部件CU內(nèi)設(shè)有一個(gè)用來(lái)存放程序的主存貯器CUM。整個(gè)系統(tǒng)在CU統(tǒng)一控制下運(yùn)行系統(tǒng)程序的用戶程序。執(zhí)行主存中的用戶程序指令播送給各個(gè)PE，控制PE并行地執(zhí)行。特點(diǎn)：處理器陣列一般是通過(guò)CU接到一臺(tái)管理處理機(jī)SC上，SC一般是一種通用計(jì)算機(jī)，用于管理整個(gè)系統(tǒng)的全部資源，完成系統(tǒng)維護(hù)、輸入輸出、用戶程序的匯編及向量化編譯、作業(yè)調(diào)度、存貯分配、設(shè)備管理、文件管理等操作系統(tǒng)的功能。（2）集中式共享存貯的陣列

16、處理機(jī):特點(diǎn),每個(gè)PE沒(méi)有局部存儲(chǔ)器，存儲(chǔ)模塊以集中形式為所有PE共享，互連網(wǎng)絡(luò)ICN受CU控制。 恒等置換I（Xn-1Xn-2X1X0）= Xn-1Xn-2X1X0直連交換置換E（ Xn-1Xn-2X1X0 ）= Xn-1Xn-2X1X0第0位取反方體置換Cubek為二進(jìn)制第k位取反均勻洗牌置換 二進(jìn)制左移一位逆均勻洗牌-1二進(jìn)制右移一位蝶式置換（Butterfly）二進(jìn)制首尾互換子蝶式（subbutterfly）(k) 置換二進(jìn)制0位與k位互換超蝶式置換(k) :二進(jìn)制最高位與第k位互換移數(shù)置換:將輸入端數(shù)組循環(huán)移動(dòng)一定的位置向輸出端傳輸。其函數(shù)表達(dá)式：a(X)=(X+k) mod N,

17、0X N ,k為常數(shù)，指移動(dòng)的位置值加減2i（PM2I）置換:實(shí)際上是一種移數(shù)置換包含2n個(gè)互連函數(shù)，其表達(dá)式為PM2+i(j)=j+2 i(mod N）; PM2-i(j)=j-2 i(mod N)式中，0jN-1，0in-1，n=log2N互聯(lián)網(wǎng)絡(luò)設(shè)計(jì)的四個(gè)特征多處理機(jī)結(jié)構(gòu)分類:共享存儲(chǔ)型(緊耦合系統(tǒng)),點(diǎn)對(duì)點(diǎn)型/分布型(松耦合多處理機(jī)系統(tǒng))多處理機(jī)互連結(jié)構(gòu)（總線、交叉開(kāi)關(guān)、多端口存儲(chǔ)器、多級(jí)互聯(lián)網(wǎng)）總線結(jié)構(gòu)：把所有功能模塊（或部件、或計(jì)算機(jī)）連接到一條公共通信通路上，又稱為分時(shí)或公共總線.交叉開(kāi)關(guān)網(wǎng)絡(luò):包含一組縱橫開(kāi)關(guān)陣列，把縱向的處理機(jī)P及I/O通道與橫向的存儲(chǔ)器模塊M連接起來(lái)，使每個(gè)

18、處理器都有有它單獨(dú)可用的通路與存儲(chǔ)器模塊相連，這樣可以加大頻帶寬度，每個(gè)交叉點(diǎn)都有開(kāi)關(guān)、多路控制轉(zhuǎn)換及仲裁部件。多端口存儲(chǔ)器互連方式:每個(gè)存貯器模塊有多個(gè)存取端口，將分布在交叉開(kāi)關(guān)矩陣中的控制，轉(zhuǎn)換和優(yōu)先級(jí)仲裁邏輯分別移到相應(yīng)存貯器模塊的接口中，構(gòu)成多端口存貯器的結(jié)構(gòu)。多級(jí)互連網(wǎng): MIMD和SIMD計(jì)算機(jī)都使用多級(jí)網(wǎng)絡(luò)。每一級(jí)都用了多個(gè)a×b開(kāi)關(guān)，相鄰各級(jí)開(kāi)關(guān)之間都有固定的級(jí)間連接。為了在輸入和輸出之間建立所需的連接，可用動(dòng)態(tài)設(shè)置開(kāi)關(guān)的狀態(tài)來(lái)實(shí)現(xiàn)?？偩€仲裁算法:1. 靜態(tài)優(yōu)先級(jí)算法-為每個(gè)連到總線上的處理機(jī)（或計(jì)算機(jī)模塊）分配一個(gè)唯一的固定優(yōu)先級(jí)。優(yōu)點(diǎn)：算法簡(jiǎn)單，易實(shí)現(xiàn).缺點(diǎn)：優(yōu)先級(jí)低的處理機(jī)將很少有機(jī)會(huì)使用總線 2. 平等算法：以輪轉(zhuǎn)方式將總線按固