HN 소개: 곱셈 횟수를 절반으로 줄인 행렬 곱셈

 (github.com/trevorpogue)
3P by GN⁺ | ★ favorite | 댓글 1개
  • 이 저장소는 GEMM 및 딥러닝 하드웨어 가속기에서 더 적은 하드웨어 자원이나 실행 시간으로 같은 행렬 곱셈 결과를 계산하는 systolic array 아키텍처를 검증하기 위한 소스 코드임
  • 제안된 방식은 일부 행렬 곱셈을 더 저렴한 저비트폭 덧셈으로 바꾸며, 같은 성능에 필요한 multiplier를 절반으로 줄이거나 MAC 단위당 성능을 높이는 것을 목표로 함
  • 결과는 유사한 컴퓨트 플랫폼의 최신 가속기 대비 CNN 추론 최대 3× 가속, multiplier/clock당 곱셈 처리량 2× 이상, 낮은 면적과 높은 클럭 주파수를 달성함
  • 적용 범위는 dense matrix multiplication과 이를 주로 사용하는 fully-connected layer, CNN, RNN, attention layer/transformer model이며, 주로 고정소수점·양자화 추론에서 기존 방식과 동일한 출력을 생성함
  • 아키텍처는 기존 systolic array와 같은 기능·인터페이스를 유지하도록 설계되어, 추가 전처리나 후처리 없이 기존 가속기 시스템의 MXU를 교체하는 방식으로 통합 가능함

프로젝트 목적과 성과

  • Algebraic Enhancements for GEMM & AI Accelerators는 GEMM과 딥러닝 하드웨어 가속기 시스템의 소스 코드를 담고 있음
  • 이 시스템은 제안되었거나 아직 충분히 탐구되지 않은 효율적 행렬 곱셈 알고리듬을 하드웨어에서 구현하는 systolic array 아키텍처를 검증하는 데 사용됨
  • 목표는 같은 출력을 더 적은 하드웨어 자원이나 더 짧은 실행 시간으로 계산하는 것임
  • 결과로 제시된 성능은 다음과 같음
    • 같은 유형의 컴퓨트 플랫폼에 구현된 최신 가속기 대비 CNN 추론 최대 3× 빠름
    • conventional limit인 1을 넘는 mults/multiplier/clock cycle 2× 이상
    • 낮은 면적과 높은 클럭 주파수

논문과 박사학위 논문에서 검증된 아키텍처

MAC·multiplier당 성능을 높이는 이유

  • 딥러닝 모델의 계산 작업 대부분은 일반적으로 matrix multiplication으로 매핑될 수 있으며, 이는 multiply-accumulate 연산의 연속으로 구성됨
  • 추가적인 algebraic innovation이 없으면 딥러닝 가속기의 처리량은 clock cycle당 수행 가능한 MAC 연산 수의 최대치로 제한됨
  • 딥러닝 가속기는 많은 MAC unit을 포함하므로, multiplier와 MAC unit은 GEMM 및 딥러닝 가속기에서 하드웨어 면적을 크게 차지하는 compute resource가 되기 쉬움
  • accelerator의 처리량은 하드웨어 예산이 감당할 수 있는 multiplier 수에 직접 제한될 수 있음
    • FPGA 구현에서는 MAC unit을 인스턴스화하는 DSP unit이 LUT와 register보다 먼저 부족해질 수 있음
  • 이 프로젝트는 matrix multiplication 알고리듬과 custom hardware 구현에 algebraic enhancement를 적용해 이 제한을 넘는 방향을 탐구함

적용 범위와 제약

  • 제안된 systolic array 하드웨어 아키텍처는 dense matrix multiplication 가속을 개선함
  • matrix multiplication으로 주로 분해되는 DNN 모델과 layer에서 활용 가능함
    • fully-connected layer
    • CNN
    • RNN
    • attention layer 및 transformer model
  • 대부분의 기여는 고정소수점 데이터 타입과 양자화 신경망 추론에 초점을 둠
    • 일부 고정소수점 개념은 향후 floating point로 확장 가능할 수 있음
    • 고정소수점 데이터 타입을 사용하므로 제시된 알고리듬과 하드웨어 아키텍처는 기존 알고리듬·아키텍처와 동일한 출력을 생성함
    • numerical stability에는 변화가 없음
  • 결과는 FPGA에서 검증되었지만, 제안된 아키텍처는 일반적이며 대부분의 개선은 custom integrated circuit과 FPGA 구현 모두에 적용 가능함
  • 아키텍처는 systolic array 기반임
    • Google TPU 같은 GEMM 및 딥러닝 가속 설계에 쓰이는 효율적인 설계 유형임
    • 일부 개념은 향후 non-systolic array 설계로 확장 가능할 수 있음
    • 기존 systolic array와 동일한 기능과 인터페이스를 유지함
    • algebraic enhancement는 systolic array 내부에 완전히 self-contained되어 추가 전처리나 후처리 단계가 필요 없음

성능 결과 미리보기

  • [1]과 [3]의 아키텍처를 결합한 합성 및 성능 결과는 유사한 컴퓨트 플랫폼의 최신 가속기와 비교해 다음을 달성함

가속기 시스템 구조

  • 소스 코드에 구현된 딥러닝 가속기 시스템은 [1]-[4]에서 제안된 systolic array를 host하고 검증하는 데 사용됨
  • 시스템 구현은 non-sparse DNN model의 고정소수점·양자화 입력 추론에 특화됨
    • convolutional layer
    • fully-connected layer
    • pooling layer
  • 모든 DNN layer는 하드웨어에서 완전히 가속됨
  • 단일 하드웨어 설계에서 arbitrary layer dimensions와 kernel sizes를 가진 ML model을 가속할 수 있음
  • input bitwidth와 systolic array dimension은 parameter로 설정 가능함
  • 일반적인 GEMM accelerator로도 고도로 최적화되어 있음

주요 블록

  • Matrix Multiply Unit / MXU

    • 행렬 곱셈을 수행하는 systolic array 아키텍처를 포함함
    • [1]-[4]의 각 방법에서 제안된 서로 다른 systolic array/MXU가 시스템의 MXU 자리에 교체됨

  • GEMM Unit

    • MXU, SRAM, addition logic을 포함함
    • matrix tile을 누적해 임의 크기 행렬의 GEMM 실행을 가능하게 함

  • Post-GEMM Unit

    • matrix multiplication 출력에 neural network-specific function을 수행함
    • bias 추가, quantization을 위한 inter-layer rescaling, activation, padding, pooling을 포함함

  • Memory Unit

    • layer activation을 보관하는 on-chip SRAM과 memory access control logic을 포함함
    • data duplication이나 delay 없이 convolution을 GEMM으로 in-place 매핑하는 효율적 caching 및 memory access hardware 알고리듬을 구현함
    • SRAM memory와 control을 half 또는 quarter clock rate로 실행하면서 full clock rate로 새 데이터를 출력하는 memory partitioning scheme을 사용해 전체 system frequency와 power를 개선함

  • Off-chip DDR DRAM

    • weights 저장에 사용됨

  • RxTx Unit

    • host와 연결되는 PCIe interface를 담당함

  • Instruction Unit

    • host가 보낸 accelerator instruction을 decoding함
    • 단일 하드웨어 설계에서 arbitrary layer dimensions와 kernel sizes를 가진 ML model을 가속할 수 있게 함

소스 코드 구성

  • compiler
    • Python ML model description을 accelerator instruction으로 파싱하는 compiler
    • PCIe driver와 인터페이스해 accelerator에서 model execution을 시작하고, 결과와 performance counter를 읽고, correctness를 테스트하는 코드 포함
  • rtl
    • 합성 가능한 SystemVerilog accelerator RTL
  • sim
    • 검증용 simulation environment 설정 스크립트
  • tests
    • Python과 cocotb로 작성된 UVM testbench 소스 코드
  • utils
    • 프로젝트에서 사용한 추가 Python package와 개발용 utility script
  • rtl/top/define.svh와 rtl/top/pkg.sv
    • 여러 configurable parameter를 포함함
    • FIP_METHOD는 systolic array type을 정의하며 baseline, FIP, FFIP [1] 등이 예시임
    • SZI와 SZJ는 systolic array의 height와 width를 정의함
    • LAYERIO_WIDTH와 WEIGHT_WIDTH는 input bitwidth를 정의함
  • rtl/arith
    • mxu.sv와 mac_array.sv를 포함함
    • FIP_METHOD 값에 따라 baseline 및 제안된 일부 systolic array 아키텍처인 FIP, FFIP [1]의 RTL을 담고 있음

추가 문서

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 꽤 멋져 보이는데, 함정이 뭘까? 예를 들어 왜 이미 가속기에 구현되어 있지 않은지 궁금함
    정말 잊힌 알고리즘일 뿐인지, 아니면 가속기 제작 비용 등에 영향을 주는 제약이 있는지 궁금함

    • 단순한 소프트웨어 알고리즘이 아니라 하드웨어 아키텍처 최적화임
      이득을 보려면 알고리즘의 차원에 맞는 하드웨어를 만들어야 하고, 그건 비용이 큰 결정임
    • 고정소수점 행렬 곱셈 가속기라면 특별한 함정은 없고, 그냥 간과된 알고리즘이라고 봄
      Winograd의 알고리즘에 기반하는데, 우연히도 Winograd가 나중에 CNN 가속에서 매우 유명해진 별개의 알고리즘도 제안해서 이 알고리즘이 덜 주목받았을 수 있음. 다만 이건 추측임
    • 행렬 곱셈 알고리즘은 많고 각각 장단점이 큼
      항상 정확도, 실행 시간, 확장성 사이의 균형인데, 이 방식은 부동소수점에서는 정확도가 나쁠 가능성이 있음
    • 완전히 잊힌 건 아님
      UMAC 같은 의사 내적 기반 Wegman-Carter 인증자 안에 어느 정도 남아 있음. 배경은 [1]의 3장을 보면 됨
      [1] https://cr.yp.to/antiforgery/pema-20071022.pdf
    • 대충 훑어본 수준이라 틀렸으면 정정해 달라면, 이건 행렬 곱셈의 대체가 아니라 AI/ML에서 보이는 종류의 선형 시스템에 꽤 괜찮은 결과를 내는 근사 방식으로 이해했음
      그 용도라면 충분히 괜찮은 것 아닌가 싶음

  • 2018년에 비슷한 걸 해보려다 박사과정 지원이 전부 떨어져서 접었던 게 떠오름
    https://github.com/ixaxaar/pytorch-dni
    여기 개념은 한 걸음 더 나아가, 외부 네트워크로 역전파를 복제하려고 하며 뇌가 실제로 그렇게 할 가능성이 있다고 주장함

    • 연결점을 잘 모르겠음
      이 작업은 행렬 곱셈의 저수준 최적화이고, 링크한 저장소는 역전파된 기울기를 더 싼 추정값으로 대체하려는 것처럼 보임. 둘 사이의 유사점이 무엇인지 궁금함
    • 이건 공짜 점심은 없다에 가까운 상황처럼 느껴짐
      이렇게 기울기를 근사해서 아낀 시간은 기울기 정확도 손실 때문에 더 많은 반복 학습이 필요해지면서 사라질 것 같은데, 그렇지 않은가?
    • 기술 논의와는 별개로, 그 아키텍처 GIF를 뭘로 만들었는지 궁금함. 보기 좋음

  • 정말 흥미롭고 읽을 만함. 댓글에서 왜 더 나은지 헷갈리는 사람들을 위해 말하면, 논문은 FPGA나 ASIC 같은 하드웨어에서 행렬 곱셈 파이프라인을 합성하는 얘기임
    CPU나 GPU에서는 덧셈과 곱셈 시간이 대체로 비슷해서 체감하기 어렵지만, 곱셈 유닛은 훨씬 많은 트랜지스터를 차지함. 회로 복잡도를 줄이면 속도와 병렬 처리량을 높이고 전력과 배선 복잡도를 낮출 수 있음. 이 접근은 효율적인 희소 행렬 곱셈 가속기에 특히 유용할 수 있음
    행렬 곱셈에서 곱셈을 없애는 또 다른 멋진 방법은 다른 반환(semiring) 을 쓰는 것임 [1]. 예를 들어 Tropical Semiring [2]은 곱셈을 덧셈으로, 덧셈을 min 또는 max로 대체함. 여전히 행렬 곱셈이지만 이항 연산이 바뀐 형태임. 비교적 새로운 분야인 Tropical Algebra [3] 연구는 지금 꽤 활발하고 풍부하며, 다양한 최적화 문제와 신경망 최적화 연구 [4]에 쓰이고 있음
    이 방식도 하드웨어 합성에 잘 맞는데, 대부분의 FPGA 구성 가능 논리 블록은 한 클럭에 add/min/max를 할 수 있는 반면, 효율적인 곱셈에는 고정된 전용 온칩 하드웨어 곱셈기가 필요하기 때문임
    관련된 다른 반환으로 곱셈을 효율적으로 제거하는 방법은 로그 반환(Log Semiring) [5]을 쓰는 것임. 마르코프 체인처럼 확률을 연쇄적으로 곱해야 하면 숫자가 금방 매우 작아져 부동소수점 정확도가 떨어짐. 먼저 로그를 취해 스케일링하면 곱셈은 덧셈이 되고, 덧셈은 x + log1p(exp(y - x))가 됨
    [1] https://en.wikipedia.org/wiki/Semiring
    [2] https://en.wikipedia.org/wiki/Tropical_semiring
    [3] https://en.wikipedia.org/wiki/Tropical_geometry
    [4] https://proceedings.mlr.press/v80/zhang18i/zhang18i.pdf
    [5] https://en.wikipedia.org/wiki/Log_semiring

    • [4]의 논문은 정말 매혹적임
      이 분야 초보에 가깝지만, 거의 모든 ReLU 네트워크를 두 tropical 다항식의 tropical 비율로 표현할 수 있고, 따라서 표면 시각화 같은 기하학적 원리로 분석할 수 있음을 보이는 것 같음. 더 최근 연구에서도 인용됨: https://scholar.google.com/scholar?cites=1003719112553620451... 여기서 의미 있는 진전이 있었는지 궁금함
    • 와, 이게 바로 Unified Algebra가 다루는 내용임
      http://www.cs.toronto.edu/~hehner/UA.pdf
    • 로그를 취해 숫자를 스케일링하면 곱셈이 덧셈이 되고 덧셈이 x + log1p(exp(y - x))가 된다는 부분은, 로그 수 체계에서의 덧셈/뺄셈이 곱셈보다 훨씬 비쌈
      특히 올바른 반올림 결과까지 신경 쓰면 필요한 하드웨어 룩업 테이블이 꽤 커짐
    • 로그를 취해 곱셈을 덧셈으로 바꾸는 방식은 수십 년간 쓰여 온 GF(2^x) 의 접근과 같은 것 아닌가?
      떠오르는 유일한 한계는 체의 크기임
    • 어느 정도 관련 있는 것으로 수론 변환이 있음
      https://ieeexplore.ieee.org/abstract/document/1451721

  • 이게 실제로 동작한다니 놀라움
    보통 곱셈을 쓸지 덧셈을 쓸지 감지하는 비용이 그냥 곱셈을 하는 것보다 느림. 특히 엄청난 양의 작업을 병렬로 수행할 때는 더 그럼

    • OpenBLAS와 cuBLAS와 비교하면 어느 정도일지 궁금함

  • 1968년에 발명된 절차가 지금까지 이 목적으로 쓰이지 않았다는 점이 흥미로움

    • GF(2^x)도 지난 세기 중반까지는 어디에 쓸지 아무도 몰랐음
      아, 그러고 보니 컴퓨터 과학 자체도 지난 세기 중반까지는 거의 존재하지 않았지

  • 행렬 곱셈의 아입방 시간 알고리즘 뒤에 있는 수학 이론에 관심 있으면 여기서 시작할 수 있음: https://en.wikipedia.org/wiki/Matrix_multiplication_algorith...
    실수 j > 0마다 어떤 n이 존재해서, 임의의 n x n 행렬 두 개를 O(n^(2+j)) 단계에 곱할 수 있다고 추측함
    현재는 2+j = w = 2.3728596, 즉 j > 0.3728596에 대해 증명됨

    • 이 서술이 맞는지 모르겠음
      “모든 j에 대해 어떤 n이 존재한다”로 시작하면 이후 문장에서 n과 j가 상수가 됨. 그러면 상수 크기 행렬을 상수 시간에 곱할 수 있다는 말뿐임. 기술적으로는 맞지만, 더 강한 주장을 하려던 것 같음
    • 시간이 갈수록 진전이 더 어려워지는 것 같음
      어쩌면 j=1/e에서 바닥을 칠지도 모름. 이건 추측이라고 부르지도 않겠지만, 현재 값 근처에 있는 편리한 상수일 뿐임. 수학이 우리에게 그런 장난을 친다면 꽤 웃길 듯함
    • 임의의 j > 0에 대해 성립한다고 예측하는 건 꽤 대담함
      왜 그렇게 생각하는지 직관을 공유해 줄 수 있나?

  • 이 README는 개선점이 무엇인지, 어떻게 곱셈을 절반으로 줄이는지 설명을 정말 못함
    Big O 실행 시간은 어떻게 되나? 알려진 최적 경계를 바꾸는 건가?
    그림도 산만하고 이 접근이 왜 빠르거나 좋은지 거의 설명하지 못함. 그래서 PDF까지 클릭하기가 꺼려짐
    프로젝트 신뢰도를 높이고 싶다면 실제로 무슨 일이 일어나는지 솔직하고 명확하게 설명하고, 사람들을 과장 광고로 끌어들이는 듯한 그림 대신 분명한 설명과 도식을 제공하면 좋겠음. 이게 엄청난 돌파구인지 아니면 별것 아닌지 구분하기 어렵다. 안타깝게도 AI 열풍을 이용하려는 의도적 선택처럼 느껴지기도 함. 더 믿고 싶은 대안은 저자가 단순히 수정하고 맥락을 더 잘 제공해야 한다는 쪽임

    • “Big O 실행 시간은?”에 대해선, 곱셈을 절반으로 줄인다는 주장이라 Big O에는 영향을 주지 않음
      논문(https://arxiv.org/abs/2311.12224)에서 곱셈 수를 절반으로 줄이는 수학은 이해하기 어렵지 않음. 전통적인 행렬 곱셈인 식 2와 식 3~6만 읽으면 됨
      광고한 대로 곱셈을 절반으로 줄이는 대신, 많은 덧셈/뺄셈을 추가하는 건 분명해 보임. 이후에는 그 알고리즘을 더 잘 벡터화하는데, 이런 작업이 보통 그렇듯 금방 복잡해짐
      주된 걱정은 수치 안정성임
    • README는 별로 설명이 없지만 논문 자체의 도입부는 꽤 접근하기 쉬움
      획기적이냐에 대해서는, 면적 제약이 있는 고정소수점 가속기에 바로 적용 가능한 깔끔한 상수 배 개선이라고 봄. 모든 걸 하루아침에 바꾸진 않지만, 그렇다고 아무것도 아닌 것도 아님. 좋은 작업임
    • 엘리트주의적으로 들리길 바라진 않지만, 이 댓글의 요지를 전혀 모르겠음
      “곱셈을 절반으로 줄인다”가 Big O를 바꾸지 않는다는 걸 모를 정도로 Big O 표기법을 이해하지 못한다면 왜 그걸 묻는지 모르겠음
답변달기