On objective function selection in list scheduling algorithms for digital signal processing applications

In this paper we discuss the choice of objective function in list scheduling algorithms for scheduling dataflow graphs onto multiprocessor architectures. A majority of the list scheduling algorithms used in practice utilize a global strategy wherein actor static levels are used for making scheduling decisions. When fine grain DSP applications such as FIR or elliptical filters need to be scheduled on architectures that consist of commodity part processors and a general interconnection network whose interprocessor communication cost cannot be ignored, a traditional list scheduling algorithm is in many cases not the best choice. In an experimental study we compare these global strategies to local strategies that utilize load balancing. The study reveals that global strategies suffer from flaws that could cause local strategies to yield more than 10% shorter schedule lengths on the average. In particular we find that a novel Earliest Finish Time (EFT) strategy exhibits very good performance