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

Beitrag in einer Fachzeitschrift
(Originalarbeit)


Details zur Publikation

Autorinnen und Autoren: Ahmadinia A, Bobda C, Fekete SP, Teich J, Van Der Veen JC
Zeitschrift: IEEE Transactions on Computers
Verlag: Institute of Electrical and Electronics Engineers (IEEE)
Jahr der Veröffentlichung: 2007
Band: 56
Heftnummer: 5
Seitenbereich: 673-680
ISSN: 0018-9340


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.



FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Teich, Jürgen Prof. Dr.-Ing.
Lehrstuhl für Informatik 12 (Hardware-Software-Co-Design)


Einrichtungen weiterer Autorinnen und Autoren

Technische Universität Braunschweig


Zitierweisen

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: 

Zuletzt aktualisiert 2018-30-10 um 13:50