計(jì)算機(jī)體系結(jié)構(gòu)期末復(fù)習(xí)資料

年4月19日計(jì)算機(jī)體系結(jié)構(gòu)期末復(fù)習(xí)資料文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。第一章 計(jì)算機(jī)體系結(jié)構(gòu)的基本概念層次結(jié)構(gòu)——計(jì)算機(jī)系統(tǒng)能夠按語(yǔ)言的功能劃分為多級(jí)層次結(jié)構(gòu)，每一層以不同的語(yǔ)言為特征。第一級(jí)微程序機(jī)器級(jí)。第二級(jí)—機(jī)器語(yǔ)言。第三級(jí)—操作系統(tǒng)虛擬機(jī)。第四級(jí)—匯編語(yǔ)言虛擬機(jī)。第五級(jí)—高級(jí)語(yǔ)言虛擬機(jī)。第六級(jí)—應(yīng)用語(yǔ)言虛擬機(jī)體系結(jié)構(gòu)——程序員所看到的計(jì)算機(jī)的屬性，即概念性結(jié)構(gòu)與功能特性。透明性——在計(jì)算機(jī)技術(shù)中，對(duì)原來存在的事物或?qū)傩?，從某一角度來看又仿佛不存在的概念稱為透明性。系列機(jī)——在一個(gè)廠家生產(chǎn)的具有相同的體系結(jié)構(gòu)，但具有不同的組成和實(shí)現(xiàn)的一系列不同型號(hào)的機(jī)器。軟件兼容——同一個(gè)軟件能夠不加修改地運(yùn)行于體系結(jié)構(gòu)相同的各檔機(jī)器上，而且它們所獲得的結(jié)果一樣，差別只在于運(yùn)行的時(shí)間不同。兼容機(jī)——不同廠家生產(chǎn)的、具有相同體系結(jié)構(gòu)的計(jì)算機(jī)。計(jì)算機(jī)組成——計(jì)算機(jī)體系結(jié)構(gòu)的邏輯實(shí)現(xiàn)。計(jì)算機(jī)實(shí)現(xiàn)——計(jì)算機(jī)組成的物理實(shí)現(xiàn)。存儲(chǔ)程序計(jì)算機(jī)（馮·諾依曼結(jié)構(gòu)）——采用存儲(chǔ)程序原理，將程序和數(shù)據(jù)存放在同一存儲(chǔ)器中。指令在存儲(chǔ)器中按其執(zhí)行順序存儲(chǔ)，由指令計(jì)數(shù)器指明每條指令所在的單元地址。并行性——在同一時(shí)刻或同一時(shí)間間隔內(nèi)完成兩種或兩種以上性質(zhì)相同或不同的工作。響應(yīng)時(shí)間——從事件開始到結(jié)束之間的時(shí)間，也稱執(zhí)行時(shí)間。測(cè)試程序——用于測(cè)試計(jì)算機(jī)性能的程序，可分為四類：真實(shí)程序、核心程序、小測(cè)試程序、合成測(cè)試程序。測(cè)試程序組件——選擇一個(gè)各個(gè)方面有代表性的測(cè)試程序，組成一個(gè)通用的測(cè)試程序集合。這個(gè)通用的測(cè)試程序集合稱為測(cè)試程序組件。大概率事件優(yōu)先——此原則是計(jì)算機(jī)體系結(jié)構(gòu)中最重要和最常見的原則。對(duì)于大概率事件（最常見的事件），賦予它優(yōu)先的處理權(quán)和資源使用權(quán)，以獲得全局的最優(yōu)結(jié)果。系統(tǒng)加速比——系統(tǒng)改進(jìn)前與改進(jìn)后總執(zhí)行時(shí)間之比。Amdahl定律——加快某部件執(zhí)行速度所獲得的系統(tǒng)性能加速比，受限于該部件在系統(tǒng)中的所占的重要性。程序的局部性原理——程序在執(zhí)行時(shí)所訪問的地址不是隨機(jī)的，而是相對(duì)簇聚；這種簇聚包括指令和數(shù)據(jù)兩部分。CPI——指令時(shí)鐘數(shù)（CyclesperInstruction）。1.4對(duì)于一臺(tái)400MHz計(jì)算機(jī)執(zhí)行標(biāo)準(zhǔn)測(cè)試程序，程序中指令類型，執(zhí)行數(shù)量和平均時(shí)鐘周期數(shù)如下：指令類型指令執(zhí)行數(shù)量平均時(shí)鐘周期數(shù)整數(shù)450001數(shù)據(jù)傳送750002浮點(diǎn)80004分支15002求該計(jì)算機(jī)的有效CPI、MIPS和程序執(zhí)行時(shí)間。解：程序執(zhí)行時(shí)間=（）／400=575s1.5計(jì)算機(jī)系統(tǒng)有三個(gè)部件能夠改進(jìn)，這三個(gè)部件的加速比如下：部件加速比1＝30；部件加速比2＝20；部件加速比3＝10；(1)如果部件1和部件2的可改進(jìn)比例為30％，那么當(dāng)部件3的可改進(jìn)比例為多少時(shí)，系統(tǒng)的加速比才能夠達(dá)到10？(2)如果三個(gè)部件的可改進(jìn)比例為30％、30％和20％，三個(gè)部件同時(shí)改進(jìn)，那么系統(tǒng)中不可加速部分的執(zhí)行時(shí)間在總執(zhí)行時(shí)間中占的比例是多少？解：在多個(gè)部件可改進(jìn)情況下Amdahl定理的擴(kuò)展:式中，fi為可加速部件i在未優(yōu)化系統(tǒng)中所占的比例；Si是部件i的加速比。CISC——復(fù)雜指令集計(jì)算機(jī)。RISC——精簡(jiǎn)指令集計(jì)算機(jī)。第三章流水線技術(shù)流水線——將一個(gè)重復(fù)的時(shí)序過程，分解為若干個(gè)子過程，而每一個(gè)子過程都可有效地在其專用功能段上與其它子過程同時(shí)執(zhí)行。單功能流水線——只能完成一種固定功能的流水線。多功能流水線——流水線的各段能夠進(jìn)行不同的連接，從而使流水線在不同的時(shí)間，或者在同一時(shí)間完成不同的功能。靜態(tài)流水線——同一時(shí)間內(nèi)，流水線的各段只能按同一種功能的連接方式工作。動(dòng)態(tài)流水線——同一時(shí)間內(nèi)，當(dāng)某些段正在實(shí)現(xiàn)某種運(yùn)算時(shí)，另一些段卻在實(shí)現(xiàn)另一種運(yùn)算。部件級(jí)流水線——（運(yùn)算操作流水線）把處理機(jī)的算術(shù)邏輯部件分段，以便為各種數(shù)據(jù)類型進(jìn)行流水操作。處理機(jī)級(jí)流水線——（指令流水線）把解釋指令的過程按照流水方式處理。處理機(jī)間流水線——（宏流水線）由兩個(gè)以上的處理機(jī)串行地對(duì)同一數(shù)據(jù)流進(jìn)行處理，每一個(gè)處理機(jī)完成一項(xiàng)任務(wù)。線性流水線——指流水線的各段串行連接，沒有反饋回路。非線性流水線——指流水線中除有串行連接的通路外，還有反饋回路。標(biāo)量流水處理機(jī)——處理機(jī)不具有向量數(shù)據(jù)表示，僅對(duì)標(biāo)量數(shù)據(jù)進(jìn)行流水處理。向量流水處理機(jī)——處理機(jī)具有向量數(shù)據(jù)表示，并經(jīng)過向量指令對(duì)向量的各元素進(jìn)行處理。結(jié)構(gòu)相關(guān)——某些指令組合在流水線中重疊執(zhí)行時(shí)，發(fā)生資源沖突，則稱該流水線有結(jié)構(gòu)相關(guān)。數(shù)據(jù)相關(guān)——當(dāng)指令在流水線中重疊執(zhí)行時(shí)，流水線有可能改變指令讀/寫操作的順序，使得讀/寫操作順序不同于它們非流水實(shí)現(xiàn)時(shí)的順序，將導(dǎo)致數(shù)據(jù)相關(guān)。定向——將計(jì)算結(jié)果從其產(chǎn)生的地方直接送到其它指令需要它的地方，或所有需要它的功能單元，避免暫停。RAW——兩條指令i，j，i在j前進(jìn)入流水線，j執(zhí)行要用到i的結(jié)果，但當(dāng)其在流水線中重疊執(zhí)行時(shí)，j可能在i寫入其結(jié)果之前就先行對(duì)保存該結(jié)果的寄存器進(jìn)行讀操作，得到錯(cuò)誤值。WAW——兩條指令i，j，i在j前進(jìn)入流水線，j、i的操作數(shù)一樣，在流水線中重疊執(zhí)行時(shí)，j可能在i寫入其結(jié)果之前就先行對(duì)保存該結(jié)果的寄存器進(jìn)行寫操作，導(dǎo)致寫錯(cuò)誤。WAR——兩條指令i，j，i在j前進(jìn)入流水線，j可能在i讀某個(gè)寄存器之前對(duì)該寄存器進(jìn)行寫操作，導(dǎo)致i讀出數(shù)據(jù)錯(cuò)誤。有一條流水線如下所示。求連續(xù)輸入10條指令，該流水線的實(shí)際吞吐率和效率；該流水線的瓶頸在哪一段？請(qǐng)采取三種不同的措施消除此“瓶頸”。對(duì)于你所給出的新流水線，計(jì)算連續(xù)輸入10條指令時(shí)，其實(shí)際吞吐率和效率。解：（1）（2）瓶頸在3、4段。變成八級(jí)流水線（細(xì)分）變成兩級(jí)流水線（合并）重復(fù)設(shè)置部件1123-13-24-14-24-34-4★如果流水線有m段，各段的處理時(shí)間分別是ti（i=1，2，…，m），現(xiàn)在有n個(gè)任務(wù)需要完成，且每個(gè)任務(wù)均需流水線各段實(shí)現(xiàn)，請(qǐng)計(jì)算：流水線完成這n個(gè)任務(wù)所需要的時(shí)間；和非流水線實(shí)現(xiàn)相比，這n個(gè)任務(wù)流水實(shí)現(xiàn)的加速比是多少？加速比的峰值是多少？解：（1）（2）第五章存儲(chǔ)層次存儲(chǔ)層次——采用不同的技術(shù)實(shí)現(xiàn)的存儲(chǔ)器，處在離CPU不同距離的層次上，目標(biāo)是達(dá)到離CPU最近的存儲(chǔ)器的速度，最遠(yuǎn)的存儲(chǔ)器的容量。全相聯(lián)映象——主存中的任一塊能夠被放置到Cache中任意一個(gè)地方。直接映象——主存中的每一塊只能被放置到Cache中唯一的一個(gè)地方。組相聯(lián)映象——主存中的每一塊能夠放置到Cache中唯一的一組中任何一個(gè)地方（Cache分成若干組，每組由若干塊構(gòu)成）。替換算法——由于主存中的塊比Cache中的塊多，因此當(dāng)要從主存中調(diào)一個(gè)塊到Cache中時(shí)，會(huì)出現(xiàn)該塊所映象到的一組（或一個(gè)）Cache塊已全部被占用的情況。這時(shí)，需要被迫騰出其中的某一塊，以接納新調(diào)入的塊。LRU——選擇最近最少被訪問的塊作為被替換的塊。實(shí)際實(shí)現(xiàn)都是選擇最久沒有被訪問的塊作為被替換的塊。寫直達(dá)法——在執(zhí)行寫操作時(shí)，不但把信息寫入Cache中相應(yīng)的塊，而且也寫入下一級(jí)存儲(chǔ)器中相應(yīng)的塊。寫回法——只把信息寫入Cache中相應(yīng)塊，該塊只有被替換時(shí)，才被寫回主存。按寫分配法——寫失效時(shí)，先把所寫單元所在的塊調(diào)入Cache，然后再進(jìn)行寫入。不按寫分配法——寫失效時(shí)，直接寫入下一級(jí)存儲(chǔ)器中，而不把相應(yīng)的塊調(diào)入Cache。命中時(shí)間——訪問Cache命中時(shí)所用的時(shí)間。失效率——CPU訪存時(shí)，在一級(jí)存儲(chǔ)器中找不到所需信息的概率。失效開銷——CPU向二級(jí)存儲(chǔ)器發(fā)出訪問請(qǐng)求到把這個(gè)數(shù)據(jù)調(diào)入一級(jí)存儲(chǔ)器所需的時(shí)間。強(qiáng)制性失效——當(dāng)?shù)谝淮卧L問一個(gè)塊時(shí)，該塊不在Cache中，需要從下一級(jí)存儲(chǔ)器中調(diào)入Cache，這就是強(qiáng)制性失效。容量失效——如果程序在執(zhí)行時(shí)，所需要的塊不能全部調(diào)入Cache中，則當(dāng)某些塊被替換后又重新被訪問，就會(huì)產(chǎn)生失效，這種失效就稱作容量失效。沖突失效——在組相聯(lián)或直接映象Cache中，若太多的塊映象到同一組（塊）中，則會(huì)出現(xiàn)該組中某個(gè)塊被別的塊替換（即使別的組或塊有空閑位置），然后又被重新訪問的情況。2：1Cache經(jīng)驗(yàn)規(guī)則——大小為N的直接映象Cache的失效率約等于大小為N/2的兩路組相聯(lián)Cache的實(shí)效率。相聯(lián)度——在組相聯(lián)中，每組Cache中的塊數(shù)。VictimCache——位于Cache和存儲(chǔ)器之間的又一級(jí)Cache，容量小，采用全相聯(lián)策略。用于存放由于失效而被丟棄（替換）的那些塊。每當(dāng)失效發(fā)生時(shí)，在訪問下一級(jí)存儲(chǔ)器之前，先檢查VictimCache中是否含有所需塊。偽相聯(lián)Cache——一種既能獲得多路組相聯(lián)Cache的低失效率，又能獲得直接映象Cache的命中速度的相聯(lián)辦法。★降低Cache失效率有哪幾種方法？簡(jiǎn)述其基本思想。常見的降低Cache失效率的方法有下面幾種：增加Cache塊大小。增加塊大小利用了程序的空間局部性。提高相聯(lián)度，降低沖突失效。VictimCache，降低沖突失效。偽相聯(lián)Cache，降低沖突失效。硬件預(yù)取技術(shù)，指令和數(shù)據(jù)都能夠在處理器提出訪問請(qǐng)求前進(jìn)行預(yù)取。由編譯器控制的預(yù)取，硬件預(yù)取的替代方法，在編譯時(shí)加入預(yù)取的指令，在數(shù)據(jù)被用到之前發(fā)出預(yù)取請(qǐng)求。編譯器優(yōu)化，經(jīng)過對(duì)軟件的優(yōu)化來降低失效率?！锝o定以下的假設(shè)，試計(jì)算直接映象Cache和兩路組相聯(lián)Cache的平均訪問時(shí)間以及CPU的性能。由計(jì)算結(jié)果能得出什么結(jié)論？理想Cache情況下的CPI為2.0，時(shí)鐘周期為2ns，平均每條指令訪存1.2次；兩者Cache容量均為64KB，塊大小都是32字節(jié)；組相聯(lián)Cache中的多路選擇器使CPU的時(shí)鐘周期增加了10％；這兩種Cache的失效開銷都是80ns；命中時(shí)間為1個(gè)時(shí)鐘周期；64KB直接映象Cache的失效率為1.4％，64KB兩路組相聯(lián)Cache的失效率為1.0％。解：平均訪問時(shí)間＝命中時(shí)間＋失效率×失效開銷平均訪問時(shí)間1-路=2.0+1.4%*80=3.12ns平均訪問時(shí)間2-路=2.0*(1+10%)+1.0%*80=3.0ns兩路組相聯(lián)的平均訪問時(shí)間比較低CPUtime=（CPU執(zhí)行+存儲(chǔ)等待周期）*時(shí)鐘周期CPUtime=IC（CPI執(zhí)行+總失效次數(shù)/指令總數(shù)*失效開銷）*時(shí)鐘周期=IC（（CPI執(zhí)行*時(shí)鐘周期）+（每條指令的訪存次數(shù)*失效率*失效開銷*時(shí)鐘周期））CPUtime1-way=IC(2.0*2+1.2*0.014*80)＝5.344ICCPUtime2-way=IC(2.2*2+1.2*0.01*80)＝5.36IC相對(duì)性能比：5.36/5.344=1.003直接映象cache的訪問速度比兩路組相聯(lián)cache要快1.04倍，而兩路組相聯(lián)Cache的平均性能比直接映象cache要高1.003倍。因此這里選擇兩路組相聯(lián)。★偽相聯(lián)中，假設(shè)在直接映象位置沒有發(fā)現(xiàn)匹配，而在另一個(gè)位置才找到數(shù)據(jù)（偽命中）時(shí)，需要1個(gè)額外的周期，而且不交換兩個(gè)Cache中的數(shù)據(jù)，失效開銷為50個(gè)時(shí)鐘周期。試求：推導(dǎo)出平均訪存的時(shí)間公式。利用（1）中得到的公式，對(duì)于2KBCache和128KBCache，重新計(jì)算偽相聯(lián)的平均訪存時(shí)間。請(qǐng)問哪一種偽相聯(lián)更快？假設(shè)2KB直接映象Cache的總失效率為0.098，2路相聯(lián)的總失效率為0.076； 128KB直接映象Cache的總失效率為0.010，2路相聯(lián)的總失效率為0.007。解：不論作了何種改進(jìn)，失效開銷相同。不論是否交換內(nèi)容，在同一“偽相聯(lián)”組中的兩塊都是用同一個(gè)索引得到的，因此失效率相同，即：失效率偽相聯(lián)＝失效率2路。偽相聯(lián)cache的命中時(shí)間等于直接映象cache的命中時(shí)間加上偽相聯(lián)查找過程中的命中時(shí)間*該命中所需的額外開銷。命中時(shí)間偽相聯(lián)＝命中時(shí)間1路＋偽命中率偽相聯(lián)×1交換或不交換內(nèi)容，偽相聯(lián)的命中率都是由于在第一次失效時(shí)，將地址取反，再在第二次查