Phased Scheduling of Stream Programs - Karczmarek, Michal; Thies, Bill; Amarasinghe, Saman (Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES 2003). San Diego, CA, 2003)
As embedded DSP applications become more complex, it is increasingly important to provide high-level stream abstractions that can be compiled without sacrifi cing efficiency. In this paper, we describe scheduler support for StreamIt, a high-level language for signal processing applications. A StreamIt program consists of a set of autonomous filters that communicate with each other via FIFO queues. As in Synchronous Data ow (SDF), the input and output rates of each filter are known at compile time. However, unlike SDF, the stream graph is represented using hierarchical structures, each of which has a single input and a single output. We describe a scheduling algorithm that leverages the structure of StreamIt to provide a flexible tradeoff between code size and bu er size. The algorithm describes the execution of each hierarchical unit as a set of phases. A complete cycle through the phases represents a single steady-state execution. By varying the granularity of a phase, our algorithm provides a continuum between single appearance schedules and minimum latency schedules. We demonstrate that a minimal latency schedule is eff ective in decreasing bu er requirements for some applications, while the phased representation mitigates the associated increase in code size.