da4ml: Distributed Arithmetic for Real-time Neural Networks on FPGAs

이 논문은 FPGA 기반 실시간 신경망 추론을 위해 분산 산술(Distributed Arithmetic)을 활용하여, 기존 방식 대비 연산 속도는 높이면서도 칩 면적 사용량은 최대 3분의 1까지 줄일 수 있는 효율적인 CMVM(상수 행렬-벡터 곱셈) 알고리즘을 제안하고 이를 `hls4ml` 라이브러리에 통합했습니다.

핵심

1. 문제 상황: "초고속 요리사가 필요한 초미니 주방"

상상해 보세요. 당신은 세계에서 가장 빠른 레스토랑의 요리사입니다. 손님들은 음식이 나오기까지 **0.000001초(마이크로초)**도 기다리지 못합니다. 게다가 주방(FPGA 하드웨어)은 아주 좁아서, 요리 도구(자원)를 조금만 많이 써도 주방이 꽉 차서 더 이상 요리를 할 수 없습니다.

지금까지의 방식은 요리할 때마다 매번 재료를 하나하나 다 썰고 볶는 방식(기존의 계산 방식)이었습니다. 이 방식은 정확하긴 하지만, 시간이 너무 오래 걸리고 도구(공간)를 너무 많이 차지한다는 단점이 있었습니다.

2. 해결책: da4ml — "마법의 레시피와 미리 준비된 재료"

연구팀은 **da4ml**라는 새로운 '마법의 레시피'를 개발했습니다. 이 레시피의 핵심 원리는 두 가지입니다.

① "비슷한 재료는 한 번에 처리하기" (그래프 기반 분해)

기존에는 양파 10개를 썰어야 하면 10번을 따로 썰었습니다. 하지만 da4ml는 "어? 이 양파 10개는 모양이 거의 비슷하네?"라고 알아차립니다. 그래서 비슷한 재료들을 하나의 덩어리로 묶어서 한 번에 처리하는 방식을 사용합니다. 이를 통해 요리 도구(하드웨어 자원)를 훨씬 적게 쓰면서도 속도는 높였습니다.

② "중복되는 동작 찾아내기" (공통 부분식 제거)

요리를 하다 보면 "소금 뿌리기"라는 동작이 계속 반복될 수 있습니다. da4ml는 이 반복되는 동작을 미리 파악해서, **"한 번만 소금을 뿌려두고, 그 결과물을 여기저기 돌려쓰자!"**라고 제안합니다. 이를 통해 불필요한 움직임을 줄여 요리 시간을 획기적으로 단축했습니다.

3. 결과: "더 작아진 주방, 더 빨라진 요리"

이 마법의 레시피를 적용했더니 놀라운 결과가 나왔습니다.

• 공간 절약: 주방 도구(하드웨어 자원)를 최대 1/3이나 줄였습니다. 덕분에 예전에는 너무 커서 들어가지 못했던 복잡한 요리(대규모 AI 모델)도 이 작은 주방에서 만들 수 있게 되었습니다.
• 속도 향상: 요리 시간(지연 시간)이 훨씬 짧아졌습니다.
• 압도적인 효율: 기존의 가장 똑똑한 방식보다 계산 속도가 무려 10만 배나 빨라졌습니다.

4. 요약하자면?

이 논문은 **"AI라는 거대한 요리를, 아주 좁고 바쁜 하드웨어 주방에서도 빛의 속도로 만들어낼 수 있도록 만드는 똑똑한 자동화 시스템"**을 만든 것입니다.

이 기술 덕분에 유럽 입자 물리 연구소(CERN) 같은 곳에서 엄청난 양의 데이터를 실시간으로 분석할 때, 훨씬 더 정확하고 빠른 AI를 사용할 수 있게 되었습니다.

기술 요약

[기술 요약] da4ml: FPGA 기반 실시간 신경망을 위한 분산 산술(Distributed Arithmetic) 최적화

1. 문제 정의 (Problem Statement)

CERN의 대형 강입자 충돌기(LHC)와 같은 초고속 데이터 처리 환경에서는 마이크로초($\mu s$) 단위의 극도로 낮은 추론 지연 시간(Latency)이 요구됩니다. 이를 위해 신경망을 FPGA에 구현할 때, 연산 속도를 극대화하기 위해 모든 레이어를 완전히 펼치고 파이프라이닝(Fully unrolled and pipelined)하는 방식을 사용합니다.

이 방식의 핵심적인 병목 현상은 상수 행렬-벡터 곱셈(Constant Matrix-Vector Multiplication, CMVM) 연산에서 발생하는 막대한 **자원 소모(Area utilization)**입니다. 특히 FPGA의 LUT(Look-Up Table) 사용량이 급증하여, 복잡한 모델을 하나의 칩에 구현하는 것이 물리적으로 불가능해지는 문제가 발생합니다. 기존의 최적화 알고리즘들은 연산 시간이 너무 오래 걸리거나(예: $H_{cmvm}$), 비트 시프트(Bit-shift)나 부호(Sign)가 다른 공통 부분식을 제대로 찾아내지 못하는 한계가 있었습니다.

2. 제안 방법론 (Methodology: da4ml 알고리즘)

본 논문은 CMVM 연산을 최적화하기 위해 **그래프 기반 분해(Graph-based decomposition)**와 **비용 인식 공통 부분식 제거(Cost-aware Common Subexpression Elimination, CSE)**를 결합한 하이브리드 알고리즘인 da4ml를 제안합니다.

• 1단계: 그래프 기반 분해 (Graph-based Decomposition):
  행렬의 각 열(Column)을 그래프의 정점(Vertex)으로 간주하고, 열 간의 유사성을 기반으로 최소 신장 트리(Minimum Spanning Tree, MST)를 구성합니다. 이를 통해 행렬 $M$을 두 개의 희소 행렬 $M_1$과 $M_2$로 분해($M = M_1M_2$)하여, 고수준의 패턴을 먼저 추출합니다.
• 2단계: 비용 인식 CSE (Cost-aware CSE):
  분해된 행렬에 대해 CSE를 적용합니다. 단순히 빈도가 높은 식을 찾는 것이 아니라, **연산 비용 함수(Cost function)**를 도입합니다. 즉, 두 피연산자(Operand) 간의 비트 폭(Bitwidth)과 시프트 값이 유사하여 LUT 소모를 최소화할 수 있는 부분식을 우선적으로 선택합니다.
• 구현 특징:
  • 정밀도 유지: 근사 계산(Approximation)을 사용하지 않고 수치적 정밀도를 완벽하게 유지합니다.
  • CSD(Canonical Signed Digit) 활용: 비트 표현을 최적화하여 덧셈/뺄셈 연산 횟수를 최소화합니다.
  • 효율적인 복잡도: 기존 알고리즘보다 훨씬 빠른 $O(N^2)$의 시간 복잡도를 가집니다.

3. 주요 기여 (Key Contributions)

1. 새로운 최적화 프레임워크: 자원 효율성과 계산 속도를 동시에 잡은 혁신적인 CMVM 최적화 알고리즘을 제안했습니다.
2. 오픈소스 라이브러리 및 통합: da4ml를 오픈소스로 공개하였으며, FPGA 신경망 구현의 표준 도구인 hls4ml 라이브러리에 드롭인(Drop-in) 방식으로 통합하여 사용성을 극대화했습니다.
3. 직접 RTL 생성 지원: HLS(High-Level Synthesis)를 거치지 않고도 직접 Verilog/VHDL 코드를 생성할 수 있는 기능을 제공하여 빠른 프로토타이핑을 가능하게 했습니다.

4. 실험 결과 (Results)

다양한 벤치마크와 실제 물리 실험용 신경망을 통해 검증한 결과는 다음과 같습니다.

• 연산 효율성: 무작위 행렬 테스트 결과, 기존 최적화 알고리즘($H_{cmvm}$) 대비 계산 속도가 약 $10^5$배(10만 배) 빠르면서도, 자원 사용량(Adder 개수)은 대등하거나 더 우수한 수준을 보였습니다.
• 자원 절감: 실제 신경망(Jet Tagging, SVHN, Muon Tracking 등) 적용 시, LUT 사용량을 최대 1/3까지 줄였으며, DSP 사용량을 0으로 제거하는 성과를 거두었습니다.
• 지연 시간 및 타이밍: 지연 시간을 줄임과 동시에 타이밍 클로저(Timing closure)를 개선하여, 기존에는 구현이 불가능했던 복잡한 모델을 FPGA에 성공적으로 배치할 수 있음을 증명했습니다.
• 컴파일 속도: hls4ml를 통한 HLS 방식보다 da4ml를 통한 직접 RTL 생성 방식이 합성(Synthesis) 시간을 획기적으로 단축(예: 17시간 $\rightarrow$ 26분)시켰습니다.

5. 의의 (Significance)

이 연구는 고에너지 물리학(HEP) 분야의 극단적인 실시간 요구사항을 충족시키는 동시에, 일반적인 에지 컴퓨팅(Edge Computing) 환경에서도 저전력·고효율 FPGA 신경망 가속기를 설계하는 데 매우 중요한 기술적 토대를 제공합니다. 특히, 기존의 LUT 기반 근사 모델(LUT-based methods)들이 가진 정확도 저하 문제를 해결하면서도 높은 자원 효율성을 달성했다는 점에서 실용적 가치가 매우 높습니다.