Abstract
Floorplanning represents a critical step when dealing with Partially Reconfigurable (PR) designed Field Programmable Gate Array (FPGA) in Wireless Sensor Networks (WSNs). In the WSN, a task is always rejected by floorplanner when the free reconfigurable resources are enough but the shape is not matched, leading to high rejection rates and low utilization of resources. In this paper, we provide a novel algorithm named Best-Fit Duration and Transformation (BFDT) floorplanning to improve the performance of FPGA system. The main innovations of this paper are two folds. Firstly, to place tasks as many as possible and enhance the utilization of resources, we propose best-fit duration strategy based on the adhesion duration indicator, which keeps the positional relationship as long as possible between adjoining tasks. Secondly, we propose a task shape transformation method to allow some rejected tasks to be placed by changing their aspect ratio, therefore reduces the rejection rate. The BFDT performs very well in the simulation experiments with unknown task shapes and arriving times. Compared to the first-fit and best-fit algorithms, the BFDT reduces the rejection rate up to 22% and 13% in almost the same total execution time, which also holds a better resources utilization.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Wang, T., Li, Y., Wang, G., et al.: Sustainable and efficient data collection from WSNs to cloud. IEEE Trans. Sustainable Comput. pp(99), 1 (2017)
Vivado Design Suite User Guide: Partial Reconfiguration. http://www.xilinx.com. Accessed 11 Aug 2017
Garcia, R., Gordon-Ross, A., George, A.D.: Exploiting partially reconfigurable FPGAs for situation-based reconfiguration in wireless sensor networks. In: 17th IEEE Symposium on FCCM, pp. 243–246. IEEE, New York (2009)
Wang, T., Li, Y., Chen, Y., et al.: Fog-based evaluation approach for trustworthy communication in sensor-cloud system. IEEE Commun. Lett. pp(99), 1 (2017)
Reardon, C., Holland, B., George, A.D., et al.: RCML: an environment for estimation modeling of reconfigurable computing systems. ACM Trans. Embedded Comput. Syst. 11(S2), 43–64 (2012)
Rabozzi, M., Durelli, G.C., et al.: Floorplanning automation for partial-reconfigurable FPGAs via feasible placements generation. IEEE Trans. Very Large Scale Integr. Syst. 25(1), 151–164 (2017)
Bsoul, M., Manjikian, N., et al.: Reliability-and process variation-aware placement for FPGAs. In: Design, Automation and Test in Europe Conference and Exhibition 2010, DATE, pp. 1809–1814. IEEE, New York (2010)
Belaid, I., Muller, F., Benjemaa, M.: Off-line placement of hardware tasks on FPGA. In: Proceedings of the Field Programmable Logic and Applications 2009, FPL, pp. 591–595. IEEE, New York (2009)
Montone, A., Santambrogio, M.D., Sciuto, D., et al.: Placement and floorplanning in dynamically reconfigurable FPGAs. ACM Trans. Reconfigurable Technol. Syst. 3(4), 1–34 (2010)
Cheng, L., Wong, M.D.F.: Floorplan design for multi-million gate FPGAs. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 25(12), 292–299 (2004)
Nguyen, T.D., Kumar, A.: Prfloor: an automatic floorplanner for partially reconfigurable FPGA systems. In: Proceedings of the 2016 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, FPGA, pp. 149–158. ACM, New York (2016)
Wang, C., Wu, W., Nie, S., et al.: BFT: a placement algorithm for non-rectangle task model in reconfigurable computing system. Iet Comput. Digit. Tech. 10(3), 128–137 (2016)
Huang, M., Narayana, V.K., Simmler, H., et al.: Reconfiguration and communication-aware task scheduling for high-performance reconfigurable computing. ACM Trans. Reconfigurable Technol. Syst. 3(4), 20:1–20:25 (2010)
Wassi, G., Benkhelifa, M.E.A., et al.: Multi-shape tasks scheduling for online multitasking on FPGAs. In: 2014 International Symposium Reconfigurable and Communication-Centric Systems-on-Chip, pp. 1–7. IEEE, New York (2014)
Rabozzi, M., Lillis, J., et al.: Floorplanning for partially-reconfigurable FPGA systems via mixed-integer linear programming. In: 2014 22nd Annual International Symposium Field-Programmable Custom Computing Machines, pp. 186–193. IEEE, New York (2014)
Xilinx Virtex-5 FPGA User Guide. https://china.xilinx.com/support/documentation/user_guides/ug190.pdf. Accessed 16 Jan 2017
Acknowledgements
This work was supported by National Natural Science Foundation of China under Grant Nos. 61672423 and Natural Science Foundation of Shaanxi Province of China 2016SF-428. We are also grateful to Xilinx, Inc. for their support in ISE 14.6 integrated development environment in auto placement and route.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Wang, J., Wu, W., Qin, Z., Zhao, D. (2017). A Floorplanning Algorithm for Partially Reconfigurable FPGA in Wireless Sensor Network. In: Wang, G., Atiquzzaman, M., Yan, Z., Choo, KK. (eds) Security, Privacy, and Anonymity in Computation, Communication, and Storage. SpaCCS 2017. Lecture Notes in Computer Science(), vol 10658. Springer, Cham. https://doi.org/10.1007/978-3-319-72395-2_60
Download citation
DOI: https://doi.org/10.1007/978-3-319-72395-2_60
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-72394-5
Online ISBN: 978-3-319-72395-2
eBook Packages: Computer ScienceComputer Science (R0)