컴퓨터공학 300 주제 시리즈의 085번째 글이다. 전체 지도는 여기.

한 줄 요약

조합 회로는 출력이 지금 입력만으로 정해지는 회로(덧셈기, 멀티플렉서)이고, 순차 회로는 출력이 과거의 입력, 곧 저장된 상태에도 의존하는 회로(레지스터, 카운터)다. CPU 는 “레지스터에 저장된 상태 → 조합 회로로 계산 → 클록에 맞춰 다시 레지스터에 저장” 을 끝없이 반복하는 기계다.

왜 필요한가

앞 글에서 게이트로 어떤 불 함수든 만들 수 있다는 것을 봤다. 그런데 함수만으로는 컴퓨터가 되지 않는다. 컴퓨터는 값을 기억해야 한다. 프로그램 카운터, 레지스터, 메모리는 모두 상태다.

이 구분은 소프트웨어에도 그대로 있다. 순수 함수와 상태를 가진 객체, 무상태 서비스와 상태 저장 서비스. 하드웨어에서 이 둘이 어떻게 맞물리는지 보면 “클록 속도”, “레지스터”, “한 사이클” 같은 말이 구체적인 뜻을 갖게 된다.

핵심 개념

조합 회로: 입력 → 출력, 기억 없음

출력이 오직 현재 입력의 함수인 회로다. 대표 부품은 다음과 같다.

부품 하는 일 쓰이는 곳
반가산기·전가산기 1비트 덧셈과 캐리 ALU 의 덧셈기
멀티플렉서(MUX) 선택 신호로 여러 입력 중 하나를 고름 레지스터 선택, 분기 결과 선택
디코더 n 비트 입력을 2^n 개 중 하나의 선으로 메모리 주소 해석, 명령어 해독
비교기 두 수의 대소·동등 판정 분기 조건
ALU 덧셈·뺄셈·논리 연산을 제어 신호로 고름 CPU 의 연산 중심

전가산기와 리플 캐리 덧셈기

1비트 전가산기는 두 비트 a, b 와 아래 자리에서 올라온 캐리 cin 을 받아 합 s 와 캐리 cout 을 낸다.

s    = a ⊕ b ⊕ cin
cout = a·b + cin·(a ⊕ b)

이것을 n 개 이어 붙이면 n 비트 덧셈기가 된다.

 a3 b3      a2 b2      a1 b1      a0 b0
  │  │       │  │       │  │       │  │
 ┌┴──┴┐ c3  ┌┴──┴┐ c2  ┌┴──┴┐ c1  ┌┴──┴┐  c0=0
 │ FA │◄────│ FA │◄────│ FA │◄────│ FA │◄──
 └─┬──┘     └─┬──┘     └─┬──┘     └─┬──┘
c4 s3         s2         s1         s0

캐리가 물결처럼 한 칸씩 전파되므로 지연이 비트 수에 비례한다. 64비트에서는 너무 느리다. 그래서 실제 CPU 는 캐리를 미리 계산하는 캐리 예측(carry-lookahead) 같은 구조로 지연을 로그 수준으로 줄인다. 게이트를 더 쓰는 대신 시간을 산다. 하드웨어 설계의 전형적인 거래다.

순차 회로: 상태가 있다

출력이 입력과 현재 상태에 의존한다. 상태를 붙잡아 두는 가장 작은 단위가 래치와 플립플롭이다.

  • SR 래치: NOR 두 개의 출력을 서로의 입력으로 되먹인다. 이 되먹임 고리가 1비트를 기억한다.
  • D 래치: 활성화 신호가 켜져 있는 동안 입력 D 를 그대로 통과시키고, 꺼지면 마지막 값을 유지한다.
  • D 플립플롭: 클록이 0→1 로 바뀌는 순간(상승 에지)에만 D 를 샘플링해 저장한다. 나머지 시간에는 입력이 흔들려도 출력이 변하지 않는다.

여러 개의 D 플립플롭을 나란히 놓으면 레지스터가 된다. 64비트 레지스터는 플립플롭 64개다.

동기식 설계: 클록이 박자를 맞춘다

현대 디지털 회로는 거의 다 동기식이다. 구조는 단순하다.

       ┌──────────────────────────────┐
       │                              │
       ▼                              │
  ┌─────────┐   현재 상태   ┌──────────┐ │ 다음 상태
  │ 레지스터 │──────────────►│ 조합 회로 │─┘
  └─────────┘               └──────────┘
       ▲                        ▲
     클록                       입력
  1. 클록 에지에서 레지스터가 “다음 상태” 를 받아 저장한다.
  2. 다음 에지까지 조합 회로가 새 상태로부터 다음 상태를 계산한다.
  3. 반복.

조건은 하나다. 조합 회로의 계산이 한 클록 주기 안에 끝나야 한다. 정확히는 플립플롭 출력 지연 + 조합 회로 임계 경로 지연 + 플립플롭 설정 시간(setup time) ≤ 클록 주기. 이 부등식이 CPU 의 최대 클록 주파수를 정한다.

유한 상태 기계

상태와 전이 규칙으로 동작을 기술하는 모델이 유한 상태 기계(FSM)다. 하드웨어 FSM 은 “상태 레지스터 + 다음 상태 조합 회로 + 출력 조합 회로” 로 그대로 구현된다. 신호등 제어기, 시리얼 통신 수신기, CPU 의 다중 사이클 제어 장치가 FSM 이다. 소프트웨어의 TCP 상태 전이나 주문 상태 관리와 같은 개념이다.

메모리도 순차 회로다

SRAM 셀은 인버터 두 개를 서로 물린 되먹임 구조로 1비트를 기억한다(보통 트랜지스터 6개). DRAM 셀은 트랜지스터 1개와 축전기 1개로 전하를 담으며, 전하가 새기 때문에 주기적으로 다시 써 주는 리프레시가 필요하다. 이 차이가 SRAM 이 캐시에, DRAM 이 주기억 장치에 쓰이는 이유다(#092 메모리 계층).

직접 해 보기

전가산기로 4비트 덧셈기를 만들고, 그 덧셈기와 D 플립플롭 4개로 4비트 카운터를 만든다. python3 로 실행해 확인했다.

def full_adder(a, b, cin):
    s = a ^ b ^ cin
    cout = (a & b) | (cin & (a ^ b))
    return s, cout

def ripple_add(x, y, n=4):
    carry, out = 0, 0
    for i in range(n):                      # 하위 비트부터 캐리가 물결처럼 전파
        s, carry = full_adder((x >> i) & 1, (y >> i) & 1, carry)
        out |= s << i
    return out, carry

print(ripple_add(0b0110, 0b0011))   # 6 + 3
print(ripple_add(0b1111, 0b0001))   # 15 + 1 -> 넘침

def mux(sel, a, b):                 # 2:1 멀티플렉서
    return (a & (1 - sel)) | (b & sel)
print([mux(s, 0, 1) for s in (0, 1)])

class DFlipFlop:
    def __init__(self): self.q = 0
    def tick(self, d):              # 클록 상승 에지에서만 d 를 저장
        self.q = d
        return self.q

class Counter4:                     # 상태(레지스터) + 조합 회로(덧셈기)
    def __init__(self): self.reg = [DFlipFlop() for _ in range(4)]
    def value(self): return sum(ff.q << i for i, ff in enumerate(self.reg))
    def tick(self):
        nxt, _ = ripple_add(self.value(), 1)   # 다음 상태 = 현재 + 1
        for i, ff in enumerate(self.reg):
            ff.tick((nxt >> i) & 1)

c = Counter4()
seq = []
for _ in range(18):
    seq.append(c.value()); c.tick()
print(seq)

출력:

(9, 0)
(0, 1)
[0, 1]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1]

카운터는 15 다음에 0 으로 돌아간다. 4비트 레지스터가 2^4 를 넘는 값을 담지 못하기 때문이다(#082 오버플로와 같은 현상이다). tick() 이 클록 에지 역할을 한다. 두 번 부르지 않는 한 값은 변하지 않는다.

현업에서는

  • 클록 주파수의 의미: CPU 사양의 GHz 는 이 동기식 루프가 1초에 몇 번 도는지다. 주파수를 무작정 못 올리는 이유는 임계 경로 지연과 전력·발열이다. 그래서 같은 주파수에서 한 사이클에 더 많은 일을 하는 방향(파이프라인, 슈퍼스칼라, 멀티코어)으로 발전했다.
  • 상태 기계로 설계하기: 결제·배포·잡 스케줄러처럼 상태가 많은 기능은 상태와 허용 전이를 표로 먼저 그리면 버그가 줄어든다. 쿠버네티스 파드의 Pending → Running → Succeeded/Failed 같은 단계도 같은 사고방식으로 읽을 수 있다.
  • 멱등성과 순수성: 조합 회로처럼 같은 입력에 같은 출력을 내는 코드는 테스트와 캐싱이 쉽다. 상태는 레지스터처럼 정해진 경계(DB, 상태 저장 서비스)에 모아 두는 것이 운영을 편하게 한다.

확인 문제

  1. 조합 회로와 순차 회로를 가르는 기준은 무엇인가.
  2. D 래치와 D 플립플롭의 차이는.
  3. 리플 캐리 덧셈기의 지연이 비트 수에 비례하는 이유는.
  4. 동기식 회로에서 클록 주기의 하한을 정하는 요소 세 가지를 적어라.

풀이

  1. 출력이 현재 입력만으로 정해지면 조합, 저장된 상태에도 의존하면 순차다.
  2. 래치는 활성화 신호가 켜진 동안 계속 입력을 통과시키고(레벨 감지), 플립플롭은 클록 에지 순간에만 입력을 저장한다(에지 감지).
  3. 각 자리의 합이 아래 자리 캐리를 기다려야 해서 캐리가 최하위에서 최상위까지 차례로 전파되기 때문이다.
  4. 플립플롭 출력 지연, 조합 회로의 임계 경로 지연, 플립플롭의 설정 시간.

더 읽을거리 (References)