Interactive Companion 1987 Paper PDF Scholar Context

Synchronous Data Flow for Signal Processing

A fixed-rate stream graph becomes something a compiler can reason about like circuitry: token balance, repeating schedules, bounded buffers, and parallel structure all become visible. This page turns that bargain into diagrams instead of prose.

Core Rule
fixed rates
Compiler Output
periodic schedule
Memory Result
bounded FIFO
q = [6, 4, 2, 3]
Example repetition vector
0 net tokens
Steady-state arc change
static
Dispatch strategy
DSP-first
Best-fit workload

1. Pipeline Overview

A multirate filter chain is a perfect SDF postcard. Click actors to inspect their contracts; hover edges to see the rate mismatch the scheduler must reconcile.

Multirate Stream Graph

Selected Actor

Color intensity encodes pressure on scheduling and buffering. Hotter links indicate larger transient occupancy or stronger rate conversion.

2. Balance and Schedule

SDF turns “can this run forever?” into integer bookkeeping. The heatmap shows one steady-state period; the line chart shows buffer occupancy over that exact schedule.

Firing Timeline Heatmap

Edge Occupancy Trace

3. Memory and Buffering

Static schedules do not make memory free; they make memory visible. Toggle through allocation strategies to see how compile-time knowledge lowers peak FIFO demand.

Buffer Requirement Matrix

Peak Memory Comparison

4. Frontier and Limits

The model wins by refusing messy behavior. This final view compares static SDF against more dynamic dataflow families and the irregular workloads that escape fixed-rate analysis.

Where Static Structure Pays

Workload Fit Radar

References

Lee & Messerschmitt, 1987 — Synchronous Data Flow for Signal Processing
Lee & Messerschmitt, 1987 — Static Scheduling of SDF Programs
Lee & Parks, 1995 — Dataflow Process Networks
Bhattacharyya, Murthy & Lee, 1999 — Software Synthesis from SDF
Thies, Karczmarek & Amarasinghe, 2002 — StreamIt
Bhattacharyya & Lee, 1994 — Memory Management for Multirate DSP
Murthy & Bhattacharyya, 2000 — Buffer Merging
Episode context also connects naturally to later compiler and accelerator work on static structure, bounded queues, and stream regularity.