Run fast when you can: Loop pipelining with uncertain and non-uniform memory dependencies
File(s)
Accepted version
Author(s)
Liu, J
Wickerson, J
Bayliss, S
Constantinides, GA
Type
Conference Paper
Abstract
As a key optimisation method in high-level synthesis (HLS), high-performance loop pipelining is enabled by the static scheduling algorithm. When there are non-trivial memory dependencies in the loop, current HLS tools have to apply conservative pipeline schedule that also leads to nearly sequential execution. In this paper, we demonstrate using parametric polyhedral model to mathematically capture uncertain (i.e., parameterised by an undetermined variable) and/or non-uniform (i.e., varying between loop iterations) memory dependence patterns. According to this static analysis, if we always execute the loop with an aggressive (fast) pipeline schedule, we can generate the parameter conditions in which this execution is safe and the parametric break points when the execution encounters memory conflicts. Then, we apply these information into an automated source-to-source code transformation, which implements parametric loop pipelining and loop splitting. The transformed loop is synthesised by Vivado HLS and its execution speed can be adjusted at runtime to avoid memory conflicts. The experiments over a set of benchmark loops show that our optimisation can improve the runtime pipeline performance significantly with a reasonable overhead of hardware resources.
Date Issued
2018-04-16
Date Acceptance
2017-11-27
Citation
2017 51st Asilomar Conference on Signals, Systems, and Computers, 2018
ISBN
9781538618240
ISSN
2576-2303
Publisher
IEEE
Journal / Book Title
2017 51st Asilomar Conference on Signals, Systems, and Computers
Copyright Statement
© 2018 The Authors.
Sponsor
Engineering & Physical Science Research Council (E
Royal Academy Of Engineering
Imagination Technologies Ltd
Engineering & Physical Science Research Council (EPSRC)
Grant Number
11908 (EP/K034448/1)
Prof Constantinides Chair
Prof Constantinides Chair
EP/P010040/1
Source
52nd Annual Asilomar Conference on Signals, Systems, and Computers
Subjects
Science & Technology
Technology
Computer Science, Information Systems
Engineering, Electrical & Electronic
Telecommunications
Computer Science
Engineering
Publication Status
Published
Start Date
2018-10-28
Finish Date
2018-11-01
Coverage Spatial
Pacific Grove, California, USA
Date Publish Online
2018-04-16