論文の概要: Efficient Parallelization of an Ubiquitous Sequential Computation
- arxiv url: http://arxiv.org/abs/2311.06281v2
- Date: Wed, 15 Nov 2023 14:53:19 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-16 19:11:28.756971
- Title: Efficient Parallelization of an Ubiquitous Sequential Computation
- Title(参考訳): ユビキタスシーケンシャル計算の効率的な並列化
- Authors: Franz A. Heinsen
- Abstract要約: x_t = a_t x_t-1 + b_t$ を並列に計算するための簡潔な式が見つかる。
n$並列プロセッサでは、$n$要素の計算は$mathcalO(log n)$ timeと$mathcalO(n)$ spaceを発生させる。
ソフトウェアで表現を実装し、並列ハードウェア上でテストし、$fracnlog n$の係数で逐次計算よりも高速に実行されることを検証します。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We find a succinct expression for computing the sequence $x_t = a_t x_{t-1} +
b_t$ in parallel with two prefix sums, given $t = (1, 2, \dots, n)$, $a_t \in
\mathbb{R}^n$, $b_t \in \mathbb{R}^n$, and initial value $x_0 \in \mathbb{R}$.
On $n$ parallel processors, the computation of $n$ elements incurs
$\mathcal{O}(\log n)$ time and $\mathcal{O}(n)$ space. Sequences of this form
are ubiquitous in science and engineering, making efficient parallelization
useful for a vast number of applications. We implement our expression in
software, test it on parallel hardware, and verify that it executes faster than
sequential computation by a factor of $\frac{n}{\log n}$.
- Abstract(参考訳): x_t = a_t x_{t-1} + b_t$ を2つのプレフィックス和と並行して計算するための簡潔な式を見つけ、$t = (1, 2, \dots, n)$, $a_t \in \mathbb{R}^n$, $b_t \in \mathbb{R}^n$, initial value $x_0 \in \mathbb{R}$とする。
n$並列プロセッサでは、$n$要素の計算は$\mathcal{O}(\log n)$ timeと$\mathcal{O}(n)$ spaceを発生させる。
この形式のシーケンスは科学や工学においてユビキタスであり、効率的な並列化は多数のアプリケーションに有用である。
ソフトウェアで式を実装し、並列ハードウェアでテストし、$\frac{n}{\log n}$という係数でシーケンシャルな計算よりも高速に実行されることを検証します。
関連論文リスト
- Multi-level projection with exponential parallel speedup; Application to sparse auto-encoders neural networks [2.264332709661011]
ell_1,infty$ノルムの時間複雑性は、$mathbbRntimes m$の行列に対して$mathcalObig(n m big)$のみであることを示す。
実験によると、我々の2レベル$ell_1,infty$プロジェクションは、実際の最速アルゴリズムよりも2.5ドル速い。
論文 参考訳(メタデータ) (2024-05-03T13:21:49Z) - Fast Attention Requires Bounded Entries [19.17278873525312]
内部製品注意計算はTransformer, GPT-1, BERT, GPT-2, GPT-3, ChatGPTなどの大規模言語モデルを訓練するための基本的なタスクである。
行列を暗黙的に$A$とすることで、より高速なアルゴリズムが可能かどうかを検討する。
このことは、入力行列がより小さいエントリを持つ場合、注意計算の方がはるかに効率的である、実際に観察された現象の理論的な説明を与える。
論文 参考訳(メタデータ) (2023-02-26T02:42:39Z) - Enlarging the notion of additivity of resource quantifiers [62.997667081978825]
量子状態 $varrho$ と量子化器 $cal E(varrho) が与えられたとき、$cal E(varrhootimes N)$ を決定するのは難しい。
本研究では, ある球対称状態の1発の蒸留可能な絡み合いを, このような拡張付加性によって定量的に近似できることを示す。
論文 参考訳(メタデータ) (2022-07-31T00:23:10Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳(メタデータ) (2022-06-17T17:55:43Z) - Low-degree learning and the metric entropy of polynomials [49.1574468325115]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳(メタデータ) (2022-03-17T23:52:08Z) - Quantum machine learning with subspace states [8.22379888383833]
量子部分空間状態に基づく量子線型代数の新しいアプローチを導入し,新しい3つの量子機械学習アルゴリズムを提案する。
1つ目は、分布 $Pr[S]= det(X_SX_ST)$ for $|S|=d$ using $O(nd)$ gates and with circuit depth $O(dlog n)$である。
2つ目は、複素行列に対して$mathcalAk$の量子特異値推定アルゴリズムであり、このアルゴリズムの高速化は指数関数的である。
論文 参考訳(メタデータ) (2022-01-31T19:34:47Z) - Computational Complexity of Normalizing Constants for the Product of
Determinantal Point Processes [12.640283469603357]
正規化定数の計算における計算複雑性について検討する。
例えば、$sum_Sdet(bf A_S,S)p$は、すべての(固定された)正の偶数に対して、$p$ が UP-hard で Mod$_3$P-hard であることを示す。
論文 参考訳(メタデータ) (2021-11-28T14:08:25Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳(メタデータ) (2020-08-24T06:50:57Z) - Continuous Submodular Maximization: Beyond DR-Submodularity [48.04323002262095]
最初に、バニラ座標の昇華の単純な変種を証明し、Coordinate-Ascent+ と呼ぶ。
次にCoordinate-Ascent++を提案し、同じ回数のイテレーションを実行しながら(1-1/e-varepsilon)$-approximationを保証する。
Coordinate-Ascent++の各ラウンドの計算は容易に並列化でき、マシン当たりの計算コストは$O(n/sqrtvarepsilon+nlog n)$である。
論文 参考訳(メタデータ) (2020-06-21T06:57:59Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳(メタデータ) (2020-06-12T10:21:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。