싱글 사이클, 멀티 사이클 CPU와 명령어 파이프라이닝에 대해 알아보겠습니다.

본 글의 내용은 포항공과대학교의 CSED311의 내용을 기반으로
수업에서 다루지 않은 몇몇 내용을 추가하여 구성하였습니다.

CPU의 구현

싱글 사이클 CPU

CPU가 명령어 하나를 실행하려면 보통 아래 다섯 단계를 거칩니다.

• IF (Instruction Fetch) : PC가 가리키는 주소에서 명령어를 메모리(I-cache)로 부터 가져옵니다. 동시에 PC를 다음 명령어 주소로 업데이트합니다.
• ID (Instruction Decode) : 가져온 명령어를 해석합니다. 명령어가 덧셈인지 load인지 분기인지 파악하고, 필요한 레지스터 값을 읽어옵니다.
• EX (EXecute) : 실제 연산을 수행합니다. ALU에서 덧셈, 뺄셈, 비교 같은 산술/논리 연산을 하거나, 메모리 접근이 필요한 명령어라면 주소를 계산합니다. 분기 명령어의 경우 분기 조건을 이 단계에서 판단합니다.
• MEM (MEMory Access) : 메모리에 접근하는 단계입니다. store 명령이면 데이터 메모리(D-cache)에 쓰고, load 명령이면 읽어옵니다.
• WB (Write Back) : 결과를 레지스터에 쓰는 단계입니다. ALU 연산 결과나 메모리에서 읽어온 값을 목적지 레지스터에 저장합니다.

한 클럭 사이클 안에서 이러한 명령어의 모든 단계를 전부 끝내는 구조의 CPU를 싱글 사이클 CPU라고 부릅니다. 한 사이클 안에 메모리에서 명령어를 가져오고, 디코드하고, 연산하고, 메모리 접근하고, 레지스터에 쓰는 걸 전부 수행합니다. 이렇게 구현하면 구현이 단순하고 이해하기 쉽습니다.

하지만 치명적인 단점이 있는데, 클럭 사이클의 길이를 가장 느린 명령어에 맞춰야 한다는 점입니다. 예를 들어 ADD 명령어는 메모리 접근이 필요 없으므로 IF, ID, EX, WB만 하면 되는데, LOAD는 IF, ID, EX, MEM, WB 다섯 단계를 전부 거쳐야 합니다. 싱글 사이클에서는 모든 명령어가 같은 사이클 길이를 쓰므로, add도 load만큼 긴 사이클을 기다려야합니다. 느리게 끝나는 명령어 때문에 시간을 낭비하는 겁니다.

각 단계별 소요 시간을 아래와 같이 가정해 보겠습니다.

싱글 사이클 CPU에서는 클럭 주기를 가장 느린 Load 명령어에 맞춰 800ps로 고정해야 합니다. 따라서 500ps면 충분한 Branch 명령어도 매 사이클마다 800ps를 소모하게 되어, 명령어당 300ps가 낭비됩니다.

싱글 사이클 CPU의 설계

싱글 사이클 CPU는 한 클럭 안에서 명령어 하나를 처음부터 끝까지 실행합니다. 그래서 모든 기능 유닛이 동시에 동작할 수 있어야하고, 제어 회로가 단순합니다.

싱글 사이클 CPU의 각 유닛간 데이터패스는 IF부터 WB까지 경로가 한 줄로 쭉 연결된 구조입니다. 명령어 메모리와 데이터 메모리가 별도로 존재하고, ALU는 하나지만 PC + 4 를 계산하는 전용 Adder는 별도로 필요합니다. ALU가 EX에서 연산을 하는 동시에 PC + 4 다음 주소 계산도 진행해야하기 때문입니다.

제어 유닛은 조합 논리(combinational logic)으로 구성됩니다. 한 사이클 안에 모든 것이 끝나므로 제어 유닛에서 현재 상태를 기억할 필요가 없습니다. 명령어를 입력으로 받아서 ALU, 메모리 등 각 유닛에 필요한 제어신호, 예를 들어 RegDst, ALUSrc, MemtoReg와 같은 신호를 한 번에 출력합니다.

클럭 사이클 길이는 IF -> WB의 경로 중 가장 긴 경로의 전파 지연(propagation delay)으로 결정됩니다. 이를 크리티컬 패스(critical path) 라고 하는데, 보통은 Load 명령어의 경로가 가장 깁니다. 명령어 메모리 -> 레지스터 읽기 -> ALU 연산 -> 데이터 메모리 -> 레지스터 쓰기까지 모든 유닛을 직렬로 거치기 때문입니다. 싱글 사이클 CPU에서는 모든 명령어가 같은 시간, 한 사이클 안에 작업을 끝내야 하기 때문에 명령어들이 모두 이 크리티컬 패스 길이만큼의 시간을 써야합니다.

멀티 사이클 CPU

이를 해결하기 위해, 각 명령어가 자신이 필요로 하는 시간만큼만 걸리도록 하는 방식이 멀티 사이클 CPU입니다. 한 명령어를 여러번의 클락으로 나누고, 각 인스트럭션이 필요로 하는 시간만큼 여러번의 클락을 소모하게 하는 것입니다.

멀티 사이클 CPU에서는 각각의 명령어의 CPI (Cycles Per Instruction)이 다르고, Programmer Visible State는 인스트럭션의 사이클이 끝날때만 갱신됩니다. 명령어가 여러 클럭에 거쳐 실행되므로 CPI가 1보다 큽니다. 대신 time/cycle이 싱글 사이클보다 훨씬 짧아져 전체적인 성능이 향상됩니다.

앞서 본 명령어들을 멀티 사이클 CPU에 올려보겠습니다. 클럭 주기를 가장 짧은 단계인 100ps로 잡으면, 100ps짜리 단계는 1 클럭, 200ps짜리 단계는 2 클럭이 필요합니다.

각 명령어가 자신이 실제로 필요한 만큼만 클럭을 소모하므로, 싱글 사이클에서 모든 명령어가 800ps에 묶여있던 것과 달리 Branch는 500ps, R-type은 600ps에 끝나게 됩니다.

또한, 싱글 사이클 CPU에서 한 사이클에 모든 작업을 처리해야해서 인스트럭션을 가져오는 메모리, 데이터를 가져오는 메모리가 따로 필요했던 것과 대비되어, 멀티 사이클 CPU에서는 IF와 MEM이 서로 다른 사이클에서 처리되므로 메모리를 하나만 두고, IF에서는 명령어를 가져오고, MEM에서는 데이터를 읽거나 쓰는 식으로 사용하여 하드웨어를 공유할 수 있다는 장점 또한 있습니다. (다만 현대 CPU에서는 한정된 메모리 대역폭에서 속도 향상을 위해 I-cache와 D-cache가 분리되어 있으므로 메모리를 하나로 공유한다는 장점은 실제로는 큰 의미가 없습니다. 트랜지스터가 귀하고 하드웨어 자원이 제한되어 있던 초기 CPU에서 이러한 장점이 있었다고 알아두면 되겠습니다.)

멀티 사이클 CPU의 설계

멀티 사이클 CPU는 명령어 하나를 여러개의 사이클에 실행해야하기 때문에, 싱글 사이클 CPU와 설계 차이가 있습니다.

첫 번째로, 임시 레지스터가 필요합니다. 싱글 사이클에서는 데이터가 한 사이클 안에서 회로를 쭉 흘러가기만 하면 됐지만, 멀티 사이클에서는 이번 사이클의 결과가 다음 사이클까지 전달되어야합니다. IR이 명령어를, 레지스터 파일이 레지스터에서 읽은 값을, ALU가 연산 결과를, 메모리 유닛이 메모리에서 읽은 결과를 각각 저장해 명령어 실행 주기 동안 저장합니다.

두 번째로, FSM(Finite State Machine) 기반의 제어 유닛이 필요합니다. 같은 ALU가 어떤 사이클에서는 PC + 4를 계산해야하고, 다른 사이클에서는 SUB 연산을 합니다. 같은 메모리가 IF에서는 명령어를 내보내고 MEM에서는 데이터를 읽습니다. 이 때문에 각 모듈간을 잇는 멀티플렉서의 선택 신호가 현재 명령어가 어떤 단계까지 처리되었느냐에 따라 달라져야합니다. 싱글 사이클처럼 명령어만 보고 제어 신호를 결정하는 조합 논리는 불가능하고, 현재 상태를 기억하고 그에 따라 제어신호를 바꿔주는 FSM이 필요해집니다.

마이크로코드

마이크로코드는 멀티 사이클 CPU에서 FSM을 구현하는 방법 중 하나로, FSM의 제어 신호를 ROM에 저장해두는 방식입니다. 하드와이어드 방식에서는 현재 상태와 opcode를 입력으로 받아서 논리 게이트로 직접 제어 신호를 만들어냅니다. 빠르지만, 명령어를 추가하거나 제어 로직을 수정하려면 회로 전체의 설계를 바꿔야합니다.

마이크로코드 방식에서는 각 상태에서 어떤 제어 신호를 켜야하는지를 ROM 테이블에 미리 적어둡니다. 한 줄이 하나의 마이크로명령어(microinstruction)이고, 거기에 ALUSrcA, ALUSrcB, MemRead 같은 제어 신호 값과 다음 상태 정보가 담겨 있습니다. FSM의 현재 상태가 ROM의 주소가 되어 해당 줄을 읽어오면, 그게 이번 사이클의 제어 신호가 됩니다.

가장 큰 장점은 유연성입니다. 새로운 명령어를 추가하거나 기존 명령어의 동작을 바꾸고 싶으면 ROM의 내용만 수정하면 됩니다.

반면 단점은 속도인데, 매 사이클마다 ROM을 읽어와야하므로 그만큼 지연이 추가됩니다. 그래서 성능이 중요한 현대 CPU에서는 자주 쓰는 간단한 명령어는 제어 신호를 하드와이어링으로 처리하고, 복잡한 명령어만 마이크로코드로 처리합니다.

밀리코드, 나노코드

밀리코드와 나노코드는 마이크로 코드를 계층적으로 나눈 구조입니다.

마이크로코드는 한 마이크로명령어에 모든 제어 신호가 들어 있습니다. 그런데 서로 다른 마이크로 명령어들이 같은 제어 신호 조합을 반복하는 경우가 많습니다. 예를 들어 "메모리에서 읽어오기"라는 제어 신호 조합은 Load 명령어에서도 쓰이고 IF 단계에서도 쓰입니다. 이렇게 중복되는 제어 신호를 매번 전부 저장하면 ROM 공간이 낭비됩니다.

나노코드(Nanocode) 는 이 문제를 해결하는 마이크로코드 하위의 제어 계층입니다. 실제 제어 신호 조합들을 나노코드 ROM에 저장해두고, 마이크로코드 ROM에는 필요한 제어 신호가 들어있는 나노코드 ROM의 주소(포인터)만 저장해둡니다. 마이크로코드가 실행되면 먼저 마이크로코드 ROM에서 나노코드의 주소를 읽어오고, 그 주소로 나노코드 ROM에 가서 실제 제어 신호를 가져옵니다. 중복되는 제어 신호를 나노코드 ROM에 한 번만 저장할 수 있으니 전체 ROM 크기가 줄어듭니다. 대신 ROM을 두 번 읽어야하므로 속도가 느려진다는 단점이 있습니다.

밀리코드(Millicode) 는 나노코드와 반대로, 마이크로코드 상위에 있는 제어 계층입니다. 복잡한 명령어를 처리할 때, 마이크로코드만으로는 길어지고 관리가 어려울 수 있습니다. 밀리코드는 일종의 서브루틴처럼 동작해서, 자주 반복되는 마이크로코드 시퀀스를 하나의 밀리코드 루틴으로 묶어둡니다. 복잡한 명령어가 실행되면 밀리코드를 호출하고, 밀리코드가 내부적으로 마이크로코드 시퀀스를 실행하는 구조입니다.

현실에서의 마이크로코드

현대 x86 프로세서는 마이크로코드를 적극적으로 활용합니다. add, mov 같은 간단한 명령어는 하드와이어드 디코더가 직접 제어 신호를 결정합니다. 반면 REP MOVSB, CPUID, WRMSR 같은 CISC 특유의 복잡한 명령어는 마이크로코드 ROM에서 마이크로옵 시퀀스를 읽어와서 실행합니다. 이전 글에서 x86 CISC가 내부 명령어를 단순화하여 내부적으로는 RISC 스타일로 CPU를 작동시킨다고 하였는데, 이러한 RISC 스타일 마이크로옵이 그러한 역할을 수행하는 장치입니다.

밀리코드는 IBM의 z/Architecture 메인프레임에서 대표적으로 쓰입니다. 예를 들어 컨텍스트 스위칭, 인터럽트 처리, 가상 메모리 폴트 처리 같은 매우 복잡한 동작은 마이크로코드로 구현하기는 너무 길고 복잡합니다. 이러한 동작을 z/Architecture에서는 밀리코드 루틴으로 작성해두어 펌웨어 수준 서브루틴처럼 이용합니다.

나노코드는 CPU의 속도가 느려진다는 치명적인 단점이 있어, 현대 CPU에서는 잘 사용되지 않습니다. 역사적인 사례로는 1970년대 후반에 나온 모토로라 68000 (M68K)가 있는데, 마이크로코드 ROM에는 나노코드 주소만 저장하고, 나노코드 ROM에 실제 제어 신호 조합을 저장해 ROM 크기를 줄였습니다. 트랜지스터가 충분한 현대에는 ROM 크기를 줄이기 위해 별도 계층을 추가하는 것보다는, ROM을 두 번 읽는 속도 손실을 피하는게 더 중요하기 때문에, 나노코드 루틴을 사용하는 경우는 매우 드뭅니다.

파이프라인 CPU

파이프라이닝은 멀티 사이클 CPU에서 한 단계 더 나아간 구조입니다. 멀티 사이클에서는 명령어 하나가 여러 단계를 거치며 실행되는 동안 나머지 단계의 하드웨어가 놀고 있었습니다. 파이프라이닝은 이 놀고 있는 유휴 하드웨어에 바로 다음 명령어를 넣어서 여러 명령어를 동시에 겹쳐 실행합니다.

예를 들어 첫 번째 명령어가 ID 단계에 있으면, IF 하드웨어는 비어있으니까 두 번째 명령어를 가져옵니다. 첫 번째가 EX로 가면, 두 번째는 ID로, 세 번째는 새로 IF로 들어옵니다. 이렇게 하면 5단 파이프라인 기준으로 최대 5개의 명령어가 각기 다른 단계에서 동시에 처리됩니다.

개별 명령어의 레이턴시는 여전히 5 사이클이지만, 매 사이클마다 명령어 하나가 완료되니까 처리량은 사이클당 1개가 됩니다. 이전 글에서 다뤘던 throughput != 1/latency 구조가 적용되는 부분입니다.

구조적으로 멀티 사이클과의 핵심 차이는 파이프라인 레지스터입니다. 멀티 사이클에서는 임시 레지스터가 매 사이클 덮어쓰여도 괜찮았습니다. 어차피 한 번에 처리되는 명령어는 하나뿐이니까요. 하지만 파이프라이닝에서는 여러 명령어가 동시에 처리되므로, 각각의 파이프라인 단계 사이에 파이프라인 레지스터를 두어서 명령어별 데이터를 독립적으로 보존해야합니다. 파이프라인이 5개라면, IF/ID, ID/EX, EX/MEM, MEM/WB 네 개의 파이프라인 레지스터가 있고, 각각 해당 단계의 결과와 제어 신호를 함께 저장해서 다음 단계로 넘깁니다.

제어 신호는 ID 단계에서 한 번에 생성되고, 그 신호들이 파이프라인 레지스터를 타고 명령어와 함께 단계별로 흘러가면서 해당 단계에서 쓰입니다. 제어 신호가 자연스럽게 다음 단계로 흘러가므로, 멀티 사이클때 처럼 FSM이 현재 상태를 기억할 필요가 없습니다.

파이프라이닝의 성능

이상적인 경우, N단 파이프라인은 처리량을 N배 높일 수 있습니다. 매 사이클마다 명령어가 하나씩 완료되므로, 파이프라인이 없을 때보다 N배 더 많은 명령어를 같은 시간에 처리됩니다. 다만 현실에서는 이렇게 간단하게 성능 향상이 적용되지 않습니다.

첫번째로 파이프라인 레지스터(래치)의 오버헤드가 있습니다. 앞서 말했듯 파이프라인의 각 단계 사이에는 중간 결과를 저장하는 래치가 필요한데, 이 래치를 통과하는데도 시간이 걸립니다. 파이프라인이 없을 때 전체 연산 지연을 $T$, 래치 지연을 $S$라고 하면, $K$단 파이프라인의 한 사이클 길이는 다음과 같습니다.

$$T_{\text{clk}}(K) = \frac{T}{K} + S$$

연산 부분 $T$는 $K$로 나뉘어 줄어들지만, 매 단계마다 래치를 한 번씩 통과해야 하므로 $S$는 그대로 더해집니다. 처리량은 사이클당 명령어 1개이므로 $\text{Throughput}(K) = \frac{1}{T/K + S}$가 되고, $K \to \infty$일 때 사이클은 $S$로 수렴해 처리량의 상한이 $\frac{1}{S}$로 고정됩니다. 즉 파이프라이닝의 이론적 최대 속도 향상은

$$\text{Speedup}_{\max} = \frac{T + S}{S} \approx \frac{T}{S}$$

가 됩니다($T \gg S$일 때).

예를 들어 $T = 10\text{ns}$, $S = 1\text{ns}$라고 합시다. 파이프라인이 없으면 한 사이클은 11ns입니다. $K = 5$단으로 나누면 $10/5 + 1 = 3\text{ns}$가 되어 처리량이 약 3.7배 빨라집니다. $K = 10$이면 2ns로 5.5배, $K = 100$이면 1.1ns로 10배까지 올라갑니다. $K$를 무한히 키워도 사이클은 1ns($=S$) 아래로 내려가지 않으므로, 이론적인 최대 속도 향상은 $T/S = 10$배 부근에서 멈춥니다.

둘째로 하드웨어 비용이 증가합니다. 조합 논리의 총량 $G$는 파이프라인을 나눠도 변하지 않지만, 래치가 $K$개 필요하므로 단계 수에 비례하여 비용이 늘어납니다.

$$C(K) = G + L \cdot K$$

여기서 $L$은 래치 한 개당 드는 비용(면적·전력의 대용치인 게이트 수)입니다. $K = 1$(파이프라인 없음)일 때 $C = G + L$이고, $K$가 커질수록 기울기 $L$의 직선으로 비용이 증가합니다.

예를 들어 조합 논리가 $G = 1000$ 게이트, 래치 하나가 $L = 50$ 게이트라고 합시다. 파이프라인이 없으면 1000 게이트지만, $K = 5$단이면 $1000 + 50 \cdot 5 = 1250$ 게이트로 25% 늘어납니다. $K = 10$단이면 1500 게이트(50% 증가), $K = 20$단이면 2000 게이트로 원래의 두 배가 됩니다. 단계를 잘게 쪼갤수록 처리량은 늘지만, 그만큼 면적과 전력 비용도 함께 따라옵니다.

따라서 단순히 파이프라인을 무한히 늘리는 것이 아니라, 파이프라인에 따른 성능 증가와 비용의 균형점에서 적절한 파이프라인 깊이를 선택하는 것이 중요합니다. 1981년에 Peter M. Kogge는 성능 대비 비용을 최대화하는 최적 파이프라인 깊이를 아래와 같은 공식으로 제안했습니다.

$$K_{\text{opt}} = \sqrt{\frac{T \cdot G}{S \cdot L}}$$

이 식은 처리량 $\frac{1}{T/K + S}$을 비용 $G + L \cdot K$로 나눈 성능/비용 비율을 $K$에 대해 미분해 0이 되는 지점에서 나옵니다. 직관적으로 보면, 분자의 $T \cdot G$는 "파이프라이닝으로 얻을 수 있는 이득"을 나타내고(원래 연산이 길고 무거울수록 나눌 가치가 큼), 분모의 $S \cdot L$은 "단계를 늘릴 때 드는 비용"을 나타냅니다(래치 지연과 면적이 클수록 단계를 늘리기 부담스러움).

앞서 든 예시 값을 그대로 넣어보면, $T = 10\text{ns}$, $S = 1\text{ns}$, $G = 1000$, $L = 50$일 때 $K_{\text{opt}} = \sqrt{10 \cdot 1000 / (1 \cdot 50)} = \sqrt{200} \approx 14$입니다. 즉 이 가정 아래에서는 14단 정도가 성능 대비 비용이 가장 좋은 지점이고, 그보다 더 잘게 쪼개면 래치 오버헤드와 하드웨어 비용 증가가 처리량 향상을 갉아먹기 시작합니다.

물론 실제 CPU 설계에서는 이 공식만으로 깊이를 정하지 않습니다. 뒤에서 다룰 파이프라인 해저드(데이터·제어·구조적 해저드)로 인한 스톨, 분기 예측 실패 시 파이프라인 플러시 비용, 전력 소모, 검증 난이도 등이 모두 깊이를 제약하는 요인입니다. Kogge 공식은 어디까지나 "이상적인 조건에서의 상한선"을 보여주는 기본 공식입니다.

파이프라인 해저드

파이프라이닝은 여러 명령어를 겹쳐서 실행하기 때문에, 명령어 간의 의존성이 있으면 문제가 생깁니다. 이로 인해 생기는 문제가 데이터 해저드(Data Hazard) 와 컨트롤 해저드(Control Hazard) 입니다.

데이터 해저드

데이터 해저드는 파이프라인에서 앞 명령어의 결과를 뒤 명령어가 필요로 할 때, 아직 결과가 준비되지 않아서 생기는 문제입니다.

예를 들어 아래와 같은 RISC-V 명령어 두 개가 연속으로 실행된다고 합시다.

add x1, x2, x3   # x1 = x2 + x3
sub x4, x1, x5   # x4 = x1 - x5

sub는 add가 계산한 x1을 입력으로 씁니다. 그런데 5단 파이프라인에서 add가 계산을 끝내는 시점은 EX 단계(사이클 3)이고, 그 결과가 레지스터 파일에 실제로 쓰이는 시점은 WB 단계(사이클 5)입니다. 반면 sub는 한 사이클 뒤에 들어와서 ID 단계에서 x1을 읽으려고 하는데, 이때는 사이클 3이라 아직 x1에는 옛날 값이 들어 있습니다. 이게 바로 RAW(Read After Write) 데이터 해저드입니다.

해결 방법은 세 가지가 있습니다.

첫째는 스톨(stall) 입니다. 결과가 준비될 때까지 뒤 명령어를 멈추고 기다립니다. 파이프라인에는 버블(빈 사이클)이 삽입되어서 앞 명령어가 처리되는 동안 조합 로직의 나머지 로직은 놀게 됩니다. 가장 단순한 방법이지만, 성능 손실이 큽니다.

둘째는 포워딩(forwarding) 입니다. 또는 바이패싱(bypassing) 이라고도 합니다. ALU 연산의 결과는 EX 단계가 끝나면 ALU 출력에 이미 존재합니다. 이 결과값이 레지스터에 쓰여질 때까지(WB) 기다릴 필요 없이, EX/MEM 파이프라인 레지스터에 값을 바로 꺼내서 다음 명령어의 ALU 입력으로 넘겨주는 겁니다. 하드웨어적으로는 파이프라인 레지스터의 출력에서 ALU 입력으로 가는 바이패스 경로와 멀티플렉서를 추가하고, 포워딩 유닛이 "지금 읽으려는 레지스터가 앞 단계에서 쓰여질 예정인지" 감지해서 ALU 멀티플렉서를 제어합니다.

포워딩으로 대부분의 데이터 해저드는 해결할 수 있지만, 해결할 수 없는 유형의 해저드도 있습니다. load-use 해저드입니다. load 명령어는 EX 다음의 MEM 단계가 끝나야 값이 나옵니다. 바로 다음 명령어가 그 값을 EX에서 쓰려면 사이클이 맞지 않습니다. 이 경우에는 1사이클 스톨이 불가피합니다.

lw  x1, 0(x2)    # x1 = MEM[x2 + 0]
add x3, x1, x4   # x3 = x1 + x4

lw의 결과는 MEM 단계가 끝나는 사이클 4에 나오는데, add는 사이클 4에 EX에 들어가야 하므로 한 사이클 빠릅니다. 포워딩 경로를 동원해도 시간 자체를 거꾸로 돌릴 수는 없으니, add를 한 사이클 멈추고 그 자리에 버블을 넣어야 합니다. 이후엔 MEM/WB 레지스터에서 add의 EX 입력으로 포워딩이 들어옵니다.

셋째는 컴파일러가 명령어 순서를 재배치(scheduling)하는 방법입니다. load 다음에는 그 값을 쓰는 명령어가 바로 오지 않도록, 사이에 먼저 처리되어도 무관한 명령어를 끼워넣습니다.

예를 들어 아래와 같은 C 코드가 있다고 합시다.

int a = arr[i];
int b = a + 1;
int c = brr[j];
int d = c * 2;

이를 그대로 컴파일하면 lw a 바로 뒤에 addi b, a, 1이 와서 load-use 스톨이 한 번 발생하고, lw c 뒤에 slli d, c, 1이 와서 또 한 번 스톨이 발생합니다. 하지만 a와 c, b와 d는 서로 의존하지 않기 때문에, 컴파일러는 다음처럼 순서를 바꿀 수 있습니다.

lw   a, 0(arr_i)
lw   c, 0(brr_j)   # a를 기다리는 동안 c를 미리 로드
addi b, a, 1       # 이 시점엔 a가 이미 준비됨
slli d, c, 1       # c도 이미 준비됨

lw a와 addi b 사이에 lw c가 들어가 있어서 load-use 간격이 벌어지고, 두 개의 스톨이 모두 사라집니다. 같은 작업을 두 사이클 더 빨리 끝낼 수 있는 셈입니다.

대표적인 컴파일러인 GCC와 LLVM(Clang) 모두 이러한 명령어 스케쥴링을 수행합니다. 먼저 명령어 간의 의존성 그래프 (dependency graph)를 만들어서 어떤 명령어가 어떤 명령어의 결과에 의존하는지 파악하고, 의존 관계가 없는 명령어들의 순서를 자유롭게 재배치합니다. GCC는 -O2 이상에서 이 최적화가 활성화되어, 레지스터 할당 전후로 두 번 스케쥴링을 수행합니다. LLVM도 마찬가지로 중간 표현(LLVM-IR) 수준과 머신 코드 수준에서 각각 스케쥴링을 수행하는데, 두 컴파일러 모두 타겟 CPU 별로 명령어 latency, 실행 유닛 수 같은 파이프라인 정보를 테이블로 가지고 있어서, 해당 CPU에 맞는 최적의 순서를 결정합니다.

데이터 해저드는 앞서 말한 비용 대비 성능 효율에 더해서, 너무 깊은 파이프라인을 사용할 수 없게 하는 요소 중 하나입니다. 만약 깊은 파이프라인을 이용한다면, 포워딩이 커버해야하는 거리가 상당히 멀어집니다. 5단 파이프라인에서는 ADD 다음에 그 결과를 쓰는 SUB이 오면, EX의 결과를 바로 다음 EX로 포워딩하면 한 사이클 차이라 깔끔하게 해결됩니다. 그런데 EX 단계를 쪼개서 EX1, EX2, EX3으로 만들면, 연산 결과는 EX3에서 나오는데 다음 명령어는 EX1에서 이미 이 값이 필요합니다. 데이터 포워딩으로도 커버가 불가능한 사이클이 늘어나서 스톨이 더 자주 발생합니다.

load-use 해저드는 더 심각해집니다. 5단의 간결한 파이프라인에서는 load 후 1 사이클 스톨이면 충분했는데, MEM 단계를 여러 단계로 쪼개서 더 깊은 파이프라인을 만들면 메모리에서 값이 나오기까지 더 많은 사이클이 걸립니다. 그만큼 스톨 사이클이 늘어나거나, 컴파일러가 사이에 끼워넣어야 할 명령어 수가 많아집니다.

컨트롤 해저드

컨트롤 해저드는 분기 명령어에서 다음에 실행할 명령어의 주소를 아직 모르는 상태에서, 파이프라인이 이미 다음 명령어를 가져와서 생기는 문제입니다.

예를 들어 아래와 같은 코드가 있다고 합시다.

beq  x1, x2, L1   # x1 == x2 이면 L1로 분기
add  x3, x4, x5   # 분기가 안 일어났을 때 실행될 명령어
sub  x6, x7, x8
...
L1:
or   x9, x10, x11

5단 파이프라인에서 beq의 분기 조건은 EX 단계(사이클 3)에서야 결정됩니다. 그 사이에 add와 sub는 이미 IF, ID 단계에 들어와 있습니다. 만약 분기가 실제로 일어났다면 이 두 명령어는 잘못 가져온 것이므로 버리고(flush), L1의 or 부터 다시 가져와야 합니다.

두 사이클이 버블로 날아가서, 분기 한 번에 2사이클의 페널티가 생깁니다. IF 단계는 명령어를 해석하기 전이라 분기 여부조차 알 수 없고, 분기 종류는 ID에서, 조건은 EX에서야 확정되기 때문에 그 사이에 가져온 명령어들을 모두 flush해야 하는 것입니다.

해결 방법은 아래와 같습니다.

첫째는 데이터 해저드와 마찬가지로 스톨입니다. 분기 명령어를 만나면 뒤 명령어를 가져오지 않고 기다리다가 분기의 결과가 나오면 다음 명령어를 가져오는 것입니다. 안전하고 간단하지만, 분기가 나올 때마다 사이클이 크게 낭비되어 성능 손실이 큽니다.

둘째는 분기 결정의 조기화입니다. 분기 비교를 EX가 아닌 ID 단계에서 처리하도록 하드웨어를 추가하면, 스톨의 패널티가 2사이클에서 1사이클로 감소합니다. MIPS가 이런 방식을 사용하는 대표적인 CPU입니다.

셋째는 지연 분기(delayed branch) 입니다. 이건 ISA 차원의 약속인데, 분기 명령어 뒤에 오는 한 개(또는 그 이상)의 명령어 자리를 branch delay slot으로 정의하고, 하드웨어가 분기 여부와 무관하게 그 슬롯의 명령어를 항상 실행하도록 만듭니다. 즉 "분기가 일어나든 말든 슬롯은 무조건 실행한다"는 의미가 명령어 집합의 일부가 됩니다. 그러면 IF 단계에서 잘못 가져올 걱정 자체가 사라지므로 flush할 일이 없고, 분기 페널티 사이클이 그대로 사라집니다.

대신 그 슬롯을 의미 있는 명령어로 채우는 것은 컴파일러의 몫입니다. 컴파일러는 분기 앞쪽에서 분기 조건이나 점프 주소에 영향을 주지 않는 독립적인 명령어를 하나 골라서 슬롯으로 옮깁니다. 예를 들어 MIPS 코드에서:

addu $t0, $t1, $t2   # 분기와 무관한 계산
beq  $a0, $a1, L1

addu는 beq의 비교 대상($a0, $a1)과 무관하므로, 분기 앞이든 뒤든 결과가 같습니다. 컴파일러는 이를 다음처럼 재배치합니다.

beq  $a0, $a1, L1
addu $t0, $t1, $t2   # branch delay slot — 분기 여부와 무관하게 항상 실행

이렇게 하면 addu는 어차피 실행해야 할 명령이었으므로 1사이클 페널티가 공짜로 메워집니다. 만약 옮길 만한 독립 명령어가 없으면 컴파일러는 슬롯에 nop을 박아넣어야 하고, 이 경우엔 그냥 스톨과 같은 페널티를 부담합니다.

지연 분기는 1980년대 초기 RISC들이 흔히 채택한 방식으로, MIPS, SPARC, PA-RISC, SuperH 등이 모두 1사이클짜리 delay slot을 ISA에 박아두었습니다. 하지만 파이프라인 깊이가 늘어나면 슬롯 하나로는 분기 페널티를 다 메울 수 없고, 슈퍼스칼라/비순차 실행이 일반화되면서 분기 예측기의 정확도가 훨씬 좋은 해법이 되었습니다. 무엇보다 ISA에 못 박힌 의미론이라 나중에 파이프라인 구조를 바꾸기도 어렵습니다. 그래서 ARM, PowerPC, Alpha 같은 후발 RISC들은 처음부터 delay slot을 도입하지 않았고, RISC-V도 명시적으로 빼버렸으며, MIPS조차 2014년 R6 개정에서 delay slot을 폐기했습니다.

넷째는 컴파일러 단에서 분기 자체를 줄이거나 없애는 방법입니다. if-conversion은 짧은 if-then-else를 조건부 이동(x86 cmov, ARM predication, RISC-V Zicond 등) 으로 바꿔 분기를 아예 제거합니다. 루프 언롤링은 본문을 복제해 반복마다 도는 백 엣지 분기 횟수를 줄이고, 인라이닝은 함수 호출과 리턴 분기를 통째로 없앱니다.

예를 들어 x = (a > b) ? a : b를 그대로 컴파일하면 비교 후 분기 한 번이 들어가지만, if-conversion을 적용하면 다음처럼 분기 없이 끝납니다.

cmp  a, b
mov  x, b
cmovg x, a   # a > b이면 x = a, 아니면 그대로 b

마지막은 분기 예측(branch prediction) 입니다. 현대 CPU에서 주로 사용하는 방법입니다. 분기 예측에는 다양한 방법이 있는데, 이는 다음 글에서 더 자세히 살펴보도록 하겠습니다.