611. 분산 산술 (Distributed Arithmetic) 매크로

핵심 인사이트 (3줄 요약)

본질: 분산 산술 (Distributed Arithmetic, DA)은 고정 계수 내적을 비트 단위로 재배열해, 곱셈기 대신 룩업 테이블 (Look-Up Table, LUT)과 시프트 누산기로 처리하는 연산 구조다.

가치: 유한 임펄스 응답 필터 (Finite Impulse Response Filter, FIR)나 이산 코사인 변환 (Discrete Cosine Transform, DCT)처럼 계수가 고정된 디지털 신호 처리 (Digital Signal Processing, DSP)에서는, DA가 필드 프로그래머블 게이트 어레이 (Field-Programmable Gate Array, FPGA)의 LUT 자원을 직접 성능으로 바꿔 준다.

판단 포인트: 계수 수가 늘수록 LUT 크기가 지수적으로 커지므로, 비트 직렬/병렬 선택, 파티셔닝, 옵셋 바이너리 코딩 (Offset Binary Coding, OBC), 누산기 비트폭 설계가 DA 채택의 성패를 좌우한다.

Ⅰ. 개요 및 필요성

분산 산술은 "곱셈을 꼭 실시간으로 해야 하는가"라는 질문에서 출발한 하드웨어 최적화 기법이다. 많은 DSP 알고리즘은 y = Σ c_i x_i 형태의 내적을 반복한다. 이때 계수 c_i가 고정되어 있다면, 매 샘플마다 곱셈기를 돌리는 대신 가능한 부분합을 미리 계산해 두고 주소로 꺼내 올 수 있다.

이 방식이 필요한 이유는 곱셈기가 빠르지만 공짜가 아니기 때문이다. 작은 FPGA나 저전력 시스템에서는 전용 DSP 슬라이스가 부족할 수 있고, 필터 탭이 수십 개만 되어도 곱셈기 수가 급격히 늘어난다. 반면 일반 LUT 자원은 상대적으로 넉넉한 경우가 많아, 고정 계수 문제를 LUT 중심 구조로 다시 쓰면 면적과 타이밍 모두 유리해질 수 있다.

즉 DA는 연산을 없애는 기술이 아니라, 연산 시점을 바꾸는 기술이다. 설계 시점에 가능한 합을 미리 준비하고, 실행 시점에는 주소 선택과 누산만 한다. 그래서 DA는 "산술 회로"이면서 동시에 "메모리 기반 계산"이다.

📢 섹션 요약 비유: DA는 시험장에서 매번 긴 곱셈을 푸는 학생이 아니라, 자주 나오는 정답을 미리 카드에 적어 두고 필요한 순간 꺼내 보는 학생과 같다. 준비를 많이 할수록 시험 시간은 짧아진다.

Ⅱ. 아키텍처 및 핵심 원리

DA의 핵심은 시그마 순서를 바꾸는 것이다. 고정 계수 내적을 비트로 분해하면 다음처럼 볼 수 있다.

y = Σ c_i x_i
  = Σ_b 2^b · (Σ c_i x_i[b])

여기서 x_i[b]는 각 입력의 b번째 비트다. 괄호 안쪽 합은 해당 비트들이 0/1로 어떤 조합을 이루느냐에 따라 정해지는 상수의 합이므로, 가능한 결과를 LUT에 저장할 수 있다. 실행 시에는 입력들의 같은 비트 위치를 모아 주소를 만들고, LUT에서 부분합을 읽어 와 시프트 누산한다.

┌────────────────────────────────────────────────────────────────────────────┐
│ x0[b] x1[b] x2[b] ... xK-1[b]  ->  address bits                           │
│                                      │                                     │
│                                      ▼                                     │
│                           LUT of precomputed sums                          │
│                                      │                                     │
│                                      ▼                                     │
│                         shift / accumulate over bit index b                │
│                                      │                                     │
│                                      ▼                                     │
│                                     output y                               │
└────────────────────────────────────────────────────────────────────────────┘

구성 요소	역할	설계 포인트
입력 시프트 레지스터	동일 비트 위치 추출	비트 직렬이면 샘플당 B사이클이 필요하다
LUT	부분합 저장	계수 수 K에 대해 크기가 `2^K`로 증가한다
시프트 누산기	비트 가중치 반영	오버플로와 파이프라인 균형이 중요하다
부호 처리	음수 입력/계수 대응	OBC 또는 sign-bit 보정이 필요하다

DA의 장점은 명확하지만, 그대로 두면 LUT 폭발 문제가 생긴다. 예를 들어 16개 계수를 한 LUT에 넣으면 65,536개 엔트리가 필요하다. 그래서 실제 설계에서는 4개 혹은 6개 단위로 파티셔닝해 여러 작은 LUT와 가산 트리로 쪼갠다. 즉 DA의 진짜 기술은 수식 자체보다도 "테이블을 얼마나 잘 분해하느냐"에 있다.

📢 섹션 요약 비유: DA 아키텍처는 재료를 한 번에 다 볶는 큰 팬이 아니라, 미리 손질한 소스들을 작은 통에 나눠 담아 두고 주문이 오면 빠르게 섞는 주방과 같다. 정리 방식이 곧 속도다.

Ⅲ. 비교 및 연결

DA는 모든 곱셈을 대체하는 만능 해법이 아니다. 특히 계수가 자주 바뀌는 경우에는 전통적인 곱셈-누산기 (Multiply-Accumulate, MAC)가 더 낫다. 핵심은 문제의 구조가 고정 계수인지, 그리고 FPGA 자원이 무엇이 남아 있는지다.

항목	전통적 MAC	분산 산술 (DA)
계수 변경	런타임 변경에 강함	고정 계수에 최적
핵심 자원	DSP 슬라이스, 곱셈기	LUT, 레지스터, 가산기
지연 구조	곱셈기 임계 경로 존재	LUT 접근 + 누산 경로
규모 확장	탭 수만큼 곱셈기 증가	LUT 크기 관리가 핵심
잘 맞는 작업	적응형 필터, 범용 DSP	FIR, DCT, 웨이블릿, 고정 커널 연산

DA 내부에서도 구조 선택이 갈린다. 비트 직렬형은 하드웨어가 작지만 샘플 하나를 끝내는 데 입력 비트 수만큼 클럭이 든다. 반대로 비트 병렬형은 여러 비트 평면을 동시에 처리해 빠르지만 LUT 뱅크와 누산 경로가 크게 늘어난다. 따라서 샘플링 주파수, 입력 비트폭, 허용 면적을 동시에 봐야 한다.

연결 관점에서는 JPEG의 DCT, 음성 처리용 FIR, 저비트 인공신경망이 대표적이다. 이들은 모두 "고정된 계수와 반복되는 내적"이라는 공통 구조를 가진다. 그래서 DA는 고전 DSP 기법이면서, 동시에 저정밀 인공지능 가속기에서 다시 주목받는 현대적 기법이기도 하다.

📢 섹션 요약 비유: 일반 MAC가 만능 공구함이라면, DA는 자주 쓰는 작업에 맞춰 미리 세팅된 전용 지그다. 작업이 반복될수록 전용 지그가 훨씬 효율적이다.

Ⅳ. 실무 적용 및 기술사 판단

DA를 채택할지 여부는 계수 고정성, 목표 샘플링 속도, FPGA 자원 맵을 함께 봐야 한다. 예를 들어 16비트 입력을 비트 직렬 DA로 처리하면, 한 출력 샘플당 기본적으로 16클럭이 필요하다. 따라서 샘플링 속도가 Fs라면 최소 fclk >= 16 × Fs가 되어야 하며, 여기에 파이프라인 오버헤드와 여유 마진도 더해야 한다.

실무 판단 포인트

고정 계수 필터: DSP 슬라이스가 부족한 저가형 FPGA라면 DA가 강력한 대안이다.
가변 계수/적응형 필터: 계수 갱신이 잦으면 LUT 재구성이 부담이므로 일반 MAC가 유리하다.
대규모 탭 수: 4~6입력 LUT 크기에 맞춰 파티셔닝하고, 부분합을 트리로 합쳐야 한다.
부호·스케일 관리: OBC, sign extension, saturation 정책 없이는 계산 결과가 틀어지기 쉽다.

체크리스트

계수가 충분히 고정적이라 LUT 사전 계산이 의미 있는가?
LUT 크기가 타깃 FPGA의 기본 LUT 입력 수와 잘 맞는가?
누산기 비트폭이 입력 비트폭 + 계수 비트폭 + log2(탭 수) 수준의 성장 여유를 갖는가?
비트 직렬 구조라면 필요한 처리량을 클럭과 파이프라인으로 감당할 수 있는가?

피해야 할 안티패턴

탭 수가 큰데도 무작정 단일 거대 LUT 하나로 구현하려는 설계
계수가 계속 바뀌는 적응형 시스템에 DA를 억지로 적용하는 설계
LUT 절감에만 집중하다가 누산기 오버플로와 정밀도 손실을 무시하는 설계
📢 섹션 요약 비유: DA 실무 설계는 창고 정리와 같다. 물건을 미리 분류해 두면 일은 빨라지지만, 칸을 너무 크게 잡거나 자주 바뀌는 물건까지 억지로 고정 칸에 넣으면 오히려 더 혼란스러워진다.

Ⅴ. 기대효과 및 결론

분산 산술의 가장 큰 효과는 고정 계수 계산을 FPGA의 본래 강점인 LUT 구조와 직접 결합시킨다는 점이다. 곱셈기를 덜 쓰고도 높은 병렬성과 예측 가능한 타이밍을 얻을 수 있어, 영상·음성·통신 필터링 같은 반복 작업에서 매우 효율적이다. 특히 DSP 슬라이스가 모자란 환경에서는 "남는 LUT를 성능으로 바꾸는" 실질적 수단이 된다.

반대로 LUT 크기 증가와 비트 직렬 지연은 항상 경계해야 한다. DA가 빛나는 영역은 분명하지만, 모든 내적 문제에 적용하는 순간 오히려 메모리와 제어 복잡도가 발목을 잡는다. 그래서 현대 설계에서는 DA, MAC, LUT-less 구조를 혼합해 쓰는 하이브리드 접근이 많다.

결론적으로 DA는 곱셈기를 없애는 기술이 아니라, 문제 구조를 읽고 계산을 기억장치 친화적으로 재배치하는 아키텍처 사고방식이다. 이 관점을 이해하면 왜 오래된 DSP 기법이 오늘날 FPGA와 저정밀 AI 하드웨어에서 다시 중요해지는지 보인다.

📢 섹션 요약 비유: DA는 무거운 짐을 힘으로 드는 대신, 미리 상자를 분류하고 가장 짧은 동선으로 옮기게 만드는 물류 시스템과 같다. 계산 능력보다 배치 전략이 이긴다.

📌 관련 개념 맵

개념	연결 포인트
LUT (Look-Up Table)	DA가 곱셈기 대신 활용하는 핵심 하드웨어 자원이다.
FIR Filter	고정 계수 내적이 반복되는 대표 응용처로 DA와 궁합이 좋다.
OBC (Offset Binary Coding)	부호 처리를 단순화하고 LUT 크기 최적화에 도움을 주는 기법이다.
Bit-Serial Architecture	면적을 줄이는 대신 여러 클럭에 걸쳐 출력을 완성하는 DA의 대표 구현 방식이다.
DSP Slice	DA가 대체하거나 보완하는 FPGA 전용 곱셈 자원이다.
Low-Precision AI	반복 내적과 저비트 연산 특성 덕분에 DA 응용이 다시 확대되는 분야다.

📈 관련 키워드 및 발전 흐름도

고정 계수 내적 문제
        │
        ▼
비트 직렬 분산 산술
        │
        ▼
파티셔닝 · OBC 기반 LUT 축소
        │
        ▼
비트 병렬 · 파이프라인 DA
        │
        ▼
LUT-less / 하이브리드 MAC-DA 구조
        │
        ▼
저정밀 AI · FPGA 가속기 응용

이 흐름은 DA가 전통적 FIR 최적화 기법에서 출발해, 자원 제약형 가속기 전반으로 확장되는 과정을 보여 준다.

👶 어린이를 위한 3줄 비유 설명

어려운 곱셈 문제를 매번 풀지 않고, 자주 쓰는 답을 미리 카드 상자에 넣어 두는 거예요.
필요할 때는 카드만 빨리 꺼내 더하면 되니까 훨씬 빠르고 힘이 덜 들어요.
그래서 작은 컴퓨터도 많은 계산을 똑똑하게 해낼 수 있어요.