DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

TRAVERSAL: A Fast and Adaptive Graph-based Placement and Routing for CGRAs

Canesche, Michael and Menezes, Marcelo and Carvalho, Westerley and Sill Torres, Frank and Jamieson, Peter and Nacif, Jose Augusto and Ferreira, Ricardo (2020) TRAVERSAL: A Fast and Adaptive Graph-based Placement and Routing for CGRAs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. IEEE - Institute of Electrical and Electronics Engineers. doi: 10.1109/TCAD.2020.3025513. ISSN 0278-0070.

[img] PDF - Only accessible within DLR - Published version

Official URL: https://ieeexplore.ieee.org/document/9201522


Coarse Grain Reconfigurable Architectures (CGRAs) are an emerging hybrid computational architecture that has the parallel customization benefits of low-level logic devices such as FPGAs and ASICs, while the relative coarseness of these architectures makes CGRAs easier to design for, which is more similar to the traditional processor. In the process of mapping designs to CGRAs, flexible, fast, and adaptive Placement and Routing (P&R) is fundamental in order to implement efficient run-time reconfigurable frameworks. It is well-known that P&R is an NP-complete problem, and thus, solutions rely on heuristics to achieve quality results with acceptable execution times. CGRA P&R has different constraints compared to traditional VLSI P&R, e.g. path latency balancing and modulo scheduling of loops. In this work, we propose a graph-based P&R approach that uses graph traversals to map designs to CGRAs. Additionally, we parallelize our approach with a graph-based greedy heuristic that executes on a GPU. We compare our proposed P&R approach with the CGRA-ME framework, which implements Simulated Annealing and Integer Linear Programming placement algorithms. Our results show that this new approach can generate optimal mappings and improve the execution run-time up to several orders of magnitude. Furthermore, considering spatial mapping at the millisecond scale, our GPU approach is one order of magnitude faster compared to the state-of-the-art tool VPR.

Item URL in elib:https://elib.dlr.de/136268/
Document Type:Article
Title:TRAVERSAL: A Fast and Adaptive Graph-based Placement and Routing for CGRAs
AuthorsInstitution or Email of AuthorsAuthor's ORCID iD
Canesche, MichaelUNSPECIFIEDhttps://orcid.org/0000-0001-7882-0787
Menezes, MarceloUNSPECIFIEDhttps://orcid.org/0000-0002-8484-0941
Carvalho, WesterleyUNSPECIFIEDhttps://orcid.org/0000-0002-4030-4098
Sill Torres, FrankUNSPECIFIEDhttps://orcid.org/0000-0002-4028-455X
Jamieson, PeterUNSPECIFIEDhttps://orcid.org/0000-0002-3741-0201
Nacif, Jose AugustoUNSPECIFIEDhttps://orcid.org/0000-0003-0703-5620
Ferreira, RicardoUNSPECIFIEDhttps://orcid.org/0000-0003-1802-7829
Date:21 September 2020
Journal or Publication Title:IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Refereed publication:Yes
Open Access:No
Gold Open Access:No
In ISI Web of Science:Yes
Publisher:IEEE - Institute of Electrical and Electronics Engineers
Keywords:Computer architecture, Routing,Scheduling, Hardware, Simulated annealing
HGF - Research field:other
HGF - Program:other
HGF - Program Themes:other
DLR - Research area:no assignment
DLR - Program:no assignment
DLR - Research theme (Project):no assignment
Location: Bremerhaven
Institutes and Institutions:Institute for the Protection of Maritime Infrastructures > Reslience of Maritime Systems
Deposited By: Sill Torres, Frank
Deposited On:26 Oct 2020 09:36
Last Modified:26 Oct 2020 09:36

Repository Staff Only: item control page

Help & Contact
electronic library is running on EPrints 3.3.12
Website and database design: Copyright © German Aerospace Center (DLR). All rights reserved.