Optimal free-space management and routing-conscious dynamic placement for reconfigurable devices

Ahmadinia A, Bobda C, Fekete SP, Teich J, Van Der Veen JC (2007)

Publication Status: Published

Publication Type: Journal article, Original article

Publication year: 2007

Journal

IEEE Transactions on Computers Institute of Electrical and Electronics Engineers (IEEE)

Publisher: Institute of Electrical and Electronics Engineers (IEEE)

Book Volume: 56

Pages Range: 673-680

Journal Issue: 5

DOI: 10.1109/TC.2007.1028

Abstract

We describe algorithmic results on 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 maintenance of free and occupied space of a set of n rectangular modules in time O(n log n); previous approaches needed a time of O(n) for correct results and O(n) for heuristic results. We also show a matching lower bound of Ω(n log n), so our approach is optimal. 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 with Θ(n log n). Both resulting algorithms are practically easy to implement and show convincing experimental behavior. © 2007 IEEE.

Authors with CRIS profile

Jürgen Teich Lehrstuhl für Informatik 12 (Hardware-Software-Co-Design)

Related research project(s)

Optimization methodologies for reconfiguration management on reconfigurable hardware nodes (ReCoNodes) SPP 1148: Rekonfigurierbare Rechensysteme June 1, 2003 - May 31, 2009

Involved external institutions

Technische Universität Braunschweig

Germany (DE)

How to cite

APA:

Ahmadinia, A., Bobda, C., Fekete, S.P., Teich, J., & Van Der Veen, J.C. (2007). Optimal free-space management and routing-conscious dynamic placement for reconfigurable devices. IEEE Transactions on Computers, 56(5), 673-680. https://dx.doi.org/10.1109/TC.2007.1028

MLA:

Ahmadinia, Ali, et al. "Optimal free-space management and routing-conscious dynamic placement for reconfigurable devices." IEEE Transactions on Computers 56.5 (2007): 673-680.

BibTeX: Download