Manish Handa
ABSTRACT
A fast and efficient algorithm for finding empty area is necessary for online placement, task relocation and defragmentation on a partially reconfigurable FPGA. We present an algorithm that finds empty area as a list of overlapping maximal rectangles. Using an innovative representation of the FPGA, we are able to predict possible locations of the maximal empty rectangles. Worst-case time complexity of our algorithm is O(xy) where x is the number of columns, y is the number of rows and x.y is the total number of cells on the FPGA. Experiments show that, in practice, our algorithm needs to scan less than 15% of the FPGA cells to make a list of all maximal empty rectangles.
- M. Gericota, G. Alves, M. Silva, and J. Ferreira. Run-Time Management of Logic Resources on Reconfigurable Systems. In Proc. of Design, Automation and Test in Europe, Mar. 2003. Google Scholar
Digital Library
- M. Handa and R. Vemuri. Area Fragmentation in Reconfigurable Operating Systems. In Proc. of the International Conference on Engineering of Reconfigurable Systems and Algorithms. CSREA Press, Jun. 2004.Google Scholar
- P. Healy and M. Creavin. An Optimal Algorithm for Rectangle Placement. In Technical Report UL-CSIS-97-1. Dept. of Computer Science and Information Systems, University of Limerick, Limerick, Ireland, 1997.Google Scholar
- M. Orlowski. A New Algorithm for the Largest Empty Rectangle. In Algorithmica, volume 5, pages 65--73, 1990.Google ScholarCross Ref
- J. Edmonds, J. Gryz, D. Liang, and R. J. Miller. Mining for Empty Spaces in Large Data Sets. In Theoretical Computer Science, volume 296(3), pages 435--452. Else-vier Science Publishers Ltd., 2003. Google ScholarDigital Library
- K. Bazargan, R. Kastner, and M. Sarrafzadeh. Fast Template Placement for Reconfigurable Computing Systems. In IEEE Design and Test of computers- Special Issue on Reconfigurable Computing, volume 17(1), pages 68--83, Jan.-Mar. 2000. Google ScholarDigital Library
- H. Walder, C. Steiger, and M. Platzner. Fast Online Task Placement on FPGAs: Free Space Partitioning and 2D-Hashing . In Proc. of International Parallel and Distributed Processing Symposium (IPDPS'03), Apr. 2003. Google ScholarDigital Library
- A. Aggarwal and S. Suri. Fast Algorithms for Computing the Largest Empty Rectangle. In Proceedings of the third annual symposium on Computational geometry, pages 278--290, Jun. 1987. Google ScholarDigital Library
Index Terms
- An efficient algorithm for finding empty space for online FPGA placement
Recommendations
An Efficient and Effective Algorithm for Online Task Placement with I/O Communications in Partially Reconfigurable FPGAs
In a partially reconfigurable FPGA of the future, arbitrary portions of its logic resources and interconnection networks will be reconfigured without affecting the other parts. Multiple tasks will be mapped and executed concurrently in such an FPGA. ...
Hardware accelerated FPGA placement
A key advantage of field-programmable gate arrays (FPGAs) over full-custom and semi-custom devices is that they provide relatively quick implementation from concept to physical realization. However, as modern FPGAs reach close to one million logic ...
A Novel Approach for Finding Candidate Locations for Online FPGA Placement
CIT '10: Proceedings of the 2010 10th IEEE International Conference on Computer and Information TechnologyReconfigurable computing (RC) has been viewed as an efficient solution to achieve high performance and flexibility. Hardware tasks can be dynamically placed on and removed from reconfigurable platforms. Field-programmable gate arrays (FPGA) provide ...
Comments