A Novel Puzzle Based Compaction (PBC) Strategy for Enhancing the Utilization of Reconfigurable Resources

Partially reconfigurable field programmable gate arrays (FPGAs) can accommodate several independent tasks simultaneously. FPGA, as all reconfigurable chips, relies on the “host-then-compact-when-needed” 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.