深層強化学習を使用して発見された高速ソートアルゴリズム | 深センボールドベンチャーソリューションズ株式会社

Nature volume 618、pages 257–263 (2023)この記事を引用

88k アクセス

952 オルトメトリック

メトリクスの詳細

ソートやハッシュなどの基本的なアルゴリズムは、毎日何兆回も使用されます1。計算の需要が高まるにつれて、これらのアルゴリズムのパフォーマンスを可能な限り高めることが重要になってきています。過去に目覚ましい進歩が達成されました 2 が、これらのルーチンの効率をさらに改善することは、人間の科学者にとっても、計算によるアプローチにとっても困難であることが判明しています。ここでは、これまで知られていなかったルーチンを発見することで、人工知能がどのように現在の最先端技術を超えることができるかを示します。これを実現するために、私たちはシングルプレイヤーゲームとしてより良い並べ替えルーチンを見つけるというタスクを定式化しました。次に、このゲームをプレイするために新しい深層強化学習エージェント AlphaDev をトレーニングしました。 AlphaDev は、これまで知られていた人間のベンチマークを上回る小さな並べ替えアルゴリズムをゼロから発見しました。これらのアルゴリズムは、LLVM 標準 C++ ソートライブラリ 3 に統合されています。ソートライブラリのこの部分に対するこの変更は、強化学習を使用して自動的に検出されたアルゴリズムによるコンポーネントの置き換えを表します。また、追加のドメインでの結果も示し、アプローチの一般性を示します。

アルゴリズムを改善するには、人間の直感とノウハウが非常に重要です。しかし、多くのアルゴリズムは人間の専門家がそれ以上最適化できない段階に達しており、計算上のボトルネックが増大し続けています。何十年にもわたる古典的なプログラム合成文献の研究は、正しいプログラムを生成したり、レイテンシのプロキシを使用してプログラムを最適化したりすることを目的としています。これらには、列挙的検索手法 4、5、6、7 や確率的検索 5、6、8、9、10 に加え、正しいプログラムを生成するためにプログラム合成で深層学習を使用するという最近の傾向 11、12、13、14、15、16 が含まれます。。深層強化学習 (DRL) を使用すると、CPU 命令レベルで実際に測定されたレイテンシーを最適化し、以前の研究と比較して正確で高速なプログラムのスペースをより効率的に検索および考慮することで、正確でパフォーマンスの高いアルゴリズムを生成することで、これをさらに一歩進めることができます。。

コンピューターサイエンスにおける基本的な問題の 1 つは、シーケンスをどのようにソートするかということです 17、18、19、20。これは、世界中の初等コンピュータサイエンスのクラスで教えられており 21、22、広範囲のアプリケーションで遍在的に使用されています 23、24、25。数十年にわたるコンピュータサイエンスの研究は、並べ替えアルゴリズムの発見と最適化に焦点を当ててきました26、27、28。実際的なソリューションの重要な要素は、短い一連の要素に対する小さな並べ替えです。このアルゴリズムは、分割統治アプローチを使用する大きな配列をソートするときに繰り返し呼び出されます29。この作業では、(1) 固定ソートと (2) 変数ソートの 2 種類の小規模ソートアルゴリズムに焦点を当てます。固定ソートアルゴリズムは固定長のシーケンスをソートします (たとえば、ソート 3 は長さ 3 のシーケンスのみをソートできます)。一方、可変ソートアルゴリズムはさまざまなサイズのシーケンスをソートできます (たとえば、変数ソート 5 は 1 から 5 の範囲のシーケンスをソートできます)。要素）。

私たちは、新しく効率的な並べ替えアルゴリズムを発見するという問題を、AssemblyGame と呼ぶシングルプレイヤーゲームとして定式化します。このゲームでは、プレーヤーは、アセンブリ命令 30 と呼ばれる一連の低レベル CPU 命令を選択し、組み合わせて新しい効率的なソートアルゴリズムを生成します。プレーヤーはアセンブリ命令の組み合わせ空間を考慮して、正確かつ高速なアルゴリズムを生成する必要があるため、これは困難です。 AssemblyGame の難しさは、チェス (10120 ゲーム) 31 や囲碁 (10700 ゲーム) 32 などの非常に難しいゲームに似た検索空間のサイズだけでなく、報酬関数の性質からも生じます。 AssemblyGame での 1 つの間違った命令により、アルゴリズム全体が無効になる可能性があり、このゲーム空間での探索は信じられないほど困難になります。

ゲームをプレイするには、正しく効率的なアルゴリズムを検索するように訓練された学習エージェントである AlphaDev を導入します。このエージェントは、(1) 学習アルゴリズムと (2) 表現関数という 2 つのコアコンポーネントで構成されます。 AlphaDev 学習アルゴリズムには、AssemblyGame をプレイするために、DRL と確率的検索最適化アルゴリズムの両方を組み込むことができます。 AlphaDev の主な学習アルゴリズムは、よく知られた DRL アルゴリズムである AlphaZero33 の拡張であり、AssemblyGame を解決するための検索をガイドするようにニューラルネットワークがトレーニングされます。表現関数は交換可能であり、アセンブリプログラムの基礎となる構造をキャプチャします。主要な AlphaDev 表現は、Transformers34 に基づいています。

AlphaDev を使用して、私たちは、新しく、最先端の人間によるベンチマークよりも効率的な、固定および可変ソートアルゴリズムをゼロから発見しました。 AlphaDev によって発見されたソート 3、ソート 4、およびソート 5 の修正されたソートソリューションは、LLVM 標準 C++ ライブラリ 3 の標準ソート関数に統合されました。このライブラリは、大学や多数の国際企業を含む数百万のユーザーによって使用されています35。さらに、新しいアルゴリズムの発見を分析し、AlphaDev を確率的検索最適化アプローチと比較し、AlphaDev をさらなるドメインに適用して、アプローチの汎用性を示します。

C++ などの高級言語からアルゴリズムをマシンコードにコンパイルする場合 (たとえば、図 1a のソート関数)、アルゴリズムは最初にアセンブリにコンパイルされます (図 1b)。次に、アセンブラはアセンブリプログラムを実行可能なマシンコードに変換します。この作業では、アセンブリレベルでアルゴリズムを最適化します30。一般的なアセンブリプログラムでは、値がメモリからレジスタにコピーされ、レジスタ間で操作されてからメモリに書き戻されます。サポートされるアセンブリ命令のセットは、プロセッサアーキテクチャによって異なります。この研究では、AT&T 構文 36 を使用する x86 プロセッサアーキテクチャによってサポートされるアセンブリ命令のサブセットに焦点を当てます。各命令の形式は、Opcode⟨OperandA、OperandB⟩です。命令の例は mov です。これは、値をソース (A) から宛先 (B) に移動するものとして定義されます。比較 (cmp)、条件付き移動 (cmovX)、およびジャンプ (jX) などのさらなる命令定義は、拡張データテーブル 1 にあります。図 1b の例では、%eax、%ecx、%edx、%edi が以下に対応します。 4 つの異なるレジスタ位置と (%rsi)、4(%rsi) は 2 つの異なるメモリ位置に対応します。記号 $2 は定数値のプレースホルダーであり、この例ではベクトルの長さに対応します。この作業では、アセンブリプログラムとアセンブリアルゴリズムという用語を同じ意味で使用します。これは、AlphaDev が AssemblyGame を再生するたびに、最初は順序付けされていない命令セットからアセンブリプログラムを最初から構築し、新しい効率的なアルゴリズムを定義するためです。

a、最大 2 つの要素からなる入力シーケンスを並べ替える変数 sort 2 関数の C++ 実装。 b. a の C++ 実装は、この同等の低レベルアセンブリ表現にコンパイルされます。

このセクションでは、CPU 命令レベルでの最適化アルゴリズムを強化学習 (RL) 問題 37 として定式化します。この問題では、環境は AssemblyGame と呼ばれるシングルプレイヤーゲームとしてモデル化されます。このゲームの各状態はベクトル St = ⟨Pt, Zt⟩ として定義されます。ここで、Pt はゲーム内でこれまでに生成されたアルゴリズムの表現であり、Zt は事前定義されたセットに対して現在のアルゴリズムを実行した後のメモリとレジスタの状態を表します。入力。図 2a に見られるように、タイムステップ t で、プレイヤーは現在の状態 St を受け取り、アクションを実行します。これには、これまでに生成された現在のアルゴリズムに正当なアセンブリ命令 (mov など) を追加することが含まれます。アルゴリズムの正確さと待ち時間の両方の尺度を含む報酬 r が受け取られます。アルゴリズムの正確性 (図 2b) には、N 個のテストシーケンスのセットを現在のアルゴリズム Pt に入力して N 個の出力を生成することが含まれます。次に、これらの出力が期待される出力と比較され、正しさの報酬 rt が計算されます。レイテンシ報酬は、(1) アルゴリズムの長さの増加 (長さとレイテンシに高度な相関関係がある場合) に対してエージェントにペナルティを課す (アルゴリズム長報酬と呼ばれます)、または (2) アルゴリズムの実際のレイテンシを測定することによって生成できます。。ゲームは限られた数のステップで実行され、その後ゲームは終了します。ゲームに勝つことは、アセンブリ命令を使用して正しい低遅延アルゴリズムを生成することに相当します。ゲームに負けることは、間違ったアルゴリズム、または正しいが非効率なアルゴリズムを生成することに相当します。

a、AssemblyGame は AlphaDev によってプレイされます。AlphaDev は、これまでに生成された現在のアセンブリアルゴリズムを入力として受け取り、実行するアクションを選択することによってゲームをプレイします。この例では、アクションは mov アセンブリ命令であり、現在のアルゴリズムに追加されます。エージェントは、b で説明したアルゴリズムの正確さと、アルゴリズムの待ち時間の関数である報酬を受け取ります。ゲームは、プレーヤーが低遅延の正しいアルゴリズムを発見することで勝利します。 b, プログラムの正確性と待ち時間の計算を使用して、報酬 rt を計算します。この例では、テストシーケンスがアルゴリズムに入力されます。たとえば、3 つの要素をソートする場合、テスト入力は、長さ 3 の未ソート要素のすべてのシーケンスで構成されます。シーケンスごとに、アルゴリズムの出力が予想される出力と比較されます (ソートの場合、予想される出力はソートされた要素です) ）。この例では、出力 ${\bf{D}}{\boldsymbol{{\prime} }}$ が予想される出力 ${\bf{B}}{\boldsymbol{{\prime}) と一致しません。 }}$ したがって、アルゴリズムは正しくありません。

このシングルプレイヤーゲームをプレイするエージェントを AlphaDev と呼びます。エージェントの主な学習アルゴリズムは、AlphaZero エージェント 32 の拡張であり、ディープニューラルネットワーク 33,38 を使用してモンテカルロツリー検索 (MCTS) 計画手順をガイドします。ニューラルネットワークへの入力は状態 St で、出力はポリシーと値の予測です。ポリシー予測はアクション全体の分布であり、値関数はエージェントが現在の状態 St から受け取ると期待される累積収益 R の予測です。ゲーム中、エージェントは現在の状態 St を入力として受け取ります。 MCTS プロシージャを実行し、これを使用して次に実行するアクションを選択します。生成されたゲームはネットワークのパラメータを更新するために使用され、エージェントが学習できるようになります。

AlphaDev が命令の空間を効率的に探索するには、複雑なアルゴリズム構造を表現できる表現 39,40 を備えていることが重要です。これを達成するために、AlphaDev 表現ネットワーク (拡張データ図 1a) を導入します。このネットワークは 2 つのコンポーネントで構成されます。(1) アルゴリズム構造の表現をエージェントに提供するトランスフォーマーエンコーダーネットワーク、および (2) アルゴリズムがメモリとレジスタのダイナミクスにどのような影響を与えるかをエージェントが予測するのに役立つ CPU 状態エンコーダーネットワークです。。 CPU 状態エンコーダネットワークは、特定の入力セットの各レジスタとメモリ位置の状態を入力として受け取る多層パーセプトロンで構成されます。これらのネットワークはそれぞれ、AlphaDev 状態表現を生成するために結合されるエンベディングを出力します。

トランスフォーマーは自然なテキストエンコーダーであり、最近言語モデルで大きな成功を収めています14、34、41。そのため、これが私たちに、標準トランスをモデルの組み立て命令に適合させる動機を与えました。私たちは、アセンブリ命令を表すために、MultiQuery トランスフォーマーエンコーダ 42 を適応させたトランスエンコーダーを開発し、AlphaDev 表現ネットワークに組み込みました。各アセンブリ命令のオペコードと対応するオペランドはワンホットエンコーディングに変換され、連結されて生の入力シーケンスが形成されます。これは、多層トランスフォーマーエンコーダーを介して供給され、対応する埋め込みベクトルにマッピングされます (図については、拡張データの図 1b を参照)。

レイテンシーは、エージェントがパフォーマンスの高いアルゴリズムを発見するように導くために使用される重要な報酬シグナルです。レイテンシをより適切に推定するために、デュアル値関数セットアップを実装しました。これにより、AlphaDev には 2 つの値関数ヘッドがあります。1 つはアルゴリズムの正確性を予測し、2 番目はアルゴリズムのレイテンシを予測します。レイテンシヘッドは、トレーニング中に AlphaDev のモンテカルロターゲットとしてプログラムの実際に計算されたレイテンシを使用することにより、特定のプログラムのレイテンシを直接予測するために使用されます。このデュアルヘッドのアプローチは、実際のレイテンシを最適化する際に、通常のシングルヘッド値関数セットアップよりも大幅に優れた結果を達成しました。

私たちは、AlphaDev エージェントをゼロからトレーニングして、正確でありながら最先端の人間のベンチマークよりも低いレイテンシを実現する、さまざまな固定ソートアルゴリズムと可変ソートアルゴリズムを生成しました。

ソート 3、ソート 4、ソート 5 の 3 つの基本アルゴリズムを検討しました。これらのアルゴリズムの最先端の人間によるベンチマークは、効率的な条件付きブランチレスアセンブリコードを生成するソートネットワーク 43 です。これは、すべての命令が順番に実行され、分岐が含まれないことを意味します。これらのアルゴリズムはすでに高度に最適化されているため、改善するのは困難です。表 1a に見られるように、AlphaDev は、ソート 3 およびソート 5 の人間のベンチマークよりも命令数が少ないアルゴリズムを見つけることができ、ソート 4 では最先端のパフォーマンスに匹敵します。これらの短いアルゴリズムは、実際に待ち時間の短縮につながります。条件付きブランチレスの場合、アルゴリズムの長さとレイテンシーは相関関係があります。詳細については、補足情報の付録 B を参照してください。また、AlphaDev のバリアントを使用して、わずかに大きなソートへのスケーリングも検討しました。ソート 6 では 3 つの命令、ソート 7 では 2 つの命令、ソート 8 では 1 つの命令を保存することができました。これは、将来の作業に有望な基盤となります。このアプローチの概要については、補足情報の付録 C を参照してください。

3 つの変数並べ替えアルゴリズム、VarSort3、VarSort4、および VarSort5 を検討しました。それぞれの場合における人間によるベンチマークは、特定の入力長に対して、対応する並べ替えネットワークを呼び出すアルゴリズムとして定義されます。この場合、分岐が必要となり、エージェントは (1) 構築する必要があるサブアルゴリズムの数を決定し、(2) メインアルゴリズムの本体を並行して構築する必要があるため、問題の複雑さが大幅に増加します。エージェントは、他のサブアルゴリズムからサブアルゴリズムを呼び出す必要がある場合もあります。この場合、表 1a に示すように、長さを最適化すると、人間のベンチマークと比較してアルゴリズムが大幅に短くなります。ただし、分岐によって生じる複雑さのため、レイテンシと長さは必ずしも相関しているわけではありません。詳細については、補足情報を参照してください。そのため、計算された信頼区間 44 を使用して、100 台の異なるマシンにわたるレイテンシ測定の 5 パーセンタイルを取得することでプログラムの実際のレイテンシを測定し、このメトリクスを最適化する手順を実装しました。完全なベンチマーク設定については、「方法」を参照してください。表 1b に示すように、レイテンシを最適化すると、エージェントはいずれの場合も人間のベンチマークで大幅に向上します。

AlphaDev によって発見されたソリューションには、より効率的なパフォーマンスにつながる新しくエキサイティングなアルゴリズムの発見が含まれています。固定ソート設定では、AlphaDev が 2 つの興味深い命令シーケンスを発見しました。これらの命令をソートネットワークアルゴリズムに適用すると、毎回 1 つのアセンブリ命令がアルゴリズムを削減します。それぞれの命令シーケンスを、それぞれ (1) AlphaDev スワップ移動、(2) AlphaDev コピー移動と呼びます。

図 3a は、3 つの要素に対する最適な分類ネットワークを示しています (分類ネットワークの概要については「方法」を参照)。 AlphaDev が丸で囲んだネットワークセグメントをどのように改善したかを説明します。この構造にはさまざまなサイズの分類ネットワークで見られる多くの変形があり、それぞれの場合に同じ議論が当てはまります。ネットワークの丸で囲まれた部分 (最後の 2 つのコンパレーター) は、入力シーケンス ⟨A、B、C⟩ を受け取り、表 2a (左) に示すように各入力を変換する一連の命令として見ることができます。ただし、ワイヤ B および C のコンパレータはこの演算子の前にあるため、B ≤ C である入力シーケンスが保証されます。これは、表 2a (右) に示すように、最初の出力として min(A, B, C) の代わりに min(A, B) を計算すれば十分であることを意味します。図 3b と図 3c の疑似コードの違いは、AlphaDev スワップ移動が適用されるたびに 1 つの命令をどのように節約するかを示しています。

a, 3 つの入力に最適な古典的な並べ替えネットワーク。丸で囲まれたコンパレータは AlphaDev によって改良されました。詳細については、AlphaDev のスワップの動きを参照してください。 b、c、AlphaDev スワップ移動を適用する前 (b) と、AlphaDev スワップ移動を適用した後 (c) のアセンブリ疑似コード。結果として 1 つの命令が削除されます。 d、AlphaDev によって改良された、最適な古典的なソートネットワークコンパレータ構成。詳細については、「AlphaDev コピーの移動」を参照してください。 e,f、AlphaDev コピー移動を適用する前 (e) と、AlphaDev コピー移動を適用した後 (f) のアセンブリ擬似コード。結果として 1 つの命令が削除されます。

図 3d は、4 つのワイヤに適用される 3 つのコンパレータで構成されるソートネットワーク構成を示しています。この構成はソート 8 ソートネットワークに見られ、表 2b (左側) に示すように、4 つの入力 ⟨A、B、C、D⟩ を受け取り、それらを 4 つの出力に変換する演算子に対応します。ソート 8 の一部として、演算子に流入する入力が次の不等式を満たすことがわかります: ${\rm{D}}\ge \min ({\rm{A}},{\rm{C} })$。これは、表 2b (右側) で定義されている AlphaDev コピー移動を適用することでオペレーターを改善できることを意味し、結果として元のオペレーターよりも命令が 1 つ少なくなります。元のオペレータとAlphaDevコピー移動を適用した後のコード間のコードの違いは、それぞれ図3e、fに視覚化されています。

AlphaDev によって発見された VarSort4 アルゴリズムは特に興味深いものです。ヒューマンベンチマークアルゴリズムとAlphaDevのフロー図をそれぞれ図4a、bに示します。人間のベンチマークアルゴリズムは入力ベクトルの長さを決定し、対応する並べ替えネットワークを呼び出して要素を並べ替えます。 AlphaDev ソリューションは、図 4b に示すように、まったく異なるアプローチを採用しています。入力ベクトルの長さが厳密に 2 より大きい場合は、sort 3 がすぐに呼び出され、最初の 3 つの要素がソートされます。ベクトルが 3 要素より大きい場合は、単純化されたソート 4 アルゴリズムが呼び出され、入力ベクトル内のソートされていない残りの要素がソートされます。ルーチンのこの簡素化された部分により、アルゴリズムの長さとレイテンシの点で大幅な利点が得られます。

a、変数ソート 4 (VarSort4) ヒューマンベンチマークアルゴリズムのフロー図。このアルゴリズムでは、ソートされていない一連の数値がアルゴリズムに入力されます。シーケンスの長さが 4、3、または 2 つの数値の場合、対応するソート 4、ソート 3、またはソート 2 ソートネットワークが呼び出され、結果のシーケンスがソートされます。結果は関数によって返され、出力されます。 b. AlphaDev によって発見された VarSort4 アルゴリズム。このアルゴリズムは、長さ 4、3、または 2 つの数値のシーケンスも入力として受け取ります。この場合、長さが 2 の場合、ソート 2 ソートネットワークを呼び出して戻ります。長さが 3 の場合、sort 3 を呼び出して最初の 3 つの数値を並べ替えて戻ります。ただし、長さが 3 より大きい場合は、ソート 3 が呼び出され、その後、ソートされていない残りの数値をソートする単純化されたソート 4 ルーチンが呼び出されます。ルーチンのこの部分により、待ち時間が大幅に節約されます。

プログラム最適化の他のアプローチと比較した RL の利点と制限を理解することが重要です。そのため、私たちは最先端の確率的超最適化アプローチ 8 を実装し、それを並べ替え設定に適合させて、AlphaDev の学習アルゴリズムとして使用しました。この亜種を AlphaDev-S と呼びます (詳細については「メソッド」を参照)。このアルゴリズムは、少なくとも AlphaDev と同じ量のリソースと実時間を使用して実行されます。 AlphaDev-S では、ミューテーションのたびにレイテンシを計算する必要があるため、レイテンシを直接最適化するには法外な時間がかかります。そのため、AlphaDev-S はレイテンシプロキシ、つまりアルゴリズムの長さを最適化し、トレーニングの最後に、AlphaDev-S によって生成されたすべての正しいプログラムを検索し、それぞれをベンチマークしてレイテンシが最も低いソリューションを見つけます。一般に、事前知識なしでゼロから学習する場合、AlphaDev は AlphaDev-S よりも常に優れたパフォーマンスを発揮することがわかります。さらに、プログラムのサイズが大きくなるにつれて、AlphaDev は、AlphaDev-S (最悪の場合は 31 兆のプログラム) に比べて、桁違いに少ないプログラム (最悪の場合は 1,200 万のプログラム) を探索します。これは、局所最適化に陥りやすい幅優先の確率的検索手順と比較して、AlphaDev がアルゴリズムの空間をより適切に探索できるためである可能性があります。この探索仮説の概要については、「メソッド」を参照してください。さらに、AlphaDev はレイテンシ値関数の予測を使用するため、検索中にレイテンシを評価することはなく、生成されたプログラムの 0.002% 未満について実際に測定されたレイテンシを計算するだけで済みます。最適に近いソリューションで学習アルゴリズムをウォームスタートするなど、以前の知識を AlphaDev-S に組み込むと、AlphaDev-S はソート 3、ソート 4、およびソート 5 (分岐なしアセンブリアルゴリズム) の計算効率が向上し、競争力の高い低パフォーマンスも生成します。それぞれの場合のレイテンシアルゴリズムは AlphaDev のアルゴリズムと一致します。ただし、分岐 (if–else ステートメント) が必要なアルゴリズムの場合、アルゴリズムの長さとレイテンシーに十分な相関関係がなく、AlphaDev は、最適に近いソリューションでこのアルゴリズムをウォームスタートした場合でも、AlphaDev-S よりもレイテンシーの低いソリューションを発見します。これらのアルゴリズムの詳細な分析については、「メソッド」を参照してください。

AlphaDev の汎用性をテストするために、一連の追加ドメインでエージェントをトレーニングします。これらには、以下に示す VarInt と呼ばれるプロトコルバッファー逆シリアル化サブルーチンと、競合コーディングの問題が含まれます (詳細については、補足情報の付録 D を参照してください)。競合コーディングドメインのレイテンシパフォーマンスを表 1b に示します。

プロトコルバッファーは、構造化データをシリアル化するために使用される Google のオープンソースデータ形式です45。この形式は、パフォーマンスやネットワーク負荷が主な関心事である場合によく使用されます。 VarInt アルゴリズム 46 は、シリアル化プロセスと逆シリアル化プロセスの両方における重要なコンポーネントです。 AlphaDev エージェントを変数ソートと同様にトレーニングし、正確性と測定されたレイテンシーに関して VarInt 逆シリアル化関数を最適化しました。正確さを期すために、各入力を正しく逆シリアル化したエージェントに報酬を与えます。一般的な protobuf のユースケースをカバーする 80 個の入力と対応する出力のセットを使用します。 AlphaDev は、最適化された VarInt 逆シリアル化関数を学習し、単一値入力に対する人間のベンチマークを大幅に上回るパフォーマンスを実現します。私たちのエージェントは、人間のベンチマークよりも短く (表 1a)、約 3 倍高速である (表 1b) ブランチレスソリューションを発見しました。その際、エージェントは、AlphaDev が 2 つの操作を 1 つの命令に結合することを学習し、レイテンシの節約につながる新しい VarInt 割り当ての動きも発見しました。この動きの完全な概要については、補足情報の付録 D.1 を参照してください。これは、AlphaDev が自明ではない現実世界のアルゴリズムを最適化するために一般化できることを強く示しています。

LLVM libc++ 標準ソートライブラリのソート 3、ソート 4、およびソート 5 アルゴリズムは、より大きなソートアルゴリズムによって何度も呼び出されるため、ライブラリの基本コンポーネントです。 AlphaDev が発見したソート 3、ソート 4、ソート 5 の低レベルアセンブリソートアルゴリズムを C++ でリバースエンジニアリングしたところ、ソートの実装により長さ 5 のシーケンスでは最大 70%、長さ 5 のシーケンスでは約 1.7% の改善が見られたことがわかりました。 250,000 要素を超えるシーケンス。これらの改善は、ARMv8、Intel Skylake、および AMD Zen 2 CPU アーキテクチャの uint32、uint64、および float データ型を対象としています。完全なパフォーマンス表については、補足情報の付録 E を参照してください。パフォーマンスの向上は、AlphaDev によって生成されたブランチレス条件付きアセンブリと、新しい AlphaDev スワップ動作の両方によるものです。ソート 5 では、より効率的な C++ 実装につながる、AlphaDev によって発見された長さ 43 のアルゴリズムを使用しました。これらのアルゴリズムはレビューのために送信され、libc++ 標準ソートライブラリ 3 に正式に組み込まれました。これらのサブルーチンに対する変更は、10 年以上ぶりのことです。また、この並べ替えライブラリ内のコンポーネントが、強化学習を使用して自動的に検出されたアルゴリズムに置き換えられたのはこれが初めてです。これらのルーチンは毎日何兆回も呼び出されていると推定されています1,35,47。

AlphaDev は、世界中の何百万もの開発者やアプリケーションによって使用されている LLVM C++ ライブラリに組み込まれている、新しい最先端の並べ替えアルゴリズムをゼロから発見します23、24、25。 AlphaDev と確率的検索はどちらも強力なアルゴリズムです。将来の研究の興味深い方向性は、これらのアルゴリズムを組み合わせて、両方のアプローチの相補的な利点を実現することを研究することです。

AlphaDev は理論上、テストケースの徹底的な検証を必要としない関数に一般化できることに注意することが重要です。たとえば、ハッシュ関数 48 および暗号化ハッシュ関数 49 は、ハッシュ衝突の数によって関数の正確さを定義します。したがって、この場合、AlphaDev は、遅延だけでなく衝突も最小限に抑えるように最適化できます。 AlphaDev は、理論的には、大規模で印象的な関数本体内の複雑なロジックコンポーネントを最適化することもできます。私たちは、AlphaDev が人工知能とプログラム合成コミュニティの両方に興味深い洞察を提供し、新しいアプローチを刺激できることを願っています。

AlphaZero33 は、ポリシー改善オペレーターとして MCTS を活用する RL アルゴリズムです。これは、(1) 状態 St の潜在表現 ht を出力する表現ネットワーク frep から構成されます。 (2) 期待されるリターン (値) ${\hat{v}}_{t}$ とポリシー (つまり、アクション空間全体への分布) を予測する予測ネットワーク fpred ${\hat {\pi }}_{t}$ を与えられた潜在状態から抽出します。このアルゴリズムは、計画時に真のダイナミクスと報酬を使用します。 MuZero38 は、同じ表現ネットワークと予測ネットワークを備えた AlphaZero のモデルベースのバリアントですが、ダイナミクスのモデルを学習して報酬を予測し、それを計画に使用します。具体的には、次の潜在状態 ${{\bf{\text{h}}}}_{t}^{k+1}$ と報酬 ${\hat{r }}_{t}^{k+1}$ 遷移の結果。下付き文字 t は実際の環境のタイムステップを表し、上付き文字 k はモデル内のタイムステップを表すことに注意してください。

新しい状態に到達すると、AlphaZero はまず、表現ネットワークを使用して状態を潜在表現にエンコードします。次に、真のダイナミクスまたはダイナミクスネットワーク (MuZero 用) と予測ネットワーク fps(ht) を使用して、状態遷移をサンプリングすることによって、探索ツリーを満たすいくつかの軌跡をシミュレートします。各ノードでは、予測子信頼ツリー上限 32 と呼ばれる楽観的な戦略を使用してアクションが選択されます。これは、探索 (新しいアクションの試行) と活用 (最適なアクションの現在の推定値のサブツリーをさらに下に進む) のバランスをとることを目的としています。この戦略は、予測されたポリシー ${\hat{\pi }}_{t}$ に厳密に従うことから始まり、徐々に予測値関数の最大化に移行します。最終的に、アクションは、MCTS 中の訪問回数に比例した確率でルートノードからサンプリングすることによって推奨されます。次に、予測されたポリシーは、MCTS ポリシーの訪問数と一致するようにトレーニングされ、検索手順をポリシーに絞り込み、その後の MCTS の繰り返しで見込みのないノードが無視されるようにします。

並べ替えネットワークは、その構造が最新の CPU アーキテクチャ上で並列化できるため、非常に効率的です。したがって、挿入ソートなどの一般的で効率的な基本ケースのアルゴリズムと比較して、特に小規模なソートで実行時パフォーマンスが向上する傾向があります17、43、50。ソーティングネットワーク43は、コンパレータ（縦線）とワイヤー（横線）と呼ばれる2種類のアイテムで構成されます（拡張データ図2a）。各ワイヤーは左から右に値を運びます。 2 本のワイヤがコンパレータで交差すると、2 本のワイヤの値が比較されます。下のワイヤの値が上のワイヤの値より小さい場合、拡張データの図 2b に示すように、ワイヤ間で値が交換されます。ソートネットワークのプログラムによる実装は、入力シーケンスの要素の特定のペアに対してこれらのスワップを特定の順序で実行することで構成されます。

一部のプログラムの不変性 (たとえば、レジスタ割り当ての順序) と不正な命令 (たとえば、2 つのメモリ位置の比較) を削除することで、アクション空間を整理しました。これにより、アクションスペースのサイズが削減され、収束率が向上します。実験では次のルールを使用しました。

メモリ位置は常に増分順序で読み取られます。

レジスタは増分順序で割り当てられます。

比較したり、条件付きでメモリ位置に移動したりすることはできません (不正)。

各メモリ位置への読み書きは 1 回だけ行うことができます。

初期化されていないレジスタは使用できません（違法）。

連続して比較命令を実行しないでください。

AlphaDev は Tensor Processing Unit (TPU) v.3 上でトレーニングされ、TPU コアごとの合計バッチサイズは 1,024 です。最大 16 個の TPU コアを使用し、100 万回の反復でトレーニングします。アクター側では、ゲームはスタンドアロン TPU v.4 でプレイされ、最大 512 人のアクターを使用します。実際には、すべてのタスクにわたって、トレーニングが収束するまでに最悪の場合でも 2 日かかります。

プログラムを最適化するために考えられる他のアプローチと比較した RL の利点と制限を理解することが重要です。そのため、私たちは最先端の確率的超最適化アプローチ 8 を実装し、ソート機能を最適化するための学習アルゴリズムとして AlphaDev に組み込みました。この適応バージョンを AlphaDev-S と呼びます。私たちの再実装は、特にソートドメイン向けに最適化されています。これには、アセンブリ環境で実行するアルゴリズムの実装、並べ替えに固有の正確性とパフォーマンス損失関数の定義、および最適なバリアントを特定するための広範なハイパーパラメータスイープの実行が含まれます。 AlphaDev-S に使用されるコスト関数は、c = 正確性 + α × パフォーマンスです。ここで、正確性はまだソートされていない誤った入力シーケンス要素の数の計算に対応し、パフォーマンスはアルゴリズムの長さの報酬に対応し、α は 2 つのコストをトレードオフする重みです。機能。レイテンシーを直接最適化することはできません。これにより、学習アルゴリズムが大幅に遅くなり、学習が不可能になるためです。この関数は、AlphaDev で使用されるアセンブリ命令の同じセットをサポートするだけでなく、不正または違法なアクションの同じセットを排除するように適合されていることに注意してください。また、同じプログラム正確性計算モジュール (図 2b) を使用して、正確性項を計算します。

次に、AlphaDev-S は、バッファに格納されているプログラム (バッファは空であるか、すでにソートされたプログラムで初期化されている可能性があります) に変換を最初に提案することによって実行されます。次に、プログラムの正確性モジュールとアルゴリズムの長さを使用して、正確性とパフォーマンスの項がそれぞれ計算されます。コストが現在の最良のコストよりも低い場合、新しいプログラムは高い確率で受け入れられますが、そうでない場合は拒否されます。次に、正確性コスト関数と変換重みについて詳しく説明します。

正しさのコスト関数として、3 種類のコスト関数を実装しました。最初の値は、間違って配置されたアイテムの割合として定義されます: $\frac{PP{C}_{t}}{P}$ ここで、P は配置するアイテムの総数、PCt は正しく配置されたアイテムの数です。タイムステップ t で。 2 番目の変数は、この方程式の平方根です。最終的なコスト関数は差 $\sqrt{-{PC}_{t}}$ の平方根を計算し、これが最高のパフォーマンスをもたらします。

プログラムのサイズを増やす命令の追加 (Add Transform)、2 つの命令の交換 (Swap Transform)、命令のオペコードのランダムな変更 (Opcode Transform)、選択した命令のオペランドのランダムなサンプリングなど、いくつかのプログラム変換を有効にしました。 (オペランド変換)、オペコードとそれに対応するオペランドをランダムにサンプリングします (命令変換)。これらの変換のサンプリングに影響を与えて、一部の変換のサンプリング頻度を増減させることができます。大規模なハイパーパラメータスイープを実行することで、サンプリング変換の重みを最適化しました。

ここでは、AlphaDev で使用される DRL と確率的検索学習アルゴリズムの利点と限界をより深く理解するのに役立つ一連の調査研究を紹介します。 AlphaDev と AlphaDev-S を比較します。 AlphaDev-S の 2 つのバリアント (1) コールドスタート (AlphaDev-S-CS) と (2) ウォームスタート (AlphaDev-S-WS) を実装しました。 AlphaDev-S-CS は以前の情報を使用せず、空のプログラムバッファからプログラムを生成する必要があります。 AlphaDev-S-WS のバッファは、正しい並べ替えプログラム (最適な並べ替えネットワークアセンブリプログラムなど) でウォームスタートされ、プログラムを編集してさらに最適化します。個別ソートアルゴリズム設定と変数ソートアルゴリズム設定の両方で、バリアントを AlphaDev と比較しました。

AlphaDev は常に事前知識なしでゼロから学習するため、直接比較するのはコールドスタートの確率的検索バージョンである AlphaDev-S-CS となります。ただし、初期に最適に近いプログラムが利用できる場合もあるため、AlphaDev をウォームスタート確率的検索バージョンである AlphaDev-S-WS と比較します。

確率的検索のバリアントでは、レイテンシーを直接最適化することができないことに注意してください。これは、計算効率のせいで学習が不可能になるためです。そのため、AlphaDev-S バリアントはアルゴリズムの長さを最適化します。次に、トレーニングの最後に、さまざまな長さにわたって AlphaDev-S 用に生成されたプログラムのセットを反復処理し、レイテンシーが最も低いプログラムを特定します。

いずれの場合も、確率的検索アルゴリズム (AlphaDev-S) は、少なくとも AlphaDev と同じ計算リソースと実時間を使用して実行されます。

まず、固定ソートアルゴリズムに対するさまざまなアプローチのパフォーマンスを調べます。この場合、条件付きブランチレス設定ではアルゴリズムの長さとレイテンシが高度に相関しているため、すべてのアルゴリズムのバリアントはアルゴリズムの長さを最適化します (詳細については、補足情報を参照してください)。

コールドスタート設定では、拡張データテーブル 2a に見られるように、AlphaDev-S-CS はそれぞれのケースで最適なプログラムを見つけることができません。さらに、拡張データ表 2b に示すように、AlphaDev-S-CS は AlphaDev よりも桁違いに多くのプログラムを探索します。ウォームスタート設定では、AlphaDev-S は最適に近いソートされたプログラムでウォームスタートされ、拡張データ表 2a に示すように、それぞれのケースで AlphaDev のパフォーマンスと一致します。拡張データ表 2c に示すように、AlphaDev よりも計算効率が高くなりますが、拡張データ表 2b に示すように、ソート 3 とソート 5 については桁違いに多くのプログラムを探索します。 AlphaDev-S-WS には、最適に近い初期プログラムが提供されているため、このシナリオでは大きな利点があると言えます。「変数ソート」セクションで、アルゴリズムがより複雑になり、分岐が導入された場合、最適に近いプログラムで学習アルゴリズムをウォームスタートするだけでは十分ではなく、次善のソリューションで行き詰まる可能性があることを示します。

また、ソート 3 には 17 命令より短いプログラムが存在しないことを証明するために総当たりアプローチも使用しました。およそ 1032 個のプログラムを列挙する必要があり、枝刈りヒューリスティックを使用したとしても、この仮説を証明するのに 3 日以上かかりました。ソート 4 以降では、このアプローチは実行できません。

プログラムの長さは、アルゴリズムのパフォーマンスの単なる指標にすぎません。分岐構造を導入すると、プログラムの長さとレイテンシーには十分な相関関係がありません。そこで、実機上でプログラムを実行し、レイテンシを測定します。測定に影響を与える可能性のある多数のノイズ源を考慮すると、マイクロベンチマークは非常に困難です。これは、他のプロセスからの干渉が発生する可能性がある共有マシンで実行する場合に特に当てはまります。私たちのアプローチは、別のマシン上で複製された別のベンチマークサービスを用意し、さまざまな条件下で制御された環境で多くの測定を迅速に実行できるようにすることです。システムは次のように動作します。

RL エージェントは、複製されたサービスを使用してマシン全体で 1,000 件の測定値を処理します。

測定ごとに、サービスは 10,000 個のランダムな入力に対して指定された並べ替えアルゴリズムを実行します (たとえば、並べ替え 3 の場合、これは 3 × 10,000 = 30,000 個のランダムな整数になります)。

CPU パフォーマンスカウンター (CPU_CLK_UNHALTED.CORE) を使用して所要時間を測定します。

次に、ほとんどのノイズ源は一方的なもの (キャッシュミス、プリエンプションなど) であると想定しているため、5 パーセンタイルを最終測定値として採用します。トレーニング中に、計算効率を高めるために 10 台のマシンにわたって測定値を処理します。トレーニング後、AlphaDev のソリューションをベースラインソリューションと比較してベンチマークし、精度とノイズ低減を高めるために 100 台のマシンにわたる測定値を処理します。各ベンチマークについて、分位表形式の分布のない両側信頼区間を使用して信頼区間を計算します44。

拡張データ表 3a に見られるように、遅延を直接最適化する場合、AlphaDev は VarSort3、VarSort4、および VarSort5 で AlphaDev-S-WS よりも優れたパフォーマンスを示します。 AlphaDev-S-CS は、いずれの場合も解決策を見つけることができません。 VarSort4 と VarSort5 の場合、プログラムの長さとレイテンシには相関関係がありません (詳細については、補足情報を参照してください)。これは、プログラムの長さをパフォーマンスの代用として使用できない場合、AlphaDev は AlphaDev-S と比較して、より低いレイテンシのソリューションを見つけることができることを示しています。これは、確率的検索が最適に近いプログラムでウォームスタートされた場合でも当てはまります。さらに、AlphaDev は、拡張データ表 3b に見られるように、最大 1,200 万のプログラムを探索した後、最適なソリューションに収束します。これは、それぞれ AlphaDev-S-CS および AlphaDev-S-WS の値よりも桁違いに低くなります (最悪の場合、31 兆プログラム)。

私たちは、AlphaDev-S は、確率的検索手順の結果として探索能力が制限されているため、スクラッチから学習するときにプログラムを見つけるのに苦労し、ウォームスタート時に局所最適化にはまってしまうと提案しました。拡張データ図 3 は、VarSort5 のそれぞれのトレーニング手順中に発見された AlphaDev および AlphaDev-S のアセンブリアルゴリズムの 2 次元 t 確率的近傍埋め込み (t-SNE) 投影 51 を示しています。投影で使用される特徴には、正確性、レイテンシー、アルゴリズムの長さ、アルゴリズムごとに使用される命令のヒストグラム数が含まれます。拡張データの図 3a は、それぞれ AlphaDev、AlphaDev-S-CS、および AlphaDev-S-WS によって探索されたアルゴリズム空間内の領域を示しています。一方、拡張データの図 3b は、t-SNE 投影内の各点にアルゴリズムの正確さを重ね合わせています。色は、間違ったアルゴリズム (紫) から正しいアルゴリズム (黄色) まで、検出された各アルゴリズムの正しさを示します。 AlphaDev-S バリアントはどちらも、初期シードの周囲に密集した円形領域をカバーしており、確率的検索手順の幅優先の性質を強調しています。これは、AlphaDev-S-CS が最初から学習するときに、適切な時間内に誤ったアルゴリズムの空間をナビゲートして正しいアルゴリズムを発見できないことを示しています。同様の議論が AlphaDev-S-WS にも当てはまります。つまり、すでに正しいものの最適ではない専門家のデモンストレーションから最適化する場合、アルゴリズムはその近傍を探索することに偏り、この極大値を回避するのに苦労します。対照的に、AlphaDev は、長期価値関数がアルゴリズム空間の新しく興味深い部分を発見するための指針となるため、より多様なアルゴリズム空間をカバーします。拡張データの図 3b に見られるように、誤ったアルゴリズムの空間を脱出して、正しいアルゴリズムの新しい空間を発見することができ、AlphaDev によってもたらされる探索の利点が強調されています。

アセンブリプログラムを最適化するアプローチは数多くありますが、それらは列挙型検索、確率的検索、記号的検索の 3 つのグループに分類されています5。

まず、列挙型検索手法には、総当たりのプログラム列挙 4、5、6 と、記号定理証明 52、53 を使用した暗黙的な列挙が含まれます。これらのアプローチは、プログラムの空間を検索して、事前定義されたプログラムのセット、ヒューリスティック関数、および/またはコスト関数に基づいて解決策を見つけます。これらのアプローチは、特にプログラムのサイズと複雑さが増大するにつれて、プログラム空間の広い領域にまたがるのに苦労します。

第 2 に、確率的検索手法は、マルコフ連鎖モンテカルロサンプリングなどのサンプリングメカニズムに依存することで、包括的な列挙を回避します5、6、8、9。 Rajeev Alur et al.5 は、背景理論のシンボルを使用する論理式によって提供される正確性の仕様を定義しています。目標は、仕様を定義する論理式が有効となるような実装式を見つけることです。このアイデアは、テストケースを繰り返し追加し、指定されたテストケースを解決するためにプログラムを検索および拡張することです。これらは、書籍「Hacker's Joy」54 の問題の正しさを最適化します。 Phitchaya Mangpo Phothilimthana et al.6 は、手作りの枝刈りルールに依存しながら、列挙的、確率的、および記号的検索を並行して実行することに基づく LENS アルゴリズムを紹介しています。この設定では最大 21 個の命令を最適化できますが、レイテンシの最適化や分岐のサポートはできません。もう 1 つのアルゴリズム 8 は、マルコフ連鎖モンテカルロ拒絶サンプリングに基づいており、正確性とパフォーマンスの関数である損失関数を使用して、アセンブリ内のプログラムに変換を適用します。これらのアプローチの多くは極小値で行き詰まる傾向があり、プログラムのサイズや複雑さが増大するにつれて困難になる可能性もあります。さらに、実際に測定されたレイテンシーをこれらのアプローチに組み込むことは、実行不可能であるか、法外に高価です。

第三に、シンボリック検索アプローチを実装してアセンブリプログラムを最適化することもできます。これらには、SAT ソルバー 55、SMT ソルバー 5、6、および混合整数計画 (MIP) 56、57 が含まれます。ただし、これらのアプローチにはスケーリングの問題があります。たとえば、古典的なソルバーでは、問題を特定の標準形式に変換する必要があります。通常、効率的な定式化を見つけるには、前述のソルバーの専門家とかなりの時間が必要です。さらに、問題を新たに修正する場合は、これを繰り返す必要があります。従来のソルバーは並列化も難しいため、より多くのハードウェアを活用して解決プロセスを高速化することは困難です。もう 1 つのシンボリック検索アルゴリズムは、マルチフェーズアプローチを実装する Cholorphyll10 です。まず、コードとデータが存在する場所を指定するパーティション注釈を含むソースプログラムを入力として必要とします。次に、レイアウトシンセサイザーがプログラムのフラグメントを物理コアにマッピングして、計算コストを最小限に抑えます。次に、コードはコアごとのプログラムフラグメントに分割され、プログラムフラグメントはマシンコードにコンパイルされます。この時点で、スーパーオプティマイザーはこれらの各フラグメントを最適化します。

さまざまなアプローチ 58、59、60 が、単一命令複数データ (SIMD) セットアップで実行されるソート関数にも適用されています。この設定では命令の実行を並列化できますが、LLVM の libc++ std::sort ライブラリなどの一般的なライブラリでは現在サポートされていません。一例としては、Gilles Barthe et al.7 による、SIMD 命令を使用してループを自動的にベクトル化することでプログラムを最適化する方法論が提案されています。彼らは、プログラムへの変換の正しさを検証し、その変換を使用して検索ベースの手順を実行するためのフレームワークを導入することによってこれを実現します。彼らのフレームワークは、最大 9 命令の SIMD ループ構造を 0.12 秒で検出できます。これは、最小 2 倍の高速化に相当します。

プログラムの最適化に RL を使用した研究もいくつかあります。 Kevin Ellis et al.62 は、コードを記述して評価するためのポリシーと値関数を学習し、推論中にモンテカルロスタイルの検索戦略を実行します。この作業には事前トレーニングのステップが必要で、事前定義された仕様を満たす正しいプログラムを生成することを目的としています。このアプローチは、コンピュータ支援設計や文字列編集プログラムにうまく適用されています。 SuperSonic63 は、RL メタオプティマイザーを使用して異なる RL アーキテクチャ間で選択し、Multi-Armed Bandit ポリシー検索を使用して状態表現、報酬関数、および現在のタスクに最適な RL アルゴリズムを見つけます。これには、状態空間の一部として使用される多くの RL アルゴリズムとアーキテクチャを追跡する必要があります。対照的に、私たちのアプローチは、MCTS 検索と強力な状態表現を利用して、単一の RL アーキテクチャをトレーニングすることだけに焦点を当てています。 Shypula ら 64 は、教師ありアセンブリデータセットを作成し、それを使用して、最適化されていないコードを最適化されたコードにマッピングするための Transformer モデルをトレーニングし、その後、ソリューションの品質を向上させるための RL ステージを実行します。私たちの方法では、教師付きデータセットや 2 つの個別のトレーニングおよび微調整ステージは必要なく、代わりに RL と検索を使用してすべてをエンドツーエンドで最適化します。 Chen ら 65 は、独自のドメイン固有言語を定義し、中間プログラム表現をより適切に使用して合成ルーチンをガイドする入出力プログラム合成を実行しています。彼らは、Rudy Bunel et al.66 のセットアップを使用して、これを RL に組み込むことができ、生成された関数の正確性を向上できることを示しています。ただし、プログラムの長さや遅延については最適化されません。

入出力のペアからプログラムを学習するという問題には、多くの研究が取り組んでいます。アプローチの 1 つのタイプは、入力を出力に直接照合するためのニューラルネットワークを学習します11、13、67、68。このアプローチは既存のライブラリに統合するのが難しく、これまで見たことのない入力に一般化するのに苦労する可能性がありますが、グラフ表現を使用することで最近いくつかの心強い進歩が見られます69。別のタイプのアプローチは、学習されたモデルに基づいてプログラム空間で検索を実行することです12、70、71、72。たとえば、Chen et al.70 は、部分プログラムと入出力ペアに基づいて次のプログラムトークンを予測するモデルを使用しています。これは、私たちのアプローチで検索が誘導される方法といくつかの類似点があります。AlphaZero で事前に学習されたポリシーは、部分的なプログラムとそのプログラムの入力に対する影響の組み合わせに基づいて学習された、次のトークンを予測するためのモデルです。ただし、私たちは正しく効率的なプログラムを見つけることに興味があります。これは、部分プログラムの予想レイテンシーを近似するための値関数をさらに学習し、AlphaZero を使用してこの値関数を検索プロセスに組み込むことで実現します。

大規模な言語モデルを使用してコードを生成する深層学習アプローチもいくつかあります。これらのアプローチは、トランスパイル、コードのリファクタリング、コードの説明 15 から、自然言語記述 14 を使用した人間レベルの競合コードの生成まで、その用途はさまざまです。この特定の作業は、正しいコードを生成することを目的としていますが、低遅延ソリューションの生成には焦点を当てていません。

ソートアルゴリズムに取り組んだプログラム合成の研究がいくつかあります。たとえば、White et al.26 は並べ替え関数の学習に RL を使用しています。彼らの研究では、いくつかのヒューリスティックとドメイン固有の言語を使用して、強化プログラミングソートと呼ばれるソートアルゴリズムを生成しています。 Srivastava et al.27 は、プログラム合成を検証問題としてエンコードしています。具体的には、関数式、合成されたプログラムに現れるドメインとガード、およびリソース制約から構成されるタプルとして合成タスクを表します。その考え方は、事前に指定されたリソース制約が与えられると、シンセサイザーが事前に定義された仕様を満たすプログラムを生成して正確性を保証するというものです。これを適用して、マージソートとクイックソートを検出します。 Jason Ansel et al.28 は、事前に定義されたアルゴリズム (挿入ソート、マージソート、クイックソートなど) を入力として受け取り、オートチューナー機能を使用して、実行のためにこれらのアルゴリズムをいつ選択するかを決定します。これは、アルゴリズムの選択方法と実行場所を決定するルールと変換を含む言語を定義することによって実現されます。

システムのトレーニングに使用されるデータは、論文で説明されている手順に従って合成的に生成されました。 AlphaDev によって発見されたコピーおよびスワップ演算子のアルゴリズムは、主要論文で紹介されています。また、ソート 3 ～ 8 および VarSort3、4、5 用に発見された AlphaDev アセンブリ実装を Github (https://github.com/deepmind/alphadev) でリリースしました。各実装が正しいことを確認するための徹底的なテストが含まれています。さらに、補足情報の付録 G には、AlphaDev によって発見されたソート 3、ソート 4、およびソート 5 の追加の正しいソートアルゴリズムのリストが含まれています。 3 つの異なる CPU アーキテクチャと float、int32、および int64 データ型については、補足情報の付録 E で詳しく説明されています。さらに、AlphaDev のソート 3、ソート 4、およびソート 5 の実装は、LLVM libc++ 標準ソートライブラリ 3 にあります。

また、環境、完全なアクター、トレーニングループ、およびコア MCTS アルゴリズムを含む疑似コードを https://github.com/deepmind/alphadev でリリースしました。さらに、アーキテクチャの再現を可能にするポリシー、値、および表現ネットワークの実際の JAX 実装も含まれています。最後に、エージェントで使用するハイパーパラメータ定義を含む構成ファイルが完成しました。

アマゾン。 Amazon S3 - 2 兆のオブジェクト、110 万リクエスト/秒。 AWS https://aws.amazon.com/blogs/aws/amazon-s3-two-trillion-objects-11-million-requests-second/ (2013)。

Cormen, TH et al. アルゴリズム入門 (MIT Press、2022)。

Gelmi, M. sort3、sort4、sort5 のブランチレスソート関数を紹介します。 LLVM.org https://reviews.llvm.org/D118029 (2022)。

Bansal, S. & Aiken, A. のぞき穴スーパーオプティマイザーの自動生成。 ACM SIGARCH コンピューティング。アーチ。ニュース 34、394–403 (2006)。

アルール、R.ら。構文ガイド付き合成 (IEEE、2013)。

Photilimthana、PM et al. 超最適化のスケールアップ。プロセスで。プログラミング言語およびオペレーティングシステムのアーキテクチャサポートに関する第 21 回国際会議 297 ～ 310 (ACM、2016)。

Barthe、G. et al. リレーショナル検証から SIMD ループ合成まで。プロセスで。並列プログラミングの原則と実践に関する第 18 回 ACM SIGPLAN シンポジウム 123 ～ 134 (ACM、2013)。

Schkufza, E.、Sharma, R. & Aiken, A. 確率的超最適化。 ACM SIGPLAN Notices 48、305–315 (2013)。

Bunel、R. et al. プログラムの超最適化を学習します。プロセスで。学習表現に関する国際会議 (ICLR、2016)。

Photilimthana、PM et al. Chlorophyll: 低消費電力空間アーキテクチャ用の合成支援コンパイラー。 ACM SIGPLAN Notices 49、396–407 (2014)。

Vinyals、O. et al. 外国語としての文法。上級ニューラルインフォーム。手順システム。 28、2773–2781 (2015)。

Chen, X.、Liu, C. & Song, D. 入出力例から複雑なプログラムを合成する方向。プロセスで。学習表現に関する国際会議 (ICLR、2018)。

デブリン、J.ら。 Robustfill: ノイズの多い I/O の下で学習するニューラルプログラム。プロセスで。機械学習に関する国際会議 990–998 (PMLR、2017)。

リー、Ｙら。 AlphaCode による競争レベルのコード生成。サイエンス 378、1092–1097 (2022)。

ピアース、H.ら。コーデックスやその他の大規模な言語モデルは、セキュリティバグの修正に役立つでしょうか? https://arxiv.org/abs/2112.02125 (2021) でプレプリント。

チェン、M.ら。コード上でトレーニングされた大規模な言語モデルを評価します。 https://arxiv.org/abs/2107.03374 (2021) でプレプリント。

Bingmann, T.、Marianczuk, J.、Sanders, P. 少量の品目セット向けの高速仕分け機を開発。ソフトウェア: 練習します。エキスパート。 51、965–1004 (2021)。

Levcopoulos, C. & Petersson, O. Splitsort: 適応型並べ替えアルゴリズム。知らせる。手順レット。 39、205–211 (1991)。

Helman, DR、Bader, DA、JáJá, J. 実験的研究によるランダム化された並列並べ替えアルゴリズム。 J. 並列配布。計算します。 52、1–23 (1998)。

モンタナ州グッドリッチランダム化シェルソート: シンプルな忘却型ソートアルゴリズム。プロセスで。離散アルゴリズムに関する第 21 回年次 ACM-SIAM シンポジウム 1262 ～ 1277 (ACM、2010)。

Mehlhorn, K.、Sanders, P. & Sanders, P. アルゴリズムとデータ構造: 基本ツールボックス Vol. 55. (スプリンガー、2008)。

Knebl, H. アルゴリズムとデータ構造 (Springer、2020)。

Karatzoglou, A.、Baltrunas, L.、Shi, Y. 推薦システムのランク付けを学習。プロセスで。レコメンダーシステムに関する第 7 回 ACM 会議の 493 ～ 494 (ACM、2013)。

Yang, JY, Zhang, B. & Mao, Y. ネットワークベースの製造環境における情報検索ソートアルゴリズムに関する研究。応用力学と材料 Vol. 484、183–186 (トランステック出版、2014)。

Krallmann, J.、Schwiegelshohn, U.、Yahyapour, R. ジョブスケジュールアルゴリズムの設計と評価について。並列処理のためのジョブスケジューリング戦略に関するワークショップ 17 ～ 42 (Springer、1999)。

White, SK、Martinez, T. & Rudolph, G. 強化プログラミングを使用した新しいソートアルゴリズムの生成。プロセスで。進化計算に関する IEEE 会議 1 ～ 8 (IEEE、2010)。

Srivastava, S.、Gulwani, S.、Foster, JS プログラム検証からプログラム合成まで。プロセスで。プログラミング言語の原則に関する第 37 回 ACM SIGPLAN-SIGACT シンポジウム 313 ～ 326 (ACM、2010)。

アンセル、J. et al. Petabricks: アルゴリズムを選択するための言語およびコンパイラ。 ACM Sigplan Notices 44、38–49 (2009)。

スミス、DR 分割統治アルゴリズムの設計。科学。計算します。プログラム。 5、37–58 (1985)。

KR・アーバインら。 Intel ベースのコンピュータ用アセンブリ言語 (Prentice Hall、2003)。

シャノン、西暦 XXII 年。チェスをプレイするためにコンピューターをプログラミングする。ロンドン、エディンブ。ダブリンのフィロス。マグ。 J.Sci. 41.314、256–275 (1950)。

シルバー、D. et al. ディープニューラルネットワークとツリー検索を使用して囲碁をマスターします。ネイチャー 529、484–489 (2016)。

シルバー、D. et al. チェス、将棋、囲碁をセルフプレイで習得する一般的な強化学習アルゴリズム。サイエンス 362、1140–1144 (2018)。

Vaswani、A. et al. 必要なのは注意力だけです。上級ニューラルインフォーム。手順システム。 30、5999–6009 (2017)。

LLVM。 LLVM ユーザー https://llvm.org/Users.html (LLVM、2022)。

Bartlett, J. Learn to Program with Assembly 271–273 (Apress、2021)。

RS サットン & AG バルト『強化学習: はじめに』第 2 版 (MIT Press、2018 年)。

Schrittwieser, J. et al. 学習したモデルを使用して計画を立てることで、アタリ、囲碁、チェス、将棋をマスターします。ネイチャー 588、604–609 (2020)。

Maillard, O.-A.、Ryabko, D. & Munos, R. 強化学習における状態表現の選択。上級ニューラルインフォーム。手順システム。 24、2627–2635 (2011)。

Qian、R.ら。時空間対比映像表現学習。プロセスで。コンピュータービジョンとパターン認識に関する IEEE/CVF 会議 6964 ～ 6974 (IEEE、2021)。

ブラウン、T.ら。言語モデルは少数回の学習です。上級ニューラルインフォーム。手順システム。 33、1877–1901 (2020)。

Shazeer, N. 高速トランスフォーマーデコーディング: 必要なのは 1 つの書き込みヘッドだけです。プレプリントは https://arxiv.org/abs/1911.02150 (2019) にあります。

Bundala, D. & Závodny, J. 最適な仕分けネットワーク。プロセスで。言語とオートマトンの理論と応用に関する国際会議 236–247 (Springer、2014)。

Hahn、GJ & Meeker、WQ Statistical Intervals: A Guide for Practitioners Vol. 92 (ジョンワイリー & サンズ、2011)。

グーグル。プロトコルバッファ、バージョン 0.2.5。 https://developers.google.com/protocol-buffers (2022)。

グーグル。 VarInt プロトコルバッファのシリアル化および逆シリアル化、バージョン 0.2.5。 https://developers.google.com/protocol-buffers/docs/encoding (2022)。

Protvin, R. & Levenberg, J. Google が数十億行のコードを単一のリポジトリに保存する理由。共通。 ACM 59、78–87 (2016)。

バーマン、I.ら。多重衝突耐性のあるハッシュ関数とその応用。プロセスで。暗号技術の理論と応用に関する年次国際会議 133–161 (Springer、2018)。

Damgård、IB 衝突のないハッシュ関数と公開鍵署名スキーム。暗号技術の理論と応用に関するワークショップ 203–216 (Springer、1987)。

ファン、M. ソート、ビットセット (GitHub、2021)。

Van der Maaten, L. & Hinton, G. t-SNE を使用したデータの視覚化。 J.マッハ。学ぶ。解像度 9.11、2579 ～ 2605 年 (2008 年)。

グルワニ、S.ら。ループフリーのプログラムの合成。 ACM SIGPLAN Notices 46.6、62–73 (2011)。

サスナウスカス、R. et al. Souper: 合成スーパーオプティマイザー。プレプリントは https://arxiv.org/abs/1711.04422 (2017) にあります。

ウォーレン、HS Hacker's Delight (ピアソン教育、2013)。

Hamdi, Y.、Jabour, S. & Sais, L. ManySAT: 並列 SAT ソルバー。 J. 満足度、ブールモデル。計算します。 6、245–262 (2010)。

ルイジアナ州ウルジー混合整数計画法。 Wiley Encyclopedia of Computer Science and Engineering 1–10 (Wiley、2007)。

Nair、V. et al. ニューラルネットワークを使用して混合整数計画を解きます。プレプリントは https://arxiv.org/abs/2012.13349 (2020) にあります。

井上博ほか AA-sort: マルチコア SIMD プロセッサ用の新しい並列ソートアルゴリズム。プロセスで。並列アーキテクチャおよびコンパイル技術に関する国際会議 (PACT 2007) 189–198 (IEEE、2007)。

Ｙｉｎ、Ｚ．ら。 avx-512 ベースのマルチコアおよびメニーコアアーキテクチャでの効率的な並列ソート。プロセスで。 IEEE 21st International Conference on High Performance Computing and Communications 168–176 (IEEE、2019)。

ブラッチャー、M.ら。ベクトル化され、パフォーマンスが移植可能なクイックソート。 https://arxiv.org/abs/2205.05982 (2022) でプレプリント。

ウィキペディア。単一命令、複数データ https://en.m.wikipedia.org/wiki/SIMD (2022)。

エリス、Ｋ．ら。作成、実行、評価: REPL を使用したプログラム合成。上級ニューラルインフォーム。手順 Syst.32、9137–9146 (2019)。

Wang, H. et al. コード最適化のための強化学習アーキテクチャ設計を自動化します。プロセスで。第 31 回 ACM SIGPLAN コンパイラー構築に関する国際会議 129–143 (ACM、2022)。

Shypula、AG et al. 現実世界のプログラムを超最適化する方法を学習します。プレプリントは https://arxiv.org/abs/2109.13498 (2022) にあります。

Chen, X.、Liu, C. & Song, D. 実行誘導ニューラルプログラム合成。プロセスで。学習表現に関する国際会議 (ICLR、2018)。

Bunel、R. et al. ニューラルプログラム合成に文法と強化学習を活用します。プロセスで。学習表現に関する国際会議 (ICLR、2018)。

Aharoni, R. & Goldberg, Y. 文字列からツリーへのニューラル機械翻訳に向けて。プロセスで。第 55 回計算言語学協会年次総会 132–140 (ACL、2017)。

Dong, L. & Lapata, M. 神経的注意を伴う論理形式への言語。プロセスで。第 54 回計算言語学協会年次総会 33–43 (ACL、2016)。

Ibarz、B. et al. ジェネラリストのニューラルアルゴリズム学習者。プロセスで。グラフで学ぶカンファレンス Vol. 198、2:1–2:23 (PMLR、2022)。

Chen, X.、Song, D. & Tian, Y. ドメイン固有言語を超えたニューラルプログラム合成の潜在実行。上級ニューラルインフォーム。手順システム。 34、22196–22208 (2021)。

パリソット、E. et al. 神経記号的プログラムの合成。プレプリントは https://arxiv.org/abs/1611.01855 (2016) にあります。

Ellis, K.、Solar-Lezama, A.、Tenenbaum, J. ベイジアンプログラム学習のためのサンプリング。上級ニューラルインフォーム。手順システム。 29、1297–1305 (2016)。

リファレンスをダウンロードする

研究の調整にご協力いただいた P. Kurylowicz、N. Anderson、Z. Ahmed に感謝します。 L. Dionne と N. Klauser は、LLVM コードを辛抱強くレビューしてくれました。プロジェクトの進行中に有益なアドバイスをいただいた N. Vaish、D. Gove、D. Kutenin、A. Fawzi。また、DeepMind の同僚の励ましとサポートにも感謝します。

これらの著者は同様に貢献しました: Daniel J. Mankowitz、Andreamichi、Anton Zhernov、Marco Gelmi、Marco Selvi、Cosmin Paduraru、Edouard Leurent

ディープマインド、ロンドン、イギリス

ダニエル・J・マンコヴィッツ、アンドレア・ミチ、アントン・ゼルノフ、マルコ・ジェルミ、マルコ・セルヴィ、コスミン・パドゥラル、エドゥアール・ルーラン、シャリク・イクバル、ジャン＝バティスト・レスピオー、アレックス・アヘルン、トーマス・ケッペ、ケビン・ミリキン、スティーヴン・ガフニー、ソフィー・エルスター、ジャクソン・ブロシア、クリスギャンブル, キーラン・ミラン, ロバート・タン, タイラン・カムギル, モハマダミン・バレカティン, ユジア・リー, アモル・マンダーン, トーマス・ヒューバート, ジュリアン・ステップヴィーザー, デミス・ハサビス, プッシュミート・コーリ, マーティン・リードミラー, オリオール・ヴィニャルズ & デヴィッド・シルバー

Google、マウンテンビュー、カリフォルニア州、米国

ファン・ミンジェ

PubMed Google Scholar でこの著者を検索することもできます

DJM、A.Michi、AZ がこのアイデアを考案し、研究を主導しました。 A.Michi、DJM、AZ、MG、MS、CP、EL、SI、A.Mandhane がニューラルネットワークアーキテクチャとトレーニングを開発しました。 J.-BL、CP、MG、DJM、EL がベースラインを開発しました。 MG、AZ、DJM、MH、AA、TK、K.Millikin は、生成されたアルゴリズムを分析し、ソートパッチを支援しました。 DJM、A.Michi、AZ、SG、SE、JB、RT、CG、K.Milan が調査を管理しました。 A.Michi、MG、MS が技術プラットフォームを主導しました。 A.Mandhane、TH、YL、JS、TC、MB、PK、MR、DS、OV、DH が技術的なアドバイスとアイデアを提供してくれました。 DJM と AZ がこのプロジェクトを発案しました。 DJM、CP、EL、A.Michi、MG、AZ、PK、MS が論文を執筆しました。

ダニエル・J・マンコウィッツへの通信。

DJM、A.Michi、AZ、MG、MS、CP、EL、SI、A.Mandhane、PK、MR、DS、OV は、DeepMind Technologies の名前で、この論文に含まれる主題に関連する特許出願を計画しています。限定。残りの著者は競合する利益を宣言していません。

Nature は、この研究の査読に貢献してくれた Zheng Wang と他の匿名の査読者に感謝します。

発行者注記 Springer Nature は、発行された地図および所属機関の管轄権の主張に関して中立を保っています。

(a) AlphaDev 表現ネットワークは、これまでに生成されたアセンブリアルゴリズムを入力として受け取る Transformer Encoder ネットワークを構成します。また、メモリとレジスタの現在の状態を入力として受け取る CPU 状態エンコーダネットワークも含まれています。正確なアーキテクチャとハイパーパラメータについては、付録 A の補足情報を参照してください。 (b) Transformer Encoder ネットワークに命令を入力する前に、各プログラム命令のオペコードとオペランドはワンホットエンコーディングに変換されて連結されます。結果として得られるエンコードは、Transformer Encoder ネットワークに供給されます。

(a) 横線はワイヤと呼ばれ、縦線はコンパレータと呼ばれます。 (b) 最初はソートされていない値のシーケンスが、左側のソートネットワークに入力されます。さまざまな段階で、2 本のワイヤがコンパレータに遭遇します。コンパレータの上部の値がコンパレータの下部の値より小さい場合、数値が切り替わります。最適な並べ替えネットワークでは、最小数のコンパレータを使用して未並べ替えの値のシーケンスを並べ替えられるように、コンパレータを特定の位置に配置します。

(a) AlphaDev-S と比較した AlphaDev (青) によって探索された領域を示す 2D t-SNE51 投影。 (b) (a) と同じ 2D t-SNE 投影。誤ったプログラム (紫色) から正しいプログラム (黄色) までの各点にアルゴリズムの正しさが重ね合わされています。図に見られるように、AlphaDev-S は局所最適から抜け出すのに苦労しますが、AlphaDev は誤ったプログラムの空間から正しいプログラムの空間まで探索することができます。

オープンアクセスこの記事はクリエイティブコモンズ表示 4.0 国際ライセンスに基づいてライセンスされており、元の著者と情報源に適切なクレジットを表示する限り、あらゆる媒体または形式での使用、共有、翻案、配布、複製が許可されます。クリエイティブコモンズライセンスへのリンクを提供し、変更が加えられたかどうかを示します。この記事内の画像またはその他のサードパーティ素材は、素材のクレジットラインに別段の記載がない限り、記事のクリエイティブコモンズライセンスに含まれています。素材が記事のクリエイティブコモンズライセンスに含まれておらず、意図した使用が法的規制で許可されていない場合、または許可されている使用を超えている場合は、著作権所有者から直接許可を得る必要があります。このライセンスのコピーを表示するには、http://creativecommons.org/licenses/by/4.0/ にアクセスしてください。

転載と許可

マンコウィッツ、DJ、ミチ、A.、Zhernov、A. 他深層強化学習を使用して発見された、より高速な並べ替えアルゴリズム。 Nature 618、257–263 (2023)。 https://doi.org/10.1038/s41586-023-06004-9

引用をダウンロード

受信日: 2022 年 7 月 25 日

受理日: 2023 年 3 月 23 日

公開日: 2023 年 6 月 7 日

発行日: 2023 年 6 月 8 日

DOI: https://doi.org/10.1038/s41586-023-06004-9

次のリンクを共有すると、誰でもこのコンテンツを読むことができます。

申し訳ございませんが、現在この記事の共有リンクは利用できません。

Springer Nature SharedIt コンテンツ共有イニシアチブによって提供

コメントを送信すると、利用規約とコミュニティガイドラインに従うことに同意したことになります。虐待的なもの、または当社の規約やガイドラインに準拠していないものを見つけた場合は、不適切としてフラグを立ててください。