Learning to Parallelize with OpenMP by Augmented Heterogeneous AST Representation
本論文は、拡張されたヘテロジニアスなAST表現と新たに作成されたOMP_Serialデータセットを利用した新しいグラフベースの学習手法であるGraph2Parを提案し、OpenMPによる並列化可能なループの検出において、既存の最先端のトークンベースの手法を凌駕する85%の精度を達成する。
原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。 免責事項の全文を読む
現代のコンピュータは、それぞれがコンマ数秒でタスクをこなすことができる小さな作業員がひしめき合う、広大な都市のようになっています。これらのマシンを高速に動作させるために、プログラマーは、作業員を一人ずつ順番に並べるのではなく、多くの作業員を同時に送り出して仕事をさせる方法を教えなければなりません。パラレル化（並列化）として知られるこの手法は、今日の強力なハードウェアの性能を最大限に引き出すために不可ло欠です。しかし、コンピュータにどのように仕事を分割させるかを伝えるのは困難な作業です。それには、プログラムの異なる部分が互いにどのように依存しているかについての深い理解が必要です。もしプログラマーの推測が間違っていれば、プログラムはクラッシュしたり、誤った答えを出力したりする可能性があります。何十年もの間、専門家たちは、こうしたチームワークの機会を自動的に見つけ出すためのツールを構築してきましたが、それらのツールは慎重になりすぎて多くのチャンスを見逃したり、複雑なコード構造によって混乱したりすることがよくあります。
最近の研究において、研究者たちは、機械が言語を理解する方法に触発された手法を用いて、コンピュータ自身にこれらの機会を認識させることを試みました。アイオワ州立大学とインテル・ラボのリー・チェン氏らが率いるチームは、Cプログラミング言語で使用される「OpenMP」と呼ばれる特定の種類の命令に焦点を当てました。これらの命令は、コンピュータに対して、どこで複数の作業員を同時に開始しても安全であるかを伝える標識のような役割を果たします。課題は、厳格な数学的ルールに依存している既存のツールが、木を見て森を見ずの状態に陥りやすいことでした。従来の解析器にとって複雑に見える関数呼び出しや入れ子構造が含まれているという理由だけで、完璧に並列化可能なループを見逃してしまうことがあるのです。研究者たちは、これを解決するためには、コードを単なる言葉の羅列としてではなく、その構造と意味を持つ「地図」としてコンピュータに示す新しい方法が必要であると気づきました。
この課題に取り組むため、チームはまず、OMP Serialと名付けた膨大な例のライブラリを構築する必要がありました。彼らは、すでに並列化としてマークされている約18,600個のループと、並列化されていない約14,000個のループを集めました。これらは、インターネット上にある数千の現実世界のソフトウェアプロジェクトや、特定のパターンをテストするために慎重に作成された合成例から抽出されました。このコレクションは、学習のための豊かな正解（グラウンド・トゥルース）となりました。しかし、データを持っているだけでは戦いの半分に過ぎません。それを真にコードを理解できる機械学習モデルに投入する方法が必要でした。コードを本の中の一文のように（つまり、単語の順序が最も重要であるように）扱うのではなく、彼らはそれを複雑な地図として扱うことにしました。彼らは「拡張されたヘテロジニアス抽象構文木（augmented heterogeneous abstract syntax tree）」と呼ばれる表現を作成しました。簡単に言えば、これはコードのあらゆる断片を接続する詳細なグラフです。それは、親コマンドとその子コマンドのようなプログラムの階層構造だけでなく、コードが次のステップへとどのように流れるか、そしてコード内の単語がテキスト内でどのように隣接しているかをも示します。この地図は、プログラムの構造的な骨組みを捉えると同時に、単純な単語のリストでは見落としてしまうような、異なる部分間の微妙な関係性をも保持しています。
この新しい地図を手にした研究者たちは、ヘテロジニアス・グラフ・トランスフォーマーとして知られる高度な学習モデルを訓練しました。このモデルを、何千ものこれらの地図と、それぞれの正しい答え（そのループが並列化可能か、そうでないか）を見せられている学生だと想像してください。モデルは、安全性を判断するための隠れたパターンを見つけ出すことを学びます。モデルは地図における異なる種類の接続に注意を払い、例えば、関数呼び出しと変数の間のリンクが、二つの数学的演算の間のリンクとは異なる意味を持つ可能性があることを理解します。訓練後、モデルは、どのループを並列化できるか、そして決定的なことに、それを行うためにどの特定の種類の命令を使用すべきかを予測する能力についてテストされました。結果は驚くべきものでした。モデルは、並列化可能な領域を検出するにおいて85パーセントの精度を達成し、従来の静的解析に依存する最良の既存ツールを大幅に上回りました。
また、この研究は、従来のツールが具体的にどこで失敗していたのかも明らかにしました。研究者たちは、従来のソフトウェアが最も多くミスを犯すのは、関数呼び出しを含むループ、大量のデータを単一の値に集約（リデュース）するループ、そして他のループの中にネストされたループであることを見出しました。これらは、厳格な解析器にとってはコードが乱雑に見えるものの、実際には並列作業に安全な、非常にトリッキーなケースです。対照的に、新しい機械学習のアプローチは、これらの複雑な構造をはるかに高い成功率で処理しました。それは単に推測したのではなく、コードの形状の背後にある論理を学んだのです。研究者たちは、豊かな構造的視点と強力な学習アルゴリズムを組み合わせることで、長い間人間の直感に頼ってきたタスクを自動化できることを実証しました。この研究は、高速なソフトウェアを書くための未来が、コンピュータのためのより優れたルールブックにあるのではなく、熟練した人間のプログラマーのように、コードを静的なコマンドの連鎖としてではなく、生きた相互接続されたシステムとして見る方法をコンピュータに教えることにあることを示唆しています。
自分の分野の論文に埋もれていませんか？
研究キーワードに一致する最新の論文のダイジェストを毎日受け取りましょう——技術要約付き、あなたの言語で。