An Online Task Placement Algorithm Based on MER Enumeration for Partially Reconfigurable Device

Tieyuan PAN  Li ZHU  Lian ZENG  Takahiro WATANABE  Yasuhiro TAKASHIMA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A   No.7   pp.1345-1354
Publication Date: 2016/07/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E99.A.1345
Type of Manuscript: Special Section PAPER (Special Section on Design Methodologies for System on a Chip)
Category: 
Keyword: 
online task placement,  reconfigurable device,  efficient data structure,  MER enumeration,  

Full Text: PDF>>
Buy this Article



Summary: 
Recently, due to the development of design and manufacturing technologies for VLSI systems, an embedded system 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, a partially reconfigurable device is promising. In this paper, we propose an efficient data structure to manage the reconfigurable units. And then, on the assumption that each task utilizes the rectangle shaped resources, a very simple MER enumeration algorithm based on this data structure is proposed. By utilizing the result of MER enumeration, the free space on the reconfigurable device can be used sufficiently. We analyze the complexity of the proposed algorithm and confirm its efficiency by experiments.