AN EFFICIENT PLACEMENT ALGORITHM FOR RUN-TIME RECONFIGURABLE EMBEDDED SYSTEM

In the era of application convergence, the small handheld battery-powered portable devices are required to multiplex their limited hardware resources between many complex applications. Our first contribution in this paper is a modular and block based configuration architecture for modern FPGAs like Xilinx’s Virtex-4 and Virtex-5 devices, to increase multi-tasking capabilities, power savings and performance improvement of applications for mobile handsets. Our second contribution is an on-line placement algorithm based on bin packing, called Hierarchical Best Fit Ascending (HBFA) algorithm, which is more efficient than Best Fit (BF) algorithm for mapping a dynamic task list onto the FPGA. The overall time complexity of the proposed on-line placement algorithm, HBFA, is reduced to O(n) in comparison to the complexity of BF algorithm which is O(n 2). The placement solution provided by HBFA algorithm is also better than that of BF algorithm. KEY WORDS Reconfigurable computing, application convergence, task mapping