新しいアルゴリズムは、スパーステンソルを100倍高速に乗算します

ビデオ: 新しいアルゴリズムは、スパーステンソルを100倍高速に乗算します

ビデオ: ルーメン| Unrealの内部 2022, 十一月
新しいアルゴリズムは、スパーステンソルを100倍高速に乗算します
新しいアルゴリズムは、スパーステンソルを100倍高速に乗算します
Anonim
Image
Image

スパース行列の例

MITの研究者は、任意のランクのスパーステンソルで操作を実行するように最適化されたコードを自動的に生成するC ++ライブラリを開発しました。行列を使用して計算する場合、このコードの実行時間は手動で最適化されたプログラムの実行時間と同等であり、ランクの高いテンソルの場合、はるかに高速に動作しました(ほぼ100倍)。この記事はプログラミング言語に関するACMの議事録に掲載されました。プログラムの成果は、専用のWebサイトでオンラインで確認できます。

データを操作するときは、行列またはテンソルの形式でデータを表すと便利なことがよくあります。このようなマトリックスを使用して、FacebookページまたはマッチショッパーとAmazonでの商品のレビューとの間のリンクを説明できます。この場合、この方法で記録された情報のほとんどは「役に立たない」ことが判明する可能性があります。たとえば、Amazonカスタマーレビューテンソルには約1,019個のコンポーネントが含まれていますが、ゼロ以外のコンポーネントは109個だけです。このようなテンソルはスパースと呼ばれます。

スパーステンソルを使用した計算は、任意の数にゼロを掛けると常にゼロになるという事実を考慮に入れると、大幅に加速できます。さらに、中間計算の結果を保存することは、大量のデータでは効果がないため、いくつかの追加の最適化を行う必要があります。たとえば、式Σi、j AijkBij + Ckの計算は、1つのステップで実行する必要があり、個別の乗算および加算演算に分割しないでください。通常、このような最適化は手動で行われ、操作の種類ごとに独自のテンプレート(いわゆるカーネル、カーネル)が開発されます。

Image
Image

スパースベクトルを使用する場合の計算の簡略化。

この記事では、科学者は、データ構造の分析に基づいてプログラムコードを自動的に生成する、テンソルを使用した任意の式の新しい最適化ツールを提案します。ユーザーは、最適化するデータストレージ形式と操作のシーケンスを指定するだけで済みます。彼らのアプローチを実証するために、科学者たちはtaco(Tensor Algebra COmpiler、Tensor AlgebraCompiler)と呼ばれるC ++ライブラリを開発しました。

このために、科学者は、レベルの数がテンソルのランクに等しい(ツリーのルートを別のレベルとして除く)ツリー形式のテンソルの表現に基づいた便利なデータストレージ形式を開発しました。 )。次に、テンソル演算(乗算と加算)がそのようなツリーの演算としてどのように実装されるかを理解しました。このように、2つのテンソルの乗算は、木を横切る方向を示すグラフを使用して実行され、合計は2つの木をマージすることによって実現されます。最後に、科学者たちは、これらのアイデアを使用してコードパターンを生成する再帰的アルゴリズムについて説明しました。

Image
Image

ツリーを使用してスパース行列を表す例

次に、研究者は、開発したライブラリのパフォーマンスを既存のプログラムと比較しました。スパース行列の計算だけでなく、すべての手動で最適化されたアルゴリズムにも対応していることが判明し、場合によっては、tacoを使用した計算時間がさらに短くなることが判明しました。上位のテンソルを使用する場合、タコスは既存のアナログを何倍も上回りました。たとえば、ニューオーリンズのローカルネットワークFacebookでの投稿の分析から生成された、3番目のランクのテンソルは、新しいアルゴリズムがMATLAB TensorToolboxより114倍速く増加しました。

以前、MITの研究者が、他のプログラムのソースコードのエラーを自動的に検索して修正するプログラムを開発した方法について書きました。そしてケンブリッジの科学者たちは、コードを盗み、そこから独自のプロジェクトを収集するための人工知能を教えました。

トピックによって人気があります

人気の投稿