# CS2006301 計算機組織 Computer Organization
Textbook: Patterson, D. A., Hennessy, J. L.（民104）。計算機組織與設計：硬體/軟體的介面（5E）。臺北市：臺灣東華、臺灣愛思唯爾。
Instructor: 陳錫明 Shyi-Ming Chen, 劉一宇 Yi-Yu Liu
###### tags: `TaiwanTech`, `CS`
## １計算機抽象化與科技
* 電腦的定義
* A device that computes, especially a programmable electronic machine
* 每當計算的成本下降成 1/10，使用計算機的機會即大增
* 歷史上的裝置
* 1822 Difference Engine 多項式計算
* 1889 Tabulating machine 人口普查
* 1944 Harvard Mark I 火砲射擊
* 1946 ENIAC 第一台全電子式可程式化通用計算機
* 十進位
* 真空管
* 每秒1900個加法
* 藉由纜線與開關設計程式
* 此後電腦開始商用
* 1959 IBM 1401
* 第一台電晶體電腦
* 計算應用種類與特性
* 個人型計算機 Personal computer, PC
* 1973 Xerox Alto
* bitmap螢幕
* 滑鼠
* 所見即所得編輯器
* 實驗性，未量產
* 計畫主持人 2009 獲得 Turing Award
* 1977 Apple 個人電腦
* 1981 IBM PC
* 造就 Intel 與 Microsoft
* 低成本
* 供應單一使用者的效能
* 執行其他公司的軟體（應用程式）
* 伺服器 server
* 以前大型主機、迷你計算機與超級電腦的現代版
* 藉由網路使用
* 一件大型工作，如科學或工程計算
* 多件小型工作，如大型網路伺服器
* 使用他處軟體(資料庫或模擬系統)，經常客製化調整
* 計算與輸出入容量的擴充性
* 可靠度
* 最低階差不多像是桌上型計算機，用於檔案儲存、小型商業應用或簡單網路服務
* 最高階是超級電腦(supercomputer)，包含數百至數千個處理器和照位元組的記憶體，用於高階科學及工程計算
* 嵌入式計算機 embedded computer
* 置入另一裝置，如汽車的微處理器、手機電視遊樂器與電視的計算機
* 執行單一應用或一組相關應用
* 與硬體整合
* 最低效能與成本功耗限制
* 1995 使用率前三：x86、6800、Hitachi SuperH
* 2002 使用率前三：arm、x86、Motorola 6800
* 後電腦時代的新計算機
* 個人行動裝置 personal mobile device, PMD
* 電池驅動
* 無線聯線
* 執行可下載的軟體應用(app)
* 不具鍵鼠、改由觸控或語音
* 智慧手機與平板是現在最大的處理器市場
* 庫房規模計算機 Warehouse Scale Computer, WSC
* 數據中心
* 用於雲端計算(Cloud Computing)
* 租用給他人提供軟體服務(軟體即服務, Software as a Service, SaaS)
* 取代伺服器
* 電腦發展受市場與需求影響：追求甜蜜點平衡
* 效能與準確
* 高階程式語言
* 相容性
* 電腦史能幫助計算機架構師發想未來可能性
* Computer Architecture = ISA+Machine Architecture
* VLSI -> Computer architecture -> Market
### 計算機架構中的八大理念
* 摩爾定律
* 積體電路的電晶體數量每18至24個月加倍
* 處理器速度每1.5年2倍
* 從3~5年的參考資料，猜測了50年的發展
* 記憶體容量也符合摩爾定律
* DRAM容量每3年4倍，每位元價格每年改善25%
* 硬碟容量每1年1.5~2倍，每位元價格每年改善100%
* 所以 Intel 創辦人原打算設計記憶體
* 效能提升也有點像摩爾定律
* 2006年後效能發展趨於平緩
* 電晶體的大小已從 100micro 到 nano 級
* 硬體的發展帶動資訊工程發展（優化軟體提升硬體使用的可能性）
* 應配合設計結束時的技術水準進行設計
* 抽象化
* 把下層化為邏輯模型，隱藏瑣碎的技術細節
* 經常的情形變快
* 針對經常情況做最佳化
* 應仔細實驗測量何為經常情況
* Amdahl 定律: $改善後執行時間=\dfrac{受改善影響部分的執行時間}{改善幅度}+不受影響部分的執行時間$
* 回收遞降定律 the law of diminishing returns
* 平行性
* 平行運算提升效能
* 管道化
* 串聯形式的特殊平行性
* 預測
* 預測夠準確且錯誤回復成本不算太高時，預先猜測結果並據以往下執行將更快速
* 階層
* 記憶體階層可創造出類似既大又快且便宜的記憶體
* 可靠性
* 加入冗餘額外組件，可在失效發生時接替並協助檢測失效情況，達成可靠(dependable)
### 你的程式之下
* 系統軟體
* 作業系統 operating system
* 基本輸出入
* 配置儲存
* 有保護的資源分享
* 編譯器 compiler
* 高階程式語言(high-levle programming language)翻譯成硬體指令
* 組譯器(assembler): 組合語言(assembly language)翻譯成機器語言(machine language)
### 覆蓋之下
* **計算機五大傳統標準要件**
* 輸入 input
* 10美金的滑鼠，光學模組占0.5~0.7美金
* 輸出 output
* 記憶體 memory
* 資料通道 datapath
* 控制 control
* 硬體
* 圖形顯示器
* 液晶顯示器 liquid crystal display, LCD
* 薄層液態聚合物，電場變化控制透光度
* 主動式矩陣(active matrix): 每個像素一個電晶體控制該像素
* 觸控螢幕
* 電容式為主
* 更新緩衝區(raster refresh buffer)／畫面緩衝區(frame buffer): 緩衝即將顯示的螢幕影像
* 積體電路 integrated circuit／晶片 chip
* 中央處理器單元 central processor unit／中央處理單元 central processing unit／CPU
* 資料通道 datapath: 算術運算
* 控制 control: 依指令控制資料通道、記憶體與 I/O
* 快取記憶體 cache memory: 更快更小的記憶體，靜態隨機存取記憶體(static random access memory, SRAM)，絕大多數空間都是快取記憶體
* 記憶體 memory: 存放執行中程式
* 動態隨機存取記憶體 dynamic random access memory, DRAM
* 主記憶體 main memory, primary memory
* 正在研發混合不揮發功能的記憶體
* 指令集架構 instruction set architecture／架構 architecture
* 硬體與低階軟體間的抽象介面
* 包括指令與所有可用硬體裝置
* 使上層設計者無須在意下層情況
* 非揮發性記憶體 nonvolatile memory
* 次記憶體 secondary memory
* 保存所有執行中與非執行中的資料與程式
* 記憶體階層中的較低階層
* 磁碟 magnetic disk
* 快閃記憶體 flash memory: 半導體記憶體
* 網路
* 通訊
* 資源共享
* 非本地存取
* 區域網路 local area network
* 乙太網路 Ethernet
* 廣域網路 wide area network
* 全球資訊網 World Wide Web／網際網路 Internet
### 建構處理器與記憶體的技術
* 1947 電晶體 貝爾實驗室
* 1958 積體電路 德州儀器
* 1971 Intel 4004 第一顆微處理器
* Intel 原本打算做記憶體，做微處理器時已接近破產
* 替人代工後取得設計著作權
* 80年代 IC 進入 VLSI
* RISC 開始發展
* 現在的 CISC 的底層設計也向 RISC 靠攏
* 積體電路製作流程
* 半導體材料、矽
* 可以變成導體、絕緣體或開關(電晶體 transistor)
* 香腸狀的矽晶磊(silicon crystal ingot)
* 細片成晶圓(wafer)
* 切割成晶粒(die)，也稱晶片(chip)
* 黏結 bonding: 聯結封裝的接角
* 缺陷 defect: 製作過程中難以避免的晶圓瑕疵
* 積體電路成本
* 晶粒成本=晶圓成本/(晶圓的晶粒數\*良率)
* 晶圓的晶粒數=晶圓面積/晶粒面積
* 良率(yield)=1/(1+每單位面積缺陷\*晶粒面積/2)^2
* 冪次數字與製程步驟數相關
### 效能
* MIPS = IC / 執行時間
* 缺少 CPI
* 反應時間 response time
* 一件工作從開始到結束的執行時間
* Elapsed time 含處理、輸出入、系統
* CPU time 僅計算處理器
* 常用於個人計算機
* 處理量 throughput/頻寬 bandwidth
* 單位時間內可完成的工作量
* 常用於資料中心
* 效能=執行時間的倒數
* 主要專注於反應時間
* 主要專注於中央處理器效能，不考慮系統與輸出入
* 改善效能就是降低執行時間
* 中央處理器執行需時=中央處理器執行時脈數/時脈速率
* 中央處理器時脈數=指令數\*指令平均時脈(CPI)
* $\dfrac秒{程式}=\dfrac{指令數}{程式}\times\dfrac{時脈數}{指令}\times\dfrac秒{時脈}$
* 電腦最基本的執行單位：instruction（assembly最接近）
* 電腦最基本時間單位：clock cycle
* 最基本指令需要幾個時脈：不一定

| 要素 | 指令數 | CPI | 時脈速率 |
|:---------------------:|:------:|:---:|:--------:|
| 軟體(演算法+程式語言) | Y | Y | N |
| 編譯器 | Y | Y | N |
| 指令集 | Y | Y | N |
| 組織 | N | Y | Y |
| 硬體 | N | N | Y |

### 功耗障壁
* CMOS(互補金氧半導體)電晶體功耗
* $能耗\propto\dfrac12\times電容性負載\times電壓^2\times切換頻率$
* 新世代製程降低電壓，電晶體功耗降低
* 電壓過低將要處理漏電的消耗(靜態功耗)
### 巨變：由單處理器轉移至多處理器
* 多處理器(多核)可以在處理量上改善微處理器
* 2003年處理器效能改善趨緩
* 平行程式撰寫較難
* 考慮底層硬體均衡負載
* 多核間通訊與同步花費
### 實例：測試 Intel Core i7
* 工作負載 workload: 一組被執行程式
* 測試程式 benchmark: 量測效能的程式
* 會影響針對較常見情形優化時的偏好
* Actual Target Workload: 對於平常工作的效能表現明顯，但跨平台不見得公平
* Full Application Benchmarks: 跨平台支援增加，但代表性降低
* Small Kernel Benchmarks: 簡單，但容易被欺騙
* Microbenchmark: 最不能代表實際應用程式
* SPEC 系統效能評估組織: 建立測試標準的組織，12個整數測試，17個浮點數測試，一套功耗測試(10%負載)
* 靠賣 benchmark source code 賺錢
* 各程式效率比值的幾何平均（避免執行時間算術平均的單一程式加權問題）
* Power Benchmark: 每單位能源可以執行多少指令
* 安兔兔: 手機跑分
## 指令：計算機的語言
* 指令集選用
* 硬體與編譯器容易建構
* 最高效能
* 最低成本與電耗
* MIPS R2000
* CPU
* 32個暫存器
* ALU
* 乘除法
* FPU
* 暫存器
* ALU
* Coprocessor
* 錯誤處理
### 計算機硬體的運作
* **規律性易導致簡單的設計 Simoplicity favors regularity**
* MIPS所有指令都只執行一種運算並使用三個變數
* 載入／儲存
* 計算
* 跳躍／分支
* 浮點數
* 記憶體管理
* 其他
* 僅有三種格式
* `#`: 註解
### 計算機硬體的運算元
* **越小就越快 Smaller is faster**
* 內部電子訊號傳遞距離短，時脈即可高
* 暫存器 registers: 指令的運算元，32個
* `$s`: 高階語言變數暫存器，8個
* `$t`: MIPS暫時暫存器，8個
* 進化
* Accumulator: 1個暫存器 acc = acc + mem[A]
* Stack: tos = tos + next
* General Purpose Register: 32
* A = A + B
* A = B + C
* L/S
* 字組 word: 32 位元
* 資料陣列
* `4N($sM)`
### 有號與無號數字
* 2的補數 two's complement（主流）
* x+<span style="text-decoration:overline">x</span>=-1
* 1的補數 one's complement
* 早期科學計算機使用，有正0與負0
* 偏移表示法 biased notation
* 全0最小，全1最大
### 在計算機中表示指令
* 機器語言 machine language
* 十六進位表示法
* 指令大多使用數字代表
* 內儲程式 stored-program: 記憶體儲存編輯器、原始碼、編譯器、機器碼與資料文字（馮紐曼架構）
* 二進碼相容性 binary compatibility: 指令集不改就能相容
* 指令格式 instruction format
* 32位元
* 欄位 field
* op: 運作碼(opcode)，6位元
* rs: 第一來源暫存器，5位元
* rt: 第二來源暫存器，5位元
* rd: 目的暫存器，5位元
* shmt: 位移量(shift amount)，5位元
* funct: 功能碼(function code)，6位元
* 常數或位址，16位元
* **好的設計需要有好的折衷 good design demands good compromises**
* 位址指標需要找方法能用較少的欄位長度表示出來
* 指令型態
* R型／R格式
* op+rs+rt+rd+shmt+funct
* I型／I格式
* op+rs+rt+constant
* 16位元的constant可以表示基底位置暫存器+-2^15^bytes距離的位置
* 換句話說暫存器變多會導致基底位置允許偏移量範圍變小
* 現在的暫存器數量大多是16或32個
* 多種格式增加硬體複雜度，但可以用使指令模樣相似一點稍微彌補
* opcode決定指令是R式或I式
* 暫存器運算與算數運算
* `lw` : 載入字組
* `sw` : 儲存字組
* `add` : 加
* `sub` : 減
* `addi` : 加立即值
* 對立即值做延伸後運算
### 邏輯運算
* 打包(packing)或取出(unpacking)字組內位元的運算
* 運算
* `sll` : 左移邏輯
* `srl` : 右移邏輯
* shamt 表示位移量
* 不使用 rs 和 funct
* `and` , `andi` : 及、及立即值
* `or` , `ori` : 或、或立即值
* `nor` : 反或
* `xor` : 互斥或
* 遮罩 mask: 用來過濾另一個暫存器資料的二進位數字樣式
* 要做出 not 使用 `nor` 與 0
* and 與 or 提供立即值版本，補 16 個零到高位形成常數
* C語言允許在字組中定義欄位 field，將多個物件打包入一個字組，使用 `and`、`or`、`sll`與`srl`操作欄位
### 能做決定的指令
* 分支指令
* 條件式分支 conditional branch
* `beq`: 若reg1==reg2則跳到label
* `bne`: 若不等...
* 無條件分支: unconditional branch
* `j`: jump
* 通常if-then-else會反轉condition，讓不符條件的跳到else
* 組譯器會協助處理分支位址
* 高階程式語言的優點在於不必明確寫出標籤與分支
* 同樣的指令可以處理迴圈
* 基本區塊 basic block
* 除結尾外沒有分支指令（結尾也未必要有），除開頭外沒有分支的標籤
* 編譯的第一階段工作就是分解出基本區塊
* 其他比較
* `slt`: 小於時設定，若reg2<reg3則reg1=1
* `slti`: 小於立即值時設定，若reg2<i則reg1=1\
* 組合以上四個指令就能達成六種邏輯比較然後分支
* 因「簡化」的設計理念，不設計相等或不等以外的分支指令
* 比較指令有無號版本（sltu與sltiu）
### 以計算機硬體來幫助程序呼叫
### MIPS 對 32 位元立即值及位址的定址法
### 平行性與指令：同步
### 翻譯與啟動一個程式
# 大且快：利用記憶體階層
- 區域性原則：程式在任何時候僅存取一小部分的位址空間
- 時間區域性：若一資料位置被存取，則可能其將再次被存取
- 空間區域性：若一資料位置被存取，則可能其附近資料位置將被存取
- 程式結構自然會產生區域性，如迴圈（時間區域性）、循序讀取指令或存取陣列（空間區域性）
- 記憶體階層：多層不同速度容量記憶體的結構
- 較快的記憶體單位成本較高、容量較小、離處理器越近
- 模擬出既大又快的記憶體使用
- 資料放置也依記憶體階層規則
### 快取的基礎
- 處理器與主記憶體間的記憶體階層
- 現亦可表示任何一種利用存取區域性的儲存體
- 直接對映
- 每個記憶體位置正好對映一個快取位置
- （區塊位址）取餘數（快取中的區塊數）
- 標籤：位於表格索引欄位，包含辨識快取字組是否為所需字組的位址資訊
- 有效位元：分辨空白區塊與有效資料區塊
- 大印象：在高階層預測所需資料，並保證錯失後在低階層尋找資料的機制
#### 存取一個快取
- 存取位址欄位
- 標籤欄位：與快取標籤位值比對
- 快取索引：選取區塊
- 本書架構
- 字組以4位元組對齊。最低2位元指向一個位元組在字組的位置，故忽略
- 考慮情形
- 32位元
- 直接對映
- 容量2個區塊，索引個位元
- 區塊2個字組，區塊字組使用個位元，其中兩個位元是位元組的部分
- 則標籤大小：
- 快取總位元數：
- 含有效欄位快取位元數：
- 較大的區塊可用空間區域性降低錯失率
- 但區塊大小佔不少的快取比例時錯失仍會上升（快取區塊數量變少）
- 且錯失成本增加，錯失懲罰（傳遞時間）因快取區塊大而顯著上升
- 儘早重新開始：
- 區塊字組一傳回即恢復執行
- 隱藏傳遞時間降低錯失懲罰
- 常見於處理器指令存取
- 對於資料存取效果較差。因資料字組較難以預測使用
- 所請求字組先送 或 重要字組先送：
- 從所需字組開始傳送至末尾，再傳送區塊前半部分
- 與儘早重新開始受限於相同特性
#### 處理快取錯失