Fair and Square: Replacing One Real Multiplication with a Single Square and One Complex Multiplication with Three Squares When Performing Matrix Multiplication and Convolutions

この論文は、行列乗算や畳み込みにおいて実数乗算を単一の二乗演算へ、複素数乗算を 3 つの二乗演算へ漸近的に置換可能であることを示し、ハードウェア実装におけるリソース削減を実現する手法とアーキテクチャを提案しています。

要約

この論文は、**「計算機が数字を掛け合わせる（乗算）作業を、より簡単で安価な『二乗（自乗）』の作業に置き換える」**という画期的なアイデアを提案しています。

AI（人工知能）や画像処理などで使われる「行列計算」や「畳み込み（コンボリューション）」という複雑な計算を、ハードウェアの規模を半分に減らしながら、同じ結果を出す方法を見つけることができたのです。

この難しい話を、料理と建築の例えを使って、わかりやすく解説しましょう。

---

🍳 料理の例え：「混ぜる」か「焼く」か

通常、コンピュータが「A × B（A と B を掛ける）」という計算をするとき、それは**「高価で複雑なオーブン」**を使っているようなものです。このオーブン（乗算器）は、電気も食料（ゲート数）もたくさん使います。

一方、この論文が提案するのは、**「安くて簡単なトースター（二乗器）」**を使う方法です。
実は、トースター 1 台のサイズは、オーブン 1 台の半分しかありません。

魔法のレシピ：$(a+b)^2$ の秘密

この論文の核心は、数学の公式を少しひねったことにあります。
「掛け算（$a \times b$）」は、実は**「足して二乗する」「引いて二乗する」「元の数を二乗する」**という 3 つの操作を組み合わせれば、トースターだけで作れてしまうのです。

掛け算の代わり：
「2 人の身長を足して二乗し、そこから 2 人それぞれの二乗を引けば、2 人の『掛け合わせ』の値が得られる」

このように、高価な「掛け算オーブン」を、安価な「二乗トースター」に置き換えることで、計算コストを劇的に下げることができます。

---

🏗️ 建築の例え：巨大なビル（行列計算）

AI が画像を認識する際、何百万もの数字の掛け算（行列計算）を行います。これは、巨大なビルを建てるようなものです。

1. 実数の場合（普通の数字）

• 従来の方法： 1 階ごとに「掛け算の柱」を何本も立てていました。
• 新しい方法： 「掛け算の柱」を「二乗の柱」に置き換えます。
  • 最初は「足して二乗する」作業が増えるように見えますが、「建物の外壁（行や列の合計）」を事前に計算して、何度も使い回せることに気づきました。
  • 結果： ビルが大きくなるほど（行列のサイズが大きくなるほど）、1 つの計算に必要な「二乗トースター」の数は、元の「掛け算オーブン」とほぼ同じ（1 対 1）になります。
  • メリット： トースターはオーブンより半分のサイズなので、ビルの土地代（チップの面積）と電気代（消費電力）が半分以下に！

2. 複素数の場合（AI でよく使われる複雑な数字）

AI の世界では、数字に「実数」と「虚数」という 2 つの側面を持つ「複素数」を使います。

• 従来の方法： 1 つの複素数掛け算には、実数の掛け算が 4 つ必要でした。
• 新しい方法（4 回バージョン）： 4 つの「二乗トースター」を使えば、1 つの複素数掛け算が済みます。
• さらに新しい方法（3 回バージョン）： 論文の後半では、**「3 つの二乗トースター」**だけで済む、さらに賢いレシピも発見されました。
  • これにより、複雑な計算でも、ハードウェアのサイズを大幅に縮小できます。

---

🚀 具体的な応用：どんな機械に使えるの？

このアイデアは、以下のような最新の AI 用ハードウェアに組み込むことができます。

1. シストリック・アレイ（Systolic Arrays）：
   • 数字がリレーのように流れて計算する回路です。ここでは、掛け算をする部品を「二乗する部品」に差し替えるだけで、同じように動きます。
2. テンソル・コア（Tensor Cores）：
   • 最新の GPU（グラフィックボード）に入っている、AI 計算の心臓部です。ここを改造すれば、同じ面積で 2 倍の性能が出たり、同じ性能で半分のコストで済んだりします。
3. 畳み込み（Convolutions）：
   • 画像認識で使われる「フィルター」処理も、この「掛け算→二乗」の魔法で高速化・低コスト化できます。

---

💡 まとめ：なぜこれがすごいのか？

この論文が伝えたかったことはシンプルです。

「掛け算という『重労働』を、二乗という『軽作業』に置き換える魔法のレシピを見つけた。これを使えば、AI 用のチップを 半分以下のサイズで、半分以下の電力で 作れるようになる！」

まるで、高価な大理石で家を作る代わりに、安くて丈夫なレンガを工夫して積み上げることで、同じ家を作れるようになったようなものです。

AI がもっと身近になり、スマホや家電に高性能な AI が搭載される未来が、この「二乗の魔法」によって加速するかもしれません。

技術概要

論文サマリー：行列乗算と畳み込みにおける乗算から乗算回路への置換

1. 背景と課題 (Problem)

人工知能（AI）、デジタル信号処理（DSP）およびその他の多くのアプリケーションにおいて、行列乗算や畳み込み演算は不可欠であり、その実装の最適化は極めて重要です。
これらの演算の核心となる「乗算（Multiplication）」は、ハードウェア実装においてリソース（ゲート数）と電力消費の主要な要因となっています。特に $n$ ビットの乗算器は、同じビット長の「2 乗（Squaring）」回路に比べて約 2 倍のゲート数を必要とします。
従来の最適化手法では、乗算回数を減らすアプローチが主流でしたが、本論文は**「乗算演算自体を、よりリソース効率の良い 2 乗演算に置換する」**という全く新しいアプローチを提案しています。

2. 手法と基本原理 (Methodology)

本論文の核心は、数学的な恒等式を用いて乗算を 2 乗演算に変換する手法にあります。

2.1 基本メカニズム

以下の代数恒等式を利用します：
$$(a+b)^2 = a^2 + b^2 + 2ab \implies ab = \frac{1}{2} \left( (a+b)^2 - a^2 - b^2 \right)$$
$$(a-b)^2 = a^2 + b^2 - 2ab \implies -ab = \frac{1}{2} \left( (a-b)^2 - a^2 - b^2 \right)$$

これにより、任意の乗算 $ab$ を、和の 2 乗 $(a+b)^2$ と、個々の項の 2 乗 $a^2, b^2$ の線形結合として表現できます。

2.2 実装戦略

• 乗算の置換: 行列乗算や畳み込みの各ステップで、乗算器（Multiplier）を「部分乗算器（Partial Multiplier）」に置き換えます。部分乗算器は、入力値の和を 2 乗する回路です。
• 事前計算と再利用: 式変形により生じる $a^2$ や $b^2$ の項（行列の行・列ごとの 2 乗和）は、行列の要素に依存するが出力インデックスには依存しないため、事前に計算し、すべての出力要素で再利用（共有）できます。
• スケーリング: 最終結果は 2 倍になるため、右シフト（1 ビットシフト）で補正します。

3. 主要な貢献と結果 (Key Contributions & Results)

3.1 実数行列乗算 (Real Matrix Multiplication)

• 手法: $M \times N$ 行列 $A$ と $N \times P$ 行列 $B$ の積を計算する場合、各要素の乗算 $a_{ik}b_{kj}$ を上記の恒等式で置換します。
• 計算量:
  • 従来の乗算数: $M \times N \times P$
  • 提案手法の 2 乗数: $M \times N \times P$（和の 2 乗）+ $M \times N$（$A$ の行 2 乗和）+ $N \times P$（$B$ の列 2 乗和）
• 効率化: 行列サイズ $M, P$ が大きくなるにつれ、乗算あたりの 2 乗演算数の比率は $1 + \frac{1}{P} + \frac{1}{M}$ となり、1 に収束します。つまり、実質的に乗算 1 回あたり 2 乗 1 回で済みます。

3.2 複素数行列乗算 (Complex Matrix Multiplication)

複素数乗算を 2 乗演算で実現する 2 つのアプローチが提案されています。

1. 4 乗アプローチ (Section 6):
   • 複素乗算の実部と虚部をそれぞれ 2 つの 2 乗演算（計 4 つ）で構成します。
   • 大規模行列において、複素乗算 1 回あたり4 回の 2 乗演算で実現可能です。
2. 3 乗アプローチ (Section 9):
   • 複素乗算を 3 つの実数乗算に変換する手法（Karatsuba 法の変種など）を、さらに 2 乗演算に展開します。
   • 実部と虚部で共通の項 $(c+a+b)^2$ を共有することで、乗算 1 回あたり3 回の 2 乗演算で実現可能です。
   • 大規模行列において、乗算あたりの 2 乗演算数の比率は3 に収束します。

3.3 畳み込みと線形変換 (Convolutions & Linear Transforms)

• 畳み込み: 1 次元および 2 次元の畳み込みに対しても同様の手法が適用可能です。カーネル重みが定数の場合、重みの 2 乗和は事前に計算可能であり、入力サンプルごとの計算コストを大幅に削減できます。
• 線形変換: DFT（離散フーリエ変換）などの線形変換においても、係数が定数であれば事前計算により同様の効率化が図れます。

3.4 ハードウェアアーキテクチャ

本論文では、これらのアルゴリズムをハードウェア化する具体的なアーキテクチャを提案しています：

• 部分乗算器ベースの MAC (Multiply-Accumulate): 従来の乗算器を 2 乗器と加算器に置換した回路。
• 2 乗ベースの Systolic Array: 処理要素（PE）内の乗算器を置換し、追加項（$S_a, S_b$）を流し込むことで行列乗算を高速化する配列。
• 2 乗ベースの Tensor Core: 既存の Tensor Core アーキテクチャを改造し、部分乗算（2 乗）と初期値設定（事前計算された 2 乗和）を行うことで、AI 推論などの大規模演算を効率化。

4. 意義と結論 (Significance & Conclusion)

4.1 リソース削減効果

$n$ ビットの 2 乗回路は、$n \times n$ 乗算器に比べてゲート数が約半分で済みます。

• 実数演算では、乗算 1 回を 2 乗 1 回に置き換えることで、乗算器の面積と電力を約 50% 削減できます。
• 複素数演算（3 乗アプローチ）でも、従来の複素乗算（通常 4 実数乗算）を 3 実数 2 乗演算に置き換えることで、大幅なリソース削減が期待されます。

4.2 応用範囲

• AI 推論・学習: 行列乗算と畳み込みはニューラルネットワークの主要な負荷であり、この技術はエッジデバイスや大規模データセンターにおけるエネルギー効率とコストの大幅な改善につながります。
• 近似計算への拡張: 厳密な 2 乗ではなく「近似 2 乗」を用いることで、さらに精度と速度のトレードオフを調整可能です。

4.3 結論

本論文は、行列乗算、畳み込み、線形変換において、乗算演算を 2 乗演算に漸近的に置換する画期的な手法を提示しました。特に、複素数演算において 3 つの 2 乗演算で 1 つの複素乗算を代替できる点は、ハードウェア設計における重要なブレイクスルーです。これにより、AI や信号処理ハードウェアの面積、電力、コストを劇的に削減する可能性が開かれました。