Fugu-MT 論文翻訳(概要): A New Parallel Algorithm for Sinkhorn Word-Movers Distance and Its Performance on PIUMA and Xeon CPU

論文の概要: A New Parallel Algorithm for Sinkhorn Word-Movers Distance and Its Performance on PIUMA and Xeon CPU

arxiv url: http://arxiv.org/abs/2107.06433v1
Date: Wed, 14 Jul 2021 00:29:18 GMT
ステータス: 処理完了
システム内更新日: 2021-07-15 14:07:32.947186
Title: A New Parallel Algorithm for Sinkhorn Word-Movers Distance and Its Performance on PIUMA and Xeon CPU
Title（参考訳）: シンクホーン単語移動距離の新しい並列アルゴリズムとそのPiumAおよびXeon CPU上での性能
Authors: Jesmin Jahan Tithi and Fabrizio Petrini
Abstract要約: Word Movers Distance (WMD)は、2つの文書間の意味的相違を測定する。我々は、他の多くの文書に対して1つの文書のWMDを計算するために、共有メモリ並列Sinkhorn-Knoppアルゴリズムを提案する。並列実装は、Intel Cascade Lakeシステムの4つのNUMAソケットにまたがる96コアでの67倍の高速化を実現している。
参考スコア（独自算出の注目度）: 0.3655021726150367
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The Word Movers Distance (WMD) measures the semantic dissimilarity between two text documents by computing the cost of optimally moving all words of a source/query document to the most similar words of a target document. Computing WMD between two documents is costly because it requires solving an optimization problem that costs $O (V^3 \log(V)) $ where $V$ is the number of unique words in the document. Fortunately, WMD can be framed as an Earth Mover's Distance (EMD) for which the algorithmic complexity can be reduced to $O(V^2)$ by adding an entropy penalty to the optimization problem and solving it using the Sinkhorn-Knopp algorithm. Additionally, the computation can be made highly parallel by computing the WMD of a single query document against multiple target documents at once, for example by finding whether a given tweet is similar to any other tweets of a given day. In this paper, we first present a shared-memory parallel Sinkhorn-Knopp algorithm to compute the WMD of one document against many other documents by adopting the $ O(V^2)$ EMD algorithm. We then algorithmically transform the original $O(V^2)$ dense compute-heavy version into an equivalent sparse one which is mapped onto the new Intel Programmable Integrated Unified Memory Architecture (PIUMA) system. The WMD parallel implementation achieves 67x speedup on 96 cores across 4 NUMA sockets of an Intel Cascade Lake system. We also show that PIUMA cores are around 1.2-2.6x faster than Xeon cores on Sinkhorn-WMD and also provide better strong scaling.
Abstract（参考訳）: Word Movers Distance (WMD)は、ソース/クエリ文書の全ての単語をターゲット文書の最も類似した単語に最適に移動させるコストを計算することによって、2つの文書間の意味的相違を測定する。 2つのドキュメント間のwmdの計算にはコストがかかる。それは、ドキュメント内のユニークな単語の数が$v$である場合、$o (v^3 \log(v)) $の最適化問題を解決する必要があるからだ。幸いなことに、wmd はアルゴリズムの複雑さを最適化問題にエントロピーペナルティを追加し、spinhorn-knoppアルゴリズムを用いて解くことで $o(v^2)$ に還元できる earth mover's distance (emd) として構成することができる。さらに、ひとつのクエリドキュメントのWMDを複数のターゲットドキュメントに対して一度に計算することで、例えば、あるツイートがある日の他のつぶやきと似ているかどうかを調べることで、計算を非常に並列にすることができる。本稿では、まず共有メモリ並列Sinkhorn-Knoppアルゴリズムを提案し、$O(V^2)$ EMDアルゴリズムを用いて、1つの文書のWMDを他の多くの文書に対して計算する。次に,元の$O(V^2)$高密度計算重度バージョンを,新しいIntel Programmable Integrated Unified Memory Architecture (PiumA)システムにマッピングした等価スパース版に変換する。 WMD並列実装は、Intel Cascade Lakeシステムの4つのNUMAソケットにまたがる96コアでの67倍の高速化を実現している。また、PiumAコアはシンクホーンWMDのXeonコアよりも1.2-2.6倍高速であり、より強力なスケーリングを提供することを示した。

関連論文リスト

Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls [83.89771461061903]
検証者による木探索アルゴリズムの最近の進歩は、大規模言語モデル(LLM)の推論能力を大幅に向上させた。検証者による木探索アルゴリズムの最近の進歩は、大規模言語モデル(LLM)の推論能力を大幅に向上させた。意味論的に等価なコンテンツを持つ冗長な状態による$textitover-Exploration$と、検証器のスコアリングにおける高いばらつきに起因する$textitunder-Exploration$である。各種木探索アルゴリズムに適合するフレキシブルなプラグアンドプレイシステムであるFETCHを提案する。
論文参考訳（メタデータ） (2025-02-16T16:12:01Z)
Hardware-Aware Parallel Prompt Decoding for Memory-Efficient Acceleration of LLM Inference [19.167604927651073]
LLM(Large Language Models)の自動回帰デコーディングは、ハードウェアの性能に大きなオーバーヘッドをもたらす。トレーニング可能なパラメータを0.0002$%しか必要とせず,A100-40GBのGPUをたった16時間で効率的にトレーニングできる並列プロンプトデコーディングを提案する。我々のアプローチでは、最大2.49$times$ スピードアップを示し、最小のメモリオーバーヘッドは0.0004$%である。
論文参考訳（メタデータ） (2024-05-28T22:19:30Z)
Linear-time Minimum Bayes Risk Decoding with Reference Aggregation [52.1701152610258]
最小ベイズリスク(MBR、Minimum Bayes Risk)は、機械翻訳の品質向上を図ったテキスト生成技術である。これは2次複雑性を持つ実用計量のペアワイズ計算を必要とする。本稿では,集約された参照表現に対して計算したスコアを用いて,ペアワイズメトリックスコアを近似する。
論文参考訳（メタデータ） (2024-02-06T18:59:30Z)
Generative Sliced MMD Flows with Riesz Kernels [0.393259574660092]
最大平均誤差(MMD)フローは大規模計算において高い計算コストを被る。 Riesz カーネルの MMD フローが $K(x,y) = - |x-y|r$, $r in (0,2)$ であることを示す。
論文参考訳（メタデータ） (2023-05-19T06:33:57Z)
Scalable Quantum Error Correction for Surface Codes using FPGA [67.74017895815125]
フォールトトレラントな量子コンピュータは、出現するよりも早くデコードし、エラーを修正する必要がある。並列計算資源を利用したUnion-Findデコーダの分散バージョンを報告する。この実装では、並列コンピューティングリソースをハイブリッドツリーグリッド構造に整理する、Heliosと呼ばれるスケーラブルなアーキテクチャを採用している。
論文参考訳（メタデータ） (2023-01-20T04:23:00Z)
Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文参考訳（メタデータ） (2022-10-14T01:42:05Z)
Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
Person Re-Identification (ReID) は、歩行者を分離したカメラで識別する。実値特徴記述子を用いた既存のReID法は精度が高いが、ユークリッド距離計算が遅いため効率が低い。本稿では,ReID 処理を 0.25 倍高速化するサブスペース一貫性規則化 (SCR) アルゴリズムを提案する。
論文参考訳（メタデータ） (2022-07-13T02:44:05Z)
A Push-Relabel Based Additive Approximation for Optimal Transport [5.111364864495785]
最適な輸送を計算するための厳密なアルゴリズムは遅くなる。我々は、OT距離の$varepsilon$approximationを求めるための、新しい非常に単純なアプローチを導入する。我々のアルゴリズムは、OT距離を計算するために、O(n2/varepsilon2)$のほぼ最適実行時間を達成する。
論文参考訳（メタデータ） (2022-03-07T21:40:14Z)
Compressing 1D Time-Channel Separable Convolutions using Sparse Random Ternary Matrices [65.4388266814055]
1次元時間チャネル分離可能な畳み込みの1x1-畳み込みを、定数でスパースな乱数三元行列で-1,0,+1$の重みで置き換える。 Google Speech Commands v1のコマンド認識のために、最新の精度を同じネットワークサイズで97.21%$から97.41%$に改善します。 librispeech上での音声認識では、トレーニングすべき重みの数は半分になり、浮動小数点ベースラインの単語誤り率の約1%を犠牲にします。
論文参考訳（メタデータ） (2021-03-31T15:09:20Z)
Exact, Parallelizable Dynamic Time Warping Alignment with Linear Memory [0.0]
我々は,O(M+N)メモリを用いて,正確な大域的最適DTWアライメントを計算する分割・征服アルゴリズムを提案する。我々のアルゴリズムは、同じメモリ制約でmin(M, N)の係数まで並列化できるので、十分なGPUで教科書版よりも効率的に実行できる。
論文参考訳（メタデータ） (2020-08-04T15:00:33Z)
An Efficient Shared-memory Parallel Sinkhorn-Knopp Algorithm to Compute the Word Mover's Distance [0.18275108630751835]
Word Mover's Distance (WMD) は、2つの文書間の意味的相違を測定するメトリクスである。我々は、他の多くの文書に対して、ある文書のWMDを計算するための共有メモリ並列アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-05-14T05:30:18Z)

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

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