計算機結構考古題｜歷屆國考試題彙整

Amdahl’s Law 是評估電腦效能的重要概念： 說明它的意義。（5 分） 它對於改善電腦效能有何幫助？（5 分） 程式X 在電腦A 上執行需要100 秒，其中乘法指令占了40%，請問 有沒有可能藉由改善乘法器的速度達到把程式X 的執行速度加倍的 目的？若是可以，該把乘法器的速度加強到幾倍？若是不可以，那是 為什麼？（15 分）

我們要把以下的C 程式片段編譯成MIPS 組合語言程式。假設變數g 是 存在$s1 暫存器裡，陣列B 的base address 是存在$s2 暫存器裡。 B[9] = g + B[8]; 以下是編譯後的MIPS 組合語言程式。請推導出L, X, Y, Z, M 這五個欄位 裡的值。這些值是暫存器名稱（例如$s3）或（十進位）立即值。（25 分） lw $t0, X(L) % $t0 = Memory[L+X] add $t0, Y, $t0 % $t0 = Y + $t0 sw $t0, Z(M) % Memory[M+Z] = $t0

記憶體設計 何謂快取記憶體（cache memory）？（5 分） 何謂虛擬記憶體（virtual memory）？（5 分） 以上兩者的工作原理有什麼相近之處？（5 分） 有一個direct mapped cache，它有8 個block，每個block 存一筆memory word。假設一開始該cache 內容全部空白，請問依序存取八筆memory word（address 依序為0, 4, 8, 4, 8, 0, 3, 0）後，總共有幾次cache miss？ （10 分） 71260

考量在下圖的MIPS 處理器管線（pipeline）裡執行以下MIPS 組合語言 程式： lw add sub or and $4, 8($9) $2, $3, $4 $7, $6, $5 $8, $2, $7 $1, $3, $8 如果電路中沒有forwarding unit，請列出在第五個clock cycle 結束時， 在MIPS 五級pipeline stage（IF, ID, EXE, MEM, WB）中各有那個指令 在執行？（若沒有指令在執行，那就列為nop 指令）（12 分） 當forwarding unit 有作用時，請列出在第五個clock cycle 結束時，在 MIPS 五級pipeline stage（IF, ID, EXE, MEM, WB）中各有那個指令在 執行？（若沒有指令在執行，那就列為nop 指令）（13 分）

在計算機結構中，2 對1 多工器（2-to-1 Multiplexer）是一個常用的電路。 考慮一個2 對1 多工器Y = Mult(A,B,S)，就是在兩個輸入訊號（A 或B） 當中選取其中一個來當作輸出訊號（Y），選取的原則由一控制訊號（S） 來決定。如果S = 1，那就Y = A。如果S = 0，那就Y = B。請回答下列 有關多工器的問題。 請畫出A, B, S, Y 四個訊號的真值表（Truth Table）。（8 分） 請利用AND、OR 與NOT 邏輯運算元（logic operator）來表示Y 與A, B, S 的關係。（8 分） 考慮一個4 對1 多工器Z=Mult4（A,B,C,D,S,T），其中： 當S = 0，T = 0 時，Z = A；當S = 1，T = 0 時，Z = B； 當S = 0，T = 1 時，Z = C；當S = 1，T = 1 時，Z = D。 請利用AND、OR 與NOT 邏輯運算元，來表示Z 與A, B, C, D, S, T 的關係。（9 分）

AI 伺服器的運算能力常以FLOPs 來表示其運算的效能。 請解釋FLOPs。（9 分） 請解釋FP 32。（8 分） 請解釋FP 64。（8 分） 71260

考慮以下計算機，其所執行之程式有四種指令，每種指令之特性如下表 的各欄位所示。其中NC 表示“不需計入考量”。在本題中，計算效能 （throughput）定義為每秒可執行的指令數。 指令 在程式占 有之比重 擷取時間 解碼時間 ALU 執行時間 記憶體 儲存時間 結果寫入 （WB）時間 Load 25% 2ns 2ns 2ns 2ns 2ns Store 20% 2ns 2ns NC Arithmetic 30% 2ns NC 2ns Branch 25% 2ns NC NC 如果該電腦以single-cycle processor 實現。請問throughput 是多少？ （8 分） 如果該電腦以multi-cycle processor 實現。請問throughput 是多少？ （8 分） 如果該電腦以5-stage pipelined processor 實現。假設沒有任何資料錯 置或是結構錯置的發生，也不計中斷時間，請問throughput 是多少？ （9 分）

總工作量（Work）的定義就是處理器花在某個程式上的時間總和（不包 含待命時間）。而工作深度（Depth）就是根據計算的相依性，找出相依 性最長的那件工作。如下圖所示： 本圖所示之例子，一個程式的工作是將16 個數加總起來，如果我們把所 有運算步驟的相依性繪製成一個圖，那麼Depth 是4，而Work 是15。 現今考慮一個程式的工作是將N 個數加總起來的時候： 請建立Work 與N 的關係式。（12 分） 請建立Depth 與N 的關係式。（13 分）

請回答以下有關CPU（Central Processing Unit）與GPU（Graphical Processing Unit）在架構與功能方面比較的問題。 一個CPU 內的核心（core）數量，比一個GPU 的核心數量多出數十 倍到數百倍。對或錯？（5 分） CPU 內的單一核心的時脈速率（clock rate）比GPU 內單一核心的時 脈速率大。對或錯？（5 分） GPU 內之記憶體結構大多採用快取記憶體（cache），而CPU 內之記 憶體結構適合多核心同時進行資料存取。對或錯？（5 分） 假設CPU 在執行程式時，CPI（clock cycles per instruction）從2 變成 3，時脈速率從2 GHz 變成3 GHz，則執行時間會變成原來的幾倍？ 請詳細提供計算過程，否則不予計分。（10 分）

在處理器的結構當中，管線化（Pipelining）屬於加速執行的一種選項。 當處理器的指令集架構可將處理器管線化成在四均等的管線中執行指 令，將可使每道指令在「正常狀況」下於通過四個管線階段所需的總時 間為4.0 ns（nano second）（也就是每一均等階段需1.0 ns 的時間）。請回 答以下問題。 執行一道、五道、十道、一百道、一千道指令時，各需多少時間？ （10 分） 承上題，相較於沒有管線化的架構，執行一道、五道、十道、一百道、 一千道指令時，分別可預期獲得幾倍的加速？（註：沒有加速，是謂 「零倍加速」。）（請用紙、筆、手作除法計算，回答到小數第二位而小 數第三位四捨五入來處理）（10 分） 請具體舉例說明一個「非正常狀況」的狀況，是什麼狀況？（硬體故 障、停電、人為外力中斷等不計）（5 分） 71260

請回答以下有關2 的補數（two’s complement）邏輯設計的問題。在一個4 位元的系統中，2 的補數可以用於表示正數（positive number）與負數 （negative number）。 請將這個4 位元的系統的+2 以二進位方式（binary form）表示。（5 分） 請將這個4 位元的系統的-2 以二進位方式（binary form）表示。（5 分） 以IN =A[3],A[2],A[1],A[0]代表一個數字IN 在這個系統中的4 個位元。 其中A[3]是MSB（most significant bit）。以OUT = B[3], B[2], B[1], B[0] 來代表數字IN 的2 的補數。其中B[3]是MSB。如今提供給你四個加 法器（ADDER[3]，ADDER[2]，ADDER[1]，ADDER[0]）與四個NOT gate。每一個ADDER[i]接受兩個輸入X[i]與Y[i]，運算後會產生一個 進位CARRY[i]與和SUM[i]，（for i=0 to 3）。請使用IN 與四個加法器、 四個NOT gate，以及AND、OR 等邏輯運算子（logic operator）進行 運算來表示OUT。（提示：將X[0]設定為NOT A[0]，Y[0]設定為1， 則B[0]就是SUM[0]），請表示如何從A[3], A[2], A[1]得到B[3], B[2], B[1]。（15 分）

假設實體記憶體有四頁，以及參考頁面的編號序列為abgadeabadegde （也就是先參考頁面a，接續頁面b，再接續頁面g，……，一直到最後 頁面e）。請逐一跟隨（trace）與計算以下每一種記憶體置換策略 （replacement strategy），會發生幾次的頁面存取錯誤（page fault）。（假設 每種策略最初所有頁的內容都是空白的。） FIFO（First In First Out）（5 分） LRU（Least Recently Used）（5 分） LIFO（Last In First Out）（5 分） MRU（Most Recently Used）（5 分） 請設計與說明一套你自己提出的置換策略，以及展示會發生幾次頁面 存取錯誤。（5 分）

假設C 語言的指令 f = (g - h) - (i - j) 被編譯成組合語言的指令時，會將其中的變數f,g,h,i,j 分別存放在 暫存器$s0,$s1,$s2,$s3,$s4。已知組合語言指令 sub $t0, $s1, $s2 將$s1 的內容減$s2 的內容以後儲存在暫存器$t0。 則上述的C 語言指令會被編譯成怎樣的組合程式片段？（20 分）

請定義位元組（byte）及字組（word），並說明定義的理由，請務必涵蓋 是否分別等於多少個位元（bit），以及是否與處理器的硬體組成有什麼關 係。如果在暫存器之間傳送一個位元組需要T 秒，則傳送一個字組、兩 個字組及四個字組分別需要多少時間？（20 分）

有一處理器的時脈週期時間（clock cycle time）為2 奈秒（ns），錯失懲 罰（miss penalty）為20 個時脈週期，每一個指令的錯失率（miss rate） 為0.04，快取記憶體（cache）存取時間（包含偵測是否命中）為1 個時 脈週期。假設讀與寫的錯失懲罰相同，並且忽略寫入停頓（stall），則平 均記憶體存取時間（average memory access time）為多少奈秒？請詳細說 明計算過程，否則不予計分。（20 分）

假設在執行程式時，CPI（clock cycles per instruction）從1.5 變成2，時 脈速率（clock rate）從900 MHz 變成800 MHz，則執行時間會變成原來 的幾倍？請詳細說明計算過程，否則不予計分。（20 分） 71260

下列組合語言程式 lw $t1, 0($s3) add $t0, $t1, $s2 將記憶體裡面的資料載入暫存器$t1，然後使用該暫存器的內容於接下 來的加法運算。這樣的程式在管線化（pipelining）時，為什麼會有或沒 有危障（hazard）？如果有，是那一種危障？是否可以利用硬體加速？如 果可以，請說明其方法。加速後能不能完全沒有停頓（pipeline stall）？ （20 分）

若某一設備平均正常時間（mean time to failure, MTTF）與平均修護時間 （mean time to repair, MTTR）分別為3年與2天，請計算其平均故障之間的 時間（mean time between failures, MTBF）與可用度（availability）分別 為多少？（20分）

為完成某些計算工作，有一個最快的程式在使用一個處理器的情況下， 需要60秒才能完成。如果同時使用五個處理器，理論上最少要多少時 間？在實際的執行情況下，有沒有可能比理論上的最少時間還少就可以 完成？如果可能，請說明理由。（20分）

有一32位元的數值A5BC2749從主記憶體位址1704開始存放。 （每小題10分，共20分） 若電腦系統使用big endian，則存放在位址1706的位元組為何？請務必 說明理由。 若使用little endian 則又如何？

有的人會用million instructions per second（MIPS）來表示處理器的效能。 請說明為什麼用MIPS 表示效能並不恰當。（20分）

已知某一計算機的組合語言有一個指令是把兩個暫存器的內容相加放 到第三個暫存器。如果該計算機一共有32個暫存器可以儲存資料，則其 對應的機器語言指令一共至少需要有多少位元來代表這些暫存器？ 請詳細說明計算過程，否則不予計分。（20分）

請說明下列有關指令集的問題： 有些CPU 的指令集的浮點運算（floating point operations）是以可有可 無（optional）的協同處理器（co-processor）的形式來支援。為什麼？ （10 分） 如果某個CPU 沒有配置浮點運算的協同處理器，那它該如何達成浮 點運算？（10 分）

某指令集有四類（class）指令，分別為class A, class B, class C, class D。 此指令集有兩種硬體的實現方式P1 及P2。這些指令在P1 及P2 的clock rate 及CPI（cycles per instruction）如下表。有一個程式總共執行了10,000 個指令，其中class A, class B, class C, class D 的指令比重各為40%, 30%, 20%, 10%。 clock rate CPI of class A CPI of class B CPI of class C CPI of class D P1 1.0 GHz 1 2

P2 1.2 GHz 1 3 3 6 依該程式在P1 及P2 上執行的CPI 值而言，P1 及P2 那一個比較快？ （10 分） 依該程式在P1 及P2 上執行的時間而言，P1 及P2 那一個比較快？ （10 分） 71260 三、2’s complement 是一種用二進位表示有號數的方法。它的好處是可以在 加法或減法處理中，不需因為數字的正負而使用不同的計算方式。例如， 兩個二進位數字A 及B 之減法可表達為A – B = A + (~B) + 1，其中“~” 是bitwise not 運算。下圖為一個1-bit Arithmetic Logic Unit (ALU)，其中a, b 為1-bit input signal，Result 為1-bit output signal, Binvert (1 bit, possible values: 0/1), CarryIn (1 bit, possible values: 0/1)及Operation (2 bits, possible values: 00/01/10/11)為控制訊號。請依序設定這三個控制訊號值，使得 Result = a – b。（20分） 四、請說明下列有關高效能處理器的問題： Pipelining 是指把一個工作拆成多個前後銜接的子工作。如果拆成五個子 工作，理想情況下，這個pipeline 的效能可以變為原來的幾倍？（10 分） 有那些因素會無法達成上題中的理想效能？（10 分）

請說明下列有關記憶體設計的問題： 請依下表格式作答，並在空格中以1～3 之數值（1 最佳，2 其次，3 最 差）來分別評比SRAM（static random access memory）, DRAM（dynamic random access memory）, HD（hard disk）的Speed 及Capacity。（10 分） Storage Devices SRAM DRAM HD Speed Capacity 如何根據以上的分析，以階層（hierarchical）的方式將這三種storage devices 組合成為處理器（CPU）的記憶體系統，以優化整體的效能？ （10 分） Operation Binvert Result CarryOut Carryln a b

計算機的分類方法中，最有名的方法之一是Flynn’s taxonomy 或稱 classification，其依據指令流的數目以及數據流的數目將計算機分成： 單指令流單數據流（single instruction stream, single data stream，或稱 SISD）計算機、單指令流多數據流（single instruction stream, multiple data streams，或稱SIMD）計算機、多指令流單數據流（multiple instruction streams, single data stream，或稱MISD）計算機、多指令流多數據流 （multiple instruction streams, multiple data streams，或稱MIMD）計算 機。試說明這四種計算機類別分別適用於那些型態的計算工作，並舉出 日常常見實際應用的代表機器一種（舉例應具體、足以反映機器的特 色）。（20 分）

假設某計算機程式花費執行時間的15%做開頭的啓始動作以及結束時的 處理，並且在這些過程中並無任何改善程式碼效能的機會；另外25%的 時間做數據搬移（即記憶體讀寫動作，此處假設過程中並無中央處理器 的額外時間負擔）；其他60%的時間則是做數據處理（亦即處理計算的 工作）。 若僅改善數據處理使用的演算法使得數據處理的部分加速了20 倍， 則程式整體的加速為若干倍？（7 分） 若不改善程式而僅將中央處理器替換成一個處理速度是兩倍快的中 央處理器，則程式整體的加速為若干倍？（7 分） 若不對記憶體系統做任何改善，則程式整體加速的上限為若干倍？ （6 分） 71260

試以二進數字系統為例，討論有正負號的定點數字表示法與浮點數字表 示法（浮點數字表示法的格式請以IEEE 754 標準為依據；但不需刻意 使用標準中使用的各欄位大小）。假設兩種數字表示法使用的位元數目 是相同的，都是32 個位元。（每小題5 分，共20 分） 列出並說明定點數字表示法使用的格式（含各欄位的名稱、大小、功 用）。 列出並說明浮點數字表示法使用的格式（內容項目應同上）。 浮點數字表示法中，一般是否有規範到（使用到）不需使用位元而能 表示出來的資訊？如果有，是那些？ 浮點數字表示法可以表示數值非常細微或是極端巨大、範圍非常寬廣 的許多數字。以32 個位元的表示法為例，其能夠表示的不同數值數 量約略為若干？並請作必要說明。

中央處理器（central processing unit，CPU）的主要設計方向是採用管線 化處理（pipelined processing）。（每小題5 分，共20 分） 相較於非管線化的設計，管線化的設計在硬體線路複雜度方面的需求 為何？並說明之。 相較於非管線化的設計，管線化的設計在程式執行時功率消耗的需求 為何？並說明之。 相較於非管線化的設計，管線化的設計在程式執行時間方面的表現為 何？並說明之。 管線化處理設計上常見的挑戰有三大類管線危障（pipeline hazards）， 試條列並說明之。

階層式記憶體的設計是基於程式執行時使用記憶體上顯現出來某些特 性的原理。（每小題5 分，共20 分） 寫出這個原理的名稱並說明其意義。 這個原理又分別可以在時間上與空間上具體觀察到其行為。分別說明 這個原理在時間上與空間上表現的行為是如何？ 以快取記憶體為例：在設計快取記憶體時，一般我們會在那些（至少 列出重要者一項即可）設計參數上，如何利用到時間上的這種行為特 性，做出怎樣的設計結果？ 在設計快取記憶體時，一般我們又會在那些（至少列出重要者一項即 可）設計參數上，如何利用到空間上的這種行為特性，做出怎樣的設 計結果？

一般用途（general-purpose）計算機是我們日常最常使用的計算機型式， 而其中最為人熟悉的就是桌上型電腦或筆記型電腦。其中央處理器 （central processing unit，簡稱CPU）主要有兩種依循的設計概念：複雜 指令集計算機（complex instruction set computer，簡稱CISC），以及精 簡指令集計算機（reduced instruction set computer，簡稱RISC）。 試舉出複雜指令集計算機的主要優良特性其中二項。（5 分） 試逐項條列上述二項優良特性分別會帶給設計者或使用者什麼益處 （針對每項優良特性，至少列出二項正確的益處即可；如有必要，可 以加上簡要的說明文字）。（5 分） 試舉出精簡指令集計算機的主要優良特性其中二項。（5 分） 試逐項條列上述二項優良特性分別會帶給設計者或使用者什麼益處 （針對每項優良特性，至少列出二項正確的益處即可；如有必要，可 以加上簡要的說明文字）。（5 分）

一計算機中的處理器在無管道化的設計時執行一道指令平均需時0.8 ns （奈秒）。設此計算機的指令集架構可將處理器管道化（pipelined）成 在五階的管道中執行指令，使每道指令應可於通過五個管道階的所需時 間1.0 ns 完成。則相較於未管道化時， 執行一、五、十、百道指令時，分別可預期獲得何等加速性？（5 分） 理想情況下的加速性是多少？（5 分） 若程式中需執行的指令數可視為無限，但是為了避免管道危障 （pipeline hazards），其中20%的指令需耗時1.5 個管道的時脈週期、 30%的指令需耗時2.0 個管道的時脈週期、其餘的指令則需耗時1.0 個管道的時脈週期時，其加速性又是多少？（5 分） 承上題，若此時仍欲獲得前述理想情況下的加速性，則處理器的時脈 週期應為若干？（5 分） 71260

已知一四位元的加法器設計如下圖所示： 其中FA 代表full adder，中文是全加器。 說明圖中全加器的定義，並繪製其真值表（truth table）。（6 分） 以一控制訊號OP = 0 代表進行加法、OP = 1 代表進行減法，將此加 法器修改成加減法器。（6 分） 以2 的補數形式進行加減法時，與運算相關的旗標一般共有四個，分 別用以代表運算結果是否有進位/借位、是否有滿溢、是否為負值、 以及是否為0。試分別列出欲在上圖中求出這四個旗標應使用的布林 式（Boolean equations）。（8 分） B3 A3 B2 A2 B1 A1 B0 A0 C3 C2 C1 FA FA FA FA C0 C4 S3 S2 S1 S0

一般用途（general-purpose）計算機的中央處理器（central processing unit，簡稱CPU）目前主要依循的設計方向是採用精簡指令集計算機 （reduced instruction set computer，簡稱RISC）的概念，目的即是有利 於管道化的處理器設計。一般管道中可以分成指令擷取、指令解碼、執 行、記憶體存取以及結果寫回五個管道階段。試分別列出精簡指令集計 算機特性中，有利於各管道階的最主要者一項，並作必要說明： 有利於指令擷取者。（4 分） 有利於指令解碼者。（4 分） 有利於執行者。（4 分） 有利於記憶體存取者。（4 分） 有利於結果寫回者。（4 分） 71260

假設計算機程式允許使用32 個位元來定址位元組大小的記憶體位置， 作業系統允許的頁（page）大小是2 KB（K 代表210，B 代表位元組）， 主記憶體或稱實體記憶體（physical memory）的大小是512 MB（M 代 表220）時， 頁表（page table）內應包含多少個項次（entries）？（4 分） 以位元組定址的實體位址（physical address）應包含多少個位元？（4 分） 在主記憶體中標示頁框（page frame）的位置最少需使用多少個位元？ （4 分） 程式執行時，其所發出的記憶體位址稱為何種位址？（4 分） 以條列式詳述程式由中央處理器（CPU）發出記憶體位址起、至該記 憶體位置的存取動作完成（假設不會發生頁錯誤 page fault）之間的 所有過程。說明中應盡可能使用題目中提到（或未提到）的相關專業 術語。（4 分）

在處理器的指令集中，每一個指令均有兩個成分：指令碼（operation code）與運算元 （operand）。與運算元關係密切的一個名詞為定址模式（addressing mode）。請說明 什麼是定址模式？通常一個微處理器中，都至少會具備那四個最基本的定址模式？ 請列舉並說明之。（20 分）

假設一個程式在一個CPU 時脈頻率為4 GHz 的計算機Ａ中的執行時間為12 秒。若 希望設計一個計算機B，可以在8 秒內完成此程式的執行。執行計算機B 的設計工 程師了解增加CPU 的時脈頻率是一個可行的方案，然而如此一來會影響到計算機B 中CPU 的其餘部分的設計，導致執行上述程式時，需要1.2 倍的時脈數目。請問計 算機B 中CPU 的時脈頻率為多少？（20 分）

執行某一個程式時，指令快取記憶器的失誤率（miss rate）為2%，資料快取記憶器 的失誤率為5%。若一個處理器在沒有記憶器停滯（memory stall）的情況下，其CPI 為1.5，而所有快取記憶器的失誤代價（miss penalty）都為120 個時脈。若所有對記 憶器的載入與儲存動作在執行該程式時為30%。計算在一個完全沒有失誤的完美快 取記憶器下，該程式的執行速度可以較實際有失誤的快取記憶器快多少倍？（20 分）

設計一個簡單的資料處理單元（或稱為資料路徑）並繪出其邏輯方塊圖，執行下列 兩個RTL 指述： R1 R0 R0 : xy R1 R0 R0 : y x − ← + ← 其中x 與y 分別為兩條控制信號。另外與資料處理單元相關的四個旗號為N（negative）、 Z（zero）、V（overflow）、C（carry），請說明其意義，並繪出相關的邏輯電路。（20 分） 106 年專門職業及技術人員高等考試 會計師、不動產估價師、專利師考試試題 71260 全一張 （背面） 等 別： 高等考試 類 科： 專利師（選試專業英文及計算機結構）、專利師（選試專業日文及 計算機結構） 科 目： 計算機結構

若某一處理器使用三級管線結構：指令擷取（F，instruction fetch）、指令解碼（D， instruction decoding）與指令執行（E，instruction execution）。請在下列指定條件下， 繪出下列程式片段的管線時序圖。 Loop Shift-right R1 Decrement R3 Branch=0 Loop Next Add R1, R2 若分歧位址（branch address）在指令執行級中計算時，分歧代價（即時脈週期損 失）為多少時脈週期？（5 分） 承的條件，當採用延遲分歧（delayed branch）的方法時，分歧代價為多少時脈 週期？（5 分） 若分歧位址（branch address）在指令解碼級中計算時，分歧代價為多少時脈週期？ （5 分） 承的條件，當採用延遲分歧（delayed branch）的方法時，分歧代價為多少時脈 週期？（5 分）

一般用途處理器的指令集可以根據不同面向來作分類。常見的分類方式中有一種是 根據指令中可以使用的運算元數量，而有0 個、1 個、2 個、3 個、4 個運算元的設 計方向。試回答下列問題： Java 語言的bytecode 在上述提及的分類方式中應屬多少個運算元的指令集？請具 體說明之，否則不予計分。（參考資料：Java bytecode 中原則上每道指令的長度 即為一個位元組。）（6 分） 4 個運算元的指令集一般會如何使用這4 個運算元？試逐個詳細說明之。（7 分） 有一種指令集設計方向稱為簡化指令集計算機（英文簡稱RISC）的架構，目前廣 受採用。RISC 一般採用多少個運算元的指令集設計？其具體原因為何？（7 分）

在談論一般用途應用程式的效能時， 何謂回應時間（英文用語是response time）？表示回應時間時使用的物理單位是 什麼？談論回應時間時所考慮的被處理對象又是什麼？（4 分） 回應時間中除了中央處理單元時間外，還包含了那些時間項目？（4 分） 表示中央處理單元時間常用的算術式是什麼？（4 分） 在的式子中有那些參數可以經由改善程式中的演算法來變動，以達改善之目的？ （4 分） 重作，這次採取的手段是改善指令集架構。（4 分）

處理器一般需具備數據搬移、數據處理與控制流向的能力，並能處理定點與浮點兩 種數據型態。試回答下列問題： 以逐步的方式詳細說明如何將二浮點數相加。（設採用的是IEEE-754 浮點表示 法，其表示値的方式是(-1)S(1+Fraction)*2(Exponent-Bias)。）（10 分） 指令“BranchIfEqual (R5==#(-1)) then to PC+#2010”中，為了判斷條件是否成立， 一共用到多少種的那些定址模式？為了擷取目標指令，又一共用到多少種的那些 定址模式？（10 分） 105年專門職業及技術人員高等考試會計師、 不動產估價師、專利師、民間之公證人考試試題 代號： 及計算機結構） 全一張 （背面） 70660 71260

中央處理單元的設計有一種稱為管道化（pipelined）處理的方式。相較於非管道化 （non-pipelined）處理，對某特定指令集架構而言： 何者可以更快完成個別指令的執行？並扼要說明原因。（5 分） 何者可以更快完成許多道連續指令、或程式的執行？並扼要說明原因。（5 分） 何者較可能需要用到更多且重覆的硬體資源？並扼要說明原因。（5 分） 何者在編譯上需要作那些額外的考慮？並扼要說明原因。（5 分）

一般用途計算機中的記憶體系統通常設計為階層式的。假設最高的階層連接中央處 理器，而最低的階層連接輸出入。以目前一般個人電腦的設計而言： 列出各階層名稱，依次由最高的階層至最低的階層排列（勿遺漏系統中任何儲存 體）。（5 分） 對任何階層的讀寫有可能發生錯失。在那些階層中不可能發生錯失？並說明原因。 （5 分） 在那些階層中發生錯失時，程式或中央處理單元會耐心等待錯失處理結束？並說 明原因。（5 分） 在那些階層中發生錯失時，系統在錯失處理結束前會做程序切換（context switch）？並說明原因。（5 分）

單一週期實作（single-cycle implementation）與管線化實作（pipeline implementation） 為二種常見的資料路徑（data path）設計方式，請詳述二種設計概念，並用以下公 式分析二種實作方式對執行時間之影響。（25 分） 註：程式執行時間＝執行的機器指令數×平均每道指令所花費時脈數×時脈週期

管線化資料路徑（pipelined data path）中，有時下一道指令不能緊接著下一個時脈 執行，這種情況稱之為危障（hazard），請詳述有那三種危障？並舉例說明之。 （25 分）

請詳述直接映射快取（direct mapped cache）、全關聯性快取（fully associative cache）、集合-關聯性快取（set-associative cache），並分析其失誤率（miss rate） 和硬體成本（hardware cost）。（25 分）

請詳述區域性原則（principle of locality）有那幾種？並舉例說明。為何區域性原則 （principle of locality）對記憶體階層的概念非常重要？（25 分）

一部電腦，假設資料的表示方式是採用2 的補數（Two’s Complement） 請畫出用4 個1 位元加法器（One-bit Full Adder）做兩個4 個位元的相加，兩個 4 個位元資料分別是A0、A1、A2、A3 與B0、B1、B2、B3，其結果放於S0、S1、 S2、S3，各位元相加後之進位分別放於C0、C1、C2、C3。（10 分） 承上，請利用AND、OR 或XOR 閘判斷兩個4 個位元相加後，是否有溢位 （Overflow）？（10 分）

一浮點暫存器（Floating-point Register）由32 位元組成，浮點表示方式係採用IEEE 754 浮點標準，最左邊位元表示符號：0 表示正，1 表示負的值；最右邊24 位元 表示小數點後的數目；中間的7 位元表示指數，指數的基底（Radix）是採用 超2n-1(Excess 2n-1, n 為指數長度)，今有一浮點數，其值以16 進位表示如下：（*表示乘） 請寫出此浮點數在如下計算機浮點暫存器的內容。（20 分） x xxxxxxx xxxxxxxxxxxxxxxxxxxxxxxx

請列舉複雜指令集電腦（Complex Instruction Set Computer; CISC）的四種定址方式，

請說明控制單元設計方法的兩種方式，硬體線路控制（Hard Wired）與微程式控制

一電腦硬體設計者，已知有如下資料： 令形態（Instruction Class or Format） 並簡單說明其目標位址（Target Address）的計算方式。（20 分） （Microprogramming），各有何優缺點？各用在何種機器上（RISC 或CISC）？ （20 分） 指 A B C 每一指令時鐘脈波 nstruction; CPI） （Clock Cycles Per I 1 2 3 對一 2，對每一條不同指令形態所需的指令數如下： 程式碼 特別高階語言，有兩程式碼1 和 每一指令形態所需指令數目 A B C 1 4 2 4 2 8 2 2 例如，程式碼1 由4 A 指令，2 條B 指令，和4 條C 指令所組成，請回答如下問題： 每一個程式碼各需執行幾個指令（Instruction Counts）？（6 分） 程式碼各需要幾個時鐘脈波（CPI）？（7 分） 條 那一個程式碼執行比較快？（7 分） 每一個

今有一C 語言程式，一精簡指令集計算機（RISC, Reduced Instruction Set Computer）， 及一複雜指令集計算機（CISC, Complex Instruction Set Computer）。 兩個計算機使用的編譯器（compiler）是否可為同一個？為何如此？（6 分） 轉譯成機器碼後，兩個計算機的機器碼一般而言何者有較多道指令？為何如此？ （7 分） 執行該程式的機器碼時，兩個計算機一般而言何者較快？為何如此？（7 分）

效能一般指的是計算機執行機器碼程式時的速度，通常以所需的時間來反映。相關計算 式如下：程式執行時間=執行的機器指令數×平均每道指令所花費時脈數×時脈週期 透過編譯器與組譯器（assembler）可以改善上式中那些參數？並扼要說明之。 （6 分） 透過積體電子技術無法改善上式中那些參數？並扼要說明之。（7 分） 若機器碼程式共執行了1010 道指令，其中45%為數據處理（data processing）類指 令，其平均每道指令所花費時脈數為1.5；30%為數據搬移（data movement）類 指令，其平均每道指令所花費時脈數為2.5；20%為控制流向（control flow）類指 令，其平均每道指令所花費時脈數為4.0；其餘為系統呼叫（system call）類指令， 其平均每道指令所花費時脈數為20.0。則程式執行時間在時脈頻率為5 GHz 時為 若干？（7 分）

在處理器的設計中： 一般是如何定義出字元（word）的大小？（6 分） 若稱其記憶體空間有4 GB（G 表giga 或稱為接近109 的2 的整數次方值；B 表 byte），則一般稱其為幾個位元的架構？（7 分） 何謂管線化（pipelined）的指令執行方式？何謂超純量（superscalar）的指令執行 方式？（7 分） 102年專門職業及技術人員高等考試律師、 會計師、不動產估價師、專利師考試試題 代號： 類 科： 專利師 全一張 （背面） 70660 71260

設有一計算機，若僅考慮中央處理器（CPU），某應用程式執行的情形為：數據處 理（data processing）類指令執行的比例為50%，數據搬移（data movement）類指 令執行的比例為30%，以及控制流向（control flow）類指令執行的比例為20%。理 想情況下，管線化處理時每道指令所花費的時脈數（CPI, Cycles Per Instruction）為 1.0。以下計算結果均請取至小數點後兩位： 若僅考慮數據相依性（data dependency）造成的管線停頓，以致於35%的指令需 停頓1 個週期、25%的指令需停頓2 個週期。則此時的CPI 將為若干？（6 分） 若僅考慮控制相依性（control dependency）造成的管線停頓，以致於在20%的控 制流向指令中，有40%因不改變控制流向而不需停頓，另60%因改變控制流向而 需停頓4 個週期。則此時的CPI 將為若干？（7 分） 同時考慮數據相依性及控制相依性時，有1/5 的數據相依造成的管線停頓及1/3 的控制相依造成的管線停頓將與另一種管線停頓重疊。則此時的CPI 將為若干？ （7 分）

在精簡指令集計算機（RISC, Reduced Instruction Set Computer）設計中： 同時配備有指令快取記憶體（instruction cache memory）及數據快取記憶體（data cache memory）有何特殊重要性及優勢？請針對RISC 的特性作答。（6 分） 程式中那些類別的指令會用到指令快取記憶體？那些類別的指令會用到數據快取 記憶體？並分別具體舉例說明之。請儘量用專業的指令類別名稱答題。（7 分） 設程式執行時對指令快取記憶體及數據快取記憶體的存取數比例為2：1，且在理 想快取設計下的每道指令時脈數（CPI）為1。若實際情況下指令快取記憶體的 錯失率（miss rate）為20%，錯失懲罰（miss penalty）為12 個時脈週期；數據快 取記憶體的錯失率為35%，錯失懲罰為15 個時脈週期。則實際的CPI 為若干？ （計算結果請取至小數點後一位。）（7 分）

在常見的電腦系統中，basic input output system（BIOS）之組成元件及功能為何？ （20 分）

包含多個處理器（processors）的電腦在執行一個應用軟體時，其效能能否達到 superlinear speedup？請說明superlinear speedup 之意義及能否達到的可能原因。 （20 分）

比較記憶體使用DRAM 及SRAM 的優缺點及其原因。（20 分）

針對指令集（instruction set）之理念不同而產生RISC 與CISC 兩種電腦。請說明這 兩種指令集的意義及其可能之優缺點。（20 分）

有一32 位元的數值A5B71749 從主記憶體位址1700 開始存放。若電腦系統使用 big endian，則存放在位址1702 的位元組為何？又若使用little endian 則又如何？請 詳加說明理由。（20 分）

什麼叫做一個位址的指令集（one-address instruction set）？（4 分） 什麼叫做零個位址的指令集（zero-address instruction set）？（4 分） 零個位址的指令集的電腦比起一個位址的指令集的電腦優缺點何在？（6 分） 請利用一個位址的指令集寫出將記憶體中的兩數A 和B 相加，然後結果存回C 的組合語言程式，並說明每個指令的意義。（8 分） 請用零個位址的指令集寫同樣的程式，並說明每個指令的意義。（8 分）

假設一個CPU 的clock rate 為8 GHz，那麼其cycle time 為幾秒？（4 分） 一個程式在一個clock rate 為4GHz 的CPU 需要10 秒的執行時間，假設我們改進 了這個CPU 的設計，讓同樣的程式可以在8 秒執行完畢，但所需的CPU cycle 變 成原來的1.2 倍，那麼現在新CPU 的clock rate 為多少GHz？（12 分）

設計一個一位元的全加法器，假設輸入為A、B、Carry-in，輸出為C、Carry-out， 寫出其真假值表。（8 分）並畫出其簡化過後的邏輯閘圖。（12 分）

假設一個指令可以分成指令擷取（instruction fetch）、指令解碼（instruction decode）、 指令執行（instruction execution）、結果存回（result store）四個步驟。請問： 若我們按照此四個步驟來做pipeline 執行，對一個有1000 個指令的程式，本來需 要10 秒的執行時間，採用pipeline 後最快可在幾秒內執行完畢？（10 分） 若其中的第101 個指令無法pipeline，必須等第100 個指令執行完後才可以執行， 其他指令都可以pipeline，那麼在此情況下程式多快可以執行完畢？（10 分）

假設一個程式的指令cache 的錯失率（miss ratio）為2%，資料cache 的錯失率為 4%。如果CPU 執行一個指令需2 個cycle time，而一個cache 錯失（不管是指令或 資料）的代價是100 個cycle time。假設程式中有36%的指令會使用到資料cache， 那麼此程式執行的時間會是在完美cache（0%錯失率）情況下的幾倍？（14 分）

為什麼現在的計算機結構往多核心（multi-core）微處理器方向發展，請依下列三個 方向作答。 單核心處理器的瓶頸為何？（10 分） Deep pipeline 繼續發展會碰到那些問題？（10 分） 新的應用趨勢為何？（10 分）

請討論如何降低Smart Phone 的功率消耗，請依下列三個方向作答。 記憶體部分。（10 分） Display 部分。（10 分） CPU 部分。（10 分）

何謂System-on-Chip（SoC）？它的用途為何？其設計流程為何？（20 分）

何謂redundant array of inexpensive disks（RAID）？RAID 6 的運作機制為何？它有 什麼優點？（20 分）

請以全加器（full adder）及XOR gate 為基本元件（basic block），建構4-bit 加減 法器（4-bit adder-subtracter）。（5 分） 請以上例的架構，說明如何進行加法及減法運算。（5 分） 舉一例説明，3 個運算元的8-bit carry-save-adder。其延遲（delay）為何？（5 分） 請以carry-save-adder為基本的建構方塊圖（building block），建構一個延遲（delay） 最短的8 × 8 wallace tree 乘法器（multiplier）。（5 分）

假設有兩種方法可以改進一台電腦的效能：第一種方法為加速乘法指令（multiply instruction）達到4 倍快；第二種方法為加速記憶體存取指令（memory access）達到 2 倍快。如果我們執行一個程式100 秒後，分析結果為：10%時間執行乘法指令， 50%時間執行記憶體存取指令，40%時間執行其他指令。請問： 如果只加速乘法指令，整體效能的改進（speed-up）為何？（5 分） 如果同時加速乘法指令及記憶體存取指令，整體效能的改進（speed-up）為何？ （5 分） 何謂Amdahl’s law？（5 分） 以上例説明在僅加速乘法指令及記憶體存取指令的前提下，Amdahl’s law 的結果， 可能的最大效能改進（speed-up）的極限為何？（5 分）

何謂Principle of locality？有那兩種locality？請以不同的程式結構，分別說明為 何會發生這兩種locality。（10 分） 有下列virtual memory system i. 40-bit virtual byte address ii. 16 KB page iii. 36-bit physical address 假設所有的virtual pages 都在使用，且每個page table entry（記錄項目）需另有 10 個管理用的位元（如valid, dirty, replacement 等），請問page table 的大小 （size）為何？（10 分）

給定下列數字表示1001 1010。若該表示式為unsigned number，請問該數字為何？ 若該表示式為2’s complement signed number，請問該數字為何？（10 分） 98年專門職業及技術人員高等考試律師、會計師、社會工作師 不動產估價師、專利師考試試題 代號： 類 科： 專利師 70660 71260 全一張 （背面）

給定一台電腦，以下為執行程式後，分析四種指令所得到的特性。其中X 表示不需使 用。又，throughput 定義為每秒可執行的指令數（instructions per second）。請問： Distribution IF ID EX MEM WB Load 25% 2ns 1ns 2ns 2ns 1ns Store 10% 2ns 1ns X Arithmetic 45% 1ns X 1ns Branch 20% 2ns X X 如果該電腦以single-cycle processor 實現。請問throughput 是多少？（6 分） 如果該電腦以multi-cycle processor 實現。請問throughput 是多少？（7 分） 如果該電腦以5-stage pipelined processor 實現。假設沒有任何data hazard, structural hazard 及control hazard 發生，請問throughput 是多少？（7 分） 六、下圖為ALU 的設計。請根據該設計，回答Add, Nor, Or 的控制信號為何？（10 分） Operations 4 bits (Anegat, Binvert, Op) Add Nor Or 0 3 Op 1 CarryOut 0 1 b 2 Result Anegat CarryIn 0 1 Binvert Operations a Less

假設一計算機（只能儲存整數），2 個連續bytes 構成一個word，一個byte 8 個bits， 整數以二進位數方式儲存，資料表示則以2 的補數方式表示。一指令由16 位元組成， 指令格式如下： opcode (4) x (1) y(1) address /disp (10) 其中x=0 採用直接定址，x=1 採用間接定址；y=0 採用程式計數（Program-counter Based） 定址，y=1 採用基底（Base-relative Based）定址，請問假設只考慮直接定址，記憶體 可定址到的大小為何？每一記憶體位置可儲存資料的長度為何？可儲存整數的範 圍、指令暫存器（Instruction Register, IR）的長度為何？（20 分）

在一計算機結構中，一指令由24 位元組成，其中6 個位元為操作碼（Operation Code）， 6 個位元為各種定址方式之表示，12 個位元為位址（Address）或位移（Displacement）， 給予記憶體和暫存器資料（以16 進位表示）如下： (3300)=001800 /*表示記憶體位址3300 之內容為001800*/ (3630)=003300 (6690)=103000 (0300)=003630 (B) =006000 (PC) =003000 (X) =000000 假設LDA 指令係將指定的記憶體位址內資料載入累積器（Accumulator），請寫出執行 LDA 300（採用直接定址）；LDA300（300 為memory address，採用PC-relative 定址， 目標位址（Target Address）的值為PC 的值加上位移值（Displacement））；LDA @630, X （630 為memory address，採用PC-relative，X 表示索引，@表示間接定址）；LDA #630 後暫存器A 之內容。（20 分）

在一計算機結構中，假設數字系統使用的是二的補數（2’s Complement），請設計一邏 輯線路以偵測兩個數字an-1an-2…a0 與bn-1bn-2…b0 相加，其結果cn-1cn-2…c0 是否溢位 （Overflow）；並用兩個四位數的二進位數相加說明。（20 分）

請列舉三種I/O 操作方式來做處理器（Processor）與I/O 模組（I/O Module）之資料 交換，並說明其優缺點。（20 分）

在指令串流排（Instruction Pinelining）中，可將一指令之執行分為存取指令（Fetch Instruction, FI），解碼指令（Decode Instruction, DI），計算運算元（Calculate Operands, CO），存取運算元（Fetch Operands），執行指令（Execute Instruction, EI），和寫入運 算元（Write Operands, WO）六個階段（Stage），請畫出9 個指令利用此六個階段執 行之時序圖（Timing Diagram），並計算利用此六個階段指令串流排執行9 個指令比 六個階段沒有使用指令串流排執行可節省多少單位時間。（20 分）

Virtual memory 主要在解決電腦系統的甚麼問題？請說明Demand Paging 的觀念以及 Translation Lookaside Buffer (TLB)的主要用途。（20 分）

何謂RAID(Redundant Array of Inexpensive Disks)？請說明RAID1 到RAID5 的差異。 （15 分）

在設計pipelined CPU 時需面對Structural hazard、Data hazard 及Control hazard 的問 題，請說明這三種問題為何並簡要說明一般所採取的解決方法。（20 分）

請說明在Pipelined Processor 中Branch Target Buffers 的主要用途。（15 分）

比較Memory-Mapped I/O 與Isolated I/O 之差異。（10 分） 六、比較Invalid snoopy protocols 中Write-invalidate、Illinois 及Berkeley 三種策略的異同 點。（20 分）