ヘテロジニアスDAGスケジューリングのためのギャップ認識生成による学習手法

要旨: 不均一（ヘテロジニアス）な環境における有向非巡回グラフ（DAG）の効率的なスケジューリングは、資源容量と依存関係のために困難です。実際には、さまざまな資源プールとタスク種別を持つ環境間で適応する必要性に加え、急速なスケジュール生成が求められることが、これらの課題をさらに複雑にします。本研究では、タスク—プール適合係数および生成に起因する最適性ギャップに対処する、不均一DAGスケジューリングのためのエンドツーエンド強化学習フレームワークWeCANを提案します。WeCANは、二段階のシングルパス設計を採用します。すなわち、単一のフォワードパスでタスク—プールスコアとグローバルパラメータを生成し、その後に生成マップがスケジュールを構築することで、ネットワーク呼び出しの反復なしに生成を実現します。重み付きクロスアテンション・エンコーダは、適合係数によってゲートされたタスク—プール間の相互作用をモデル化し、環境の変動に対してサイズ非依存です。さらに、広く用いられるリストスケジューリングのマップは、到達可能性が制限されることで、生成に起因する最適性ギャップを生じさせ得ます。そこで本研究では、生成マップの到達可能な集合を、実行可能なスケジュール順序によって特徴づける順序空間解析を導入し、生成に起因するギャップのメカニズムを説明するとともに、ギャップ消去のための十分条件を導出します。これらの条件に導かれて、解析的にパラメータ化された減少型スキップ規則を備えたskip-extendedな実現を設計します。これにより、単一パスの効率を維持したまま到達可能な順序集合を拡大します。計算グラフおよび実世界のTPC-H DAGに関する実験では、強力なベースラインに対してメイクスパンが改善されました。推論時間は古典的なヒューリスティックと同程度であり、複数ラウンドのニューラルスケジューラよりも高速でした。