論文の概要: MaxWeight With Discounted UCB: A Provably Stable Scheduling Policy for
Nonstationary Multi-Server Systems With Unknown Statistics
- arxiv url: http://arxiv.org/abs/2209.01126v1
- Date: Fri, 2 Sep 2022 15:37:02 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-05 13:02:42.260735
- Title: MaxWeight With Discounted UCB: A Provably Stable Scheduling Policy for
Nonstationary Multi-Server Systems With Unknown Statistics
- Title（参考訳）: MaxWeight with Discounted UCB: 未知統計を持つ非定常マルチサーバシステムのための安定的なスケジューリングポリシー
- Authors: Zixian Yang, R. Srikant, Lei Ying
- Abstract要約: 本稿では,複数のサーバと複数のジョブを備えたマルチサーバシステムについて考察する。
各タイムスロットでは、利用可能なサーバがキューからジョブを選択し、完了するまでそのジョブをサービスする。
そこで我々は,サーバにジョブをスケジュールする統計処理を同時に学習する,割引高信頼境界(UCB)アルゴリズムのMaxWeightを提案する。
- 参考スコア（独自算出の注目度）: 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, and crowdsourcing. This paper considers a
multi-server system with multiple servers and multiple types of jobs. The
system maintains a separate queue for each type of jobs. For each time slot,
each available server picks a job from a queue and then serves the job until it
is complete. The arrival rates of the queues and the mean service times are
unknown and even nonstationary. We propose the MaxWeight with discounted upper
confidence bound (UCB) algorithm, which simultaneously learns the statistics
and schedules jobs to servers. We prove that the proposed algorithm can
stabilize the queues when the arrival rates are strictly within the service
capacity region. Specifically, we prove that the queue lengths are bounded in
the mean under the assumption that the mean service times change relatively
slowly over time and the arrival rates are bounded away from the capacity
region by a constant whose value depends on the discount factor used in the
discounted UCB. Simulation results confirm that the proposed algorithm can
stabilize the queues and that it outperforms MaxWeight with empirical mean and
MaxWeight with discounted empirical mean. The proposed algorithm is also better
than MaxWeight with UCB in the nonstationary setting.
- Abstract（参考訳）: マルチサーバキューシステムは、機械学習、無線ネットワーク、クラウドソーシングにおけるジョブスケジューリングのモデルとして広く使われている。
本稿では,複数のサーバと複数のジョブを持つマルチサーバシステムについて考察する。
システムは、ジョブの種類ごとに別々のキューを保持する。
各タイムスロットでは、利用可能な各サーバがキューからジョブを選択し、それが完了するまでジョブを提供する。
待ち行列の到着率と平均サービス時間は未知であり、静止していない。
そこで我々は,サーバにジョブをスケジュールする統計処理を同時に学習する,割引高信頼境界(UCB)アルゴリズムのMaxWeightを提案する。
提案アルゴリズムは,到着率が厳密にサービス容量領域内にある場合の待ち行列を安定化できることを示す。
具体的には、平均サービス時間が時間とともに相対的に変化し、割引されたUCBで使用される割引係数に依存する定数で到着率がキャパシティ領域から切り離されるという仮定のもと、待ち行列の長さが平均で境界づけられていることを証明する。
シミュレーションの結果,提案アルゴリズムはキューを安定化し,MaxWeightを実証平均で上回り,MaxWeightを実証平均で上回ることを確認した。
提案アルゴリズムは,非定常条件下での UCB による MaxWeight よりも優れている。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。