zzun.net zzun's blog since 2001

Computer Architecture
SNU CSE / 2007 Spring / Prof. 민상렬

* Design Techniques (ex. Pipelining, Cache, Multiprocessor)
1. Engineering methodology
- common case를 optimize / rare case를 correct하게
2. Correctness criteria
- pipeline, cache 등의 테크닉을 사용하더라도 가장 simple한 디자인(테크닉 없는)에서와 같은 결과가 나오게
3. Evaluation methods
- Time(Resoponse time)과 Rate(throughput)
4. Technology trends
- VLSI에서 트랜지스터가 작아질 경우 : 집적도 향상 / signal path가 짧아짐 / switch 시간이 짧아짐(clock rate 향상)
- VLSI 기술 향상 속도에 비해 몇 배의 속도로 Computer Architecture가 발전하고 있음.

ISA design goals : max(Performance), min(Cost), min(Power Consumptioon)
ISA design constraint : Compiler 지원, OS 지원

CISC to RISC
- 과거엔 Memory 속도가 느렸기 때문에 하나의 instruction으로 최대한 많은 작업을 해야 했음(CISC)
- Cache, Pipelining, Single Chilp Processor의 등장으로 RISC로 발전함.

IBM System/360 : 최초로 한 ISA에 여러 Implemenatation : 다양한 성능의 욕구를 충족시킬 수 있게 됨

MIPS instructions
- addu (add unsigned) : overflow가 발생할 수 없음
- addi addiu는 있으나 subi subiu가 없는 이유 : addi addiu로 가능하고, I-format의 개수가 제한되어 있으므로(2^6)
- sll srl sra : logical shift는 0으로 채우고, arithmatic shift는 sign bit로 채움
- sh sb lh lb : Register의 4 byte 중 Least Significant Byte를 보내고 받음
- lhu (load halfword unsinged) : 읽어온 정보를 bit stream으로 취급하여 남은 16bit를 0으로 채움

MIPS Addressing Modes
- PC-relative branch : PC +- immediate
- Pseudo-direct addressing jump : PC 4bit + immediate 26bit + 00(2 bit)
- Addressing Mode가 복잡하면 pipelining이 어려우므로 RISC에서는 Load/Store Architecture

MIPS Register Convention
- for Interoperability between different compilers on the same ISA : seperate compilation
- $fp (frame pointer) : 같은 function 내에서도 $sp는 시간에 따라 바뀌므로 reliable pointer가 필요함

MIPS Calling Convention
- Hybrid between Caller-Save and Callee-Save : why? Evaluation method : min(Load/Store instructions)
- $a0-3, $v0-1, $ra는 무조건 caller-save : call(jal) 순간에 해당 레지스터의 값이 덮어써지므로 callee는 불가능

교재 : Computer Organization & Design / Patterson and Hennessy / Morgan Kaufmann
교수 : 김지홍 교수님
학기 : 2003 Spring

Chapter 6. Enhancing Performance with Pipelining

Pipelining Lessons
- single task의 latency에는 영향이 없음. throughput에만 영향.
- Potential Speedup = pipeline stage 수
- Pipeline rate는 slowest pipeline stage에 의해 제한된다.
- Unbalanced lengths of pipe stages는 speedup을 감소시킨다.
- fill과 drain도 역시 speedup을 감소시킨다.
- Stall for Dependences

Pipeline Hazards
- Structural hazards : Resource conflicts. HW적. 특별한 해결책X -> 2-port Memory
- Control hazards : 다른 inst'n의 결과가 현재 inst'n에 필요할때 -> Prediction, Delayed Branch
- Data hazards : Forwarding으로 해결 -> 예외 : Load-Use Hazard : Stall

Hazard Detection
- 이전 inst'n이 RegWrite & RD!=0 & RD = 현재 inst'n 소스(RS 또는 RT)

Branch Hazards : Prediction
- Static Prediction : Branch Not Taken
- Taken Branch Penalty : 3 cycles Stall
- improve : target address를 빨리 계산, branch 여부를 빨리 결정
- Dynamic Branch Prediction : Branch History Table에 최근 branch 결과를 저장.
- Delayed Branch Slot 채우는 방법 : From Before, Target, Fall through
- Delayed Slot 수행 중 Exception 발생시 : 그 Slot 바로 위의 Branch로 돌아와야 함.

Exception
- 같은 Cycle에서의 여러 Exception 발생 가능성
- 어떤 inst'n이 원인인가를 어떻게 detect?
- 여러 Exception들을 어떻게 우선순위?
- pipeline의 마지막 단계에 가서 Handler를 부름. 그 전까지는 State를 바꾸는걸 허용하지 않음.
- Precise interrupt : 발생이전 inst'n은 모두 수행. 그 이후는 모두 수행하지 않음.
                            interrupt 원인 inst'n을 알아내는게 어려움. 머신의 성능에 제한을 줌.

Advanced
- Superpipeling : 더 많은 pipelining stages
- Superscalar : Multiple inst'ns per stage
- Dynamic pipelinening : in-order issue -> out-of-order execute -> in-order commit

Pipeline Depth increse ->? Performance increse
- 한 stage의 clock이 줄어드는데 한계가 있음.
- 병렬성은 saturation 되는데 반해, overhead는 증가함.


Chapter 7. Large and Fast: Exploting Memory Hierarchy

Locality
- loops : temporal locality
- Sequential inst'n accesses : spatial locality
- Access to an array : spatial locality

Write Policy
- Write through : 메모리에도 씀. M의 data가 항상 최신! 성능떨어짐 -> Write buffer를 둠.
- Write back : dirty bit을 둠. read miss시 replace하면서 write의 overhead까지 떠안음.
                   write가 여러번 될때 유리. 빠름. 메모리 bandwidth를 적게 씀.

Write Miss Policy
- Write Allocate (fetch on write) : write-miss 발생시 block 로드. WB와 어울림.
- No-Write Allocate (write around) : Low-level에 쓰고, 캐쉬로는 읽어오지 않음. WT와 어울림.

Block size
- 크게할수록 Performance는 향상. Hit Time커짐, Miss Rate줄어듬. Miss Penalty커짐.
- 너무 커지면, 지나치게 많은 정보를 cache로 읽어오므로 성능떨어짐.(캐쉬가 충분히 크면 영향X)
- Miss Penalty 줄이기 : Early restart. 혹은 Requested/Critical word first

Average memory access time
= Hit time + Miss rate * Miss Penalty

Reduce Miss Rate
- N-way Set Associative Cache
- associativity가 커지면 : Set수 줄어듬. miss rate 줄어듬. hit time 커짐.

Reduce Miss Penalty
- second-level cache : 첫 cache보다 access time은 크지만, 용량이 크고 miss rate이 작음.
- Primary Cache는 hit time이 중요 : direct mapped
- Secondary Cache는 miss rate이 중요 : associative

Virtual Memory
- Motivation : 메모리 용량 한계. protection(safe sharing of M)

Miss Classification
- Compulsory misses : first access. Cold-start. -> 큰 블락 -> Miss Penalty 증가
- Capacity misses : cache size 때문에 발생 -> 큰 캐쉬 -> 억세스타임 증가
- Conflict misses : 여러블락 같은 셋. Full-Assoc.면 없어짐 -> 높은 Assoc. -> 억세스타임 증가


Chapter 8. Interfacing Processors and Peripherals

Bus의 장점
- Versatility : 새 장치 추가 쉽다. 같은 bus standard를 쓰는 다른 system으로 장치를 옮길 수 있다.
- Low Cost : 하나의 set으로 여러 용도에 사용.

Bus의 단점
- Communication bottleneck : Bus의 Bandwidth가 I/O의 throughput 최대값을 제한함.
- maximum bus speed의 제한 : 버스의 길이. 디바이스 갯수.