Fugu-MT 論文翻訳(概要): Customized Monte Carlo Tree Search for LLVM/Polly's Composable Loop Optimization Transformations

論文の概要: Customized Monte Carlo Tree Search for LLVM/Polly's Composable Loop Optimization Transformations

arxiv url: http://arxiv.org/abs/2105.04555v1
Date: Mon, 10 May 2021 21:57:39 GMT
ステータス: 処理完了
システム内更新日: 2021-05-13 05:16:11.344973
Title: Customized Monte Carlo Tree Search for LLVM/Polly's Composable Loop Optimization Transformations
Title（参考訳）: LLVM/Pollyの合成可能なループ最適化のためのモンテカルロ木探索
Authors: Jaehoon Koo, Prasanna Balaprakash, Michael Kruse, Xingfu Wu, Paul Hovland, Mary Hall
Abstract要約: 我々は、ループ変換の最良の組み合わせを見つけるために、モンテカルロ木探索(MCTS)に基づく探索アルゴリズムを開発しました。実験の結果,我々のmctsアルゴリズムは,pollyの最適化よりも2.3倍の高速化でpragmaの組み合わせを見出した。
参考スコア（独自算出の注目度）: 0.8312466807725921
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Polly is the LLVM project's polyhedral loop nest optimizer. Recently, user-directed loop transformation pragmas were proposed based on LLVM/Clang and Polly. The search space exposed by the transformation pragmas is a tree, wherein each node represents a specific combination of loop transformations that can be applied to the code resulting from the parent node's loop transformations. We have developed a search algorithm based on Monte Carlo tree search (MCTS) to find the best combination of loop transformations. Our algorithm consists of two phases: exploring loop transformations at different depths of the tree to identify promising regions in the tree search space and exploiting those regions by performing a local search. Moreover, a restart mechanism is used to avoid the MCTS getting trapped in a local solution. The best and worst solutions are transferred from the previous phases of the restarts to leverage the search history. We compare our approach with random, greedy, and breadth-first search methods on PolyBench kernels and ECP proxy applications. Experimental results show that our MCTS algorithm finds pragma combinations with a speedup of 2.3x over Polly's heuristic optimizations on average.
Abstract（参考訳）: PollyはLLVMプロジェクトのpolyhedralループネストオプティマイザである。近年,LLVM/Clang と Polly に基づくユーザ指向のループ変換法が提案されている。変換プラグマによって露出される探索空間は木であり、各ノードは親ノードのループ変換から得られるコードに適用可能なループ変換の特定の組み合わせを表す。我々は,モンテカルロ木探索(MCTS)に基づく探索アルゴリズムを開発し,ループ変換の最適組み合わせを求める。本アルゴリズムは,木深度の異なるループ変換を探索し,木探索空間内の有望な領域を同定し,局所探索を行うことによりそれらの領域を利用する。さらに、MCTSが局所溶液に閉じ込められるのを避けるために再起動機構が使用される。最善のソリューションと最悪のソリューションは、検索履歴を活用するために再起動前のフェーズから転送される。提案手法を,PolyBenchカーネルおよびECPプロキシアプリケーション上でのランダム,強欲,広義の探索手法と比較した。実験の結果,mtsアルゴリズムは平均でポリーのヒューリスティック最適化よりも2.3倍の速度アップでpragmaの組み合わせを見出した。

関連論文リスト

LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
論文参考訳（メタデータ） (2024-06-29T05:14:04Z)
DeciLS-PBO: an Effective Local Search Method for Pseudo-Boolean Optimization [10.513103815142731]
PBO(Pseudo-Boolean Optimization)の解法における局所探索アルゴリズムの改良法について検討する。我々のアルゴリズムであるDeciLS-PBOは最先端のアルゴリズムと比較して有望な性能を持つ。
論文参考訳（メタデータ） (2023-01-28T17:03:56Z)
Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
興味のあるタスクを直接検索できる,スケーラブルで汎用的なフレームワークを初めて提示する。基礎となる数学表現の自然木構造に着想を得て、空間を超木に再配置する。我々は,モンテカルロ法を木探索に適用し,レジェクションサンプリングと等価形状検出を備える。
論文参考訳（メタデータ） (2022-09-27T17:51:31Z)
Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
Langevin Monte Carlo Thompson Sampling (LMC-TS) が提案されている。提案アルゴリズムは,文脈的帯域幅の特別な場合において,最高のトンプソンサンプリングアルゴリズムと同じサブ線形残差を達成できることを示す。
論文参考訳（メタデータ） (2022-06-22T17:58:23Z)
CITS: Coherent Ising Tree Search Algorithm Towards Solving Combinatorial Optimization Problems [0.0]
本稿では、マルコフ連鎖からSAに基づく奥行き制限木への探索空間の拡大による探索アルゴリズムを提案する。それぞれのイテレーションにおいて、このアルゴリズムは、先を見据えて、木に沿って探索することで、実現可能な探索空間内で最高の準最適解を選択する」。以上の結果から,IsingのNP最適化問題に対する高次木探索戦略は,より少ないエポックの範囲で解決可能であることが示唆された。
論文参考訳（メタデータ） (2022-03-09T10:07:26Z)
A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse [121.54116938140754]
両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
論文参考訳（メタデータ） (2021-12-09T02:27:52Z)
Multidimensional Assignment Problem for multipartite entity resolution [69.48568967931608]
Multipartiteエンティティ解決は、複数のデータセットから1つのエンティティにレコードを統合することを目的としている。代入問題を解くために、グリーディアルゴリズムと大規模近傍探索という2つの手順を適用する。データベースのサイズが大きくなるにつれて、設計ベースのマルチスタートがより効率的であることを示す。
論文参考訳（メタデータ） (2021-12-06T20:34:55Z)
Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。両レベル最適化のための2つの新しいアルゴリズムを提案する。両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文参考訳（メタデータ） (2021-06-08T21:05:30Z)
Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems [0.6882042556551609]
このアプローチでは,問題インスタンスの探索空間木を探索するアルゴリズムを用いる。このアルゴリズムはモンテカルロ木探索(Monte Carlo tree search)をベースとしている。
論文参考訳（メタデータ） (2020-10-22T08:33:58Z)
Evolutionary Algorithm and Multifactorial Evolutionary Algorithm on Clustered Shortest-Path Tree problem [2.578242050187029]
CluSPT(Clustered Shortest-Path Tree Problem)はNPハード問題である。探索処理の性能を向上させるために,2つの手法を提案する。
論文参考訳（メタデータ） (2020-10-19T08:37:18Z)
Autotuning Search Space for Loop Transformations [0.03683202928838612]
本稿では,木の形をとるループ変換探索空間を提案する。検索空間を探索する簡単なオートチューナーを実装し,選択したPolyBenchカーネルに適用した。
論文参考訳（メタデータ） (2020-10-13T16:26:57Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。