AlphaGoの開発元として有名なGoogle DeepMind社が深層強化学習を応用してさまざまなコンピューティングアルゴリズムを改善するAI「AlphaDev」を発表しました。同時に、AlphaDevを利用してソートアルゴリズムを高速化できたという論文がNatureに掲載されています。

AlphaDev discovers faster sorting algorithms

https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms

Faster sorting algorithms discovered using deep reinforcement learning | Nature

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

ソートアルゴリズムとは、バラバラな状態のデータを順番通りに並び替えるアルゴリズムです。検索結果やSNS投稿のランク付けをはじめ、一般的なアプリのあらゆる部分で活用されており、世界中を合わせると毎日何兆回と実行されています。非常に重要で基礎となるアルゴリズムのため、世界中の研究者たちによって何十年と改善され続けており、すでにこれ以上ないほど効率的な実装となっていました。



しかし、人間による改善活動は主にC++のコードレベルで行われています。C++で書かれたコードは、実際にコードが実行される前にアセンブリ言語にコンパイルされ、その後アセンブラによって機械語に変換するという手順を踏みます。DeepMindの研究チームはこの「アセンブリ言語」レベルであれば、C++のコードからは見つからないような改善点が見つかると考えたとのこと。



AlphaDevはAlphaZeroをベースにしたAIで、ソートを1人用の「組み立てゲーム」とみなしてトレーニングすることでアルゴリズムの改善を行えるようにしたとのこと。AlphaZeroについては下記の記事で解説しています。

世界最強の囲碁AI・AlphaGoがあらゆるボードゲームを学習できる「AlphaZero」に進化 - GIGAZINE



「組み立てゲーム」のイメージ図は以下の通り。AlphaDevは各ターンにおいてCPUに保存されている情報と生成済みのアルゴリズムを確認し、新たにアルゴリズムに命令を追加します。アルゴリズムの構築が完了すると、そのアルゴリズムを実行してテスト・答え合わせを行い、正答できたかどうかと正答までの時間でスコアを算出しています。正しい答えを出せる高速なプログラムを発見できると勝利というわけです。



この手法を利用することで、AlphaDevはオープンソースのコンパイラー基盤「LLVM」で利用されている標準ライブラリ「libc++」のソートの実装を高速化できたとのこと。3〜5要素のソートで最大70％高速化しており、25万要素を超えるような大規模なソートでも約1.7％高速化できたと述べられています。

3要素のソートを例に挙げると、AlphaDevは前の処理で2つの入力の大小が事前に固定されている場合があることを見逃さずに命令数を1つ減らすことができたとのこと。



また、従来であれば下図の左のように要素数次第で「4要素用の処理」「3要素用の処理」「2要素用の処理」と分けていたところを、下図右のように3要素以上の場合においていったん3要素用のソート処理を行い、もし4要素だった場合は後から単純な処理を付け足すという手法で大きく処理速度を改善しました。



AlphaDevが開発したソートアルゴリズムはLLVM libc++に導入済みで、すでに何百万人もの開発者たちに利用されています。

AlphaDevはソートアルゴリズムだけでなく、ハッシュ関数の高速化にも成功しています。ハッシュ関数が最も利用されているデータ構造用の処理に注力した結果、9〜16バイトの入力において30％高速にハッシュを計算することが可能になったとのこと。この改善されたハッシュ関数はAbseilライブラリに導入済みと述べられています。