論文の概要: Edge Generation Scheduling for DAG Tasks using Deep Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2308.14647v1
• Date: Mon, 28 Aug 2023 15:19:18 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-29 13:27:27.073499
• Title: Edge Generation Scheduling for DAG Tasks using Deep Reinforcement Learning
• Title（参考訳）: 深部強化学習を用いたDAGタスクのエッジ生成スケジューリング
• Authors: Binqi Sun, Mirco Theile, Ziyuan Qin, Daniele Bernardini, Debayan Roy, Andrea Bastoni, and Marco Caccamo
• Abstract要約: 直接非巡回グラフ(DAG)タスクは現在、複雑なアプリケーションをモデル化するためにリアルタイムドメインで採用されている。 エッジを反復的に生成することでDAG幅を最小化する新しいDAGスケジューリングフレームワークを提案する。 我々は,提案アルゴリズムの有効性を,最先端DAGスケジューリングと最適混合整数線形プログラミングベースラインとの比較により評価した。
• 参考スコア（独自算出の注目度）: 2.365237699556817
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Directed acyclic graph (DAG) tasks are currently adopted in the real-time domain to model complex applications from the automotive, avionics, and industrial domain that implement their functionalities through chains of intercommunicating tasks. This paper studies the problem of scheduling real-time DAG tasks by presenting a novel schedulability test based on the concept of trivial schedulability. Using this schedulability test, we propose a new DAG scheduling framework (edge generation scheduling -- EGS) that attempts to minimize the DAG width by iteratively generating edges while guaranteeing the deadline constraint. We study how to efficiently solve the problem of generating edges by developing a deep reinforcement learning algorithm combined with a graph representation neural network to learn an efficient edge generation policy for EGS. We evaluate the effectiveness of the proposed algorithm by comparing it with state-of-the-art DAG scheduling heuristics and an optimal mixed-integer linear programming baseline. Experimental results show that the proposed algorithm outperforms the state-of-the-art by requiring fewer processors to schedule the same DAG tasks.
• Abstract（参考訳）: 有向非循環グラフ(dag)タスクは現在、リアルタイムドメインで採用されており、相互通信タスクの連鎖を通じて機能を実装する自動車、アビオニクス、産業ドメインから複雑なアプリケーションをモデル化している。 本稿では,自明なシェジュラビリティの概念に基づく新しいシェジュラビリティテストを提案することにより,リアルタイム dag タスクのスケジューリングの問題について述べる。 このスケジューリング可能性テストを用いて、期限制約を保証しつつエッジを反復的に生成することでDAG幅を最小化する新しいDAGスケジューリングフレームワーク(エッジジェネレーションスケジューリング -- EGS)を提案する。 グラフ表現ニューラルネットワークと組み合わせた深部強化学習アルゴリズムを開発し,ESGの効率的なエッジ生成ポリシーを学習することにより,エッジ生成の効率よく解決する方法を検討する。 我々は,提案アルゴリズムの有効性を,最先端DAGスケジューリングヒューリスティックスと最適混合整数線形プログラミングベースラインとの比較により評価した。 実験の結果,提案アルゴリズムは,同一のDAGタスクをスケジュールするプロセッサを少なくすることで,最先端のアルゴリズムよりも優れていることがわかった。

関連論文リスト

• Instance-Aware Graph Prompt Learning [71.26108600288308]
  本稿では,インスタンス対応グラフプロンプト学習(IA-GPL)について紹介する。 このプロセスでは、軽量アーキテクチャを使用して各インスタンスの中間プロンプトを生成する。 複数のデータセットと設定で実施された実験は、最先端のベースラインと比較して、IA-GPLの優れたパフォーマンスを示している。
  論文  参考訳（メタデータ） (2024-11-26T18:38:38Z)
• $ψ$DAG: Projected Stochastic Approximation Iteration for DAG Structure Learning [6.612096312467342]
  Directed A Graphs (DAGs) の構造を学ぶことは、ノード数に応じてスケールする可能なグラフの巨大な検索空間のため、大きな課題となる。 近年の進歩は、微分可能指数関数性制約を取り入れた連続最適化タスクとしてこの問題を再定義している。 本稿では,SGD(Gradient Descent)に基づく最適化手法と統合した近似手法を用いて,DAGを学習する新しいフレームワークを提案する。
  論文  参考訳（メタデータ） (2024-10-31T12:13:11Z)
• TS-EoH: An Edge Server Task Scheduling Algorithm Based on Evolution of Heuristic [0.6827423171182154]
  本稿では,EC理論と進化的アルゴリズムに基づく新しいタスクスケジューリング手法を提案する。 実験の結果,タスクスケジューリングアルゴリズムは従来の強化学習法よりも優れていた。
  論文  参考訳（メタデータ） (2024-09-04T10:00:32Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAEはグラフオートエンコーダフレームワークで、GNNの転送性と安定性を活用して、再トレーニングなしに効率的なネットワークアライメントを実現する。 実験の結果、T-GAEは最先端の最適化手法と最高のGNN手法を最大38.7%、50.8%で上回っていることがわかった。
  論文  参考訳（メタデータ） (2023-10-05T02:58:29Z)
• GA-DRL: Graph Neural Network-Augmented Deep Reinforcement Learning for DAG Task Scheduling over Dynamic Vehicular Clouds [35.418964557667096]
  本稿では、動的VC上でDAGタスクをスケジューリングするためのグラフニューラルネットワーク強化深部強化学習方式(GA-DRL)を提案する。 GA-DRLはDAGタスク完了時間で既存のベンチマークを上回っている。
  論文  参考訳（メタデータ） (2023-07-03T06:41:15Z)
• 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)
• A Scalable Deep Reinforcement Learning Model for Online Scheduling Coflows of Multi-Stage Jobs for High Performance Computing [9.866286878494979]
  多段階ジョブでは、各ジョブは複数のコフローで構成され、DAG(Directed Acyclic Graph)によって表現される。 本稿では,入力を処理する新しいパイプライン-DAGNNを提案し,新しいコフロースケジューリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-21T09:36:55Z)
• Better than the Best: Gradient-based Improper Reinforcement Learning for Network Scheduling [60.48359567964899]
  パケット遅延を最小限に抑えるため,制約付き待ち行列ネットワークにおけるスケジューリングの問題を考える。 我々は、利用可能な原子ポリシーよりも優れたスケジューラを生成するポリシー勾配に基づく強化学習アルゴリズムを使用する。
  論文  参考訳（メタデータ） (2021-05-01T10:18:34Z)
• Learning to Schedule DAG Tasks [7.577417675452624]
  有向非周期グラフ(DAG)のスケジューリングに関する新しい学習手法を提案する。 このアルゴリズムは強化学習エージェントを用いて、DAGに向けられたエッジを反復的に追加する。 我々の手法は既存のスケジューリングアルゴリズムにも容易に適用できる。
  論文  参考訳（メタデータ） (2021-03-05T01:10:24Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Efficient and Stable Graph Scattering Transforms via Pruning [86.76336979318681]
  グラフ散乱変換(GST)は、グラフデータから特徴を抽出する訓練のないディープGCNモデルを提供する。 GSTが支払う価格は、層の数によって増加する空間と時間の指数関数的な複雑さである。 本研究は, GST の複雑性の限界に対処し, 効率的な (p) GST アプローチを導入する。
  論文  参考訳（メタデータ） (2020-01-27T16:05:56Z)

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

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