論文の概要: 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) - Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。
プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。
各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
論文 参考訳（メタデータ） (2023-06-07T14:07:35Z) - Efficient distributed representations with linear-time attention scores normalization [3.8673630752805437]
本研究では,有界ノルムを持つ埋め込みベクトルに対するアテンションスコア正規化定数の線形時間近似を提案する。
推定公式の精度は、競合するカーネルメソッドを桁違いに上回る。
提案アルゴリズムは高度に解釈可能であり,任意の埋め込み問題に容易に適応できる。
論文 参考訳（メタデータ） (2023-03-30T15:48:26Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。