  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.
