(IEH101)SEC2_處理器核心、匯流排（BUS）與輸出入之設計(解題說明)

IEH嵌入式系統的基本硬體架構技術

（2）處理器核心、匯流排（BUS）與輸出入之設計

------------------------------------------------------------------------------------------------------

For 2-01,-------------------------------------------------------------------------------------------

------------------------------------------------------------------------------------------------------

For 2-02,-------------------------------------------------------------------------------------------

Ref. to 學貫EY814_計算機組織,5e（中譯本）_Ch06_算術處理.ppt ch6.4

布斯乘法演算法（英語：Booth's multiplication algorithm）是計算機中一種利用數的2的補碼形式來計算乘法的演算法。該演算法由安德魯·唐納德·布斯於 1950 年發明，當時他在倫敦大學柏貝克學院做晶體學研究。布斯曾使用過一種台式計算器，由於用這種計算器來做移位計算比加法快，他發明了該演算法來加快計算速度。布斯演算法在計算機體系結構學科中備受關注。

演算法描述

對於 N 位乘數 Y，布斯演算法檢查其2的補碼形式的最後一位和一個隱含的低位，命名為 y-1 ，初始值為 0 。對於 yi, i = 0, 1, ..., N - 1，考察 yi 和 yi - 1 。當這兩位相同時，存放積的累加器 P 的值保持不變。當 yi = 0 且 yi - 1 = 1 時，被乘數乘以 2i 加到 P 中。當 yi = 1 且 yi - 1 = 0 時，從 P 中減去被乘數乘以 2i 的值。演算法結束後， P 中的數即為乘法結果。

該演算法對被乘數和積這兩個數的表達方式並沒有作規定。一般地，和乘數一樣，可以採用2的補碼方式表達。也可以採用其他計數形式，只要支持加減法就行。這個演算法從乘數的最低位執行到最高位，從 i = 0 開始，接下來和 2i 的乘法被累加器 P 的算術右移所取代。較低位可以被移出，加減法可以只在 P 的前 N 位上進行。[1]

典型實現

布斯演算法的實現，可以通過重複地在 P 上加兩個預設值 A 和 S 其中的一個，然後對 P 實施算術右移。設 m 和 r 分別為被乘數和乘數，再令 x 和 y 分別為 m 和 r 中的數字位數。

確定 A 和 S 的值，以及 P 的初始值。這三個數字的總長度應等於( x + y + 1 )：

對於 A ，以 m 的填充前x位（最靠左的位），用零填滿剩下的( y + 1 )位；
對於 S ，以( - m )的值填充前x位，用零填滿剩下的( y + 1 )位；
對於 P ：用0填滿最左的 x 位，將 r 的值附加在尾部；最右一位用零佔位（輔助位，當i=0時i-1=-1,指的就是這個輔助位）；

考察 P 的最右兩位：

如果等於 01，求出 P + A 的值，忽略上溢；
如果等於 10，求出 P + S 的值，忽略上溢；
如果等於 00，不做任何運算，在下一步中直接採用 P 的值；
如果等於 11，不做任何運算，在下一步中直接採用 P 的值。

對第 2 步中得到的值進行算術右移一位，並將結果賦給 P ；
重複第 2 步和第 3 步，一共做 y 次；
舍掉 P 的最右一位，得到的即為 m 和 r 的積。

換另一種說法：把前x位用一個單獨的數R0表示，中間y位用另一個數表示R1表示，輔助位用Z表示在這裡，要通過重複的把R0加上或者減去m來得到結果。具體如下：初始值R0=0,R1=r.Z=0,此時來考查yi和yi-1這兩位，在這裡就是m的最後一位和Z的值。這裡要說下為什麼每次看的都是這兩位了。在下邊每次運算後都會把R0,R1,Z中的值右移一次，RO的最後一位移入R1的高位，R1的最後一位移入Z。這裡要注意的是在右移R0時，如果他的最高位是1,則移位後最高位用１填充，如果最高位是０，移位後最高位用０填充。接下來要按m的最後一位和Z的值來判斷怎麼加減了：

如果為01,則R0+m，進位忽略。然後R0,R1,Z右移一位，再下一步判斷，直到把R0的每一位都判斷過後為結束
如果為10,則R0-m，借位忽略（只要x位的R0的值）。然後R0,R1,Z右移一位，再下一步判斷，直到把R0的每一位都判斷過後為結束
如果為00或是11,則R0的值保持不變。然後R0,R1,Z右移一位，再下一步判斷，直到把R0的每一位都判斷過後為結束

最後是結果，結果就是R0並上R1的值。比如R0=3,R1=25,結果就是325.

演算法原理

考慮一個由若干個 0 包圍著若干個 1 的正的二進制乘數，比如 00111110，積可以表達為：

$M \times \,^{\prime\prime} 0 \; 0 \; 1 \; 1 \; 1 \; 1 \; 1 \; 0 \,^{\prime\prime} = M \times (2^5 + 2^4 + 2^3 + 2^2 + 2^1) = M \times 62$

其中，M 代表被乘數。變形為下式可以使運算次數可以減為兩次：

$M \times \,^{\prime\prime} 0 \; 1 \; 0 \; 0 \; 0 \; 0 \mbox{-1} \; 0 \,^{\prime\prime} = M \times (2^6 - 2^1) = M \times 62.$

事實上，任何二進制數中連續的 1 可以被分解為兩個二進制數之差：

$(\ldots 0 \overbrace{1 \ldots 1}^{n} 0 \ldots)_{2} \equiv (\ldots 1 \overbrace{0 \ldots 0}^{n} 0 \ldots)_{2} - (\ldots 0 \overbrace{0 \ldots 1}^{n} 0 \ldots)_2.$

因此，我們可以用更簡單的運算來替換原數中連續為 1 的數字的乘法，通過加上乘數，對部分積進行移位運算，最後再將之從乘數中減去。它利用了我們在針對為零的位做乘法時，不需要做其他運算，只需移位這一特點，這很像我們在做和 99 的乘法時利用 99 = 100 − 1 這一性質。這種模式可以擴展應用於任何一串數字中連續為 1 的部分（包括只有一個 1 的情況）。那麼，

$M \times \,^{\prime\prime} 0 \; 0 \; 1 \; 1 \; 1 \; 0 \; 1 \; 0 \,^{\prime\prime} = M \times (2^5 + 2^4 + 2^3 + 2^1) = M \times 58$

$M \times \,^{\prime\prime} 0 \; 1 \; 0 \; 0 \mbox{-1} \; 0 \; 1 \; 0 \,^{\prime\prime} = M \times (2^6 - 2^3 + 2^1) = M \times 58.$

布斯演算法遵從這種模式，它在遇到一串數字中的第一組從 0 到 1 的變化時（即遇到 01 時）執行加法，在遇到這一串連續 1 的尾部時（即遇到 10 時）執行減法。這在乘數為負時同樣有效。當乘數中的連續 1 比較多時（形成比較長的 1 串時），布斯演算法較一般的乘法演算法執行的加減法運算少。

------------------------------------------------------------------------------------------------------

For 2-03,-------------------------------------------------------------------------------------------

概念題，瞭解

Pipelining/Cache

Ref. to 學貫EY814_計算機組織,5e（中譯本）_Ch08_管線處理.ppt

Ref. to 學貫EY814_計算機組織,5e（中譯本）_Ch05_記憶體系統.ppt

Cache快取

高速快取（英語：Cache），其原始意義是指存取速度比一般隨機存取記憶體（RAM）來得快的一種RAM，一般而言它不像系統主記憶體那樣使用DRAM技術，而使用昂貴但較快速的SRAM技術。

原理

Cache一詞來源於1967年的一篇電子工程期刊論文。其作者將法語詞「cache」賦予「safekeeping storage」的涵義，用於電腦工程領域。

當CPU處理資料時，它會先到Cache中去尋找，如果資料因之前的操作已經讀取而被暫存其中，就不需要再從隨機存取記憶體（Main memory）中讀取資料——由於CPU的執行速度一般比主記憶體的讀取速度快，主記憶體儲器周期（訪問主記憶體儲器所需要的時間）為數個時鐘周期。因此若要存取主記憶體的話，就必須等待數個CPU周期從而造成浪費。

提供「高速快取」的目的是為了讓資料存取的速度適應CPU的處理速度，其基於的原理是記憶體中「程式執行與資料存取的局域性行為」，即一定程式執行時間和空間內，被存取的代碼集中於一部分。為了充分發揮高速快取的作用，不僅依靠「暫存剛剛存取過的資料」，還要使用硬體實作的指令預測與資料預取技術——儘可能把將要使用的資料預先從記憶體中取到高速快取裡。

CPU的高速快取曾經是用在超級電腦上的一種高階技術，不過現今電腦上使用的的AMD或Intel微處理器都在晶片內部整合了大小不等的資料高速快取和指令高速快取，通稱為L1高速快取（L1 Cache 即 Level 1 On-die Cache，第一級片上高速緩衝存儲器）；而比L1更大容量的L2高速快取曾經被放在CPU外部（主機板或者CPU介面卡上），但是現在已經成為CPU內部的標準元件；更昂貴的頂級家用和工作站CPU甚至會配備比L2高速快取還要大的L3高速快取（level 3 On-die Cache 第三級高速緩衝存儲器）。

位址映象與變換

由於主記憶體容量遠大於高速快取的容量，因此兩者之間就必須按一定的規則對應起來。高速快取的位址映象就是指按某種規則把主記憶體塊裝入高速快取中。位址變換是指當按某種映象方式把主記憶體塊裝入高速快取後，每次存取高速快取時，如何把主記憶體的實體位址（Physical address）或虛擬位址（Virtual address）變換成高速快取的位址，從而存取高速快取中的資料。

映象和變換的方式有四種：直接映象、全相連映象、組相連映象、區段相連映象。

概念的擴充

現在高速快取的概念已被擴充，不僅在CPU和主記憶體之間有Cache而且在記憶體和硬碟之間也有Cache（磁碟高速快取），乃至在硬碟與網路之間也有某種意義上的Cache - Internet臨時資料夾──凡是位於速度相差較大的兩種硬體之間的，用於協調兩者資料傳輸速度差異的結構，均可稱之為Cache。

Pipelining指令管線化

RISC機器的五層管線示意圖

RISC機器的五層管線示意圖（IF：讀取指令，ID：指令解碼，EX：執行，MEM：記憶體存取, WB：寫回暫存器）

指令管線化是為了讓計算機和其它數位電子裝置能夠加速指令的通過速度（單位時間內被執行的指令數量）而設計的技術。

管線化是假設程式執行時有一連串的指令要被執行（垂直座標i是指令集，水平座標表時間t）。絕大多數當代的CPU都是利用時脈驅動。

而CPU是由內部的邏輯閘與正反器組成。當受到時脈觸發時，正反器得到新的數值，並且邏輯閘需要一段時間來解析出新的數值，而當受到下一個時脈觸發時正反器又得到新的數值，以此類推。而藉由邏輯閘分散成很多小區塊，再讓正反器鏈接這些小區塊組，使邏輯閘輸出正確數值的時間延遲得以減少，這樣一來就可以減少指令執行所需要的周期。

舉例來說，典型的RISC管線被分解成五個階段，每個階段之間使用正反器鏈接。

讀取指令
指令解碼與讀取暫存器
執行
記憶體存取
寫回暫存器

危害：當一名程式員（或者組合者/編譯者）編寫組合代碼（或者彙編碼）時，他們會假定每個指令是循序執行的。而這個假設會使管線化無效。當此現象發生後程式會表現的不正常，而此現象就是危害。不過目前有提供幾種技術來解決這些危害像是轉發與延遲等。

未管線化的架構產生的效率低，因為有些CPU的模組在其他模組執行時是閒置的。管線化雖並不會完全消除CPU的閒置時間，但是能夠讓這些模組並行運作而大幅提升程式執行的效率。

管線在處理器的內部被組織成層級，各個層級的管線能半獨立地單獨運作。每一個層級都被管理並且鏈結到一條「鏈「，因而每個層級的輸出被送到其它層級直至任務完成。處理器的這種組織方式能使總體的處理時間顯著縮短。

但並不是所有的指令都是獨立的。在一條簡單的管線中，完成一個指令可能需要5層。（如圖：RISC機器的五層管線示意圖）要在最佳效能下運算，當第一個指令被執行時，這個管線需要執行隨後4條獨立的指令。如果隨後4條指令依賴於第一條指令的輸出，管線控制邏輯必須插入延遲時脈周期到管線內，直到依賴被解除。而轉發技術能顯著減少延時。憑藉多個層，雖然管線化在理論上能提高效能，優勝於無管線的內核（假設時脈也因應層的數量按比例增加），但事實上，許多指令碼設計中並不會考慮到理想的執行。

微架構 (Microarchitecture)	管線層數 (Pipeline stages)
Sony Cell	23
IBM PowerPC 7	17
IBM Xenon	19
AMD Athlon	10
AMD Athlon XP	11
AMD Athlon64	12
AMD Phenom	12
AMD Opteron	15
ARM7TDMI(-S)	3
ARM7EJ-S	5
ARM810	5
ARM9TDMI	5
ARM1020E	6
XScale PXA210/PXA250	7
ARM1136J(F)-S	8
ARM1156T2(F)-S	9
ARM Cortex-A5	8
ARM Cortex-A8	13
AVR32 AP7	7
AVR32 UC3	3
DLX	5
Intel P5 (Pentium)	5
Intel P6 (Pentium Pro)	14
Intel P6 (Pentium III)	10
Intel NetBurst (Willamette)	20
Intel NetBurst (Northwood)	20
Intel NetBurst (Prescott)	31
Intel NetBurst (Cedar Mill)	31
Intel Core	14
Intel Atom	16
LatticeMico32	6
R4000	8
StrongARM SA-110	5
SuperH SH2	5
SuperH SH2A	5
SuperH SH4	5
SuperH SH4A	7
UltraSPARC	9
UltraSPARC T1	6
UltraSPARC T2	8
WinChip	4
LC2200 32 bit	5

優缺點

並非在所有情況下管線技術都起作用。可能有一些缺點。如果一條指令管線能夠在每一個時脈週期(clock cycle)接納一條新的指令，被稱為完整管線化(fully pipelined)。因管線中的指令需要延遲處理而要等待數個時脈週期，被稱為非完整管線化。

管線化的優點

減少了處理器執行指令所需要的時脈週期，在通常情況下增加了指令的輸入頻率(issue-rate)。
一些積體電路(combinational circuits)，例如加法器(adders)或者乘法器(multipliers)，通過添加更多的環路(circuitry)使其工作得更快。如果以管線化替代，能相對地減少環路。

沒有管線化的優點

非管線化的處理器每次(at a time)只執行一個指令。防止分支延時（事實上，每個分支都會產生延時）和序列指令被並列執行產生的問題。設計比較簡單和較低生產成本。
在執行相同的指令時，非管線化處理器的指令傳輸延遲時間(The instruction latency)比管線化處理器明顯較短。這是因為管線化的處理器必須在數據路徑(data path)中添加額外正反器(flip-flops)。
非管線化處理器有固定指令位寬(a stable instruction bandwidth)。管線化處理器的效能更難以預測，並且不同的程式之間的變化(vary)可能更大。

範例

[编辑] 一般的管線

一般的四層管線架構；不同的顏色格表示不同的指令

右圖是一般有4層管線的示意圖：

讀取指令(Fetch)
指令解碼（Decode）
執行指令(Execute)
寫回執行結果(Write-back)

上方的大灰色格是一連串未執行的指令；下方的大灰色格則是已執行完成的指令；中間的大白色格則是管線。

執行順序如以下列表所示：

時序	執行情況
0	四條指令等待執行
1	從主記憶體儲器(memory)中讀取綠色指令
2	綠色指令被解碼從主記憶體儲器中讀取紫色指令
3	綠色指令被執行（事實上運算已經開始(performed)）紫色指令被解碼從主記憶體儲器中讀取藍色指令
4	綠色指令的運算結果被寫回到暫存器(register)或者主記憶體儲器紫色指令被執行藍色指令被解碼從主記憶體儲器中讀取紅色指令
5	綠色指令被執行完畢紫色指令的運算結果被寫回到暫存器或者主記憶體儲器藍色指令被執行紅色指令被解碼
6	紫色指令被執行完畢藍色指令的運算結果被寫回到暫存器或者主記憶體儲器紅色指令被執行
7	藍色指令被執行完畢紅色指令的運算結果被寫回到暫存器或者主記憶體儲器
8	紅色指令被執行完畢
9	所有指令皆執行完畢

汽泡

一個氣泡在編號為3的時脈週期中，指令執行被延遲

主條目：氣泡 (電腦運算)

指令執行中產生一個「打嗝」(hiccup),在管線中生成一個沒有實效的氣泡。

如右圖，在編號為2的時脈週期中，紫色指令的讀取被延遲，並且在編號為3的時脈週期中解碼層也產生了一個氣泡。所有在紫色指令之後的指令都被延遲執行，而在其之前已經執行了的指令則不受影響。

由於氣泡使指令執行延遲了一個時脈週期，完成全部4條指令的執行共需要8個時脈週期。

而氣泡處對指令的讀取、解碼、執行與寫回都沒有實質影響。這可以使用nop代碼來完成。

[编辑] 範例一

一個典型的加法指令可能會寫成像ADD A, B, C，而中央處理器(CPU)會將主記憶體儲器(Memory)內 A 位置與 B 位置的數值相加後放到 C 位置。在管線化處理器內，管線控制器會將這個指令分拆成一連串微指令：

LOAD A, R1

LOAD B, R2

ADD R1, R2, R3

STORE R3, C

LOAD next instruction

R1, R2 和 R3是CPU內的暫存器(register是CPU裡面能夠快速存取的暫存記憶體)。主記憶體儲器內標註為A位置和B位置之存儲單元中的數值被載入（或稱複製）到暫存器 R1 和 R2 中，然後送到加法器中相加，結果輸出到暫存器 R3 中，R3 中的數值再被存儲到主記憶體儲器內標註為C位置的存儲單元。

而且在非管線化的例子，開始驅動加法動作到完成的時間是不變的。

在這個範例中的管線分為3層：載入，執行，存儲。每一步被稱為管線層（或稱管線階段）(pipeline stages)。

在非管線化處理器中，同一時間只允許一個層運作，所以必須等待指令執行完畢才能開始執行下一條指令。在管線化處理器中，所有的層能在同一時間處理不同的指令。當一條指令在執行層，另外一條指令在解碼層，第三條指令在讀取層。

管線沒有減少執行指令所花費的時間；它增加了在同一時間被處理的指令數量，並且減少了完成指令之間的延遲。隨著處理器中管線層的數量增加，能在同一時間被處理的指令數量也相應增加，也減少了指令等待處理所產生的延遲。現在生產的微處理器至少有2層管線。[來源請求]（Atmel AVR 與 PIC 微控制器都有2層管線）Intel Pentium 4 處理器有20層管線。

[编辑] 範例二

以下表格具體列出3層管線理論：

管線層(Stage)	說明(Description)
讀取(Load)	從主記憶體儲器中讀取指令
執行(Execute)	執行指令
存儲(Store)	將執行結果存儲到主記憶體儲器和/或者暫存器

以組合語言表示將會被執行的指令列表：

LOAD #40, A ; 讀取 40 載入 A 內

MOVE A, B ; 將 A 內的數據複製到 B 內

ADD #20, B ; 將 B 內的數據與 20 相加

STORE B, 0x300 ; 將 B 內的數據儲存到地址為 0x300 的存儲器單元

代碼的執行循序如下：

第1週期
讀取	執行	儲存
LOAD

從主記憶體儲器中讀取LOAD指令。

第2週期
讀取	執行	儲存
MOVE	LOAD

LOAD 指令被執行，同時從主記憶體儲器中讀取 MOVE 指令。

第3週期
讀取	執行	儲存
ADD	MOVE	LOAD

LOAD 指令在存儲層(Store stage)，LOAD 指令的執行結果 #40 (the number 40) 將被存儲到暫存器A。同時，MOVE 指令被執行。MOVE 指令必須等待 LOAD 指令執行完畢才能將暫存器A 中的內容移動到暫存器B 中。

第4週期
讀取	執行	儲存
STORE	ADD	MOVE

STORE 指令被載入，同時 MOVE 指令執行完畢，並且 ADD 指令被執行。

注意! 有時候，一個指令會依賴於其他指令的執行結構（例如以上的 MOVE 指令）。當一個指令因為操作數而需參照一個特定的位置，讀取（作為輸入）或者寫入（作為輸入），執行那些指令的循序不同於程式原本的執行循序能導致危害(hazards)。目前有機種技術用於預防危害，或者繞過(working around)它們。

[编辑] 複雜化

很多處理器的管線深度到5層、7層、10層，甚至31層（像是Intel Pentium 4 Prescott）。Xelerator X10q甚至有多於1000層的管線深度[1]。當程式出現分支將不利於過深管線，整條管線將會無效化。為了減輕此狀況，分支預測就變的重要。如果分支預測錯誤，也能夠藉由自行結束預測來避免加速惡化效率。在某些運用上，像是超級電腦運算，為了能夠將超長管線的運算優勢凸顯出來，會特地將程式寫的極少分支化來避免預測失敗，而且深度的管線化主要是為了能降低每個時脈執行的指令量而設計。當程式經常出現分支，把分支重新排序（像是將更為需要的指令提早放入管線中）而將明顯的降低損失的速度以避免將分支「沖垮」。像是gcov程式能夠使用一種覆蓋率檢查的技術檢查特定分支的執行頻率，但是這種檢查法經常是最佳化的最後手段。處理能力高的管線會因為很多分支的程式而降低效率，這是因為處理器不知道下一個要讀取的指令是甚麼，而需要等待完成分支指令而讓管線清空。處理完分支之後，下一個指令就要經過所有管線，直到整個指令集的結果出現，而處理器才會再繼續執行。而在極端的狀況下，管線化處理器的效能理論上可能會與未管線化處理器一致，甚至是每層管線都在待命狀態，而且指令經常在管線之中跑來跑去時的效能比較差一些。

由於指令管線化，處理器讀取機器碼時並不會立即執行。因為如此，在很接近的地方執行更新機器碼的動作就可能無法作用，因為這些機器碼已經進入預讀輸入隊列內。指令快取又會讓此現象更加惡化。不過這只會在能夠自我變更的程式出現此現象。

------------------------------------------------------------------------------------------------------

For 2-04 -------------------------------------------------------------------------------------

Cycles per instruction(CPI)

CPI: Cycles per Instruction
指一個指令執行的時候CPU的運行的周期。

In computer architecture, cycles per instruction (aka clock cycles per instruction, clocks per instruction, or CPI) is a term used to describe one aspect of a processor's performance: the number of clock cycles that happen when an instruction is being executed. It is the multiplicative inverse of instructions per cycle.

Explanation

Let us assume a classic RISC pipeline, with the following 5 stages:

Instruction fetch cycle (IF)
Instruction decode/Register fetch cycle (ID)
Execution/Effective address cycle (EX)
Memory access (MEM)
Write-back cycle (WB)

Each stage requires one clock cycle and an instruction passes through the stages sequentially. Without pipelining, a new instruction is fetched in stage 1 only after the previous instruction finishes at stage 5. Therefore without pipelining the number of cycles it takes to execute an instruction is 5. This is the definition of CPI.

With pipelining we can improve the CPI by exploiting instruction level parallelism. For example, what if an instruction is fetched every cycle? We could theoretically have 5 instructions in the 5 pipeline stages at once (one instruction per stage). In this case, a different instruction would complete stage 5 in every clock cycle, and therefore on average we have one clock cycle per instruction (CPI = 1).

With a single-issue processor, the best CPI attainable is 1. However with multiple-issue processors, we may achieve even better CPI values. For example a processor that issues two instructions per clock cycle (see Superscalar) can achieve a CPI of 0.5 when two instructions are completing every clock cycle.

[edit] Calculations

[edit] Multi-cycle example

For the multi-cycle MIPS, there are 5 types of instructions:

Load (5 cycles)
Store (4 cycles)
R-type (4 cycles)
Branch (3 cycles)
Jump (3 cycles)

If a program has:

50% R-type instructions
15% load instructions
25% store instructions
8% branch instructions
2% jump instructions

then, the CPI is:

CPI = (4 × 50 + 5 × 15 + 4 × 25 + 3 × 8 + 3 × 2) / 100 = 4.05.

[edit] Example

[1] A 40-MHz processor was used to execute a benchmark program with the following instruction mix and clock cycle count:

Instruction type	Instruction count	Clock cycle count
Integer arithmetic	45000	1
Data transfer	32000	2
Floating point	15000	2
Control transfer	8000	2

Determine the effective CPI, MIPS rate, and execution time for this program.

Total instruction count = 100000.

CPI = (45000*1 + 32000*2 + 15000*2 + 8000*2)/100000 = 155000/100000 = 1.55.

MIPS = clock frequency/(CPI*1000000) = (40*1000000)/(1.55*1000000) = 25.8.

Therefore:

Execution time (T) = CPI*Instruction count*clock time = CPI*Instruction count/frequency = 1.55*100000/40000000 = 1.55/400 = 3.87 ms.

------------------------------------------------------------------------------------------------------

For 2-05 -------------------------------------------------------------------------------------

------------------------------------------------------------------------------------------------------

For 2-06, 2-09-------------------------------------------------------------------------------------

在I/O系統架構，裝置控制器扮演CPU和裝置之間的溝通角色，在輸入/輸出作業中，CPU與裝置控制器傳送訊息的方式主要有三種：輪詢（Polling）、中斷（Interrupt）和直接記憶體存取（Direct Memory Access , DMA）。

直接記憶體存取DMA

直接記憶體存取（Direct Memory Access，DMA）是計算機科學中的一種內存訪問技術。它允許某些電腦內部的硬體子系統（電腦外設），可以獨立地直接讀寫系統記憶體，而不需繞道CPU。在同等程度的CPU負擔下，DMA是一種快速的數據傳送方式。很多硬體的系統會使用DMA，包含硬碟控制器、繪圖顯示卡、網路卡和音效卡。

直接記憶體存取

DMA 是所有現代電腦的重要特色，他允許不同速度的硬體裝置來溝通，而不需要依於 CPU 的大量中斷負載。否則，CPU 需要從來源把每一片段的資料複製到暫存器，然後把他們再次寫回到新的地方。在這個時間中，CPU 對於其他的工作來說就無法使用。

DMA 傳輸重要地將一個記憶體區從一個裝置複製到另外一個。當 CPU 初始化這個傳輸動作，傳輸動作本身是由 DMA 控制器來實行和完成。典型的例子就是移動一個外部記憶體的區塊到晶片內部更快的記憶體去。像是這樣的操作並沒有讓處理器工作拖延，反而可以被重新排程去處理其他的工作。DMA 傳輸對於高效能嵌入式系統演算法和網路是很重要的。

舉個例子，PC ISA DMA 控制器擁有 8 個 DMA 通道，其中的 7 個通道是可以讓 PC 的 CPU 所利用。每一個 DMA 通道有一個 16位元位址暫存器和一個 16 位元計數暫存器。要初始化資料傳輸時，裝置驅動程式一起設定 DMA 通道的位址和計數暫存器，以及資料傳輸的方向，讀取或寫入。然後指示 DMA 硬體開始這個傳輸動作。當傳輸結束的時候，裝置就會以中斷的方式通知 CPU。

DRQ 意為 DMA 要求；DACK 意為 DMA 確認。這些符號一般在有 DMA 功能的電腦系統硬體概要上可以看到。他們表示了介於 CPU 和 DMA 控制器之間的電子訊號傳輸線路。

------------------------------------------------------------------------------------------------------

For 2-07-------------------------------------------------------------------------------------

INT

RESET

------------------------------------------------------------------------------------------------------

For 2-08-------------------------------------------------------------------------------------

AMBA 2.0

Ref. to Introduction to AMBA Bus System.pdf

Ref. to AMBA Specification.pdf

------------------------------------------------------------------------------------------------------

For 2-10-------------------------------------------------------------------------------------

66Mhz * 256bits

=16896Mbits/s

=2112 Mbyte/s

------------------------------------------------------------------------------------------------------

For 2-11-------------------------------------------------------------------------------------

觀念題

Ref. to 學貫EY814_計算機組織,5e（中譯本）_Ch04_輸入／輸出組織.ppt

------------------------------------------------------------------------------------------------------

For 2-12-------------------------------------------------------------------------------------

AMAT=0.2*10ns+1ns=3ns

(0.2*10ns + 0.2*1ns) +0.8*1ns

CPU快取/cpu cache

在電腦系統中，CPU快取（CPU Cache，在本文中簡稱快取）是用於減少處理器訪問記憶體所需平均時間的部件。在金字塔式存儲體系中它位於自頂向下的第二層，僅次於CPU暫存器。其容量遠小於記憶體，但速度卻可以接近處理器的頻率。

當處理器發出記憶體訪問請求時，會先查看快取內是否有請求資料。如果存在（命中），則不經訪問記憶體直接返回該資料；如果不存在（失效），則要先把記憶體中的相應資料載入快取，再將其返回處理器。

快取之所以有效，主要是因為程式運行時對記憶體的訪問呈現局部性（Locality）特徵。這種局部性既包括空間局部性（Spatial Locality），也包括時間局部性（Temporal Locality）。有效利用這種局部性，快取可以達到極高的命中率。

在處理器看來，快取是一個透明部件。因此，程式設計師通常無法直接干預對快取的操作。但是，確實可以根據快取的特點對程式代碼實施特定優化，從而更好地利用快取。

性能評估模型

評估快取的性能通常使用平均記憶體訪問時間（Average Memory Access Time, AMAT）這一指標。在一個簡化模型中，該值可依下式求得：

$AMAT = T_{hit} + MR \times MP$

式中三項的意義：

$T_{hit}$ 為命中時間（Hit Time）：從定位快取塊、經標籤比較並選中，一直到傳回資料所需的時間。
為失效率（Miss Rate）：在特定次數的記憶體訪問中，發生快取失效次數所佔的比重。
為失效代價（Miss Penalty）：從定位快取塊、經標籤比較判定失效，然後再從記憶體中定位資料並載入快取，最後直到把目標資料返回所需的時間。

------------------------------------------------------------------------------------------------------

For 2-13-------------------------------------------------------------------------------------

3^4=81

3^5=243

3^6=729

------------------------------------------------------------------------------------------------------

For 2-14 -----------------------------------------------------------------------------

Frame buffer

Loop buffer

Branch target buffer

Translation look-aside buffer

Ref. to 學貫EY814_計算機組織,5e（中譯本）_Ch05_記憶體系統.ppt ch5.7

------------------------------------------------------------------------------------------------------

For 2-15 ---------------------------------------------------------------

------------------------------------------------------------------------------------------------------

For 2-16, 2-17, 2-20, 2-22, 2-25 ---------------------------------------------------------------

基本觀念題

------------------------------------------------------------------------------------------------------

For 2-18 -----------------------------------------------------------------------------

ARM中斷流程

程式的執行過程中，CPU經常會收到硬體中斷的訊號，告知硬體有些事情需要去處理，比如：OS的System Clock...等等。而ARM的外部硬體中斷訊號由IRQ及FIQ兩支訊號腳來控制，當IRQ(Interrupt Request)或FIQ(Fast Interrupt Request)，當IRQ或FIQ被觸發時，則ARM CPU將會強制的進入IRQ或FIQ模式，在ARM裏IRQ有r13/r14/spsr是banked register，FIQ則有r8/r9/r10/r11/r12/r13/r14/spsr，所以沒有banked register的部份，程式就必需自行處理保存資料，所以FIQ可提供比IRQ還要好的效能。

5.IRQ 和 FIQ 之間的區別
答：IRQ和FIQ是ARM處理器的兩種程式設計型態。IRQ是指中斷型態，FIR是指快速中斷型態。對于 FIQ 你必須儘快處理你的事情并離開這個型態。IRQ 可以被 FIQ 所中斷，但 IRQ 無法中斷 FIQ。為了使 FIQ 更快，所以這種型態有更多的影子暫存器。FIQ 無法呼叫 SWI（軟體中斷）。FIQ 還必須禁用中斷。如果一個 FIQ 例程必須重新啟用中斷，則它太慢了，并應該是 IRQ 而不是 FIQ。

I/O對應的方式

I/O mapped I/O(port-mapped I/O或Direct I/O)

I/O與memory均擁有自己的記憶體空間
需要特別的指令來處理I/O

好處是完全不用考慮記憶體空間被I/O佔用，缺點需要額外的指令專門處理I/O存取。

Memory Mapped I/O

I/O與memory共用記憶體空間
不需要特別指令來處理I/O
其實Memory mapped I/O只是將I/O的port或memory 映射(mapping)到記憶體位址(memory address)上，

其好處就是可以把I/O存取直接當成存取記憶體來用，缺點是有映射到的區域原則上就不能放真正的記憶體。

------------------------------------------------------------------------------------------------------

For 2-19,2-24 -----------------------------------------------------------------------------

Hyper threading

Pipeline stall Ref. to 學貫EY814_計算機組織,5e（中譯本）_Ch08_管線處理.ppt ch8.1~8.3

Cache

Forwarding

超執行緒（HT, Hyper-Threading）是英特爾研發的一個技術，於2002年發佈。超執行緒技術原先只應用於Xeon 處理器中，當時稱為「Super-Threading」。之後陸續應用在Pentium 4中，將技術主流化。早期代號為Jackson。

通過此技術，英特爾實現在一個實體處理器中，提供兩個邏輯線程。之後的Pentium D縱使不支援超執行緒技術，但就整合了兩個實體核心，所以仍會見到兩個邏輯線程。超執行緒的未來發展，是提升處理器的邏輯線程，英特爾有計劃將8核心的處理器，加以配合超執行緒技術，使之成為16個邏輯線程的產品。

英特爾表示，超執行緒技術讓（P4）處理器增加5%的裸晶面積，就可以換來15%~30%的效能提升。但實際上，在某些程式或未對多執行緒編譯的程式而言，超執行緒反而會降低效能。除此之外，超執行緒技術亦要作業系統的配合，普通支援多處理器技術的系統亦未必能充分發揮該技術。例如Windows 2000，英特爾並不鼓勵使用者在此系統中利用超執行緒。原先不支援多核心的Windows XP Home Edition卻支援超執行緒技術。

運作方式

每個單位時間內，CPU只能處理一個執行緒，以這樣的單位進行，如果想要在單位時間內處理超過一個的執行緒是不可能的，除非是有兩個核心處理單元。雙核心技術是將兩個一樣的CPU放置於一個封裝內（或直接將兩個CPU做成一個晶片），而英特爾的HT技術是在CPU內部僅複製必要的資源、讓CPU模擬成兩個邏輯核心；也就是一個實體核心，兩個邏輯核心，在單位時間內處理兩個執行緒，模擬雙核心運作。

Intel自Pentium開始引入超純量、亂序執行（en:Out-of-order_execution）、暫存器重新命名（en:Register renaming）、多指令解碼器等特性；這些特性的原理是讓CPU擁有大量資源以增加指令執行效率，可是在現實中這些資源經常閒置；為了有效利用這些資源，就乾脆再增加一些資源來執行第二個執行緒，讓這些閒置資源執行另一個執行緒，而且CPU只要增加少數資源就可以模擬成兩個邏輯核心。

[編輯] 顧慮

由於處理器實際上只有一個核心，能夠提升的效能約為5~15%左右，且萬一發生資源互搶的情形時，整體效能反而會下拉。這亦是AMD不提供虛擬雙核心處理器的理由。另外，由於架構的不同，AMD的處理器對多工處理的表現會較好，所以沒有迫切性令產品支援相關的技術。

要令到電腦支援超執行緒技術，必須要軟體和硬體的配合。處理器本身要支援超執行緒，晶片組亦要支援相關處理器。為此，當時的Intel推出了新的晶片組，i865PE和i875P。要充分發揮超執行緒的效能，使用者要使用Windows 2000之後的作業系統，而Windows XP家用版亦同樣支援超執行緒技術。除了微軟的Windows外，Linux kernel 2.4.x亦開始支援該技術。軟體方面，不是所有程式都可以發揮超執行緒，通常優化了多處理器的程式都可以支援到。此類軟體通常是圖形或視訊處理軟體。早期，遊戲軟體的支援是比較少。但隨著多核心技術的普及，愈來愈多遊戲軟體支援多線程的處理器。

[編輯] 使用HT技術的CPU

Pentium 4 CPU中，Northwood及其之後推出的版本內建超執行緒技術；但在早期的Northwood核心中，一些型號的HT技術被關閉，縱使有軟體偵測到超執行緒技術的存在，使用者並不可以啟用；而雙核心的Pentium D中也只有EE版提供HT技術。

英特爾的Core 2 Duo處理器則沒有HT技術。但處理器已整合了兩個實體核心，所以仍然支援兩個線程。

而英特爾在2008年推出的Intel Core i7及Intel Atom處理器又支援類似HT的技術，在 Nehalem 中，Hyper-Threading 大舉捲土重來。在 Intel NetBurst 架構的 Northwood 版本中開始導入的 Hyper-Threading－在 Intel 世界之外稱為 Simultaneous Multi-Threading (SMT)－是善用執行緒平行性的方法，讓單一核心在應用軟體層能提供兩個邏輯核心、而且確實可以提升一些效能。

Pipeline stall/ pipeline bubbling

The Major Hurdle of Pipelining—

Pipeline Hazards

There are situations, called hazards, that prevent the next instruction in the instruction

stream from executing during its designated clock cycle. Hazards reduce

the performance from the ideal speedup gained by pipelining. There are

three classes of hazards:

1. Structural hazards arise from resource conflicts when the hardware cannot

support all possible combinations of instructions in simultaneous overlapped

execution.

2. Data hazards arise when an instruction depends on the results of a previous

instruction in a way that is exposed by the overlapping of instructions in the

pipeline.

3. Control hazards arise from the pipelining of branches and other instructions

that change the PC.

Hazards in pipelines can make it necessary to stall the pipeline. In Chapter 1,

we mentioned that the processor could stall on an event such as a cache miss.

Stalls arising from hazards in pipelined machines are more complex than the simple

stall for a cache miss. Eliminating a hazard often requires that some instructions

in the pipeline be allowed to proceed while others are delayed. For the

pipelines we discuss in this chapter, when an instruction is stalled, all instructions

issued later than the stalled instruction—and hence not as far along in the

pipeline—are also stalled. Instructions issued earlier than the stalled instruction—

and hence farther along in the pipeline—must continue, since otherwise

the hazard will never clear. As a result, no new instructions are fetched during the

stall. In contrast to this process of stalling only a portion of the pipeline, a cache

miss stalls all the instructions in the pipeline both before and after the instruction

causing the miss. (For the simple pipelines of this chapter there is no advantage

in selecting stalling instructions on a cache miss, but in future chapters we will

examine pipelines and caches that reduce cache miss costs by selectively stalling

on a cache miss.) We will see several examples of how pipeline stalls operate in

this section—don’t worry, they aren’t as complex as they might sound!

Hazards are problems with the instruction pipeline in central processing unit (CPU) microarchitectures that potentially result in incorrect computation. There are typically three types of hazards:

data hazards
structural hazards
control hazards (branching hazards)

There are several methods used to deal with hazards, including pipeline stalls (pipeline bubbling), register forwarding, and in the case of out-of-order execution, the scoreboarding method and the Tomasulo algorithm.

Background

Further information: instruction pipeline

Instructions in a pipelined processor are performed in several stages, so that at any given time several instructions are being processed in the various stages of the pipeline, such as fetch and execute. There are many different instruction pipeline microarchitectures, and instructions may be executed out-of-order. A hazard occurs when two or more of these simultaneous (possibly out of order) instructions conflict.

[edit] Types

[edit] Data hazards

Data hazards occur when instructions that exhibit data dependence modify data in different stages of a pipeline. Ignoring potential data hazards can result in race conditions (sometimes known as race hazards). There are three situations in which a data hazard can occur:

read after write (RAW), a true dependency
write after read (WAR)
write after write (WAW)

consider two instructions i and j, with i occurring before j in program order.

[edit] Read After Write (RAW)

(j tries to read a source before i writes to it) A read after write (RAW) data hazard refers to a situation where an instruction refers to a result that has not yet been calculated or retrieved. This can occur because even though an instruction is executed after a previous instruction, the previous instruction has not been completely processed through the pipeline.

[edit] Example

For example:

i1. R2 <- R1 + R3
i2. R4 <- R2 + R3

The first instruction is calculating a value to be saved in register 2, and the second is going to use this value to compute a result for register 4. However, in a pipeline, when we fetch the operands for the 2nd operation, the results from the first will not yet have been saved, and hence we have a data dependency.

We say that there is a data dependency with instruction 2, as it is dependent on the completion of instruction 1.

[edit] Write After Read (WAR)

(j tries to write a destination before it is read by i) A write after read (WAR) data hazard represents a problem with concurrent execution.

[edit] Example

For example:

i1. R4 <- R1 + R3
i2. R3 <- R1 + R2

If we are in a situation that there is a chance that i2 may be completed before i1 (i.e. with concurrent execution) we must ensure that we do not store the result of register 3 before i1 has had a chance to fetch the operands.

[edit] Write After Write (WAW)

(j tries to write an operand before it is written by i) A write after write (WAW) data hazard may occur in a concurrent execution environment.

[edit] Example

For example:

i1. R2 <- R1 + R2
i2. R2 <- R4 + R7

We must delay the WB (Write Back) of i2 until the execution of i1.

[edit] Structural hazards

A structural hazard occurs when a part of the processor's hardware is needed by two or more instructions at the same time. A canonical example is a single memory unit that is accessed both in the fetch stage where an instruction is retrieved from memory, and the memory stage where data is written and/or read from memory.[1] They can often be resolved by separating the component into orthogonal units (such as separate caches) or bubbling the pipeline.

[edit] Control hazards (branch hazards)

Further information: branch (computer science)

Branching hazards (also known as control hazards) occur with branches. On many instruction pipeline microarchitectures, the processor will not know the outcome of the branch when it needs to insert a new instruction into the pipeline (normally the fetch stage).

[edit] Eliminating hazards

[edit] Generic

[edit] Pipeline bubbling

Bubbling the pipeline, also known as a pipeline break or a pipeline stall, is a method for preventing data, structural, and branch hazards from occurring. As instructions are fetched, control logic determines whether a hazard could/will occur. If this is true, then the control logic inserts NOPs into the pipeline. Thus, before the next instruction (which would cause the hazard) is executed, the previous one will have had sufficient time to complete and prevent the hazard. If the number of NOPs is equal to the number of stages in the pipeline, the processor has been cleared of all instructions and can proceed free from hazards. This is called flushing the pipeline. All forms of stalling introduce a delay before the processor can resume execution.

Data hazards

There are several main solutions and algorithms used to resolve data hazards:

insert a pipeline bubble whenever a read after write (RAW) dependency is encountered, guaranteed to increase latency, or
utilize out-of-order execution to potentially prevent the need for pipeline bubbles
utilize register forwarding to use data from later stages in the pipeline

In the case of out-of-order execution, the algorithm used can be:

scoreboarding, in which case a pipeline bubble will only be needed when there is no functional unit available
the Tomasulo algorithm, which utilizes register renaming allowing the continual issuing of instructions

We can delegate the task of removing data dependencies to the compiler, which can fill in an appropriate number of NOP instructions between dependent instructions to ensure correct operation, or re-order instructions where possible.

[edit] Register forwarding

Forwarding involves feeding output data into a previous stage of the pipeline. Forwarding is implemented by feeding back the output of an instruction into the previous stage(s) of the pipeline as soon as the output of that instruction is available.

[edit] Example

NOTE: In the following examples, computed values are in bold, while Register numbers are not.

For instance, let's say we want to write the value 3 to register 1, (which already contains a 6), and then add 7 to register 1 and store the result in register 2, i.e.:

Instruction 0: Register 1 = 6

Instruction 1: Register 1 = 3

Instruction 2: Register 2 = Register 1 + 7 = 10

Following execution, register 2 should contain the value 10. However, if Instruction 1 (write 3 to register 1) does not completely exit the pipeline before Instruction 2 starts execution, it means that Register 1 does not contain the value 3 when Instruction 2 performs its addition. In such an event, Instruction 2 adds 7 to the old value of register 1 (6), and so register 2 would contain 13 instead, i.e:

Instruction 0: Register 1 = 6

Instruction 2: Register 2 = Register 1 + 7 = 13

Instruction 1: Register 1 = 3

This error occurs because Instruction 2 reads Register 1 before Instruction 1 has committed/stored the result of its write operation to Register 1. So when Instruction 2 is reading the contents of Register 1, register 1 still contains 6, not 3.

Forwarding (described below) helps correct such errors by depending on the fact that the output of Instruction 1 (which is 3) can be used by subsequent instructions before the value 3 is committed to/stored in Register 1.

Forwarding applied to our example means that we do not wait to commit/store the output of Instruction 1 in Register 1 (in this example, the output is 3) before making that output available to the subsequent instruction (in this case, Instruction 2). The effect is that Instruction 2 uses the correct (the more recent) value of Register 1: the commit/store was made immediately and not pipelined.

With forwarding enabled, the ID/EX or Instruction Decode/Execution stage of the pipeline now has two inputs: the value read from the register specified (in this example, the value 6 from Register 1), and the new value of Register 1 (in this example, this value is 3) which is sent from the next stage (EX/MEM) or Instruction Execute/Memory Access. Additional control logic is used to determine which input to use.

[edit] Control hazards (branch hazards)

To avoid control hazards microarchitectures can:

insert a pipeline bubble (discussed above), guaranteed to increase latency, or
use branch prediction and essentially guesstimate which instructions to insert, in which case a pipeline bubble will only be needed in the case of an incorrect prediction

In the event that a branch causes a pipeline bubble after incorrect instructions have entered the pipeline, care must be taken to prevent any of the wrongly-loaded instructions from having any effect on the processor state excluding energy wasted processing them before they were discovered to be loaded incorrectly.

------------------------------------------------------------------------------------------------------

For 2-21-----------------------------------------------------------------------------

在我們的資料途徑中，最重要的結構就是暫存器檔案(Register file)。一個暫存器檔案包括一組暫存器，只要提供暫存器編號，就可一對暫存器進行讀寫動作。暫存器檔案可用D型正反器陣列加上一個讀寫埠的解碼器來建構。由於讀取一個暫存器不會對狀態有何影響，所以我門只需要一個暫存器編號做為輸入，而唯一的輸出即為暫存器所儲存的值。暫存器的寫入則需要三個輸入，一個是暫存器編號，一個是被寫入的資料，一個則是時脈以控制寫入的動作。

A register file is an array of processor registers in a central processing unit (CPU). Modern integrated circuit-based register files are usually implemented by way of fast static RAMs with multiple ports. Such RAMs are distinguished by having dedicated read and write ports, whereas ordinary multiported SRAMs will usually read and write through the same ports.

The instruction set architecture of a CPU will almost always define a set of registers which are used to stage data between memory and the functional units on the chip. In simpler CPUs, these architectural registers correspond one-for-one to the entries in a physical register file within the CPU. More complicated CPUs use register renaming, so that the mapping of which physical entry stores a particular architectural register changes dynamically during execution. The register file is part of the architecture and visible to the programmer, as opposed to the concept of transparent caches.

在CPU裏面最重要的結構就是暫存器檔案(Register File)。