Maximal strips data structure to represent free space on partially reconfigurable FPGAs

References

• A. Ahmadinia, C. Bobda, M. Bednara, and J. Teich, A new approach for on-line placement on reconfigurable devices, Proceedings of the 2004 Reconfigurable Architectures Workshop (2004)
   Google Scholar
• Ahmadinia , A. , Bobda , C. and Teich , J. 2003 . Temporal task clustering for online placement on reconfigurable hardware . : 359 – 362 . Proceedings of the IEEE International Conference on Field Programmable Technology
   Google Scholar
• Bazargan , K. , Kastner , R. and Sarrafzadeh , M. 2000 . Fast template placement for reconfigurable computing systems . IEEE Des. Test Comput. , 17 : 68 – 83 .
   Google Scholar
• Becker , J. , Hübner , M. , Hettich , G. , Constapel , R. , Eisenmann , J. and Luka , J. 2007 . Dynamic and partial FPGA exploitation . Proc. IEEE , 95 : 438 – 452 .
   Google Scholar
• Chiu , G.-M. and Chen , S.-K. 1999 . An efficient submesh allocation scheme for two-dimensional meshes with little overhead . IEEE Trans. Parall. Distr. Syst. , 10 : 471 – 486 .
   Web of Science ®Google Scholar
• Cormen , T.H. , Leiserson , C.E. , Rivest , R.L. and Stein , C. 2001 . Introduction to Algorithms , 2nd ed. , Boston, MA : McGraw-Hill .
   Google Scholar
• J. Cui, Q. Deng, X. He, and Z. Gu, An efficient algorithm for online management of 2D area of partially reconfigurable FPGAs, Proceedings of the Conference on Design Automation and Test in Europe (2007)
   Google Scholar
• Datta , A. 1992 . Efficient algorithms for the largest rectangle problem . Inform. Sci. , 64 : 121 – 141 .
   Google Scholar
• O. Diessel and G. Wigley, Opportunities for operating systems research in reconfigurable computing, Technical Report ACRC-99-018, School of Computer and Information Science, University of South Australia (1999)
   Google Scholar
• Edmonds , J. , Gryz , J. , Liang , D. and Mille , R.J. 2003 . Mining for empty spaces in large data sets . Theor. Comput. Sci. , 296 : 435 – 452 .
   Google Scholar
• A.A. ElFarag, H.M. El-Boghdadi, and S.I. Shaheen, Miss ratio improvement for real-time applications using fragmentation-aware placement, Proceedings of the 2007 Reconfigurable Architectures Workshop (2007)
   Google Scholar
• Handa , M. and Vemuri , R. 2004 . An efficient algorithm for finding empty space for online FPGA placement . : 960 – 965 . Proceedings of the 41st Design Automation Conference
   Google Scholar
• Naamad , A. , Lee , D.T. and Hsu , W.-L. 1984 . On the maximum empty rectangle problem . Discr. Appl. Math. , 8 : 267 – 277 .
   Google Scholar
• Nandy , S.C. , Bhattacharya , B.B. and Ray , S. 1990 . Efficient algorithms for identifying all maximal isothetic empty rectangles in VLSI layout design . : 255 – 269 . Proceedings of the 10th Conference on Foundations of Software Technology and Theoretical Computer Science (Lecture Notes in Computer Science #472)
   Google Scholar
• Orlowski , M. 1990 . A new algorithm for the largest empty rectangle problem . Algorithmica , 5 : 65 – 73 .
   Google Scholar
• Sedcole , P. , Blodget , B. , Becker , T. , Anderson , J. and Lysaght , P. 2006 . Modular dynamic reconfiguration in virtex FPGAs . IEE Proc. Comput. Dig. Tech. , 153 : 157 – 164 .
   Google Scholar
• Steiger , C. , Walder , H. and Platzner , M. 2004 . Operating systems for reconfigurable embedded platforms: Online scheduling of real-time tasks . IEEE Trans. Comput. , 53 : 1393 – 1407 .
   Web of Science ®Google Scholar
• C. Steiger, H. Walder, M. Platzner, and L. Thiele, Online scheduling and placement of real-time tasks to partially reconfigurable devices, Proceedings of the Real-time Systems Symposium (2003)
   Google Scholar
• Tabero , J. , Mecha , H. , Septién , S. , Román , S. and Mozos , D. 2003 . A vertex-list approach to 2D HW multitasking management in RTR FPGAs . : 545 – 550 . Proceedings of the Design of Circuits and Integrated Systems Conference
   Google Scholar
• H. Walder and M. Platzner, Reconfigurable hardware operating systems: From design concepts to realizations, Proceedings of the International Conference on Engineering of Reconfigurable Systems and Algorithms (2003)
   Google Scholar
• Walder , H. and Platzner , M. 2003 . Online scheduling for block-partitioned reconfigurable devices . : 290 – 295 . Proceedings of the Design Automation and Test in Europe
   Google Scholar
• H. Walder, C. Steiger, and M. Platzner, Fast online task placement on FPGAs: Free space partitioning and 2D-hashing, Proceedings of the Reconfigurable Architectures Workshop (2003)
   Google Scholar
• Zhou , X.-G. , Wang , Y. , Huang , X.-Z. and Peng , C.-L. 2006 . On-line scheduling of real-time tasks for reconfigurable computing system . : 57 – 64 . Proceedings of the IEEE International Conference on Field Programmable Technology
   Google Scholar