OrderMap: A CGRA Mapping Algorithm based on DFG Analysis and Graph Homomorphism
Authors:
- 25 October 2022
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-3
Abstract
Coarse-grained reconfigurable architecture (CGRA) accelerator is a promising solution in fields such as deep learning and edge computing. One of the difficult problems to design the accelerator is to map the data flow graph (DFG) to the architecture efficiently. The previous mapping algorithms based on graph structure mainly focus on optimization during the placement and routing stage, which may fall into a local minimum and lead to an increase in initiation interval (II). We propose a CGRA mapping algorithm, OrderMap, based on DFG analysis and graph homomorphism. It analyzes the DFG structure information to decide the node mapping order, followed by placement, and routing. Experimental results show that our algorithm is faster than CGRA-ME with smaller IIs. Compared with FastCGRA based on the depth-first order, OrderMap is 22.3 × faster with the same mapping results.Keywords
Funding Information
- National Natural Science Foundation of China
This publication has 6 references indexed in Scilit:
- PathSeeker: A Fast Mapping Algorithm for CGRAs2022
- FastCGRA: A Modeling, Evaluation, and Exploration Platform for Large-Scale Coarse-Grained Reconfigurable Arrays2021
- A Survey of Coarse-Grained Reconfigurable Architecture and DesignACM Computing Surveys, 2019
- Generic Connectivity-Based CGRA Mapping via Integer Linear Programming2019
- MAERIACM SIGPLAN Notices, 2018
- Graph minor approach for application mapping on CGRAs2012