Probabilistic scheduling in high-level synthesis
File(s)
Accepted version
Author(s)
Cheng, Jianyi
Wickerson, John
Constantinides, George
Type
Conference Paper
Abstract
High-level synthesis (HLS) tools automatically trans-form 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 through put analysis in the dynamically scheduled Dynamatic tool incurs a17% ADP overhead.
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 through put analysis in the dynamically scheduled Dynamatic tool incurs a17% ADP overhead.
Date Issued
2021-06-02
Date Acceptance
2021-03-08
Citation
2021 IEEE 29th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), 2021, pp.195-203
Publisher
IEEE
Start Page
195
End Page
203
Journal / Book Title
2021 IEEE 29th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)
Copyright Statement
© 2021 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. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
Sponsor
Engineering & Physical Science Research Council (EPSRC)
Grant Number
EP/P010040/1
Source
The 29th IEEE International Symposium on Field-Programmable Custom Computing Machines
Subjects
Science & Technology
Technology
Computer Science, Hardware & Architecture
Computer Science, Theory & Methods
Engineering, Electrical & Electronic
Computer Science
Engineering
High-Level Synthesis
Probabilistic Analysis
Petri Nets
Dynamic Scheduling
MODULE SELECTION
PERFORMANCE ANALYSIS
PETRI NETS
DESIGN
OPTIMIZATION
EXPLORATION
Publication Status
Published
Start Date
2021-05-09
Finish Date
2021-05-12
Coverage Spatial
Virtual