Search
Duplicate

컴퓨터 구조 및 설계/ 프로세서

서론

1장에서 컴퓨터 성능은 세 가지 주요 요인, 즉 명령어 개수, 클럭 사이클 시간, 명령어 당 클럭 사이클 수(CPI)에 의해 결정된다는 것을 알았다.
2장에서 살펴본 바와 같이 컴파일러와 명령어 집합 구조가 프로그램에 필요한 명령어 개수를 결정한다. 그러나 클럭 사이클 시간과 명령어당 클럭 사이클 수는 프로세서의 구현 방법에 따라 결정된다.
이 장에서는 MIPS 명령어 집합을 두 가지 다른 방법으로 구현하여 데이터패스와 제어 유닛을 완성시키려 한다.
이 장은 프로세서를 구현하는데 사용되는 원리와 기법들에 대한 설명을 포함하고 있다. 이 절에서는 매우 추상적이고 단순한 개괄을 서술하며, 다음 절에서는 데이터패스를 만들고 MIPS 같은 명령어 집합 구현에 충분한 프로세서의 간단한 버전을 구성한다.
지 장은 많은 부분을 조금 더 현실적인 파이프라인 MIPS 구현에 할애하고 마지막으로 x86과 같은 좀 더 복잡한 명령어 집합을 구현하는데 필요한 개념들을 설명한다.

기본적인 MIPS 구현

핵심적인 MIPS 명령어 집합의 부분집합을 구현할 것인데, 그 부분집합은 다음과 같다.
메모리 참조 명령어인 워드 적재(lw)와 워드 저장(sw)
산술/논리 명령어인 add, sub, AND, OR, slt
같을 시 분기 명령어인 beq와 점프 명령어 j
이 부분집합은 정수형 명령어를 모두 포함하지는 않으며 (예컨대 자리이동, 곱하기, 나누기가 빠져 있음) 부동소수점 명령어는 하나도 포함하지 않는다. 그렇지만 데이터패스와 제어 유닛을 설계하는데 사용되는 핵심 원리는 설명될 것이다. 나머지 명령어에 대한 구현 또한 거의 비슷하다.
이 장에서 MIPS 명령어의 일부를 구현하는데 사용되는 대부분의 개념은 고성능 컴퓨터에서부터 범용 마이크로프로세서 및 임베디드 프로세서에 이르기까지 다양한 종류의 컴퓨터를 만드는데 쓰인다.

구현에 대한 개요

2장에서 정수형 산술/논리 명령어, 메모리 참조 명령어, 분기 명령어를 포함하는 핵심적인 MIPS 명령어를 살펴보았다. 이러한 명령어 구현에 필요한 일의 상당히 많은 부분은 명령어 종류에 상관없이 동일하다. 어떤 명령어든지 처음 두 단계는 다음과 같이 모두 동일하다.
1.
프로그램 카운터(PC)를 프로그램이 저장되어 있는 메모리에 보내어 메모리로부터 명령어를 가져온다.
2.
읽을 레지스터를 선택하는 명령어 필드를 사용하여 하나 또는 두 개의 레지스터를 읽는다. 워드 적재 명령어는 레지스터 하나만 읽으면 되지만 대부분의 다른 명령어는 레지스터 두 개를 읽는다.
이 두 단계 이후 명령어 실행을 끝내기 위해 필요한 행동들은 명령어 종류에 따라 달라진다. 다행히도 세 가지 명령어 종류(메모리 참조 명령어, 산술/논리 명령어, 분기 명령어) 각각에 대해서는 명령어가 무엇인지에 상관없이 필요한 행동들이 대부분 같다.
MIPS 명령어 집합의 단순함과 규칙적인 특성이 많은 종류의 명령어 실행을 비슷하게 만들어 줌으로써 구현을 단순화 한다.
예컨대 점프 명령어를 제외한 모든 명령어 종류가 레지스터를 읽은 후에는 ALU를 사용한다. 메모리 참조 명령어는 주소 계산을 위해 ALU를 사용하고, 산술/논리 명령어는 연산을 수행하기 위해 ALU를 사용하고, 분기 명령어는 비교하기 위해 사용한다.
ALU를 사용한 후에는 명령어 실행을 끝내는데 필요한 행동들이 명령어 종류에 따라 서로 다르다.
메모리 참조 명령어는 메모리에 접근할 것이다. 저장 명령어는 데이터를 기록하기 위해 접근하고, 적재 명령어는 데이터를 읽기 위하여 접근한다.
산술/논리 명령어와 적재 명령어는 ALU와 메모리에서 온 데이터를 레지스터에 써야 한다.
마지막으로 분기 명령어의 경우에는 비교 결과에 따라 다음 명령어의 주소를 바꿀 수도 있고 PC 값을 4만큼 증가시켜 다음 명령어의 주소를 갖게 할 수도 있다.
그림 4.1은 MIPS 구현을 상위 수준에서 본 그림으로서 여러 기능 유닛과 그들 사이의 연결에 초점을 맞추고 있다. 프로세서 내의 데이터 흐름을 거의 다 보여주고 있지만 명령어 실행에 중요한 두 가지 측면이 빠져 있다.
첫째로 그림 4.1에는 서로 다른 근원지에서 나온 데이터가 같은 유닛으로 가는 곳이 몇 군데 있다.
예컨대 PC에 들어갈 값은 두 덧셈기 중 하나에서 나오고 레지스터 파일에 쓰일 데이터는 ALU나 데이터 메모리에서 나오며, ALU의 두 번째 입력은 레지스터나 명령어의 수치 필드에서 나온다.
실제로는 이들 데이터 선을 단순히 그냥 연결할 수가 없다. 그러므로 다수의 근원지 중에서 하나를 선택하여 그것만을 목적지로 보내는 구성 요소를 추가해야 한다. 이 같은 선택은 일반적으로 멀티플렉서(multiplexor)라 불리는 소자를 사용하여 이루어진다.
사실 이 구성 요소는 데이터 선택기(data selector)라는 것이 더 적절한 이름이다. 멀티플렉서는 제어선의 값에 따라 여러 개 입력 중에서 하나를 선택한다. 제어선은 주로 실행 중인 명령어에서 나오는 정보에 따라 설정된다.
둘째로 어떤 유닛들은 명령어 종류에 따라 다르게 제어되어야 하는데, 이 부분이 빠져 있다.
예컨대 데이터 메모리는 적재 명령어일 때는 읽기, 저장 명령어일 때는 쓰기를 해야 한다.
레지스터 파일은 적재 명령어나 산술/논리 연산 명령어일 때만 쓰기를 한다. 물론 ALU는 여러 가지 연산 중 하나를 수행해야 한다. 이 동작들도 멀티플렉서처럼 명령어의 여러 필드 값에 따라 정해지는 제어선에 의해 통제된다.
그림 4.2는 그림 4.1의 데이터패스에 주요 기능 유닛을 위한 제어선과 필요한 멀티플렉서 세 개를 추가한 그림이다.
제어 유닛(control unit)은 기능 유닛들과 두 멀티 플렉서의 제어선 값을 결정하는데 사용하는 것으로, 명령어를 입력으로 써야 한다.
세 번째 멀티플렉서는 PC+4와 분기 목적지 주소 중 어느 것을 PC에 써야 할지 결정하는 것인데, ALU의 Zero 출력으로 제어된다. 이 출력은 beq 명령어에서 비교할 때에 사용된다.
MIPS 명령어 집합의 규칙성과 단순성은 간단한 디코딩 과정만으로 제어선의 값을 결정할 수 있게 하였다.

논리 설계 관례

컴퓨터 설계에 대하여 논의하기 위해서는 컴퓨터를 구현하고 있는 논리 회로가 어떻게 동작하고 또 컴퓨터가 어떻게 클러킹 되는지를 결정해야 한다. 이 절에서는 이 장에서 많이 사용하게 될 디지털 논리의 핵심 아이디어 몇 가지를 되새겨 볼 것이다.
MIPS 구현에 쓰이는 데이터패스 요소는 두 가지 종류의 논리 소자들로 구성된다. 데이터 값에만 동작하는 소자와 상태를 포함하는 소자가 그것이다.
데이터 값에만 동작하는 소자는 모두 조합소자(combinational element)인데, 그 의미는 그들의 출력이 현재의 입력에만 의존한다는 것이다. 조합소자는 같은 입력이 주어지면 항상 같은 출력을 낸다.
4.1절에서 보았던 ALU가 조합소자이다. ALU는 내부 기억소자가 없기 때문에 주어진 입력에 대하여 항상 같은 출력을 낸다.
설계에 쓰이는 또 다른 종류의 소자들은 조합소자가 아니고 대신 상태(state)를 갖는다. 소자에 내부 기억장소가 있으면 상태를 갖게 된다. 이러한 소자들을 상태소자(state element)라고 부른다.
그 이유는 컴퓨터의 플러그를 뺐다 해도 플러그를 뺴기 전에 소자가 가지고 있던 값들로 상태소자를 적재하면 다시 시작시킬 수 있기 때문이다. 더구나 상태소자들을 저장했다가 다시 복원하면 컴퓨터가 꺼지지 않았던 것과 마찬가지다.
따라서 상태 소자들은 컴퓨터를 완전히 특징 짓는다. 그림 4.1의 명령어 메모리, 데이터 메모리 및 레지스터가 상태소자의 예이다.
상태소자는 적어도 2개의 입력과 1개의 출력을 갖는다. 꼭 있어야 되는 입력은 기록할 데이터와 클럭이다. 클럭 입력은 데이터 값이 소자에 기록되는 시점을 결정한다.
상태소자의 출력은 이전 클럭 사이클에 기록된 값이다. 논리적으로 가장 간단한 상태소자 중 하나는 D형 플립플롭인데 이 D형 플립플롭에는 두 개의 입력(데이터 값과 클럭)과 하나의 출력이 있다.
MIPS 구현에는 플립플롭 말고도 두 가지 상태소자가 더 사용된다. 메모리와 레지스터가 그것으로 그림 4.1에서도 볼 수 있다.
상태소자에 언제 쓸 것인가는 클럭이 결정하지만 상태소자의 값을 읽는 것은 언제라도 가능하다.
상태를 포함하는 논리소자들을 순차회로(sequnetial circuit)라 부르는데 이는 이들의 출력이 입력 뿐만 아니라 내부 상태에도 의존하기 때문이다. 예컨대 레지스터 파일의 출력은 입력되는 레지스터 번호와 전에 레지스터에 기록된 값 모두에 영향을 받는다.

클러킹 방법론

클러킹 방법론(clocking methodology)은 신호를 언제 읽을 수 있고 언제 쓸 수 있는지를 정의한다.
읽기와 쓰기의 타이밍을 명시하는 것은 중요하다. 신호를 읽고 있는데 동시에 누군가가 새로운 값을 쓴다면 읽은 값이 옛 값일 수도 있고 새로 쓴 값일 수도 있고 심지어는 두 값이 뒤섞인 것이 될 수도 있기 때문이다.
컴퓨터 설계는 이런 예측 불가능성을 용납하지 못한다. 클러킹 방법론은 예측 가능성을 보장하기 위해 고안 되었다.
단순화를 위해 에지 구동 클러킹(edge-triggered clocking) 방법론을 가정한다. 에지 구동 클러킹 방법론은 순차논리소자에 저장된 값은 클럭 에지에서만 바꿀 수 있다는 것을 의미한다.
클럭 에지란 그림 4.3에서 보듯이 낮은 값에서 높은 값 혹은 그 반대로의 빠른 변이를 말한다.
상태소자들만이 데이터 값을 저장할 수 있기 때문에 모든 조합회로는 상태소자에서 입력을 받고 상태소자로 출력을 내보낸다. 입력은 이전 클럭 사이클에서 쓴 값이고 출력은 다음 클럭 사이클에서 사용할 수 있는 값이다.
그림 4.3은 일단의 조합회로를 둘러싸고 있는 두 개의 상태소자를 보여주고 있다.
이 회로는 하나의 클럭 사이클에 동작한다. 즉 모든 신호가 상태소자 1에서 나와서 조합회로를 거쳐 상태소자 2까지 전달되는데 하나의 클럭 사이클이 걸린다.
신호들이 상태소자 2에 도착하는데 필요한 시간이 클럭 사이클 길이를 정의하게 된다.
매 클럭 에지마다 상태소자에 쓰기가 행해지는 경우는 앞으로 쓰기 제어신호(control signal)를 표시하지 않겠다. 반대로 상태소자가 매 클럭마다 갱신되는 것이 아니라면 쓰기 제어신호가 분명하게 표시되어야 한다.
클럭 신호와 쓰기 제어신호는 상태소자의 입력이며, 쓰기 제어신호가 인가되고 활성화 클럭 에지일 때만 상태소자가 변하게 된다.
인가된(asserted)이라는 용어는 논리적으로 높은 신호를 표시하며, 인가(assert)라는 용어는 신호를 높은 값으로 만든다는 뜻이다.
논리적으로 낮은 값을 표시하기 위해서는 비인가(deassert) 또는 비인가된(deasseted)이라는 용어를 사용해야 한다.
인가 혹은 비인가라는 용어를 사용하는 이유는 하드웨어를 구현할 때 때때로 1이 논리적으로 높은 값을 나타내기도 하고 때때로 1이 논맂거으로 낮은 값을 나타내기도 하기 때문이다.
그림 4.4에서 보는 바와 같이 에지 구동 방법론은 레지스터 내용을 읽고 그 값을 조합회로로 보내고 같은 레지스터에 쓰는 작업 모두가 한 클럭 사이클에 일어나는 것을 허용한다.
쓰기가 상향 클럭 에지에서 일어난다고 가정하든지 하향 클럭 에지에서 일어난다고 하정하든지 상관없다.
왜냐하면 조합회로에 대한 입력은 선택된 클럭 에지에서만 변하기 때문이다. 이 책에서는 상향 클럭 에지를 사용한다.
에지 구동 타이밍 방법론에서는 한 클럭 사이클 내에는 피드백(feedback)이 되지 않는다. 그러므로 그림 4.4의 회로는 제대로 동작한다.
32비트 MIPS가 취급하는 거의 모든 데이터가 32비트 폭을 갖기 때문에 이 프로세서의 상태소자와 논리소자의 입력과 출력 폭은 거의 다 32비트이다. 어떤 입력이나 출력의 폭이 32비트가 아니면 반드시 이를 명시할 것이다.
그림에서 버스(bus)는 굵은 선으로 표시할 것이다. 버스는 폭이 2비트 이상인 신호들이다.
어떤 때는 여러 버스들을 합쳐서 더 넓은 버스를 만들기도 한다. 예컨대 16비트 버스 두 개를 합하여 32비트 버스로 만들 수 있다.
이런 경우에는 버스선에 레이블을 붙여서 더 넓은 버스를 만들기 위해 버스들을 합쳤다는 것을 명확하게 나타낸다.
소자 간의 데이터 흐름 방향을 명확히 하기 위해 화살표를 붙이기도 한다.
끝으로 데이터를 운반하는 신호와 구별하기 위해 제어신호는 파란색으로 나타낸다.

데이터패스 만들기

데이터패스 설계를 시작하는 적당한 방법은 MIPS 명령어 종류 각각을 실행하는데 필요한 주요 구성 요소들을 살펴보는 것이다. 각 명령어들이 어떤 데이터패스 구성요소(datapath element)들을 필요로 하는지 살펴보는 것으로 시작하자.
그 뒤 추상화 단계를 거쳐 깊이 들어가도록 하겠다. 데이터패스 구성 요소를 나타낼 때는 제어신호도 함께 나타내 보이겠다. 추상화를 사용하여 기초부터 설명을 시작하도록 한다.
그림 4.5a는 우리가 필요로 하는 첫 번째 구성 요소를 보여주고 있다. 프로그램의 명령어를 저장하고 주소가 주어지면 해당 명령어를 보내 주는 메모리 유닛이다.
그림 4.5b는 프로그램 카운터(PC: program counter)를 보여준다. 2장에서 본 바에 의하면 PC는 현재 명령어의 주소를 가지고 있는 레지스터이다.
끝으로 PC를 다음 명령어 주소로 증가시키는 덧셈기가 필요하다. 이 덧셈기는 조합회로이고 ALU를 가지고 쉽게 만들 수 있다. ALU가 항상 덧셈을 하도록 제어선을 연결하기만 하면 된다.
이런 ALU는 영구히 덧셈기로 만들어져서 다른 ALU 기능은 수행할 수 없으므로 그림 4.5에서처럼 Add라는 레이블을 붙이도록 한다.
어느 명령어든지 실행하기 위해서는 메모리에서 명령어를 가져오는 것으로 시작해야 한다.
다음 명령어 실행을 준비하기 위해서 프로그램 카운터가 다음 명령어를 가리키도록 4만큼 증가시켜야 한다.
그림 4.5의 세 가지 구성 요소를 어떻게 합쳐서 명령어를 인출하고 PC를 증가시켜 다음 명령어의 주소를 구하는 데이터패스를 만드는지를 그림 4.6에 보였다.
이제 R 형식 명령어들을 생각해 보자. (그림 2.18 참조) 모든 R 형식 명령어들은 두 개의 레지스터를 읽고 레지스터 내용에 ALU 연산을 수행하며 그 결과를 레지스터에 쓴다.
이러한 명령어들을 R 형식 명령어 또는 산술/논리 명령어라 부른다. 왜냐면 이 명령어들은 산술연산이나 논리연산을 행하기 때문이다. 이 명령어 종류는 2장에서 소개된 add, sub, AND, OR, slt 명령어를 포함하고 있다.
이러한 명령어의 전형적인 예는 add $t1, $t2, $t3와 같다는 것을 상기하라. 이 명령어는 $t2와 $t3를 읽고 $t1에 쓴다.
프로세서의 범용 레지스터 32개는 레지스터 파일(register file)이라고 하는 구조 속에 들어 있다. 레지스터 파일은 레지스터들을 모아 놓은 것인데, 파일 내의 레지스터의 번호를 지정하면 어느 레지스터라도 읽고 쓸 수 있다.
레지스터 파일은 컴퓨터의 레지스터 상태를 갖고 있다. 레지스터에서 읽어 들인 갓ㅂ을 연산하려면 ALU가 필요하다.
R 형식 명령어들은 레지스터 피연산자 세 개를 가지고 있기 때문에, 매 명령어마다 레지스터 파일에서 두 데이터 워드를 읽고 데이터 워드 하나를 써야 한다.
레지스터에서 데이터 워드를 읽기 위해서는 레지스터의 입력과 출력이 하나씩 필요하다. 읽을 레지스터 번호를 지정하는 입력과 레지스터에서 읽은 값을 내보내는 출력이다.
데이터 워드를 쓰기 위해서는 입력이 두 개 필요하다. 한 입력은 쓸 레지스터 번호를 지정하고 다른 입력은 레지스터에 쓸 데이터 값을 제공한다.
레지스터 파일은 Read register 입력에 실리는 번호에 해당하는 레지스터의 내용을 항상 출력한다. 그러나 쓰기는 쓰기 제어신호에 의해 제어되므로 클럭 에지에서 쓰기가 일어나려면 이 제어 신호가 인가 되어야 한다.
따라서 전체적으로 네 개의 입력(레지스터 번호용 세 개, 데이터용 한 개)과 두 개의 출력(모두 데이터용)이 필요하다.
그림 4.7a에 이를 보였다. 레지스터 번호 입력은 32개의 레지스터 중 하나를 지정해야 하므로 5비트 크기인 반면(32=2), 데이터 입력과 데이터 출력 버스는 모두 32비트 폭을 가진다.
5
그림 4.7b는 ALU를 보여주고 있다. ALU는 32비트 입력 두 개를 받아서 32비트 결과와 결과가 0인지 아닌지를 나타내는 1비트 신호를 만든다.
ALU 제어신호가 어떻게 정해져야 하는지 알 필요가 있을 경우에 ALU 제어 유닛을 간략히 알아보도록 하겠다.
다음에는 MIPS의 워드 적재 명령어와 워드 저장 명령어를 생각해 보자.
이 두 가지 명령어는 일반적으로 lw $t1, offset_value($2) 또는 sw $t1, offset_value($t2)와 같은 형식을 갖는다. 이 명령어들은 베이스 레지스터(여기서는 $t2)와 명령어에 포함되어 있는 16비트 부호있는 변위 필드를 더하여 메모리 주소를 계산한다.
저장 명령어이면 저장할 값을 레지스터 파일에서 읽어와야 하는데 이 값은 $t1에 있다. 적재 명령어이면 메모리로부터 읽어 들인 값을 지정된 레지스터($t1)에 써야 한다.
따라서 그림 4.7의 레지스터 파일과 ALU가 둘 다 필요하다.
그 외에도 명령어의 16비트 변위 필드 값을 32비트 부호있는 값으로 부호확장(sign-extend) 하기 위한 유닛이 필요하며 또 읽고 쓸 데이터 메모리가 필요하다.
데이터 메모리는 저장 명령어일 때만 쓰기를 해야 한다. 따라서 데이터 메모리는 읽기와 쓰기 제어신호, 주소 입력, 메모리에 쓸 데이터 타입이 필요하다.
그림 4.8은 부호확장 유닛과 데이터 메모리를 보여주고 있다.
beq 명령어는 비교할 레지스터 두 개와 16비트 변위의 세 피연산자를 갖는다. 변위는 분기 명령어 주소에 대한 상대적인 분기 목적지(branch target address)를 계산하는데 사용된다. 명령어 형태는 beq $t1, $t2, offset이다.
이 명령어를 구현하기 위해서는 PC 값에다 명령어 변위 필드의 부호확장 값을 더해서 분기 목적지 주소를 계산해야 한다. 분기 명령어의 정의에는 우리가 주의를 기울여야 하는 두 가지 점이 있다.
명령어 집합 구조는 분기 주소 계산의 베이스 주소가 분기 명령어 다음 명령어의 주소라고 서술하고 있다. 명령어 인출 데이터패스에서 PC+4(다음 명령어의 주소)를 계산하기 때문에 이 값을 분기 목적지 주소 계산의 베이스로 사용하는 것이 편하다.
구조는 또한 변위 필드는 2비트만큼 왼쪽 자리이동하여 워드 변위가 된다고 서술한다. 이렇게 함으로써 변위 필드의 유효 범위를 4배만큼 증가시킨다.
두 번째 문제를 다루기 위해서는 변위 필드를 2비트 이동시켜야 한다.
분기 목적지 주소를 계산하는 것 외에 실행할 다음 명령어가 뒤에 있는 명령어가 될지 아니면 분기 목적지 주소에 있는 명령어가 될지를 판단해야 한다.
조건이 사실일 때(즉 피연산자 값이 같을 때) 분기 목적지 주소가 새로운 PC 값이 되며 분기가 일어났다(branch taken)라고 말한다.
피연산자 값이 같지 않으면 증가된 PC 값이 새 PC 값이 된다(다른 보통 명령어와 같이) 이 경우에는 분기가 일어나지 않았다(branch not taken)고 말한다.
따라서 분기 데이터패스는 분기 목적지 주소를 계산하고 레지스터 내용을 비교하는 두 가지 일을 해야 한다. (분기는 데이터패스의 명령어 인출 부분에도 영향을 미치는데 이 문제는 조금 뒤에 설명하겠다)
분기를 다루는 데이터패스 부분을 그림 4.9에 보였다. 분기 목적지 주소를 계산하기 위해서 분기 데이터패스는 부호확장 유닛과 덧셈기를 포함한다.
비교를 수행하기 위해서는 레지스터 피연산자가 두 개 필요하고 이들을 읽기 위해서 그림 4.7a와 같은 레지스터 파일이 필요하다(레지스터 파일에 쓸 필요는 없지만)
이 외에도 비교 연산은 ALU를 사용한다. ALU는 결과가 0인지를 나타내는 출력 신호를 제공하기 때문에 두 레지스터 피연산자를 제어신호와 함께 ALU에 보내 뺄셈을 하게 된다.
ALU의 Zero 신호가 인가되면 두 개의 값이 같다는 것을 알 수 있다. Zero 출력은 연산 결과가 0인지를 항상 표시하지만 우리는 분기 명령어의 같은지 여부 테스트에서만 사용하도록 한다.
데이터패스에서 사용하려면 ALU 제어신호를 정확히 어떻게 연결해야 하는지는 나중에 보여주겠다.
점프(jump) 명령어는 명령어의 하위 26비트를 2비트만큼 왼쪽으로 자리이동한 값으로 PC의 하위 28비트를 대체한다. 이 자리이동은 점프 변위 뒤 00을 덧붙이면 된다.

단일 데이터패스 만들기

이제까지 각각의 명령어 종류에 필요한 데이터패스 구성 요소에 대하여 알아보았다. 이제 이 데이터패스 구성 요소들을 하나로 묶고 여기에 제어를 첨가함으로써 구현을 완성하고자 한다.
가장 간단한 데이터패스는 모든 명령어를 한 클럭 사이클에 실행하도록 시도하는 것이다. 이것은 어느 데이터패스 자원도 명령어당 두 번 이상 사용될 수 없음을 의미한다.
따라서 두 번 이상 사용할 필요가 있는 구성 요소는 필요한 만큼 여러 개를 두어야 한다. 그러므로 데이터 메모리와는 별도로 명령어 메모리가 필요한 것이다.
몇몇 기능 유닛은 복제할 필요가 있지만, 많은 구성 요소들은 서로 다른 명령어 흐름들이 공유하여 사용할 수 있다.
두 개의 다른 명령어 종류들이 데이터패스 구성 요소를 공유하기 위해서는 그 구성 요소의 입력에 여러 개의 연결을 허용해야 하며, 멀티플렉서와 제어신호를 사용해서 그 입력들 중 하나를 선택해야 한다.

예제) 데이터패스 구축

산술/논리(R 형식) 명령어 데이터패스와 메모리 명령어 데이터패스는 매우 비슷하나 다음과 같은 점이 다르다.
산술/논리 연산 명령어는 ALU를 사용하는데, 입력은 두 레지스터에서부터 온다. 메모리 명령어 역시 주소를 계산하기 위하여 ALU를 사용하지만, ALU의 두 번째 입력은 명령어의 16비트 변위 필드를 부호확장한 값이다.
목적지 레지스터에 저장되는 값은 ALU에서 (R 형식 명령어인 경우) 오거나 메모리에서(적재 명령어의 경우) 온다.
메모리 참조 명령어와 산술/논리 연산 명령어를 실행하는 데이터패스를 만들되 파일 하나와 ALU 하나를 사용하여 두 종류의 명령어를 처리하도록 하라. 단 멀티플렉서는 필요한 경우 얼마든지 사용해도 괜찮다.
레지스터 파일 하나와 ALU 하나만을 사용하는 데이터패스를 만들기 위해서는 두 번째 ALU 입력에 두 종류의 다른 근원지를, 그리고 레지스터에 저장할 데이터 입력에도 두 개의 다른 근원지를 연결할 수 있어야 한다. 따라서 ALU 입력에 멀티플렉서 하나 그리고 레지스터 파일의 데이터 입력에 멀티플렉서 하나를 설치해야 한다. 그림 4.10에 합쳐진 데이터 패스를 보였다.
이제 명령어 인출을 위한 데이터패스(그림 4.6)와 R 형식 명령어와 메모리 명령어를 위한 데이터패스(그림 4.10), 분기 명령어를 위한 데이터패스(그림 4.9)를 하나로 합쳐서 MIPS 구조를 위한 단순화된 데이터패스를 만들 수 있다.
그림 4.11은 이렇게 분리된 조각들을 합쳐서 만든 데이터패스를 보여 주고 있다. 분기 명령어는 주 ALU를 레지스터 피연산자 비교에 사용하므로 분기 목적지 주소 계산을 위해서는 그림 4.9의 덧셈기가 있어야 한다.
또한 PC에 들어갈 값으로 순차적인 다음 명령어 주소(PC+4)와 분기 목적지 주소 중 하나를 선택하기 위해 또 다른 멀티플렉서가 필요하다.
이와 같은 단순화한 데이터패스를 완성하였으니 이제 제어 유닛을 덧붙여야 할 때다. 제어 유닛은 필요한 입력들을 받아들여 각 상태소자의 쓰기 신호, 각 멀티플렉서의 선택 신호, 그리고 ALU 제어신호를 만들어내야 한다. ALU 제어 유닛은 여러 가지 면에서 다르기 때문에 이것을 먼저 설계하고 나머지는 그 다음에 하는게 바람직 하다.

단순한 구현

이 절에서는 앞의 MIPS 부분집합을 가장 간단히 구현한다면 어떤 형태가 될지 알아본다. 4.3절의 데이터패스에 단순한 제어기능을 추가하여 단순한 구현을 만들고자 한다.
이 단순한 구현은 워드 적재(lw), 워드 저장(sw), 같을 시 분기(beq), 산술/논리 연산 명령어인 add, sub, AND, OR, set on less than 명령어를 포함한다. 차후에 점프 명령어(j)를 포함하도록 설계를 확장할 예정이다.

ALU 제어

MIPS ALU는 제어 입력 4개를 사용하는 다음 6개 조합을 정의하고 있다.
Show All
Search
ALU control lines
Function
1
10
add
Open
110
subtract
Open
111
set on less than
Open
1100
NOR
Open
ALU는 명령어 종류에 따라 첫 5가지 기능 중 하나를 수행하게 된다. (NOR는 우리가 구현하는 부분집합에서는 보이지 않는 MIPS 명령어 집합의 다른 부분에서 필요하다)
워드 적재, 워드 저장 명령어인 경우에는 메모리 주소를 계산하기 위한 덧셈용으로 ALU를 사용한다.
R 형식 명령어의 경우에는 명령어 하위 6비트의 기능 필드 값에 따라 5가지 연산(AND, OR, subtract, add, set on less than) 중 하나를 수행하게 된다.
같을 시 분기 명령어의 경우에 ALU는 뺄셈을 수행하게 된다.
명령어 기능 필드와 2비트 제어 필드(ALUOp라 불림)를 입력으로 갖는 조그만 제어 유닛을 만들어서 4비트 ALU 제어 입력을 발생시킬 수 있다.
ALUOp가 표시해야 될 연산은 적재와 저장의 경우에는 덧셈(00), beq의 경우에는 뺄셈(01), 산술/논리 연ㅅ나의 경우에는 기능 필드에서 나타내는 연산(10)이 된다.
ALU 제어 유닛의 출력은 4비트 신호인데 이 4비트 신호는 앞서 말한 4비트 조합 중 하나를 만들어 냄으로써 ALU를 직접 제어한다.
그림 4.12는 2비트 ALUOp 제어와 6비트 기능 코드를 사용하여 어떻게 ALU 제어 입력을 만드는지 보여준다. 이 장 뒷부분에서는 ALLOp 비트가 주 제어 유닛에서 어떻게 만들어지는지를 보여주겠다.
주 제어 유닛이 ALUOp 비트를 생성하고 ALU 제어 유닛은 이것을 입력으로 받아서 ALU를 제어하는 실제 신호를 만들어 내는 이런 다단계 디코딩은 많이 쓰이는 구현 기법이다.
다단계 제어를 사용하면 주 제어 유닛의 크기를 줄일 수 있다. 또한 여러 개의 작은 유닛을 사용하는 것은 제어 유닛 속도를 증가시킬 수도 있다.
제어 유닛의 속도가 클럭 사이클 시간에 큰 영향을 미치는 경우가 많으므로 이러한 최적화는 중요하다.
2비트 ALUOp 필드와 6비트 기능 필드를 4비트의 ALU 연산 제어 비트로 사상 시키는 방법에는 여러 가지가 있다.
기능 필드가 가질 수 있는 값 64개 중에서 겨우 몇 개만이 사용되고, 그것도 ALUOp 비트가 이진수 값 10일 때만 사용되기 때문에, 가능한 값들 중에서 일부만을 사용하여 ALU 제어 비트를 만들어내는 조그만 논리회로를 사용할 수 있다.
이 논리회로를 설계하는 단계로서 기능 코드 필드의 관심 있는 값들과 ALUOp 비트에 대한 진리표를 만드는 것이 도움이 된다. 이것을 그림 4.13에 보였다.
이 진리표(truth table)는 이 같은 두 가지 입력 필드 값에 따라 4비트 ALU 제어 값이 어떻게 설정되는지를 보여주고 있다.
완전한 진리표는 매우 클 뿐만 아니라(28=2562^{8} = 256) 많은 입력 값에 대해 ALU 제어 값이 전혀 상관없기(don’t care) 때문에 ALU 제어가 반드시 특정한 값을 가져야 하는 경우만을 표시하였다.
출력이 모두 0이나 don’t care인 엔트리는 빼고 출력이 1이 되어야 하는 엔트리만을 진리표에 나타내는 이 방법을 이 장이 끝날 때까지 계속 사용할 것이다.
일부 입력 값에 대해서는 관심이 없는 경우가 많으며 표는 작게 유지하는 것이 좋으므로 don’t care 항을 사용한다. 이 진리표의 don’t care 항은 출력이 이 열에 해당한느 입력과 상관없다는 것을 의미한다.
예컨대 그림 4.13의 첫 번째 행처럼 ALUOp 비트 값이 00이면 기능 코드 값에 상관없이 ALU 제어신호가 0010이 된다. 이 경우 이 행의 기능 코드 입력은 don’t care가 된다.
나중에 다른 종류의 don’t care 항의 예를 보게될 것이다.
일단 진리표가 만들어지면 이를 최적화하고 그 다음에 게이트로 바꾼다. 이 절차는 완전히 기계적이다. 따라서 마지막 단계는 여기서 설명하지 않고 부록 D의 D.2 절에서 그 과정과 결과를 설명한다.

주 제어 유닛의 설계

이제까지 기능 코드와 2비트 신호를 제어 입력으로 사용하는 ALU를 어떻게 설계하는가를 설명해 왔는데 이제는 나머지 제어 유닛을 살펴보도록 하자. 그림 4.11의 데이터패스에 필요한 명령어 필드와 제어선들을 알아내는 것으로 이 과정을 시작하자.
명령어 필드들을 데이터패스에 연결하는 방법을 이해하기 위해서는 세 가지 명령어 종류, 즉 R 형식 명령어, 분기 명령어, 적재/저장 명령어 종류의 형식을 다시 살펴보는 것이 효과적일 것이다.
이들 명령어 형식은 그림 4.14에 나타나 있다.
우리가 앞으로 사용할 명령어 형식에 대해 몇 가지 눈여겨볼 점이 있다.
opcode라 불리는 op 필드는 항상 비트 31:26에 포함된다. 이 필드를 Op[5:0]라고 부른다.
읽을 레지스터 두 개는 항상 rs, rt 필드에 의해 지정되는데 rs, rt 필드는 비트 25:21과 비트 20:16에 나타난다. 이것은 R 형식 명령어, 같을 시 분기 및 저장 명령어에 적용된다.
적재 명령어와 저장 명령어를 위한 베이스 레지스터는 항상 비트 25:21(rs)에 있다.
같을 시 분기, 적재, 저장 명령어를 위한 16비트 변위는 항상 비트 15:0에 있다.
목적지 레지스터는 두 곳 중 하나에 있다. 적재 명령어에서는 비트 20:16(rt)에 있고 R 형식 명령어에서는 비트 15:11(rd)에 있다. 따라서 쓰기가 행해질 레지스터 번호로 명령어의 어느 필드를 사용할지 선택하기 위하여 멀티플렉서를 추가해야 한다.
2장의 첫 번째 설계 원칙인 간단하게 하기 위해서는 규칙적인 것이 좋다는 여기에서 제어를 명시하는데도 잘 들어 맞는다.
위의 정보를 이용하여 단순한 데이터패스에 명령어 레이블과 또 다른 멀티플렉서(레지스터 파일의 Write register 번호 입력을 위하여)를 추가한다.
그림 4.15는 이 같은 추가 이외에도 ALU 제어 블록, 상태소자용 쓰기 신호, 데이터 메모리용 읽기 신호, 멀티플렉서용 제어신호를 보여주고 있다.
모든 멀티플렉서는 두 개의 입력을 가지고 있기 때문에 멀티플렉서는 하나의 제어선을 필요로 한다.
그림 4.15에는 1비트 제어선 7개와 2비트 ALUOp 제어신호가 하나 있다. ALUOp 제어신호의 동작은 이미 정의하였으므로 명령어를 실행할 때 이 제어신호들의 값을 어떻게 설정할지 결정하기 전에 이 제어신호들이 무슨 일을 하는지 정의하는 것이 좋을 것 같다. 그림 4.16은 이 7개 제어선의 기능을 설명하고 있다.
제어선 각각의 기능에 대하여 살펴보았으니 이제는 제어선들의 값을 어떻게 할지 알아보자. 제어 유닛은 제어신호 중 하나를 제외한 나머지 모두를 명령어의 opcode 필드만 보고 결정할 수 있다. PCSrc 제어선만은 예외이다.
실행 중인 명령어가 branch on equal이며(제어 유닛이 판단할 수 있음) 동시에 ALU의 Zero 출력이 참일 경우에만 PCSrc가 인가되어야 한다.
PCSrc 신호를 만들려면 제어 유닛에서 나오는 Branch 신호와 ALU의 Zero 신호를 AND해야 한다.
이들 9개 제어신호들은 (그림 4.16의 7개와 ALUOp 두 비트) 제어 유닛의 6개 입력신호(opcode 비트 31:26)에 따라서 결정된다.
제어 유닛과 제어신호가 나와 있는 데이터패스는 4.17에 있다.
제어 유닛에 대한 수식이나 진리표를 작성하기 전에 제어 기능을 간략하게 정의하는 것이 유익하다.
제어신호의 값은 opcode에만 의존하기 때문에, 각각의 opcode 값에 대해 각 제어신호가 0, 1, don’t care(X) 중 어느 값이 되어야 하는지를 정의한다.
그림 4.18은 제어신호들이 각각의 opcode에 대해 어떤 값이 되어야 하는지를 나타낸다.
이 같은 정보는 그림 4.12, 4.16, 4.17로부터 곧바로 얻을 수 있다.

데이터패스의 동작

그림 4.16과 4.18에 포함된 정보를 가지고 제어 유닛의 논리회로를 설계할 수 있다. 그러나 설계에 들어가기 전에 각각의 명령어가 데이터패스를 어떻게 사용하는지를 살펴보자.
다음 몇 개의 그림에서 세 가지 명령어 종류들이 데이터패스를 통과하는 흐름을 보인다. 각각의 그림에서 인가된 제어신호와 활성화된 데이터패스 구성 요소는 진하게 표시하였다.
제어가 0인 멀티플렉서는 비록 제어선이 진하게 표시되지 않더라도 분명한 동작을 취한다는 점에 유의하라. 여러 비트로 된 제어신호들은 그중 어느 하나라도 인가되면 진하게 표시하였다.
그림 4.19는 add $t1, $t2, $t3과 같은 R 형식 명령어의 데이터패스 동작을 보여주고 있다. 모든 일이 하나의 클럭 사이클에 일어나지만 명령어 실행을 네 단계로 생각할 수 있다. 이들 단계는 정보의 흐름에 따라 순서가 결정된다.
1.
명령어를 명령어 메모리에서 가져오고 PC 값을 증가시킨다.
2.
두 레지스터 $t2와 $t3를 레지스터 파일로부터 읽는다. 이 단계에서 주 제어 유닛이 제어선의 값들을 계산한다.
3.
ALU는 레지스터 파일에서 읽어 들인 값들에 대해 연산을 하는데 기능 코드(명령어 funct 필드인 비트 5:0)를 사용하여 ALU 제어신호를 만든다.
4.
ALU의 결과 값이 레지스터 파일에 기록되는데 목적지 레지스터($t1)는 명령어의 비트 15:11을 이용하여 선택한다.
다음과 같은 워드 적재 명령어의 실행을 그림 4.19와 같은 방법으로 나타낼 수 있다.
lw $t1, offset($t2)
Plain Text
그림 4.20은 적재 명령어를 위하여 활성화된 기능 유닛과 인가된 제어선들을 보여주고 있다. 적재 명령어는 다섯 단계로 동작하는 것으로 생각할 수 있다. (R 형식 명령어는 네 단계로 실행된다)
1.
명령어를 명령어 메모리에서 가져오고 PC 값을 증가시킨다.
2.
레지스터($t2) 값을 레지스터 파일로부터 읽는다.
3.
ALU는 레지스터 파일에서 읽어 들인 값과 명령어의 하위 16비트(offset)를 부호확장한 값과의 합을 구한다.
4.
이 합을 데이터 메모리 접근을 위한 주소로 사용한다.
5.
메모리 유닛에서 가져온 데이터를 레지스터 파일에 기록한다. 목적지 레지스터($t1)는 명령어의 비트 20:16이 지정한다.
마지막으로 beq $t1, $t2, offset와 같은 같을 시 분기 명령어의 동작을 같은 방법으로 설명할 수 있다. 이 명령어는 R 형식 명령어와 상당히 비슷하게 동작한다. 그러나 ALU 출력이 PC 값이 PC+4로 바뀔 것인가 아니면 분기 목적지 주소로 바뀔 것인가를 판단하기 위해 사용되는 것이 다르다. 그림 4.21은 실행의 네 단계를 보여주고 있다.
1.
명령어를 명령어 메모리에서 가져오고 PC 값을 증가시킨다.
2.
두 레지스터 $t1과 $t2를 레지스터 파일로부터 읽는다.
3.
ALU는 레지스터 파일에서 읽어 들인 값들에 대해 뺄셈을 한다. 명령어의 하위 16비트(offset)를 부호확장한 후 2비트 왼쪽 자리이동한 값에다 PC+4 값을 더한다. 결과 값이 분기 목적지 주소이다.
4.
어떤 덧셈기의 결과를 PC에 저장할지 ALU의 Zero 출력을 이용하여 판단한다.

제어 유닛의 완성

이제까지 명령어들이 단계별로 어떻게 동작하는지 알아보았으니 이제는 제어 유닛의 구현에 대하여 알아보자. 제어 기능은 그림 4.18의 내용을 이용하면 명확히 정의될 수 있다. 제어 유닛의 출력은 제어선들이며 입력은 6비트의 opcode 필드(Op[5:0])이다. 따라서 opcode의 이진수 인코딩을 이용하여 각 출력의 진리표를 만들 수 있다.
제어 유닛의 논리를 커다란 진리표로 하나로 만든 것이 그림 4.22이다. 이 표는 모든 출력을 망라하고 있으며 opcode 비트들을 입력으로 사용하고 있다. 이것은 제어 기능을 완벽하게 명시하며 자동화된 방법을 이용하여 게이트로 곧바로 구현할 수 있다.
게이트로 구현하는 마지막 단계는 부록 D의 D.2 절에 있다.
이제 MIPS 핵심 명령어 집합에 대한 단일 사이클 구현(single-cycle implementation)을 완성하였으니 명령어 집합의 다른 명령어를 처리하기 위해 어떻게 기본 데이터패스와 제어가 확장될 수 있는지를 보여주기 위해 점프 명령어를 추가하자.

예제) 점프 명령어의 구현

그림 4.17은 2장에서 보았던 명령어 중 많은 것들에 대한 구현을 보여준다. 여기에 빠져 있는 명령어 종류가 점프 명령어이다. 점프 명령어를 포함하도록 그림 4.17의 데이터패스와 제어를 확장하라. 새로운 제어선들의 값은 어떻게 결정되는지 설명하라.
그림 4.23에서 볼 수 있는 것처럼 점프 명령어는 어떤 면에서는 분기 명령어와 비슷하지만 목적지 PC 값 계산 방식이 다르고 또한 조건 분기가 아니라는 점이 다르다. 분기 명령어처럼 점프 명령어의 하위 2비트는 항상 00이다. 32비트 주소 중 그 다음 하위 26비트는 명령어의 26비트 수치 필드에서 나온다. 새 주소와 나머지 상위 4비트는 점프 명령어 주소에 4를 더한 값의 상위 4비트이다. 따라서 다음 세 개 값의 연접(concatenation)을 PC에 저장하면 점프 명령어를 구현할 수 있다.
현재 PC+4의 상위 4비트(다음 명령어 주소의 비트 31:28)
점프 명령어의 26비트 수치 필드
비트 00
그림 4.24는 그림 4.17에 점프 명령어를 위한 제어가 추가된 것을 보여주고 있다. 증가된 PC 값(PC+4), 분기 목적지 PC, 점프 목적지 PC 중에서 하나를 새로운 PC 값의 근원지로 선택하기 위해 멀티플렉서가 추가되었다. 이 추가된 멀티플렉서를 위해 제어신호가 하나 추가로 필요하다. 이 제어신호(Jump라 불림)는 명령어가 점프, 즉 opcode가 2일 때만 인가된다.

단일 사이클 구현은 오늘날 왜 사용되지 않는가?

비록 단일 사이클 설계가 올바르게 작동한다 하더라도 비효율성 때문에 현대적 설계에서는 쓰이지 않는다. 왜 그러한지는 너무 분명한데, 이 같은 단일 사이클 설계에서는 클럭 사이클이 모든 명령어에 대해 같은 길이를 가져야 하기 때문이다.
물록 클럭 사이클은 컴퓨터에서 가능한 경로 중 가장 긴 경로에 의해 결정된다. 이 최장 경로는 적재 명령어라는 것이 거의 확실한데, 적재 명령어는 명령어 메모리, 레지스터 파일, ALU, 데이터 메모리, 레지스터 파일의 다섯 개 기능 유닛을 차례로 사용한다.
CPI 값은 1이지만 단일 사이클 구현은 클럭 사이클이 너무 길기 때문에 전체 성능에서 좋지 않다.
고정된 클럭 사이클을 갖는 단일 사이클 설계를 사용할 때 지불해야 될 대가는 엄청나지만 앞선 작은 명령어 집합에서는 받아들일 수 있을만한 것으로 생각된다.
이같이 매우 간단한 명령어 집합을 가졌던 초창기의 컴퓨터는 이러한 구현 방법을 사용하였다.
그러나 부동소수점 유닛을 구현하려 하거나 좀 더 복잡한 명령어를 갖는 명령어 집합인 경우에는 단일 사이클 구현은 잘 작동하지 않을 것이다.
클럭 사이클은 모든 명령어에 대한 최악의 지연과 같다고 가정해야 하기 때문에 흔한 경우의 지연은 줄여 주지만, 최악의 경우 사이클 시간은 개선하지 못하는 구현은 소용이 없다. 따라서 단일 사이클 구현은 자주 생기는 일을 빠르게라는 1장의 핵심 설계 원칙을 위반하고 있다.
다음 절에서는 파이프라이닝이라는 또 다른 구현 기술을 살펴볼 것이다. 단일 사이클 데이터패스와 매우 유사한 데이터패스를 사용하지만, 처리율이 훨씬 크기 때문에 매우 효율적이다. 파이프라이닝은 여러 개의 명령어를 동시에 실행하여 효율을 높인다.

파이프라이닝에 대한 개관

파이프라이닝(pipelining)은 여러 명령어가 중첩되어 실행되는 구현 기술이다. 오늘날 파이프라이닝은 아주 보편적인 기술이다.
세탁을 많이 하는 사람은 직관적으로 파이프라이닝을 사용해왔다. 파이프라이닝 되지 않은(nonpipelined) 세탁 방법은 다음과 같을 것이다.
1.
세탁기에 한 아름의 더러운 옷을 넣는다.
2.
세탁기 작동이 끝나면 젖은 옷을 건조기에 넣는다.
3.
건조기 작동이 끝나면 건조된 옷을 탁자 위에 놓고 접는다.
4.
접는 일이 끝나면 같은 방 친구에게 옷을 장롱에 넣어 달라고 부탁한다.
방 친구가 일을 끝내면 그 다음 더러운 옷 한 묶음에 대해 다시 시작한다.
그림 4.25에서 보는 바와 같이 파이프라인 방법은 시간이 훨씬 덜 걸린다. 첫 번째 묶음의 세탁이 끝나서 건조기에 넣은 후, 두 번째 더러운 옷 묶음을 세탁기에 넣는다.
첫 번째 묶음이 건조되면 탁자 위에 놓고 접기 시작하고, 젖은 옷 묶음은 건조기에 또 다음의 더러운 옷 묶음은 세탁기에 넣는다.
다음은 친구에게 첫 번째 묶음을 옷장에 넣어줄 것을 부탁하고, 당신은 두 번째 묶음을 접기 시작하며 세 번째 묶음을 건조기에, 네 번째 묶음은 세탁기에 넣는다.
이 시점에서는 모든 과정(파이프라이닝에서는 단계(stage)라고 한다)이 동시에 작동하고 있다. 각 단계를 위한 별도의 자원이 있는한 작업들을 파이프라이닝 할 수 있다.
파이프라이닝의 역설적인 점 하나는 더러운 양말 하나를 세탁기에 넣고 건조한 후 접어서 옷장에 넣을 때까지의 시간은 파이프라이닝을 한다고 더 짧아지는 것이 아니라는 것이다.
묶음이 많을 떄 파이프라이닝이 더 빠른 이유는 모든 것이 병렬로 동작하며 따라서 같은 시간에 더 많은 묶음이 끝날 수 있기 때문이다.
파이프라이닝은 세탁 시스템의 처리량을 증가시킨다. 그러므로 파이프라이닝이 단일 묶음을 끝내는데 걸리는 시간을 단축하지는 못하지만, 해야 할 빨래가 많을 경우에는 처리량이 증가하므로 일을 끝내는데 걸리는 전체 시간을 단축시킨다.
만약 모든 단계가 거의 같은 시간이 걸리며 할 일이 충분히 많다면 파이프라이닝에 의한 속도 향상은 파이프라인의 단계 수와 같다.
세탁, 건조, 접기 그리고 넣기의 네 단계가 있으므로 이 경우는 4이다. 파이프라인 세탁소는 파이프라이닝 되지 않은 경우에 비해 4배 빠를 수 있다.
그림 4.25에서는 겨우 2.3배 빠른데, 이 경우는 묶음이 4개 밖에 없기 때문이다. 그림 4.25의 파이프라인 버전에서 작업의 시작과 끝 부분에서는 파이프라인이 완전히 차 있지 않다. 할 일의 수가 파이프라인 단계 수에 비해 많이 않을 경우에는 이 같은 시작 시간과 마무리 시간이 성능에 영향을 미친다.
일감의 수가 4보다 훨씬 크다면 대부분의 시간에 단계들이 다 차 있을 것이고 따라서 처리량의 증가는 4배에 가깝게 될 것이다.
명령어 실행을 파이프라이닝한 프로세서도 같은 원리가 적용된다. MIPS 명령어는 전통적으로 다섯 단계가 걸린다.
1.
메모리에서 명령어를 가져온다.
2.
명령어를 해독하는 동시에 레지스터를 읽는다. MIPS 명령어는 형식이 규칙적이므로 읽기와 해독이 동시에 일어날 수 있다.
3.
연산을 수행하거나 주소를 계산한다.
4.
데이터 메모리에 있는 피연산자에 접근한다.
5.
결과 값을 레지스터에 쓴다.
따라서 이 장에서 살펴보는 MIPS 파이프라인은 다섯 단계를 가진다. 다음 예제는 파이프라이닝이 세탁소에서 속도 증가를 보였듯이 명령어 실행에서도 속도를 증가시키는 것을 보여준다.

예제) 단일 사이클 대 파이프라인의 성능

이 논의를 구체적으로 하기 위해 파이프라인을 만든다. 이 예제와 이 장의 나머지에서는 load word(lw), store word(sw), add(add), subtract(sub), AND(and), OR(or), set-less-than(slt), branch-on-equal(beq) 8개의 명령어에만 관심을 갖도록 한다.
단일 사이클 구현에서 명령어 사이의 평균 시간을 파이프라인 구현의 경우와 비교하라. 단일 사이클 구현에서는 모든 명령어가 한 클럭 사이클 걸린다. 이 예제에서 주요 기능 유닛의 동작시간은 메모리 접근 200ps, ALU 연산 200ps, 레지스터 파일 읽기나 쓰기 100ps이다. 단일 사이클 모델에서는 모든 명령어가 한 클럭 사이클이 걸리므로 가장 느린 명령어를 수용할 수 있을만큼 클럭 사이클이 길어져야 한다.
8개의 명령어 각각에 필요한 시간은 그림 4.26에 나와 있다. 단일 사이클 설계는 가장 느린 명령어를 수용해야 한다. 그림 4.26에서 알 수 있듯이 가장 느린 명령어는 lw 이다. 따라서 모든 명령어에 필요한 시간은 800ps이다.
그림 4.27은 그림 4.25와 비슷하게 3개의 워드 적재 명령어의 파이프라이닝 되지 않은 실행과 파이프라인 실행을 비교한다. 따라서 파이프라이닝 되지 않은 설계에서 첫 번째 명령어와 네 번째 명령어 사이의 시간은 3x800ps 즉 2400ps이다.
모든 파이프라인 단계는 한 클럭 사이클이 걸린다. 따라서 클럭 사이클은 가장 느린 동작을 수용할 만큼 충분히 길어야 한다. 단일 사이클 설계에서 어떤 명령어들은 500ps에 실행될 수 있지만 최악의 경우인 800ps의 클럭사이클을 가져야 되었듯이, 파이프라인 실행 클럭 사이클도 어떤 단계는 100ps가 걸리지만 최악의 경우인 200ps가 되어야 한다. 파이프라이닝은 아직도 4배의 성능 향상을 제공한다. 첫 번째 명령어와 네 번째 명령어 사이의 시간은 3x200ps, 즉 600ps이다.
위에 설명한 속도 향상에 관한 논의를 식으로 바꿀 수 있다. 단계들이 완벽하게 균형을 이루고 있으면 파이프라인 프로세서에서 명령어 사이의 시간은 다음과 같다. (이상적인 조건을 가정한다면)
명령어 사이의 시간(파이프라인) = 명령어 사이의 시간(파이프라이닝 되지 않음) / 파이프 단계 수
Plain Text
이상적인 조건하에 많은 명령어가 있을 경우 파이프라이닝에 의한 속도 향상은 파이프 단계 수와 거의 같다. 다섯 단계 파이프라인은 거의 다섯 배 더 빠르다.
위 식에 따르면 다섯 단계 파이프 라인은 800ps의 파이프라이닝 되지 않은 시스템보다 5배 향상된 성능을 제공해야 한다.
즉 클럭사이클이 160ps가 되어야 한다. 그러나 예제는 단계가 완벽하게 균형 잡혀 있지는 않다는 것을 보여준다.
더구나 파이프라이닝은 어느 정도의 오버헤드를 포함하고 있다. 이 오버헤드의 원인이 어디 있는지는 금방 알게 될 것이다.
이런 이유로 파이프라인 프로세서에서의 명령어당 시간이 가능한 최솟값보다 커져서 속도 향상은 파이프라인 단계 수보다 작아진다.
더구나 예제에서 4배만큼의 성능 향상이 있다는 주장은 3개 명령어에 대한 전체 실행시간에 반영되어 있지 않다. 실행시간은 1400ps대 2400ps이다.
물론 이것은 전체 명령어 개수가 많지 않기 때문이다. 명령어의 수를 증가시키면 무슨 일이 일어날까? 앞에서 본 그림을 1,000,003개의 명령어로 확장시키자. 파이프라인 예제에 1,000,000개의 명령어를 추가한다.
명령어 하나당 200ps가 전체 실행시간에 추가된다. 전체 실행시간은 1,000,000 x 200ps + 1400ps 즉 200,001,400ps이다.
파이프라이닝 되지 않은 예제에서 1,000,000개의 명령어를 추가하여 각 명령어는 800ps씩이 걸린다. 따라서 전체 실행 시간은 1,000,000 x 800ps + 2400ps 즉 800,002,400ps이다.
이같은 이상적인 조건 하에서는 파이프라이닝 되지 않은 컴퓨터와 파이프라인 컴퓨터에서의 실제 프로그램의 전체 실행시간의 비율은 명령어 사이의 시간 비율에 가깝다.
800,002,400ps / 200,001,400ps ≃ 800ps / 200ps ≃ 4.00
Plain Text
파이프라이닝은 개별 명령어의 실행시간을 줄이지는 못하지만 대신 명령어 처리량을 증대시킴으로써 성능을 향상시킨다. 실제 프로그램들은 수십억 개의 명령어를 실행하기 때문에 명령어 처리량이 중요한 척도이다.

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

파이프라이닝에 대한 이런 간단한 설명만으로도 MIPS 명령어 집합 설계의 핵심을 파악할 수 있다. MIPS 명령어 집합은 원래 파이프라인 실행을 위해 설계된 것이다.
첫째, 모든 MIPS 명령어는 같은 길이를 갖는다.
이 같은 제한조건은 첫 번째 파이프라인 단계에서 명령어를 가져오고 그 명령어들을 두 번째 단계에서 해독하는 것을 훨씬 쉽게 해준다.
x86 같은 명령어 집합에서는 명령어 길이가 1바이트에서부터 15바이트까지 변하기 때문에 파이프라이닝이 생각보다 매우 힘들다.
최근의 x86 구조의 구현은 실제로는 x86 명령어들을 MIPS 명령어처럼 생긴 단순한 마이크로 명령어들로 변환한다. 그리고 원래의 x86 명령어 대신 마이크로명령어를 파이프라이닝한다. 이에대해서는 4.10절에서 설명한다.
둘째, MIPS는 몇 가지 안 되는 명령어 형식을 가지고 있다.
모든 명령어에서 근원지 레지스터 필드는 같은 위치에 있다. 이 같은 대칭성은 두 번째 단계에서 하드웨어가 어떤 종류의 명령어가 인출되었는지를 결정하는 동안 레지스터 파일 읽기를 동시에 할 수 있다는 것을 의미한다.
만약 MIPS 명령어 형식이 대칭적이 아니면 단계 2를 나누어서 총 6개의 파이프라인 단계가 되었을 것이다. 곧 긴 파이프라인의 어두운 면을 보게 될 것이다.
셋째, MIPS에서는 메모리 피연산자가 적재와 저장 명령어에서만 나타난다.
이 같은 제한은 메모리 주소를 계산하기 위해 실행 단계를 사용하고 다음 단계에서 메모리에 접근할 수 있다는 것을 의미한다.
x86처럼 메모리에 있는 피연산자에 연산을 할 수 있으면 단계 3과 4가 주소 단계, 메모리 단계, 실행 단계로 확장되어야 한다.
넷째, 2장에서 설명한 바와 같이 피연산자는 메모리에 정렬(align) 되어 있어야 한다.
따라서 한 데이터 전송 명령어가 두 번의 데이터 메모리 접근을 요구할까 봐 걱정할 필요가 없다. 파이프라인 단계 하나에서 프로세서와 메모리가 필요한 데이터를 주고 받을 수 있다.

파이프라인 해저드

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

구조적 해저드

첫 번째 해저드는 구조적 해저드(structual hazard)라 불린다. 이는 같은 클럭 사이클에 실행하기를 원하는 명령어의 조합을 하드웨어가 지원할 수 없다는 것을 의미한다.
세탁소에서는 독립된 세탁기와 건조기를 사용하지 않고 세탁기와 건조기가 같이 붙어 있는 기계를 사용하든지 또는 친구가 다른 일을 하느라고 바빠서 빨래를 치우지 않으면 구조적 해저드가 발생한다.
그러면 조심스럽게 스케쥴링된 파이프라인 계획이 틀어진다.
위에서 이야기한 것처럼 MIPS 명령어 집합은 파이프라이닝하도록 설계되었기 때문에 설계자가 파이프라인을 설계할 때 구조적 해저드를 피하는 것이 비교적 용이하다. 그러나 메모리가 두 개가 아니고 하나라고 생각해 보자.
그림 4.27의 파이프라인에 네 번째 명령어가 추가된다면 같은 클럭 사이클에 첫 번째 명령어는 메모리에서 데이터에 접근하고, 네 번째 명령어는 같은 메모리에서 명령어를 가져오게 된다. 앞의 파이프라인에 메모리가 하나라면 구조적 해저드를 피할 수 없을 것이다.

데이터 해저드

데이터 해저드(data hazard)는 어떤 단계가 다른 단계가 끝나기를 기다려야 하기 때문에 파이프라인이 지연되어야 하는 경우 일어난다. 옷을 개다가 한 짝이 없는 양말을 발견했다고 생각하자.
한 가지 방법은 방으로 달려가서 옷장을 뒤져 나머지 짝을 찾아보는 것이다. 옷장을 뒤지고 있는 동안은 건조 과정을 끝내고 개는 과정을 기다리는 옷들과 세탁 과정을 끝내고 건조 과정을 기다리는 옷들은 기다려야만 한다는 것이 분명하다.
컴퓨터 파이프라인에서는 어떤 명령어가 아직 파이프라인에 있는 앞선 명령어에 종속성을 가질 때 데이터 해저드가 일어난다(세탁에서는 이 같은 관계가 실제로 존재하지 않는다)
예컨대 add 명령어 바로 다음에 add의 합($s0)을 사용하는 뺄셈 명령어가 뒤따르는 경우를 가정하자.
add $s0, $t0, $t1 sub $t2, $s0, $t3
Plain Text
별다른 조치가 없다면 데이터 해저드가 파이프라인을 심각하게 지연시킬 수 있다. add 명령어는 다섯 번째 단계까지는 결과 값을 쓰지 않을텐데 이는 파이프라인이 세 개의 클럭 사이클을 낭비해야 한다는 것을 의미한다.
컴파일러를 이용해서 이런 데이터 해저드를 모두 제거하려고 할 수도 있지만 결과는 그리 만족스럽지 못할 것이다. 이 같은 의존성은 너무 자주 일어나고 지연은 너무 길어서 컴파일러가 우리를 이 같은 딜레마로부터 구해줄 것이라고 기대하기가 어렵다.
첫 번째 해결책은 데이터 해저드를 해결하려고 노력하기 전에 명령어가 끝날 때까지 기다릴 필요가 없다는 관찰에 기반을 두고 있다.
위와 같은 코드인 경우 ALU가 add 명령어의 합을 만들어내자마자 이것을 뺄셈의 입력으로 사용할 수 있다. 별도의 하드웨어를 추가하여 정상적으로는 얻을 수 없는 값을 내부자원으로부터 일찍 받아 오는 것을 전방전달(forwarding) 또는 우회전달(bypassing)이라고 한다.

예제) 두 명령어 사이의 전방전달

앞의 두 명령어에서 어느 파이프라인 단계가 전방전달에 의해 연결되어야 하는지를 보여라. 파이프라인 다섯 단계 동안의 데이터패스를 나타내기 위해 그림 4.28의 그림을 사용하라. 각 명령어에 데이터패스를 한 벌씩 할당해 정렬하라. 그림 4.25의 세탁소 파이프라인과 비슷하게 정렬하면 된다.
그림 4.29는 add 명령어의 실행 단계 후의 $s0 값을 sub 명령어의 실행 단계 입력으로 전방전달하기 위한 연결을 보여주고 있다.
그림 표현에서 목적지 단계가 근원지 단계보다 시간상 늦을 경우에만 전방전달 통로가 유효하다.
예컨대 첫 번째 명령어의 메모리 접근 단계의 출력으로부터 다음 명령어의 실행 단계 입력으로의 전방전달 통로는 유효한 통로가 될 수 없다. 왜냐면 그 통로는 시간이 뒤로 돌아가는 것을 의미하기 때문이다.
전방전달은 매우 잘 동작하는데 자세한 것은 4.7절에서 설명한다. 그러나 전방전달이 모든 파이프라인 지연을 방지할 수는 없다.
예컨대 첫 번째 명령어가 add 명령어가 아니고 $s0의 적재 명령어라고 가정하자. 그림 4.29를 보고 상상할 수 있는 것처럼 원한느 데이터는 종속관계에 있는 첫 번째 명령어의 4단계 후에만 사용할 수 있다. 이는 sub 명령어의 세 번째 단계 입력으로는 너무 늦다.
따라서 그림 4.30에서 보는 바와 같이 적재-사용 데이터 해저드(load-use data hazard)의 경우에는 전방전달을 해도 한 단계가 지연되어야 한다.
이 그림은 파이프라인 지연(pipeline stall)이라는 중요한 파이프라인 개념을 보여주고 있다. 지연은 거품(bubble)이라는 별명으로 불리는 경우도 많다. 파이프라인의 다른 곳에서도 지연을 볼 수 있다.
4.7절은 이같이 어려운 경우의 처리 방법을 설명하는데, 하드웨어 검출과 지연을 사용하거나 적재-사용 데이터 해저드를 피할 수 있게 명령어의 순서를 바꾸는 소프트웨어를 사용한다.

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

C로 작성된 다음 코드를 생각해 보자.
a = b + e; c = b + f;
Plain Text
다음은 이 코드에 대한 MIPS코드이다. 모든 변수는 메모리에 있고 $t0를 베이스로 사용해서 접근할 수 있는 위치에 있다고 가정한다.
lw $t1, 0($t0) lw $t2, 4($t0) add $t3, $t1, $t2 sw $t3, l2($t0) lw $t4, 8($t0) add $t5, $t1, $t4 sw $t5, l6($t0)
Plain Text
위 코드에서 해저드를 찾아내고 파이프라인 지연을 피할 수 있도록 명령어들을 재정렬하라.
두 add 명령어가 모두 해저드를 가지고 있는데 이는 바로 앞의 명령어인 lw 명령어와 각각 종속성이 있기 때문이다. 전방전달을 하면 첫 번째 lw 명령어에 대한 첫 번째 add 명령어의 종속성과 저장 명령어 관련 모든 해저드를 포함하여 가능성 있는 몇 가지 다른 해저드가 제거됨에 주목하라. 세 번째 lw 명령어를 위로 올리면 두 해저드가 모두 없어진다.
lw $t1, 0($t0) lw $t2, 4($t0) lw $t4, 8($t0) add $t3, $t1, $t2 sw $t3, l2($t0) add $t5, $t1, $t4 sw $t5, l6($t0)
Plain Text
전방전달 유닛이 있는 파이프라인 프로세서에서 재정렬된 코드는 원래 코드보다 두 사이클 먼저 완료된다.
전방전달은 언급한 네 가지 통찰(4.5절) 외에 MIPS 구조에 대한 또 다른 점을 인식하게 한다. 각각의 MIPS 명령어는 기껏해야 하나의 결과 쓰기를 할 뿐이며 그것도 파이프라인 끝에서 한다. 명령어 하나에 전방전달해야 하는 결과가 여러 개 있든가 명령어 실행의 초기에 결과 쓰기를 한다면 전방전달은 더 어려워졌을 것이다.

제어 해저드

세 번째 해저드는 제어 해저드(control hazard)라 불리는데 다른 명령어들이 실행 중에 한 명령어의 결과 값에 기반을 둔 결정을 할 필요가 있을 때 일어난다.
어떤 세탁소 점원에게 축구팀 유니폼을 세탁하는 임무가 주어졌다고 하자.
세탁물이 얼마나 더러운지를 알아내면 선택한 세제와 물 온도가 유니폼을 깨끗하게 할 수 있을 정도로는 강해야 하지만 너무 강해 유니폼이 곧 해질 정도는 안 되도록 결정해야 한다.
앞의 세탁소 파이프라인에서 세탁기 설정을 바꿀 필요가 있는지 아닌지를 결정하라면 두 번째 단계까지 기다려서 마른 유니폼을 조사해야 한다. 어떻게 할 것인가?
세탁소나 컴퓨터의 제어 해저드에 대한 두 가지 해결책이 있는데, 그중 첫 번째는 지연이다.
지연: 첫 번째 묶음이 건조될 때까지 그냥 순차적으로 작업하되 올바른 비율이 될 때까지 반복한다.
이 같은 보수적인 방법이 동작하는 것은 확실하지만 느리다.
컴퓨터에서 이러한 결정 작업에 해당하는 것이 바로 분기 명령어이다. 바로 다음 클럭 사이클에서 분기 명령어를 이을 명령어를 가져오기 시작해야 한다. 그러나 파이프라인은 다음 명령어가 어느 것이 되어야 할지 알 수가 없다. 왜냐면 이제 방금 메모리에서 분기 명령어를 받았을 뿐이기 때문이다.
세탁소에서와 같이 한다면 한 가지 가능한 해결책은 분기 명령어를 가져온 직후 지연시켜서 파이프라인이 분기의 결과를 판단하고 어느 주소에서 다음 명령어를 가져올지 알게 될 때까지 기다리게 하는 것이다.
하드웨어가 충분하기 때문에 파이프라인의 두 번째 단계에서 레지스터를 테스트하고 분기 주소를 계산하고 PC 값을 바꿀 수 있다고 가정하다(세부 사항은 4.8절을 참조하라)
이렇게 별도의 하드웨어가 있어도 조건부 분기가 포함된 아래 프로그램을 실행하는 파이프라인은 그림 4.31처럼 보일 것이다. 분기가 실패하면 실행되는 lw 명령어는 시작하기 전에 별도의 200ps 클럭 사이클 동안 지연된다.

예제) 분기 시 지연(stall on branch)의 성능

분기 명령어가 나오면 지연시키는 방법이 CPI에 미치는 영향을 추정하라. 다른 모든 명령어의 CPI는 1이라고 가정한다.
3장의 그림 3.28에서 본 바와 같이 분기 명령어가 SPECint2006에서 실행되는 명령어의 17%이다. 다른 명령어들은 CPI가 1이고 분기 명령어는 지연 때문에 한 클럭 사이클이 더 필요하다. 따라서 CPI 값은 1.17이 되고 이상적인 경우와 비교하면 1.17배 속도 저하가 생긴다.
파이프라인이 긴 경우에는 흔히 그렇듯이 분기를 두 번째 단계에서 다 해결하지 못한다면, 분기 명령어마다 지연시키는 것은 훨씬 더 큰 속도 저하를 초래할 것이다. 이 방법은 지불해야 할 대가가 너무 커서 대부분의 컴퓨터에서 사용하기 힘들기 때문에 제어 해저드에 대한 두 번째 해결책이 나오게 되었다.
예측: 유니폼 세탁에 적절한 배합을 어느 정도 잘 알고 있다면, 첫 번째 묶음이 건조될 때까지 기다리는 동안 배합을 예측해서 두 번째 묶음을 세탁한다.
이 방법은 예측이 맞으면 파이프라인의 성능을 떨어뜨리지 않는다. 그러나 예측이 틀렸으면 다시 세탁해야 한다.
대부분의 컴퓨터가 분기 명령어를 다루기 위해서 예측(prediction)을 사용한다. 간단한 방법은 분기가 항상 실패한다고 예측하는 것이다. 예측이 옳으면 파이프라인은 최고 속도로 진행된다. 실제로 분기가 일어날 때만 파이프라인이 지연된다. 그림 4.32는 이러한 예를 보여준다.
분기 예측(branch prediction)에 대한 좀 더 정교한 버전은 어떤 경우에는 분기한다(taken)고 예측하고 어떤 경우는 분기하지 않는다고(untaken) 예측하는 것이다.
우리 비유에서는 짙은 색 유니폼(홈 경기 유니폼)을 한 가지 배합으로 빨고, 밝은 색 유니폼(원정 경기 유니폼)을 또 다른 배합으로 빠는 것이다.
프로그래밍의 경우 순환문의 끝에는 순환문의 꼭대기로 점프라하라는 분기 명령어가 있다. 이 명령어들은 분기가 일어날 가능성이 높고 분기 방향이 후방이므로, 이에 착안하여 현재 위치보다 작은 주소로 점프하는 분기 명령어는 분기가 항상 일어난다고 예측할 수 있다.
이러한 분기 예측 방법들은 보편적 행동에 의존하며 특정 분기 명령어의 개별성은 고려하지 않는다.
동적 하드웨어 예측기(dynamic hardware predictor)는 이와는 정반대로 개별 분기 명령어의 행동에 의존하는 예측을 하며 프로그램이 진행되는 도중에 예측을 바꿀 수 있다.
앞의 비유에 동적 예측을 적용하면 유니폼이 과거에 얼마나 더러웠는지 찾아봐서 적절한 배합을 추측하고 최근 예측의 성공 여부에 따라 다음 예측을 조정한다.
분기의 동적 예측에 대한 보편적 방법 중 하나는 각 분기가 일어났는지 안 일어났는지 이력을 기록하고, 최근의 과거 이력을 사용하여 미래를 예측하는 것이다.
좀 뒤에 보겠지만 유지되는 이력의 양이나 정보의 종류가 많아져서 그 결과 동적 분기 에측기가 90% 이상의 정확도를 가지게 되었다. (4.8절 참조)
예측이 어긋났을 때는 잘 못 예측한 분기 명령어 뒤에 나오는 명령어들을 무효화하고 올바른 분기 주소로부터 파이프라인을 다시 시작해야 한다. 세탁물 비유에서는 잘못 예측한 세탁물을 다시 빨 수 있도록 새로운 세탁물을 받아들이는 것을 중지해야 한다.
제어 해저드에 대한 다른 모든 해결책에서와 마찬가지로 분기 예측에서도 긴 파이프라인은 문제를 악화시키기 때문에 예측의 비용을 증대시킨다. 제어 해저드에 대한 해결책들은 4.8절에서 자세히 다루어진다.

파이프라이닝 개관에 대한 요약

파이프라이닝은 순차적인 명령어 스트림에 있는 명령어간 병렬성을 추구하는 기술이다. 이는 멀티프로세서 프로그래밍과는 달리 기본적으로 프로그래머에게 보이지 않는다는 상당한 이점을 가지고 있다.
이 장의 다음 절들에서 4.4절의 단일 사이클 구현에서 사용한 MIPS 명령어 집합의 일부를 사용하여 파이프라이닝의 개념을 설명하고 파이프라인의 단순화된 버전을 보인다. 또 파이프라이닝이 갖는 문제점과 전형적 상황에서 얻을 수 있는 성능에 대하여 알아본다.

프로그램 성능의 이해

메모리 시스템을 제외하고는 파이프라인이 효과적 동작이 프로세서 CPI 즉 프로세서의 성능을 결정하는데 있어 매우 중요한 요인이다.
4.10절에서 보겠지만 최신 다중 내보내기(multiple issue) 파이프라인 프로세서의 성능을 이해하는 것은 복잡하여 단순 파이프라인 프로세서에서 일어나는 문제점들보다 더 많은 것을 알아야 한다.
그러나 구조적 해저드, 데이터 해저드, 제어 해저드는 단순 파이프라인 프로세서 뿐만 아니라 좀 더 정교한 프로세서에서도 중요하다.
오늘날 파이프라인에서 구조적 해저드는 보통 부동소수점 유닛 주변에서 주로 일어나는데, 부동소수점 유닛은 완전히 파이프라이닝되어 있지 않을 수 있다.
제어 해저드는 정수형 프로그램에서 주로 일어나는데, 이는 분기 명령어가 자주 나타나는데 반하여 예측 가능한 분기는 오히려 적기 때문이다.
데이터 해저드는 정수형 프로그램이나 부동소수점 프로그램 양쪽에서 성능상 병목으로 작용할 수 있다. 많은 경우에 부동소수점 프로그램에서 데이터 해저드를 다루는게 더 쉽다. 왜냐하면 부동소수점 프로그램에서는 분기 명령어가 자주 나오지 않고 좀 더 규칙적인 메모리 접근 패턴을 가지고 있어 컴파일러가 해저드를 피하기 위해 명령어를 재정렬하기 쉽기 때문이다.
규칙적인 메모리 접근 패턴이 적고 포인터를 많이 사용하는 정수형 프로그램에서는 그런 최적화를 하는 것이 좀 더 어렵다. 재정렬을 통해 데이터 종속성을 줄이려는 야심찬 컴파일러와 하드웨어 기법들이 존재한다.

요점 정리

파이프라이닝은 동시에 실행되는 명령어의 수를 증가시키며 명령어들이 시작하고 끝나는 속도를 증가시킨다. 파이프라이닝은 각각의 명령어 실행을 끝내는데 걸리는 시간을 단축시키지는 않는데 이 시간을 지연시간(latency)이라고 부른다.
예컨대 다섯 단계 파이프라인은 한 명령어가 끝나는데 다섯 클럭 사이클이 걸린다. 1장에서 사용했던 용어를 사용하면 파이프라이닝은 각각의 명령어 지연시간(execution time 또는 latency) 보다는 처리율을 향상시킨다.
명령어 집합은 파이프라인 설계도를 쉽게도 하고 어렵게도 한다. 파이프라인 설계자들은 이미 구조적 해저드, 제어 해저드, 데이터 해저드 등과 맞닥뜨려 이를 해결해 왔다. 분기 예측, 전방전달은 올바른 결과를 얻으면서도 컴퓨터를 빠르게 하는데 도움을 준다.

파이프라인 데이터패스 및 제어

아래 그림은 4.4절의 단일 사이클 데이터패스에 파이프라인 단계를 같이 보여주고 있다. 명령어를 다섯 단계로 나눈 것은 다섯 단계 파이프라인을 의미하며 이는 한 클럭 사이클에 최대 5개의 명령어가 실행 중일 수 있다는 것을 의미한다. 따라서 데이터패스를 5개 부분으로 나누어여 하며 각 부분은 명령어 실행 단계에 따라 다음과 같이 이름이 붙여진다.
1.
IF: 명령어 인출
2.
ID: 명령어 해독 및 레지스터 파일 읽기
3.
EX: 실행 또는 주소 계산
4.
MEM: 데이터 메모리 접근
5.
WB: 쓰기(write back)
그림 4.33을 보면 이 5개 요소가 데이터패스를 그리는 방법에 대충 맞아 들어간다. 명령어와 데이터는 실행되면서 다섯 단계를 왼쪽에서 오른쪽으로 움직여간다.
다시 세탁소 비유로 돌아가면 옷들은 선을 따라 움직여 가면서 더 깨끗해지고 건조되고 정돈되어가지 결코 뒤쪽으로 움직여가지는 않는다.
그러나 명령어에서는 이같이 왼쪽에서 오른쪽으로 흐르는 것에 두 가지 예외가 있다.
쓰기 단계: 이 단계에서는 결과를 데이터패스의 중앙에 있는 레지스터 파일에다 쓴다.
PC의 다음 값 선정: 증가된 PC 값과 MEM 단계의 분기 주소 중에서 고른다.
오른쪽에서 왼쪽으로 흐르는 데이터는 현재 데이터에 영향을 주지 않는다. 파이프라인의 뒤쪽에 있는 명령어들만이 이 같은 역방향 데이터 흐름에 영향을 받는다.
오른쪽에서 왼쪽으로 가는 첫 번째 연결선은 데이터 해저드로 이어질 수 있으며 두 번째 연결선은 제어 해저드로 이어질 수 있다.
파이프라인 실행에서 일어나는 일을 보여주는 한 가지 방법은 각 명령어가 자신의 데이터패스를 가지고 있는 것처럼 하고, 이들을 시간 축에 배치하여 그들 사이의 관계를 보여주는 것이다.
그림 4.34는 공통 시간 축에 명령어들 자신의 데이터패스를 보여 줌으로써 그림 4.27의 명령어 실행을 보여준다.
예컨대 그림 4.34에서 보는 바와 같이 명령어 메모리는 명령어의 다섯 단계 중 한 단계에서만 사용된다. 그러므로 이 명령어가 다른 네 단계에 있는 동안에 명령어 메모리는 다른 명령어가 사용할 수 있다.
다른 네 단계 동안에도 각 명령어의 값을 유지하기 위해 명령어 메모리에서 읽어 들인 값을 레지스터에 저장해야 한다. 비슷한 논지가 모든 파이프라인 단계에 적용된다.
따라서 그림 4.33에서의 단계 사이를 나누는 선이 있는 곳마다 레지스터를 두어야 한다. 다시 세탁소 비유로 돌아가면 다음 단계로 갈 옷을 보관하기 위해 각 단계 사이에 바구니를 비치해야 한다.
그림 4.35는 파이프라인 데이터패스를 보여주는데 파이프라인 레지스터가 강조 되어 있다. 모든 명령어는 매 클럭 사이클마다 한 파이프라인 레지스터에서 다음 레지스터로 전진한다. 레지스터는 이 제리스터가 분리하고 있는 두 단계를 따라 이름 붙여진다.
예컨대 IF 단계와 ID 단계 사이의 파이프라인 레지스터는 IF/ID라 불린다.
쓰기(write-back) 단계 끝에는 파이프라인 레지스터가 없다는 것에 주목하라. 모든 명령어는 컴퓨터의 상태 —레지스터 파일, 메모리, PC— 를 갱신해야 한다. 이렇게 갱신되는 상태는 별도의 파이프라인 레지스터가 필요없다.
예컨대 적재 명령어는 32개 레지스터 중 하나에다 결과 값을 쓰는데, 뒤에 있는 명령어 중에서 이 데이터를 필요로 하는 것이 있으면 그냥 그 레지스터를 읽으면 된다. 따라서 파이프라인 레지스터에 저장할 필요가 없다.
모든 명령어는 PC 값을 증가시키든 분기 목적지 주소로 바꾸든 아무튼 PC 값을 바꾼다. PC는 파이프라인 레지스터로 생각할 수 있다.
즉 파이프라인의 IF 단계에 데이터를 제공하는 파이프라인 레지스터로 생각할 수 있다는 말이다. 그러나 그림 4.35에서 파란색으로 표시된 파이프라인 레지스터와는 달리 PC는 사용자가 볼 수 있는 구조적 상태이다.
예외가 일어나면 구조적 상태의 내용은 저장되어야 하지만 파이프라인 레지스터는 버리게 되는게 다르다. 세탁소 비유에서는 PC를 세탁 단계 전의 더러운 옷 묶음을 가지고 있는 바구니로 볼 수 있다.
그림 4.36-4.38은 적재 명령어가 파이프라인의 다섯 단계를 통과해 감에 따라 활성화되는 데이터패스 부분을 파란색으로 보여주고 있다.
적재 명령어는 다섯 단계 모두에서 활성화되므로 적재 명령어를 첫 번째로 보였다.
그림 4.28-4.30처럼 레지스터나 메모리가 읽힐 때는 레지스터 또는 메모리의 오른쪽 반을 강조하고 이들에게 쓰기가 행해질 때는 왼쪽 반을 강조한다.
각 그림에서 명령어 약어인 lw와 함께 활성화된 파이프 단계의 이름을 보여준다. 다섯 단계는 다음과 같다.
1.
명령어 인출(Instruction fetch)
그림 4.36의 왼쪽 그림은 PC에 있는 주소를 사용하여 메모리로부터 명령어를 읽어오고 IF/ID 파이프라인 레지스터에 저장하는 것을 보여준다. PC 주소는 4만큼 증가되어 PC에 다시 저장됨으로써 다음 클럭 사이클에 사용될 수 있다.
이 증가한 주소는 IF/ID 파이프라인 레지스터에도 쓰이는데 이것은 beq와 같은 명령어처럼 뒤에 필요한 경우를 위해서이다.
컴퓨터는 어떤 종류의 명령어를 가져오고 있는지 모르기 때문에 어떤 명령어에 대해서도 대비해야 하며 잠재적으로 필요한 정보를 파이프라인을 따라 전달해야 한다.
2.
명령어 해독 및 레지스터 파일 읽기 (instruction decode and register file read)
그림 4.36의 아래 그림은 IF/ID 파이프라인 레지스터의 명령어 부분이 16비트 수치 필드(32비트로 부호확장됨) 값과 레지스터 번호 두 개를 제공하는 것을 보여준다.
세 값 모두 증가한 PC 주소 값과 더불어 ID/EX 파이프라인 레지스터에 저장된다. 차후의 클럭 사이클에 어느 명령어에 의해 필요할지 모르는 것은 모두 전달한다.
3.
실행 또는 주소 계산 (execute or address calculation)
그림 4.37은 적재 명령어가 ID/EX 파이프라인 레지스터로부터 레지스터 1의 내용과 부호확장된 수치를 읽고, ALU를 사용하여 이들을 더하는 것을 보여준다. 합은 EX/MEM 파이프라인 레지스터에 저장된다.
4.
메모리 접근 (memory access)
그림 4.38의 위쪽 그림은 적재 명령어가 EX/MEM 파이프라인 레지스터에서 주소를 받아서 데이터 메모리를 읽고 이 데이터를 MEM/WB 파이프라인 레지스터에 저장하는 것을 보여준다.
5.
쓰기 (write-back)
그림 4.38의 아래 그림은 마지막 단계를 보여준다. MEM/WB 파이프라인 레지스터에서 데이터를 읽어서 그 데이터를 그림 중앙에 있는 레지스터 파일에 쓴다.
이 같이 적재 명령어를 따라가 보면 후속 파이프 단계에서 필요한 정보는 모두 파이프라인 레지스터를 통해 그 필요 단계까지 전달되어야 한다는 것을 알 수 있다.
저장 명령어를 따라가 보면 후속 파이프 단계를 위해 정보를 전달해야 하는 것뿐만 아니라 명령어 실행도 유사하다는 것을 알 수 있다. 다음은 저장 명령어의 다섯 단계이다.
1.
명령어 인출
PC의 주소를 사용하여 메모리에서 명령어를 읽어서 IF/ID 파이프라인 레지스터에 저장한다. 명령어가 판별되기 전에 이 단계가 실행되기 때문에 그림 4.36의 상단 그림은 적재 명령어 뿐만 아니라 저장 명령어에 대해서도 동작한다.
2.
명령어 해독 및 레지스터 파일 읽기
IF/ID 파이프라인 레지스터에 있는 명령어가 레지스터 번호를 공급하여 두 개의 레지스터를 읽고 또한 16비트 수치의 부호를 확장한다.
이들 세 개의 32비트 값들 모두가 ID/EX 파이프라인 레지스터에 저장된다. 적재 명령어를 위한 그림 4.36의 아래 그림은 저장 명령어를 위한 두 번째 단계의 동작도 보여준다.
이 같이 첫 두 단계는 모든 명령어에 의해 실행되는데, 왜냐하면 아직은 명령어 종류를 알기에는 너무 이르기 때문이다.
3.
실행 및 주소 계산
그림 4.39는 세 번째 단계를 보여 주는데 실제 주소(effective address)는 EX/MEM 파이프라인 레지스터에 저장된다.
4.
메모리 접근
그림 4.40의 위쪽 그림은 데이터가 메모리에 써지고 있는 것을 보여준다. 저장되어야 할 데이터를 가지고 있는 레지스터는 앞 단계에서 읽혔고 읽힌 값이 ID/EX에 저장되어 있다는 것을 기억하라.
MEM 단계에서 데이터를 쓸 수 있게 하는 유일한 방법은 EX 단계에서 데이터를 EX/MEM 파이프라인 레지스터에 저장하는 것이다. 방금 전 실제 주소를 EX/MEM에다 저장했던 것과 비슷하다.
5.
쓰기
그림 4.40의 아래 그림은 저장 명령어의 마지막 단계를 보여주고 있다. 이 명령어에 관해서는 쓰기 단계에서는 아무 일도 일어나지 않는다. 저장 명령어를 뒤따르는 명령어가 이미 진행 중이기 때문에 이 명령어들을 더 빨리 수행할 방법은 없다.
따라서 어떤 명령어가 특정 단계에서 아무 일을 하지 않아도 그 단계를 거쳐 가야 한다. 왜냐하면 뒤따르는 명령어들이 최고 속도로 이미 진행 중이기 때문이다.
앞선 파이프 단계에서 뒤의 파이프 단계로 무엇인가를 보내기 위해서는 그 정보가 파이프라인 레지스터에 저장되어야 한다는 것을 저장 명령어는 다시 한 번 보여주고 있다. 그렇지 않으면 다음 명령어가 그 파이프라인 단계에 들어올 때 그 정보는 잃어버리게 된다.
저장 명령어의 경우에 ID 단계에서 읽었던 레지스터 중 하나를 MEM 단계로 전달할 필요가 있는데, 그 값이 MEM 단계에서 메모리에 저장되기 때문이다. 이 데이터가 처음에는 ID/EX 파이프라인 레지스터에 저장되고 나중에 EX/MEM 파이프라인 레지스터에 전달된다.
적재 명령어와 저장 명령어는 두 번째 중요한 점을 보여주고 있다.
즉 데이터패스의 각 구성 요소, 즉 명령어 메모리, 레지스터 읽기 포트, ALU, 데이터 메모리, 레지스터의 각 구성 요소, 즉 명령어 메모리, 레지스터 읽기 포트, ALU, 데이터 메모리, 레지스터 쓰기 포트 등은 한 파이프라인 단계에서만 사용될 수 있다.
그렇지 않으면 구고적 해저드(structural hazard)를 일으키게 될 것이다. 따라서 이들 구성 요소와 그 요소들의 제어는 한 파이프라인 단계와 연관 지을 수 있다.
이제 적재 명령어 설계에서의 문제점을 들추어낼 수 있다. 적재 명령어의 최종 단계에서 어느 레지스터가 변하는가? 좀 더 구체적으로 말하면 어느 명령어가 쓰기 레지스터 번호를 제공하는가?
IF/ID 파이프라인 레지스터에 있는 명령어가 쓰기 레지스터 번호를 제공하는데, 사실 이 명령어는 적재 명령어보다 상당히 뒤에 실행되는 명령어이다.
따라서 적재 명령어에 있는 목적지 레지스터 번호를 간직할 필요가 있다. 저장 명령어가 MEM 단계에서 사용하기 위해 ID/EX의 레지스터 내용은 EX/MEM 파이프라인 레지스터로 전달했듯이, 적재 명령어도 레지스터 번호를 ID/EX에서 EX/MEM을 거쳐 MEM/WB 파이프라인 레지스터로 보내야 WB 단계에서 사용할 수 있다.
레지스터 번호를 전달하는 것을 다른 관점에서 생각할 수도 있다. 파이프라인 데이터패스를 공유하기 위해서는 IF 단계에서 읽은 명령어를 간직해야 한다. 그러므로 각 파이프라인 레지스터는 현 단계나 뒷 단계에서 필요한 명령어 부분을 가지고 있다.
그림 4.41은 올바른 데이터패스를 보여주고 있는데 쓰기 레지스터 번호를 먼저 ID/EX 레지스터로, 그 뒤에는 EX/MEM 레지스터로, MEM/WB 레지스터로 전달한다. 이 레지스터 번호는 WB 단계에 쓰기를 행할 레지스터를 명시하기 위해 사용된다.
그림 4.42는 워드 적재 명령어의 올바른 데이터패스를 하나로 그린 그림인데, 그림 4.36부터 4.38에 이르면서 다섯 단계 전체에서 사용되는 하드웨어를 강조하여 보여주고 있다. 분기 명령어가 예상대로 동작하도록 어떻게 만들 것인가에 대한 설명은 4.8절을 보라.

그림으로 표현하는 파이프라인

파이프라이닝은 이해하기 힘들다. 왜냐하면 많은 명령어들이 매 클럭 사이클에 하나의 데이터패스에서 동시에 실행되기 때문이다. 이해를 돕기 위한 파이프라인 그림에는 두 가지 기본적 유형이 있다.
그림 4.34와 같은 다중 클럭 사이클 파이프라인 다이어그램(multiple clock cycle pipeline diagram)과 그림 4.36에서 그림 4.40까지와 같은 단일 클럭 사이클 파이프라인 다이어그램(single clock cycle pipeline diagram)이 그것이다.
다음 다섯 개의 명령어로 된 코드를 가지고 두 가지 파이프라인 다이어그램 유형을 사용하여 명령어 실행 과정을 보이겠다.
lw $10, 20($1) sub $11, $2, $3 add $12, $3, $4 lw $13, 24($1) add $14, $5, $6
Python
그림 4.43은 이들 명령어들에 대한 다중 클럭 사이클 파이프라인 다이어그램을 보여준다. 시간은 다이어그램이 나와 있는 페이지를 왼쪽에서 오른쪽으로 가로질러 진행하며 명령어는 페이지 위쪽에서 아래쪽으로 진행한다.
이는 그림 4.25에 있는 세탁소 파이프라인과 비슷하다. 파이프라인 단계 표시는 명령어 축을 따라 배치되며 해당 클럭 사이클의 열에 들어간다.
이 같은 스타일로 그려진 데이터패스는 파이프라인의 다섯 단계를 그림으로 나타내고 있지만, 각 파이프 단계의 이름을 쓴 사각형을 사용해도 아무 문제 없다.
그림 4.44는 다중 클럭 사이클 파이프라인 다이어그램의 전통적인 버전을 보여 주고 있다. 그림 4.43은 각 단계에서 사용되는 물리적 자원을 보여 주고 있는 반면에 그림 4.44는 각 단계의 이름을 사용한다.
단일 클럭 사이클 파이프라인 다이어그램은 한 클럭 사이클 동안의 전체 데이터패스의 상태를 나타낸다. 보통 각 파이프라인 단계 위에 이 단계에 있는 명령어 이름을 레이블로 표시하여 파이프라인에 있는 다섯 명령어를 모두 나타낸다.
각 클럭 사이클 동안 파이프라인 안에서 무슨 일이 일어났는지를 구체적으로 보여 주기 위해 이 그림을 사용한다. 특히 연속된 클럭 사이클 동안의 파이프라인 동작을 보여 주기 위해 그룹으로 사용한다. 개략적인 파이프라인 상황을 나타내기 위해서는 다중 클럭 사이클 다이어그램을 사용한다.
단일 클럭 사이클 다이어그램은 다중 클럭 사이클 다이어그램을 수직으로 자른 단면을 보여 주는 셈이므로, 주어진 클럭 사이클에 파이프라인 상에 있는 명령어 각각에 의해 사용되는 데이터패스를 나타내게 된다.
예컨대 그림 4.45는 그림 4.43과 그림 4.44의 클럭 사이클 5에 해당하는 단일 클럭 사이클 다이어그램을 보여준다.

파이프라인 제어

4.3절에서 단일 사이클 데이터패스에 제어를 추가했던 것처럼 파이프라인 데이터패스에 제어를 추가한다. 처음에는 문제를 장밋빛 안경을 통해 보는 것처럼 단순한 설계로 싲가한다.
첫 번째 단계는 기존 데이터패스에 제어선 레이블을 붙이는 것이다. 그림 4.46은 이러한 제어선을 보여준다.
그림 4.17의 간단한 데이터패스용 제어로부터 가능한 한 많은 것을 빌려온다. 특히 똑같은 ALU 제어회로, 분기회로, 목적지 레지스터 번호 멀티플렉서, 제어선을 사용한다.
이 같은 기능들은 그림 4.12, 그림 4.16, 그림 4.18에서 정의되었다. 다음 설명을 더 쉽게 따라갈 수 있게 하기 위해 핵심 정보를 그림 4.47부터 그림 4.49에 다시 보였다.
단일 사이클 구현에서와 같이 매 클럭 사이클마다 PC에 쓰기가 행해지며 따라서 PC를 위한 쓰기 신호는 따로 없다고 가정한다. 같은 논리로 파이프라인 레지스터들(IF/ID, ID/EX, EX/MEM, MEM/WB)을 위한 쓰기 신호가 따로 없다. 왜냐하면 파이프라인 레지스터 역시 매 클럭 사이클마다 쓰기가 행해지기 때문이다.
파이프라인을 위한 제어를 명시하기 위해서는 각 파이프라인 단계 동안의 제어 값들을 정하기만 하면 된다. 각 제어선은 한 파이프라인 단계에서만 활성화되는 구성 요소들과 관련 있기 때문에 제어선을 파이프라인 단계에 따라 다섯 그룹으로 나눌 수 있다.
1.
명령어 인출
명령어 메모리를 읽고 PC 값을 쓰기 위한 제어신호들은 항상 인가되므로 이 파이프라인 단계에는 제어할 것이 없다.
2.
명령어 해독/레지스터 파일 읽기
이전 단계에서와 마찬가지로 매 클럭 사이클마다 같은 일이 일어나기 때문에 설정할 제어선이 없다.
3.
실행/주소 계산
설정할 신호들은 RegDst, ALUOp, ALUSrc이다. 이 신호들은 목적지 레지스터와 ALU 연산을 선택하고 Read data 2와 부호확장된 수치 중 하나를 ALU의 입력으로 선택한다.
4.
메모리 접근
이 단계에서 설정되는 제어선은 Branch, MemRead, MemWrite이다. 이 신호들은 각각 같을 시 분기, 적재, 저장 명령어일 때 설정된다. 제어가 Branch를 인가하고 ALU 결과가 0이 아닌 한 그림 4.48의 PCSrc는 순차적인 다음 주소를 선택한다는 것을 기억하라.
5.
쓰기
두 제어선은 MemtoReg과 RegWrite인데 MemtoReg는 레지스터 파일에 ALU 결과를 보낼 것인가 메모리 값을 보낼 것인가를 결정하며 RegWrite는 선택된 값을 레지스터에 쓰게 하는 신호이다.
데이터패스를 파이프라이닝 하는 것이 제어선의 의미를 바꾸지는 않기 때문에 전과 같은 제어 값을 사용할 수 있다. 그림 4.49는 4.4절에서와 같은 값을 갖지만 9개의 제어선이 파이프라인 단계에 의해 그룹화 되어 있다.
제어를 구현하는 것은 각 단계에서 9개 제어신호 값을 그 명령어에 해당하는 값으로 설정하는 것을 의미한다. 이렇게 하는 가장 간단한 방법은 파이프라인 레지스터를 제어 정보를 포함하도록 확장하는 것이다.
제어선들이 EX 단계에서 출발하기 때문에 제어 정보를 명령어 해독 단계 동안에 생성할 수 있다. 그림 4.50은 명령어가 파이프라인을 흘러 내려가면서 제어신호들이 적당한 파이프라인 단계에서 사용되는 것을 보여준다.
마치 그림 4.41에서 적재 명령어를 위한 목적지 레지스터 번호가 파이프라인을 따라 흘러 내려가는 것과 같다.
그림 4.51은 확장된 파이프라인 레지스터와 해당 단계에 연결된 제어선을 가진 전체 데이터패스를 보여준다.

데이터 해저드: 전방전달 대 지연

그림 4.43에서 4.45까지에 나와 있는 명령어들은 독립적인 관계였다. 즉 어느 명령어도 다른 명령어들에 의해 계산된 결과를 사용하지 않았다. 그러나 4.5절에 데이터 해저드가 파이프라인 실행에서 장애물이라는 것을 보았다. 많은 종속성을 가지고 있는 프로그램을 보자.
sub $2, $1, $3 # Register $2 written by sub and $12, $2, $5 # 1st operand($2) depends on sub or $13, $6, $2 # 2nd operand($2) depends on sub add $14, $2, $2 # 1st($2) & 2nd($2) depend on sub sw $15, 100($2) # Base ($2) depends on sub
Python
마지막 네 개 명령어 모두 첫 번째 명령어의 레지스터 $2의 결과에 종속적이다. 만약 레지스터 $2가 뺄셈 명령어 이전에는 값 10을 가지고 있었고 뺄셈 명령어 이후에는 -20을 가진다면 프로그래머는 레지스터 $2를 참조하는 그 다음 명령어들이 -20을 사용하는 것을 의도했을 것이다.
이 프로그램이 우리 파이프라인 기계에서 어떻게 수행될까? 그림 4.52는 다중 클럭 사이클 파이프라인 표현을 사용하여 이 명령어들의 실행을 보여주고 있다.
현재의 파이프라인 기계에서 이 프로그램의 실행을 보여주기 위해 그림 4.52의 상단에 레지스터 $2의 값을 나타내었다. 이 값은 sub 명령어가 결과 값의 쓰기를 행하는 클럭 사이클 5의 중간에 바뀐다.
sub와 add 간의 해저드는 레지스터 파일 하드웨어의 설계에 의해 해결될 수 있다. 같은 클럭 사이클에 한 레지스터에 대한 읽기와 쓰기가 행해진다면 무슨 일이 일어날까?
쓰기는 클럭 사이클의 앞부분에서 일어나고 읽기는 뒷부분에서 일어난다고 가정한다. 그러면 읽기는 새로 써진 값을 읽게 된다. 따라서 실제 레지스터 파일의 많은 구현이 그렇듯이 이 예에서도 이런 데이터 해저드는 발생하지 않는다.
그림 4.52는 읽기가 클럭 사이클 5(CC 5)나 그 이후에 일어나지 않는 한 레지스터 $2를 읽은 값은 sub 명령어의 결과 값이 아니라는 것을 보여주고 있다.
-20이라는 올바른 값을 갖게 되는 명령어는 add와 sw이다. AND와 OR 명령어는 10이라는 틀린 값을 갖게 된다.
이런 그림을 사용하면 시간 축에서 뒤로 갈 때 그러한 문제가 있다는 것이 자명해진다.
4.5절에서 언급한 것처럼 원하는 결과는 EX 단계의 끝, 즉 클럭 사이클 3의 끝에서 만들어진다. AND와 OR 명령어가 언제 데이터를 필요로 하는가?
EX 단계의 시작인 클럭 사이클 4와 5에서 각각 필요하다. 데이터가 레지스터 파일에서 읽을 수 있게 되기 전이라도 데이터가 가용하자마자 이를 필요로 하는 유닛으로 전방전달하기만 하면 이 코드들을 지연 없이 실행할 수 있다.
그러면 전방전들은 어떻게 동작하는가? 이 절의 나머지에서는 단순호를 위해 EX단계의 연산으로 전방전달하는 문제만을 생각하자. ALU의 연산이나 실제 주소 계산이 그러한 경우이다.
앞선 명령어가 WB 단계에서 쓰기를 하려는 레지스터를 다른 명령어가 EX 단계에서 사용하려고 시도할 때, 실제로는 ALU의 입력으로 그 값이 필요하다는 것을 알 수 있다.
파이프라인 레지스터의 필드에 이름을 붙이면 종속성을 좀 더 자세히 표시할 수 있다. 예컨대 'ID/EX.RegisterRs'는 파이프라인 레지스터 ID/EX에 있는 한 레지스터의 번호, 즉 레지스터 파일의 첫 번째 읽기 포트에 실린 레지스터 번호를 나타낸다.
이름의 첫 번째 부분('.'의 왼쪽 부분)은 파이프라인 레지스터 이름이고, 두 번째 부분은 그 레지스터 필드 이름이다. 이 같은 표기법을 이용하여 두 쌍의 해저드 조건을 표시하면 다음과 같다.
1a. EX/MEM.RegisterRd = ID/EX.RegisterRs 1b. EX/MEM.RegisterRd = ID/EX.RegisterRt 2a. MEM/WB.RegisterRd = ID/EX.RegisterRs 2b. MEM/WB.RegisterRd = ID/EX.RegisterRt
Python
앞의 코드에서 첫 번째 해저드는 레지스터 $2에 관한 것으로 sub, $2, $1, $3의 결과와 and $12, $2, $5의 첫 번째 읽기 피연산자 사이에서 발생한다.
이 같은 해저드는 and 명령어 EX 단계에 있고 앞선 명령어(sub)가 MEM 단계에 있을 때 검출될 수 있다. 즉 해저드 조건 1a를 만족시킨다.
EX/MEM.RegisterRd = ID/EX.RegisterRs = $2
Python

예제) 종속성 검출

앞의 코드에서 종속성을 구분하라.
sub $2, $1, $3 # Register $2 written by sub and $12, $2, $5 # 1st operand($2) depends on sub or $13, $6, $2 # 2nd operand($2) depends on sub add $14, $2, $2 # 1st($2) & 2nd($2) depend on sub sw $15, 100($2) # Base ($2) depends on sub
Python
위에서 언급한 바와 같이 sub-and 관계는 종류 1a 해저드이다. 나머지 해저드는 다음과 가타.
sub-or는 종류 2b 해저드이다.
MEM/WB/RegisterRd = ID/EX.RegisterRt = $2
Python
sub-add의 두 개의 종속성은 해저드가 아니다. 왜냐하면 레지스터 파일이 add가 ID 단계에 있을 때 올바른 데이터를 제공하기 때문이다.
sub와 sw 사이에는 데이터 해저드가 없다. 왜냐하면 sub가 $에 쓴 다음 클럭 사이클에서 sw가 $2를 읽기 때문이다.
어떤 명령어들은 레지스터에 쓰기를 하지 않기 때문에 이 같은 방침은 정확하지 않다. 필요 없을 때에도 전방전달을 하는 경우가 있기 때문이다.
한 가지 해결책은 RegWrite 신호가 활성화되어 있는지 확인하는 것이다. EX 단계와 MEM 단계 동안에 파이프라인 레지스터의 WB 제어 필드를 조사하면 RegWrite 신호가 인가되었는지를 알 수 있다.
또 MIPS의 $0는 항상 상수 0을 가지고 있어서 그 값을 바꿀 수 없다. 파이프라인에 있는 명령어의 목적지가 $0라면 (예컨대 s11 $0, $1, 2) 결과 값을 굳이 전방전달할 필요가 없다.
레지스터 $0로 가는 값은 전방전달하지 않는다면 어셈블리 프로그래머나 컴파일러에게 $0를 목적지 레지스터로 사용하지 말라고 할 필요가 없다. 첫 번째 해저드 조건에 EX/MEM.RegisterRd ≠ 0을 추가하고, 두 번째 조건에 MEM/WB.RegisterRd ≠ 0을 추가하면 위의 조건들은 제대로 작동할 것이다.
이제 해저드를 검출할 수 있으므로 문제의 반은 풀린 것이다. 그러나 아직은 올바른 데이터를 전방전달해야 한다는 문제가 남아 있다.
그림 4.53은 그림 4.52에서와 똑같은 코드에 대하여 파이프라인 레지스터와 ALU 입력 사이의 종속성을 보여 준다. 바뀐 것은 WB 단계가 레지스터 팡리에 쓸 때까지 기다리는 대신, 파이프라인 레지스터에서부터 종속성이 시작된다는 점이다.
파이프라인 레지스터가 전방전달할 데이터를 가지고 있기 때문에 요구한 데이터는 후속 명령어들이 필요한 시간에 맞추어 도착한다.
ID/EX 레지스터뿐만 아니라 어느 파이프라인 레지스터에서라도 ALU 입력을 가져올 수 있다면 적절한 데이터를 전방전달할 수 있다. ALU 입력에 멀티플렉서를 추가하고 적절한 제어를 붙이면 이 같은 데이터 종속성이 존재하더라도 파이프라인을 최고 속도로 실행할 수 있다.
당분간 전방전달할 필요가 있는 명령어는 4개의 R 형식 명령어 add, sub, AND, OR 뿐이라고 가정하자. 그림 4.54는 전방전달을 추가하기 전과 후의 ALU와 파이프라인 레지스터를 확대해 보여준다.
그림 4.55는 ALU 멀티플렉서를 위한 제어선의 값들을 보여주는데, 이를 통해 레지스터 파일 값과 전방전달된 값들 중 하나를 선택한다.
이 같은 전방전달 제어는 EX 단계에서 이루어지는데 ALU 전방전달 멀티플렉서가 이 단계에 있기 때문이다. 따라서 전방전달 여부를 결정할 수 있도록 피연산자 레지스터 번호를 ID 단계에서부터 ID/EX 파이프라인 레지스터를 거쳐 전달해주어야 한다.
rt필드(비트 20:16)은 이미 ID/EX 파이프라인 레지스터에 저장되어 있다. 하지만 전방전달이 추가되기 전까지는 ID/EX 레지스터에 rs 필드를 저장할 필요가 없었다. 따라서 rs필드(비트 25:21)가 ID/EX에 추가되어야 한다.
이제 해저드를 건출하기 위한 제어신호에 대해 서술해 보자.
1.
EX 해저드
if (EX/MEM.RegWrite and (EX/MEM.RegisterRd ≠ 0) and (EX/MEM.RegisterRd = ID/EX.RegisterRs)) ForawrdA = 10 if (EX/MEM.RegWrite and (EX/MEM.RegisterRd ≠ 0) and (EX/MEM.RegisterRd = ID/EX.RegisterRt)) ForawrdB = 10
Python
EX/MEM.RegisterRd 필드는 ALU 명령어의 레지스터 목적지(명령어의 Rd 필드)나 적재 명령어의 레지스터 목적지(명령어의 Rt 필드)라는 것을 기억하라
이 경우에 바로 앞 명령어의 결과를 ALU 입력 중 하나로 전방전달한다. 바로 앞 명령어가 레지스터 파일에 쓰기를 하는 명령어이고 쓰기 레지스터 번호가 ALU 입력 A나 B의 읽기 레지스터 번호와 같다면(레지스터 0은 아니라고 가정) 파이프라인 레지스터 EX/MEM에서 값을 받도록 멀니플렉서를 제어한다.
2.
MEM 해저드
if (MEM/WB.RegWrite and (EX/MEM.RegisterRd ≠ 0) and (MEM/EX.RegisterRd = ID/EX.RegisterRs)) ForawrdA = 01 if (MEM/WB.RegWrite and (EX/MEM.RegisterRd ≠ 0) and (MEM/EX.RegisterRd = ID/EX.RegisterRt)) ForawrdB = 01
Python
위에서 언급한 바와 같이 WB 단계에는 해저드가 없다. 왜냐하면 WB 단계에 있는 명령어가 값을 저장하는 레지스터를 ID 단계에 있는 명령어가 읽는다면 레지스터 파일은 올바른 값을 제공한다고 가정하기 때문이다.
그러한 레지스터 파일은 다른 형태의 전방전달을 하고 있는 셈이지만 이 일은 레지스터 파일 내에서 일어난다.
한 가지 복잡한 것은 WB 단계에 있는 명령어의 결과 값과 MEM 단계에 있는 명령어의 결과 값 모두와 ALU 단계에 있는 명령어의 근원지 피연산자 사이에 데이터 해저드가 일어날 수 있다는 것이다.
예컨대 어떤 벡터를 한 레지스터에서 합한다고 할 때 명령어 코드 모두가 같은 레지스터를 읽고 쓰려고 할 것이다.
add $1, $1, $2 add $1, $1, $3 add $1, $1, $4 ...
Python
이 경우에 결과 값은 MEM 단계로부터 전방전달된다. 왜냐하면 MEM 단계에 있는 결과 값이 더 최근의 것이기 때문이다. 따라서 MEM 해저드에 대한 제어는 다음과 같다.
if (MEM/WB.RegWrite and (EX/MEM.RegisterRd ≠ 0) and not (EX/MEM.RegWrite and (EX/MEM.RegisterRd ≠ 0) and (EX/MEM.RegisterRd ≠ ID/EX.RegisterRS)) and (MEM/EX.RegisterRd = ID/EX.RegisterRs)) ForawrdA = 01 if (MEM/WB.RegWrite and (EX/MEM.RegisterRd ≠ 0) and not (EX/MEM.RegWrite and (EX/MEM.RegisterRd ≠ 0) and (EX/MEM.RegisterRd ≠ ID/EX.RegisterRt)) and (MEM/EX.RegisterRd = ID/EX.RegisterRt)) ForawrdB = 01
Python
그림 4.56은 EX 단계의 명령어를 위한 전방전달을 지원하기 위해 필요한 하드웨어를 보여준다. EX/MEM.RegisterRd 필드는 ALU 명령어의 레지스터 목적지(명령어의 Rd 필드)나 적재 명령어의 레지스터 목적지(명령어의 Rt 필드)이다.

데이터 해저드와 지연

4.5절에서 설명한 바와 같이 전방전달이 해결 못 하는 경우 중 하나는 적재 명령어를 뒤따르는 명령어가 적재 명령어에서 쓰기를 행하는 레지스터를 읽으려고 시도할 때이다. 그림 4.58이 이 같은 문제를 보여주고 있다.
클럭 사이클 4에서 적재 명령어가 데이터를 읽고 있는데 ALU는 이미 그 다음 명령어를 위한 연산을 수행하고 있다. 따라서 적재 명령어 뒤에 이 결과 값을 읽는 명령어가 뒤따라 나오면 누군가가 파이프라인을 지연시켜야 한다.
따라서 전방전달 유닛 외에 해저드 검출 유닛도 필요하다. 이 유닛은 ID 단계에서 동작하여 적재 명령어와 결과 값 사용 사이에 지연을 추가할 수 있도록 한다. 적재 명령어만 검사하면 되므로 해저드 검출 유닛에 대한 제어는 아래와 같은 단 한가지 조건을 갖는다.
if (ID/EX.MemRead and ((ID/EX.RegisterRt = IF/ID.RegisterRs) or (ID/EX.RegisterRt = IF/ID.RegisterRt))) stall the pipeline
Python
첫 번째 줄은 명령어가 적재 명령어인지를 테스트한다. 데이터 메모리를 읽는 유일한 명령어가 적재 명령어이기 때문이다.
다음 두 줄은 EX 단계에 있는 적재 명령어의 목적지 레지스터 필드가 ID 단계에 있는 명령어의 근원지 레지스터인지를 체크한다. 조건이 충족되면 명령어는 한 사이클만큼 지연된다.
한 클럭 사이클 지연 후에는 전방전달 회로가 종속성을 처리할 수 있으므로 실행은 계속 진행된다. (만약 전방 전달이 없다면 그림 4.58의 명령어들은 또 다른 한 사이클만큼의 지연을 필요로 한다)
만약 ID 단계에 있는 명령어가 지연된다면 IF 단계에 있는 명령어 역시 지연된다. 그렇지 않으면 인출된 명령어를 잃게 된다.
이처럼 두 명령어의 진행을 막으려면 PC 레지스터와 IF/ID 파이프라인 레지스터만 변하지 않게 하면 된다. 이 레지스터 값들이 그대로 유지되면 IF 단계에서는 PC 값을 이용하여 똑같은 명령어를 계속 읽고, ID 단계에서는 IF/ID 파이프라인 레지스터의 같은 명령어 필드를 이용하여 rs, rt 레지스터를 계속 읽는다.
다시 세탁소 비유로 돌아가면 세탁기는 같은 옷을 계속 빨고 건조기는 빈 채로 계속 돌리는 것과 같다. EX 단계부터 시작되는 파이프라인의 후반부도 뭔가를 해야 하는데, 하는 일은 아무런 효과도 없는 명령어 nop을 실행하는 것이다.
거품처럼 동작하는 이 같은 nop을 어떻게 파이프라인에 삽입할 수 있을까? 그림 4.49에서 EX, MEM, WB 단계의 9개 제어신호 모두를 인가하지 않으면 (즉 0으로 만들면) '아무것도 하지 않는' nop 명령어를 만들 수 있다.
ID 단계에서 해저드를 찾아내면 ID/EX 파이프라인 레지스터의 EX, MEM, WB 제어 필드 값을 모두 0으로 만들어서 파이프라인에 거품을 집어 넣을 수 있다.
이 제어 값들은 매 클럭마다 앞으로 전진하면서 적절한 효과를 낸다. 모든 제어 값이 0 이므로 레지스터나 메모리에는 쓰기가 전혀 행해지지는 않는다.
그림 4.59는 하드웨어에서 실제로 무슨 일이 일어나는지를 보여준다. AND 명령어와 관련된 파이프라인 실행 자리는 nop으로 바뀌어 AND 명령어 이후의 모든 명령어는 한 사이클씩 지연된다.
수도관에서 공기거품처럼 지연거품은 그 뒤에 있는 것을 모두 지연시키며 한 사이클에 한 단계씩 명령어 파이프를 진행하여 끝에서 빠져나간다.
이 예제에서 해저드는 AND 및 OR 명령어로 하여금 클럭 사이클 3에 했던 것을 클럭 사이클 4에 반복하도록 강요한다. 즉 AND 명령어는 레지스터를 읽고 해독하고 OR 명령어는 명령어 메모리에서 다시 가져오게 된다.
지연의 겉모양은 이렇게 같은 일을 반복하는 것이고, 이 반복의 효과는 AND와 OR 명령어의 시간을 잡아 늘려서 add 명령어의 인출을 지연시키는 것이다.
그림 4.60은 해저드 검출 유닛과 전방전달 유닛이 어떻게 파이프라인에 연결되는지를 강조해서 보여주고 있다.
전과 같이 전방전달 유닛은 ALU 멀티플렉서를 제어하여 범용 레지스터로부터 값을 받지 않고 해당 파이프라인 레지스터로부터 값을 받도록 한다.
해저드 검출 유닛은 PC와 IF/ID 레지스터에 쓰는 것을 제어할 뿐만 안리ㅏ 멀티플렉서가 실제 제어 값과 0 중에서 하나를 선택하도록 한다.
적재, 사용(load-use) 해저드 검사가 참이면 해저드 검출 유닛은 파이프라인을 지연시키고 제어 필드를 0으로 만든다.
좀 더 구체적인 것을 보고 싶다면 4.13절을 참고하라. 이 절에서는 지연을 일으키는 해저드를 갖고 있는 MIPS 코드 예제를 단일 클럭 파이프라인 다이어그램을 사용하여 보여주고 있다.

요점 정리

컴파일러는 대개 하드웨어에 의존해서 해저드를 해결하고 그렇게 함으로써 올바른 실행을 보장받지만, 최고 성능을 위해서는 컴파일러가 파이프라인을 이해해야 한다. 그렇지 않으면 기대하지 않았던 지연이 컴파일된 코드의 성능을 지연시킬 것이다.

제어 해저드

이제까지는 산술연산과 데이터 이동을 포함하는 해저드에만 관심을 두었다. 그러나 4.5절에서 본 바와 같이 분기를 포함하는 파이프라인 해저드가 있다.
그림 4.61에 프로그램이 있는데 분기가 언제 일어날지를 나타내고 있다. 파이프라인을 유지하기 위해서는 매 클럭마다 명령어가 인출되어야 하는데 우리 설계에서는 분기를 할 것인가에 대한 결정이 MEM 파이프라인 단계에 가서 이루어진다.
4.5절에서 설명한 바와 같이 적절한 명령어를 가져오는 것을 결정하는데 있어서의 이 같은 지연을 제어 해저드 또는 분기 해저드라 부른다. 이는 이제까지 다루었던 데이터 해저드와는 다르다.
제어 해저드는 비교적 이해가 쉽고 데이터 해저드만큼 자주 일어나지 않으며 또 데이터 해저드의 전방전달처럼 제어 해저드에 대해서는 별다른 효과적인 방법이 없다. 따라서 좀 더 간단한 방법을 사용한다.

분기가 일어나지 않는다고 가정

4.5절에서 본 바와 같이 분기가 끝날 때까지 지연시키는 것은 너무 느리다. 분기 지연(branch stalling) 보다 좋은 방법으로 많이 쓰이는 것은 분기가 일어나지 않는다고 예측하고 명령어들을 순서대로 계속 실행하는 것이다.
만약 분기가 일어난다면 인출되고 해독되었던 명령어들은 버리고 분기 목적지에서 실행을 계속한다. 반 정도는 분기가 일어나지 않고 명령어를 버리는 비용이 거의 없다면 이 최적화 방법은 제어 해저드의 대가를 반으로 줄인다.
명령어를 버리기 위해서는 적재-사용 데이터 해저드의 경우 지연시키기 위해 했던 것과 같이 원래의 제어 값을 0으로 바꾸면 된다.
차이라고 한다면 분기 명령어가 MEM 단계에 도달했을 때 IF, ID, EX 단계에 있던 3개의 명령어를 바꿔 주어야 한다는 것이다. 적재-사용 지연의 경우에는 ID 단계의 제어 값만을 0으로 바꾸어 파이프라인을 통해 천천히 지나가도록 하였다.
명령어를 버린다는 것은 파이프라인의 IF, ID, EX 단계에 있는 명령어를 쓸어내야(flush) 한다는 것을 의미한다.

분기에 따른 지연 줄이기

분기 성능을 향상시키는 한 가지 방법은 분기가 일어났을 떄의 비용을 줄이는 것이다. 이제까지는 분기 명령어의 경우 다음 PC 값은 MEM 단계에서 선정된다고 가정하였다. 만약 파이프라인에서 분기 결정을 좀 더 앞당겨 할 수 있으면 더 적은 수의 명령어를 없애버려도 된다.
MIPS 구조는 큰 분기 손실을 치르지 않으면서 파이프라이닝할 수 있는 빠른 단일 사이클 분기를 지원하도록 설계되었다. 많은 분기가 간단한 테스트(예컨대 같은지 또는 부호가 어떤지)에만 의존하며 그러한 테스트들은 완전한 ALU 연산을 필요로 하는 것이 아니고 기껏해야 몇 개의 게이트들로 해낼 수 있다는 것을 설계자들은 알아 냈다.
좀 더 복잡한 분기 결정이 필요할 때에는 비교 수행을 위해 ALU를 사용하는 독립된 명령어가 요구되는데 이는 분기를 위해 조건 코드를 사용하는 것과 비슷한 경우이다.
분기 결정을 앞으로 끌어올리려면 분기 목적지 주소를 계산하는 것과 분기 여부를 판단하는 것 두 가지 일이 좀 더 일찍 일어나야 한다. 이 중 쉬운 부분은 분기 주소 계산을 끌어올리는 것이다.
IF/ID 파이프라인 레지스터에는 이미 PC 값과 수치 필드가 들어 있다. 따라서 분기 덧셈기를 EX 단계에서 ID 단계로 옮기기만 하면 된다.
물론 분기 목적지 주소 계산은 모든 명령어에 대해 수행될 것이지만 필요할 때에만 사용될 것이다.
어려운 부분은 분기 여부에 대한 판단이다. 같을 시 분기의 경우에는 같은지 알아보기 위해 ID 단계에서 읽은 두 레지스터 값을 비교해야 한다. 두 레지스터 값을 비트별로 exclusive-OR 하고 그 결과 비티들을 OR 하여서 같은지 검사한다.
분기 테스트를 ID 단계로 옮기는 것은 추가적인 전방전달 유닛과 해저드 검출 하드웨어를 필요로 한다는 것을 의미한다. 왜냐하면 아직 파이프라인 상에 있는 결과 값에 종속적인 분기도 이 같은 최적화를 하면 제대로 동작할 수 있기 때문이다.
예컨대 같을 시 분기(또한 그 역도 성립)를 구현하기 위해서는 결과 값들을 ID 단계에 있는 동등 여부 테스트 회로(equality test logic)로 전방전달할 필요가 있다. 그러나 여기에는 두 가지 복잡한 요인이 있다.
1.
명령어를 해독하고 동등 여부 유닛에의 전방전달이 필요한지 결정하고 또 동등한지 비교하는 일을 ID 단계 동안에 끝내야 한다. 그래야만 명령어가 분기할 경우 PC 값을 분기 목적지 주소로 바꿀 수가 있다.
전에는 ALU 전방전달 회로가 분기 명령어의 피연산자들을 전방전달하였지만 ID 단계에 동등 여부 테스트 유닛을 도입하면 새로운 전방전달 회로가 필요하다.
분기 명령어를 위해 전방전달되는 근원지 피연산자들은 EX/MEM 파이프라인 레지스터나 MEM/WB 파이프라인 레지스터에서 온다.
2.
분기 비교에 사용할 값들은 ID 단계에서 필요하지만, 더 나중에 생성될 수 있기 때문에 데이터 해저드가 일어나거나 지연이 필요하게 될 가능성이 있다.
예컨대 분기 명령어 바로 앞에 있는 ALU 명령어가 분기 비교를 위한 피연산자 중 하나를 생성하면 지연이 요구된다. 왜냐면 ALU 명령어를 위한 EX 단계가 분기 명령어의 ID 사이클보다 뒤에 일어날 것이기 때문이다.
좀 더 확장하면 적재 명령어 바로 뒤에 적재 결과를 사용하는 조건부 분기 명령어가 뒤따라 나오는 경우에는 두 사이클의 지연이 필요하다. 왜냐면 적재 명령어의 결과는 MEM 사이클의 끝에서 나오지만 분기 명령어가 필요로 하는 것은 ID 단계의 시작점이기 때문이다.
이 같은 어려움에도 불구하고 분기 실행을 ID 단계로 옮기는 것은 개선이라고 볼 수 있는데, 이는 분기가 발생하였을 때 단 하나의 명령어, 즉 현재 인출되고 있는 명령어만으로 분기의 손실을 줄일 수 있기 때문이다.
IF 단계의 명령어를 버리기 위해서 IF.Flush라는 제어선을 추가하는데 이 제어선은 IF/ID 파이프라인 레지스터의 명령어 필드를 0으로 만든다. 레지스터를 0으로 만드는 것은 인출된 명령어를 nop으로 바꾸는 것인데, 이 명령어는 상태를 바꾸기 위한 어떤 일도 하지 않는다.

예제) 파이프라인 분기

이 명령어 코드에서 분기가 일어날 때 무슨 일이 생기는지를 보여라. 분기가 일어나지 않는 것으로 파이프라인이 최적화되어 있고 분기 실행을 ID 단계로 옮겼다고 가정하라.
36 sub $10, $4, $8 40 beq $1, $3, 7 # PC-relative branch to 40 + 4 + 7 * 4 = 72 44 and $12, $2, $5 48 or $13, $2, $6 52 add $14, $4, $2 56 slt $15, $6, $7 ... 72 lw $4, 50($7)
Python
그림 4.62는 분기가 일어날 때 무슨 일이 생기는지 보여준다. 그림 4.61과는 달리 분기가 일어났을 때 파이프라인에 거품이 하나만 생긴다.

동적 분기 예측

분기가 일어나지 않는다고 가정하는 것도 분기 예측의 한 가지 방법이다. 이 경우에는 분기가 일어나지 않는다고 예측하는 것이며 예측이 틀렸을 경우에는 파이프라인에 있는 데이터를 쓸어내는 것이다.
단순한 다섯 단계 파이프라인의 경우에는 이러한 방법이 아마도 적당할 것이며, 컴파일러 기반의 예측 방법과 함께 사용할 수 있을 것이다.
파이프라인이 더 깊어지면 분기 실패로 인한 손실이 증가하는데, 이때의 손실은 클럭 사이클 단위로 계산한 것이다. 다중 내보내기 파이프라인의 경우도 분기 손실이 증가하는데, 이때의 손실은 잃어버린 명령어 수로 계산한 것이다.
이 같은 특성을 조합하면 공격적인 파이프라인에서는 단순한 정적 예측 방법은 너무나 많은 성능 손실을 초래할 것이다. 4.5절에서 언급한 바와 같이 좀 더 많은 하드웨어를 사용하여 프로그램 실행 중에 분기를 예측하는 방법을 시도해 볼 수 있다.
한 가지 방법은 이 분기 명령어가 지난번에 실행되었을 때 분기가 일어났는지를 알아보기 위해 명령어 주소를 살펴보는 것이다. 만약 분기가 일어났다면 지난번과 같은 주소에서 새로운 명령어를 가져오도록 한다. 이 기법을 동적 분기 예측(dynamic branch prediction)이라 한다.
이 같은 기법을 구현하는 한 가지 방법은 분기 예측 버퍼(branch prediction buffer) 또는 분기 이력표(branch history table)라고 하는 자료구조를 이용하는 것이다. 분기 예측 버퍼는 분기 명령어 주소의 하위 비트에 의해 인덱스 되는 작은 메모리이다. 메모리는 분기가 최근에 일어났는지 그렇지 않은지를 나타내는 비트를 가지고 있다.
이것은 가장 간단한 종류의 버퍼인데 사실상 예측이 옳은지 그른지는 모른다. 심지어 하위 주소 비트가 같지만 전혀 다른 분기 명령어에 의해 버퍼가 설정되었을 수도 있다.
그러나 그렇다 하더라도 실행의 정확성(correctness)에는 영향을 미치지 않는다. 예측은 단지 맞기를 바라는 힌트이므로 예측된 방향에서 명령어를 가져올 뿐이다.
만일 힌트가 잘못된 것으로 판명되면 잘못 예측된 명령어는 삭제되고 예측 비트를 바꾼 후 올바른 순서의 명령어를 인출하여 실행한다.
이 같은 간단한 1비트 예측 방법은 성능에서 문제점을 가지고 있다. 분기가 거의 항상 일어날지라도 분기가 일어나지 않을 때는 한 번이 아닌 두 번의 잘못된 예측을 할 가능성이 높다. 다음 예는 이같은 딜레마를 보여준다.

예제) 순환문과 예측

분기가 9번 연속해서 일어나고 한 번 일어나지 않는 순환문 분기를 생각해 보자. 이 같은 분기에서 예측의 정확도는 얼마인가? 이 분기를 위한 예측 비트가 예측 버퍼에 있다고 가정하라
안정 상태의 예측 행위는 첫 번째와 마지막 순환문 반복에서 예측을 잘못할 것이다. 마지막 반복에서의 예측 잘못은 예측 비트가 분기가 일어날 것이라고 말해 주기 때문에 피할 수가 없다.
왜냐하면 분기가 이 시점까지 연속해서 9번 일어났기 때문이다. 첫 번째 반복에서의 예측 잘못은 순환문에 대한 마지막 반복의 지난번 실행에서 예측 비트가 반전되어 있기 때문이다.
그 반복을 빠져나갈 때 분기가 일어나지 않았었다. 따라서 실제는 90%의 분기가 일어나지만 예측의 정확도는 80%에 지나지 않는다. (두번의 예측 잘못과 8번의 정확한 예측)
이상적으로는 이 같이 아주 규칙적인 분기에 대한 예측의 정확도는 실제 분기 되는 횟수와 일치해야 한다. 이 같은 약점을 보완하기 위해 흔히 2비트 예측 방법을 사용한다.
2비트 예측 방법에서는 예측이 두 번 잘못되었을 때 예측 값이 바뀐다. 그림 4.63은 2비트 예측 방법을 위한 유한 상태기를 보여 준다.
분기 예측 버퍼는 작은 특수 버퍼로 구현될 수 있는데 이 버퍼는 IF 파이프라인 단계에서 명령어 주소로 접근한다. 분기가 일어난다고 예측되면 PC 값이 알려지자마자 목적지 주소로부터 명령어를 가져온다.
이는 앞서 설명한 바와 같이 ID 단계처럼 이른 시기에 일어날 수도 있다. 분기가 일어나지 않는다고 예측되면 순차 주소에서 명령어를 가져오고 실행이 계속된다. 예측이 잘못된 것으로 판명되면 예측 비트들 값이 그림 4.63에서 보는 바와 같이 바뀐다.

파이프라인 정리

이 장에서는 일상 생활에서 파이프라인의 원리를 보여주는 세탁소에서 시작하였다. 이 같은 비유를 안내 삼아 명령어의 파이프라이닝을 단계별로 설명하였는데 단일 사이클 데이터패스에서 시작하여 파이프라인 레지스터, 전방전달 경로, 데이터 해저드 검출 유닛, 분기 예측 그리고 예외 상황에서 명령어 쓸어내기 등을 추가해 왔다. 그림 4.65는 최종적으로 만들어진 데이터패스와 제어를 보여주고 있다.

예외

제어는 프로세서 설계에 있어서 가장 다루기 어려운 영역이다. 즉 올바르게 동작하고 빠르게 동작하도록 하기에 가장 어려운 부분이다. 제어의 가장 어려운 부분 중 하나가 예외(exception)와 인터럽트(interrupt)를 구현하는 것이다.
이들은 처음에 프로세서 내부로부터 예상치 못했던 사건을 처리하기 위해 만들어졌다. 산술에서의 오버플로가 한 예이다.
같은 메커니즘이 입출력장치로 확장되어 프로세서와의 통신에 사용되게 되었다.
많은 구조에서 또 많은 책의 저자들은 인터럽트와 예외를 구분하지 않고 두 종류의 사건을 지칭하기 위해 오래된 이름인 인터럽트를 사용한다. 예컨대 Intel x86은 인터럽트를 사용한다.
우리는 MIPS의 규약을 좇아서 원인이 내부적인지 외부적인지 구분하지 않고 제어흐름에서의 예기치 못한 변화를 지칭하는데 예외라는 용어를 쓰고, 사건이 외부적인 요인으로 일어날 경우에만 인터럽트라는 용어를 사용한다.
다음은 다섯 가지 상황이 프로세서에 의해 내부적으로 일어나든가 아니면 외부적으로 일어나는 예이다.
기본 보기
Search
사건 종류
근원지
MIPS 용어
입출력 장치 요구
Open
외부
인터럽트
사용자 프로그램의 운영체제 호출
Open
내부
예외
산술 오버플로
Open
내부
예외
정의 안 된 명령어 사용
Open
내부
예외
하드웨어의 오동작
Open
내, 외부
예외 또는 인터럽트
예외 조건을 검출하고 적절한 조치를 취하는 것이 컴퓨터의 최장 타이밍 경로상에 있게 되어 클럭 사이클 시간과 성능을 결정하게 된다.
제어 유닛을 설계할 때 예외에 대해 적절한 관심을 기울이지 않으면 복잡한 구현에다 예외를 추가하려는 노력은 설계를 올바르게 하려는 일을 더욱더 복잡하게 만들 뿐만 아니라 성능을 현저히 저하시킨다.

MIPS 구조의 예외 처리

현재까지의 구현에서 발생할 수 있는 두 가지 종류의 예외는 저으이 안 된 명령어의 실행과 산술 오버플로이다. 다음에 다룰 예외의 예로서 add $1, $2, $1의 산술 오버플로를 사용할 예정이다.
예외가 일어났을 때 컴퓨터가 해야 되는 기본 동작은 문제를 일으킨 명려엉의 주소를 예외 프로그램 카운터(EPC: exception program counter)에 저장하고 어떤 특정 주소에 있는 운영체제로 제어를 옮기는 것이다.
그러면 운영 체제는 알맞는 행동을 취할 수 있는데 이러한 행동에는 사용자 프로그램에 어떤 서비스를 제공한다든지, 오버플로에 대하여 미리 정의된 행동을 취한다든지, 아니면 프로그램의 실행을 중지하고 오류를 보고한다든지 하는 것이 포함된다.
예외 때문에 필요로 했던 행동을 취한 다음에는 운영체제가 프로그램을 끝내든지 아니면 실행을 계속할 수 있다. 실행을 계속할 경우에는 어느 곳에서 실행을 재개해야 하는지를 판단하기 위해 EPC를 사용한다.
운영체제가 예외를 처리하려면 예외를 일으킨 명령어 뿐만 아니라 예외의 원인을 알아야 한다. 예외의 원인을 알기 위해 사용되는 두 가지 주요 방법이 있다.
MIPS 구조에서 사용되는 방법은 Cause 레지스터라 불리는 상태 레지스터를 이용하는데 이 상태 레지스터는 예외의 원인을 나타내는 필드를 가지고 있다.
두 번째 방법은 벡터 인터럽트(vectored interrupt)를 사용하는 것인데 이 방법에서는 제어가 옮겨져야 되는 주소가 예외의 원인에 의해 결정된다. 예컨대 위에 언급한 두 종류의 예외를 처리하기 위해 다음 두 예외 벡터 주소를 정의 한다.
기본 보기
Search
예외 종류
예외 벡터 주소
정의 안 된 명령어
Open
8000 0000(hex)
산술 오버플로
Open
8000 0180(hex)
운영체제는 예외가 시작되는 주소를 보고 그 원인을 안다. 주소는 32바이트씩(8개 명령어씩) 떨어져 있으며 운영체제는 예외의 원인을 기록해야 하고 제한된 처리를 차례대로 한다.
예외가 벡터화 안 되어 있으면 모든 예외에 대해 하나의 시작점이 사용될 수 있으며 운영체제는 이유를 알아내기 위해 상태 레지스터를 해독해야 한다.
앞의 기본적인 구현에 몇 개의 레지스터와 제어신호를 추가하고 제어를 약간 확장하여 예외에 필요한 처리를 수행할 수 있다. MIPS 구조에서 쓰이는 예외 시스템을 구현하고 있다고 가정하자. 단일 진입점은 주소 8000 0180(hex)이다. MIPS 구현에 두 개의 레지스터를 추가할 필요가 있다.
EPC: 예외가 일어났던 명령어의 주소를 보관하기 위해 사용되는 32비트 레지스터(이 레지스터는 예외가 벡터화가 되어도 필요하다)
Cause: 예외의 원인을 기록하는데 사용되는 레지스터. MIPS 구조에서 이 레지스터는 32비트이지만 몇 비트는 현재 사용되지 않는다. 위에서 말한 두 가지 예외 원인을 인코딩하는 5비트 필드가 있다고 가정한다. 즉 10은 정의 안 된 명령어를, 12는 산술 오버플로를 뜻한다고 하자.

파이프라인 구현에서의 예외

파이프라인 구현은 예외를 제어 해저드의 다른 형태로 취급한다.
예컨대 add 명령어가 산술 오버플로를 가진다고 생각하자. 앞 절에서 분기가 일어났을 때 했던 것처럼 add 명령어의 다음 명령어들을 파이프라인에서 쓸어버리고 새로운 주소에서 명령어를 가져와야 한다.
분기가 일어났을 떄 사용했던 것과 같은 방법을 사용할 예정이지만 제어선들의 인가를 해제한다.
잘못된 분기 예측을 다루었을 때 IF 단계의 명령어를 nop으로 바꿈으로써 명령어를 버리는 방법을 보았었다.
ID 단계의 명령어를 버리기 위해서는 ID 단계의 멀티플렉서를 사용하여 제어신호들을 0으로 만듦으로써 지연시킨다. ID.Flush라 불리는 새로운 제어신호는 해저드 검출 유닛의 지연신호와 OR 하여 ID 단계의 명령어를 버린다.
EX 단계의 명령어를 버리기 위해 EX.Flush라는 새로운 신호를 사용한다. 이 신호는 새로운 멀티플렉서가 제어신호들을 0으로 만들게 한다. MIPS 예외 주소인 주소 8000 0180(hex)로부터 명령어를 인출하기 위해서는 PC 멀티플렉서에 입력을 추가하여 8000 0180(hex) 값을 PC로 보낼 수 있게 한다. 그림 4.66이 이같이 수정된 것을 보여준다.
이 예는 예외와 관련된 한 가지 문제점을 지적하고 있다.
만약 명령어의 중간에 실행을 중지시키지 않으면 프로그래머는 레지스터 $1의 원래 값이 오버플로를 일으키도록 했다는 것을 알 수가 없을 것이다. 왜냐하면 $1은 add 명령어의 목적지 레지스터로서 잘못된 영향을 받을 것이기 때문이다.
조심스러운 설계를 하여 오버플로 예외가 EX 단계에 검출되도록 한다. 그렇게 함으로써 EX.Flush 신호를 사용하여 EX 단계의 명령어가 WB 단계에서 결과 값을 쓰지 않도록 할 수 있다. 많은 예외의 경우에는 예외를 일으켰던 명령어가 마치 정상적으로 실행되는 것처럼 실행 완료하기를 요구하고 있다.
이렇게 하는 가장 간단한 방법은 해당 명령어를 쓸어내 버리고 예외가 처리된 후에 그 명령어를 처음부터 다시 싲가하는 것이다.
마지막 단계는 문제를 일으킨 명령어 주소를 예외 프로그램 카운터에 저장하는 것이다. 실제로는 주소+4의 값을 저장하게 된다.
그래서 예외 처리루틴은 저장된 값에서 4를 빼야 한다. 그림 4.66은 예외를 처리하기 위한 분기 하드웨어와 필요한 것들을 포함하는 데이터패스 그림이다.

예제) 파이프라인 컴퓨터에서의 예외

다음과 같은 명령어 코드가 주어진다.
40 sub $11, $2, $4 44 and $12, $2, $5 48 or $13, $2, $6 4C add $1, $2, $1 50 slt $15, $6, $7 54 lw $16, 50($7) ...
Python
예외가 일어낫을 때 호출되는 명령어들은 다음 명령어로 시작된다고 가정한다.
80000180 sw $26, 1000($0) 80000184 sw $27, 1004($0)
Python
add 명령어에서 오버플로 예외가 발생한다면 파이프라인에서 무슨 일이 일어나는지를 보여라
그림 4.67은 add 명령어가 EX 단계에 있을 때부터 시작해서 이 사건을 보여주고 있다. 오버플로가 이 시점에서 검출되어 8000 0180(hex) 값이 PC에 쓰인다. 클럭 사이클 7은 add 명령어와 그 다음 두 개의 명령어를 버리고 예외코드의 첫 번째 명령어가 인출됨을 보여주고 있다. add 다음의 명령어 주소 4C(hex) + 4 = 50(hex)가 EPC에 저장됨에 주목하라
이 절의 앞부분에서 다섯 가지 예외를 언급하였으며 5장에서는 또 다른 예외를 다룰 예정이다.
항상 5개의 명령어가 활성화되어 있기 때문에 예외를 적절한 명령어와 연결 짓는 것은 어려운 일이다. 게다가 한 클럭 사이클에서 여러 개의 예외가 동시에 일어날 수도 있다.
보통의 해결책은 예외에 우선순위를 주어 어떤 것이 먼저 서비스되어야 하는지 결정하기 쉽도록 하는 것이다. 대부분의 MIPS 구현에서는 가장 앞선 명령어가 인터럽트 되도록 하드웨어가 예외를 정렬해 준다.
입출력장치의 요구와 하드웨어 오동작은 특정 명령어와 연관되어 있지는 않다. 따라서 언제 파이프라인을 인터럽트 할 것인가에 대해서는 어느 정도 유연성을 가지고 있다. 그러므로 다른 예외에 사용되는 기법을 사용해도 무난하다.
EPC는 인터럽트당한 명령어의 주소를 갖게되며 MIPS Cause 레지스터는 하나의 클럭 사이클에서의 가능한 모든 예외를 기록하고 있으므로 예외 소프트웨어는 예외를 적절한 명령어와 대응시켜야 한다.
가장 중요한 단서는 어떤 종류의 예외가 어느 파이프라인 단계에서 일어날 수 있는지를 아는 것이다. 예컨대 정의 안 된 명령어는 ID 단계에서 발견되며 운영체제를 부르는 것은 EX 단계에서 일어난다.
예외는 Cause 레지스터에 주십된다. 이를 근거로 하여 일단 앞서 일어난 예외가 서비스된 다음에는 늦게 일어난 예외에 근거하여 하드웨어가 인터럽트할 수 있다.
예외가 기대한 대로 처리되도록 하드웨어와 운영체제가 함께 협력하여 동작해야 한다.
일반적으로 하드웨어가 맡은 부분은 예외가 일어난 명령어를 중간에서 중지시키고, 이전 명령어의 실행을 모두 끝내고, 뒤따라 나오는 모든 명령어는 쓸어버리고, 예외의 원인을 나타내도록 레지스터를 설정하고, 예외가 일어난 명령어의 주소를 저장하고, 미리 약속된 주소로 점프하는 일이다.
운영체제가 맡은 부분은 예외 원인을 살펴 적절히 행동하는 것이다. 정의 안 된 명령어, 하드웨어 오동작, 산술 오버플로 예외의 경우에 운영체제는 일반적으로 프로그램 실행을 취소하고 원인을 나타내는 메시지를 출력한다.
입출력 장치 요구나 운영체제 서비스 호출의 경우엔느 프로그램의 상태를 저장하고 원하는 일을 수행한 후 원래의 프로그램을 복원하여 실행을 계속한다.
입출력 장치 요구의 경우에는 입출력을 요구하였던 프로그램을 재개하기 전에 다른 프로그램을 실행하도록 할 수 있다. 왜냐하면 그 프로그램은 입출력이 끝날 때까지는 진행 시킬 수 없는 경우가 흔하기 때문이다. 이것이 프로그램의 상태를 저장하고 복원하는 능력이 매우 중요한 이유이다.
예외들 중에서 가장 중요하면서도 자주 사용하는 것 중의 하나는 페이지 부재와 TLB 예외처리이다. 5장에서 이러한 예외와 처리에 대해 더 자세히 다룬다.

명령어를 통한 병렬성

파이프라이닝은 명령어들 사이의 병렬성을 이용한다. 이 같은 병렬성을 명령어 수준 병렬성(ILP: instruction-level parallelism)이라 한다. 명령어 수준 병렬성의 양을 증가시키는 두 가지 기본적인 방법이 있다.
첫 번째 방법은 파이프라인의 깊이를 증가시켜 더 많은 명령어들을 중첩시키는 것이다.
앞의 세탁소 비유에서 세탁기 사이클이 다른 것에 비해 길다면, 세탁기를 3개의 기계로 나눌 수 있다. 한 기계가 하던 세탁, 헹굼, 탈수의 세 단계를 각각 다른 기계로 나눌 수 있다. 그렇게 하면 네 단 계 파이프라인에서 여섯 단계 파이프라인으로 바뀐다.
최고 성능을 얻기 위해서는 나머지 단계들을 다시 균형을 잡아서 단계들이 같은 길이를 갖도록 할 필요가 있다. 이는 프로세서나 세탁소에서 다 마찬가지이다. 추구되는 병렬성의 양은 늘어난다. 왜냐하면 더 많은 연산들이 중첩되기 때문이다. 클럭 사이클이 더 짧아질 수 있기 때문에 성능은 더 좋아질 가능성이 있다.
두 번째 방법은 컴퓨터 내부의 구성 요소들을 여러 벌 갖도록 하여 매 파이프라인의 단계에서 다수의 명령어를 내보낼 수 있도록 하는 것이다. 이 같은 기법의 일반적인 이름은 다중 내보내기(multiple issue)이다.
말하자면 다중 내보내기 세탁소에는 세탁기가 3대, 건조기가 3대있다. 같은 시간 안에 세탁물을 접어서 다른 곳에 옮겨 놓는 것도 세 배 더 해야 하므로 보조원도 더 많이 고용해야 할 것이다.
모든 기계를 계속 바쁘도록 만들고 일거리를 다음 파이프라인 단계로 넘기기 위해서 해야 되는 일이 늘어난다는 것이 단점이다.
매 단계마다 다수의 명령어를 내보내면 명령어 실행 속도가 클럭 속도보다 빨라질 수 있다. 다른 말로 하면 CPI가 1보다 작아질 수 있다. CPI 값이 1보다 작아지면 척도를 뒤집어서 IPC, 즉 클럭 사이클당 명령어 수(instruction per clock cycle)를 사용하기도 한다.
따라서 4 GHz의 네 명령어 다중 내보내기 마이크로프로세서는 초당 최대 160억개의 명령어를 실행할 수 있다. 이 경우에는 0.25 CPI 또는 4 IPC를 갖게 된다.
다섯 단계 파이프라인을 가정하면 그러한 프로세서는 주어진 시간에 20개의 명령어를 동시에 실행하고 있다. 오늘날의 고성능 프로세서들은 매 클럭 사이클에 3-6개의 명령어를 내보내려 노력한다. 그저 그런 컴퓨터도 2 IPC를 갖는 것을 목표로 한다.
그러나 동시에 실행될 수 있는 명령어 종류에 제약이 있고 종속성이 생기면 할 수 있는 일에 대해서도 많은 제약이 있다.
다중 내보내기 프로세서를 구현하는데 두 가지 주요 방법이 있는데 주된 차이는 컴파일러가 할 일과 하드웨어가 할 일을 나누는 방법에 있다.
일을 어떻게 나누냐는 것 자체가 여러 가지 결정들이 정적으로 이루어질 것이냐(즉 컴파일 시에) 아니면 동적으로 이루어질 것이냐(즉 실행 중에)를 결정하기 때문에 이러한 방법은 떄로는 정적 다중 내보내기(static multiple issue)와 동적 다중 내보내기(dynamic multiple issue)라 불린다.
두 가지 방법 모두 더 많이 사용되는 다른 이름이 있지만, 이 이름들은 더 명확하지 않거나 제한적이다.
두 방법은 다중 내보내기 파이프라인이 다루어야 할 두 가지 중요한 문제를 서로 다르게 해결한다.
1.
명령어로 내보내기 슬롯(issue slot)을 채우기
주어진 클럭 사이클에 얼마나 많은 명령어를 내보내며 또 어떤 명령어들을 내보낼 것인지 프로세서는 어떻게 결정할까?
대부분의 정적 내보내기 프로세서인 경우 이 같은 절차는 적어도 부분적으로는 컴파일러에 의해 처리된다. 동적 내보내기 설계에서는 컴파일러가 명령어의 순서를 다중 내보내기에 유리하게 미리 바꾸어서 내보내기율을 개선할 수 있게 도와주기도 하지만, 보통 이 문제를 프로세서가 실행 중에 처리한다.
2.
데이터 해저드와 제어 해저드의 처리
정적 내보내기 프로세서에서는 데이터 해저드와 제어 해저드의 전부 또는 일부를 컴파일러가 정적으로 처리한다. 반면에 대부분의 동적 내보내기 프로세서는 실행 시간에 동작하는 하드웨어 기법을 이용하여 적어도 일부 종류의 해저드를 없애려고 노력한다.
이 두 가지가 서로 다른 방법이라고 말하기는 하지만, 실제 기법에서는 한 방법이 다른 방법에 차용되는 경우가 많기 때문에 어느 방법도 완전히 순수하다고 말할 수는 없다.

추정의 개념

더 많은 ILP를 찾아내고 이용하는 중요한 방법 중 하나는 추정(speculation)이다. 예측이라는 개념을 기반으로 하여 추정은 컴파일러나 프로세서가 명령어의 특성에 대해 추측하도록 허락하여 이 명령어에 종속적일 수 있는 다른 명령어들의 실행을 시작할 수 있게 하는 방법이다.
예컨대 분기 명령어의 결과를 추정한다면 분기 명령어 뒤의 명령어들이 일찍 실행될 수 있다. 또 다른 예는 적재 명령어 바로 앞의 저장 명령어가 같은 주소를 참조하지 않는다고 추정하여 적재 명령어가 저장 명령어보다 먼저 실행될 수 있게 하는 것이다.
추정 기법의 어려운 점은 추정이 잘못될 수 있다는 것이다. 따라서 어떠한 추정 기법도 추정이 올바른지 체크할 방법과 추정해서 실행했던 명령어들을 되돌리거나 아니면 그 효과를 취소하는 방법을 포함해야 한다. 이 같은 취소 능력에 대한 구현은 추정을 지원하는 프로세서가 더 높은 복잡도를 갖게 한다.
추정은 컴파일러에서 이루어질 수도 있고 하드웨어가 할 수도 있다. 예컨대 컴파일러가 추정을 통해 명령어를 재정렬해서 어떤 명령어를 분기 명령어 너머로 또는 적재 명령어를 저장 명령어 너머로 옮길 수 있다. 프로세서 하드웨어는 이 절의 뒤에서 설명할 기법들을 사용하여 실행 시에 이와 같은 변환을 수행할 수 있다.
그러나 잘못된 추정에 대한 회복 방법은 다르다. 소프트웨어로 추정하는 경우에 컴파일러는 추정의 정확성을 체크할 명령어들을 추가하고 추정이 잘못되었을 때 사용할 오류 수정 루틴을 제공한다.
하드웨어 추정인 경우 프로세서는 추정 결과가 더 이상 추정이 아니라는 것을 알 때까지 추정 결과를 버퍼링하는 것이 보통이다. 추정이 옳다면 버퍼의 내용을 레지스터나 메모리에 씀으로써 명령어 실행이 완성된다.
만약 추정이 틀렸으면 하드웨어는 버퍼 내용을 쓸어버리고 올바른 명령어 순서를 다시 실행한다.
추정은 또 다른 문제가 생길 수 있는 가능성을 야기한다. 어떤 명령어에 추정을 하면 전에는 없었던 예외가 발생할 수 있다.
예컨대 적재 명령어가 추정에 의해 다른 위치로 옮겨졌는데, 추정이 잘못되었을 경우에는 이 명령어가 사용하는 주소가 불법 주소가 된다고 가정하자. 그러면 일어나지 말아야 할 예외가 일어날 수 있다.
이 적재 명령어가 추정된 것이 아니라면 이 예외는 반드시 일어나야 된다는 사실 때문에 문제는 더 복잡해진다. 컴파일러 기반의 추정에서는 이러한 예외가 정말 일어나야 한다는 것이 확실해질 때까지 무시할 수 있게 해 주는 특별 추정 지원을 추가함으로써 이 문제를 피할 수 있다.
하드웨어 기반 추정에서는 예외를 버퍼링해 두었다가, 예외를 일으킨 명령어가 추정 상태에서 벗어나 실행을 완료할 준비가 되면 이때 예외를 일으키고 정상적인 예외 처리를 진행한다.
추정이 올바르게 이루어지면 성능이 향상되고 추정이 잘못되면 성능이 감소하기 떄문에 추정을 언제 하는 것이 좋은지 결정하는데 막대한 노력을 기울여야 한다.

정적 다중 내보내기

모든 정적 다중 내보내기 프로세서는 컴파일러가 명령어들을 묶고 해저드를 처리하는 일을 도와주도록 사용한다.
정적 내보내기 프로세서에서 같은 클럭 사이클에 내보내지는 명령어의 묶음 —내보내기 패킷(issue packet)이라 한다— 을 여러 개의 연산자를 갖는 큰 명령어 하나로 생각할 수 있다.
이 같은 관점은 비유 이상의 의미를 갖는다. 정적 다중 내보내기 프로세서는 일반적으로 주어진 클럭 사이클에 같이 나갈 수 있는 명령어 조합에 제한이 있기 때문에, 내보내기 패킷을 미리 정의된 필드에 여러 연산자가 있는 단일 명령어로 보는 것이 유용하다.
이 같은 관점이 이 접근 방법에 붙은 원래의 명칭 VLIW(Very Long Instruction Word)의 유래이다.
대부분의 정적 내보내기 프로세서들은 컴파일러가 데이터 해저드와 제어 해저드를 처리하는데 어느 정도의 책임을 지도록 한다. 컴파일러의 책임은 모든 해저드를 줄이거나 막기 위한 정적 분기 예측과 코드 스케쥴링을 포함한다.
더 공격적으로 이런 기술을 사용하는 프로세서들을 설명하기 전에 MIPS 프로세서의 단순한 정적 내보내기 버전을 살펴보자.

예: MIPS 명령어 집합 구조의 정적 다중 내보내기

정적 다중 내보내기의 맛을 보기 위하여 간단한 2개 명령어 내보내기 MIPS 프로세서를 살펴본다. 이 프로세서에서 명령어 중 하나는 정수형 ALU 연산이나 분기 명령어가 될 수 있으며 다른 명령어 하나는 적재 명령어나 저장 명령어가 될 수 있다.
이러한 설계는 몇몇 임베디드 MIPS 프로세서에서 사용되고 있는 것과 같다. 사이클당 두 개의 명령어를 내보내려면 명령어들을 64비트 단위로 인출하고 해독할 수 있어야 한다.
많은 정적 다중 내보내기 프로세서와 모든 VLIW 프로세서에서는 명령어 해독과 명령어 내보내기를 단순화하기 위해 동시에 내보내는 명령어의 레이아웃에 제한을 둔다.
이 예에서는 ALU나 분기 명령어가 먼저 나오도록 해서 명령어 두 개를 짝짓고 64비트 경계에 정렬되도록 한다. 두 명령어 중 하나를 사용할 수 없으면 nop으로 대체해야 한다.
따라서 명령어는 항상 쌍으로 내보내기가 행새지며 이 중 하나는 nop일 가능성이 있다. 그림 4.68은 명령어가 파이프라인에 쌍으로 들어가면 어떻게 보이는가를 알려주고 있다.
정적 다중 내보내기 프로세서는 발생 가능성이 있는 데이터 해저드와 제어 해저드를 어떻게 다루느냐에 따라 달라진다.
어떤 설계에서는 모든 해저드를 제거하고 코드를 스케쥴링하고 nop을 삽입하여 코드가 해저드 검출이나 하드웨어가 만드는 지연을 필요로 하지 않고 잘 실행되도록 하는 모든 책임을 컴파일러가 지게 한다.
다른 설계에서는 하드웨어가 2개 내보내기 패킷 사이의 데이터 해저드를 검출하고 지연을 생성하는 반면, 컴파일러는 명령어 쌍 안에서 종속성이 생기지 않게 하는 일을 책임지게 한다.
그렇더라도 해저드는 일반적으로 종속적인 명령어가 들어 있는 내보내기 패킷 전체를 지연시킨다. 소프트웨어가 모든 해저드를 처리하든지 혹은 서로 다른 내보내기 패킷 사이의 해저드 일부만을 감소시키든지 간에, 외형상 커다란 명령어 하나가 복수의 연산을 수행하는 것으로 보는 것이 타당하다. 우리는 이 예에서 후자의 방법을 택한다.
ALU 명령어와 데이터 전송 명령어를 병렬로 내보내기 위해서는 일반적인 해저드 검출 회로와 지연 회로 이외에 추가로 필요한 첫 번쨰 하드웨어가 레지스터 파일의 추가 포트이다(그림 4.69 참조)
한 클럭 사이클에 ALU 연산을 위해 두 레지스터를 읽어야 되고 저장 명령어를 위해 두 레지스터를 더 읽어야 되며, ALU 연산을 위해 하나의 쓰기 포트, 또 적재 명령어를 위해 하나의 쓰기 포트가 필요하다.
ALU는 ALU 연산에 묶여 있기 때문에 데이터 전송을 위한 실제 주소를 계산하기 위해서는 독자적인 덧셈기가 필요하다. 이 같은 추가 자원 없이는 2개 내보내기 파이프라인은 구조적 해저드에 의해 방해를 받는다.
분명히 이 같은 2개 내보내기 프로세서는 2배까지 성능을 높일 수 있다. 그러나 이를 위해서는 두 배의 명령어가 실행 중 중첩되어야 하고, 이러한 추가적 중첩은 데이터 해저드나 제어 해저드에 의한 성능 저하를 증가시킨다.
예컨대 단순한 다섯 단계 파이프라인에서 적재 명령어는 한 클럭 사이클의 사용 지연(use latency)을 가지고 있는데 이는 한 명령어가 지연 없이 결과를 사용하는 것을 방해한다.
2개 내보내기 다섯 단계 파이프라인에서 적재 명령어의 결과는 다음 클럭 사이클에서 사용될 수 없다. 이것은 다음 두 개 명령어가 지연 없이는 적재 결과를 사용할 수 없다는 것을 의미한다.
더구나 단순한 다섯 단계 파이프라인에서는 사용 지연이 없었던 ALU 명령어도 이제는 1개 명령어의 사용 지연을 갖게 된다. 왜냐하면 연산 결과가 쌍으로 묶인 적재 명령어나 저장 명령어에서 사용될 수 없기 때문이다.
다중 내보내기 프로세서에서 가능한 병렬성을 효과적으로 추구하기 위해서는 좀 더 의욕적인 컴파일러나 하드웨어 스케쥴링 기법이 요구되고 정적 다중 내보내기는 컴파일러가 이러한 역할을 해 주기 요구한다.

예제) 간단한 다중 내보내기 코드 스케쥴링

MIPS용 정적 2개 내보내기 파이프라인에서는 아래와 같은 순환문이 어떻게 스케쥴링 되는가?
Loop: lw $t0, 0($s1) # $t0 = array element addu $t0, $t0, $s2 # add scalar in $s2 sw $t0, 0($s1) # store result addi $s1, $s1, -4 # decrement pointer bne $s1, $zero, Loop # branch $s1 != 0
Python
가능한 한 많은 파이프라인 지연을 피하도록 명령어를 재정렬하라. 예측 분기가 사용되고 제어 해저드는 하드웨어에 의해 처리된다고 가정한다.
첫 세 개의 명령어에 데이터 종속성이 있고 마지막 두 개의 명령어 사이에 역시 데이터 종속성이 있다. 그림 4.70은 이 명령어를 위한 가장 좋은 스케쥴을 보여 주고 있다.
단 하나의 명령어 쌍 만이 내보내기 슬롯 두 개 모두를 사용하는 것을 알 수 있다. 따라서 순환문 반복에 네 클럭이 걸린다. 즉 5개 명령어를 실행하는데 네 클럭 사이클이 걸린다. 따라서 가장 좋은 경우에는 0.5 CPI를 갖는데 반해 이 경우에는 0.8 CPI라는 실망스러운 값을 갖게 된다. IPC로 말하면 가장 좋은 경우가 2.0인데 반해 이 경우는 1.25의 IPC 값을 갖는다.
CPI나 IPC로 계산할 때 nop은 유용한 명령어로 취급하지 않는다. 유용한 명령어로 취급하면 CPI 값은 좋아지지만 성능은 좋아지지 않는다.
순환문에서 좀 더 좋은 성능을 얻기 위한 한 가지 중요한 컴파일러 기법은 순환문 펼치기(loop unrolling)이다. 이름이 암시하듯이 순환문 몸체를 여러 벌 만드는 기술이다. 펼치기를 한 후 서로 다른 방복에 속하는 명령어들을 중첩시킴으로써 가용한 ILP가 더 많아진다.

예제) 다중 내보내기 파이프라인을 위한 순환문 펼치기

위 예제에서 순환문 펼치기와 스케쥴리잉 얼마나 잘 동작하는지 보자. 순환문 인덱스는 4의 배수라고 가정한다.
순환문을 지연 없이 스케쥴링하기 위해서는 순환문 본체를 네 벌 만들 필요가 있다. 순환문 펼치기를 하고 불필요한 순환문 오버헤드 명령어를 없애면 순환문은 4개의 lw, add, sw와 한 개의 addi, bne를 가지고 있다. 순환문 펼치기를 한 후 스케쥴링 한 코드가 그림 4.71에 나와 있다.
펼치기 과정 도중 컴파일러는 추가적인 레지스터들($t1, $t2, $t3)을 도입했다. 이런 과정 —레지스터 재명명(register renaming)이라 함— 의 목적은 진정한 데이터 종속성은 아니지만 잠재적 해저드의 원인이 되거나 컴파일러가 코드를 유연하게 스케쥴링 하는 것을 방해하는 종속성을 없애자는 것이다.
$t0만을 사용하여 펼치기를 한 코드가 어떻게 보이는지를 생각해 보자. lw $t0, 0($s1), addu $t0, $t0, $s2가 여러번 나타나고 그 뒤에 sw $t0, 4($s1)가 나올 것이다.
그런데 이 코드는 $t0를 사용했음에도 불구하고 실제로는 완전히 독립적인 코드이다. 어떤 데이터 값도 한 명령어 쌍과 다른 명령어 쌍 사이를 흘러가지 않는다. 이것이 소위 반종속성(antidependence) 또는 이름 종속성(name dependence)이다. 이것은 실제 데이터 종속성이라기보다 순전히 하나의 이름을 계속 사용함으로써 강요되는 순서이다.
순환문 펼치기 과정에서 레지스터들을 재명명함으로써 독립적으로 된 명령어들을 컴파일러가 쉽게 옮길 수 있게 하여 이 코드를 좀 더 잘 스케쥴링 하도록 해준다. 재명명 과정은 이름 종속성만 없애고 진정한 종속성은 유지한다.
이제는 순환문 14개 명령어 중에서 12개 명령어가 쌍으로 실행된다는 것을 알 수 있다. 4번의 순환문 반복에 여덟 클럭, 즉 반복당 두 클럭이 걸리므로 CPI 값은 8/14 = 0.57이 된다.
순환문을 펼치고 스케쥴링한 후 2개 내보내기를 하면 거의 2배의 성능 향상을 얻을 수 있는데 일부는 순환문 제어 명령어들을 줄인데 기인하고 또 일부는 2개 내보내기 실행을 한 결과이다. 이 같은 성능 향상을 위해 지불하는 대가는 임시 레지스터를 하나가 아닌 네 개나 사용해야 하고 코드 크기가 상당히 증가한다는 것이다.

동적 다중 내보내기 프로세서

동적 다중 내보내기 프로세서는 수퍼스칼라(super-scalar) 프로세서 혹은 단순히 수퍼스칼라라고도 한다. 제일 간단한 수퍼스칼라 프로세서는 명령어를 순차대로(in-order) 내보내고 주어진 클럭 사이클에 몇 개의 명령어를 내보낼지를 결정한다.
분명히 이런 프로세서에서 좋은 성능을 얻기 위해서는 컴파일러가 명령어를 스케쥴링하여 종속성 있는 명령어들의 위치를 멀리 떨어뜨리고 그렇게 해서 명령어 내보내기율을 증가시켜야 한다.
그러한 컴파일러 스케쥴링을 하더라도 단순한 수퍼스칼라 프로세서는 VLIW 프로세서와 중요한 차이가 있다. 즉 스케쥴링을 했든 안 했든 상관없이 코드는 올바르게 실행되도록 하드웨어에 의해 보장된다는 것이다.
더구나 컴파일된 코드는 내보내기율이나 프로세서의 파이프라인 구조와는 상관없이 항상 올바르게 동작한다. 어떤 VLIW 설계에서는 이렇지는 않다. 서로 다른 프로세서 모델로 옮겨 갈 때는 재컴파일이 필요하다.
또 다른 정적 내보내기 프로세서의 경우 구현이 달라지면 코드가 올바르게 실해오디기는 하지만 성능이 너무 저하되기 때문에 실제적으로는 재컴파일하는게 필요하다.
많은 수퍼스칼라 프로세서는 동적 내보내기를 결정하는 기본 틀을 확장하여 동적 파이프라인 스케쥴링(dynamic pipeline scheduling)을 포함하도록 한다.
동적 파이프라인 스케쥴링은 해저드와 지연은 피하면서 주어진 클럭 사이클에 어떤 명령어를 실행할 것인지 선택한다. 데이터 해저드를 피하는 간단한 예를 가지고 시작하자. 다음과 같은 명령어 코드를 생각해 보자.
lw $t0, 20($2) addu $t1, $t0, $t2 sub $s4, $s4, $t3 slti $t5, $s4, 20
Python
여기서 sub 명령어는 실행될 준비가 되어 있지만 이 명령어들은 lw와 addu가 먼저 끝날 때까지 기다려야 되는데 메모리가 느리다면 많은 클럭 사이클이 걸릴 수도 있다. 동적 파이프라인 스케쥴링은 그러한 해저드를 완전히 혹은 부분적으로 피할 수 있게 해준다.

동적 파이프라인 스케쥴링

동적 파이프라인 스케쥴링은 다음에 어떤 명령어를 실행할 것인가를 선택하고 지연을 피하기 위해 명령어들을 재정렬할 수도 있다.
그러한 프로세서에서 파이프라인은 세 개의 주요 유닛으로 나누어지는데 명령어 인출 및 내보내기 유닛, 다수의 가능 유닛(2013년 고성능 컴퓨터 설계에서는 12개 이상임), 결과 쓰기 유닛(commit unit)이 그것이다. 그림 4.72는 이 같은 모델을 보여주고 있다.
첫 번째 유닛은 명령어를 가져오고 해독하고 각가그이 명령어를 실행 단계의 해당 기능 유닛에 보낸다. 각 기능 유닛은 대기영역(reservation station)이라 불리는 버퍼를 갖기ㅗ 있는데 이 대기영역은 피연산자와 연ㅅ나자를 가지고 있다.
버퍼에 필요한 모든 피연산자가 준비되고 실행할 기능 유닛이 준비가 되어 있으면 결과가 계산된다. 결과가 완료되면 이 결과는 결과 쓰기 유닛 뿐만 아니라 이 특정한 결과를 기다리고 있는 대기영역에 보내진다.
결과 쓰기 유닛에서는 결과 값을 버퍼에 두었다가 안전하다고 생각이 들 때 결과 값을 레지스터 파일이나 메모리(저장 명령어의 경우)에 쓴다.
결과 쓰기 유닛에 있는 이 버퍼는 재정렬 버퍼(reorder buffer)라고 불리는데 전방전달 회로가 정적 스케쥴 파이프랑니에서 하였던 것과 같은 방법으로 피연산자들을 제공하는데 사용된다.
일단 결과 값이 레지스터 팡리에 써지면 정상적인 파이프라인에서와 같이 레지스터 파일로부터 직접 읽을 수 있다.
피연산자를 대기영역에 버퍼링하는 것과 결과 값을 재정렬 버퍼에 임시 저장하는 것을 같이 사용하면 이것이 바로 레지스터 재명명의 한 종류이다. 지난번 순환문 펼치기 예제에서 컴파일러가 사용했던 것도 레지스터 재명명의 일종이다. 이것이 개념적으로 어떻게 동작하는지 알기 위해 다음 단계를 생각해 보자.
1.
명령어가 내보내질 때 명령어는 해당 기능 유닛의 대기영역으로 복사된다.
피연산자 중 하나가 레지스터 파일이나 재정렬 버퍼에 있으면 이 피연산자는 즉시 대기영역으로 복사된다.
명령어는 모든 피연산자와 실행 유닛이 사용 가능할 때까지 버퍼링된다. 명령어를 내보낼 때 피연산자의 레지스터 복사본은 더 이상 필요 없으며 만약 해당 레지스터에의 쓰기가 일어났다면 그 값에 대해 중복 쓰기가 일어날 수도 있다.
2.
만약 피연산자가 레지스터 파일이나 재정렬 버퍼에 없다면 기능 유닛에 의해 생성될 때까지 기다려야 한다.
결과를 만들어 낼 기능 유닛의 이름이 추적된다. 그 기능 유닛이 결국 결과를 만들면 레지스터를 우회하여 기능 유닛에서 기다리고 있는 대기영역으로 직접 복사된다.
이 같은 단계로 레지스터 재명명을 구현하기 위해 재정렬 버퍼와 대기영역이 효과적으로 사용된다.
개념적으로는 동적 스케쥴 파이프라인을 프로그램의 데이터 흐름 구조를 분석하는 것으로 생각할 수 있다. 프로세서는 프로그램의 데이터 흐름 순서를 유지하는 어떤 순서에 따라 명령어를 실행한다.
이 실행 형태를 비순차 실행(out-of-order execution)이라 부른다. 왜냐하면 명령어는 인출되어 온 순서와 다르게 실행될 수 있기 때문이다.
프로그램이 단순하게 순차 실행되는 파이프라인에서 실해오디는 것처럼 만들려면 명령어 인출 및 해독 유닛이 명령어들을 순서대로 내보내 주어야 하고 (이 경우 종속성 추적이 가능하게 된다) 쓰기 유닛은 프로그램 인출 순서대로 결과를 레지스터나 메모리에 써야 한다.
이 같은 보수적인 방식은 순차 결과 쓰기(in-order commit)라 불린다. 따라서 만약 예외가 일어난다면 컴퓨터는 마지막으로 실행되었던 명령어를 가리키게 되고 예외를 일으킨 명령어 이전 명령어에 의해 쓰기가 되었던 레지스터들만이 갱신된다.
파이프랑니의 전단부, 즉 명령어 인출 및 내보내기 부분과 후단부 즉 결과 쓰기 부분은 순서대로 실행되지만 기능 유닛들은 필요한 데이터가 가용하면 언제나 실행을 자유롭게 시작할 수 있다. 오늘날 모든 동적 스케쥴과 파이프라인은 순서대로 결과 쓰기를 사용한다.
동적 스케쥴링은 흔히 하드웨어 기반의 추정을 포함하도록 확장된다. 특히 분기의 결과에 대해서는 더더욱 그러하다. 분기의 방향을 예측함으로써 동적 스케쥴 프로세서는 예측한 경로를 따라 명령어 인출과 실행을 계속할 수 있다.
명령어들은 순서대로 결과를 쓰기 때문에, 예측한 경로의 어떠한 명령어도 결과를 쓰기 전에 분기 예측의 정확성 여부를 판단할 수 있다.
추정 동적 스케쥴 파이프라인도 적재 주소에 대한 추정을 할 수 있는데, 이는 적재-저장 재정렬을 하게 해주고 결과 쓰기 유닛으로 하여금 올바르지 않은 추정을 피하게 해준다.
다음 절에서는 Intel Core i7 설계에서 추정 동적 스케쥴링을 어떻게 사용하였는지 알아보자.
컴파일러가 데이터 종속성이 있는 명령어들 주변의 코드를 스케쥴링 할 수 있다면 왜 수퍼스칼라 프로세서는 동적 스케쥴링을 사용할까? 여기에는 세 가지 주요 이유가 있다.
첫째, 모든 지연이 예측 가능하지는 않다.
특히 메모리 계층 구조에서 캐시 실패는 예측 불가능한 지연을 일으킨다. 동적 스케쥴링은 프로세서로 하여금 이러한 지연을 감춤으로써 지연이 끝나기를 기다리는 동안에도 명령어를 계속 실행할 수 있도록 한다.
둘째, 만약 프로세서가 동적 분기 예측을 사용하여 분기 결과에 대해 추정한다면 컴파일시에는 명령어의 정확한 순서를 알 수가 없다.
왜냐하면 이 순서는 분기에 대한 예측과 실제 행동에 의존하기 때문이다. 동적 스케쥴링을 사용하지 않고 더 많은 ILP를 찾으려고 동적 추정을 하는 것은 그러한 추정의 이득을 크게 제한하게 된다.
셋째, 파이프라인 지연과 내보내기 대역폭이 구현마다 다름에 따라 코드를 가장 잘 컴파일하는 것도 변하게 된다.
예컨대 종속적 명령어 시퀀스를 어떻게 스케쥴링하는가는 내보내기 대역폭과 지연에 의해 영향 받는다. 파이프라인 구조는 컴파일 기반의 레지스터 재명명 과정 뿐만 아니라 지연을 피하기 위해 순환문의 펼치기 횟수에 영향을 준다.
동적 스케쥴링은 하드웨어로 하여금 이 같은 자세한 것을 감추도록 해준다. 따라서 사용자나 소프트웨어 공급자의 경우 같은 명령어 집합의 서로 다른 구현에 따라 한 가지 프로그램이 여러 가지 버전을 갖는 것에 대해 우려할 필요가 없다.
비슷한 이유로 물려받은 오래된 코드는 재컴파일할 필요 없이 새로운 구현에 의해 얻어지는 대부분의 이득을 취할 수 있다.
파이프라이닝과 다중 내보니기 실행은 최고 명령어 처리량을 증가시키고 명령어 수준 병렬성(ILP)을 찾아내려 노력한다. 그러나 프로그램에서의 데이터 종속성, 제어 종속성은 지속적으로 얻을 수 있는 성능(sustained performance)의 상한점에 제한을 가한다. 그것은 때로는 프로세서가 종속성이 해결될 때까지 기다려야 하기 때문이다.
ILP를 찾아내기 위해 소프트웨어 중심의 접근방법은 그러한 종속성을 찾아내고 효과를 줄이는데 컴파일러의 능력에 의존하는 반면에 하드웨어 중심의 접근방법은 파이프라인과 내보내기 방법들의 확장에 의존한다.
컴파일러나 하드웨어에 의해 행해지는 추정은 예측을 통해 찾아낼 수 있는 ILP의 양을 증가시킬 수 있다. 그러나 잘못 추정하는 것은 성능을 저하시킬 가능성이 높기 때문에 주의를 기울여야 한다.
최신 고성능 마이크로프로세서들은 클럭당 여러 개의 명령어들을 내보낼 수 있다. 불행히도 그러한 내보내기율을 유지하는 것은 매우 어렵다.
예컨대 클럭당 4-6개의 명령어를 내보낼 수 있는 프로세서들이 존재함에도 불구하고 클럭당 세 개 이상의 명령어를 유지하는 응용은 매우 희귀하다. 이것에 대해서는 두 가지 주요 원인이 있다.
첫째, 파이프라인 내에서 성능의 주요 병목은 없앨 수 없는 종석성에 기인한다.
이 종속성 때문에 명령어 간의 병렬성은 줄고 지속적 내보내기율도 줄게 된다. 비록 진정한 데이터 종속성에 대해서는 할 수 있는게 별로 없지만 많은 경우 컴파일러나 하드웨어는 종속성이 존재하는지 그렇지 않은지에 대해 정확히 알지 못하기 때문에 종속성이 존재한다고 보수적으로 가정해야 한다.
예컨대 포인터를 사용하는 코드, 특히 많은 동의 문제(aliasing)을 일으키는 식으로 포인터를 사용하는 경우는 좀 더 많은 함축적인 잠재 종속성을 만들게 된다. 반면에 아주 규칙적인 배열 접근은 컴파일러로 하여금 종속성이 존재하지 않는다고 판단 하도록 유도한다.
비슷한 이유로 분기 명령어의 경우 실행 시나 혹은 컴파일 시에 정확히 예측되지 않으면 ILP를 찾아내는 능력에 제한을 가하게 된다. 더 많은 ILP가 있음에도 불구하고 멀리 떨어져 있는 ILP(때로는 명령어 수천 개의 실행만큼 떨어져 있다)를 찾을 수 없는 컴파일러나 하드웨어 능력의 한계 때문에 활용하지 못하는 경우가 많이 있다.
둘째, 메모리 계층구조에서의 손실이 파이프라인을 충분히 이용할 능력을 제한한다. 어떤 메모리 시스템의 지연은 감춰질 수 있지만 제한된 양의 ILP를 가지고는 감출 수 있는 지연의 양에 한계가 있게 된다.

에너지 효율성과 고급 파이프라이닝

동적 다중 내보내기와 추정 방법을 통해 명령어 수준 병렬성을 더 많이 이용하면서 생기는 부정적 측면은 전력 효율성이다. 매번 등장하는 신기술은 더 많은 트랜지스터를 사용하여 성능을 높일 수 있게 하였으나, 매우 비효율적으로 성능을 높인 경우가 많았다.
전력 장벽에 부딪히게 되자 전처럼 깊은 파이프라인이나 적극적 추정 방법을 사용하지 않는 프로세서 여러 개를 칩 하나에 넣는 설계가 나타나고 있다.
단순한 프로세서들이 정교한 프로세서들에 비해 빠르지는 않지만 단위 에너지(줄, joule)당 성능이 더 좋으므로, 트랜지스터의 개수보다 소모 전력에 의해 제한을 받는 설계에서는 칩 당 성능이 더 좋다는 믿음이 있기 때문이다.
그림 4.73은 과거 및 최신 마이크로프로세서들의 파이프라인 단계 수, 내보내는 명령어 개수, 추정 수준, 클럭 속도, 칩당 코어 개수, 소모 전력 등을 보여주고 있다. 회사들이 다중코어 설계 쪽으로 감에 따라 파이프라인 단계 수와 소모 전력이 감소함을 보여주고 있다.

실례: ARM Cortex-A8과 Intel Core i7 파이프라인 프로세서

그림 4.74는 이 절에서 알아볼 두 개의 마이크로프로세서에 대한 사양을 보여주고 있는데 이 두 개의 프로세서는 포스트 PC 시대의 두 기둥이다.

ARM Cortex-A8

ARM Cortex-A8은 1 GHz의 속도에 14단계 파이프라인을 갖고 있다. 동적 다중 내보내기를 사용하는데 클럭 사이클당 두 개의 명령어를 내보낼 수 있다. 명령어 내보내기, 실행 및 쓰기를 하는데 정적 순차 파이프라인 구조를 갖고 있다.
파이프라인은 명령어 인출, 명령어 해독, 명령어 실행 등 세 개의 부분으로 구성되어 있다. 그림 4.75는 전체 파이프라인을 보여주고 있다.
첫 세 단계에서는 한 번에 두 개의 명령어를 인출하고 12개 명령어 용량의 선인출 버퍼를 가득 채우려 노력한다. 2단계 분기 예측기를 사용하는데 이 예측기는 512개 용량의 분기 목적지 버퍼와 4096개 용량의 전역 이력 버퍼, 미래의 복귀 주소를 예측하기 위한 8개 용량의 복귀 스택을 사용한다.
분기 예측이 잘못되었으면 파이프라인을 다 비우게 되어 잘못 예측한 손실로 13개 클럭을 요구하게 된다.
다섯 단계의 해독 파이프라인은 명령어 쌍들 사이에 종속성이 있는지 또 어느 실행 단계 파이프라인으로 명령어를 보낼지 결정하게 되는데 명령어 쌍들 사이에 종속성이 존재하면 순차적인 실행을 할 수 밖에 없다.
명령어 실행 부분의 여섯 개 파이프라인 단계는 적재 명령어와 저장 명령어에 하나의 파이프라인을, 산술연산에 두 개의 파이프라인을 제공한다. 이 산술연산을 위한 두 개의 파이프라인 중 첫 번쨰 것만이 곱셈을 처리할 수 있다.
두 파이프라인 중 어느 것도 적재-저장 파이프라인으로 명령어를 보낼 수 있다. 실행 단계 파이프라인은 세 개 파이프라인 간에 완벽한 전방전달을 갖고 있다.
그림 4.76은 SPEC 2000 벤치마크 프로그램에서 구할 수 있는 조그만 프로그램들을 사용하여 A8의 CPI 값을 보여주고 있다. 이상적인 CPI 값은 0.5이지만 여기에서는 최상일 떄가 1.4를, 중간인 경우는 2.0을, 최악의 경우에는 5.2의 CPI를 보여주고 있다.
중간 성능인 경우 지연의 80%는 파이프라이닝 해저드에 의한 것이고, 20%의 지연은 메모리 계층구조 때문이다. 파이프라인 해저드는 분기 예측 실패, 구조적 해저드, 명령어 쌍 간의 데이터 종속성에 의한 것이다.
정적 파이프라인 구조인 A8에서 구조적 해저드와 데이터 종속성을 피하는 것은 컴파일러에 달려 있다.

Intel Core i7 920

x86 마이크로프로세서들은 정교한 파이프라이닝 기법들을 사용하는데, 이 기법들로는 동적 다중 내보내기, 비순차 실행과 추정을 사용하는 14단계 파이프라인의 동적 파이프라인 스케쥴링 등이 있다.
그러나 2장에서 설명한 바와 같이 이 프로세서들은 복잡한 x86 명령어 집합을 구현하는데 어려움이 있다. Intel은 x86 명령어를 인출한 후 이를 내부적으로 사용하는 MIPS와 비슷한 명령어로 변환을 한다.
이 명령어를 Intel에서는 마이크로연산(micro-operation)이라 부른다. 이 마이크로연산은 정교한 동적 스케쥴링과 추정 파이프라인에 의해 실행되는데 이 파이프라인은 클럭 사이클당 6개 마이크로연산까지 지속적으로 실행할 수 있다. 이 절에서는 마이크로연산과 파이프라인에 집중한다.
우리가 정교한 동적 스케쥴 프로세서의 설계를 생각하면 기능 유닛의 설계, 캐시 및 레지스터 파일, 명령어 내보내기 유닛, 전체 파이프라인 제어 등이 섞여서 데이터패스와 파이프라인을 분리하는게 어려워진다. 이런 이유로 많은 엔지니어와 연구자들은 마이크로구조(micro-architecture)라는 용어를 도입하여 프로세서의 구체적인 내부 구조를 가리킬 때 사용하였다.
Intel Core i7은 재정렬 버퍼와 레지스터 재명명을 함께 사용하여 반종속성과 추정 실패 문제를 해결하고 있다.
레지스터 재명명은 프로세서의 구조적 레지스터(architectural register)(x86 구조의 64비트 버전의 경우 16개)를 더 큰 물리적 레지스터 집합으로 명시적으로 재명명한다. Core i7은 레지스터 재명명을 반종속성을 제거하는데 사용하고 있다.
레지스터 재명명은 프로세서로 하여금 구조적 레지스터와 물리적 레지스터 간의 사상 관계 표를 유지하도록 요구하고 있는데 이 표는 어떤 물리적 레지스터가 구조적 레지스터의 가장 최근 복사본인지를 알려준다.
일어나는 재명명을 기록하여 놓음으로써 레지스터 재명명은 추정 실패시 원상 복구하는 또 다른 방법을 제공한다. 즉 처음에 잘못 추정한 명령어 이후 일어났던 사상을 없던 일로 하면 그만이다.
이렇게 하면 프로세서의 상태를 제대로 실행된 마지막 명령어로 되돌려 주기 때문에 구조적 레지스터와 물리적 레지스터 사이의 사상을 올바르게 유지하게 된다.
그림 4.77은 Core i7의 전반적인 구조 및 파이프라인을 보여주고 있다. 아래는 x86 명령어가 실행시 거쳐야 하는 여덟 단계를 나타내고 있따.
1.
명령어 인출
프로세서는 속도와 예측 정확도 사이에서 균형을 유지하기 위해 다단계 분기 목적지 버퍼를 사용한다. 함수의 복귀(return) 속도를 높이기 위해 복귀 주소 스택(return address stack)을 갖고 있다.
예측 실패는 15사이클 정도의 손실을 가져오며 예측 주소를 이용하여 명령어 인출 유닛은 명령어 캐시로부터 16바이트를 인출한다.
2.
16바이트를 선해독 명령어 버퍼(predecode instruction buffer)에 넣는다.
선해독 단계에서는 인출된 16바이트를 개별적인 x86 명령어로 변환한다. x86 명령어의 길이가 1바이트로부터 15바이트에 이르기 때문에 선해독 과정은 쉽지 않다. 선해독기는 명령어의 길이를 알기 위해 상당수 바이트들을 들여다봐야 한다. 각각의 x86 명령어는 18개 용량의 명령어 큐에 놓이게 된다.
3.
마이크로연산 해독
각각의 x86 명령어는 마이크로연산(micro-op)으로 변환된다. 세 개의 단순 해독기는 x86 명령어를 다루는데 이 명령어들은 하나의 마이크로연산으로 곧바로 번역된다. 좀 더 복잡한 의미를 갖는 x86 명령어들은 마이크로코드 엔진(복합 해독기)을 사용하여 마이크로연산 시퀀스로 변환된다.
이 엔진은 매 사이클에 네 개의 마이크로연산까지 만들어 낼 수 있으며 필요한 마이크로연산 시퀀스를 생성할 때까지 계속 이용하게 된다. 이 마이크로연산들은 28개 용량의 마이크로연산 버퍼에 놓이는데 x86 명령어의 순서에 따라 놓이게 된다.
4.
마이크로연산 버퍼는 순환열검출(loop stream detection)을 수행한다.
만약 순환문(loop)을 형성하는 조그마한 명령어 시퀀스(28개 명령어 미만이거나 256바이트 길이 미만)가 있다면 순환열검출기는 순환문을 검출하여 곧바로 버퍼로부터 해당 마이크로연산들을 내보내게 된다. 이렇게 함으로써 명령어를 인출하고 해독할 필요성을 없애게 된다.
5.
명령어 내보내기 수행
레지스터 테이블에서 레지스터 주소를 들여다보고 레지스터를 재명명하고 재정렬 버퍼에 배정한 다음 레지스터나 재정렬 버퍼에 필요한 결과 값이 있으면 이를 인출해 온 후 마이크로연산을 대기영역에 보낸다.
6.
i7은36개 용량을 갖는 중앙 대기영역을 갖고 있는데 여섯 개의 기능 유닛이 공유하여 사용한다. 매 클럭 사이클에 최대 6개의 마이크로연산이 기능 유닛으로 보내진다.
7.
각각의 기능 유닛은마이크로연산을 실행하게 되며 결과는 대기영역 중 필요로 하는 곳이나 레지스터 은퇴 유닛(register retirement unit)으로 보내진다. 레지스터 은퇴 유닛에서는 일단 명령어가 더 이상 추정이 아니라고 알려지면 레지스터 상태를 갱신하게 된다. 재정렬 버퍼에서 해당 명령어 관련 항목은 완료라고 표시된다.
8.
재정렬 버퍼의 맨 앞부분에 하나 이상의 명령어가 완료되었다고 표시되면 레지스터 은퇴 유닛에서 기다리던 쓰기대기(pending write)가 실행되어 쓰기가 행해지고 명령어는 재정렬 버퍼에서 삭제된다.

Intel Core i7 920 성능

그림 4.78은 SPEC 2006 벤치마크 프로그램들에 대한 Intel Core i7의 CPI 값을 보여주고 있다. 이상적인 CPI는 0.25지만 가장 좋은 경우는 0.44이고 중간 성능인 경우가 0.79이며, 가장 나쁜 성능의 경우 2.67이었다.
동적 비순차 실행 파이프라인에서 파이프라인 지연과 메모리 지연을 구분하는게 어렵지만 분기 예측과 추정의 효과를 보여줄 수 있다. 그림 4.79에서는 분기 명령어의 예측 실패율과 최종적으로 명령어의 결과가 무효화되었던 작업 비율을 볼 수 있다.
이 작업 비율은 파이프라인 속으로 보내진 마이크로연산의 개수로 측정하였는데 보내진 전체 마이크로연산 대비 상대 비율이다.
분기 명령어의 예측 실패율은 최소가 0%, 평균이 2%, 최대는 10%이었으며 작업 손실은 최소가 1%, 중간이 18%, 최대는 39%였다.
어떤 경우에는 작업 손실률이 분기 명령어의 예측 실패율과 매우 가깝게 일치하고 있는데 gobmk나 astar가 그것이며 mcf 같은 경우는 작업 손실률이 분기 명령어의 예측 실패율이 비해 상당히 큰 것으로 나타났다.
이와 같이 결과 비율이 상당히 넓게 분산되는 이유는 메모리 동작에 기인하는 것처럼 보인다. 메모리 참조 지연이 일어나는 경우 mcf는 데이터 캐시 실패율이 매우 높은 경우에도 대기영역이 충분히 비어 있으면 잘못된 추정 동안이라도 많은 명령어를 보내게 된다.
많은 추정 명령어 중에서 분기 명령어가 하나라도 예측이 잘못되었다면 이 모든 명령어에 해당하는 마이크로연산이 모두 버려지게 된다.
Intel Core i7은 고성능을 달성하기 위해 14단계 파이프라인과 공격적 다중 내보내기를 함께 사용한다. 연속적 명령어들 사이의 지연을 낮게 유지함으로써 데이터 종속성의 영향을 감소시킨다. 이 같은 프로세서에서 실행되고 있는 프로그램의 경우 무엇이 가장 위험한 잠재적 성능인가?
다음 리스트는 몇 가지 잠재적 성능 문제점들을 포함하고 있는데, 이 중 마지막 세 가지는 어떤 형태로든 모든 고성능 파이프라인 프로세서에 적용된다.
다수의 단순 마이크로연산으로 사상되지 않는 x86 명령어의 사용
예측하기 어려운 분기 명령어, 예측 실패에 의한 지연을 일으키고 추정이 실패하였을 때 재시작하게 만든다.
긴 종속성, 이 경우는 오래 실행되는 명령어에 의해 일어나거나 메모리 계층 구조에 의해 일어나는데 지연을 가져온다.
메모리에 접근할 때 생기는 성능 지연. 프로세서를 지연시킨다.

더 빠르게: 명령어 수준 병렬성과 행렬 곱셈

3장의 DGEMM 예제로 되돌아가서 보면 순환문 펼치기를 통해 명령어 수준 병렬성의 효과를 볼 수 있다. 이 명령어 수준 병렬성은 다중 내보내기, 비순차 실행 프로세서가 더 많은 명령어를 다룰 수 있게 만들어 준다.
아래 코드는은 그림 3.23에 있는 코드를 순환문 펼치기를 한 후의 결과를 보여주는데 AVX 명령어를 생성하기 위하여 C intrinsic 함수를 포함하고 있따.
#include <x86intrin.h> #define UNROLL (4) void dgemm(int n, double* A, double* B, double* C) { for (int i = 0; i < n; i += UNROLL * 4) { for (int j = 0; j < n; j++) { __m245d c[4]; for (int x = 0; x < UNROLL; x++) { c[x] = _mm256_load_pd(C + i + x * 4 + j * n); } for (int k = 0; k < n; k++) { __m256d b = _mm256_broadcast_sd(B + k + j * n); for (int x = 0; x < UNROLL; x++) { c[x] = _mm256_add_pd(c[x], _mm256_mul_pd(_mm256_load_pd(A + n * k + x * 4 + i), b)); } } for (int x = 0; x < UNROLL; x++) { _mm56_sotre_pd(C + i + x * 4 + j * n, c[x]; } } } }
C
그림 4.71에서 보았던 순환문 펼치기의 예제처럼 순환문을 네 번 펼치려 한다. (C 코드에 상수 UNROLL을 사용하여 순환문 펼치기 횟수를 조절할 수 있게 하였다)
그림 3.23에서는 intrinsic 함수 각각에 대해 네 벌 복사함으로써 순환문 펼치기를 수동으로 한 데 반해 이번에는 -O3 최적화로 순환문 펼치기를 해 주는 gcc 컴파이럴를 사용할 수 있다.
각각의 intrinsic 함수를 4번 반복하는 for 순환문으로 둘러싸고, 그림 3.23의 스칼라 C0는 4-원소 배열 c[ ]로 바꾼다.
아래 코드는 펼치기를 한 코드의 어셈블리 언어 출력을 보여주고 있다. 기대했던 대로 위 코드는 그림 3.24에서의 AVX 명령어 각각에 대해 4개 버전이 있음을 보여준다.
단 하나의 예외가 있다. vbroadcastsd 명령어의 경우는 하나만 보이는데 이는 레지스터 %ymm0에 있는 B 원소 네 벌을 순환문 전체에서 사용할 수 있기 때문이다.
따라서 그림 3.24에서 봤던 5개의 AVX 명령어는 아래 코드에서는 17개가 되었으면 7개의 정수 명령어가 양쪽에 나타나는 것을 볼 수 있다.
단지 상수와 주소 모드는 순환문 펼치기라는 것을 나타내기 위해 바뀌어 있다. 따라서 네 번의 순환문 펼치기에도 불구하고 순환문의 본체 부분에서의 명령어 개수는 12개에서 24개로 두 배만 늘어났을 뿐이다.
vmovapd (%r11), %ymm4 # Load 4 elements of C into %ymm4 mov %rbx, %rax # register %rax = %rbx xor %ecx, %ecx # register %ecx = 0 vmovapd 0x20(%r11), %ymm3 # Load 4 element of C into %ymm3 vmovapd 0x40(%r11), %ymm2 # Load 4 element of C into %ymm2 vmovapd 0x60(%r11), %ymm1 # Load 4 element of C into %ymm1 vbroadcastsd (%rcx, %r9, 1), %ymm0 # Make 4 copies of B elements add $0x8, %rcx # register %rcx = %rcx + 8 vmulpd (%rax), %ymm0, %ymm5 # Parallel mul %ymm0, 4 A elements vaddpd %ymm5, %ymm4, %ymm4 # Parallel add %ymm5, %ymm4 vmulpd 0x20(%rax), %ymm0, %ymm5 # Parallel mul %ymm0, 4 A elements vaddpd %ymm5, %ymm3, %ymm3 # Parallel add %ymm5, %ymm3 vmulpd 0x40(%rax), %ymm0, %ymm5 # Parallel mul %ymm0, 4 A elements vmulpd 0x60(%rax), %ymm0, %ymm0 # Parallel mul %ymm0, 4 A elements add %r8, %rax # register %rax = %rax + %r8 cmp %r10, %rcx # compare %r8 to %rax vaddpd %ymm5, %ymm2, %ymm2 # Parallel add %ymm5, %ymm2 vaddpd %ymm0, %ymm1, %ymm1 # Parallel add %ymm0, %ymm1 jne 68<dgemm+0x68> # jump if %r8 $rax add $0x1, %esi # register % esi = % esi + 1 vmovapd %ymm4, (%r11) # Store %ymm4 into 4 C elements vmovapd %ymm3, 0x20(%r11) # Store %ymm3 into 4 C elements vmovapd %ymm2, 0x40(%r11) # Store %ymm2 into 4 C elements vmovapd %ymm1, 0x60(%r11) # Store %ymm1 into 4 C elements
C
그림 4.82는 32x32 행렬에 대한 DGEMM 프로그램의 성능 향상을 보여주고 있는데, 최적화하지 않은 경우, AVX 명령어를 사용했을 경우, AVX 명령어를 사용하면서 최적화 했을 경우 등 세 가지에 대해 보여주고 있다.
순환문 펼치기는 6.4 GFLOPS에서 14.6 GFLOPS로 두 배 이상의 성능 증가를 보여 주고 있다. 서브워드 병렬성과 명령어 수준 병렬성을 위한 최적화를 하면 그림 3.21에서의 최적화하지 않은 DGEMM과 비교했을 때 8.59배의 속도 향상을 가져왔다.

오류 및 함정

오류: 파이프라이닝은 쉽다.
저자의 책들이 올바르게 파이프라인을 실행하는 것이 어렵다는 것을 증명하고 있다. 저자의 다른 책은 100명 이상이 검토하였고 18개 대학에서 강의하면서 테스트했음에도 추판에서는 파이프라인 버그가 있었다.
오류: 파이프라이닝 발상들은 기술과는 상관없이 구현될 수 있다.
칩 상의 트랜지스터 수와 트랜지스터의 속도가 다섯 단계 파이프라인을 가장 좋은 해결책으로 만들었던 당시에는 지연분기가 제어 해저드에 대한 단순 해결책이었다.
그런데 파이프라인이 길어지고 수퍼스칼라 실행에다 동적 분기 예측이 도입되면서 지연 분기는 없어도 그만인 것이 되었다.
1990년대 초에는 동적 파이프라인 스케쥴링은 너무나 많은 자원을 차지하여 고성능에 쓰이지 않았다. 그러나 Moore의 법칙에 따라 트랜지스터 수가 계속적으로 증가되고 논리회로가 메모리보다 훨씬 더 빨라지면서 다중 기능 유닛과 동적 파이프라이닝이 타당한 것으로 인식되었다.