[컴퓨터구조] 파이프라인

글의 참고

- https://en.wikipedia.org/wiki/Instruction_pipelining#cite_note-Guardian-3

- https://namu.wiki/w/%ED%8C%8C%EC%9D%B4%ED%94%84%EB%9D%BC%EC%9D%B8

- https://en.wikipedia.org/wiki/Hazard_(computer_architecture)

- http://www.edwardbosworth.com/My5155_Slides/Chapter11/PipeliningTheCPU.htm

---

글의 전제

- 내가 글을 쓰다가 궁금한 점은 파란색 볼드체로 표현했다. 나도 모르기 때문에 나중에 알아봐야 할 내용이라는 뜻이다.

- 밑줄로 작성된 글은 좀 더 긴 설명이 필요해서 친 것이다. 그러므로, 밑 줄 처친 글이 이해가 안간다면 링크를 따라서 관련 내용을 공부하자.

---

글의 내용

- 파이프라인, 인스트럭션, 단계(클락)

: `인스트럭션 파이프라인`은 하나의 명령어를 여러 개의 단계로 쪼개서 각 단계를 프로세서안에 존재하는 독립적인 모듈들이 병렬적으로 처리할 수 있도록 하는 메커니즘이다. 아래 그림은 `5단계 파이프라인`을 보여준다. 각 명령어는 `IF, ID, EX, MEM, WB` 단계로 쪼개지고, 각 단계는 클락 사이클에 맞춰서 병렬적으로 처리가 된다.

In computer engineering, instruction pipelining is a technique for implementing instruction-level parallelism within a single processor. Pipelining attempts to keep every part of the processor busy with some instruction by dividing incoming instructions into a series of sequential steps (the eponymous "pipeline") performed by different processor units with different parts of instructions processed in parallel.
...


- 참고 : https://en.wikipedia.org/wiki/Instruction_pipelining

: 파이프라인에서 자주 인용되는 아키텍처가 `MIPS`다. `MIPS`의 5단계 파이프라인은 다음과 같다.

1.   Fetch instruction from memory.
2.   Decode the instruction and read two registers.
3.   Execute the operation or calculate an address.
4.   Access an operand in data memory or write back a result.
5.   For LW only, write the results of the memory read into a register.

- 참고 : http://www.edwardbosworth.com/My5155_Slides/Chapter11/PipeliningTheCPU.htm

: 파이프라인 클락 속도는 가장 느린 단계의 클락에 맞춰진다. 만약, 가장 빠른 단계에 사용되는 클락에 맞출 경우, 상대적으로 느린 단계들은 일을 마무리하지 못하기 때문이다. 가장 느린 클락에 맞추면, 빨리 끝난 단계는 약간의 대기만 하면 된다.

 

 

: 아래 그림에서 맨 위의 `Waiting instructions`은 아직 처리되지 않은 명령어들이 있는 영역이고, `Completed instructions`은 이미 처리가 완려된 명령어들이 있는 영역이다. 그리고, 중간 영역이 실제 파이프라인이 수행되는 영역이다. 아래의 그림은 4단계 파이프라인 구조를 보여준다. 아래의 각 박스들이 각 단계에서 독립적, 병렬적으로 처리된다는 것을 눈여겨 봐야 한다. 

https://en.wikipedia.org/wiki/Instruction_pipelining#/media/File:Pipeline,_4_stage.svg

 

- Superpipelines

: `슈퍼파이프 라인`은 명령어를 더 많은 단계로 쪼개는 것을 의미한다. `파이프라인`의 목적은 각 단계는 하나의 클락으로 처리될 수 있도록 설계하는 것이다. 그런데, 각 단계는 프로세서안의 독립적인 모듈이 실행을 하는데, 클락 하나만으로 처리가 쉽지 않은 경우가 대 다수인 것 같다. 그런데, `슈퍼파이프 라인`은 각 단계가 하나의 클락에 대응하도록 하는 구조이다. 즉, `슈퍼파이프 라인`에서 클락을 높이면, 성능이 엄청나게 빨라진다는 의미가 된다. 예를 들어, 위 그림에서 `5단계 파이프라인`이 아닌, `1단계 파이프라인`이라고 해보자. `5단계 파이프라인`구조에서는 5개의 명령어가 7클락이면 끝난다. `1단계 파이프라인`은 병렬 구조로 처리가 불가능하므로, 하나의 명령어가 모두 끝나야, 다음 명려어가 실행된다. 결국, `명령어 5개 * 각 명령어 5 단계` 해서, 25 클락이 필요하다.

As the pipeline is made "deeper" (with a greater number of dependent steps), a given step can be implemented with simpler circuitry, which may let the processor clock run faster. Such pipelines may be called `superpipelines`.

- 참고 : https://en.wikipedia.org/wiki/Instruction_pipelining#cite_note-Guardian-3

 

- Stall

: 파이프라인 구조는 `순차 실행 모델`에 최적화 되어있는 모델이다. 그런데, 명령어를 처리하던 도중에, 즉, 하나의 명령어 처리가 끝나지 않았는데, 다른 명령어를 처리하는 루틴으로 옮겨지면 기존의 처리하던 작업들은 폐기되고 새로운 명령어를 처리하는 파이프라인이 시작된다. 이렇게 분기시에 다른 기존 명령어들을 폐기하는 것을 `stall`이라고 부른다. 그런데, `stall`은 폐기가 아닌 `지연`의 의미로 더 많이 쓰인다. 즉, `stall`은 동기화를 맞추기 위해 특정 사이클 동안 더 이상 단계를 진행하지 않는 것을 의미도 있다.

When operating efficiently, a pipelined computer will have an instruction in each stage. It is then working on all of those instructions at the same time. It can finish about one instruction for each cycle of its clock. But when a program switches to a different sequence of instructions, the pipeline sometimes must discard the data in process and restart. This is called a `stall`.

Much of the design of a pipelined computer prevents interference between the stages and reduces stalls.
...
- 참고 : https://en.wikipedia.org/wiki/Instruction_pipelining

To achieve high performance, modern processors are pipelined. They consist of multiple parts that each partially process an instruction, feed their results to the next stage in the pipeline, and start working on the next instruction in the program. This design expects instructions to execute in a particular unchanging sequence. Conditional branch instructions make it impossible to know this sequence. So conditional branches can cause "stalls" in which the pipeline has to be restarted on a different part of the program.

- 참고 : https://en.wikipedia.org/wiki/Branch_(computer_science) [ Performance problems with branch instructions ]

 

- Structural Hazard

: 시스템에 하나만 존재하는 리소스(Memory, ALU, Register 등)에 동시에 접근할 때, 발생한다(`리소스 해저드`라고도 한다). 대개, `IF`와 `MEM` 과정에서 발생한다. 왜냐면, 2개다 메모리에 접근하기 때문이다. 해결 방법은 2가지가 있다.

0" Bubble을 삽입한다.
1" 코드 영역과 데이터 영역을 나눔

: `IF`와 `MEM` 단계에서 충돌하는 이유는 아래의 그림으로 설명이 가능하다. 첫 번째 명령어의 `MEM`와 네 번째 명령어의 `IF`가 충돌하는 것을 볼 수 있다. 왜 충돌할까?

: 아래 그림을 보면, 메모리가 한 개인 것을 볼 수 있다. 즉, 한 클락에 한 번씩만 접근이 가능하다.

: 이 문제를 해결하는 방법은 간단하다. 메모리를 명령어 영역과 데이터 영역으로 나누면 된다. 그런데, 메모리는 2개로 나누는 것은 이전 모델의 호환성을 지키지 못하게 됨으로 좋은 방법이 아닌 듯 하다. 더 좋은 방법은 메모리를 여러 계층 구조로 나누는 것이다. 메모리에 위에 명령어 캐시와 데이터 캐시를 두고 CPU는 명령어가 없으면 메모리에서 명령어를 읽어와 명령어 캐시에 저장하고, 데이터가 없으면 데이터를 읽어와서 데이터 캐시에 저장하는 구조를 이용하면, 2개의 캐시가 서로 독립적이기 때문에 `IF` 단계는 `MEM`, `WB` 단계에 영향을 주지 않는다. 반대도 마찬가지다. 이렇게, 구조적 해저드를 막을 수 있다.

 

- Data Hazard

: `순차 실행 모델`은 각 명령어들이 다음 명령어가 시작되기 전에는 완료가 되었다고 전제한다. 근데, 파이프라인에서는 이러한 가정이 들어맞지 않는다. 왜냐면, 명령어를 여러 단계로 쪼갰기 때문이다. 아래에서 `add 1 to R5(명령어 1)`는 5개의 단계로 구성되어 있다고 치자. 그리고 `copy R5 to R6(명령어 2)`도 마찬가지다. `명령어 1`이 `t1`에서 시작해 `t5` 시점에 마무리 된다. `명령어 2`는 `t2`에서 시작해 `t6`에서 끝난다. 그런데, `명령어 2`에서 R5를 가져오는 단계, 즉, 2와 3 단계(명령어를 해석해서 실행하는 단계)를 거치면 R5에 값을 가져오게 된다. 그런데, 파이프라인 구조에서는 저 시점에 아직 `명령어 1`이 완벽하게 끝나지 않았다. 즉, R5에 플러스 1을 하지 않았다. 이런 상황을 `RAW(Read-After-Write) Data Hazrd`라고 정의한다. 즉, 후속 명령어 `디코드` 단계가 앞 명령어 `실행`에 의존하는 경우를 의미한다.

(i2 tries to read a source before i1 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 prior instruction, the prior instruction has been processed only partly through the pipeline.

- 참고 : https://en.wikipedia.org/wiki/Hazard_(computer_architecture)

 

: 그런데, 데이터 해저드는 RAW만 있는게 아니다. `WAR, WAW` 도 존재한다.

The model of sequential execution assumes that each instruction completes before the next one begins; this assumption is not true on a pipelined processor. A situation where the expected result is problematic is known as a `hazard`. Imagine the following two register instructions to a hypothetical processor:

1: add 1 to R5 2: copy R5 to R6

If the processor has the 5 steps listed in the initial illustration (the 'Basic five-stage pipeline' at the start of the article), instruction 1 would be fetched at time `t1` and its execution would be complete at `t5`. Instruction 2 would be fetched at `t2` and would be complete at `t6`. The first instruction might deposit the incremented number into R5 as its fifth step (register write back) at `t5`. But the second instruction might get the number from R5 (to copy to R6) in its second step (instruction decode and register fetch) at time `t3`. It seems that the first instruction would not have incremented the value by then. The above code invokes a hazard.

Writing computer programs in a compiled language might not raise these concerns, as the compiler could be designed to generate machine code that avoids hazards.

- 참고 : https://en.wikipedia.org/wiki/Instruction_pipelining

: 이런 `데이터 해저드`를 해결하는 3가지 방법이 있다.

0" Bubble 삽입
1" Operand forwarding
2" Re-ordering by compiler

 

- Bubble

: `파이프라인 프로세서`에서 `버블`은 `Pipeline stall` 이라고도 불린다. `버블`은 파이프라인 디코딩 과정에서, 해석된 명령어가 특정 값을 가져와야 하는 상황일 때, 해당 값을 읽어야 할지 말아야 할지를 결정한다. 이 결정은 앞에서 먼저 실행되고 있는 명령어에 따라 달라진다. 위에 `Hazard`의 예시를 참고하도록 하자. `버블`은 단계를 지연시킨다. 앞에서 먼저 실행되고 있는 명령어가 해당 데이터에 쓰기를 완료하면, 그 때 다시 단계를 재개한다. 대개, `버블`은 각 CPU의 `NOP` 명령어를 통해서 생성한다.

In the design of pipelined computer processors, a `pipeline stall` is a delay in execution of an instruction in order to resolve a hazard.

In a standard five-stage pipeline, during the decoding stage, the control unit will determine whether the decoded instruction reads from a register to which the currently executed instruction writes. If this condition holds, the control unit will stall the instruction by one clock cycle. It also stalls the instruction in the fetch stage, to prevent the instruction in that stage from being overwritten by the next instruction in the program.

- 참고 : https://en.wikipedia.org/wiki/Pipeline_stall

 

: 아래에서 볼 수 있다시피, 보라색 박스의 `Decode` 단계가 녹색 박스의 `Execute`단계에 의존하다 보니, 한 단계를 `지연`했다. 이 지연된 단계를 `버블`이라고 한다. 버블이 하나 발생하면, 그 뒤에 처리되야 하는 모든 명령어의 단계들이 1단계씩 지연된다. 버블이 파이프라인 사이클에서 사라지고 나면, 그제서야 다시 정상적인 사이클이 시작된다. 즉, 6 클락부터는 정상적인 사이클로 복귀한다. 그러나, 버블 때문에 아래의 파이프라인은 4개의 명령어를 7 클락이 아닌, 8 클락까지 가게 된다. 

https://en.wikipedia.org/wiki/Instruction_pipelining#/media/File:Pipeline,_4_stage_with_bubble.svg

: `stall`과 `bublle`의 차이가 뭘까? `bublle`은 일반적으로 한 단계 지연을 의미한다. `stall`은 `bubble`이 한 개의 이상될 수 있는 현상을 의미한다.

 

- Operand Forwarding

: `RAW 데이터 해저드` 같은 경우, 다음 명령어는 이전 명령어가 레지스터에 연산 결과를 쓰기전까지 `stall` 해야한다. 예를 들어, 아래와 같이 2가지 연산을 진행한다고 하자. 두 번째 명령어의 `A`가 첫 번째 명령어의 결과에 크게 의존하고 있다.

1: ADD A B C #A=B+C
2: SUB D C A #D=C-A

: 일반적인 파이프라인이라면, 아래와 같은 순서로 진행된다. `SUB` 명령어가 DECODE 이후에 두 번의 버블(stall)을 하게 된다. 두 번째 명령어는, 첫 번째 명령어가 `Write result` 과정이 끝난 시점에 드디어 데이터를 읽을 수 있게 된다.

https://en.wikipedia.org/wiki/Operand_forwarding

 

: `Operand forwarding`은 CPU가 첫 번째 명령어를 실행하고 해당 결과를 레지스터에 쓰지 않고, 다음 명령어의 실행 단계로 직접 값을 전달하는 것이다.

https://en.wikipedia.org/wiki/Operand_forwarding

: `Operand forwarding`은 하드웨어적으로 `Control Unit`이 지원해줘야 사용이 가능하다.

Because it might take a few clock cycles to write and then read from the register file, and it's very common that an instruction needs the value computed by the immediately preceeding instruction, often real pipelined CPUs 
`bypass` the register file, and pass values directly from the execute stage of one instruction into the execute stage of the next:

- 참고 : https://www.cs.uaf.edu/2011/fall/cs441/lecture/09_20_pipelining.html

 

- Re-ordering

: 컴파일러가 소스를 컴파일하는 시점에 `데이터 해저드`를 인식해서 명령어를 재배치하는 방식이다. 먼저, `NOP`을 이용해서 `데이터 해저드`를 해결한다. `Operand forwarding`을 사용하지 않는다고 전제하자. `LW R1,b`, `LW R2,c` 뒤에는 곧 바로, `ADD R3,R1,R2` 명령어를 작성할 수 가 없다. 왜냐면, `RAW 데이터 해저드`가 발생하기 때문이다. `MIPS`에서 `SW` 명령어는 `store`를 의미한다. 이 명령어도 `RWA 데이터 해저드` 때문에, `ADD R3,R1,R2` 명령어가 모두 마무리 된 후에 작성해야 한다.

http://homepage.divms.uiowa.edu/~ghosh/2-9-06.pdf

 

: 그런데, 위에 처럼 `NOP`이 많으면, 파이프라인을 하는 의미가 없다. `레지스터 재할당`을 이용하면, 아래와 같이 바꿀 수 있다. 미사용 레지스터를 이용해서 겹치지 않게 할 경우, 아래와 같이 최적화가 가능하다. 그래도, 여전히 `RAW 데이터 해저드`가 존재한다.

http://homepage.divms.uiowa.edu/~ghosh/2-9-06.pdf

 

: 여기에, `Operand forwarding` 까지 더 해지면, 모든 `NOP`을 없앨 수 있다.

http://homepage.divms.uiowa.edu/~ghosh/2-9-06.pdf

 

- Compare between pipeline and not

: 인텔 8008 마이크로 아키텍처는 프로세서안에 버스가 하나라서 파이프라인 구조를 가질 수 가 없는 구조다. 아래 그림을 보면, 프로세서안에 버스가 하나이기 때문에, 병렬적인 작업 처리가 불가능한 구조다.

https://www.cs.uaf.edu/2011/fall/cs441/lecture/09_20_pipelining.html

 

: 아래는 인텔 386 마이크로아키텍처다. `instruction` 버스와 `ALU` 버스가 나누어져 있는 것을 볼 수 있다. 즉, 명령어 패치와 실행이 동시에 이루어 질 수 있음을 의미한다.

https://www.cs.uaf.edu/2011/fall/cs441/lecture/09_20_pipelining.html

 

- NOP

: 대부분의 제조사는 프로세서가 아무런 동작을 하지 않게 하는 명령어를 제공한다. 즉, 단지 클락만 소비하게 만든다. 그럼, 이걸 왜 쓸까? 많은 이유가 있겠지만, `파이프라인 동기화`를 맞추지 위해 사용한다. 그리고, 모든 명령어에 `동일한 포맷`을 갖게 하기 위해서다.

 

: `동일한 포맷`이 뭘까? 특정 CPU가 5단계 파이프라인을 갖는다는 것은 모든 명령어에 대해 5단계 파이프라인을 적용한다는 말이다. 예외를 두면 하드웨어 차원에서 더 많은 로직들이 필요해지고 이는 비용적인 측면에서도 좋지 못하다. 그래서 아래 그림을 보면, 3단계, 4단계에서 끝날 수 있는 명령어들도 강제적으로 5단계를 적용시킨다. 빈 곳은 모두 `NOP`으로 채운다.

http://homepage.divms.uiowa.edu/~ghosh/6016.100.pdf

 

: `파이프라인 동기화`는 뭘까? 아래와 같이 `RAW(Read-After-Write) 데이터 해저드` 발생할 경우, 두 번째 명령어의 `ID`는 앞에 명령어가 모두 끝날 때, 까지 기다려야 한다.

1: lw $s1, 4($sp)            IF ID EX MEM WB
2: add $s0, $s1, $s2           IF ID EX MEM WB

: 이 때, 첫 번째 명령어를 기다리면서 각 모듈들이 수행하는 동작이 `NOP`이다.

1: lw $s1, 4($sp)        IF ID EX MEM WB
2: add $s0, $s1, $s2       IF nop nop nop ID

: 위와 같이 `NOP`이 많아지면 `파이프라인`을 하는 의미가 없다. 이럴 때, `Operand Forwarding`을 이용하면 CPU가 낭비되는 시간을 줄일 수 있다.