| 講演名 | 2015-06-20 極大未使用矩形領域列挙による動的再構成デバイスでのオンラインタスク配置アルゴリズム 潘 鉄源(早大), 朱 力(早大), 曾 濂(早大), 渡邊 孝博(早大), 高島 康裕(北九州市大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 近年，製造技術の進歩に伴ない，組み込みシステムの複雑度が高まっている．その結果として，システムを実装したチップの性能だけでなく，実装できるシステムの柔軟性や動的な適応力も重要となっている．これらの要求に対して，動的再構成可能なデバイスが有力な解の一つとして注目されている．本稿では，動的再構成デバイスにおけるオンラインタスク配置の一手法を提案する．ここでは，各タスクがデバイス上の計算資源を矩形状に利用するという仮定の下，極大未使用矩形領域を効率的に列挙する手法を提案し，その結果を用いて，タスクの計算資源割り当てを高効率に決定する．そして，この手法の有効性を確認するため，計算量解析と計算機実装による評価実験を行なった．その結果，提案手法が既存手法と比較し，より高品質な資源割り当てが実現できることを確認した． |
| 抄録(英) | Recently, due to the development of technology, the embedded application becomes more and more complex. Consequently, not only the performance of chips, but also the flexibility and dynamic adaptation of the implemented systems are required. To achieve these requirements, the partially reconfigurable device is promising. In this paper, we propose a novel online task placement algorithm based on the Maximal Empty Rectangle(MER) enumeration for partially reconfigurable device. On the assumption that each task utilizes the rectangle shaped resources, we propose a very simple but powerful algorithm to enumerate MERs. Then, by utilizing the result of MER enumeration, the fragmentation of the reconfigurable device can be reduced during task’s assignment. Finally, we analyze the complexity of the proposed algorithm and confirm its efficiency empirically |
| キーワード(和) | オンラインタスク配置 / 再構成可能なデバイス / 矩形領域列挙 / 高品質 / 資源割り当て |
| キーワード(英) | online task placement / reconfigurable device / MER enumeration / fragmentation reduction |
| 資料番号 | RECONF2015-26 |
| 発行日 | 2015-06-12 (RECONF) |
| 研究会情報 | |
| 研究会 | RECONF |
|---|---|
| 開催期間 | 2015/6/19(から2日開催) |
| 開催地（和） | 京都大学 |
| 開催地（英） | Kyoto University |
| テーマ（和） | 「十周年記念研究会」 リコンフィギャラブルシステム、一般 |
| テーマ（英） | the 10th anniversary celebration of RECONF: Reconfigurable Systems, etc. |
| 委員長氏名（和） | 渡邊 実(静岡大) |
| 委員長氏名（英） | Minoru Watanabe(Shizuoka Univ.) |
| 副委員長氏名（和） | 本村 真人(北大) / 柴田 裕一郎(長崎大) |
| 副委員長氏名（英） | Masato Motomura(Hokkaido Univ.) / Yuichiro Shibata(Nagasaki Univ.) |
| 幹事氏名（和） | 山田 裕(東芝) / 山口 佳樹(筑波大) |
| 幹事氏名（英） | Yutaka Yamada(Toshiba) / Yoshiki Yamaguchi(Univ. of Tsukuba) |
| 幹事補佐氏名（和） | 谷川 一哉(広島市大) / 三好 健文(イーツリーズ・ジャパン) |
| 幹事補佐氏名（英） | Kazuya Tanikagawa(Hiroshima City Univ.) / Takefumi Miyoshi(e-trees.Japan) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Reconfigurable Systems |
|---|---|
| 本文の言語 | ENG-JTITLE |
| タイトル（和） | 極大未使用矩形領域列挙による動的再構成デバイスでのオンラインタスク配置アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | An Online Task Placement Algorithm Based on MER Enumeration for Partially Reconfigurable Device |
| サブタイトル（和） | |
| キーワード(1)（和/英） | オンラインタスク配置 / online task placement |
| キーワード(2)（和/英） | 再構成可能なデバイス / reconfigurable device |
| キーワード(3)（和/英） | 矩形領域列挙 / MER enumeration |
| キーワード(4)（和/英） | 高品質 / fragmentation reduction |
| キーワード(5)（和/英） | 資源割り当て |
| 第 1 著者 氏名（和/英） | 潘 鉄源 / Tieyuan Pan |
| 第 1 著者 所属（和/英） | 早稲田大学(略称：早大) Waseda University(略称：Waseda Univ.) |
| 第 2 著者 氏名（和/英） | 朱 力 / Zhu Li |
| 第 2 著者 所属（和/英） | 早稲田大学(略称：早大) Waseda University(略称：Waseda Univ.) |
| 第 3 著者 氏名（和/英） | 曾 濂 / Lian Zeng |
| 第 3 著者 所属（和/英） | 早稲田大学(略称：早大) Waseda University(略称：Waseda Univ.) |
| 第 4 著者 氏名（和/英） | 渡邊 孝博 / Takahiro Watanabe |
| 第 4 著者 所属（和/英） | 早稲田大学(略称：早大) Waseda University(略称：Waseda Univ.) |
| 第 5 著者 氏名（和/英） | 高島 康裕 / Yasuhiro Takashima |
| 第 5 著者 所属（和/英） | 北九州市立大学(略称：北九州市大) University of Kitakyushu(略称：Univ. of Kitakyushu) |
| 発表年月日 | 2015-06-20 |
| 資料番号 | RECONF2015-26 |
| 巻番号（vol） | vol.115 |
| 号番号（no） | RECONF-109 |
| ページ範囲 | pp.141-146(RECONF), |
| ページ数 | 6 |
| 発行日 | 2015-06-12 (RECONF) |