A scheduling algorithm for conditional resource sharing

Abstract

A novel 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. Experimental results demonstrated that such an approach is quite effective. The proposed bottom-up hierarchical approach is computationally more effective than a global nonhierarchical one.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>