論文の概要: Learning to Schedule DAG Tasks

• arxiv url: http://arxiv.org/abs/2103.03412v1
• Date: Fri, 5 Mar 2021 01:10:24 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-09 06:38:21.214100
• Title: Learning to Schedule DAG Tasks
• Title（参考訳）: DAGタスクのスケジュールの学習
• Authors: Zhigang Hua, Feng Qi, Gan Liu and Shuang Yang
• Abstract要約: 有向非周期グラフ(DAG)のスケジューリングに関する新しい学習手法を提案する。 このアルゴリズムは強化学習エージェントを用いて、DAGに向けられたエッジを反復的に追加する。 我々の手法は既存のスケジューリングアルゴリズムにも容易に適用できる。
• 参考スコア（独自算出の注目度）: 7.577417675452624
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Scheduling computational tasks represented by directed acyclic graphs (DAGs) is challenging because of its complexity. Conventional scheduling algorithms rely heavily on simple heuristics such as shortest job first (SJF) and critical path (CP), and are often lacking in scheduling quality. In this paper, we present a novel learning-based approach to scheduling DAG tasks. The algorithm employs a reinforcement learning agent to iteratively add directed edges to the DAG, one at a time, to enforce ordering (i.e., priorities of execution and resource allocation) of "tricky" job nodes. By doing so, the original DAG scheduling problem is dramatically reduced to a much simpler proxy problem, on which heuristic scheduling algorithms such as SJF and CP can be efficiently improved. Our approach can be easily applied to any existing heuristic scheduling algorithms. On the benchmark dataset of TPC-H, we show that our learning based approach can significantly improve over popular heuristic algorithms and consistently achieves the best performance among several methods under a variety of settings.
• Abstract（参考訳）: 有向非巡回グラフ(DAG)で表される計算タスクのスケジューリングはその複雑さのため困難である。 従来のスケジューリングアルゴリズムは、最短のジョブファースト(SJF)やクリティカルパス(CP)といった単純なヒューリスティックに大きく依存しており、スケジューリング品質に欠けることが多い。 本稿では,DAGタスクのスケジューリングに新たな学習ベースアプローチを提案する。 このアルゴリズムでは、強化学習エージェントを使用して、DAGに1回ずつ有向エッジを反復的に追加し、"トリッキー"なジョブノードの順序付け(実行の優先順位とリソース割り当て)を実行する。 これにより、元のDAGスケジューリング問題は、SJFやCPなどのヒューリスティックスケジューリングアルゴリズムを効率的に改善できる、はるかに単純なプロキシ問題へと劇的に削減される。 本手法は既存のヒューリスティックスケジューリングアルゴリズムにも容易に適用できる。 TPC-Hのベンチマークデータセットから,我々の学習に基づくアプローチは,一般的なヒューリスティックアルゴリズムよりも大幅に向上し,様々な条件下でのいくつかの手法の最高の性能を一貫して達成できることを示す。

関連論文リスト

• A Schedule of Duties in the Cloud Space Using a Modified Salp Swarm Algorithm [0.0]
  クラウド領域で最も重要なNPハード問題のひとつはスケジューリングです。 Salp Swarm Algorithm (SSA)と呼ばれる集団知能アルゴリズムの1つが拡張され、改良され、適用された。 その結果,本アルゴリズムは一般に他のアルゴリズムよりも高い性能を示した。
  論文  参考訳（メタデータ） (2023-09-18T02:48:41Z)
• Edge Generation Scheduling for DAG Tasks Using Deep Reinforcement Learning [2.365237699556817]
  直接非巡回グラフ(DAG)タスクは現在、複雑なアプリケーションをモデル化するためにリアルタイムドメインで採用されている。 エッジを反復的に生成することでDAG幅を最小化する新しいDAGスケジューリングフレームワークを提案する。 我々は,提案アルゴリズムの有効性を,最先端DAGスケジューリングと最適混合整数線形プログラミングベースラインとの比較により評価した。
  論文  参考訳（メタデータ） (2023-08-28T15:19:18Z)
• An End-to-End Reinforcement Learning Approach for Job-Shop Scheduling Problems Based on Constraint Programming [5.070542698701157]
  本稿では,CPと強化学習(Reinforcement Learning, RL)を用いてスケジューリング問題を解決する新しいエンドツーエンドアプローチを提案する。 当社のアプローチでは,既存のCPソルバを活用して,プライオリティ・ディスパッチ・ルール(PDR)を学ぶエージェントをトレーニングする。
  論文  参考訳（メタデータ） (2023-06-09T08:24:56Z)
• Reinforcement Learning with Success Induced Task Prioritization [68.8204255655161]
  本稿では,自動カリキュラム学習のためのフレームワークであるSuccess induced Task Prioritization (SITP)を紹介する。 アルゴリズムはエージェントに最速の学習を提供するタスクの順序を選択する。 我々は,SITPが他のカリキュラム設計手法と一致するか,あるいは上回っていることを実証する。
  論文  参考訳（メタデータ） (2022-12-30T12:32:43Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。 マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。 本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
  論文  参考訳（メタデータ） (2022-01-25T00:10:03Z)
• GCNScheduler: Scheduling Distributed Computing Applications using Graph Convolutional Networks [12.284934135116515]
  グラフ畳み込み型ネットワークベーススケジューラ(GCNScheduler)を提案する。 タスク間データ依存関係構造とネットワーク設定を慎重に入力グラフに統合することにより、GCNSchedulerは所定の目的のためにタスクを効率的にスケジュールすることができる。 従来のHEFTアルゴリズムよりもマインパンが良く、スループット指向のHEFTとほぼ同じスループットであることを示す。
  論文  参考訳（メタデータ） (2021-10-22T01:54:10Z)
• Better than the Best: Gradient-based Improper Reinforcement Learning for Network Scheduling [60.48359567964899]
  パケット遅延を最小限に抑えるため,制約付き待ち行列ネットワークにおけるスケジューリングの問題を考える。 我々は、利用可能な原子ポリシーよりも優れたスケジューラを生成するポリシー勾配に基づく強化学習アルゴリズムを使用する。
  論文  参考訳（メタデータ） (2021-05-01T10:18:34Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。 スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。 その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
  論文  参考訳（メタデータ） (2021-03-10T03:16:12Z)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  メタラーニング強化学習アルゴリズムの手法を提案する。 学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。 従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
  論文  参考訳（メタデータ） (2021-01-08T18:55:07Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Geometric Deep Reinforcement Learning for Dynamic DAG Scheduling [8.14784681248878]
  本稿では,現実的なスケジューリング問題を解決するための強化学習手法を提案する。 高性能コンピューティングコミュニティにおいて一般的に実行されるアルゴリズムであるColesky Factorizationに適用する。 我々のアルゴリズムは,アクター・クリティカル・アルゴリズム (A2C) と組み合わせてグラフニューラルネットワークを用いて,問題の適応表現をオンザフライで構築する。
  論文  参考訳（メタデータ） (2020-11-09T10:57:21Z)

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

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