論文の概要: Parallel Scheduling Self-attention Mechanism: Generalization and
Optimization
- arxiv url: http://arxiv.org/abs/2012.01114v1
- Date: Wed, 2 Dec 2020 12:04:16 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-25 03:45:46.967506
- Title: Parallel Scheduling Self-attention Mechanism: Generalization and
Optimization
- Title(参考訳): 並列スケジューリング自己注意機構:一般化と最適化
- Authors: Mingfei Yu and Masahiro Fujita
- Abstract要約: 本稿では,SAT(Satisfiability check)ソルバによって解決された小インスタンスの最適スケジューリングから導いた一般スケジューリングアルゴリズムを提案する。
余剰計算をスキップする際のさらなる最適化戦略も推進され、元の計算の約25%と50%の削減が達成される。
提案アルゴリズムは、入力ベクトルの数がアーキテクチャで利用可能な演算ユニットの数に割り切れる限り、問題のサイズにかかわらず適用可能である。
- 参考スコア(独自算出の注目度): 0.76146285961466
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Over the past few years, self-attention is shining in the field of deep
learning, especially in the domain of natural language processing(NLP). Its
impressive effectiveness, along with ubiquitous implementations, have aroused
our interest in efficiently scheduling the data-flow of corresponding
computations onto architectures with many computing units to realize parallel
computing. In this paper, based on the theory of self-attention mechanism and
state-of-the-art realization of self-attention in language models, we propose a
general scheduling algorithm, which is derived from the optimum scheduling for
small instances solved by a satisfiability checking(SAT) solver, to parallelize
typical computations of self-attention. Strategies for further optimization on
skipping redundant computations are put forward as well, with which reductions
of almost 25% and 50% of the original computations are respectively achieved
for two widely-adopted application schemes of self-attention. With the proposed
optimization adopted, we have correspondingly come up with another two
scheduling algorithms. The proposed algorithms are applicable regardless of
problem sizes, as long as the number of input vectors is divisible to the
number of computing units available in the architecture. Due to the complexity
of proving the correctness of the algorithms mathematically for general cases,
we have conducted experiments to reveal their validity, together with the
superior quality of the solutions provided by which, by solving SAT problems
for particular instances.
- Abstract(参考訳): 過去数年間、特に自然言語処理(NLP)の分野において、ディープラーニングの分野で自己注意が輝いている。
その顕著な効果は、ユビキタスな実装とともに、並列コンピューティングを実現するために、多くの計算ユニットを持つアーキテクチャに対応する計算データフローを効率的にスケジューリングすることへの我々の関心を喚起した。
本稿では,言語モデルにおける自己アテンション機構の理論と自己アテンションの最先端化を基礎として,SAT(Satisfiability check)ソルバによって解決された小インスタンスの最適スケジューリングから導かれる一般スケジューリングアルゴリズムを提案し,自己アテンションの典型的な計算を並列化する。
冗長計算をスキップするさらなる最適化戦略も提案され、それぞれ25%と50%の削減が、広く採用されている2つのセルフアテンションのアプリケーションスキームで達成される。
提案手法を採用することで,スケジューリングアルゴリズムを新たに2つ考案した。
提案アルゴリズムは、入力ベクトルの数がアーキテクチャで利用可能な演算ユニットの数に割り切れる限り、問題のサイズにかかわらず適用可能である。
一般の場合,アルゴリズムの正しさを数学的に証明することの難しさから,特定の事例に対するSAT問題の解法によって得られる解の優れた品質とともに,それらの妥当性を明らかにする実験を行った。
関連論文リスト
- AxOMaP: Designing FPGA-based Approximate Arithmetic Operators using
Mathematical Programming [2.898055875927704]
FPGAの近似演算子を合成するための,データ解析による数学的プログラミングに基づく手法を提案する。
具体的には、特徴量データの相関解析の結果に基づいて、混合整数の2次制約付きプログラムを定式化する。
従来の進化的アルゴリズムによる最適化と比較して,PPAとBEHAVの併用最適化において,ハイパーボリュームの最大21%の改善が報告されている。
論文 参考訳(メタデータ) (2023-09-23T18:23:54Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳(メタデータ) (2023-07-17T20:11:56Z) - Efficient Convex Algorithms for Universal Kernel Learning [50.877957471649395]
カーネルの理想的な集合: 線形パラメータ化(トラクタビリティ)を認める; すべてのカーネルの集合に密着する(正確性)。
従来のカーネル最適化アルゴリズムは分類に限られており、計算に複雑なセミデフィニティプログラミング(SDP)アルゴリズムに依存していた。
本稿では,従来のSDP手法と比較して計算量を大幅に削減するSVD-QCQPQPアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-04-15T04:57:37Z) - An Efficient Merge Search Matheuristic for Maximising the Net Present
Value of Project Schedules [5.10800491975164]
リソース制約のあるプロジェクトスケジューリングは多くの実用的なアプリケーションにおいて重要な最適化問題である。
本稿では,資源制約のあるプロジェクトスケジューリングを解くために,マージ探索と並列計算に基づく新しい数学ヒューリスティックアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-10-20T13:30:23Z) - A Two-stage Framework and Reinforcement Learning-based Optimization
Algorithms for Complex Scheduling Problems [54.61091936472494]
本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。
スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。
その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
論文 参考訳(メタデータ) (2021-03-10T03:16:12Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z) - Geometric Deep Reinforcement Learning for Dynamic DAG Scheduling [8.14784681248878]
本稿では,現実的なスケジューリング問題を解決するための強化学習手法を提案する。
高性能コンピューティングコミュニティにおいて一般的に実行されるアルゴリズムであるColesky Factorizationに適用する。
我々のアルゴリズムは,アクター・クリティカル・アルゴリズム (A2C) と組み合わせてグラフニューラルネットワークを用いて,問題の適応表現をオンザフライで構築する。
論文 参考訳(メタデータ) (2020-11-09T10:57:21Z) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳(メタデータ) (2020-08-29T14:58:26Z) - Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding
Design for Multiuser MIMO Systems [59.804810122136345]
本稿では,AIIDNN(ディープ・アンフォールディング・ニューラルネット)を一般化した,ディープ・アンフォールディングのためのフレームワークを提案する。
古典的重み付き最小二乗誤差(WMMSE)反復アルゴリズムの構造に基づく効率的なIAIDNNを提案する。
提案したIAIDNNは,計算複雑性を低減した反復WMMSEアルゴリズムの性能を効率よく向上することを示す。
論文 参考訳(メタデータ) (2020-06-15T02:57:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。