Article Preview
TopIntroduction
In spite of its flexible architecture and good internal arrangement, FPGA usually suffers from external fragmentations (Roberto, Francesco, Massimo, Marco, & Donatella, 2009). As several tasks enter and leave the chip, the chip area becomes fragmented into small islands, which are unable to host newly incoming tasks (Marconi, Lu, Bertels, & Gaydadjiev, 2008). This decreases the chip ability to host new tasks, which in turn harmly affects both the chip area utilization as well as the response times of running and waiting tasks (Giani, Redaelli, Santambrogio, & Sciuto, 2007) (Banerjee, Bozorgzadeh, & Dutt, 2005).
As illustrated in Figure 1, the chip is too fragmented to can host either task Tx or Ty. Hence, they are waiting in the ready queue despite there being available sufficient noncontiguous cells to host them. Accordingly, response times for those waiting tasks become longer and chip utilization is lower than it could be.
Figure 1. How external fragmentations affect the chip area
Generally, task arrangement in reconfigurable computing may be done in either offline or online scenarios (Banerjee, Bozorgzadeh, & Dutt, 2005). The offline scenario is similar to the traditional packing problem (Fekete, Kohler, & Teich, 2001) (Fekete & Schepers, 2004) where both tasks’ size as well as its service time are known in advance. Accordingly, an optimal or near optimal task arrangements could be derived. However, such scenario becomes obsolete with the rapid development in the area of reconfigurable computing. New applications have been emerged in which each task has an arrival time and size that are unknown in advance. Hence, tasks of those applications need to be scheduled online, while the task placement is not the issue (Resano & Mozos, 2004). The challenge is then to find sufficient contiguous cells for those newly incoming online tasks.
Online task arrangement may be either static or dynamic (Banerjee, Bozorgzadeh, & Dutt, 2006). The static behavior conditions the no-preemption of running tasks, and so, it does not offer task rearrangement (Jean, Tomko, Yavagal, Shah, & Cook, 1999; Fekete, Kohler, & Teich, 2001; Bazargan, Kastner, & Sarrafzadeh, 2000; Tabero, Septien, Mesha, Mozos, & Roman, 2003). On the other hand, the dynamic behavior for online task arrangement allows the scheduler to preempt the running tasks. Hence, preempted tasks can be rearranged to create a sufficient space for the incoming tasks when those new tasks have to wait. The process of task rearrangement, which aims to minimize the amount of external fragmentations (by making tasks closer to each others) is called the chip “compaction” (El Farag, Hatem, & Shaheen, 2007; Thomas, Yi, Koen, & Georgi, 2010).