論文の概要: Edge Generation Scheduling for DAG Tasks Using Deep Reinforcement
Learning
- arxiv url: http://arxiv.org/abs/2308.14647v2
- Date: Thu, 11 Jan 2024 00:20:15 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-13 03:44:19.651357
- 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 domains 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. The code is available at
https://github.com/binqi-sun/egs.
- Abstract(参考訳): 有向非循環グラフ(dag)タスクは現在、リアルタイムドメインで採用されており、相互通信タスクの連鎖を通じて機能を実装する自動車、アビオニクス、産業ドメインから複雑なアプリケーションをモデル化している。
本稿では,自明なシェジュラビリティの概念に基づく新しいシェジュラビリティテストを提案することにより,リアルタイム dag タスクのスケジューリングの問題について述べる。
このスケジューリング可能性テストを用いて、期限制約を保証しつつエッジを反復的に生成することでDAG幅を最小化する新しいDAGスケジューリングフレームワーク(エッジジェネレーションスケジューリング -- EGS)を提案する。
グラフ表現ニューラルネットワークと組み合わせた深部強化学習アルゴリズムを開発し,ESGの効率的なエッジ生成ポリシーを学習することにより,エッジ生成の効率よく解決する方法を検討する。
我々は,提案アルゴリズムの有効性を,最先端DAGスケジューリングヒューリスティックスと最適混合整数線形プログラミングベースラインとの比較により評価した。
実験の結果,提案アルゴリズムは,同一のDAGタスクをスケジュールするプロセッサを少なくすることで,最先端のアルゴリズムよりも優れていることがわかった。
コードはhttps://github.com/binqi-sun/egsで入手できる。
関連論文リスト
- 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) - A Memetic Algorithm with Reinforcement Learning for Sociotechnical
Production Scheduling [0.0]
本稿では、フレキシブルジョブショップスケジューリング問題(DRC-FJSSP)に深層強化学習(DRL)を適用したメメティックアルゴリズムを提案する。
産業における研究プロジェクトから、フレキシブルマシン、フレキシブルなヒューマンワーカー、作業能力、セットアップと処理操作、材料到着時間、材料製造の請求書の並列タスク、シーケンス依存のセットアップ時間、人間と機械のコラボレーションにおける(一部)自動化タスクを検討する必要性を認識します。
論文 参考訳(メタデータ) (2022-12-21T11:24:32Z) - A heuristic method for data allocation and task scheduling on
heterogeneous multiprocessor systems under memory constraints [14.681986126866452]
本稿では,メモリ制約下でのデータ割り当てとタスクスケジューリングの問題に焦点をあてる。
本稿では,いくつかの特徴を組み合わせたタブ探索アルゴリズムを提案する。
実験により,提案アルゴリズムは比較的高品質な解を妥当な計算時間で得られることを示した。
論文 参考訳(メタデータ) (2022-05-09T10:46:08Z) - 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) - Distributed stochastic optimization with large delays [59.95552973784946]
大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。
DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
論文 参考訳(メタデータ) (2021-07-06T21:59:49Z) - 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) - Learning to Execute Programs with Instruction Pointer Attention Graph
Neural Networks [55.98291376393561]
グラフニューラルネットワーク(GNN)は、ソフトウェアエンジニアリングタスクを学習するための強力なツールとして登場した。
リカレントニューラルネットワーク(RNN)は、長いシーケンシャルな推論の連鎖に適しているが、プログラム構造を自然に組み込んでいるわけではない。
本稿では,新しいGNNアーキテクチャ,IPA-GNN(Instruction Pointer Attention Graph Neural Networks)を導入する。
論文 参考訳(メタデータ) (2020-10-23T19:12:30Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。