Autotuning PolyBench Benchmarks with LLVM Clang/Polly Loop Optimization Pragmas Using Bayesian Optimization

[yukarinoki]

https://chatgpt.com/share/6706068b-0540-800d-8582-6c17a7582d9f

概要—オートチューニングは、カーネルやアプリケーションの実装や設定の探索空間を調査するアプローチであり、ターゲットプラットフォーム上で実装や設定のサブセットを選択し評価することで、高性能な実装や設定を特定する方法です。また、モデルを利用して高性能な実装や設定を見つけることもあります。本論文では、ベイズ最適化を活用してパラメータ空間の探索を行うオートチューニングフレームワークを開発しました。PolyBenchベンチマークスイートのアプリケーションドメインから、最も複雑な6つのベンチマーク（syr2k、3mm、heat-3d、lu、covariance、Floyd-Warshall）を選び、新たに開発したLLVM Clang/Pollyのループ最適化プラグマをこれらのベンチマークに適用して最適化しました。その後、オートチューニングフレームワークを用いて、プラグマパラメータを最適化し、性能を向上させました。

実験結果では、我々のオートチューニングアプローチが他のコンパイル手法よりも優れた性能を発揮し、syr2k、3mm、heat-3d、lu、およびcovarianceのベンチマークにおいて、2つの大規模データセットを用いた200回のコード評価で、最大170,368の異なる設定を効果的に探索し、最短の実行時間を達成しました。また、ベイズ最適化内で4つの異なる教師あり学習手法を比較し、その有効性を評価しました。Floyd-Warshallベンチマークについては、Pollyが使用するヒューリスティックによってベンチマークが非常に遅くなるため、オートチューニングの恩恵を受けることができなかったことがわかりました。この問題に対処するため、性能を改善するためのコンパイラオプションの解決策を提案します。

[yukarinoki]

• [ ] 新たに開発したLLVM Clang/Pollyのループ最適化プラグマとは何か？
• [ ] オートチューニングフレームワークとは、何か？

[yukarinoki]

オートチューニングは

• ヒューリスティック
• モデルベース
• 機械学習

A large amount of literature on autotuning exists. Balaprakash et al. [3] surveyed the state of the practice in incorporating autotuned code into HPC applications; the authors highlighted insights from prior work and identified the challenges in advancing autotuning into wider and long-term use. Traditional autotuning methods are built on heuristics that derive from experience [6], [9], [25] and model-based methods [2], [8], [26]. At the compiler level, machine-learning-based methods are used for automatic tuning of the iterative compilation process [17] and tuning of compiler-generated code [15], [27]. Some recent work has used machine learning and sophisticated statistical learning methods to reduce the overhead of autotuning [14], [19], [28]. Most recent work on autotuning of OpenMP code has gone beyond loop schedules to look at parallel tasks and function inlining [10], [16], [24]. In particular, a lightweight framework was proposed to enable autotuning of OpenMP pragmas to ease the performance tuning of OpenMP codes across platforms [24]; the approach incorporated the Search using Random Forests (SuRF). SuRF is the earliest version of the parameter space search ytopt [31]. Currently, ytopt leverages Bayesian optimization [4], [22] to explore the parameter space search and uses different supervised learning methods within Bayesian optimization such as random forests, Gaussian process regression, extra trees, and gradient boosted regression trees.

[yukarinoki]

新しいプラグマを作ってる人もいる

KruseとFinkel[11]は、ユーザー指導型ループ変換の新しいプロトタイプをClangとPolly[18]を使用して実装し、ループ反転、ループ交換、タイル化、配列パッキングなどのループ変換プラグマをDOEのExascale Computing Project（ECP）SOLLVE[23]に追加しました。SOLLVEは、高品質で堅牢なOpenMPの実装とその拡張をLLVMに提供することを目指しています。このプラグマと関連するパラメータの組み合わせを効率的に最適化するためには、さらなる研究が必要です。

[yukarinoki]

この論文では、KruseとFInkelが作った、SOLLVE Clang/Pollyループ最適化プラグマとパラメータ探索ytoptを組み合わせた。 パラメータ探索に、ベイズ最適化を使うことが、新規性なのかな？

[yukarinoki]

• ECP SOLLVEプロジェクト[23]
• ClangとPolly[18] というのが何か調べる

[yukarinoki]

• ループ反転（ループの反復順序を逆にする）
• ループ交換（ネストされたループの順序を変更する）
• タイル化
• アンロール（およびジャム）
• 配列パッキング（ループの作業セットのデータを一時的に新しいバッファにコピーする）
• スレッド並列化

配列パッキングとは

配列パッキングとは、ループ内で頻繁にアクセスされるデータを、新しい連続したバッファ（メモリ領域）に一時的にコピーして使用する最適化手法です。これにより、データがメモリ内で連続した場所に配置され、キャッシュメモリへのアクセスが効率的になります。結果として、メモリアクセスパターンが改善され、キャッシュのヒット率が高まり、プログラムの実行速度が向上することが期待できます。

この手法は、特にデータがバラバラなメモリ位置にある場合に有効で、ループ内でアクセスされるデータを連続したメモリブロックにパック（詰め込み）することで、CPUのキャッシュ性能を最大限に引き出すことを目的としています。

[yukarinoki]

ytoptは機械学習最適化・ベイズ最適化

• ユーザーが定義したパラメータ空間（境界や制約）と、パラメータ構成の評価インターフェースを入力として受け取ります。
• optunaみたいな感じ

[yukarinoki]

PolyBenchベンチマーク

PolyBench 4.2 [32]は、さまざまなアプリケーション分野から抽出された30の数値計算で構成されるベンチマークスイートです（19の線形代数計算、3つの画像処理アプリケーション、6つの物理シミュレーション、2つのデータマイニングアプリケーション）。ベンチマークの詳細は以下の通りです。

• 線形代数:

  • BLAS (7種類): gemm、gemver、gesummv、symm、syr2k、syrk、trmm
  • カーネル (6種類): 2mm、3mm、atax、bicg、doitgen、mvt
  • ソルバー (6種類): Cholesky、durbin、gramschmidt、lu、ludcmp、trisolv

• Medley（画像処理）(3種類): deriche、floydwarshall、nussinov

• 物理シミュレーション（ステンシル） (6種類): adi、fdtd-2d、heat-3d、jacobi-1d、jacobi-2d、seidel-2d

• データマイニング (2種類): correlation、covariance

最も複雑でネストしたループのレベルが多いベンチマークが太字 syr2kは対象行列積 3mmも行列積

[yukarinoki]

最も複雑でネストしたループのレベルが多いベンチマークが

#pragma clang loop(i,j,k) tile sizes(#P3,#P4,#P5)
floor_ids(i1,j1,k1) tile_ids(i2,j2,k2)
#pragma clang loop id(i)
for (i = 0; i < _PB_N; i++) {
    #pragma clang loop id(j)
    for (j = 0; j < _PB_M; j++) {
        #pragma clang loop id(k)
        for (k = 0; k <= i; k++) {
            C[i][k] += A[k][j]*alpha*B[i][j] + B[k][j]*alpha*A[i][j];
        }
    }
}

• アプリケーションコードを分析して、重要なパラメータを特定。
• それらのパラメータをシンボル（#P0, #P1, #P2, ...）に置き換えてコードテンプレートを作成。
• ytoptオートチューナーの入力として、これらのシンボルの値の範囲を定義。
• ytoptオートチューナーを使用してパラメータ空間を探索し、新しいコードを生成。
• 生成されたコードをコンパイル・実行し、実行時間を測定。
• 実行結果を性能データベースに記録し、探索を繰り返す。