| 講演名 | 2007/3/9 動的リコンフィギャラブルプロセッサへの時間制約付き機能モジュール群分割アルゴリズムの検討(DRP,FPGA,組込技術とネットワークに関するワークショップETNET2007) 木谷 友哉, 中橋 亮, 中田 明夫, 安本 慶一, 東野 輝夫, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本稿では,マルチコンテキスト型動的再構成可能プロセッサへ時間制約を持つ実時間システムの機能モジュール群を分割し割り当てるためのアルゴリズムについて述べる.対象とするシステムを,時間制約を持つタスクグラフで表現し,それぞれのタスクをコンテキストに割り当てることでシステムの分割を実現する.本間題をコンテキストの最大サイズを最小化する整数線形計画問題(ILP)として定式化を行った.その際,解の品質を落とすことなくILP問題にするための様々な制約を考案した.また,大規模なタスク割当問題に対処できるよう,二段階のヒューリスティックアルゴリズムを考案し,いくつかの例題に適応した結果,最適解の1.1から1.3倍程度のサイズの分割結果を比較的短時間で導出できることが分かった. |
| 抄録(英) | In this paper, we formally define a task decomposition problem for multiple functional modules with timing constraints on a multi-context dynamic reconfigurable processor. We model a real-time system as a set of task graphs with timing constraints, and decompose their tasks by assigning each task to a suitable context of the processor. We formulate the task decomposition problem as an integer linear programming problem. In order to treat large sized decomposition problems, we propose a heuristic algorithm. We show that the proposed heuristic algorithm derives quasi-optical decomposition results for large sized examples in short time. |
| キーワード(和) | 実時間システム / 動的再構成可能プロセッサ / マルチコンテキスト / 整数線形計画法 / スケジューリング |
| キーワード(英) | real-time system / dynamic reconfigurable processor / multi-context / integer linear programming / scheduling |
| 資料番号 | CPSY2006-85,DC2006-99 |
| 発行日 |
| 研究会情報 | |
| 研究会 | DC |
|---|---|
| 開催期間 | 2007/3/9(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Dependable Computing (DC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 動的リコンフィギャラブルプロセッサへの時間制約付き機能モジュール群分割アルゴリズムの検討(DRP,FPGA,組込技術とネットワークに関するワークショップETNET2007) |
| サブタイトル（和） | |
| タイトル（英） | A Context Assignment Algorithm for Functional Modules with Timing Constraints on Dynamic Reconfigurable Processor |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 実時間システム / real-time system |
| キーワード(2)（和/英） | 動的再構成可能プロセッサ / dynamic reconfigurable processor |
| キーワード(3)（和/英） | マルチコンテキスト / multi-context |
| キーワード(4)（和/英） | 整数線形計画法 / integer linear programming |
| キーワード(5)（和/英） | スケジューリング / scheduling |
| 第 1 著者 氏名（和/英） | 木谷 友哉 / Tomoya KITANI |
| 第 1 著者 所属（和/英） | 奈良先端科学技術大学院大学情報科学研究科 Graduate School of Information Science, Nara Institute of Science and Techonology |
| 第 2 著者 氏名（和/英） | 中橋 亮 / Ryo NAKAHASHI |
| 第 2 著者 所属（和/英） | 大阪大学大学院情報科学研究科 Graduate School of Information Science and Technology, Osaka University |
| 第 3 著者 氏名（和/英） | 中田 明夫 / Akio NAKATA |
| 第 3 著者 所属（和/英） | 大阪大学大学院情報科学研究科 Graduate School of Information Science and Technology, Osaka University |
| 第 4 著者 氏名（和/英） | 安本 慶一 / Keiichi YASUMOTO |
| 第 4 著者 所属（和/英） | 奈良先端科学技術大学院大学情報科学研究科 Graduate School of Information Science, Nara Institute of Science and Techonology |
| 第 5 著者 氏名（和/英） | 東野 輝夫 / Teruo HIGASHINO |
| 第 5 著者 所属（和/英） | 大阪大学大学院情報科学研究科 Graduate School of Information Science and Technology, Osaka University |
| 発表年月日 | 2007/3/9 |
| 資料番号 | CPSY2006-85,DC2006-99 |
| 巻番号（vol） | vol.106 |
| 号番号（no） | 604 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |