{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T16:54:54Z","timestamp":1781110494627,"version":"3.54.1"},"reference-count":25,"publisher":"IGI Global Scientific Publishing","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,10,1]]},"abstract":"<p>Partially reconfigurable field programmable gate arrays (FPGAs) can accommodate several independent tasks simultaneously. FPGA, as all reconfigurable chips, relies on the \u201chost-then-compact-when-needed\u201d strategy. Accordingly, it should have the ability to both place incoming tasks at run time and compact the chip whenever needed. Compaction is a proposed solution to alleviate external fragmentations problem, trying to move running tasks closer to each other in order to free a sufficient area for new tasks. However, compaction conditions the suspension of the running tasks, which introduces a high penalty. In order to increase the chip area utilization as well as not affecting the response times of tasks, efficient compaction techniques become increasingly important. Unfortunately, traditional compaction techniques suffer from a variety of faults. This paper introduces a novel Puzzle Based Compaction (PBC) technique that is a shape aware technique, which takes the tasks shapes into consideration. In this regard, it succeeded not only to eliminate the internal fragmentations but also to minimize the external fragmentations. This paper develops a novel formula, which is the first not to estimate, but to exactly calculate the amount of external fragmentations generated by accommodating a set of tasks inside the reconfigurable chip.<\/p>","DOI":"10.4018\/jaec.2010100103","type":"journal-article","created":{"date-parts":[[2011,2,15]],"date-time":"2011-02-15T16:00:48Z","timestamp":1297785648000},"page":"34-70","source":"Crossref","is-referenced-by-count":0,"title":["A Novel Puzzle Based Compaction (PBC) Strategy for Enhancing the Utilization of Reconfigurable Resources"],"prefix":"10.4018","volume":"1","author":[{"given":"Ahmed I.","family":"Saleh","sequence":"first","affiliation":[{"name":"Mansoura University, Egypt"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"2432","reference":[{"key":"jaec.2010100103-0","doi-asserted-by":"crossref","unstructured":"Banerjee, S., Bozorgzadeh, E., & Dutt, N. (2005). Physically-aware HW\u2013SW partitioning for reconfigurable architectures with partial dynamic reconfiguration. In Proceedings of the DAC (pp. 335-340).","DOI":"10.1145\/1065579.1065667"},{"key":"jaec.2010100103-1","doi-asserted-by":"crossref","unstructured":"Banerjee, S., Bozorgzadeh, E., & Dutt, N. (2005). Considering run-time reconfiguration overhead in task graph transformation for dynamically reconfigurable architectures. In Proceedings of the 13th Annual IEEE Symposium (FCCM) (pp. 273-274).","DOI":"10.1109\/FCCM.2005.28"},{"issue":"11","key":"jaec.2010100103-2","first-page":"1189","article-title":"Integrating physical constraints in HW\u2013SW partitioning for architectures with partial dynamic reconfiguration. IEEE Trans. Very Large Scale Integr. (VLSI)","volume":"14","author":"S.Banerjee","year":"2006","journal-title":"Syst."},{"key":"jaec.2010100103-3","doi-asserted-by":"publisher","DOI":"10.1109\/54.825678"},{"key":"jaec.2010100103-4","doi-asserted-by":"crossref","unstructured":"Chen, Y., & Hsiung, P. (2003). Hardware Task Scheduling and Placement in Operating Systems for Dynamically Reconfigurable SoC. In. Proceedings of the EUC (pp. 489-498).","DOI":"10.1007\/11596356_50"},{"key":"jaec.2010100103-5","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1049\/ip-cdt:20000485","article-title":"Dynamic Scheduling of Tasks on Partially Reconfigurable FPGAs","volume":"Vol. 147","author":"O.Diessel","year":"2000","journal-title":"Proceedings on computers and digital techniques"},{"key":"jaec.2010100103-6","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/s11227-007-0134-4","article-title":"Improving Utilization of Reconfigurable Resources Using Two-Dimensional Compaction.","volume":"42","author":"A.El Farag","year":"2007","journal-title":"International Journal of Super-Computing"},{"key":"jaec.2010100103-7","unstructured":"Fekete, S., Kohler, E., & Teich, J. (2001). Higher-dimensional packing with order constrains. In Proceedings of Algorithms and data structures (WADS 2001) (LNCS 2125, pp. 192-204). Berlin: Springer."},{"key":"jaec.2010100103-8","first-page":"658","article-title":"Optimal FPGA module placement with temporal precedence constrains","author":"S.Fekete","year":"2001","journal-title":"Proceedings of design automation and test in Europe"},{"key":"jaec.2010100103-9","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1030.0079"},{"key":"jaec.2010100103-10","unstructured":"Giani, M., Redaelli, M., Santambrogio, M., & Sciuto, D. (2007). Task partitioning for the scheduling on reconfigurable systems driven by specification self-similarity. In Proceedings of the Int. Conf. (ERSA) (pp. 78-84)."},{"key":"jaec.2010100103-11","doi-asserted-by":"crossref","unstructured":"Hanad, M., & Vemuri, R. (2004). An efficient algorithm for finding empty space for online FPGA placement. In Proceedigns of the Design automation conference, San Diego, CA (pp. 960-965).","DOI":"10.1145\/996566.996820"},{"key":"jaec.2010100103-12","doi-asserted-by":"publisher","DOI":"10.1109\/12.773796"},{"key":"jaec.2010100103-13","doi-asserted-by":"crossref","unstructured":"Marconi, T., Lu, Y., Bertels, K., & Gaydadjiev, G. (2008). Intelligent Merging Online Task Placement Algorithm for Partial Reconfigurable Systems. In Proceedings of DATE, Munich, Germany (pp. 1346-1351).","DOI":"10.1109\/DATE.2008.4484866"},{"key":"jaec.2010100103-14","doi-asserted-by":"crossref","unstructured":"Marconi, T., Lu, Y., Bertels, K., & Gaydadjiev, G. (2008). Online Hardware Task Scheduling and Placement Algorithm on Partially Reconfigurable Devices. In R. Woods, K. Compton, C. Bouganis, & P. C. Diniz (Eds.), Proceedings of the ARC 2008 (LNCS 4943, pp. 306-311).","DOI":"10.1007\/978-3-540-78610-8_33"},{"key":"jaec.2010100103-15","doi-asserted-by":"crossref","unstructured":"Marconi, T., Lu, Y., Bertels, K., & Gaydadjiev, G. (2009). A Novel Fast Online Placement Algorithm on 2D Partially Reconfigurable Devices. In Proceedings of the FPT (pp. 296-299).","DOI":"10.1109\/FPT.2009.5377661"},{"key":"jaec.2010100103-16","doi-asserted-by":"crossref","unstructured":"Resano, J., & Mozos, D. (2004). Specific scheduling support to minimize the reconfiguration overhead of dynamically reconfigurable hardware. In Proceedings of the DAC (pp. 119-124).","DOI":"10.1145\/996566.996604"},{"issue":"5","key":"jaec.2010100103-17","article-title":"Partitioning and Scheduling of Task Graphs on Partially Dynamically Reconfigurable FPGAs.","volume":"28","author":"C.Roberto","year":"2009","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"key":"jaec.2010100103-18","doi-asserted-by":"crossref","unstructured":"Steiger, C., Walder, H., & Platzner, M. (2003). Heuristics for Online Scheduling Real-Time Tasks to Partially Reconfigurable Devices. In Y. K. Cheung & G. A. Constantinides (Eds.), Proceedings of the FPL 2003 (LNCS 2778, pp. 575-584).","DOI":"10.1007\/978-3-540-45234-8_56"},{"key":"jaec.2010100103-19","unstructured":"Tabero, J., Septien, J., Mesha, H., Mozos, D., & Roman, S. (2003). Efficient hardware multitasking through space multiplexing in 2D RTR FPGAs. In Proceedings of the Euromicro digital system design conference."},{"key":"jaec.2010100103-20","doi-asserted-by":"crossref","unstructured":"Thomas, M., Yi, L., Koen, B., & Georgi, G. (2010). 3D Compaction: A Novel Blocking-Aware Algorithm for Online Hardware Task Scheduling and Placement on 2D Partially Reconfigurable Devices. In Proceedings of ARC 2010 (pp. 194-206). Berlin: Springer Verlag.","DOI":"10.1007\/978-3-642-12133-3_19"},{"key":"jaec.2010100103-21","unstructured":"Xilinx. (2007). Virtex-5 user guide (Tech. Rep. No. UG190). San Jose, CA: Xilinx Inc."},{"key":"jaec.2010100103-22","unstructured":"Xilinx. (2008). Virtex-4 FPGA Configuration User Guide (Tech. Rep. No. UG071). San Jose, CA: Xilinx."},{"key":"jaec.2010100103-23","first-page":"57","author":"X.Zhou","year":"2006","journal-title":"On-line Scheduling of Real-time Tasks for Reconfigurable Computing System"},{"key":"jaec.2010100103-24","first-page":"132","author":"X.Zhou","year":"2007","journal-title":"Fast On-line Task Placement and Scheduling on Reconfigurable Devices"}],"container-title":["International Journal of Applied Evolutionary Computation"],"original-title":[],"language":"ng","link":[{"URL":"https:\/\/www.igi-global.com\/viewtitle.aspx?TitleId=49136","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T15:50:55Z","timestamp":1654098655000},"score":1,"resource":{"primary":{"URL":"https:\/\/services.igi-global.com\/resolvedoi\/resolve.aspx?doi=10.4018\/jaec.2010100103"}},"subtitle":[""],"short-title":[],"issued":{"date-parts":[[2010,10,1]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,10]]}},"URL":"https:\/\/doi.org\/10.4018\/jaec.2010100103","relation":{},"ISSN":["1942-3594","1942-3608"],"issn-type":[{"value":"1942-3594","type":"print"},{"value":"1942-3608","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,10,1]]}}}