M 확장 구현: 곱셈·나눗셈기 연동, 0 나누기 결과 규칙 그대로 만들기

RISC-V 코어 구현 묶음은 디코더, 데이터패스, 5단 파이프라인, 분기를 거쳐 왔다. 이번 편부터는 그 RV32I 5단 파이프라인 코어에 표준 확장을 하나씩 붙인다. 첫 번째가 M 확장(곱셈·나눗셈)이다. 명령어 자체는 7편에서 본 대로 8개뿐이지만, 구현하려면 한 사이클에 끝나지 않는 연산 장치를 파이프라인에 끼워 넣어야 한다. 이 글은 RTL 대신 비트 단위로 정확한 Python 모델로 곱셈기와 나눗셈기를 짜고, 명세의 0 나누기·오버플로 규칙이 알고리즘에서 저절로 나오는지 직접 확인한다.

1. M 확장이 하드웨어에 요구하는 것

M 확장 명령어는 모두 R 형식이고 opcode는 OP(0110011), funct7은 0000001이다. funct3가 8개 중 하나를 고른다(비특권 명세 13장).

funct3[2]가 곱셈(0)과 나눗셈(1)을 가른다. 디코더는 이 비트 하나로 어느 장치에 보낼지 정하면 된다.

예외는 하나도 없다. 0으로 나눠도, -2^31 ÷ -1처럼 몫이 넘쳐도 트랩 없이 정해진 값을 낸다. 명세 표 11의 규칙은 다음과 같다.

명세는 이 값을 고른 이유로 "단순한 부호 없는 나눗셈 회로가 자연스럽게 내는 값"이라는 점을 든다. 이 글의 4절에서 그 말이 어디까지 맞는지 모델로 확인한다.

2. 곱셈기 선택지

곱셈기는 면적과 지연 사이에서 고른다. 5단 파이프라인 코어에 붙일 때 흔한 선택지는 세 가지다.

배열 곱셈기는 32×32 부분곱 1,024개를 한 사이클에 더한다. FPGA에서는 DSP 블록 몇 개를 묶어 이렇게 만드는 경우가 많고(추정), ASIC에서는 EX 단계의 임계 경로가 길어져 클록을 깎는다. 파이프라인 곱셈기는 같은 배열을 레지스터로 2~3단에 나눈다. 지연은 고정이고 매 사이클 새 곱셈을 받을 수 있어서, 결과가 나올 때까지 의존 명령어만 멈추면 된다.

반복형은 덧셈기 하나로 한 사이클에 부분곱 하나(radix-2) 또는 둘(radix-4)을 더한다. 면적이 가장 작고 마이크로컨트롤러급 코어에 어울린다. 이 글의 모델은 반복형 두 가지를 짠다. 지연이 길고 사이클마다 무슨 일이 일어나는지 분명해서, RTL로 옮길 때 그대로 상태 기계가 되기 때문이다.

3. 곱셈기 하나로 네 명령어: 33비트 부호 확장

mulh·mulhsu·mulhu는 같은 비트를 서로 다르게 해석해 곱한다. 곱셈기를 셋 둘 수는 없으니 해석 차이를 입력 쪽에서 흡수한다. 각 피연산자 위에 1비트를 붙이는데, 부호 있게 읽을 때는 비트 31을 복사하고(부호 확장), 부호 없이 읽을 때는 0을 붙인다. 그러면 32비트 무부호 값도 33비트 부호 있는 값으로 정확히 표현되고, 곱셈기는 언제나 33×33 부호 있는 곱셈만 하면 된다.

같은 비트 0xffffffff × 0xffffffff를 세 가지로 읽어 보자. QEMU에서 실행한 결과다.

아래 32비트는 셋 다 0x00000001이다. 2의 보수에서 아래 절반은 부호 해석과 무관하기 때문이다. 그래서 mul은 sa·sb를 아무렇게나 골라도 된다.

33×33 곱은 66비트지만 위 2비트는 버린다. 두 입력이 33비트 부호 있는 값이면 곱의 크기는 $2^{64}$를 넘지 않으므로, 아래 64비트만으로 결과가 결정된다.

반복형 radix-2 모델은 이렇게 동작한다. 누산기 A(34비트)와 승수 레지스터 Q(33비트)를 나란히 두고, 매 사이클 Q의 맨 아래 비트가 1이면 A에 피승수를 더한 뒤 {A, Q}를 통째로 오른쪽으로 1비트 산술 시프트한다. 33비트 부호 있는 수에서 맨 윗비트의 무게는 $-2^{32}$이므로 마지막(33번째) 사이클만 더하기 대신 빼기를 한다. radix-4 Booth는 승수를 34비트로 늘려 2비트씩 보고 −2, −1, 0, +1, +2배 중 하나를 더하므로 17사이클이다.

def mul_radix2(a33, b33):
    A, Q, Mc = 0, b33 & ((1 << 33) - 1), a33
    for i in range(33):
        if Q & 1:
            A = wrap(A - Mc if i == 32 else A + Mc, 34)
        Q = (Q >> 1) | ((A & 1) << 32)  # {A,Q} >> 1
        A >>= 1                          # 산술 시프트
    return ((A << 33) | Q) & ((1 << 64) - 1), 33

wrap(v, 34)는 34비트 레지스터에서 넘친 비트를 버리는 함수다. 이 폭으로 30만 쌍을 돌려 한 번도 틀리지 않았으니, A는 34비트면 충분하다.

4. 나눗셈기와 0 나누기: 직접 확인

나눗셈은 곱셈보다 빠르게 만들기 어렵다. 작은 코어는 대부분 한 사이클에 몫 1비트를 내는 반복형을 쓴다. 기본 흐름은 손으로 하는 나눗셈과 같다. 나머지 레지스터 R을 왼쪽으로 1비트 밀면서 피제수의 다음 비트를 넣고, R에서 제수를 뺄 수 있으면 빼고 몫 비트 1을, 못 빼면 0을 기록한다.

4비트로 11 ÷ 3(1011 ÷ 0011)을 따라가 보자.

몫 0011 = 3, 나머지 2다. 이것이 복원(restoring) 나눗셈이다. 뺄셈 결과가 음수면 원래 R로 "되돌린다". 비복원(non-restoring)은 되돌리지 않고, R이 음수인 동안에는 다음 단계에서 제수를 빼는 대신 더한다. 단계마다 덧셈기 하나에 뺄셈/덧셈 선택만 있으면 되고, 마지막에 R이 음수면 제수를 한 번 더해 보정한다. 둘 다 32비트면 32번 반복한다.

이제 제수가 0이면 어떻게 될까. 같은 4비트 예에서 1011 ÷ 0000을 하면 매 단계 R − 0 ≥ 0이라 몫 비트가 언제나 1이다. 몫은 1111, R은 피제수 비트가 하나씩 들어와 마지막에 1011이 된다. 명세 값(몫 전부 1, 나머지 = 피제수) 그대로다. 비복원도 R이 음수가 될 일이 없어 같은 결과가 나온다. 모델로 0 나누기 10,072개(경계값 72개 + 무작위 10,000개)를 돌린 결과다.

부호 있는 나눗셈은 보통 부호 없는 회로를 재사용한다. 두 피연산자의 절댓값으로 나눈 뒤, 두 부호가 다르면 몫을 부정하고 피제수가 음수면 나머지를 부정한다. 그런데 -7 ÷ 0을 보자. |−7| ÷ 0 = 몫 0xffffffff, 나머지 7. 피제수는 음수, 제수 0은 "양수"로 읽히니 부호가 달라 몫을 부정한다. -0xffffffff를 32비트로 자르면 0x00000001이다. 명세는 0xffffffff를 요구한다. 음수 피제수(약 절반)에서 모두 틀렸다. 나머지는 7을 부정해 −7, 즉 피제수 그대로라 맞다.

고치는 방법은 조건 하나다.

neg_q = (sa < 0) != (sb < 0) and b != 0

"제수가 0이면 몫 부호를 되돌리지 않는다." 명세가 말한 "부호 없는 회로가 내는 자연스러운 값"은 맞지만, 부호 되돌리기 단계에서 이 조건 한 개는 필요하다.

오버플로 쪽은 특별 처리가 필요 없었다. 0x80000000 ÷ -1은 절댓값으로 0x80000000 ÷ 1 = 몫 0x80000000, 나머지 0이고, 두 부호가 같아 부정하지 않는다. 결과 0x80000000·0은 명세 값과 정확히 같다. 32비트 절댓값 0x80000000을 부호 없는 수로 다루기만 하면 된다.

5. 조기 종료: 반복 횟수 줄이기와 그 함정

실제 프로그램의 나눗셈은 대부분 작은 수끼리다(추정). 32번을 다 도는 것은 낭비라서 조기 종료(early termination)를 넣는 코어가 많다. 두 가지를 모델로 만들었다.

• 앞쪽 0 건너뛰기: 피제수의 앞쪽 0비트 수 clz(a)만큼 미리 왼쪽으로 밀고 32 − clz(a)번만 반복한다. 앞쪽 0비트에서는 몫 비트가 0일 것이 뻔하기 때문이다.
• 제수 맞춰 당기기: 제수를 피제수 높이까지 왼쪽으로 밀어 두고 clz(b) − clz(a) + 1번만 반복한다. a < b면 바로 몫 0, 나머지 a.

균등 분포에서는 a < b일 확률이 절반이라 맞춰 당기기가 거의 1번에 끝났다(1번이 66.5%). 크기를 고르게 뽑은 쪽이 실제에 더 가까울 것이다(추정). 대가는 하드웨어다. 0 건너뛰기는 앞자리 0 개수 세기(LZC)와 시프터 하나, 맞춰 당기기는 LZC 둘과 시프터가 필요하다.

함정이 있다. 0 건너뛰기에서 제수 0을 따로 막지 않으면 결과가 틀린다. 건너뛴 앞쪽 단계에서도 원래는 R − 0 ≥ 0이라 몫 비트가 1이었어야 하는데, 건너뛰는 바람에 0으로 남는다. 1000 ÷ 0의 몫이 0xffffffff가 아니라 0x000003ff(아래 10비트만 1)가 됐다. 0 나누기 10,072개 중 5,033개가 틀렸다. 4절에서 "알고리즘이 저절로 맞는 값을 낸다"고 했던 성질이, 반복을 줄이는 순간 깨지는 것이다. 그래서 조기 종료를 넣는 코어는 제수 0을 감지해 1사이클에 명세 값을 내는 경로를 둔다. 모델의 두 조기 종료 방식 모두 이 경로를 넣은 뒤 30만 쌍에서 불일치 0이었다.

6. 파이프라인 연동: busy, 스톨, 결과 되돌림

다사이클 장치를 5단 파이프라인에 붙이는 가장 단순한 방법은 이렇다. 곱셈·나눗셈 명령어가 EX에 들어오면 장치에 start를 주고, 장치는 끝날 때까지 busy를 1로 둔다. busy 동안 IF·ID 파이프라인 레지스터의 쓰기를 막고(스톨), EX/MEM 레지스터에는 거품(bubble)을 넣는다. done이 오면 결과를 ALU 결과 자리에 실어 MEM으로 보낸다. 그 뒤로는 일반 ALU 결과와 똑같이 포워딩되고 WB에서 쓰인다.

그림은 모델의 타임라인 함수가 계산한 결과를 옮긴 것이다. 지연 L = 4인 mul 뒤의 명령어는 L − 1 = 3사이클 멈춘다. sub는 mul과 무관한데도 함께 멈췄다. 이것이 단순한 방식의 비용이다. 의존 명령어만 멈추려면 장치가 도는 동안 뒤 명령어들이 EX를 지나가게 해야 하는데, 그러면 곱셈 결과와 뒤 명령어 결과가 같은 사이클에 WB 포트를 원할 수 있고, rd에 대한 점수판(scoreboard)과 WB 포트 중재가 필요해진다. 나눗셈 32사이클 동안 놀지 않으려는 코어는 이 길을 간다.

연동에서 놓치기 쉬운 것이 하나 더 있다. 장치가 도는 중에 앞선 명령어가 트랩이나 분기 예측 실패로 파이프라인을 비우면, 장치는 시작된 연산을 버려야 한다(kill 신호). 반대로 이미 커밋하기로 정해진 연산을 인터럽트 때문에 버리면 mepc가 가리키는 명령어가 다시 실행되므로 결과는 같지만 사이클이 낭비된다(이 부분은 트랩 편인 27편에서 다시 본다).

7. mulh + mul 융합: 레지스터 이름이 아니라 값

명세는 위아래 절반이 모두 필요할 때 mulh[[s]u] rdh, rs1, rs2 다음에 mul rdl, rs1, rs2를 쓰라고 권한다. 소스 레지스터 순서가 같고 rdh가 rs1·rs2와 다르면, 마이크로아키텍처가 두 명령어를 곱셈 한 번으로 합칠 수 있다(13.1절). 나눗셈도 div[u] rdq, rs1, rs2 다음 rem[u] rdr, rs1, rs2(rdq ≠ rs1, rs2)가 같은 역할이다.

그런데 GCC 16.2가 (uint64_t)a * b를 rv32im으로 컴파일한 결과는 이랬다.

mv     a5,a1
mulhu  a1,a0,a1
mul    a0,a0,a5

mulhu가 결과를 a1(=rs2)에 쓰기 때문에 mul은 a1 대신 미리 복사해 둔 a5를 읽는다. 값은 같지만 레지스터 이름이 달라서, 명세의 권장 순서를 이름으로 확인하는 융합 검출기는 이 쌍을 놓친다. 대신 곱셈기가 직전 연산의 피연산자 값과 66비트 곱 전체를 기억해 두고, 다음 곱셈의 피연산자 값이 같으면 바로 답을 내는 방식(결과 재사용)은 잡아낸다. radix-2 모델(33사이클)로 이 세 줄을 실행한 사이클이다.

나눗셈 쌍은 GCC가 divu a5,a0,a1 다음 remu a0,a0,a1로 명세 순서 그대로 냈다. 나눗셈기는 몫과 나머지를 동시에 갖고 있으니, 몫·나머지를 함께 저장해 두면 rem이 1사이클에 끝난다. 값 비교 방식은 32비트 비교기 둘과 레지스터 몇 개가 들지만, 피연산자가 바뀌었는지(중간에 같은 레지스터에 쓰기가 있었는지)를 따로 추적할 필요가 없다.

8. 실습: 비트 정확 모델과 QEMU 대조

모델은 한 파일(model.py)이다. 곱셈 코어 2개(radix-2, radix-4 Booth)와 나눗셈 코어 4개(복원, 비복원, 0 건너뛰기, 맞춰 당기기)를 각각 명세 규칙을 파이썬 정수로 옮긴 기준 함수와 대조했다. 입력은 경계값 72개(0, ±1, 0x7fffffff, 0x80000000, 2의 거듭제곱과 그 −1 등)의 모든 쌍 5,184개와, 균등·크기 균등·작은 수 세 분포에서 뽑은 무작위 30만 쌍(시드 19)이다.

QEMU 쪽은 경계값 9개(0, 1, −1, 2, −7, 7, 0x7fffffff, 0x80000000, 0x12345678)의 81쌍에 8개 명령어를 인라인 어셈블리로 실행해 UART로 찍었다(muldiv.c). 그중 0 나누기와 오버플로 줄은 다음과 같았다.

div  0xfffffff9, 0  → 0xffffffff
rem  0xfffffff9, 0  → 0xfffffff9
divu 0xfffffff9, 0  → 0xffffffff
div  0x80000000, -1 → 0x80000000
rem  0x80000000, -1 → 0x00000000

장비는 맥 M1 Max, riscv64-elf-gcc 16.2, QEMU 11.1.3, Python은 uv run이고 전체 모델 실행에 약 40초 걸렸다.

9. 설계 체크리스트: M 확장

명세가 구현에 맡긴 것은 지연과 구조다. 같은 명령어가 1사이클이든 33사이클이든 결과만 같으면 된다. 그래서 같은 RV32IM이라도 곱셈 지연이 1에서 33까지 다양하고, 컴파일러는 이를 모른 채 같은 코드를 낸다.

정리

• 피연산자 위에 1비트를 붙인 33×33 부호 있는 곱셈기 하나로 mul·mulh·mulhsu·mulhu를 모두 처리한다. radix-2는 33사이클, radix-4 Booth는 17사이클이다.
• 부호 없는 반복형 나눗셈기는 0 나누기 명세 값을 저절로 낸다. 부호 있는 래퍼는 "제수 0이면 몫을 부정하지 않음" 조건이 필요했다(없으면 10,072개 중 5,039개 불일치). 오버플로는 특별 처리가 필요 없었다.
• 조기 종료는 평균 반복을 32에서 5.98번까지 줄이지만, 제수 0을 따로 처리하지 않으면 0 나누기 결과가 틀린다.
• 가장 단순한 연동은 busy 동안 앞단 스톨(L − 1사이클)이다. mulh+mul 융합은 GCC가 레지스터를 바꿔 쓰므로 값 비교 방식이 67사이클을 35사이클로 줄였다.

다음 글: 20편에서는 A 확장을 구현한다. LR/SC의 예약 집합을 얼마나 크게 잡고 언제 지우는지, SC가 실패해야 하는 조건과 명세가 요구하는 전진 보장, AMO를 코어 ALU에서 실행할지 메모리 쪽에서 실행할지, 그리고 in-order 코어에서 aq·rl과 FENCE를 어떻게 지키는지를 두 하트가 메모리를 나눠 쓰는 Python 모델로 확인한다.

참고 문헌

• The RISC-V Instruction Set Manual, Volume I: Unprivileged Architecture, Version 20240411. 13장 "M" 확장(13.1 곱셈, 13.2 나눗셈과 표 11, 13.3 Zmmul). https://github.com/riscv/riscv-isa-manual
• D. Harris 외, RISC-V System-on-Chip Design, 2023. 곱셈·나눗셈 장치 구현(CORE-V Wally)
• D. Harris, S. Harris, Digital Design and Computer Architecture: RISC-V Edition, 2021. 5.2절 곱셈기·나눗셈기
• D. Patterson, J. Hennessy, Computer Organization and Design: RISC-V Edition. 3.3~3.4절 곱셈·나눗셈 하드웨어
• A. D. Booth, "A Signed Binary Multiplication Technique", Quarterly Journal of Mechanics and Applied Mathematics, 1951