Processor Structure and Function

CPU Organization

- CPU는 뭘 하나? Fetch Instruction, Interpret instruction, Fetch data, process data, write data

- CPU의 주요 구성요소 : ALU, Control Unit, Register

Register

- CPU는 temporary storage와 같은 working space가 있어야 한다. (잠시 데이터를 저장하거나, 다음 명령어가 어디있는지 기억하는 것)

- 레지스터들은 CPU의 temporary storage

- 프로세서 디자인에 따라 function의 개수가 달라진다

- 메모리 계층에서 가장 위에 있는 것: 비싸고 빠른 storage의 small set

- Organization

* 두가지 타입

1) User Visible registers : may be referenced by assembly-level instruction

1 General-Purpose Registers

* May be true general purpose

* May be restricted (stack pointer,..)

* May be used for data or addressing

* Data (Accumulator..), Address (Segment, Stack Pointer..)

* General-Purpose vs Specialized

G : 유연성과 프로그래머 옵션을 증가시킨다. 하지만 명령어길이와 복잡도도 높아진다

S : 작고 빠른 명령어. 유연성이 떨아진다

뭐가 나은가? => 답은 없다

* 개수? 8~12

   적을수록 => 더 많은 메모리 참조

   More does not reduce memory references and takes up processor real estate

   RISC 참고. 수백개의 레지스터를 사용하는 것의 이로움

* 크기? full address를 저장 충분한 공간. full word 저장 충분한 공간. 두 개의 데이터 레지스터를 합치는 것도 가능함

2 Condition code Registers

* Sets of individual bits - 연산 결과로서 CPU에 의해 set

* 프로그램들에 의해 (절대적으로) 읽혀질 수 있다

* 프로그램에 의해 set 될 수 있다 (몇몇 명령어들은 컨디션 코드를 set/clear 가능)

2) Control  & Status Registers : used by control unit to control CPU operations and by OS programs

1 Program Counter

2 Instruction Register

3 Memory Address Register

4 Memory Buffer Register

5 Refresh your Memory

6 Program Status Word (PSW)

* set of bits

* Condition code 포함 (sign of last result, zero, carry, overflow, extension, equal)

* interrupt enable/disable, interrupt mask

* Supervisor 실행명령/접근 제어 관리

+ Kernel mode

+ Monitor mode

+ Allow privileged instructions to execute (system service call)

+ Used by OS

+ Not available to user programs

3) Other registers

* pointing Process Control block

* Interrupt vector register

* Page table pointer

-> OS support, 레지스터와 메모리 사이 할당에 관해 생각해야 함

Instruction Cycle

* 명령어를 가져오고 실행한다. 하나의 명령어가 끝나야 interrupt를 실행한다.

- Indirect Cycle

* fetch operand 하기 위해 메모리 액세스를 요청할 것이다. Indirect addressing은 더 많은 메모리 액세스를 요구한다.(한 명령어를 실행할 때 하나 이상의 operands가 메모리에 포함되어야 하므로..) 따라서 추가적인 instruction subcycle이 필요하다고 생각한 것! 이것이 indirect cycle

왼쪽 그림에 대해 설명하자면..

한 명령어가 fetch되었을 때 그것의 operand specifiers들은 identify되어야 한다. 메모리에 있는 각 input operand들은 그제서야 fetch되고 이 프로세스는 indirect addressing을 요청할 것이다. opcode의 내용이 실행되고 나면 메인 메모리에 결과를 저장해야 할 것

- Data Flow (instruction fetch)

* CPU의 디자인에 의존한다

* 일반적으로 Fetch란?

PC는 다음 명령어의 주소를 갖고 있다. 주소가 MAR로 이동하고, 주소는 address bus에 탄다. Control unit이 읽을 메모리를 요청한다. 결과가 data bus에 타고, MBR로 복사되괴, IR로 복사된다. 그리고 PC++

그림을 보면!

1 PC에서

2 MAR로 주소 이동

3 MAR에서 address bus를 타고 Memory로 이동 (메모리 주소 전달)

4 Control Unit이 메모리 읽겠다 신호

5 메모리의 결과값이 data bus를 타고 MBR로

6 MBR에서 IR로 복사

7 PC++

.. 그림은 Fetch를 나타낸 것

- Data Flow (Data Fetch)

* fetch cycle이 끝나면 control unit은 IR의 내용을 검사한다. (indirect addressing을 사용하는 operand specifier가 있는지)

* 있다면 indirect cycle이 수행됨 : 옆 그림을 봅세!

1 MBR의 가장 오른쪽의 N(which contain the address reference) 비트들이 

2 MAR로 전송됨 

3 Control Unit이 메모리 읽기를 요청하면

4 결과(원하던 연산의 주소)가 메모리에서 MBR로 이동

... 그림은 Indirect diagram을 나타낸 것

- Data Flow (Execute) (Operand fetch + 연산)

* fetch와 indirect cycle은 간단하고 예측 그낭하지만 execute cycle은 그닥..

* 이것의 form은 실행되는 명령어(IR에 있는)에 의존 

* 이 사이클은 메모리 r/w, I/O, Register transfers, ALU Operations 등을 포함

- Data Flow (Interrupt)

* 쉽고 예측 가능

* 현재 PC는 인터럽트 후 (하던일을) 계속할 수 있도록 저장해야 한다

그림 보면!

1 PC의 내용이 MBR로 복사된다 (메모리에 저장하기 위해)

2 (스택 포인터와 같은) special memory location이 control unit으로부터 MAR로 load된다 (이 memory location은 1번의 목적을 위해)

3 Control unit : write

4 MBR이 메모리에 쓰여진다

5 PC는 interrupt handling routine의 주소가 쓰여진다 

결과적으로 다음 instruction cycle은 올바른 명령어를 fetch하므로서 제대로 수행될 것이다

Instruction pipelining

- 공장 컨베이어 벨트와 비슷함. 다양한 스테이지의 상품들이 동시에 수행될 수 있어 성능이 향상된다

- 2 stage

1 Fetch

2 Execution

- Prefetch란?

* 메인 메모리에 액세스하는 fetch. execution은 메인 메모리에 잘 액세스하지 않는다.

  현재 명령어를 수행하는 중에 다음 명령어를 fetch 할 수 있는!! instruction prefetch, fetch overlap이라고 불린다. 이상적으로 명령어 사이클 시간이 반으로 줄어들 수 있다

* 메모리를 경쟁하거나, 실행하는 명령어가 branch라면 execute에 목적지 주소 계산이 포함되므로 prefetch가 무의미해진다. 이 두 가지 경우 외엔 prefetch로 성능 향상이 발생한다.

* 하지만 현실에선 성능이 두배가 되지 않는다. 왜?

fetch는 보통 execution보다 짧다. jump 또는 branch 명령은 그 prefetch된 명령어가 요구된 명령어가 아님을 의미한다

-> 성능향상을 위해 add more stage!

* branching instruction 다음의 명령어를 prefetch하는 것을 예측하므로서 branch로 인한 손해를 줄이고자 한다

   만약 branch되지 않으면, prefetched instruction을 사용한다. branch 된다면 prefetched instruction을 버리고 새로운 명령어 fetch

- Pipelining

* 더 많은 stage! -> 스피드업! (하나의 stage를 쪼갠다고 할 수 있다.. 세탁기에 많이 비유를 하던데 예를 들어 A집의 세탁기 한대가 빨래->탈수->건조 를 하고 B집에 분업화된 세탁기 3대, 각각 빨래 탈수 건조를 한다고 하고, 각각의 시간은 1씩 걸린다고 했을 때 A집에서 빨래 3덩이를 돌리면 (1+1+1)*3 = 9시간이 걸린다. 그런데 B집에서 3덩이를 돌리면 우선 첫번째 덩이를 빨래하고, 그 덩이를 탈수로 옮긴다. 빨래 세탁기에는 바로 두번째 덩이를 넣을 수 있다. 또 한 시간이 지나면 첫번째 덩이는 건조로, 두번째 덩이는 탈수로, 세번째 덩이는 빨래에 들어간다. 이런식으로 세번째 덩어리까지 건조를 마치면 총 5시간이 소요된다)

FI : Fetch Instruction

DI : Decode Instruction

CO : Calculate operands

FO : Fetch operands

EI : Execute instruction

WO : write result

(모든 명령어가 6개의 스테이지가 필요한 것은 아님)

옆 그림을 보면 각각의 스테이지들이 오버랩되는 것을 볼 수 있다.

만약 pipeline 하지 않았다면 6*9=54 time이 걸렸을  것.

speedup = 54/14

* Speedup Pipelining

+ n개의 명령어, k개의 스테이지라면, branch가 없다고 가정하면 실행시간은 -> n+k+1

+ pipelining 없이 실행시간은 -> kn (overhead가 발생하지 않고 파잎라이닝이 완벽히 맞을때)

명령어가 무한에 가깝게 많아지면 speedup = k

* Discussion

+ 모든 스테이지들이 한 명령어에 필요한 것은 아니다. LOAD는 WO가 필요없음

+ 모든 스테이지들이 병렬 실행될 수 있다고 가정

* Limitation by Branching

옆 그림을 보면 instruction 3은 instruction 15로의 conditional branch이다. 시간 7에서 instruction3이 실행되기 전까지는 다음 명령어의 주소를 알 수 없다. ->따라서 그뒤로 파잎라인이 비어있다

시간 9~12동안 다른 명령어는 완료되지 않는다 -> performance penalty

6 stage instruction cycle과 alternative pipeline depiction

* Limitation by data dependencies

현재 명령어에서, 아직 파이프라인에 있는 이전 명령어의 데이터가 필요하면...? 컴파일러나 프로그래머가 해결해야함

이럴 때엔 아무것도 안하는 명령어를 넣어서 시간을 벌거나.. 메모리엔 유효하지 않지만 process엔 유효한 데이터가 있어 이렇게 해결하기도... 밑에밑에 자세히 있음

* Performance of Pipeline

이상적으로, 더 많은 스테이지는 더 많은 스피드업. 하지만!

버퍼간에 데이터를 이동하면서 더 많은 overhead

more overhead in preparation

more complex circuit for pipeline h/w

* Branch 해결

1 Multiple Streams   

- 두 개의 pipeline

- 각 branch를 다른 pipeline에 넣고 적합한 pipeline을 이용한다

- 문제점 : bus & register contention delay , 첫 branch가 완료되기 전 또다른 branch가 pipeline에 들어올 때

- 어쨌든 성능 향상 가능

2 Prefetch Branch Target

- branch의 Target이 branch 다음의 명령어들과 함께 prefetch

- branch가 실행될 때까지 keep target

- if branch is taken, target is already prefetched

- 1보다 성능은 낮지만 복잡도도 낮아짐

3 Loop buffer

- 아주 작고 빠른 메모리

- IF stage에 의해 유지됨

- n개의 가장 최근에 fetch된 명령어들을 포함함

- 만약 branch가 taken되어야 한다면, 

h/w는 target이 버퍼에 있는지 체크. 있다면 다음 명령어가 버퍼로부터 fetch, 없으면 메모리에서 fetch

- 메모리 접근 시간을 줄이고 작은 loop나 jump에 유용하다

- 만약 버퍼가 모든 loop을 저장할 수 있을 만큼 크다면 loop에 있는 명령어들은 처음 실행될 때만 메모리에서 fetch된다

- cache

4 Branch prediction

- branch가 어디서 taken될 지 예측

- 예측이 맞다면 branch penalty가 없다. 예측이 틀렸다면 파이프라인을 비우고 올바른 명령어를 fetch한다. 따라서 branch penalty가 생긴다..

- Static : 

1) predict never taken

jump가 일어나지 않을 것이라 가정하고 항상 다음 명령어를 fetch

2) predict always taken 

jump가 일어날 것이라 가정하고 항상 target instruction을 fetch

3) predict by opcode

어떤 명령어들은 jump보다 다른 것들에 more likely to result -> 75% success

- Dynamic : 

1) taken / not taken switch 

예전 기록에 기반. loop에 적합

2) branch history table

like a cache to look up

오른쪽 그림을 간단히 설명하자면, 가장 왼쪽 위 동그라미에서.시계방향으로 1 2 3 4라고 했을 때

1 일어난다고 예측했지만 -> 2 일어나지 않았고, 또 일어나지 않는다면 -> 3 일어나지 않을 것이라 예측한다. 그런데 일어난다면-> 한번은 더 일어나지 않을 것이라 예측한다. 그런데 일어난다면 -> 1로 간다

5 Delayed Branching

- 해야 될 때까지 jump하지 않는다.

- 명령어를 rearrange한다 -> 그렇게 하여 branch 명령어가 실제로 원해진 시간보다 늦게 발생되도록