Balancing static islands in dynamically scheduled circuits using continuous Petri nets

Jianyi Cheng*, Estibaliz Fraca, John Wickerson, George A. Constantinides

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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 is scheduling, i.e. determining the start time of all the operations in the untimed program. A major shortcoming of existing approaches to scheduling - whether they are static (start times determined at compile-time), dynamic (start times determined at run-time), or a hybrid of both - is that the static analysis cannot efficiently explore the run-time hardware behaviours. Existing approaches either assume the timing behaviour in extreme cases, which can cause sub-optimal performance or larger area, or use simulation-based approaches, which take a long time to explore enough program traces. In this article, we propose an efficient approach using probabilistic analysis for HLS tools to efficiently explore the timing behaviour of scheduled hardware. We capture the performance of the hardware using Timed Continous Petri nets with immediate transitions, allowing us to leverage efficient Petri net analysis tools for making HLS decisions. We demonstrate the utility of our approach by using it to automatically estimate the hardware throughput for balancing the throughput for statically scheduled components (also known as static islands) computing in a dynamically scheduled circuit. Over a set of benchmarks, we show that our approach on average incurs a 2% overhead in area-delay product compared to optimal designs by exhaustive search.
Original languageEnglish
Pages (from-to)3300-3313
Number of pages14
JournalIEEE Transactions on Computers
Volume72
Issue number11
DOIs
Publication statusPublished - 13 Jul 2023

Keywords / Materials (for Non-textual outputs)

  • dynamic scheduling
  • formal methods
  • FPGA
  • high-level synthesis
  • Petri nets

Fingerprint

Dive into the research topics of 'Balancing static islands in dynamically scheduled circuits using continuous Petri nets'. Together they form a unique fingerprint.

Cite this