A Floorplanning Algorithm for Partially Reconfigurable FPGA in Wireless Sensor Network

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.