Lecture 1 Introduction
l 舉Pentium IV 去介紹各個區塊是什麼東西
Datapath, Control, memory等構造
l Moore’s law 是說電晶體每年會成長一倍, 實際上是1.5年成長一倍
l Processor的成長率,1990年以前1.35, 之後1.58
l DRAM 4倍每三年
l Processor 和 Memory的速度差距50% 每年
l Power的需求也是逐年增加
l 4004à8008à8080à8086/8088à80286à80386à80486àPentiumàPentium Pro II IIIàPentium IV
Lecture 2 Instruction Set Architecture
l ISA Design Principle
使Hardware容易建立
Compiler可以最佳化performance, 和花最小的花費
l 基本的ISA分類
Accumulator
Stack
General purpose register
Register-memory
Register to register
l MIPS
3-address load store architecture
31 32-bit integer registers
32 32-bit floating-point registers
l Register 有他的名子, 數量, 和用途
32的數量是因為數量越少速度會越快
l 指令可以存取記憶體
l Big Endian , Little Endian
12345678h
Big Endian存12345678
Little Endian 存78563412
l Alignment看起來是將某些位置的值變成0 ß這部分不是很清楚
l Instruction Format
Op: operation code
Rs
Rt
Rd: destination register
Shamt:shift 大小 ß不知功用ß知道了!!
Funct:指令的功能
l MIPS 的Instruction Format
R-type : register type
I-type: immediate
J-type : jump
l Larger constant用兩個部份組合
Lui上部份
Ori 下埠費
l Shift指令用到Shamt:shift 大小, 之前我不知道的部份
Shift 和multiplies 有些是相同的, 乘以兩倍或是三倍
l 指令的功能
Or, ori
And, andi
Nor
Multiplyà mult 儲存HI LO
Divideàdiv LO HI
l Design principle
簡單
小 register 32
好的組合 3 instruction format
一般的狀況變快 52%指令有常數
Lecture 3 Instruction Set Architecture(II)
l Procedure
Caller 呼叫者, 回傳入參數
Callee 被呼叫者, 會傳回值
Procedure 狀態儲存使用stack
跳到callee jal
跳回callee jr
Procedure frame 是存在stack的值
l 對每個register做介紹
0
1
2~3 v0 v1
4~7 a0 a1 a2 a3 arguments
8~15 t0 t1.. t7 temporary
16~23 s0.. s7 callee saves
24~25 t8 t9 temporary
26~27 k0 k1 reserved for os
28 gp pointer to global area
29 sp stack pointer
30 fp frame pointer
31 ra return address
l MIPS Address mode
I type | Immediate addressing Base register PC relative addressing |
R type | Register addressing |
J type | Pseudodirect addressing |
l Assembler
將程式組成CPU看的懂得語言
Linker
將code和data放到memory
Loader
DLL(dynamically linked libraries)
l Compiler optimize
有很多的optimization name, 記不太起來.
l IA-32 Architecture
好像是說intel architecture 32 bit的部份
講了Intel歷年來的發展
l CISC(complex instruction set computer)
設計的目標: 簡化compilation, 最佳化code size
變動的格式, 2和3個運算元
豐富的位址格式
豐富的指令
豐富的資料型態
例子:Vax, Intel
問題:增加硬體設計的複雜度
l RISC
Fixed format instruction( 3 format)
3 operands, register register 運算
Load store address mode : displacement immediate
Lecture 4 Accessing and Understanding Performance
l Performance
Response time(latency)一個工作的回應時間
Throughput 作了多少工作
l Performance 的韻律學(metrics)期中考有考
Elapsed time 一個job的完成時間, 包含disk access, I/O
CPU time: system time , user time
User CPU time:
l 計算題的重點
Execution time = clock cycles/ clock rateß我常忘記這個
Execution time =clock cycle time * Instruction numbers * CPI
Clock cycles = insturction numbers * CPI
MIPS = instructions / execution time * 106
Performance = 1/time
Clock cycle time比較難了解ns (nero seconds), 應該是執行時間和clock rate 4Ghz 不同
比誰快
比指令多
求CPI
速度變快之後求clock rate
求MIPS
求Execution time
題目還蠻多的
l 頻估的標準Benchmark
最好用實際的應用來測試
小的benchmark比較好做標準, 但是也可能被濫用
最近的spec2000
l Performance Improvement
增加clock rate
降低CPI
Compiler 降低instruction count
l Amdahl’s Law
使用一段改良的部份去計算整體增加的倍數
先算execution time 改良的部份
在算新的和舊的的相比部份
Lecture 5 Arithmetic for Computers
l 如何表示負數
2’s complement: 兩個步驟complement the number, add 1
負數和整數可以直接相加, 其中carry in 和carry out在電路中是不同的進, 和出
l 32bit signed number
2147483647到-2147483648
l Overflow
Signed bit 不正確
l ALU
加法電路, 1-bit ALU, 32-bit ALU, subtraction,SLT(set less than), multiply有三個版本, divide 有三個版本
l Floating Point
Single precision(32bit): s 1 bit, exponent 8 bits, significand 23 bit
Double precision(64bit): s 1 bit, exponent 11 bits, significant 52 bit
Overflow:positive exponent too large
Underflow:negative exponebt too large
(-1)s*(F)*2E
l IEEE 754 standard
(-1)s*(1+F)*2E-127
Significant 要加一, exponent作移動會加上127, 所以要減回來
l Example:
將Floating point轉為decimal
將decimal 轉為Floating Point:我會將significant 1.XXX的部份算進去, 應該要減一
l Floating Point的加法
1. 將他的10進位變成相同
2. 加法
3. 正規劃結果normalize 1.XXX
4. 四捨五入
l ALU
有加法, and, or的邏輯單元
MUX(乘法) 有ALU(Add, and, or) 有Add
Lecture 6 Building Single-Cycle Datapath and Control Unit
如何設計processor, 這一章看不太懂
Data path: 抓指令單元(instruction fetch unit, read operand
Lecture 7 Multicycle Implementations
l Multicycyle 的優點
Cycle time減少
不同的指令花不同的cycle去完成
允許functional unit 可以在每個指令使用多次
l 五個執行步驟
抓指令
解碼抓register
執行, 記憶體計算或跳躍
記憶體存取
寫回
l CPI在multicycle CPU
平均約4.12
不會超過最糟的狀況5.0
l Exceptions
正常的跳躍是sequential, jumps, branches, calls, returns
指的是非程式控制的轉移
會跳到系統去執行Execption Handle, 得將使用者的狀態存下來
l 兩種不同的Execptions
Interrupts : 造成的原因external events, 和程式的執行不同步, 簡單的暫停和返回使用者的程式
Execptions: 造成的原因internal events(overflow 溢位, errors, faults記憶體), 和程式的執行同步化, 指令會被取消, 程式可能繼續或中斷)
Datapath中也有execption handle
Lecture 8 Pipelining
l Pipeline的每一個動作不是都是一樣大
但是會切成一樣大, 所以有些是空的
l 指令的執行
Single cycle implementation : 每個指令強迫變成一樣大
Multiple cycle implementation : 按照排隊clock cycle切割較小
Pipeline implementation: clock cycle 切割較小, 每個單位一樣大
l Pipeline Hazards
Structural hazards
Data hazards
Control hazards
可以用waiting去解決這些問題
l 解決structure Hazard 的方法
Stall
Split instruction and data memory
l Data hazard
Forwarding
Load 指令沒辦法用forwarding 解決只能用stall 解決àReordering code
l Control hazard解決方法
Stall: 會delay 3 clock cycle, 若是在ID stage解決會delay 2 clock cycle
Predict: 如果predict成功則沒有delay, 如果predict 失敗 浪費1 clock cycle, 並且要flush pipeline
Delay branch: 在branch 後面放一個和branch沒有關係的指令, 如果這樣的話, 那不就不用去predict了, 但是他說很少使用到這種狀況
l 用load指令去看pipeline裡面的所有動作
裡面的步驟看不太懂
l R-type指令只有四個stage
IF, Reg/Dec, Exec, Wr, 少了memory access
將bubble放到pipeline中, 沒有辦法解決, bubble, 好像直得部分都會影響, bubble和noop不同
使用noop
Store 只需要四個stage, 不用Wr, 因此都是noop取代
Beq 只需要三個stage, 不用Wr, Mem, 用noop取代
l Pipeline control 一些電路控制stage
l Pipeline設計原則
相同長度
少的instruction format
Memory的運算元只出現在load , store
Operands必須在memory 作aligned
Lecture 9 Pipelining(II)
l Datapath control得解決許多問題
Implement data forwarding
Load-use hazard
Branch
Flush pipeline
l Forwarding
使用在各個階段register存的值去作forwarding
並且有forwarding control
Forwarding 無法解決所有的hazard, forwarding 是相同的register, 只能用stall去解決, 並且要有hazard detect unit
l Dynamic branch prediction
1- bit BHT: 在一個loop, 固定會有兩次的miss
2- bit BHT: 要連錯兩次才改變狀態
l delay branch的方法
before branch instruction 從branch之前的資料抓過來
from the target address 從跳的位置去取過來
from fall through 從要跳過的位置去取過來
l 其他的Branch prediction 技術
問題: 如果predicted taken需要計算target address, 解決方法branch target buffer
Correlating predictor: 會儲存global和local的資料
Tournament branch predictor:
l Execption
Execption 也是在datapath有電路, 因為他在pipeline中有問題
Lecture 10 Advanced pipeline
l ILP(instruction level parallelism)
1. 加深pipeline, 我的感覺是將指令可以同時接收多個
2. 多個同時issue
l Multi-cycle processor的挑戰(這個應該是硬體可以一次抓兩個指令)
一個delay 會導致三個指令沒有用到
解法:用scheduling(就是排程去解決, 儘量把指令放在一起)
l IA-64 架構(這個應該是一台機器)
Register, register, RISC style instruction set
EPIC(explicitly parallel instruction computer)
以下的投影片的資料比較混亂, 都是跳躍的點一下
l superscalar
Multi-issue, dynamic scheduling(這些都好像是講tomasulo’s algorithm 或是scoreboarding的方法)
這些方法都forcus 在將CPI弄小
還舉Pentium 4為例子
l Thread Level Parallelism
這三個我都不熟
Fine-grained multi-threading:好像是每個指令都考慮到他的thread特性
Coarse-grained multithreading: 粗操的, 只有long stalls, 才做threading
SMT:
Intel HyperThreading Technology
Intel Xeon, 基本上是每個processor可以處理各自的Thread
l Memory general principle
Temporal locality: 這一次抓到這個位址, 在短時間, 還會在用到.
Spatial locality: 這個位址用到, 接連的位址, 也很可能會用到.
l Memory
Registeràcacheàmemoryàdiskàtape 往左速度越快, 往右速度越慢
並且有時間(spatial)和空間(temporal)的考量
Upper:靠近processor的記憶體
Block:區塊, 比較不知道是幹什摸的, 我想應該是一個單位的大小
Hit: 找到data
Hit rate:在upper level找到
Hit time:找到的時間
Miss: 在lower level找到
Miss rate=1- hit rate
Miss penalty:去取代一個在upper block的時間
Hit time << miss penalty (說大約要做500個指令)
l Direct mapped cache
講memory對到cache的值的結構, 我在想這是不是CPU看到的資料, 由他去抓這些資料, 不對, 應該說是CPU要使用memory的資料, 看是不是在cache裡面, 所以cache的存法, 應該是和memory類似, 因此他讀到的值是指到cache的東西, 如果抓不到, 要轉移到memory抓, 應該要有個轉移的方法
1KB Direct Mapped Cache的結構, 前面有validate bit, cache tag, cache data
l Block size
優點: 有spatial locality的優點
缺點: 降低block number, cache miss花的時間較久, 因為block 變大, 要傳資料(解決方法: early restart, critical word first)
l Write through & Write Back
Write through: 將資料一次寫到lower level(好處, 不會有不一致, 壞處, write stall 每次花時間寫到 memroy)
Write back: 將資料先寫到cache, 當要replace時才寫到memory(好處, 不會重複寫到某一個位置, 寫要two cycle, tag check + wirtes 要多花一些時間, 可以使用store buffer
l Write buffer
如果太多, 會是設計者的夢饜
投影片說不止 write through有用, write back 也有用這個東西在減少miss penalty
l Write policy
Write allocate: wirte miss 時, 將block load 到cache.(write miss,…., 不是read才會miss….)
Wirte around:寫到記憶體, 而不寫到cache.
l Memory的設計(增加頻寬去減少miss penalty
One-word-wide
Wide memory
Interleaved memory
Lecture 11 Measuring and Improving Cache Performance & Virtual Memory
l 算cache performance 時, 增加clock rate
clock rate 變快
performance 不會成比率增加還要算cache stall
cache stall 分為instruction stall 和instruction stall =number of read * miss rate * miss penalty
data stall = number of read * instruction/program * miss rate * miss penalty
加入clock rate加倍時miss penalty變加倍
l 圖形的解釋
有direct mapped(mod 4 後有一個位置)
2-way set associative(mod 4 後有2個位置)
fully associative(來一個放一個)
l 算tag size不太會
4bit 用來當block offset
用28-index bit * cache size
l L2設計方向
更大的cache, 更高的associativity, 更大的blocks
和L1設計的方向不同
l Virtual memory
現在的記憶體約512MBà29 bit
32bit可以對到更多的memory 約4G
使用page table當做轉換
l Page fault
如果page table 的validate bit 是off就會發生page fault
l LRU
使用一個bit去紀錄, 這個page table entry是否有再用, 會定時做清除動作, 當有新的要做replace的時候, 就將0 的做置換.
l Page table size
12 bit 用來存page offset, page size = 4K
220* 4 Bytes= 4M Bytes
l Inverted page table
好像是Virtual address和phisical address可以互換, 使用hash function, HAT(hash another table)
l Two-level page table
10 bit, 10 bit, 12 bit
也是可以算大小 4K + 4M
l Paging的策略
Page fault會花很多時間
LRU
使用Write back, write through太過花時間
l TLB(Translation Look-aside Buffer)
意義有點不明瞭, TLB + Cache 的結構
Lecture 12 Virtual memory
l Virtual memory算是disk storage的cache
其他概念Page, segment, page fault, address translation, page table, page replacement, page table size, inverted page table, two level-page tables, Translation Look-aside Buffer, TLB & caches, virtual caches
l Virtual memory的protection
Hardware 兩種mode: user mode和kernel mode
TLB有一個write access bit
Page tables 放在OS的位置空間
l Thrashing
在momory和disk中一直切換
l Three C
Compulsory
Capacity
Conflict
l Prefetch
事先抓資料, 可以減少CPU stall
兩種方法
Static: compiler 事先加上抓資料的instruction
Dynamic: Hardware 事先去找有抓memory的code
l Non-blocking cache
允許data cache miss 的時候再去hit 資料
Hit under miss
Hit under multiple miss
Miss upder miss
Lecture 14 Multiprocessor and Cluster
Cache coherency protocol(這個應該也是 synchronization)
Bus 的activity比較不懂
Invalidate protocol比update還要流行
Example: invalidate protocol + write back cache
楊佳玲 2004 fall advanced
Lecture 1 Introduce to computer architecture
簡介電腦的基本知識, 成長的圖形
Lecture 2 Performance & Cost Evaluation Instruction Set Design
l 一直強調simulation是現在很多人在做的研究
l Amdal’s law 速率增加的公式
l Basic ISA classes
l 大約有10種addressing mode
一般的operand type 和 size
Commaon operand types 約五種
DSP operand
Fixed point 就是算小數點
l Common operations
就是一般的包含運算阿 add, sub
資料轉移阿 load, store
控制阿 jump
System call 阿
Floating-point 阿 加法ㄚ, 檢法ㄚ
字串阿
SIMD(single instruction multiple data)一個指令有兩個資料, 可以分別乘
A | B
*
C|D
A*C|B*D
MAC 一個比較複雜的指令兩個指令的前面部份相乘再相加
Instruction set有幾種encoding方式
1. variable format不同的結構
2. fixed 固定的結構 固定放某些是某些資料
3. hybrid
l Instruction Set
variable format
變動大小可以有不同的address mode
可以將code降到最小
Fixed
適合addressing mode 教少
則是implementation會較簡單
Hybrid 混合式
l RISC 和CISC的比較
RISC的指令數是CISC的兩倍
RISC的效能約是CISC的三倍快
Lecture 3 pipelining & Dynamic instruction scheduling
ü 考三種pipeline hazard並且舉例,
Structure hazard
Data hazard
Control hazard
考三種data hazard 並且舉例, 投影片用sub和add做舉例, 並且指出哪一個register 有問題
RAW
WAR
WAW
Control Hazard on Branches 有三個stage stall, 如果猜對有one stage stall, 應該是這樣, 我這麼認為
Software scheduling也可以避免hazard(看起來是data Hazard)
Lecture 4 Dynamic Instruction Scheduling, Branch Predictiion, Speculative Execution
l Speculative execution 有下面三個項目
Branch prediction
Speculative tamasulo
Register renaming
l Correlating branch
是說branch 有相關性
例子
If(d=0)
d = 1;
if(d=1)
使用1-bit會完全猜不到, 使用2-bit會完全猜到
l Branch target buffer
Buffer 裡面放著branch 的index, 和banch要跳到的位址
沒有對到要花兩個cycle, 一個是update BTB, 一個是抓新的instruction
l Return Address Predictors
紀錄跳回來的位址, 跳的位置是個jump的位置, 使用stack 將它記起來, 約16個entry就可以減少很多的 miss
Lecture 5 Speculative Execution , Superscalar Processor, Compiler Techinques to Exploit ILP
Speculation: (不確定) 指令在不確定下也可以執行
就是當branch taken才執行的指令
通常和dynamic scheduling一起發生
l Hardware speculation
Tomasulo Algorithm分成兩種
Without speculation: Issue, Execution, Write Result(寫到register file or memory)
With speculation: Issue, Execution, Write result(寫到reorder buffer) HW buffer, commit(更新register file or memory)
當發生mispredict的時候, 會做flush的動作, 將pipeline的資料清掉
l Reorder buffer 和 physical register + register renaming
Reorder buffer 可以使register不再不確定, 將過期的register放掉
Renaming 會將architectureal registers 對到physical register set
l 這種分類不清楚
Data dependence(RAW)
Name dependence(WAW, WAR)
l Static Branch Prediction
Delayed branch 這個是在branch的空檔加上指令
Assist dynamic predictors 這個沒仔細介紹
Global code scheduling 全區的編碼
l Branch-delay slot補充的方法
Branch 之後的stall 可以用別的指令去取代
Before branch instruction 從branch之前去抓
From the target address 從目的位址
From fall through 從會跳過的位址
Lecture 6 Compiler Approach for Expoiting ILP, Midterm Review
l Static Branch Prediction
看起來是說固定猜對, 這樣的猜錯率會有34%
l Software pipelining
假如iteration 是獨立的, 可以將iteration 展開, 相同的部份用software 重新編排, 並且將這部份編成一個function, 這部份洪士灝好像沒有講清楚.
l Hardware 的memory reference speculation
意思是說, 將對memory沒有影響的指令作調換, 而且是用hardware做調換, 如果有關係的話該指令在重做
l VLIW的問題
Code size增加à對code作壓縮
連鎖指令à一個stall 造成全部的processor都stall
Binary code compatibilityà相容性, 這個比較不了解
l Dynamic scheduling
Out of order execution, 不是排順序的, 而是動態的挑指令來執行, 所以是out or order execution, 不過我覺得Tomasulo’s algorithm 好像是in order execution
l Dynamic branch prediction的技術
Local predictor
Correlation predictor
Tournament predictor
Return address predictor
Branch target buffer
Hardware base speculation, 這部分看不太懂
Lecture 7 memory hierarchy
l Write through和writeback的好壞處
WT: 好處, 可以保持資料一致性
Bad, write stall 花時間, pipeline 要等
WB: 同一個地方不會重覆一直在寫
Bad, 可能會有讀不到資料
Write allocate: write miss的時候, allocate block
Write not allocate(write around): write miss的時候, 不allocate block
l Example 感想
2-way 會使clock time增加
Clock time只對CPI有影響, 其他miss penalty的算法不變
進階問題: 假如30% 的miss penalty是overlap求AMAT?
有一個公式: miss latency=overlapped + miss penalty 看不出意義
l Improve cache performance
1. reduced miss penalty
2. reduced miss rate
3. reduce hit time
4. reduce miss rate/penalty via parallelism
l pseudo associativity 用direct mapped 模擬2-way set associate
壞處蠻多的
兩種hit的速度, CPU可能無法處理
速度可能不會更快, 當要找第二次的情形比較多的時候
Miss penalty可能更久
沒有填完
Technique |
|
|
|
|
|
|
|
|
|
l Memory
Dynamic random access memory(DRAM)
Dynamic的意思是他會每隔8ms reflash一次
它分成兩個方向抓資料
RAS Raw access strobe
CAS column access strobe
l Cache
SRAM(static random access memory)
沒有reflesh的動作
DRAM size比較大, SRAM比較貴
l Memory的架構
Simple
Wide
Interleaved(其中memory bank 也有independent的方式, 可以有nonblocking)
l 加快DRAM
Fast page mode
Synchronous DRAM:每個DRAM都有相同的clock
RAMBUS:對每一個DRAM提供介面, 每一個都有
l VM
一個由虛擬的對到實際記憶體的東西, 用page table去存對應的關係, 這樣的話可以用的記憶體利用和disk swap的方式, 可以增加實際記憶體的使用量.
Page Table, page, segment, page fault, address translation(virtual page number, page offset), Inverted Page Table, Hash Another Table(HAT), Translation Look-aside Buffer(TLB)
利用的技術 fully associative, page segment, LRU, Write back
l TLB有三種架構
傳統型: CPUàTLBàcacheàMemory
CPUàcacheàTLBàMemory
CPUàCache, TLBàMemory
l Virtual Cache
增加hit time
增加PIDàcontext switch
Aliases(Synonyms)兩個Virtual addresses對到同一個physical addresses
解法Hardware(Anti-aliasing)確認唯一
OS: page coloring 這部分一直考
Lecture 9 Multiprocessor
l Parallel computers
運用合作和溝通將問題更快速的解決.
遇到的問題, 如何溝通使用UMA或是NUMA
如何合作: synchronization (同步, 就是資料同步)
如何交換: bus , network (講到bus為主)
多少個processor比較適合
l Flynn 分類
SISD
MISD
SIMD
MIMD
l UMA
Uniform Memory Access
就是統一一個記憶體
l NUMA: Nonuniform Memory Access
就是每個processor有自己的記憶體
挑戰
溝通速度的頻頸
l 基本的Snoopy Protocols包含
1. Write Invalidate Protocol:
可以多個讀, 只有一個寫
寫到共享的資料, 傳送一個invalidate到所有的caches, 將所有的copy invalidate
如果沒有讀到, 又分成兩種方法, write through(一直更新最新的), write back(去cache裡找最新的copy)
2. Write Update Protocol: 寫到shared data將所有的copy都更新
如果沒有讀到, 記憶體都是最新的資料.
假如要寫的是相同的資料, 再同一個時間, 則是按照次序, bus會有次序
Write Invalidate 比較受歡迎
Snoopy cache state
CPU request | CPU read | CPU Write | ||
CPU read hit | CPU read miss | CPU Write hit | CPU Write miss | |
Invalidate (沒有資料) | Shared | Exclusive | ||
Shared (only read) | Shared | Shared | Exclusive | |
Exclusive (read/write) | Exclusive | shared | Exclusive | Exclusive |
BUS request | CPU read | CPU Write | ||
CPU read hit | CPU read miss | CPU Write hit | CPU Write miss | |
Invalidate (沒有資料) | Shared | Exclusive | ||
Shared (only read) | Shared | Shared | Exclusive Invalidate(bus write miss) | |
Exclusive (read/write) | Exclusive | Shared Shared(Bus read miss) | Exclusive | Exclusive Invalidate(Bus write miss) |
考前記憶
Write allocate 和 no-write allocate 是以lower level memory為觀點
Write allocate 是說memory 在write miss 時會load block 到cache.
No-write allocate 是說memory 被修改, 但是不 load 到cache
Write through 和 write back 是以cache 為觀點
Write through 是說 cache updateà memory update
Pros: no read miss, data consistency
Cons: write stall
Write back 是說 cache updateà when cache replace memory update
Pros:同一個資料不會一直update到memory
Cons: two cycle to update memory
';$(".articleExtAd").append(notVIP);setTimeout(function() {$('.top-toolbar').data('top-toolbar').setAD({title: "Computer Architecture \u694a\u4f73\u73b2 slides",label_id: 163,label_name: "\u96fb\u8166\u786c\u9ad4"});}, 2000);
再訪八里下一篇
紐約紐約 Mister Donut 甜甜圈專賣店...
離婚證人
留言列表
