| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2010-01-21 15:50 マルチバージョンタスクの最適バージョン決定問題に対する動的計画法に基づく近似解法 ○寺田早百合・潮 俊光（阪大）  CST2009-42 |
|
| 抄録 | （和） | 組込み制御システムにおいて，そのジョブの実行遅延やジッタが大きくなると実行結果の性能が劣化する．タスクの相対的デッドラインを小さくすることで遅延やジッタを軽減できるが，スケジュールは過密になり過負荷状態を招く恐れがある．したがって，スケジュール可能性を保証しつつ，実行結果の性能を最大化するように実行パラメータを調整する必要がある．本報告では各タスクはマルチバージョンタスクであるとし，バージョンごとに実行時間や相対的デッドライン，効用という実行パラメータが定まると仮定する．各タスクがリリースするジョブの最適バージョン決定問題を定式化し，グラフの最長パス探索問題に帰着する．最適解導出アルゴリズムと状態数の削減により計算量を削減する近似アルゴリズムを提案する．最後にシミュレーションにより近似アルゴリズムの有効性を示す． |
| （英） | In embedded control systems, the computational delay and the jitter of each job released by a task influence systems' performances harmfully. By decreasing relative deadlines of the jobs, we can reduce them. However, it may lead to the overload situation. The execution parameters should be selected to maximize the total benefits with satisfying schedulability conditions. In this paper, we assume that each task is designed based on a multiversion task model, where a version is specified by the relative deadline, the execution time, and the benefit of each released job. We formulate an optimal configuration problem and reduce it to a maximum path problem. We propose an approximate algorithm based on the forward dynamic programming, where states are merged and/or eliminated to reduce the computational time. The efficiency of the proposed algorithm is illustrated by simulations. | |
| キーワード | （和） | リアルタイムシステム / EDF / マルチバージョンタスクモデル / 動的計画法 / / / / |
| （英） | Real-time systems / EDF / Multiversion task model / Dynamic Programming / / / / | |
| 文献情報 | 信学技報, vol. 109, 2010年1月. | |
| 資料番号 | ||
| 発行日 | 2010-01-14 (CST) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | CST2009-42 |
|
| 研究会情報 | |
| 研究会 | MSS |
| 開催期間 | 2010-01-21 - 2010-01-22 |
| 開催地（和） | 豊田中央研究所アクタスCホール |
| 開催地（英） | Toyota Central R&D Labs. |
| テーマ（和） | 組込みシステム，一般 |
| テーマ（英） | Embedded System, etc |
| 講演論文情報の詳細 | |
| 申込み研究会 | MSS |
| 会議コード | 2010-01-CST |
| 本文の言語 | 日本語 |
| タイトル（和） | マルチバージョンタスクの最適バージョン決定問題に対する動的計画法に基づく近似解法 |
| サブタイトル（和） | |
| タイトル（英） | Approximate Solution Based on the Dynamic Programming for Optimal Configuration Problem of the Multiversion Tasks |
| サブタイトル（英） | |
| キーワード(1)（和/英） | リアルタイムシステム / Real-time systems |
| キーワード(2)（和/英） | EDF / EDF |
| キーワード(3)（和/英） | マルチバージョンタスクモデル / Multiversion task model |
| キーワード(4)（和/英） | 動的計画法 / Dynamic Programming |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 寺田 早百合 / Sayuri Terada / テラダ サユリ |
| 第1著者 所属（和/英） | 大阪大学 (略称： 阪大) Osaka University (略称： Osaka Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 潮 俊光 / Toshimitsu Ushio / ウシオ トシミツ |
| 第2著者 所属（和/英） | 大阪大学 (略称： 阪大) Osaka University (略称： Osaka Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2010-01-21 15:50:00 |
| 発表時間 | 25分 |
| 申込先研究会 | MSS |
| 資料番号 | CST2009-42 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | no.367 |
| ページ範囲 | pp.31-36 |
| ページ数 | 6 |
| 発行日 | 2010-01-14 (CST) |
[研究会発表申込システムのトップページに戻る]