Optimal Free-Space Management and Routing-Conscious Dynamic Placement   for Reconfigurable Devices
  We describe algorithmic results for two crucial aspects of allocating resources on computational hardware devices with partial reconfigurability. By using methods from the field of computational geometry, we derive a method that allows correct maintainance of free and occupied space of a set of n rectangular modules in optimal time Theta(n log n); previous approaches needed a time of O(n^2) for correct results and O(n) for heuristic results. We also show that finding an optimal feasible communication-conscious placement (which minimizes the total weighted Manhattan distance between the new module and existing demand points) can be computed in Theta(n log n). Both resulting algorithms are practically easy to implement and show convincing experimental behavior. 
Ali Ahmadinia, Christophe Bobda, Sandor Fekete, Juergen Teich, Jan van   der Veen