スマートコンパイラの明るい未来に向けて

現在、機械学習と人工知能のトピックは非常に人気がありますが、現時点では、コンピューターの計算能力のおかげで、長い間生まれてきたアイデアとアルゴリズムを実装し、大幅に改善することができます。 ほぼ毎日、この分野の新しい成果に関するニュースを読むことができます。 さらに、機械学習はほとんどすべての分野で使用されています...そしてコンパイラの開発も例外ではありません。 ただし、この領域は非常に具体的であり、独自の特性とスマートコンパイラの作成が困難です。 同時に、このトピックに関する多くの研究があり、学術環境とさまざまな企業の両方で長い間行われてきました。



コンパイラを作成するときに機械学習方法を正確に適用しようとしているのはどこですか そして、なぜこれまで「スマート」コンパイラーが開発者の日常生活の一部になっていないのですか？

コンパイラー開発で機械学習を使用するためのオプション

機械学習の特定の使用に関する最初の質問から始めましょう。 実際、最新のコンパイラーは、より効率的なマシンコードを取得できる最適化を多数備えた複雑なシステムです。 ただし、最適化およびレジスタ割り当てなどの他のタスクの一部はNP完全であり、コンパイラ開発者にヒューリスティックアルゴリズムの使用を強制します。 その結果、ほとんどのコンパイラには、使用するヒューリスティックを構成できる最適化フラグが多数あります。 LLVMでは、ほとんどすべてのパッセージに、操作に影響する可能性のあるいくつかの隠されたオプションがあり、clangを呼び出すときに-mllvmフラグを使用するか、optユーティリティで使用できます。 ただし、この多様なフラグは、一度に多くの設定が含まれ、通常最適化レベルと呼ばれる、より頻繁に使用されるオプションの背後に隠れています。 C / C ++コンパイラの場合、これらはほとんどの-O1、-O2、-O3がランタイムを最適化し、-Osがコードサイズを最適化することで知られています。 しかし、残念なことに、最適なコードが常に結果となるわけではなく（アセンブラーの専門家が生成されたコードを最適な方法で書き換えることができます）、多くは高レベル言語のソースコード、プロセッサアーキテクチャ、言語機能などに依存します。



今日の最新のプロセッサには十分なRAMと非常に高いパフォーマンスがあるにもかかわらず、アプリケーションのパフォーマンス、エネルギー効率、マシンコードサイズが重要な役割を果たしている領域がまだあります。 そのような領域の例は、RAMの量が限られている組み込みシステム、デジタル信号処理、リアルタイムシステムなどのソフトウェア開発です。 したがって、十分な規模のシステムで高性能のマシンコードを取得する必要がある場合、最良の結果をもたらす正しいコンパイルオプションの選択は重要なタスクです。 さらに、リアルタイムシステムがプラットフォーム上の特定のタスクの実行時間を可能な限り計算して最小化する必要がある場合、ワーストケースランタイム（ WCET ）の問題はなくなりませんでした。 これまで、RAMの量が限られているシステムで作業するプログラマーは、コンパイラーに完全に依存することはできず、多くの場合、生成されたマシンコードを独立して最適化します。



どの最適化が良い結果をもたらし、リグレッションにつながる可能性があるかを予測することは困難です。これには、使用されるヒューリスティックアルゴリズムの複雑さ、使用されるコンパイラの構造とパッセージに関する十分な知識、およびコンパイルされたプログラムのコードを完全に知る必要があるためです現在のアプリケーション開発プロセスは不可能です。 その結果、個人のプログラムに最適なコンパイルオプションを特定することは、オプションのさまざまな組み合わせとパフォーマンスとコードサイズの測定値を徹底的に検索するタスクになります。



さらに、編集ユニットの形式には制限があり、それを使用してオプションを選択できます。 C / C ++の場合、これはまだ多くのコードを含むことができるファイルであり、おそらくさまざまな方法で最適化することが有用ですが、現時点ではこれは不可能です。 したがって、さまざまな場合に最適化されたコードをトレーニングしてから取得できる「スマート」コンパイラは、一部の開発者にとっては夢です。

既存の研究とソリューション

当然、コンパイルオプションの自動選択の問題は、長年にわたって研究者の関心を集めてきました。 最も有名なプロジェクトの1つは、G。Fursinと彼のMILEPOST GCCチームの研究者の開発です。これは、gccコンパイラーのバージョンであり、取得したデータサンプルの以前のトレーニングに基づいて最適化パスを選択できます。 この作業では、55個の特性のセットを使用して問題を解決し、最近傍のKアルゴリズムに基づいて適切なソリューションを配布するという考えに基づいたかなり単純なモデルを使用しました。 この開発により、最適化パスの調整により、標準の最大最適化オプション-O3を使用して取得したコードの2倍のコードが得られることが示されました。



G. PekhimenkoとA.D.による研究もあります。 IBMのTPO（ トロントポータブルオプティマイザー ）のブラウン。 彼らの主なタスクは、最適化およびコード変換の非常にセットのために、発見的に選択可能な値を選択することでした。 実装には、ロジスティック回帰が使用されたため、効果的な罰金設定を行ってトレーニングを迅速に行うことができました。 分類器はMatlabで作成されました。 使用の確率はパスごとに計算され、50％を超える場合に適用されました。 この調査で削減しようとした特性の結果、静的コンパイル時間が発生しました。



A.Askhariは、プログラム全体のコンパイルオプションを一度に直接選択して、実行時間、コンパイル時間、コードサイズ、消費電力を最小限に抑えました。 G. FursinとA. Lokhmotov（ GitHubでも開発）が開発したcTuning FrameworkとCollective Mind Frameworkがこれに使用されました。



M. StephensonとS. Amarasingeによる、特定の特に重要なアルゴリズム（レジスタの割り当て、データのプリフェッチ、ハイパーブロックの形成）の最適化の選択に関する研究もあります。 それに応じて、機能ごとに独自の特性が使用されました。 解決策として、遺伝的アルゴリズムが使用されました。 開発された製品のテストは、Open Research Compiler（ORC）で実施されました。



MAGEEC （Machine Guided Energy Efficient Compiler）プロジェクトもありますが、その目標は多少異なります。 開発されたインフラストラクチャは、機械学習を使用して、高性能コンピューティングシステムのエネルギー効率を最大化するコードを生成するために必要な最適化を選択します。 MAGEECは、gccとLLVMの両方で動作するように設計されています。 このコンパイラは、大規模なTSERO（Total Software Energy Reporting and Optimization）プロジェクトの一部です。



LLVMに直接関係する研究の1つは、イリノイ大学でI. ChenとW. Adweによって開発されたソフトウェア製品であるLLVMTunerです。 2017年には、その時点で得られた結果を説明するレポートが発表されました。 このホワイトペーパーでは、個々の「ホット」サイクルを最適化しました。 このフレームワークは、大規模プログラムの自動構成用に設計されています。 LLVMTunerはLLVM IRミドルウェアで実行され、プロファイリングを使用してホットループを識別し、それらのヒューリスティックを自動的に設定します。 焦点はトップレベルのサイクルです。 選択されたサイクルとすべての呼び出し関数は、必要な最適化がさらに行われる別のモジュールに転送されます。 このソリューションにより、大規模プログラムのパフォーマンスを向上させることができます。

既存の問題

ただし、パスの最適化のヒューリスティックを個別に調整する、広く使用されているコンパイラはありません。 問題は何ですか？ ご存じのように、機械学習手法の適用の有効性と取得したモデルの品質は、適切な機能の選択とトレーニング用のデータの品質に依存します（「ノイズの多い」データの影響を受けにくいアルゴリズムの存在にもかかわらず）。 コンパイラで使用される構造とアルゴリズムを知らないと、トレーニングのために完全かつ十分な特性セットを選択することは容易ではありませんが、例えば、サイクルのサイズ、サイクルからの出口の数など、非常に理解可能で論理的な特性があります したがって、一度に多くのコンパイラに適した普遍的なソリューションを開発することは困難であり、一般的に可能であるという事実ではありません。 さらに、これは必須ではない可能性があります。



コンパイラの開発は非常に短時間で効率的かつ実行可能である必要があるため、大企業であっても既成のソリューションに基づいて産業用コンパイラを開発するのは自然です。 ほとんどの最新のソリューションは、2つのカテゴリに分類できます。たとえば、JVMのような仮想マシンで実行する-JITコンパイラと、LLSCに基づくコンパイラ、RISCのような命令で仮想マシンを実装するシステム-静的および動的コンパイラです。 もちろん、ソリューションを所有している企業はまだありますが、それらで使用される技術の開発に関与する大規模なコミュニティが不足しているため、競争力は低下しています。 その結果、今日、Google、Apple、Adobe、ARMなどの多くの大企業は、LLVMを使用して独自のソリューションを開発しています。 もちろん、gccはC / C ++のメインコンパイラであり、他の言語のソリューションは他にもありますが、とにかく、たとえばLLVMのソリューションが見つかった場合は、既存のコンパイラのかなりの部分を既にカバーしています。



また、マルチパスコンパイラは中間表現を強力に変換するため、トレーニング自体の特性のコレクション自体が大きな問題になります。初期段階で収集された特性は、後のコンパイラの最適化にはあまり関係がないため、これらの特性は高い確率で変化します。 特性は、さらに、さまざまなタイプの要素（モジュール、サイクル、ベースブロック）について個別に収集するのが理にかなっています。通常、最適化はLLVMで特定のタイプの要素を変更するように設計されているためです。



しかし、最初に、特性を収集する必要がある要素を識別するという問題が生じます。 すべての最適化中に保存できる一意の識別子を計算する多くの方法があります。たとえば：

• ASTベースのフロントエンドハッシュ
• フロントエンド解析で割り当てられた一意の番号
• チェックサムを使用してCFG（制御フローグラフ）のアークに基づいて生成された64ビット数（LLVMのPGO（プロファイルガイド最適化）に類似）

ただし、変換中にこれらの識別子を適切に保持する必要があります。要素を1つにマージ、分離、新しい要素を作成、元の要素を削除することができますが、これは簡単な作業ではありません。



第二に、変換済みのIRについて、ソースコードで記述されたソースサイクル、ベースブロックなどの境界を評価することは原則として困難です。 たとえば、LLVMで採用されたマシンコードの多段階生成により、AsmPrinterのマシン命令に基づくコード生成後にマシンベースユニットに関する情報が失われます。 したがって、ベースブロックとサイクルの識別子に関する情報も失われます。たとえば、関数の先頭からのオフセットが測定されます。したがって、この方法では、マシンコードを生成する段階でのみ、バイト数による命令としてオフセットを取得できます。 ただし、マシンコードを生成する後続の段階で、マシンフラグメントを使用する場合、さまざまなアライメントを追加できます。これにより、以前に考慮された命令のサイズが変更され、nop命令も追加されます。 このため、大きな関数の最後にあるベースブロックの場合、計算エラーは非常に大きくなり、別のブロック/サイクルに完全にシフトします。 また、後の段階での変換の一部は追跡して考慮することができますが、命令のサイズはリンカーによって異なる可能性があるため、測定の正確性は保証されません。







ご覧のように、トレーニングを行う必要があり、意思決定のためのトレーニング済みモデルの入力セットになる可能性のある機能のコレクションでさえ、非常に複雑で時間がかかります。 また、これらの問題に対する明確な解決策はありません。これは、十分なデータセットの不足により、機械学習と多数の人々を引き付けることに関連する当面の作業を複雑にします。 さて、機械学習の問題の解決策を見つけること、モデル、方法を選択すること、多数の属性を持つ正しい属性のサブセットを決定することなどの典型的な困難。 この場合に存在します。 機械学習に出会ったほとんど誰もがそれらについて知っており、おそらく、ここにはコンパイラーに固有で特定のものはありません。



スマートコンパイラがいつ普及するかを予測するのは困難です。 最近のコンパイラには、この方法で解決される可能性が低い他の問題もあり、現時点ではおそらくより優先されます。 しかし、コンパイラーはすでに、外観の夜明けよりもはるかにインテリジェントになっており、ほとんどの開発者が望むよりもやや遅いかもしれませんが、このプロセスは続きます。