Synchronous Data Flow¶
A fixed-token-rate actor graph whose channel balance and feasible periodic execution can be analyzed before it runs.
Core Idea¶
Synchronous data flow (SDF) models computation as actors joined by directed token channels, with a fixed, known number of tokens consumed and produced at each port on every firing. Those rates permit a balance test and a search for a periodic schedule before execution. A positive balance solution alone is insufficient: initial tokens must also permit a complete firing cycle before finite channel storage follows.[ref-ff68810760f4][ref-a69e834fa3da]
Scope of Application¶
Use SDF where actor boundaries and per-firing token counts can be stated in advance:
- Multirate signal processing: Static schedules can coordinate differing sample rates on one or more processors.[ref-ff68810760f4][ref-0d45797b4876]
- HDSL2 modem simulation: Ptolemy SDF blocks modeled coding and equalization; the student report used separate startup and data simulations.[^ref-972f6d1137eb]
- Sobel filtering: One FPGA multiprocessor study executed a Sobel SDF graph.[^ref-3a8a921ab877]
- JPEG encoding: The same study executed a JPEG SDF graph under different actor placements.[^ref-3a8a921ab877]
Clarity¶
Identify the actors, channels, and token counts per firing. Report separately whether the edge-balance equations have a positive repetition vector, whether a complete cycle can execute from the initial tokens, and what schedule and buffer bound were established. Fixed rates alone do not prevent inconsistency or deadlock, and “synchronous” does not require one physical clock tick for every actor.[ref-a69e834fa3da][ref-ff68810760f4] The two application reports do not supply complete numerical rate tables.[ref-972f6d1137eb][ref-3a8a921ab877]
Manages Complexity¶
Fixed rates turn part of runtime scheduling into finite token accounting. For a suitable graph, a compiler can calculate relative firing counts, find a periodic order, and allocate finite channel storage.[ref-0d45797b4876][ref-a69e834fa3da] The price is expressive power: data-dependent counts require another model or an explicit arrangement of SDF graphs.[^ref-a69e834fa3da] The modem's split modes show one implementation limit, not a universal impossibility.[^ref-972f6d1137eb]
Abstract Reasoning¶
For each channel, equate production per firing times producer repetitions with consumption per firing times consumer repetitions. Solve all edges together, then check that initial tokens allow a complete firing order. A feedback cycle may deadlock despite balanced rates. Only an executable cycle supports a repeatable schedule and finite peak channel occupancy.[^ref-a69e834fa3da]
Knowledge Transfer¶
The actor, channel, fixed-rate test transfers from a multirate filter to the modem simulation and FPGA image graphs.[ref-a69e834fa3da][ref-972f6d1137eb][^ref-3a8a921ab877] A network captures connected actors and channels but does not, by itself, supply fixed firing rates or conserved stocks. Kahn process networks add deterministic stream semantics that fixed-rate SDF alone does not guarantee. The model travels within computation where its firing and token roles remain literal.
Neighborhood in Abstraction Space¶
Synchronous Data Flow sits in a sparse region of the domain-specific corpus (98th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (2721 abstractions)
Nearest neighbors
- Activity Diagram — 0.76
- Kahn Process Networks — 0.76
- Navigation loop — 0.76
- Reaching definition — 0.76
- Node graph architecture — 0.75
Computed from structural-signature embeddings · 2026-10-17
References¶
[^ref-ff68810760f4]: Edward A. Lee and David G. Messerschmitt, “Synchronous Data Flow,” Proceedings of the IEEE 75, no. 9 (1987): 1235–1245. UC Berkeley author-institution publication page and abstract, https://ptolemy.berkeley.edu/publications/papers/87/synchdataflow/. Source access: author-hosted abstract only. [^ref-0d45797b4876]: Edward A. Lee and David G. Messerschmitt, “Static Scheduling of Synchronous Data Flow Programs for Digital Signal Processing,” IEEE Transactions on Computers C-36, no. 1 (1987): 24–35. UC Berkeley author-institution publication page and abstract, https://ptolemy.berkeley.edu/publications/papers/87/staticscheduling/. Source access: author-hosted abstract only. [^ref-a69e834fa3da]: Thomas M. Parks, José Luis Pino, and Edward A. Lee, “A Comparison of Synchronous and Cyclo-Static Dataflow,” Proceedings of the Asilomar Conference on Signals, Systems, and Computers (1995), https://ptolemy.berkeley.edu/publications/papers/95/csdfVSsdf/csdfVSsdf.pdf. Original complete paper, sections 1–2 and 5. [^ref-972f6d1137eb]: Patrick Jackson and Reza Koohrangpour, HDSL2 Modem Modeling and Simulation (University of Texas at Austin EE 382C final project report, May 12, 1999), https://users.ece.utexas.edu/~bevans/courses/ee382c/projects/spring99/jackson-koohrang/finreport.pdf. Student simulation report, sections 3–4. [^ref-3a8a921ab877]: Christof Schlaak, Maher Fakih, and Ralf Stemmer, “Power and Execution Time Measurement Methodology for SDF Applications on FPGA-based MPSoCs,” HIP3ES 2017, arXiv:1701.03709v1, https://arxiv.org/html/1701.03709v1. Original complete paper, sections 1, 3–4, Figure 1 and Table 2.