Balancing static islands in dynamically scheduled circuits using continuous petri nets
File(s)
Accepted version
Author(s)
Cheng, Jianyi
Fraca Santamaria, Estibaliz
Wickerson, John
Constantinides, George
Type
Journal Article
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 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.
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.
Date Issued
2023-11-01
Date Acceptance
2023-06-28
Citation
IEEE Transactions on Computers, 2023, 72 (11), pp.3300-3313
ISSN
0018-9340
Publisher
Institute of Electrical and Electronics Engineers
Start Page
3300
End Page
3313
Journal / Book Title
IEEE Transactions on Computers
Volume
72
Issue
11
Copyright Statement
Copyright © 2023 IEEE. Personal use of this material is permitted. However, permission to use this material for any other purposes must be obtained from the IEEE by sending a request to pubs-permissions@ieee.org. The author has applied a ’Creative Commons Attribution’ (CC BY) licence to any Author Accepted Manuscript version arising.
License URL
Identifier
https://ieeexplore.ieee.org/document/10183831
Publication Status
Published
Date Publish Online
2023-07-13