{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,21]],"date-time":"2023-12-21T19:37:59Z","timestamp":1703187479569},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["TE 163\/13-2TE 163\/13-3","TE 163\/14-2TE 163\/14-3","FE 407\/8-2FE 407\/8-3"],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"publisher","award":["03FE-PAI2"],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Reconfigurable Technol. Syst."],"published-print":{"date-parts":[[2012,6]]},"abstract":"We propose a new method for defragmenting the module layout of a reconfigurable device, enabled by a novel approach for dealing with communication needs between relocated modules and with inhomogeneities found in commonly used FPGAs. Our method is based on dynamic relocation of module positions during runtime, with only very little reconfiguration overhead; the objective is to maximize the length of contiguous free space that is available for new modules. We describe a number of algorithmic aspects of good defragmentation, and present an optimization method based on tabu search. Experimental results indicate that we can improve the quality of module layout by roughly 50% over the static layout. Among other benefits, this improvement avoids unnecessary rejections of modules.<\/jats:p>","DOI":"10.1145\/2209285.2209287","type":"journal-article","created":{"date-parts":[[2012,6,15]],"date-time":"2012-06-15T15:31:37Z","timestamp":1339774297000},"page":"1-20","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Dynamic Defragmentation of Reconfigurable Devices"],"prefix":"10.1145","volume":"5","author":[{"given":"S\u00e1ndor P.","family":"Fekete","sequence":"first","affiliation":[{"name":"Braunschweig University of Technology"}]},{"given":"Tom","family":"Kamphans","sequence":"additional","affiliation":[{"name":"Braunschweig University of Technology"}]},{"given":"Nils","family":"Schweer","sequence":"additional","affiliation":[{"name":"Braunschweig University of Technology"}]},{"given":"Christopher","family":"Tessars","sequence":"additional","affiliation":[{"name":"Braunschweig University of Technology"}]},{"given":"Jan C.","family":"van der Veen","sequence":"additional","affiliation":[{"name":"Braunschweig University of Technology"}]},{"given":"Josef","family":"Angermeier","sequence":"additional","affiliation":[{"name":"University of Erlangen-Nuremberg"}]},{"given":"Dirk","family":"Koch","sequence":"additional","affiliation":[{"name":"University of Erlangen-Nuremberg"}]},{"given":"J\u00fcrgen","family":"Teich","sequence":"additional","affiliation":[{"name":"University of Erlangen-Nuremberg"}]}],"member":"320","published-online":{"date-parts":[[2012,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM.2007.29"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Behnen K. and Neuhaus G. 1995. Grundkurs Stochastik 3rd Ed. B. G. Teubner-Verlag. Behnen K. and Neuhaus G. 1995. Grundkurs Stochastik 3rd Ed. B. G. Teubner-Verlag.","DOI":"10.1007\/978-3-663-10214-4"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701389956"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1074009"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288539"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2002.1043324"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the International Conference on Field Programmable Logic and Applications. 113--118","author":"Fekete S. P.","unstructured":"Fekete , S. P. , Kamphans , T. , Schweer , N. , Tessars , C. , van der Veen , J. C. , Angermeier , J. , Koch , D. , and Teich , J . 2008. No-Break dynamic defragmentation of reconfigurable devices . In Proceedings of the International Conference on Field Programmable Logic and Applications. 113--118 . Fekete, S. P., Kamphans, T., Schweer, N., Tessars, C., van der Veen, J. C., Angermeier, J., Koch, D., and Teich, J. 2008. No-Break dynamic defragmentation of reconfigurable devices. In Proceedings of the International Conference on Field Programmable Logic and Applications. 113--118."},{"key":"e_1_2_1_8_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_2_1_9_1","unstructured":"Gericota M. G. Alves G. R. Silva M. L. and Ferreira J. M. 2005. Run-Time defragmentation for dynamically reconfigurable hardware. In New Algorithms Architectures and Applications for Reconfigurable Computing. Gericota M. G. Alves G. R. Silva M. L. and Ferreira J. M. 2005. Run-Time defragmentation for dynamically reconfigurable hardware. In New Algorithms Architectures and Applications for Reconfigurable Computing."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/360715.360752"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/362375.362392"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/365628.365655"},{"key":"e_1_2_1_13_1","volume-title":"The Art of Computer Programming: Fundamental Algorithms","author":"Knuth D. E.","unstructured":"Knuth , D. E. 1997. The Art of Computer Programming: Fundamental Algorithms 3 rd Ed. Vol. 1 . Addison-Wesley , Reading, MA . Knuth, D. E. 1997. The Art of Computer Programming: Fundamental Algorithms 3rd Ed. Vol. 1. Addison-Wesley, Reading, MA.","edition":"3"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the IEEE International Conference on Field Programmable Technology. 433--436","author":"Koch D.","unstructured":"Koch , D. , Ahmadinia , A. , Bobda , C. , and Kalte , H . 2004. FPGA architecture extensions for preemptive multitasking and hardware defragmentation . In Proceedings of the IEEE International Conference on Field Programmable Technology. 433--436 . Koch, D., Ahmadinia, A., Bobda, C., and Kalte, H. 2004. FPGA architecture extensions for preemptive multitasking and hardware defragmentation. In Proceedings of the IEEE International Conference on Field Programmable Technology. 433--436."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1216919.1216950"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 18th International Conference on Field Programmable Logic and Applications. 119--124","author":"Koch D.","unstructured":"Koch , D. , Beckhoff , C. , and Teich , J . 2008a. ReCoBusBuilder: A novel tool and technique to build static and dynamically reconfigurable systems for fpgas . In Proceedings of the 18th International Conference on Field Programmable Logic and Applications. 119--124 . Koch, D., Beckhoff, C., and Teich, J. 2008a. ReCoBusBuilder: A novel tool and technique to build static and dynamically reconfigurable systems for fpgas. In Proceedings of the 18th International Conference on Field Programmable Logic and Applications. 119--124."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM.2008.33"},{"key":"e_1_2_1_18_1","first-page":"41","article-title":"Defragmentation algorithms for partially reconfigurable hardware","volume":"240","author":"Koester M.","year":"2007","unstructured":"Koester , M. , Kalte , H. , Porrmann , M. , and Ruckert , U. 2007 . Defragmentation algorithms for partially reconfigurable hardware . Int. Fed. Inf. Proc. Publ. 240 , 41 . Koester, M., Kalte, H., Porrmann, M., and Ruckert, U. 2007. Defragmentation algorithms for partially reconfigurable hardware. Int. Fed. Inf. Proc. Publ. 240, 41.","journal-title":"Int. Fed. Inf. Proc. Publ."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2006.884574"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 16th International Conference on Field Programmable Logic and Applications. 1--6.","author":"Lysaght P.","unstructured":"Lysaght , P. , Blodget , B. , Mason , J. , Young , J. , and Bridgford , B . 2006. Invited paper: Enhanced architecture, design methodologies and CAD tools for dynamic reconfiguration of Xilinx fpgas . In Proceedings of the 16th International Conference on Field Programmable Logic and Applications. 1--6. Lysaght, P., Blodget, B., Mason, J., Young, J., and Bridgford, B. 2006. Invited paper: Enhanced architecture, design methodologies and CAD tools for dynamic reconfiguration of Xilinx fpgas. In Proceedings of the 16th International Conference on Field Programmable Logic and Applications. 1--6."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/355620.361164"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the International Workshop on Memory Management, H. Baker Ed. Lecture Notes in Computer Science","volume":"986","author":"Wilson P. R.","unstructured":"Wilson , P. R. , Johnstone , M. S. , Neely , M. , and Boles , D . 1995. Dynamic storage allocation: A survey and critical review . In Proceedings of the International Workshop on Memory Management, H. Baker Ed. Lecture Notes in Computer Science , vol. 986 . Springer. Wilson, P. R., Johnstone, M. S., Neely, M., and Boles, D. 1995. Dynamic storage allocation: A survey and critical review. In Proceedings of the International Workshop on Memory Management, H. Baker Ed. Lecture Notes in Computer Science, vol. 986. Springer."}],"container-title":["ACM Transactions on Reconfigurable Technology and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2209285.2209287","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,30]],"date-time":"2022-12-30T09:30:40Z","timestamp":1672392640000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2209285.2209287"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["10.1145\/2209285.2209287"],"URL":"https:\/\/doi.org\/10.1145\/2209285.2209287","relation":{},"ISSN":["1936-7406","1936-7414"],"issn-type":[{"value":"1936-7406","type":"print"},{"value":"1936-7414","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,6]]},"assertion":[{"value":"2010-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}