論文の概要: Learning While Scheduling in Multi-Server Systems with Unknown
Statistics: MaxWeight with Discounted UCB
- arxiv url: http://arxiv.org/abs/2209.01126v3
- Date: Fri, 2 Jun 2023 06:57:06 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-05 20:57:39.923574
- Title: Learning While Scheduling in Multi-Server Systems with Unknown
Statistics: MaxWeight with Discounted UCB
- Title（参考訳）: 未知の統計量を持つマルチサーバシステムにおけるスケジューリング中の学習: Uncounted UCBを用いたマックスウェイト
- Authors: Zixian Yang, R. Srikant, Lei Ying
- Abstract要約: 本稿では、複数のサーバと複数のタイプのジョブを持つマルチサーバシステムについて考察する。
目標は、処理時間の統計を知ることなく、サーバ上のジョブをスケジュールすることだ。
我々は,MaxWeightスケジューリングポリシと割引された高信頼度境界(UCB)を組み合わせることで,統計を同時に学習し,ジョブをサーバにスケジュールするアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 18.898514227870926
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Multi-server queueing systems are widely used models for job scheduling in
machine learning, wireless networks, crowdsourcing, and healthcare systems.
This paper considers a multi-server system with multiple servers and multiple
types of jobs, where different job types require different amounts of
processing time at different servers. The goal is to schedule jobs on servers
without knowing the statistics of the processing times. To fully utilize the
processing power of the servers, it is known that one has to at least learn the
service rates of different job types on different servers. Prior works on this
topic decouple the learning and scheduling phases which leads to either
excessive exploration or extremely large job delays. We propose a new
algorithm, which combines the MaxWeight scheduling policy with discounted upper
confidence bound (UCB), to simultaneously learn the statistics and schedule
jobs to servers. We prove that under our algorithm the asymptotic average queue
length is bounded by one divided by the traffic slackness, which is order-wise
optimal. We also obtain an exponentially decaying probability tail bound for
any-time queue length. These results hold for both stationary and nonstationary
service rates. Simulations confirm that the delay performance of our algorithm
is several orders of magnitude better than previously proposed algorithms.
- Abstract（参考訳）: マルチサーバキューシステムは、機械学習、無線ネットワーク、クラウドソーシング、医療システムにおけるジョブスケジューリングのモデルとして広く使われている。
本稿では、複数のサーバと複数のタイプのジョブを持つマルチサーバシステムについて考察する。
目標は、処理時間の統計を知らずにサーバでジョブをスケジュールすることである。
サーバの処理能力を十分に活用するには、異なるサーバ上で異なるジョブタイプのサービスレートを少なくとも学ばなければならないことが知られている。
このトピックに関する先行研究は、過剰な探索や極めて大きな作業遅延につながる学習とスケジューリングのフェーズを分離する。
そこで我々は,MaxWeightスケジューリングポリシーと割引された高信頼度境界(UCB)を併用した新しいアルゴリズムを提案し,その統計を同時に学習し,ジョブをサーバにスケジュールする。
我々のアルゴリズムでは、漸近平均キュー長はトラフィックのスラックネスによって分割され、順序的に最適であることが証明されている。
また、任意の時間待ち行列長に対して指数関数的に減衰する確率テールを得る。
これらの結果は定常サービスと非定常サービスの両方に当てはまる。
シミュレーションにより,提案アルゴリズムよりもアルゴリズムの遅延性能が桁違いに優れていることを確認した。
関連論文リスト
- Is the GPU Half-Empty or Half-Full? Practical Scheduling Techniques for LLMs [3.7758841366694353]
文献および実用サービスシステムからスケジューリング手法を調査する。
文献からのスケジューラは、しばしば優れたパフォーマンスを得るが、かなりの複雑さをもたらす。
対照的に、実際のデプロイメントにおけるスケジューラは、しばしばテーブルに簡単にパフォーマンス向上を残しますが、実装、デプロイ、設定が容易です。
論文 参考訳（メタデータ） (2024-10-23T13:05:46Z) - Queueing Matching Bandits with Preference Feedback [10.988222071035198]
我々は、一方のN$キューと他方のK$サーバからなるマルチクラス非対称キューシステムについて検討する。
各ジョブサーバ割り当てのサービスレートは未知であり、機能ベースのMNL(Multi-nomial Logit)関数によってモデル化される。
我々は,UCBとトンプソンサンプリングに基づくアルゴリズムを提案する。このアルゴリズムは,待ち時間の平均値が$O(minN,K/epsilon)$に制限されたシステム安定性を実現する。
論文 参考訳（メタデータ） (2024-10-14T02:29:06Z) - Efficient Reinforcement Learning for Routing Jobs in Heterogeneous Queueing Systems [21.944723061337267]
我々は、中央キューに到着するジョブをヘテロジニアスサーバのシステムに効率的にルーティングする問題を考察する。
均質なシステムとは異なり、キュー長が一定のしきい値を超えた場合、ジョブを遅いサーバにルーティングするしきい値ポリシーは、ワンファストワンスローの2サーバシステムに最適であることが知られている。
本稿では,低次元ソフトしきい値パラメータ化を用いた効率的なポリシー勾配に基づくアルゴリズムであるACHQを提案する。
論文 参考訳（メタデータ） (2024-02-02T05:22:41Z) - Online Optimization for Network Resource Allocation and Comparison with
Reinforcement Learning Techniques [0.6466206145151128]
本稿では、ジョブ転送におけるオンラインネットワークリソース割り当て問題に取り組む。
本稿では指数重み付け手法に基づくランダム化オンラインアルゴリズムを提案する。
提案アルゴリズムは,その経験からアルゴリズムが適応し,学習していることを示す。
論文 参考訳（メタデータ） (2023-11-16T17:08:27Z) - Partitioning Distributed Compute Jobs with Reinforcement Learning and
Graph Neural Networks [58.720142291102135]
大規模な機械学習モデルは、幅広い分野に進歩をもたらしている。
これらのモデルの多くは、単一のマシンでトレーニングするには大きすぎるため、複数のデバイスに分散する必要がある。
スループットやブロッキングレートといったユーザクリティカルな指標に対して,並列化の最大化が準最適であることを示す。
論文 参考訳（メタデータ） (2023-01-31T17:41:07Z) - Multi-Job Intelligent Scheduling with Cross-Device Federated Learning [65.69079337653994]
フェデレートラーニング(FL)は、センシティブな生データを共有せずに、協調的なグローバル機械学習モデルのトレーニングを可能にする。
本稿では,複数のジョブを並列にトレーニングできる新しいマルチジョブFLフレームワークを提案する。
本稿では,元来の強化学習に基づくスケジューリング手法と元来のベイズ最適化に基づくスケジューリング手法を含む,複数のスケジューリング手法に基づく新しいインテリジェントスケジューリング手法を提案する。
論文 参考訳（メタデータ） (2022-11-24T06:17:40Z) - Efficient Device Scheduling with Multi-Job Federated Learning [64.21733164243781]
本稿では,複数のジョブの並列学習プロセスを実現するための,新しいマルチジョブフェデレーション学習フレームワークを提案する。
コストを最小化しつつ、複数のジョブに対してデバイスをスケジュールする強化学習法とベイズ最適化法を提案する。
提案手法は,トレーニング時間(最大8.67倍高速)と精度(最大44.6%高)において,ベースラインアプローチよりも有意に優れていた。
論文 参考訳（メタデータ） (2021-12-11T08:05:11Z) - Better than the Best: Gradient-based Improper Reinforcement Learning for
Network Scheduling [60.48359567964899]
パケット遅延を最小限に抑えるため,制約付き待ち行列ネットワークにおけるスケジューリングの問題を考える。
我々は、利用可能な原子ポリシーよりも優れたスケジューラを生成するポリシー勾配に基づく強化学習アルゴリズムを使用する。
論文 参考訳（メタデータ） (2021-05-01T10:18:34Z) - Rosella: A Self-Driving Distributed Scheduler for Heterogeneous Clusters [7.206919625027208]
異種クラスタにおけるタスクスケジューリングのための,新たな自律分散アプローチであるRosellaを紹介する。
Rosellaは自動的に計算環境を学習し、スケジューリングポリシーをリアルタイムで調整する。
32ノードのAWSクラスタ上で、さまざまなワークロードでRosellaを評価します。
論文 参考訳（メタデータ） (2020-10-28T20:12:29Z) - Temporally Correlated Task Scheduling for Sequence Learning [143.70523777803723]
多くのアプリケーションにおいて、シーケンス学習タスクは通常、複数の時間的に相関した補助タスクと関連付けられている。
シーケンス学習に学習可能なスケジューラを導入し、トレーニングのための補助的なタスクを適応的に選択できる。
本手法は,同時翻訳とストックトレンド予測の性能を著しく向上させる。
論文 参考訳（メタデータ） (2020-07-10T10:28:54Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳（メタデータ） (2020-05-27T01:10:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。