畳み込みニューラルネットワークのパフォーマンス最適化

導入

畳み込みはニューラルネットワークのコア計算の 1 つです。コンピュータービジョンにおける畳み込みの画期的な進歩により、ディープラーニングが大流行しました。畳み込みにはさまざまなバリエーションがあり、計算が複雑です。ニューラルネットワークの実行時間のほとんどは、畳み込みの計算に費やされます。ネットワークモデルの開発により、ネットワークの深さが絶えず増加しているため、畳み込み計算を最適化することが特に重要です。

技術の発展に伴い、研究者はIm2col、Winogradなどさまざまな最適化アルゴリズムを提案してきました。この記事では、まず畳み込みニューラルネットワークの概念を定義し、次にいくつかの一般的な最適化手法を簡単に紹介し、この分野における著者の経験の一部について説明します。

畳み込みニューラルネットワークの概念

畳み込みニューラルネットワーク (CNN) の概念は、信号処理の分野における畳み込みから拡張されました。信号処理の畳み込みは次のように定義される。

（１）

対称画像の畳み込み計算は直感的に理解しにくいため、図 1 に視覚化して示します。図の移動中に赤いスライダーと青い四角で描かれる三角形のパターンは、各点における畳み込み結果 (𝑓∗𝑔)(𝑡) の値です。

図 1: 信号処理における畳み込み (https://jackwish.net/convolution-neural-networks-optimization.html)

式 1 の離散形式は次のとおりです。

（２）

畳み込みを 2 次元空間に拡張すると、ニューラルネットワークでの畳み込みが得られます。これは次のように省略できます。

（３）

ここで、𝑆 は畳み込み出力、𝐼 は畳み込み入力、𝐾 は畳み込みカーネルです。この計算の動的な視覚化は conv_arithmetic (https://github.com/vdumoulin/conv_arithmetic) にありますが、ここでは紹介しません。

コンピュータービジョンの画像処理に適用する場合、画像チャネルは 2 次元畳み込みで単純に積み重ねることができます。つまり、次のようになります。

（4）

ここで、𝑐c は入力のチャネルです。これは、2D 畳み込みを 3D テンソルに適用する計算です。

多くの場合、数式の説明は直感的ではありません。図 2 は、積み重ねられた 2 次元畳み込みを視覚化したものです。このうち、入力、出力、畳み込みカーネルに関連するラベルには、接頭辞として I、O、K が付けられます。さらに、この記事の凡例では、出力、入力、畳み込みカーネルにオレンジ、黄色、緑の色が使用されます。

図2: 畳み込み計算の定義

テンソルのメモリレイアウトが NHWC の場合、畳み込み計算の対応する疑似コードは次のようになります。外側の 3 層のループは出力 𝐶C の各データポイントをトラバースし、各出力データは内側の 3 層のループを通じて累積および合計され、(ドット積) を取得する必要があります。

 ( int oh = 0 ; oh < OH ; oh ++ ) {
 ( int ow = 0 ; ow < OW ; ow ++ ) {
 ( int oc = 0 ; oc < OC ; oc ++ )の場合{
 C [ oh ] [ ow ] [ oc ] = 0 ;
 ( int kh = 0 ; kh < KH 、 kh ++ ) {
 ( int kw = 0 ; kw < KW 、 kw ++ ) {
 ( int ic = 0 ; ic < IC , ic ++ )の場合{
 C [ oh ] [ ow ] [ oc ] += A [ oh + kh ] [ ow + kw ] [ ic ] * B [ kh ] [ kw ] [ ic ] ;
 }
 }
 }
 }
 }
 }

行列乗算の最適化方法と同様に、この計算に対してもベクトル化、並列化、ループ展開などの基本的な最適化操作を実行できます。畳み込みの問題は、その𝐾𝐻と𝐾𝑊が一般に5を超えないためベクトル化が容易ではなく、特徴の計算では入力の空間次元でデータの再利用が行われることです。この計算の複雑さにより、いくつかの最適化方法が必要になります。そのうちのいくつかを以下に示します。

Im2col 最適化アルゴリズム

初期のディープラーニングフレームワークとして、Caffe は im2col ベースの方法を使用して畳み込みを実装します。これは、現在でも畳み込みの重要な最適化方法の 1 つです。

Im2col は、コンピュータービジョンの分野で画像を行列列に変換するための計算手順です。前のセクションの紹介からわかるように、2次元畳み込みの計算は比較的複雑で、最適化が困難です。そのため、ディープラーニングフレームワークの開発初期には、CaffeはIm2colメソッドを使用して3次元テンソルを2次元行列に変換し、最適化されたGEMMライブラリを最大限に活用して、さまざまなプラットフォームの畳み込み計算を高速化しました。最後に、行列乗算によって得られた 2 次元行列の結果は、Col2im を使用して 3 次元行列出力に変換されます。

アルゴリズムプロセス

特に指定がない限り、この記事で使用されるデフォルトのメモリレイアウトは NHWC です。その他のメモリレイアウトや特定の変換された行列の形状は若干異なる場合がありますが、アルゴリズム自体の説明には影響しません。

図3: Im2colアルゴリズムによる畳み込み計算のプロセス

図 3 は、Im2col アルゴリズムを使用して畳み込みを計算するプロセスの例です。具体的なプロセスは次のとおりです (簡単にするために、Padding の場合は無視します。つまり、𝑂𝐻=𝐼𝐻、𝑂𝑊=𝐼𝑊 と仮定します)。

入力は畳み込みの計算特性に従って、𝐼𝐻×𝐼𝑊×𝐼𝐶から(𝑂𝐻×𝑂𝑊)×(𝐾𝐻×𝐾𝑊×𝐼𝐶)の形状の2次元行列に拡張されます。明らかに、変換後に使用されるメモリスペースは、元の入力の約𝐾𝐻∗𝐾𝑊−1倍になります。
重みの形状は一般に4次元テンソル𝑂𝐶×𝐾𝐻×𝐾𝑊×𝐼𝐶であり、形状が(𝑂𝐶)×(𝐾𝐻×𝐾𝑊×𝐼𝐶))の2次元行列として直接処理できます。
用意した2つの2次元行列に対して、(𝐾𝐻×𝐾𝑊×𝐼𝐶)を累積和の次元として行列乗算を実行すると、出力行列(𝑂𝐻×𝑂𝑊)×(𝑂𝐶)が得られます。このプロセスは、さまざまな最適化された BLAS (基本線形代数サブプログラム) ライブラリを使用して直接実行できます。
出力行列 (𝑂𝐻×𝑂𝑊)×(𝑂𝐶) は、メモリレイアウトの観点から期待される出力テンソル 𝑂𝐻×𝑂𝑊×𝑂𝐶 です。

Im2col は、追加のメモリオーバーヘッドを犠牲にして GEMM を使用して畳み込みを計算します。これは、元の畳み込み計算では、畳み込みカーネルが入力上をスライドして出力を計算するときに、隣接する出力計算で空間内の特定の入力と出力が再利用されるためです。 Im2colを使用して3次元テンソルを2次元行列に拡張すると、再利用できたはずのこれらのデータは行列内にフラットに分散され、入力データは𝐾𝐻∗𝐾𝑊−1回コピーされます。

畳み込みカーネルのサイズ𝐾𝐻×𝐾𝑊が1×1の場合、上記の手順で𝐾𝐻と𝐾𝑊を削除できます。つまり、変換後の入力の形状は(𝑂𝐻×𝑂𝑊)×(𝐼𝐶)、畳み込みカーネルの形状は(𝑂𝐶)×(𝐼𝐶)となり、畳み込み計算は行列乗算に退化します。この場合、Im2col プロセスは実際には入力の形状を変更しないため、行列乗算演算を元の入力に対して直接実行でき、メモリ編成プロセス (つまり、上記の手順のステップ 1、2、および 4) が不要になることに注意してください。

メモリレイアウトと畳み込みパフォーマンス

ニューラルネットワークの畳み込みには、NCHW と NHWC という 2 つの主なメモリレイアウトがあります。メモリレイアウトが異なると、特に行列乗算を実行するときに、計算実行時のメモリアクセスモードに影響します。このセクションでは、Im2col 最適化アルゴリズムを使用する場合のコンピューティングパフォーマンスとメモリレイアウトの関係を分析します。

Im2col 変換が完了すると、行列乗算を実行するための入力行列と畳み込みカーネル行列が取得されます。データ分割やベクトル化など、行列計算で一般的に使用される最適化手法を計算プロセスに適用します (関連する定義については、一般行列乗算 (GEMM) 最適化アルゴリズムを参照してください: https://jackwish.net/gemm-optimization.html)。以下では、このシナリオにおけるさまざまなメモリレイアウトがパフォーマンスに与える影響を分析することに焦点を当てます。

まず、NCHWメモリレイアウトを考えます。NCHWメモリレイアウトの畳み込みが行列乗算𝐶=𝐴𝐵に対応する場合、𝐴は畳み込みカーネル（フィルタ）、𝐵は入力（入力）であり、各行列の次元は図4に示されています。図中の𝑀、𝑁、𝐾は行列の乗算、つまり絵を表すために使われ、畳み込み計算における各次元との関係も表しています。

図4: 畳み込みを行列乗算に変換したNCHWメモリレイアウト

マトリックスを分割した後、局所性のパフォーマンスを詳細に分析し、図 4 にマークします。内側は 4×4 小ブロック行列乗算内の局所性を表し、外側は縮小次元の方向における小ブロック間の局所性を表します。

出力については、ベクトル化されたロードごとに 4 つの要素がロードされ、ロードごとにキャッシュミスが発生するため、小さなブロック内のメモリの局所性は低くなります。外部表現はグローバル計算の方向に依存します。行を先にすると局所性が向上し、列を先にすると局所性が悪くなります。出力動作は、メモリを再利用しないので、ここでの議論はこれで終わりではありません。
畳み込みカーネルの場合、小さなブロック内ではメモリアクセスの局所性が低く、これは出力と同様です。小さなブロックをロードするときにキャッシュミスが発生すると、プロセッサは一度に 1 つのキャッシュラインをロードします。これにより、すべてのキャッシュラインがヒットして次のキャッシュラインが入力されるまで、後続の小さなブロックアクセスでキャッシュヒットが発生します。したがって、小さなブロックの外部局所性はより優れています。
入力の場合、小さなブロック内ではメモリの局所性も低くなります。ただし、畳み込みカーネルとは異なり、このメモリレイアウトでは次の小さなブロックのアドレス範囲が通常 1 つのキャッシュラインを超えるため、小さなブロックのキャッシュミスによりキャッシュにロードされたキャッシュラインデータは 1 回しか使用されません。したがって、入力のほぼすべてのメモリロードはキャッシュミスになります。キャッシュは加速には役立たず、すべてのメモリアクセスはデータを取得するためにメモリにアクセスする必要があります。

したがって、Im2col を使用して畳み込み計算を処理する場合、NCHW レイアウトはメモリに優しくありません。

図5は、対照的にNHWCのメモリレイアウトの例です。 NHWC と NCHW の 𝐴 行列と 𝐵 行列によって表されるテンソルが入れ替わっていることに注目する価値があります — 𝑂𝑢𝑡𝑝𝑢𝑡=𝐼𝑛𝑝𝑢𝑡×𝐹𝑖𝑙𝑡𝑒𝑟 (余分な図を描きたくないので、入れ替えています)。具体的な分割方法は同じままで、前のセクションで説明した手順で構築されたマトリックスです。

図5: NHWCメモリレイアウト畳み込みを行列乗算に変換

同様に、3 つのテンソルのメモリアクセスパフォーマンスを分析すると、次のことがわかります。

出力に関しては、NHWC と NCHW は同じ動作をします。
入力の場合、複数のベクトルロードでキャッシュミスが発生するため、小さな正方形の内部局所性はあまり良くありません。一方、縮小された次元でのスライドに使用されるメモリは連続しているため、外部局所性はより良くなります。このパフォーマンスは NCHW の畳み込みカーネルと同じであり、全体的にキャッシュに適したメモリレイアウトです。
畳み込みカーネルの場合、NHWC の状況は NCHW の入力の状況と似ており、パッチの内側と外側の両方で局所性が低くなります。

畳み込みカーネルは実行時に変更されないため、2 つのメモリレイアウトでの畳み込みカーネルのキャッシュパフォーマンスは問題になりません。畳み込みカーネルのメモリレイアウトは、モデルの読み込みフェーズで変換して、小さなブロックの外側のメモリをキャッシュに適したものにすることができます (たとえば、(𝐼𝐶×𝐾𝐻×𝐾𝑊)×(𝑂𝐶) のレイアウトを (𝑂𝐶)×(𝐼𝐶×𝐾𝐻×𝐾𝑊) に変換します)。ここで注目すべきは、一般的なフレームワークまたはエンジンの動作は、準備段階と実行段階の少なくとも 2 つの段階に分けられるということです。準備段階では、実行段階で変更されないデータである畳み込みカーネルのメモリレイアウトの並べ替えなど、モデルの一部の事前処理作業を行うことができます。

したがって、Im2col メソッドを使用して計算する場合、全体的なメモリアクセスパフォーマンスは入力状況に依存します。つまり、NHWC のメモリレイアウトは NCHW よりも優れています。私たちの実際の実験では、1×1 カーネルの畳み込みの場合、同様の最適化方法を使用すると、NCHW から NHWC に変換すると、キャッシュミス率が約 50% から約 2% に削減されることが示されています。このレベルの改善により、ソフトウェアのパフォーマンスが大幅に向上します (特に、特別に設計された行列乗算最適化メソッドを使用しなくても)。

空間組み合わせ最適化アルゴリズム

Im2col は比較的単純な畳み込み最適化アルゴリズムですが、慎重に処理しないと大きなメモリオーバーヘッドが発生します。空間パックは、行列乗算におけるメモリの再編成に似た最適化アルゴリズムです。

図6: 空間組み合わせ最適化アルゴリズムの計算分割

空間組み合わせ最適化アルゴリズムは分割統治法であり、畳み込み計算を空間特性に基づいて複数の部分に分割し、個別に処理します。図 6 は、出力と入力が空間的に 4 つの部分に分割されていることを示しています。

パーティション分割後、大きな畳み込み計算はいくつかの小さな畳み込み計算に分割されます。除算処理中の計算の総量は変わりませんが、小さな行列を計算する場合はメモリの局所性が向上し、コンピュータのストレージ階層を使用することでパフォーマンスを向上させることができます。これは、図 7 の手順を通じて実現されます。このステップは、前のセクションの Im2col によるメモリの再編成のプロセスに似ています。

𝑁×𝐻×𝑊×𝐼の形状の入力テンソルを、H次元とW次元で𝑁×𝐻/ℎ×𝑊/𝑤×𝐼𝐶の形状のℎ∗𝑤（各方向にℎと𝑤倍）テンソルに分割し、これらの小さなテンソルを連続メモリに整理します。
得られたℎ∗𝑤入力テンソルと畳み込みカーネルに対してそれぞれ2次元畳み込み演算を実行し、𝑁×𝐻/ℎ×𝑊/𝑤×𝑂𝐶の形状を持つℎ∗𝑤出力テンソルを取得します。
これらの出力テンソルはメモリレイアウトに再編成され、形状 𝑁×𝐻×𝑊×𝑂𝐶 の最終出力が得られます。

図7: 空間結合計算の手順

便宜上、上記の説明ではパディングの問題を無視していることに注意してください。実際には、ステップ 1 で入力テンソルがいくつかの小さなテンソルに分割される場合、分割された小さなブロック内の元のデータをコピーすることに加えて、隣接する小さなテンソルの境界データもコピーする必要があります。具体的には、図 8 に示すように、空間分解によって得られる小さなテンソルの形状は実際には次のようになります。

𝑁×(𝐻/ℎ+2(𝐾𝐻−1))×(𝑊/𝑤+(𝐾𝑊−1))×𝐶.(5)

ここで2(𝐾𝐻−1)と2(𝐾𝑊−1)はパディングルールに従います。ルールがイメージの場合、それらは無視できます。ルールが SAME の場合、ソーステンソル境界側のパディングはイメージでパディングされ、ソーステンソル境界上にないパディングは隣接するテンソルの値を使用します。畳み込みがどのように計算されるかを考えれば、これは明らかです。

図8: 空間結合アルゴリズムのパーティションの詳細

上記の 3 つの例の図はすべて 4 つの部分に分割されていますが、実際のアプリケーションでは、複数の部分に分割されることがあります。たとえば、辺の長さが 4 または 8 の小さなテンソルに分割できるため、コンパイラが計算操作をベクトル化しやすくなります。分割されたテンソルが小さくなるにつれて、局所性は高くなりますが、追加のメモリが消費されるという悪影響があります。この余分なメモリはパディングによって導入されます。 ℎ∗𝑤h∗w 部分に分割すると、分割後に Padding によって消費されるメモリは次のようになります。

分割の粒度が小さくなるにつれて、追加のメモリ消費が増加することがわかります。分割が最も細かい粒度の場合、つまり形状 𝑁×𝐻×𝑊×𝑂𝐶 の出力空間が 𝐻∗𝑊 部分に分割される場合、空間結合は Im2col メソッドに退化することに注目する価値があります。このとき、要素上の畳み込みは、出力要素を計算するときの行列のドット積になります。

空間除算のみが実行される場合、除算は畳み込みカーネルとは関係ありません。出力チャネルの次元が分割されると、畳み込みカーネルもそれに応じて分割されます。チャネル次元の分割は、固定空間分割後の単純なスタッキングと同等であり、メモリ消費には影響しませんが、局所性には影響します。さまざまなサイズの畳み込みの場合、適切な除算方法を見つけるのは簡単な作業ではありません。コンピュータサイエンスの多くの問題と同様に、この問題は自動化できます。たとえば、AutoTVM (https://arxiv.org/abs/1805.08166) を使用すると、この場合により適切なパーティション分割方法を見つけることができます。

ウィノグラード最適化アルゴリズム

前の 2 つのセクションで紹介した 2 つのアルゴリズム、Im2col は 3 次元テンソルを行列に整理した後、GEMM コンピューティングライブラリを呼び出します。これらのコンピューティングライブラリは主にメモリの局所性に基づくいくつかの最適化を使用しており、空間の組み合わせ最適化自体は局所性最適化を使用する方法です。このセクションで紹介する Winograd 最適化アルゴリズムは、Coppersmith-Winograd アルゴリズムを行列乗算最適化手法に応用したもので、アルゴリズム分析に基づいた手法です。

この部分は数式が多すぎて入力しづらいです。興味のある方は原文を参照してください（

https://jackwish.net/convolution-neural-networks-optimization.html

) またはその他の関連文献を参照してください。

間接畳み込み最適化アルゴリズム

Marat Dukhan が QNNPACK (Quantized Neural Network PACKage) で導入した間接畳み込みアルゴリズムは、これまで (2019 年半ば) 公開されているすべての方法の中で最も高速であると思われます。著者は最近、主要な考え方を紹介する関連記事を発表しました。

QNNPACK でのこのアルゴリズムの実装は主に量子化ニューラルネットワークに使用されますが (業界の他の量子化最適化ソリューションは比較的伝統的です。TensorFlow Lite は Im2col 最適化アルゴリズムを使用し、Tencent が作成した NCNN は Winograd 最適化アルゴリズムを使用し、OpenAI が作成した Tengine は Im2col 最適化アルゴリズムを使用します)、同様の最適化アルゴリズム設計です。

この記事が書かれた時点では、設計記事はまだ公開されておらず、アルゴリズム設計の多くの詳細を理解するには、コードと併せて理解するのが最善です。私の QNNPACK フォーク (https://github.com/jackwish/qnnpack) には、参照用にいくつかのコードにコメントを追加する explained ブランチが含まれています。

計算ワークフロー

間接畳み込みアルゴリズムの効果的な動作は、ネットワークが継続的に実行されているときに入力テンソルのメモリアドレスが変更されないという重要な前提に依存します。この機能は実際には比較的簡単に満たすことができます。アドレスを実際に変更する必要がある場合でも、固定メモリ領域にコピーすることができます。

図9: 間接畳み込みアルゴリズムのワークフロー

図 9 は間接畳み込みアルゴリズムのワークフローの詳細なプロセスを示しています。左端の部分は、複数の入力が同じ入力バッファを使用することを示します。間接畳み込みアルゴリズムは、入力バッファに基づいて図 10 に示すように「間接バッファ」（Indirect Buffer）を構築します。間接バッファは間接畳み込みアルゴリズムの中核です。図の右側に示すように、ネットワークが実行中はスケール 𝑀×𝑁 の出力が毎回計算されます。ここで、𝑀 は 𝑂𝐻×𝑂𝑊 を 1 次元として扱った後のベクトル化されたスケールです。一般的に、𝑀×𝑁は4×4、8×8、または4×8です。サイズ𝑀×𝑁の出力を計算するときは、対応する入力を間接バッファを通して取り出し、重みを取り出して結果を計算します。計算プロセスは、𝑀×𝐾と𝐾×𝑁の行列乗算を計算することと同等です。

実装では、ソフトウェアの実行プロセスは次の 2 つの部分に分かれています。

準備フェーズ: モデルをロードし、入力バッファを構成し、メモリレイアウトが後続の計算に適するように重みを再配置します。
実行フェーズ: 各入力に対して、⌈𝑂𝐻∗𝑂𝑊/𝑀⌉∗⌈𝑂𝐶/𝑁⌉ コアループを実行し、そのたびに GEMM メソッドを使用してサイズ 𝑀×𝑁 の出力を計算します。

図10: 間接バッファ

関連するセクションで説明したように、Im2col 最適化アルゴリズムには 2 つの問題があります。1 つ目は、余分なメモリを大量に消費すること、2 つ目は、入力の追加データのコピーが必要になることです。これら2つの点をどう解決すればよいのでしょうか?間接畳み込みアルゴリズムによって得られる答えは、図 10 の右半分に示すように、間接バッファ (Indirect Buffer) です。

図10は従来のIm2col最適化アルゴリズムと間接畳み込み最適化アルゴリズムの比較です。関連するセクションで紹介されているように、Im2col 最適化アルゴリズムは、図 10 の入力に関連する矢印に示すように、最初に入力を行列にコピーし、次に行列乗算演算を実行します。間接畳み込み最適化アルゴリズムで使用される間接バッファには、実際には入力へのポインタが格納されます (間接畳み込み最適化アルゴリズムでは、入力メモリアドレスを固定する必要があるのはこのためです)。実行時には、これらのポインタに基づいて、Im2col に似た行列計算プロセスをシミュレートできます。

間接バッファレイアウト

間接バッファは、畳み込みカーネルサイズのバッファのセットとして理解できます。バッファの合計は 𝑂𝐻×𝑂𝑊、各バッファのサイズは 𝐾𝐻×𝐾𝑊 です。各バッファは、特定の出力で使用される入力のアドレスに対応します。空間位置の出力を計算するたびに間接バッファが使用されます。空間位置は同じだがチャネルが異なる出力は同じ間接バッファを使用し、バッファ内の各ポインタは入力内の 𝐼𝐶 要素のインデックス付けに使用されます。計算中、出力が移動すると、対応する入力アドレスを取得するために異なる間接バッファが選択されます。出力先の座標に基づいて、使用する入力のアドレスを計算する必要はありません。これは、アドレスを事前に計算することと同じです。

図11は、𝑀×𝑁が4で、𝐾𝐻と𝐾𝑊がともに3の場合の間接バッファの実際の使用法と計算プロセスを示しています。図中のローカル間接バッファという名前は、現在考慮されているのが𝑀×𝑁を計算する際のコア計算プロセスであることを意味します。

サイズ𝑀×𝑁の出力を計算する場合、使用される入力は、対応する入力位置で𝑀ステップスライドする畳み込みカーネルによってカバーされる領域、つまりサイズ(𝐾𝐻)×(𝑀+2(𝐾𝑊−1))×𝐼𝐶の入力です。間接畳み込みアルゴリズムでは、これらの入力メモリは、合計𝑀×𝐾𝐻×𝐾𝑊のM間接バッファ内のポインタによってインデックス付けされます。図１１は、入力スペースの左上隅の入力と対応する入力バッファとの対応関係を示す。 4つの入力バッファA、B、C、Dについて、隣接する2つのバッファが指すアドレス領域は(𝐾𝑊−𝑆𝑡𝑟𝑖𝑑𝑒)/𝐾𝑊、つまり2/3であることがわかります。各バッファ内のポインタの座標もマークされています。

図11: 間接バッファの詳細な説明

フラットバッファは 3 次元 (IC 次元が増加) で描画され、間接バッファの各ポインタが IC 入力要素をインデックスできること、および各間接バッファインデックスの内容が重みに対応する入力メモリ領域であることを示します。

なお、左上の入力バッファ配置は最終的な配置方法ではなく、実際にはこれらのポインタは図11の中央にある間接バッファの形に加工されます。各バッファ内のポインタを左上隅に分割すると、𝐾𝐻×𝐾𝑊 ポインタが得られ、4つのバッファ A、B、C、D の異なる空間位置にあるポインタをまとめて収集すると、図の上部にあるバッファ配置 𝐾𝐻×𝐾𝑊×𝑀 が得られます。 4 つのバッファー A、B、C、D 内の同じ空間位置へのポインターが一緒に構成されていることがわかります。図の中央上部は視覚化効果であり、中央下部は間接バッファの実際の構成です。図中の茶色と濃い黄色は、同じ入力メモリまたはポインターに対応します。凡例において、Stride が 1 であることは注目に値します。Stride が 1 でない場合、再編成後の同じ空間内の A、B、C、D の座標 (入力内の座標に対応) は必ずしも連続しておらず、隣接する空間位置の横方向の座標は 𝑆𝑡𝑟𝑖𝑑𝑒 異なります。

間接バッファを使用した計算

間接バッファがどのように構成され、そのポインタが入力メモリのアドレスとどのように対応しているかがわかったので、計算中にこれらのバッファがどのように使用されるかを調べてみましょう。

前のセクションと同様に、このセクションでは主に、データの再利用を伴い、𝑀𝐾𝐻×𝐾𝑊サイズの入力を使用して𝑀×𝑁サイズの出力を計算することについて議論します。ここで、Im2col のアルゴリズムを確認してみましょう (図 11 の左下部分を参照)。計算がベクトル化されると、𝑀×𝑁 の行列乗算計算では、毎回 𝑀×𝑆 スケールの入力と 𝑆×𝑁 スケールの重みが取り出され、ブロック上で行列乗算が実行され、対応する部分と結果が得られます。ここで、𝑆は𝐾K次元におけるベクトル化された計算のステップ係数です。

畳み込みで Im2col 最適化アルゴリズムを使用できる理由は、逆アセンブルしてメモリの再利用を無視した後の計算プロセスが行列の乗算と同等であるためです。間接バッファを使用すると、ポインタを介して入力へのメモリアクセスをシミュレートできます。実際に𝑀×𝑁の出力を計算するマイクロカーネルを実行すると、入力をスキャンする𝑀ポインタが存在します。 𝑀ポインタは、図11の下部にある間接バッファ構造、つまり、図の右上のレイアウトに示すように、入力𝑀×𝐼𝐶に対応するメモリから、その都度𝑀アドレスを取り出します。ここでのステップでは、依然として 𝑀 × 𝑆 の形式で動作しており、 𝑆 は 𝐼𝐶 次元内を移動します。入力のこの部分がスキャンされると、𝑀ポインターは間接バッファーから対応するポインターを取得し、𝑀×𝐼𝐶入力メモリの次のトラバースを続行し、そのたびに1/(𝐾𝐻∗𝐾𝑊)の出力部分和を計算します。このプロセスを𝐾𝐻×𝐾𝑊回実行すると、𝑀×𝑁の出力が得られます。図 11 の右下隅にある疑似コードがこのプロセスに対応します。間接バッファは特定の形状に編成されているため、𝑀ポインタが更新されるたびに、間接バッファポインタ（図の疑似コードではp_indirect_buffer）から取得するだけで済みます。

このプロセスのロジックは理解しにくいので、ここで追加の説明をします。前述の𝑀ポインタがメモリをスキャンするために動き続けるとき、実際には3次元入力Im2colの後の行列をスキャンしています。入力バッファの特別な機能は、2D 行列のスキャンを 3D テンソルのスキャンに変換することです。入力のスキャン処理は、図11の上部に視覚化された入力のスキャンです。左上と左下の間の対応する入力関係を考慮すると、入力内のメモリの𝑀×𝐼𝐶ブロックを毎回スキャンしていることは難しくありません。ここで、𝑀×𝐼𝐶は𝑀1×𝐼𝐶テンソルで構成され、それらの𝑊次元間の間隔は𝑆𝑡𝑟𝑖𝑑𝑒であることに注目する価値があります。

このように、計算コアを ⌈𝑂𝐻∗𝑂𝑊/𝑀⌉∗⌈𝑂𝐶/𝑁⌉ 回実行することで、すべての出力を取得できます。

間接畳み込み最適化アルゴリズムは、畳み込み計算の 3 つの問題を解決します。1 つ目は空間ベクトル化問題、2 つ目は複雑なアドレス計算問題、3 つ目はメモリコピー問題です。一般的に畳み込みを計算する場合、入力をゼロで埋める必要があり（𝐾𝐻×𝐾𝑊が1×1でない場合）、この処理の従来の方法ではメモリコピーが発生します。間接畳み込み最適化アルゴリズムの間接バッファは、間接ポインタを通じてこの問題を巧みに解決できます。間接バッファを構築するときは、1×𝐼𝐶の追加メモリバッファを作成し、ゼロ値で埋めます。ゼロで埋める必要があるスペースの位置については、対応する間接ポインタをバッファにポイントして、後続の計算がゼロで埋めた場合と同等になるようにします。たとえば、図 11 の A の左上隅は、入力スペースの位置 (0,0) に対応します。ゼロパディングが必要な場合、この位置はゼロでなければなりません。このとき、間接バッファのアドレスを変更するだけで済みます。

議論、要約、展望

これまで、この記事では、公開またはオープンソース化された畳み込みニューラルネットワークの最適化手法をいくつか検討してきました。これらの最適化手法により、クラウドやモバイル端末でのディープラーニング技術の応用が促進され、私たちの日常生活に役立っています。たとえば、上海や中国全土の人々を悩ませている最近のゴミの分類問題でも、ディープラーニングの手法を使用して分類方法を人々に理解してもらうことができます (https://news.mydrivers.com/1/633/633858.htm)。

この記事の集中最適化方法から、畳み込みニューラルネットワークの最適化アルゴリズムは、アルゴリズム分析に基づく方法とソフトウェア最適化に基づく方法にまだ含まれていることがわかります。実際、現代のコンピュータシステムでは、ソフトウェア最適化ベースの方法、特にコンピュータストレージ階層に基づく最適化は、その方法の探索と適用が容易であるため、より重要になっています。一方、現代のコンピュータに特殊な命令を追加することで、さまざまな計算間の時間消費の違いをなくすことができます。このシナリオでは、アルゴリズム分析ベースの方法とソフトウェア最適化ベースの方法を組み合わせることで、より良い最適化結果が得られる可能性があります。

最後に、この記事で説明した最適化方法はすべて、ニューラルネットワークプロセッサ（Cambrian MLU、Google TPUなど）の開発と、DOT製品関連の指示：NVIDIA GPU DP4A、Intel AVX-512 VNNI、ARM SDOT/UDOTの最適化

<<: 数日間GitHubのホットリストを独占した後、Colossal-AIが正式にリリースされました

>>: AI アルゴリズムがハードウェアを置き換えることは可能でしょうか?