GENERATING COMPACT CODE FROM DATA-FLOW SPECIFICATIONS OF MULTIRATE SIGNAL-PROCESSING ALGORITHMS

Synchronous dataflow (SDF) semantics are well-suited to representing a nd compiling multirate signal processing algorithms. A key to this mat ch is the ability to cleanly express iteration without overspecifying the execution order of computations, thereby allowing efficient schedu les to be constructed. Due to limited program memory, it is often desi rable to translate the iteration in an SDF graph into groups of repeti tive firing patterns so that loops can be constructed in the target co de. This paper establishes fundamental topological relationships betwe en iteration and looping in SDF graphs, and presents a scheduling fram ework that provably synthesizes the most compact looping structures fo r a large class of practical SDF graphs. By modularizing different com ponents of the scheduling framework, and establishing their independen ce, we show how other scheduling objectives, such as minimizing data b uffering requirements or increasing the number of data transfers that occur in registers, can be incorporated in a manner that does not conf lict with the goal of code compactness.