ディープマインドがAIで高速アルゴリズムを発見、C++に採用 70
ストーリー by nagazou
採用 部門より
採用 部門より
ディープマインドは、ゲームをプレイするAI「AlphaZero」の最新版に当たる「AlphaDev」を使用して、従来よりも最大70％程度、高速にソートを実行するアルゴリズムを発見したそうだ（MIT Tech Review）。
この発見されたアルゴリズムはすでにC++に組み込まれているとのこと。C++のソーティングアルゴリズムが変更されたのは10年ぶり。2022年1月にディープマインドは新しいソーティング・アルゴリズムを、C++を管理する組織に提出。そして2か月間にわたる第三者審査の結果、AlphaDevの発見したアルゴリズムがC++に取り入れられることとなったという流れだそう。
ディープマインドの研究者は、ムーアの法則の終焉とチップの基礎物理的な限界に近づいていることから、今後はコンピューティングの最適化のための革新的な手法を見つけ出す必要性があるとしている。
あるAnonymous Coward 曰く、
この発見されたアルゴリズムはすでにC++に組み込まれているとのこと。C++のソーティングアルゴリズムが変更されたのは10年ぶり。2022年1月にディープマインドは新しいソーティング・アルゴリズムを、C++を管理する組織に提出。そして2か月間にわたる第三者審査の結果、AlphaDevの発見したアルゴリズムがC++に取り入れられることとなったという流れだそう。
ディープマインドの研究者は、ムーアの法則の終焉とチップの基礎物理的な限界に近づいていることから、今後はコンピューティングの最適化のための革新的な手法を見つけ出す必要性があるとしている。
あるAnonymous Coward 曰く、
アセンブリをAIに学習させたら三倍速デソートできるようになったという話なのでC++が早くなったわけではない気はする
既出…と思ったらGIGAZINEか (スコア:2, 参考になる)
これですね。
https://gigazine.net/news/20230608-alphadev-sort-algorithm/ [gigazine.net]
Re: (スコア:0)
「3～5要素のソートで最大70％高速化しており、25万要素を超えるような大規模なソートでも約1.7％高速化できたと述べられています。」
1.7%でも大したものだとは思うけれども、70%のインパクトから本文を読むとなんかちょっと残念な印象が。
Re:既出…と思ったらGIGAZINEか (スコア:2)
大量データに対応したソートアルゴリズムは、
小数を処理するときにはオーバーヘッドが大きすぎてあまり速くないので、
今時のソートライブラリは分割統治でデータ数に応じてソートアルゴリズムを切り替えるのが一般的
というのが前提で、「最大5要素の固定要素数ソートアルゴリズム」を高速化、というのが今回の話ですね。
だから、3～5要素で最大70%(≒3倍)の高速化が、
25万要素ソートの末端で適用されることで、1.7%高速化につながる、と。
ソートというのは、
「12個の玉のうち一個だけ重さが違う。天秤を3回使って見つけ出せ」
といった数学パズルの複雑版みたいなもので、
こういうパズルで「こういう順番で比較していけば、12個のうちどれが当たりでみ見つけ出せる」という比較パターンが回答になるように
ソートも、「こういう順番で比較していけば、元データがどんな並び順であっても、その並び順を判断できる(≒正しく並べ替えられる)」ような比較パターンを構築することがキモになります。
通常のソートアルゴリズムは、汎用的に要素数可変で、それぞれのアルゴリズムで規定されたルールで比較を繰り返すことになりますし、そういうルールで比較すれば正しく並び替えられることをあらかじめ証明されたものが「ソートアルゴリズム」と呼ばれるわけですがが、
要素数固定の処理ルーチンなら、どれとどれを比較していくのかも固定になりますし、
例えば、3要素のソートなら、元データのありえる順番は「1,2,3」「1,3,2」「2,1,3」「2,3,1」「3,1,2」「3,2,1」の6通り。
5要素でも元データは120通りしかありませんから、
その全データを処理させてみれば、
「ありえるどんなデータでもソートできている」=「正しいソートアルゴリズムである」かどうかは機械的に証明可能です。
あとは正しいソートアルゴリズムとして高効率なものをAIベースで探した、ということでしょう。
Re: (スコア:0)
「最大」と聞くとワースト時の偏りも気になりますね。
Re: (スコア:0)
いくつかの入力例でテストしてOKでしょってAI様がアルゴリズム出して、
本当に正しく問題解くアルゴリズムか人間が頑張って証明するのね
Re: (スコア:0)
でも「いくつかの例」の数を膨大にしとけば偶然は防げるし、そもそも候補が既知の最短行数であることは担保されてて差分を見るだけなんだから、楽しそうではある。
アルファデブ (スコア:1)
デブとか人の体形のことをからかっちゃいけないと思います。
アルファぽっちゃり とかに改名すべきだと思います。
Re: (スコア:0)
「なんでここの開発ブランチ、pochaって名前なんすか？」
「よう知らんけど、水平展開しろって言われたらしいわ」
Re: (スコア:0)
デブなアルファ・メイルかと思った（うそ
Re: (スコア:0)
私はデブ部門で働いてます。
コンパイル時の最適化をAlphaDevにやらせた感じやね (スコア:1)
x86だね
https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms [deepmind.com]
https://www.nature.com/articles/s41586-023-06004-9 [nature.com]
Re: (スコア:0)
追記：囲碁で人類最強に勝つのと比べるとあんまりインパクトないよーな
アセンブラ得意な人が頑張れば見つけられるんじゃないかと思えてしまう
Re:コンパイル時の最適化をAlphaDevにやらせた感じやね (スコア:3)
そうかもしれないけど、ヒトが組んだコードではここ10年ほど改善されていなかったみたいですし。
今回の件も、もっと理詰めで最適化っぽいことをしたのかと思いきや、AlphaXXXでおなじみ機械学習+モンテカルロ木検索で比較的短いコードを改善できたという話なので、「人類もっと頑張れ！」というべきか「もう面倒な仕事はAIに任せていいんじゃね？」というべきか…。
Re:コンパイル時の最適化をAlphaDevにやらせた感じやね (スコア:1)
> もう面倒な仕事はAIに任せていいんじゃね？
AIがやるのは面白い仕事で、面倒な仕事（テスト）とかAIのやらかしの責任とるとかが人間に任される。
Re: (スコア:0)
アルゴリズムの変更による高速化は別として、機械語レベルの最適化はもう仕事でするものではないと思います。
Re: (スコア:0)
ベンチマーク ARMもあったね
https://docs.google.com/document/d/15gW8btGdWPzHaUEDp1EMa2PZguVKgVv-ok... [google.com]
三倍速デソート (スコア:0)
ツノをつけて赤く塗ったに違いない
# デソートって何
Re:三倍速デソート (スコア:1)
># デソートって何
Deluxe Sort
Delicious Sort
Devil Sort
Death Sort
どれでしょね、あるいは他のナニカ
Re: (スコア:0)
そりゃランダマイズのことだろうな
Re:三倍速デソート (スコア:1)
でソートがデソートになったんですよ。
もう許してくださいよ。
Re: (スコア:0)
本当の意味でランダマイズができるとしたら割と有用な気がする。
Re: (スコア:0)
元に戻る汎用ルーチンだったらもっとすごいですよ。
それはunsort()かな。
Re: (スコア:0)
それで早くなるのだとしたら元の1.3倍、体感速度が3倍ってだけ
Re: (スコア:0)
デソートザクだ
あれか (スコア:0)
シャア専用アルゴリズム
Re:あれか (スコア:1)
charだけなんです。
アルゴリズムというか，実装のこと? (スコア:0)
多分，ニーモニックをどう並べるかという問題を
改善したということなのだと思うけど。
ランタイムライブラリのアセンブリ実装の改善ね。
それともコンパイラの最適化アルゴリズムまで手を入れたのだろうか。
具体的なデバイスの(ISAの)名前もないし，
なんか舌足らずな記事だなぁ(元記事からして)
Re: (スコア:0)
そもそも C++ の規格的にはアルゴリズムは指定されていなかったような。
関数の満たすべきパフォーマンス要件が指定されているだけで。
Re: (スコア:0)
一部は安定性を規定されているね。
Re: (スコア:0)
あと比較関数の呼び出し回数がO(logN)でなければならないという規定もあったような
Re: (スコア:0)
ステップを（AIにとって）可視化するためにアセンブリが適してるってだけで、同じ手法を使えば最低クロックのバイナリ生成もできるんだろうけど、とんでもない時間がかかりそう。
Re: (スコア:0)
最適化にAI使うのね。
クラウドのコンパイラ。
ただし，正しいかどうかは実行してみないとわからない。
当たるも八卦当らぬも八卦な
八卦コンパイラ。
# 誰が使うかこんなの
Re: (スコア:0)
使ったというニュースなのでは? もちろん人間のレビューは入っているようだが
Re: (スコア:0)
横だが、
ソートのバイナリコードで最速を目指す際に、機械学習（恐らくは強化学習）を使っただろうが、それと同様に、
「何度もトライしては実行ステップ数などで評価して、最も良いコードを採用する」
といった過程を、何かしらソースをコンパイルする度に行えば？と言っているんだと思う。
現時点では実験でしか行われないだろうなあ。
Re: (スコア:0)
「C++を管理する組織」って標準化委員会だと思って読んでたから
てっきりqsort()に代わる関数が追加されるのかと思いました。
何かよくわからん記事ですね。
グラディウスシリーズの安地はみつかるか？ (スコア:0)
ブロック崩しの学習結果は動画ととおりである。
機械的学習のほかに人のプレイを学習できる部分が加われば
最強のプレイヤーが作れそうだ。
Breakout | DeepMind | WIRED
https://www.youtube.com/watch?v=Q70ulPJW3Gk [youtube.com]
遺伝的アルゴリズム (スコア:0)
記事を見たけど、遺伝的アルゴリズムと何が違うのかなー、と思った。
Re: (スコア:0)
それは機械学習全般に言えることでは…
Re: (スコア:0)
そんなこと言ったら何でもGAになっちゃうよ〜ん
シェキシェキ
Re: (スコア:0)
いわゆるディープラーニングって、学習データとの誤差から計算してパラメーターの調整してくんでしょ
遺伝的アルゴリズムは交叉とか突然変異とかで適当にパラメータいじって、その中から優秀な奴を選抜するんじゃないの
結構違うと思うけど
Re: (スコア:0)
>いわゆるディープラーニングって、学習データとの誤差から計算してパラメーターの調整してくんでしょ
違うよ。
Re: (スコア:0)
どうなの
Re: (スコア:0)
君はバックプロパゲーション使わんのかね？
https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%83%E3%82%AF%E3%83%97%E3%... [wikipedia.org]
Re: (スコア:0)
手法の一種であることは否定しないけど、それが全てではないでしょ。
誤差逆伝播しないとディープラーニング名乗れんのか？
Re: (スコア:0)
過去の手を記憶したり、さらに記憶をニューラルネットにやらせたりする所が違う。囲碁を打つとかだともっと違う。
単に違いを言うならば、現状、囲碁を遺伝的アルゴリズムで打つようにした上で、最強とされる人間に勝つ、とかは出来ていないなあ。
早くなった (スコア:0)
>アセンブリをAIに学習させたら三倍速デソートできるようになったという話なのでC++が早くなったわけではない気はする
で、その三倍速のコードがC++のオフィシャルな管理組織に採用されたって話なんだから、やっぱりC++が速くなったって話じゃん
# まぁ「速くなった」のだから、「早くなった」わけではないかもね
Re: (スコア:0)
タレコミだとまるでC++標準化委員会に規格文章でも提出したかのように読めるけど、実際はLLVMに実装(libc++)の変更をコミットしたというだけの話らしいぞ。
Re: (スコア:0)
LLVMってそこまでオフィシャルでもないような。まあ、影響力は大きいと思うけど。
libstdc++には実装されたのか？ (スコア:0)
簡単に使えるようになると助かるのだが。
Re:libstdc++には実装されたのか？ (スコア:1)
Clang/LLVMに入ったみたいだがGCCは知らん
https://reviews.llvm.org/D118029 [llvm.org]