Combining dynamic and static scheduling in high-level synthesis

Abstract

A central task in high-level synthesis isscheduling: the allocationof operations to clock cycles. The classic approach to schedulingisstatic, in which each operation is mapped to a clock cycle atcompile-time, but recent years have seen the emergence ofdynamicscheduling, in which an operation’s clock cycle is only determinedat run-time. Both approaches have their merits: static schedulingcan lead to simpler circuitry and more resource sharing, while dy-namic scheduling can lead to faster hardware when the computationhas non-trivial control flow.In this work, we seek a scheduling approach that combines thebest of both worlds. Our idea is to identify the parts of the inputprogram where dynamic scheduling does not bring any perfor-mance advantage and to use static scheduling on those parts. Thesestatically-scheduled parts are then treated as black boxes whencreating a dataflow circuit for the remainder of the program whichcan benefit from the flexibility of dynamic scheduling.An empirical evaluation on a range of applications suggests thatby using this approach, we can obtain 74% of the area savings thatwould be made by switching from dynamic to static scheduling, and135% of the performance benefits that would be made by switchingfrom static to dynamic scheduling.