| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2008-03-28 14:45 再構成オーバヘッドを考慮した動的再構成可能プロセッサへの実時間タスク群分割実装アルゴリズムの提案 ○西 圭祐（阪大）・木谷友哉（奈良先端大）・中田明夫（広島市大）・東野輝夫（阪大）  DC2007-114 CPSY2007-110 |
|
| 抄録 | （和） | ネットワークのユビキタス化に伴い，多種多様な組み込みシステムの開発・生産が行われている．そのような組み込みシステムは製造コストの観点から，再構成可能論理プロセッサに実装されることが多い．近年，そのプロセッサの論理構成領域の面積利用効率を改善するため，システムの動作中に動的に回路構成を変更できるマルチコンテキスト型動的再構成可能プロセッサの研究が盛んである．マルチコンテキスト型動的再構成可能プロセッサ(DRP) に実時間並行システムを実装する場合，システムを複数のタスクに分割し，各タスクの時間制約を考慮して複数のコンテキスト上に実装する．得られたコンテキストをあらかじめ定めたタイミングで切り替えていくことにより，システム全体の動作が実現される．これまでに，DRP に対する様々なタスク分割手法が研究されているが[1] [2] [3]，これらの手法の多くは組み込みシステムを構成する内部のタスクが満たすべき実時間制約の存在を仮定しておらず，仕様が時間制約を満たすことは保証されない．本研究では，先行研究[4]を拡張し，コンテキストの切り替え時のオーバーヘッドを考慮しつつ最適なタスク割当を求めるための問題を整数線形問題(ILP) として定式化した．また，サイズの大きな問題に対しても実用的な時間で解を求められるよう，FDS (Force-directed Scheduling) と貪欲法を利用した2 段階のヒューリスティックアルゴリズムを提案している． 提案手法では，コンテキスト切り替え時のオーバーヘッドやコンテキストの枚数などをパラメータとして取り扱うことができるようにすることで，より汎用性の高い動的再構成可能プロセッサを対象としたタスク割り当てが行えるようにしている． 加えて，解くべき問題のサイズが大きい場合に対しても，実用時間で解を得るためのヒューリスティックなタスク群分割アルゴリズムを提案している．提案アルゴリズムでは，並行に動作する実行系列の各タスクをノードで表現し，同時にシステム上で実行される可能性があるタスク群に対応するノード間にエッジを引いたグラフを作る．このとき，サイズが最大のクリークを同じコンテキストに割り当て，1 つのノードとしてマージしていくことで，ある時刻において同時に実行される可能性があるタスクの集合の最大サイズを小さくする工夫を行っている． 予備実験で，複数の比較的小規模な例題に対して，提案するヒューリスティックで求めた最適解の評価値がILP によって求めた解のXXX 倍程度に抑えられることを確認した．また，ILP では実用的な時間で解が求まらない規模の例題に対しても，ヒューリスティックでは数秒のオーダで解を求めることができることを確認した．さらに，簡単な携帯電話端末の例題を元に，システム設計における本手法の有用性を評価した． |
| （英） | (Not available yet) | |
| キーワード | （和） | 実時間システム / 動的再構成可能プロセッサ / マルチコンテキスト / 整数線形計画法 / スケジューリング / / / |
| （英） | / / / / / / / | |
| 文献情報 | 信学技報, vol. 107, no. 559, DC2007-114, pp. 179-184, 2008年3月. | |
| 資料番号 | DC2007-114 | |
| 発行日 | 2008-03-20 (DC, CPSY) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | DC2007-114 CPSY2007-110 |
|
| 研究会情報 | |
| 研究会 | DC CPSY IPSJ-SLDM IPSJ-EMB |
| 開催期間 | 2008-03-27 - 2008-03-28 |
| 開催地（和） | 屋久島 離島総合開発センター |
| 開催地（英） | |
| テーマ（和） | 組込技術とネットワークに関するワークショップ ETNET2008（コンピュータシステム研究会、情報処理学会システムLSI設計技術研究会、情報処理学会組込みシステム研究会共催） |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | DC |
| 会議コード | 2008-03-DC |
| 本文の言語 | 日本語 |
| タイトル（和） | 再構成オーバヘッドを考慮した動的再構成可能プロセッサへの実時間タスク群分割実装アルゴリズムの提案 |
| サブタイトル（和） | |
| タイトル（英） | A Context Assignment Algorithm for Real-time Tasks on Dynamically Reconfigurable Processor with Reconfigurable Overhead |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 実時間システム / |
| キーワード(2)（和/英） | 動的再構成可能プロセッサ / |
| キーワード(3)（和/英） | マルチコンテキスト / |
| キーワード(4)（和/英） | 整数線形計画法 / |
| キーワード(5)（和/英） | スケジューリング / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 西 圭祐 / Keisuke Nishi / ニシ ケイスケ |
| 第1著者 所属（和/英） | 大阪大学 (略称： 阪大) Osaka University (略称： Osaka Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 木谷 友哉 / Tomoya Kitani / キタニ トモヤ |
| 第2著者 所属（和/英） | 奈良先端科学技術大学院大学 (略称： 奈良先端大) Nara Institute of Science and Technology (略称： NAIST) |
| 第3著者 氏名（和/英/ヨミ） | 中田 明夫 / Akio Nakata / ナカタ アキオ |
| 第3著者 所属（和/英） | 広島市立大学 (略称： 広島市大) Hiroshima City University (略称： Hiroshima City Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 東野 輝夫 / Teruo Higashino / ヒガシノ テルオ |
| 第4著者 所属（和/英） | 大阪大学 (略称： 阪大) Osaka University (略称： Osaka Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2008-03-28 14:45:00 |
| 発表時間 | 25分 |
| 申込先研究会 | DC |
| 資料番号 | DC2007-114, CPSY2007-110 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | no.559(DC), no.558(CPSY) |
| ページ範囲 | pp.179-184 |
| ページ数 | 6 |
| 発行日 | 2008-03-20 (DC, CPSY) |
[研究会発表申込システムのトップページに戻る]