講演抄録/キーワード |
講演名 |
2015-06-20 15:50
極大未使用矩形領域列挙による動的再構成デバイスでのオンラインタスク配置アルゴリズム ○潘 鉄源・朱 力・曾 濂・渡邊孝博(早大)・高島康裕(北九州市大) RECONF2015-26 |
抄録 |
(和) |
近年,製造技術の進歩に伴ない,組み込みシステムの複雑度が高まっている.その結果として,システムを実装したチップの性能だけでなく,実装できるシステムの柔軟性や動的な適応力も重要となっている.これらの要求に対して,動的再構成可能なデバイスが有力な解の一つとして注目されている.本稿では,動的再構成デバイスにおけるオンラインタスク配置の一手法を提案する.ここでは,各タスクがデバイス上の計算資源を矩形状に利用するという仮定の下,極大未使用矩形領域を効率的に列挙する手法を提案し,その結果を用いて,タスクの計算資源割り当てを高効率に決定する.そして,この手法の有効性を確認するため,計算量解析と計算機実装による評価実験を行なった.その結果,提案手法が既存手法と比較し,より高品質な資源割り当てが実現できることを確認した. |
(英) |
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 / / / / |
文献情報 |
信学技報, vol. 115, no. 109, RECONF2015-26, pp. 141-146, 2015年6月. |
資料番号 |
RECONF2015-26 |
発行日 |
2015-06-12 (RECONF) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
査読に ついて |
本技術報告は査読を経ていない技術報告であり,推敲を加えられていずれかの場に発表されることがあります. |
PDFダウンロード |
RECONF2015-26 |