Probabilistic scheduling in high-level synthesis

Jianyi Cheng, John Wickerson, George A. Constantinides

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.
Original languageEnglish
Title of host publication2021 IEEE 29th Annual International Symposium on Field-Programmable Custom Computing Machines
PublisherInstitute of Electrical and Electronics Engineers
Pages195-203
Number of pages9
ISBN (Electronic)9780738126739
DOIs
Publication statusPublished - 2 Jun 2021
Event29th IEEE International Symposium on Field-Programmable Custom Computing Machines - Orlando, United States
Duration: 9 May 202112 May 2021

Publication series

NameIEEE Annual International Symposium on Field-Programmable Custom Computing Machines
PublisherInstitute of Electrical and Electronics Engineers
ISSN (Print)2576-2613
ISSN (Electronic)2576-2621

Conference

Conference29th IEEE International Symposium on Field-Programmable Custom Computing Machines
Abbreviated titleFCCM 2021
Country/TerritoryUnited States
CityOrlando
Period9/05/2112/05/21

Keywords / Materials (for Non-textual outputs)

  • dynamic scheduling
  • high-level synthesis
  • petri nets
  • probabilistic analysis

Fingerprint

Dive into the research topics of 'Probabilistic scheduling in high-level synthesis'. Together they form a unique fingerprint.

Cite this