論文の概要: A heuristic method for data allocation and task scheduling on
heterogeneous multiprocessor systems under memory constraints
- arxiv url: http://arxiv.org/abs/2206.05268v1
- Date: Mon, 9 May 2022 10:46:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-13 20:12:58.603852
- Title: A heuristic method for data allocation and task scheduling on
heterogeneous multiprocessor systems under memory constraints
- Title（参考訳）: メモリ制約下における異種マルチプロセッサシステムにおけるデータ割り当てとタスクスケジューリングのヒューリスティック手法
- Authors: Junwen Ding, Liangcai Song, Siyuan Li, Chen Wu, Ronghua He, Zhouxing
Su, Zhipeng L\"u
- Abstract要約: 本稿では,メモリ制約下でのデータ割り当てとタスクスケジューリングの問題に焦点をあてる。
本稿では,いくつかの特徴を組み合わせたタブ探索アルゴリズムを提案する。
実験により,提案アルゴリズムは比較的高品質な解を妥当な計算時間で得られることを示した。
- 参考スコア（独自算出の注目度）: 14.681986126866452
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Computing workflows in heterogeneous multiprocessor systems are frequently
modeled as directed acyclic graphs of tasks and data blocks, which represent
computational modules and their dependencies in the form of data produced by a
task and used by others. However, for some workflows, such as the task schedule
in a digital signal processor may run out of memory by exposing too much
parallelism. This paper focuses on the data allocation and task scheduling
problem under memory constraints, and concentrates on shared memory platforms.
We first propose an integer linear programming model to formulate the problem.
Then we consider the problem as an extended flexible job shop scheduling
problem, while trying to minimize the critical path of the graph. To solve this
problem, we propose a tabu search algorithm (TS) which combines several
distinguished features such as a greedy initial solution construction method
and a mixed neighborhood evaluation strategy based on exact evaluation and
approximate evaluation methods. Experimental results on randomly generated
instances show that the the proposed TS algorithm can obtain relatively
high-quality solutions in a reasonable computational time. In specific, the
tabu search method averagely improves the makespan by 5-25\% compared to the
classical load balancing algorithm that are widely used in the literature.
Besides, some key features of TS are also analyzed to identify its success
factors.
- Abstract（参考訳）: ヘテロジニアスマルチプロセッサシステムにおける計算ワークフローは、しばしばタスクとデータブロックの有向非循環グラフとしてモデル化される。
しかし、デジタル信号プロセッサのタスクスケジュールのようなワークフローでは、過度に並列性を公開することでメモリが切れることがある。
本稿では,メモリ制約下でのデータ割当とタスクスケジューリングの問題に着目し,共有メモリプラットフォームに集中する。
まず,問題を定式化する整数線形プログラミングモデルを提案する。
次に,グラフのクリティカルパスを最小化しつつ,拡張フレキシブルなジョブショップスケジューリング問題として問題を考える。
そこで本研究では, 厳密な評価と近似評価法に基づいて, グリーディ初期解構築法と混合近傍評価法といったいくつかの特徴を組み合わせる, タブサーチアルゴリズム (ts) を提案する。
ランダムに生成されたインスタンスに対する実験結果から,提案アルゴリズムは比較的高品質な解を妥当な計算時間で得られることを示した。
具体的には, 文献で広く用いられている古典的負荷分散アルゴリズムと比較して, 平均で5～25\%改善する。
さらに、TSのいくつかの重要な特徴は、その成功要因を特定するために分析される。
関連論文リスト
- A Weighted K-Center Algorithm for Data Subset Selection [70.49696246526199]
サブセット選択は、トレーニングデータの小さな部分を特定する上で重要な役割を果たす、基本的な問題である。
我々は,k中心および不確かさサンプリング目的関数の重み付け和に基づいて,サブセットを計算する新しい係数3近似アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-12-17T04:41:07Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - 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) - Numerical Methods for Convex Multistage Stochastic Optimization [86.45244607927732]
最適化プログラミング(SP)、最適制御(SOC)、決定プロセス(MDP)に焦点を当てる。
凸多段マルコフ問題の解決の最近の進歩は、動的プログラミング方程式のコスト対ゴー関数の切断面近似に基づいている。
切削平面型法は多段階問題を多段階的に扱えるが、状態(決定)変数は比較的少ない。
論文 参考訳（メタデータ） (2023-03-28T01:30:40Z) - Scalable Batch Acquisition for Deep Bayesian Active Learning [70.68403899432198]
ディープラーニングでは、各ステップでマークアップする複数の例を選択することが重要です。
BatchBALDのような既存のソリューションでは、多くの例を選択する際に大きな制限がある。
本稿では,より計算効率のよいLarge BatchBALDアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-13T11:45:17Z) - Accelerating ERM for data-driven algorithm design using output-sensitive techniques [26.32088674030797]
データ駆動型アルゴリズム設計のための効率的な学習アルゴリズムを開発するための技術について研究する。
提案手法は,超平面の集合によって誘導されるポリトープを列挙する出力感受性アルゴリズムである。
本稿では、価格問題、リンクベースのクラスタリング、動的プログラミングに基づくシーケンスアライメントのアルゴリズムを提供することにより、我々の技術を説明する。
論文 参考訳（メタデータ） (2022-04-07T17:27:18Z) - 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) - Learning to Schedule DAG Tasks [7.577417675452624]
有向非周期グラフ(DAG)のスケジューリングに関する新しい学習手法を提案する。
このアルゴリズムは強化学習エージェントを用いて、DAGに向けられたエッジを反復的に追加する。
我々の手法は既存のスケジューリングアルゴリズムにも容易に適用できる。
論文 参考訳（メタデータ） (2021-03-05T01:10:24Z) - Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。
リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。
このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
論文 参考訳（メタデータ） (2021-02-27T19:28:39Z) - Data-driven Algorithm Design [21.39493074700162]
データ駆動型アルゴリズム設計は、現代のデータ科学とアルゴリズム設計の重要な側面である。
パラメータの小さな微調整は、アルゴリズムの振る舞いのカスケードを引き起こす可能性がある。
バッチおよびオンラインシナリオに対して、強力な計算および統計的パフォーマンス保証を提供する。
論文 参考訳（メタデータ） (2020-11-14T00:51:57Z) - Learning the Step-size Policy for the Limited-Memory
Broyden-Fletcher-Goldfarb-Shanno Algorithm [3.7470451129384825]
本稿では,L-BFGSアルゴリズムのステップサイズポリシの学習方法について考察する。
入力として電流勾配の局所的な情報を用いたニューラルネットワークアーキテクチャを提案する。
ステップ長ポリシは、同様の最適化問題のデータから学習され、目的関数のさらなる評価を回避し、出力ステップが予め定義された間隔内に留まることを保証します。
論文 参考訳（メタデータ） (2020-10-03T09:34:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。