An efficient algorithm for finding empty space for online FPGA placement

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.

REFERENCES

• 1: Manuel G. Gericota , Gustavo R. Alves , Miguel L. Silva , Jose M. Ferreira, Run-Time Management of Logic Resources on Reconfigurable Systems, Proceedings of the conference on Design, Automation and Test in Europe, p.10974, March 03-07, 2003
• 2: 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.
• 3: 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.
• 4: M. Orlowski. A New Algorithm for the Largest Empty Rectangle. In Algorithmica, volume 5, pages 65--73, 1990.
• 5: Jeff Edmonds , Jarek Gryz , Dongming Liang , Renée J. Miller, Mining for empty spaces in large data sets, Theoretical Computer Science, v.296 n.3, p.435-452, 14 March 2003 [doi>10.1016/S0304-3975(02)00738-7]
• 6: Kiarash Bazargan , Ryan Kastner , Majid Sarrafzadeh, Fast Template Placement for Reconfigurable Computing Systems, IEEE Design & Test, v.17 n.1, p.68-83, January 2000 [doi>10.1109/54.825678]
• 7: Herbert Walder , Christoph Steiger , Marco Platzner, Fast Online Task Placement on FPGAs: Free Space Partitioning and 2D-Hashing, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.178.2, April 22-26, 2003
• 8: A. Aggarwal , S. Suri, Fast algorithms for computing the largest empty rectangle, Proceedings of the third annual symposium on Computational geometry, p.278-290, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41988]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design

Keywords:
online placement, partially reconfigurable FPGAs, reconfigurable computing