TY - GEN
T1 - Probabilistic scheduling in high-level synthesis
AU - Cheng, Jianyi
AU - Wickerson, John
AU - Constantinides, George A.
PY - 2021/6/2
Y1 - 2021/6/2
N2 - High-level synthesis (HLS) tools automatically transform a high-level program, for example in C/C++, into a low- level hardware description. A key challenge in HLS tools is scheduling, i.e. determining the start time of all the operations in the untimed program. There are three approaches to scheduling: static, dynamic and hybrid. A major shortcoming of existing approaches to scheduling is that the tools either assume the worst- case timing behaviour, which can cause significant performance loss or area overhead, or use simulation-based approaches, which take a long time to explore enough program traces.In this paper, we propose a probabilistic model that allows HLS tools to efficiently explore the timing behaviour of hardware generated from all these scheduling approaches. We capture the performance of the hardware using Petri nets, allowing us to leverage off-the-shelf Petri net analysis tools to make HLS decisions.We demonstrate the utility of our approach by using it to automatically infer the optimal initiation interval (II) for statically scheduled components that form part of a larger dynamically scheduled circuit. An empirical evaluation on a range of benchmarks suggests that by using this approach, on average we incur a 2% overhead in area-delay product (ADP) compared to optimal designs. In contrast, the static analysis in Vitis HLS incurs a 112% ADP overhead, while the throughput analysis in the dynamically scheduled Dynamatic tool incurs a 17% ADP overhead.
AB - High-level synthesis (HLS) tools automatically transform a high-level program, for example in C/C++, into a low- level hardware description. A key challenge in HLS tools is scheduling, i.e. determining the start time of all the operations in the untimed program. There are three approaches to scheduling: static, dynamic and hybrid. A major shortcoming of existing approaches to scheduling is that the tools either assume the worst- case timing behaviour, which can cause significant performance loss or area overhead, or use simulation-based approaches, which take a long time to explore enough program traces.In this paper, we propose a probabilistic model that allows HLS tools to efficiently explore the timing behaviour of hardware generated from all these scheduling approaches. We capture the performance of the hardware using Petri nets, allowing us to leverage off-the-shelf Petri net analysis tools to make HLS decisions.We demonstrate the utility of our approach by using it to automatically infer the optimal initiation interval (II) for statically scheduled components that form part of a larger dynamically scheduled circuit. An empirical evaluation on a range of benchmarks suggests that by using this approach, on average we incur a 2% overhead in area-delay product (ADP) compared to optimal designs. In contrast, the static analysis in Vitis HLS incurs a 112% ADP overhead, while the throughput analysis in the dynamically scheduled Dynamatic tool incurs a 17% ADP overhead.
KW - dynamic scheduling
KW - high-level synthesis
KW - petri nets
KW - probabilistic analysis
UR - http://www.scopus.com/inward/record.url?scp=85107699117&partnerID=8YFLogxK
U2 - 10.1109/FCCM51124.2021.00031
DO - 10.1109/FCCM51124.2021.00031
M3 - Conference contribution
AN - SCOPUS:85107699117
T3 - IEEE Annual International Symposium on Field-Programmable Custom Computing Machines
SP - 195
EP - 203
BT - 2021 IEEE 29th Annual International Symposium on Field-Programmable Custom Computing Machines
PB - Institute of Electrical and Electronics Engineers
T2 - 29th IEEE International Symposium on Field-Programmable Custom Computing Machines
Y2 - 9 May 2021 through 12 May 2021
ER -