A Fast MER Enumeration Algorithm for Online Task Placement on Reconfigurable FPGAs

• PAN Tieyuan

  Graduate School of Information, Production and Systems, Waseda University

• ZENG Lian

  Graduate School of Information, Production and Systems, Waseda University

• TAKASHIMA Yasuhiro

  Faculty of Environmental Engineering, the University of Kitakyushu

• WATANABE Takahiro

  Graduate School of Information, Production and Systems, Waseda University

抄録

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.

収録刊行物

• IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E99.A (12), 2412-2424, 2016

  一般社団法人 電子情報通信学会

キーワード

• fast MER enumeration
• FPGAs
• low memory consumption

詳細情報

• CRID: 1390001206312158976
• NII論文ID: 130005170526
• DOI: 10.1587/transfun.e99.a.2412
• ISSN: 17451337
• ISSN: 09168508
• Web Site: https://www.jstage.jst.go.jp/article/transfun/E99.A/12/E99.A_2412/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可