Finding Free Space for Task Placement on Reconfigurable Devices


Article Preview

In this paper, an approach of free space management for FPGA area is proposed. We present a data structure for keeping the information of free space and an algorithm for finding available location to fit the tasks. The simulation proves that the algorithm has higher placement quality and lower complexity than the existed algorithm with certain circumstances.



Edited by:

Linli Xu, Wenya Tian and Elwin Mao




J. F. Zhang and X. Chen, "Finding Free Space for Task Placement on Reconfigurable Devices", Applied Mechanics and Materials, Vols. 80-81, pp. 1226-1231, 2011

Online since:

July 2011




[1] K. Bazargan, R. Kastner, M. Sarrafzadeh, Fast Template Placement for Reconfigurable Computing Systems, IEEE Design & Test of Computers 17 (2000) 68–83.


[2] W. Hu, C. Wang, J.L. Ma, T.Z. Chen, D. Chen, A Novel Approach for Finding Candidate Locations for Online FPGA Placement, Proc. IEEE 10th Int'l Conf. on Computer and Information Technology (CIT 2010) (2010) 2509-2515.


[3] H. Walder, C. Steiger, M. Platzner, Fast Online Task Placement on FPGAs: Free Space Partitioning and 2D-Hashing, Proc. Parallel and Distributed Processing Symposium (2003) 178-186.


[4] M. Handa, V. Ranga, An efficient algorithm for finding empty space for online FPGA placement, Proc. the 41st Conf. on Design automation San Diego CA USA (2004) 960 - 965.


[5] J. Cui, Q. Deng, X. He, et al., An efficient algorithm for online management of 2D area of partially reconfigurable FPGAs, Proc. Conf. on Design, automation and test in Europe. Nice France (2007) 1 – 6.


[6] Y. Lui, T. Marconi, G. Gaydadjiev, et al., An efficient algorithm for free resources management on the FPGA, Proc. Conf. on Design, automation and test in Europe. Munich Germany (2008) 1095 – 1098.


[7] Jesús Tabero, Julio Septién, Hortensia Mecha, Daniel Mozos, Task Placement Heuristic Based on 3D-Adjacency and Look-Ahead in Reconfigurable Systems, Proceedings of the ASP-DAC (2006) 396-401.