Partially reconfigurable field-programmable gate arrays (FPGAs) allow parts of the chip to be configured at run-time where each part could hold an independent task. Online placement of these tasks result in area fragmentation leading to poor utilization of chip resources. In this paper, we propose a new metric for measuring area fragmentation. The new fragmentation metric gives an indication to the continuity of the occupied (or free) space and not the amount of occupied space. We show how this metric can be extended for multi-dimensional structures. We also show how this metric can be computed efficiently at run time. Next we use this measure during online placement of tasks on FPGAs, such that the chip fragmentation is reduced. Our results show improvement of chip utilization when using this fragmentation aware placement method over other placement methods with well known bottom left first fit, and best fit placement strategies. In real time environment, we achieve an improvement in miss ratio when using the fragmentation aware placement over the bottom left placement strategy.

Although algorithms that employ dynamic reconfiguration are extremely fast, they need the underlying architecture to change structure very rapidly, possibly at each step of the computation. This increases the power requirement of such algorithms which is not acceptable in nowadays devices that strive to reduce the power requirements. This paper deals with the circuit switched tree (CST), an interconnect used to implement dynamically reconfigurable architectures. In this paper, we introduce a new technique called power aware dynamic reconfiguration (PADR). Under this technique, we propose a power-aware algorithm for configuring the CST and scheduling a class of communications, called the well-nested communications on the CST. We show that the algorithm is power optimal. The algorithm requires only local information at processing elements (PEs), yet it correctly establishes paths between communicating PEs. We also show that the algorithm is optimal and efficient.