파이프라이닝에 대한 개관

파이프라이닝(pipelining)

파이프라이닝은 여러 명령어가 중첩되어 실행되는 구현기술이다. 오늘날 파이프라이닝은 아주 보편적인 기술. 보통 세탁에 비유된다. 만약 모든 단계가 거의 같은 시간이 걸리며 할 일이 충분히 많다면 파이프라이닝에 의한 속도 향상은 파이프라인의 단계 수와 같다.

명령어 실행을 파이프라이닝한 프로세서에도 같은 원리가 적용된다. MIPS 명령어는 전통적으로 다섯 단계가 걸린다.

• 1. 메모리에서 명령어를 가져온다.
• 2. 명령어를 해독하는 동시에 레지스터를 읽는다. MIPS명령어는 형식이 규칙적이므로 읽기와 해독이 동시에 일어날 수 있다.
• 3. 연산을 수행하거나 주소를 계산한다
• 4. 데이터 메모리에 있는 피연산자에 접근한다.
• 5. 결과 값을 레지스터에 쓴다.

파이프라이닝되지 않은 단일 사이클 실행 대 파이프라인 실행

둘 다 같은 하드웨어를 사용하며 필요시시간은 이 경우 평균시간이 800 ps에서 200 ps로 낮아지면서 4배 속도향상을 볼 수 있다. 세탁소에서는 모든 단계가 같은 시간이 걸린다고 가정하였다. 만약 건조기가 가장 느리다고 한다면 건조 단계가 단계 시간을 결정한다. 컴퓨터 파이프라인의 단계 시간은 단계 시간은 가장 느린 자원에 의해 제한 받는데 ALU 연산이나 메모리 접근이 된다.

위에 설명한 속도 향상에 관한 논의를 식으로 바꿀 수 있다. 단계들이 완벽하게 균형을 이루고 있으면 파이프라인 프로세서 명령어 사이의 시간은 다음과 같다.(이상적이 조건 하에서)

명령어 사이의 시간(파이프라인) = 명령어 사이의 시간(파이프 라이닝 되지 않았을 때) / 파이프 단계 수

그럼 위의 예제는 800/5 = 160가 되어야 하지만 그러나 예제는 완벽하게 균형 잡혀 있지는 않다는 것을 보여준다. 더구나 파이프라이닝은 어느 정도의 오버헤드를 포함하고 있다. 이 오버헤드의 원인이 어디 인지는 금방 알게 될 것이다. 이런 이유로 파이프라인 프로세서에서의 명령어당 시간이 가능한 최솟값보다 커져서 속도 향상은 파이프라인 단계 수보다 작아진다.

파이프라이닝을 위한 명령어 집합 설계

파이프라이닝에 대한 이러한 갇단한 설명으로 MIPS 명령어 집합 설계의 핵심을 파악할 수 있다. MIPS 명령어 집합은 원래 파이프라인 실행을 위해 설계된 것이다.

첫째, 모든 MIPS 명령어는 같은 길이를 갖는다. 이 같은 제한 조건은 첫 번째 파이프라인 단계에서 명령어를 가져오고 그 명령어들을 두 번째 단계에서 해독하는 것을 훨씬 쉽게 해준다.

둘째, MIPS는 몇 가지 안 되는 명령어 형식을 가지고 있다. 모든 명령어에서 근원지 레지스터 필드는 같은 위치에 있다. 이 같은 대칭성은 두 번째 단계에서 하드웨어가 어떤 종류의 명령어가 인출되었는지를 결정하는 동안 레지스터 파일 읽기를 동시에 할 수 있다는 것을 의미한다.

셋째, MIPS에서는 메모리 피연산자가 적재와 저장 명령어에서만 나타낸다. 이 같은 제한은 메모리 주소를 계산하기 위해 실행 단계를 사용하고 다음 단계에서 메모리에 접근할 수 있다는 것을 의미한다.

넷째, 2장에서 살펴본 것과 같이 피연산자는 메모리에 정렬(align)되어 있어야 한다. 따라서 한 데이터 전송 명령어가 두 번의 데이터 매모리 접근을 요구할까 고민할 필요가 없다. 파이프라인 단계 하나에서 프로세서와 메모리가 필요한 데이터를 주고 받을 수 있다.

파이프라인 해저드

다음 명령어가 다음 클럭 사이클에 실행될 수 없는 상황이 있다. 이러한 사건을 해저드(hazard)라 부르는데 세 가지 종류가 있다.

구조적 해저드(structural hazard)

첫 번째 해저드는 구조적 해저드라 불린다. 이는 같은 클럭 사이클에 실행하기를 원하는 명령어의 조합을 하드웨어가 지원할 수 없다는 것을 의미한다. 세탁소에서는 독립된 세탁기와 건조기를 사용하지 않고 세탁기와 건조기가 같이 붙어 있는 기계를 사용하든지 또는 친구가 다른일을 하느라 바빠서 빨래를 치우지 않으면 구조적 해저드가 발생한다.

위에서 이야기한 것처럼 MIPS 명령어 집합은 파이프라이닝하도록 설계되었기 때문에 설계자가 파이프 라인을 설계할 때 구조적 해저드를 피하는 것이 비교적 용이하다. 그러나 메모리가 두 개가 아니고 하나라고 생각해보자. 그림 4.27의 파이프라인에 네 번째 명령어가 추가된다면 같은 클럭 사이클에 첫 번째 명령어는 메모리에서 데이터에 접근하고, 네 번째 명령어는 같은 메모리에서 명령어를 가져오게 된다. 앞의 파이프라인에 메모리가 하나라면 구조적 해저드를 피할 수 없을 것이다.

데이터 해저드(Data hazard)

데이터 해저드는 어떤 단계가 다른 단계가 끝나기를 기다려야 하기 때문에 파이프라인이 지연되어야 하는 경우이다. 명령어를 실행하는데 필요한 데이터가 아직 준비되지 않아서 계획된 명령어가 적절한 클럭 사이클에 실행될 수 없는 사건. 옷을 개다가 한 짝이 없는 양말을 발견. 한 가지 방법은 방으로 달려가서 옷장을 뒤져 나머지 짝을 찾아보는 것. 옷장을 뒤지는 동안 건조가 끝나고 개는 과정을 기다리는 옷들과 세탁 과정을 끝내고 건조 과정을 기다리는 옷들은 기다려야만 한다.

이는 어떤 명령어가 아직 파이프라인에 있는 앞선 명령어에 종속성을 가질 때 일어난다. 예를들어 add 명령어 바로 다음에 add의 합을 사용하는 뺄셈 명령어가 뒤따르는 경우를 가정하자.

add	$s0, $t0, $t1
sub 	$t2, $s0, $t3

별다른 조치가 없다면 데이터 해저드가 파이프라인을 심각하게 지연시킬 수 있다. add 명령어는 다섯 번째까지는 결과 값을 쓰지 않을 텐데 이는 파이프라인 이 세 개의 클럭 사이클을 낭비해야 한다는 것을 의미한다.

컴파일러를 이용해서 이런 데이터 해저드를 모두 제거하려고 할 수도 있지만 결과는 그리 만족스럽지 못할 것이다. 첫 번째 해결책은 데이터 해저드를 해결하려고 노력하기 전에 명령어가 끝날 때까지 기다릴 필요가 없다는 관찰에 기반을 두고 있다. 위와 같은 코드인 경우 ALU가 add 명령어의 합을 만들어 내자마자 이것을 뺄셈의 입력으로 사용할 수 있다. 별도의 하드웨어를 추가하여 정상적으로는 얻을 수 없는 값을 내부 자원으로부터 일찍 받아 오는 것을 전방전달(forwarding) 또는 우회전달(bypassing)이라고 한다. 프로그래머가 볼 수 있는 레지스터나 메모리에 아직 나타나지 않은 데이터를 기다리기보다는 내부 버퍼로부터 가져옴으로써 데이터 해저드를 해결하는 방법.

세탁소 파이프라인과 비슷하게 명령어 파이프라인을 그림으로 표현하기

각 단계를 표시하는 기호는 다음과 같다.

IF : 명령어 인출단계, 명령어 메모리를 뜻하는 상자와 함께 표시한다.
ID : 명령어 해독 / 레지스터 파일 읽기 단계, 레지스터 파일을 나타내는 상자와 함께 표시한다.
EX: 실행단계, ALU를 나타내는 그림과 함깨 표시한다.
MEM : 메모리접근단계, 데이터 메모리를 표시하는 상자와 함께 표시한다.
WB: 쓰기 단계, 쓰기가 행해지고 있는 레지스터 파일을 나타내는 상자와 함께 표시한다. 어둡게 그려진 이유는 그 구성요소가 명령어에 의해 사용되고 있다는 것을 나타낸다.

---

add 명령어의 경우에는 데이터 메모리에 접근하지 않기 때문에 흰생배경으로 되어 있다. 또한 그림의 파란색 연결은 add의 EX 단계 출력을 sb의 EX 단계 입력으로 전방전달하는 경로로 표시한다. 전당전달은 sub의 두번째 단계에서 레지스터 $s0을 읽는 것을 대신한다.

적재 명령어 다음에 나오는 R 형식 명령어가 데이터를 사용하려 시도할 때는 전방전달을 해도 지연이 필요하다. 지연이 없다면 메모리 접근 단계 출력에서 실행 단계 입력으로 가는 경로는 시간적으로 뒤로 가는 것이기 때문에 불가능하다. 이 그림은 사실상 단순화한 것이다. 왜냐하면 sub 명령어가 인출되고 해독될 때까지는 지연이 필요한지 아닌지를 알 수 없기 때문이다.

전방전달이 모든 파이프라인 지연을 방지할 수는 없다. 예를 들면 첫 번째 명령어가 add 명령어가 아니라 $s0의 적재 명령어라 가정하자. 앞선 그림에서 보는 바와 같이 적재-사용-데이터 해저드(load-use-data hazard)의 경우에는 전방전달을 해도 한 단계가 지연되어야 한다. 이 그림은 파이프라인 지연(pipeline stall)(버블이라는 별명으로 불리는 경우도 많다) 이라는 중요한 파이프라인 개념을 보여주고 있다.

예제 : 파이프라인 지연을 피하기 위한 코드의 재정렬

C로 작성된 다음 코드를 생각해보자

a = b + e
c = b + f

다음은 이 코드에 대한 MIPS 코드이다. 모든 변수는 메모리에 있고 $t0를 베이스로 사용해서 접근할 수 있는 위치에 있다고 가정한다.

lw	$t1, 0($t0)
lw	$t2, 4($t4)
add	$t3, $t1, $t2
sw	$t3, 12($t0)
lw	$t4, 8($t0)
add	$t5, $t1, $t4
sw	$t5, 16($t0)

해저드를 찾아내고 파이프라인 지연을 피할 수 있도록 재정렬. 두 add 명령어가 모두 해저드를 가지고 있는데 이는 바로 앞의 명령어인 lw 명령어와 각각 종속성이 있기 때문이다. 전방전달을 하면 첫 번째 lw 명령어에 대한 첫 번째 add 명령어의 종속성과 저장명령어 관련 모든 해저드를 포함하여 가능성 있는 몇 가지 다른 해저드가 제거된다. 세 번째 lw 명령어를 위로 올리면 두 해저드가 모두 없어진다.

lw	$t0, 0($t0)
lw	$t2, 4($t0)
lw	$t4, 8($t0)
add 	$t3, $t1, $t2
sw	$3, 12($t0)
add	$t5, $t1, $t4
sw	$t5, 16($t0)

전방전달 유닛이 파이프라인 프로세서에서, 재정렬된 코드는 원래 코드보다 두 사이클 먼저 완료된다. 전방전달은 언급한 네 가지 통찰외에 MIPS 구조에 대한 또 다른 점을 인식하게 한다. 각각의 MIPS 명령어는 최대 하나의 결과 쓰기를 할 뿐이며 그것도 파이프라인 끝에 한다. 명령어 하나에 전방전달해야 하는 결과가 여러 개 있든가 명령어 실행의 초기에 결과 쓰기를 한다면 전방전달은 더 어려워졌을 것이다.

제어 해저드

제어 해저드(분기 해저드) (branch hazard)라고도 한다. 인출한 명령어가 필요한 명령어가 아니기 때문에 적절한 명령어가 적절한 클럭 사이클에 실행될 수 없는 사건. 명령어 주소의 흐름이 파이프라인이 기대한 것과 다르기 때문에 발생한다. 이에 대한 해결책 중 첫 번째는 지연이다.

• 지연 : 첫 번째 묶음이 건조될 때까지 그냥 순차적으로 작업하되 올바른 비율이 될 때까지 반복한다.
  이 같은 보수적인 방법이 동작하는 것은 확실하지만 느리다.

다음 클럭사이클에서 분기 명령어를 이을 명령어를 가져오기 시작해야 한다. 그러나 파이프라인은 다음 명령어가 어느 것이 되어야 하는지 알 수 없다. 왜냐하면 이제 방금 메모리에서 분기 명령어를 가져온 후 지연시켜서 파이프라인이 분기의 결과를 판단하고 어느 주소에서 다음 명령어를 가져올지 알게 될 때까지 기다리게 하는 것이다. 세탁소에서처럼 한다면 한 가지 가능한 해결책은 분기 명령어를 가져온 직후 지연시켜서, 파이프라인이 분기의 결과를 판단하고 어느 주소에서 다음 명령어를 가져올지 알게 될 때까지 기다리게 하는 것이다.

제어 해저드에 대한 래결책으로 매 조건부 분기 명령어마다 지연시키는 파이프라인: 이 예는 분기가 일어난 것을 가정하고 있다. 분기 명령어의 목적지에 있는 명령어는 or 명령어이다. 분기 명령어 후에는 한 단계가 지연된다.

파이프라인이 긴 경우에는 흔히 그렇듯이 분기를 두번째 단계에서 다 해결하지 못한다면, 분기 명령어마다 지연시키는 것은 훨씬 더 큰 속도 저하를 초래할 것이다. 이 방법은 지불해야할 대가가 너무 커서 대부분의 컴퓨터에서 사용하기 힘들기 때문에 제어 해저드에 대한 두 번째 해결책이 나오게 되었다.

• 예측 : 유니폼 세탁에 적절한 배합을 이미 어느 정도 알고 있다면, 첫 번째 묶음이 건조될 때까지 기다리는 동안 배합을 예측해서 두 번째 묶음을 세탁한다

이 방법은 예측이 맞으면 파이프라인의 성능을 떨어뜨리지 않는다. 그러나 예측이 틀렸다면 다시 세탁해야 한다.

대부분의 컴퓨터가 분기 명령어를 다루기 위해서 예측을 사용한다. 간단한 방법은 분기가 항상 실패한다고 예측하는 것이다. 예측이 옳으면 파이프라인은 최고 속도로 진행된다. 실제로 분기가 일어날 때만 파이프라인이 지연된다.

제어 해저드에 대한 해결책으로 분기가 일어나지 않는다고 예측하기. 위 그림은 분기가 일어나지 않았을 때 파이프라인을 보여주고 있고 아래 그림은 분기가 일어날 때의 그림을 보여주고 있다. 본 바와 같이 이 같은 방식으로 거품을 삽입하는 것이 실제 일어나는 일을 단순화해서 보여주는 것이다. 적어도 분기 명령어 바로 다음 첫 클럭 사이클의 상황을 잘 나타낸다.

분기 예측(branch prediction)에 대한 좀 더 정교한 버전은 어떤 경우는 분기한다(taken)고 예측하고 어떤 경우는 분기하지 않는다(untaken) 예측하는 것. 프로그래밍의 경우 순환문의 끝에는 순환문의 꼭대기로 점프하라는 분기 명령어가 있다. 이 명령어들은 분기가 일어날 가능성이 높고 분기 방향이 후방이므로 이에 착안하여 현재 위치보다 작은 주소로 점프하는 분기 명령어는 분기가 항상 일어난다고 예측할 수 있다.

이러한 분기 예측 방법들은 보편적 행동에 의존하며 특정 분기 명령어의 개별성은 고려하지 않는다.

동적 하드웨어 예측기(dynamic hardware predictor)는 이와 정반대로 개별 분기 명령어의 행동에 의존하는 예측을 마녀 프로그램이 진행되는 도중에 예측을 바꿀 수 있다. (유니폼이 과거에 얼마나 더러웠는지를 찾아봐서 적절한 배합을 추측하고 예측의 성공여부에 따라 다음 예측을 조정한다)

분기 동적 예측에 대한 보편적인 방법 중 하나는 각 분기가 일어났는지 안 일어났는지를 기록하고 과거 이력을 보면서 미래를 예측하는 것이다. 예측이 어긋났을 때는 잘못 예측한 분기 명령어 뒤에 나오는 명령어들을 무효화하고 올바른 분기 주소로부터 파이프라인을 다시 시작한다.

제어헤저드에 대한 다른 모든 해결책에서와 마찬가지로 분기예측에서도 긴 파이프라인은 문제를 악화시키기 때문에 틀린 예측 비용을 증가시킨다.