A Scheduling Algorithm for Conditional Resource Sharing - A Hierarchical Reduction Approach

Abstract

A new scheduling algorithm for dataflow graphs with nested conditional branches is presented. The algorithm employs a bottom-up approach to transform a dataflow graph with conditional branches into an ''equivalent'' one that has no conditional branches. A schedule is then obtained for the latter, using a conventional scheduling algorithm, from which a schedule for the former is derived. Our approach is particularly effective when there is a large number of nested conditional branches in a dataflow graph.