Dynamic inter-block scheduling for HLS
File(s)
Accepted version
Author(s)
Cheng, Jianyi
Josipovic, Lana
Constantinides, George
Wickerson, John
Type
Conference Paper
Abstract
A recent theme in HLS research is the production
of dynamically scheduled circuits, which are made up of components that use handshaking to schedule themselves at run
time, as opposed to following a schedule determined statically at
compile time. Dynamically scheduled circuits promise superior
performance on ‘irregular’ source programs, such as those whose
control flow depends on input data, at the cost of additional area.
Current dynamic scheduling techniques are well able to
exploit parallelism among instructions within each basic block
(BB) of the source program, but parallelism between BBs is
underexplored. Although current tools allow the operations of
different BBs to overlap, they require the BBs to start in strict
program order, thus limiting the achievable parallelism and
overall performance.
We seek to lift this restriction. Doing so involves developing a
toolflow that tackles the following challenges: (1) finding consecutive subgraphs in the control-flow graph and using static analysis
to identify those subgraphs that can be safely parallelised, and
(2) adapting the circuit so that those subgraphs are executed
in parallel while ensuring deterministic circuit behaviour and
correct usage of memory interfaces.
Using two benchmark sets from related works, we compare
our proposed toolflow against a state-of-the-art dynamically
scheduled HLS tool called Dynamatic. Our results show that
after standard loop unrolling is applied, our toolflow yields a 4×
average speedup, with a negligible area overhead. This increases
to a 7.3× average speedup when our toolflow is further combined
with C-slow pipelining.
of dynamically scheduled circuits, which are made up of components that use handshaking to schedule themselves at run
time, as opposed to following a schedule determined statically at
compile time. Dynamically scheduled circuits promise superior
performance on ‘irregular’ source programs, such as those whose
control flow depends on input data, at the cost of additional area.
Current dynamic scheduling techniques are well able to
exploit parallelism among instructions within each basic block
(BB) of the source program, but parallelism between BBs is
underexplored. Although current tools allow the operations of
different BBs to overlap, they require the BBs to start in strict
program order, thus limiting the achievable parallelism and
overall performance.
We seek to lift this restriction. Doing so involves developing a
toolflow that tackles the following challenges: (1) finding consecutive subgraphs in the control-flow graph and using static analysis
to identify those subgraphs that can be safely parallelised, and
(2) adapting the circuit so that those subgraphs are executed
in parallel while ensuring deterministic circuit behaviour and
correct usage of memory interfaces.
Using two benchmark sets from related works, we compare
our proposed toolflow against a state-of-the-art dynamically
scheduled HLS tool called Dynamatic. Our results show that
after standard loop unrolling is applied, our toolflow yields a 4×
average speedup, with a negligible area overhead. This increases
to a 7.3× average speedup when our toolflow is further combined
with C-slow pipelining.
Date Issued
2023-02-13
Date Acceptance
2022-06-14
Citation
2023, pp.243-252
Start Page
243
End Page
252
Copyright Statement
Copyright © 2023 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Identifier
https://ieeexplore.ieee.org/abstract/document/10035107
Source
International Conference on Field Programmable Logic and Applications
Publication Status
Published
Start Date
2022-08-29
Finish Date
2022-09-02
Coverage Spatial
Belfast, United Kingdom
Date Publish Online
2023-02-13