HN紹介: 乗算回数を半減した行列積

 (github.com/trevorpogue)
3 ポイント 投稿者 GN⁺ 2024-03-17 | 1件のコメント | WhatsAppで共有
  • このリポジトリは、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×高速
    • 従来の上限である 1 を超える mults/multiplier/clock cycle 2×以上
    • 低面積と高クロック周波数

論文と博士論文で検証されたアーキテクチャ

MAC・multiplier 当たりの性能を高める理由

  • ディープラーニングモデルの計算処理の大半は一般に matrix multiplication にマッピングでき、これは multiply-accumulate 演算の連なりで構成される
  • 追加の algebraic innovation がなければ、ディープラーニングアクセラレータのスループットは、1 clock cycle 当たりに実行可能な MAC 演算数の最大値に制限される
  • ディープラーニングアクセラレータは多数の MAC unit を含むため、multiplier と MAC unit は GEMM およびディープラーニングアクセラレータでハードウェア面積を大きく占めやすい compute resource になる
  • アクセラレータのスループットは、ハードウェア予算で搭載可能な 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] のアーキテクチャを組み合わせた合成および性能結果は、類似のコンピュートプラットフォーム上の最新アクセラレータと比較して次を達成

    • CNN推論が最大3×高速

    • mults/multiplier/clock cycle が2×高い

アクセラレータシステム構造

  • ソースコードに実装されたディープラーニングアクセラレータシステムは、[1]-[4] で提案された systolic array をホストして検証するために使われる
  • システム実装は 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 を用いて、システム全体の周波数と消費電力を改善

  • 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 の高さと幅を定義
    • LAYERIO_WIDTH と WEIGHT_WIDTH は input bitwidth を定義
  • rtl/arith
    • mxu.sv と mac_array.sv を含む
    • FIP_METHOD の値に応じて、baseline および提案された一部の systolic array アーキテクチャである FIP、FFIP [1] の RTL を収める

追加ドキュメント

関連記事

1件のコメント

 
GN⁺ 2024-03-17
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 の構成可能論理ブロックは 1 クロックで 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 ネットワークを 2 つの 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 が存在して、任意の 2 つの 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記法を理解していないなら、なぜそれを尋ねるのか分からない。