Institute for Communication Technologies and Embedded Systems

logo: Institute for Communication Technologies and Embedded Systems

Force-Directed Scheduling for Data Flow Graph Mapping on Coarse-Grained Reconfigurable Architectures

Authors:
Fell, A. ,  Rákossy, Z. E. ,  Chattopadhyay, A.
Book Title:
International Conference on ReConFigurable Computing and FPGAs (ReConFig)
Publisher:
IEEE
Address:
Cancún, México
Date:
Dec. 2014
DOI:
10.1109/ReConFig.2014.7032519
Language:
English
Abstract:
Coarse-Grained ReconfigurableArchitectures (CGRA) are proven to be advantageous over fine-grained architectures, massively parallel GPUs and generic CPUs, in terms of energy and flexibility. However the key challenge of programmability is preventing wide-spread adoption. To exploit instruction level parallelism inherent to such architectures, optimal scheduling and mapping of algorithmic kernels is essential. Transforming an input algorithm in the form of a Data Flow Graph (DFG) into a CGRA schedule and mapping configuration is very challenging, due the necessity to consider architectural details such as memory bandwidth requirements, communication patterns, pipelining and heterogeneity to optimally extract maximum performance.
In this paper, an algorithm is proposed that employs Force-Directed Scheduling concepts to solve such scheduling and resource minimization problems. Our euristic extensions are flexible enough for generic heterogeneous CGRAs, allowing to estimate the execution time of an algorithm with different configurations, while maximizing the utilization of available hardware. Beside our experiments, we compare also given CGRA configurations intro-
duced by state-of-the-art mapping algorithms such as EPIMap, achieving optimal resource utilization by our schedule with a reduced overall DFG execution time by 39% on average.
Download:
BibTeX