文献

J-GLOBAL ID：201702229403255585   整理番号：17A0667564

HLBS:DAGベース実時間計算のための不均一弛緩に基づくスケジューリングアルゴリズム【Powered by NICT】

HLBS: Heterogeneous Laxity-Based Scheduling Algorithm for DAG-Based Real-Time Computing

著者 (5件)： Suzuki Yuhei ,  Azumi Takuya ,  Nobuhiko ,  Nishio ,  Kato Shinpei
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2016  号： CPSNA  ページ： 83-88  発行年： 2016年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： タスクグラフの並列スケジューリングは,並列処理の分野で重要な研究主題であり,挑戦的なNP完全問題であることが知られている。データフローシステムにおけるスケジューリングは,有向非循環グラフ(DAG)で表すことができる。DAGを用いた並列タスクスケジューリングにおいて,依存タスクを管理する全体実行時間を減少させる。しかし,アルゴリズムは様々なデッドラインとマルチ出力のミックス,自律運転システムのようなリアルタイムシステムには適用できない,実時間システムはDAG主にfork-join構造として知られている限られた糸で表すことができるからである。DAGの構造に依存しないことを実時間スケジューリングアルゴリズムを広く用いることができる。不均一弛緩に基づくスケジューリング(HLBS)アルゴリズム,この問題を解決するためのリストスケジューリング発見的方法を提案した。HLBSはデッドラインまで休止時間,弛緩として知られるを計算し,プロセッサに短い弛みを有するタスクを割り当てる。これはデッドラインミス率を低減するために複数のデッドラインのスケジューリングを可能にする。評価結果は,HLBSはデッドラインミス率を低下させた平均45.6%の以前の研究で提案したアルゴリズムの性能と同等の性能レベルを達成することを示した。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： 実時間処理 ,  NP完全問題 ,  *計算 ,  演算プロセッサ ,  *アルゴリズム ,  時間制限 ,  *スケジューリング ,  発見的方法 ,  並列処理
準シソーラス用語： 実行時間 ,  タスクスケジューリング ,  DAG【グラフ】 ,  タスクグラフ ,  *スケジューリングアルゴリズム ,  *実時間 , 【Automatic Indexing@JST】

分類 (3件)： ディジタル計算機方式一般  (JC02010O) ,  オペレーティングシステム  (JD03020J) ,  ネットワーク法  (KA03040X)

タイトルに関連する用語 (6件)： DAG ,  実時間 ,  計算 ,  不均一 ,  弛緩 ,  スケジューリングアルゴリズム