DMazerunner: Executing perfectly nested loops on dataflow accelerators

Shail Dave, Youngbin Kim, Sasikanth Avancha, Kyoungwoo Lee, Aviral Shrivastava

Research output: Contribution to journalArticlepeer-review

49 Scopus citations


Dataflow accelerators feature simplicity, programmability, and energy-efficiency and are visualized as a promising architecture for accelerating perfectly nested loops that dominate several important applications, including image and media processing and deep learning. Although numerous accelerator designs are being proposed, how to discover the most efficient way to execute the perfectly nested loop of an application onto computational and memory resources of a given dataflow accelerator (execution method) remains an essential and yet unsolved challenge. In this paper, we propose dMazeRunner - to efficiently and accurately explore the vast space of the different ways to spatiotemporally execute a perfectly nested loop on dataflow accelerators (execution methods). The novelty of dMazeRunner framework is in: i) a holistic representation of the loop nests, that can succinctly capture the various execution methods, ii) accurate energy and performance models that explicitly capture the computation and communication patterns, data movement, and data buffering of the different execution methods, and iii) drastic pruning of the vast search space by discarding invalid solutions and the solutions that lead to the same cost. Our experiments on various convolution layers (perfectly nested loops) of popular deep learning applications demonstrate that the solutions discovered by dMazeRunner are on average 9.16× better in Energy-Delay-Product (EDP) and 5.83× better in execution time, as compared to prior approaches. With additional pruning heuristics, dMazeRunner reduces the search time from days to seconds with a mere 2.56% increase in EDP, as compared to the optimal solution.

Original languageEnglish (US)
Article numbera70
JournalACM Transactions on Embedded Computing Systems
Issue number5s
StatePublished - Oct 2019


  • Analytical model
  • Coarse-grained reconfigurable array
  • Dataflow
  • Deep neural networks
  • Design space exploration
  • Energy-efficiency
  • Loop optimization
  • Mapping
  • Systolic arrays

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture


Dive into the research topics of 'DMazerunner: Executing perfectly nested loops on dataflow accelerators'. Together they form a unique fingerprint.

Cite this