IEICE TRANSACTIONS on Fundamentals
A Fast MER Enumeration Algorithm for Online Task Placement on Reconfigurable FPGAs
Summary :
In this paper, we propose a fast Maximal Empty Rectangle (MER) enumeration algorithm for online task placement on reconfigurable Field-Programmable Gate Arrays (FPGAs). On the assumption that each task utilizes rectangle-shaped resources, the proposed algorithm can manage the free space on FPGAs by an MER list. When assigning or removing a task, a series of MERs are selected and cut into segments according to the task and its assignment location. By processing these segments, the MER list can be updated quickly with low memory consumption. Under the proof of the upper limit of the number of the MERs on the FPGA, we analyze both the time and space complexity of the proposed algorithm. The efficiency of the proposed algorithm is verified by experiments.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E99-A No.12 pp.2412-2424
- Publication Date
- 2016/12/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E99.A.2412
- Type of Manuscript
- Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
- Category
Authors
Tieyuan PAN
Waseda University
Lian ZENG
Waseda University
Yasuhiro TAKASHIMA
the University of Kitakyushu
Takahiro WATANABE
Waseda University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Tieyuan PAN, Lian ZENG, Yasuhiro TAKASHIMA, Takahiro WATANABE, "A Fast MER Enumeration Algorithm for Online Task Placement on Reconfigurable FPGAs" in IEICE TRANSACTIONS on Fundamentals,
vol. E99-A, no. 12, pp. 2412-2424, December 2016, doi: 10.1587/transfun.E99.A.2412.
Abstract: In this paper, we propose a fast Maximal Empty Rectangle (MER) enumeration algorithm for online task placement on reconfigurable Field-Programmable Gate Arrays (FPGAs). On the assumption that each task utilizes rectangle-shaped resources, the proposed algorithm can manage the free space on FPGAs by an MER list. When assigning or removing a task, a series of MERs are selected and cut into segments according to the task and its assignment location. By processing these segments, the MER list can be updated quickly with low memory consumption. Under the proof of the upper limit of the number of the MERs on the FPGA, we analyze both the time and space complexity of the proposed algorithm. The efficiency of the proposed algorithm is verified by experiments.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E99.A.2412/_p
Copy
@ARTICLE{e99-a_12_2412,
author={Tieyuan PAN, Lian ZENG, Yasuhiro TAKASHIMA, Takahiro WATANABE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Fast MER Enumeration Algorithm for Online Task Placement on Reconfigurable FPGAs},
year={2016},
volume={E99-A},
number={12},
pages={2412-2424},
abstract={In this paper, we propose a fast Maximal Empty Rectangle (MER) enumeration algorithm for online task placement on reconfigurable Field-Programmable Gate Arrays (FPGAs). On the assumption that each task utilizes rectangle-shaped resources, the proposed algorithm can manage the free space on FPGAs by an MER list. When assigning or removing a task, a series of MERs are selected and cut into segments according to the task and its assignment location. By processing these segments, the MER list can be updated quickly with low memory consumption. Under the proof of the upper limit of the number of the MERs on the FPGA, we analyze both the time and space complexity of the proposed algorithm. The efficiency of the proposed algorithm is verified by experiments.},
keywords={},
doi={10.1587/transfun.E99.A.2412},
ISSN={1745-1337},
month={December},}
Copy
TY - JOUR
TI - A Fast MER Enumeration Algorithm for Online Task Placement on Reconfigurable FPGAs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2412
EP - 2424
AU - Tieyuan PAN
AU - Lian ZENG
AU - Yasuhiro TAKASHIMA
AU - Takahiro WATANABE
PY - 2016
DO - 10.1587/transfun.E99.A.2412
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E99-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2016
AB - In this paper, we propose a fast Maximal Empty Rectangle (MER) enumeration algorithm for online task placement on reconfigurable Field-Programmable Gate Arrays (FPGAs). On the assumption that each task utilizes rectangle-shaped resources, the proposed algorithm can manage the free space on FPGAs by an MER list. When assigning or removing a task, a series of MERs are selected and cut into segments according to the task and its assignment location. By processing these segments, the MER list can be updated quickly with low memory consumption. Under the proof of the upper limit of the number of the MERs on the FPGA, we analyze both the time and space complexity of the proposed algorithm. The efficiency of the proposed algorithm is verified by experiments.
ER -
English
