Optimal Free-Space Management and Routing-Conscious Dynamic Placement for Reconfigurable Devices

Details Optimal Free-Space Management and Routing-Conscious Dynamic Placement for Reconfigurable Devices Optimal Free-Space Management and Routing-Conscious Dynamic Placement for Reconfigurable Devices

2004-06-18

arxiv.org/abs/cs/0406035v3

Computer Science

Data Structures and Algorithms

18 pages, 8 figures, 1, table; previous 5-page extended abstract appears in "International Conference on Field-Programmable Lo

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Optimal Free-Space Management and Routing-Conscious Dynamic Placement for Reconfigurable Devices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal Free-Space Management and Routing-Conscious Dynamic Placement for Reconfigurable Devices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Free-Space Management and Routing-Conscious Dynamic Placement for Reconfigurable Devices will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-203568