文献

J-GLOBAL ID：201002272568688026   整理番号：10A0195939

マルチバージョンタスクの最適バージョン決定問題に対する動的計画法に基づく近似解法

Approximate Solution Based on the Dynamic Programming for Optimal Configuration Problem of the Multiversion Tasks

著者 (2件)： 寺田早百合 (大阪大 大学院基礎工学研究科) ,  潮俊光 (大阪大 大学院基礎工学研究科)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 109  号： 367(CST2009 37-53)  ページ： 31-36  発行年： 2010年01月14日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 組込み制御システムにおいて,そのジョブの実行遅延やジッタが大きくなると実行結果の性能が劣化する。タスクの相対的デッドラインを小さくすることで遅延やジッタを軽減できるが,スケジュールは過密になり過負荷状態を招く恐れがある。したがって,スケジュール可能性を保証しつつ,実行結果の性能を最大化するように実行パラメータを調整する必要がある。本報告では各タスクはマルチバージョンタスクであるとし,バージョンごとに実行時間や相対的デッドライン,効用という実行パラメータが定まると仮定する。各タスクがリリースするジョブの最適バージョン決定問題を定式化し,グラフの最長パス探索問題に帰着する。最適解導出アルゴリズムと状態数の削減により計算量を削減する近似アルゴリズムを提案する。最後にシミュレーションにより近似アルゴリズムの有効性を示す。(著者抄録)

シソーラス用語： 計算機処理方式 ,  *多重処理 ,  *最適化問題 ,  決定問題 ,  動的計画法 ,  *近似法 ,  *制御系 ,  埋込み【挿入】 ,  プログラム実行 ,  スケジューリング ,  探索問題 ,  グラフ ,  計算量 ,  実時間処理
準シソーラス用語： マルチタスク

分類 (1件)： システム最適化手法  (IA02050Z)

引用文献 (8件)：

• LIU, J. W. S. Real-Time Systems. 2000
• BINI, E. The space of edf deadlines : the exact region and a convex approximation. Real-Time Systems. 2009, 41, 27-51
• BALBASTRE, P. Optimal deadline assignment for periodic real-time tasks in dynamic priority systems. proceedings of the 18th Euromicro Conference on Real-Time Systems. 2006, 1, 3, 65-74
• CHANTEM, T. Generalized elastic scheduling for real-time tasks. IEEE Transactions on Computers. 2009, 58, 4, 480-495
• LIMA, G. Dynamic reconfiguration for adaptive multiversion real-time systems. Proceedings of IEEE Euromicro Conferense on Real-Time Systems, 2008. 2008, 115-124

タイトルに関連する用語 (3件)： 決定問題 ,  動的計画法 ,  近似解法