マルチバージョンタスクの最適バージョン決定問題に対する動的計画法に基づく近似解法(組込みシステム,一般)

元データ 2010-01-14

概要

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

著者

潮 俊光 大阪大学大学院基礎工学研究科
潮 俊光 神戸女学院大学
潮 俊光 大阪大学 大学院基礎工学研究科
寺田 早百合 大阪大学大学院基礎工学研究科

関連論文

▼もっと見る