論文の概要: Coded Computation across Shared Heterogeneous Workers with Communication Delay

• arxiv url: http://arxiv.org/abs/2109.11246v1
• Date: Thu, 23 Sep 2021 09:40:54 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-24 14:46:07.990179
• Title: Coded Computation across Shared Heterogeneous Workers with Communication Delay
• Title（参考訳）: 通信遅延を考慮した共有異種労働者の符号化計算
• Authors: Yuxuan Sun, Fan Zhang, Junlin Zhao, Sheng Zhou, Zhisheng Niu, Deniz G\"und\"uz
• Abstract要約: 複数の行列乗算タスクを符号化し、並列計算のためにワーカーに割り当てるマルチワーカー分散コンピューティングのシナリオを考察する。 本稿では、各作業者が符号化されたタスクを処理可能な、専用および分数的な作業者割当ポリシーの下で、作業者割当、リソース割当負荷割当アルゴリズムを提案する。 提案アルゴリズムは,ベンチマークよりもタスク遅延の完了率を低減できることを示すとともに,専用および少数のワーカ割り当てポリシがアプリケーションのスコープが異なることを観察する。
• 参考スコア（独自算出の注目度）: 42.50248255900814
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Distributed computing enables large-scale computation tasks to be processed over multiple workers in parallel. However, the randomness of communication and computation delays across workers causes the straggler effect, which may degrade the performance. Coded computation helps to mitigate the straggler effect, but the amount of redundant load and their assignment to the workers should be carefully optimized. In this work, we consider a multi-master heterogeneous-worker distributed computing scenario, where multiple matrix multiplication tasks are encoded and allocated to workers for parallel computation. The goal is to minimize the communication plus computation delay of the slowest task. We propose worker assignment, resource allocation and load allocation algorithms under both dedicated and fractional worker assignment policies, where each worker can process the encoded tasks of either a single master or multiple masters, respectively. Then, the non-convex delay minimization problem is solved by employing the Markov's inequality-based approximation, Karush-Kuhn-Tucker conditions, and successive convex approximation methods. Through extensive simulations, we show that the proposed algorithms can reduce the task completion delay compared to the benchmarks, and observe that dedicated and fractional worker assignment policies have different scopes of applications.
• Abstract（参考訳）: 分散コンピューティングにより、大規模計算タスクを複数のワーカ上で並列に処理できる。 しかし、作業者間の通信のランダム性と計算遅延がストラグラー効果を引き起こし、性能が低下する可能性がある。 コード化された計算はストラグラー効果を軽減するのに役立つが、冗長な負荷の量とワーカーへの割り当ては慎重に最適化されるべきである。 本研究では,並列計算のために複数の行列乗算タスクを符号化し,ワーカーに割り当てるマルチマスターヘテロジニアス・ワーカー分散コンピューティングシナリオを検討する。 目標は、最も遅いタスクの通信と計算遅延を最小化することです。 本稿では、各ワーカーが1つのマスタまたは複数のマスタのエンコードされたタスクをそれぞれ処理できる、専用および分数的なワーカー割当ポリシーの下で、ワーカー割当、リソース割当およびロード割当アルゴリズムを提案する。 そして、マルコフの不等式に基づく近似、カルーシュ・クーン・タッカー条件、および連続凸近似を用いて非凸遅延最小化問題を解く。 シミュレーションにより,提案アルゴリズムはベンチマークよりもタスク完了遅延を低減できることを示すとともに,専用および分数的なワーカー割り当てポリシーがアプリケーションのスコープが異なることを観察する。

関連論文リスト

• ACCO: Accumulate while you Communicate, Hiding Communications in Distributed LLM Training [16.560270624096706]
  大規模言語モデルの分散学習に適したメモリ効率最適化アルゴリズムを提案する。 本手法は、勾配計算と通信の並列実行に固有の1ステップ遅れを軽減する新しい手法に依存する。
  論文  参考訳（メタデータ） (2024-06-03T08:23:45Z)
• Fast and Straggler-Tolerant Distributed SGD with Reduced Computation Load [11.069252535469644]
  勾配降下(SGD)のような最適化手順は、ストラグラーと呼ばれる非応答性や遅い労働者の影響を軽減するために利用することができる。 これは、ワーカのサブセットがアルゴリズムの各イテレーションで計算を完了するのを待つだけで実現できる。 我々は,アルゴリズムの実行時間を通じて,作業者数と計算負荷の両方を適応させる新しいスキームを構築した。
  論文  参考訳（メタデータ） (2023-04-17T20:12:18Z)
• 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)
• Efficient Distributed Machine Learning via Combinatorial Multi-Armed Bandits [23.289979018463406]
  我々は、主ノードが$n$ワーカー間で勾配計算を分散する分散勾配降下問題を考え、そこから少なくとも$b leq n$を並列に利用することができる。 すべてのワーカーにタスクを割り当て、$k$の高速なものだけを待つことで、メインノードはアルゴリズムが進化するにつれて徐々に$k$を増大させることで、アルゴリズムのエラーをランタイムとトレードオフすることができる。 この戦略はアダプティブkシンクと呼ばれ、遅い作業者の計算作業を無視するため、追加のコストを発生させることができる。 タスクを$k$にのみ割り当てるコスト効率の高いスキームを提案する。
  論文  参考訳（メタデータ） (2022-02-16T19:18:19Z)
• A Machine Learning Approach for Task and Resource Allocation in Mobile Edge Computing Based Networks [108.57859531628264]
  無線ネットワークにおいて,共同作業,スペクトル,送信電力配分問題について検討する。 提案アルゴリズムは、標準Q-ラーニングアルゴリズムと比較して、収束に必要なイテレーション数と全ユーザの最大遅延を最大18%、11.1%削減することができる。
  論文  参考訳（メタデータ） (2020-07-20T13:46:42Z)
• Coded Distributed Computing with Partial Recovery [56.08535873173518]
  部分回復型符号化計算(CCPR)と呼ばれる新しい符号化行列ベクトル乗法を導入する。 CCPRは計算時間と復号化の複雑さを減らし、精度と計算速度のトレードオフを可能にする。 次に、この手法をより一般的な計算タスクの分散実装に拡張し、部分的回復を伴う符号化通信方式を提案する。
  論文  参考訳（メタデータ） (2020-07-04T21:34:49Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。 都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
  論文  参考訳（メタデータ） (2020-05-27T01:10:41Z)
• Straggler-aware Distributed Learning: Communication Computation Latency Trade-off [56.08535873173518]
  ストラグワーカーは冗長な計算を割り当て、データと計算をまたいでコーディングすることで許容できる。 既存のほとんどのスキームでは、各非ストラグリングワーカーは、全ての計算を完了した後、1イテレーションごとに1つのメッセージをパラメータサーバ(PS)に送信する。 このような制限を課すことで、ストレグリング動作の不正確な予測による過剰計算と、ストレグラー/非ストレグラーとしての作業員の処理による未使用の2つの主な欠点が生じる。
  論文  参考訳（メタデータ） (2020-04-10T08:39:36Z)

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

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