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) describes a streaming computation as actors connected by directed channels that carry data tokens. Its defining restriction is local and exact: on every firing, each actor consumes and produces a fixed, known number of tokens at each connected port. The actor's calculation can depend on token values, but its token counts cannot change from one firing to the next. Lee and Messerschmitt introduced this restriction to make dataflow programs, particularly multirate signal-processing programs, amenable to scheduling before execution.[1][2]
Known rates turn a graph into token arithmetic. On an edge from actor A to actor B, if A produces two tokens per firing and B consumes three, a balanced iteration needs three firings of A for every two of B. The same accounting must hold simultaneously on every edge. A topology matrix records the production and consumption counts; a positive integer repetition vector, when one exists, gives the number of times each actor fires in a complete balanced iteration. Balance is a necessary test, not a promise that actors can fire in that order: initial tokens and dependencies may still cause deadlock. When a complete balanced cycle can execute, its finite firing sequence can repeat with bounded channel storage.[3]
The advantage is conditional predictability. A suitable SDF graph can be scheduled at compile time, mapped to one or more processors, and analyzed for storage without relying on a general runtime choice of which actor to fire next. The price is expressive: data-dependent token rates and some mode-changing behaviors need a more general model or an explicit structure around separate SDF graphs.[2][3][4]
Structural Signature¶
- Actor firings: Computation is divided into identifiable steps. A firing reads its required input tokens, performs an operation, and writes its output tokens; an actor may fire many times during one graph iteration.[3][5]
- Directed token channels: An edge connects a producer to a consumer and carries an ordered stream of data tokens. The source and sink, rather than a variable-gain equation, define what each edge means. A concrete implementation may store these tokens in FIFO buffers.[1][5]
- Fixed rates per firing: Each connected port has a known consume or produce count that remains the same for every firing of that actor. This is the identity test. Numeric counts may differ across ports and actors, allowing multiple sample rates in one graph.[1][3]
- Balance test: For each edge, total tokens produced during an iteration must equal total tokens consumed. The topology matrix and a positive repetition vector express this test; a graph with fixed rates can fail it.[3]
- Execution-feasibility test: Even a balanced vector needs an ordering in which the required input tokens are available at each firing. A graph can satisfy rate equations yet lack an executable complete cycle because of deadlock.[3]
- Periodic schedule and channel bound: Once a finite, balanced cycle is executable, that firing order can repeat. The maximum occupancy of each channel during the chosen finite cycle gives a finite storage requirement. These are consequences of a feasible graph and schedule, not extra facts guaranteed by the word “synchronous.”[3]
The first three roles say what kind of computation is being modeled. The final three say what can be proved or constructed from that model when the additional conditions hold. Keeping those logical levels apart prevents a fixed-rate but inconsistent or deadlocked graph from being mislabeled as a working static schedule.
What It Is Not¶
SDF is not a synonym for every dataflow network. A network of FIFO-connected processes can leave its consumption and production rates dependent on input values or internal state. That wider network may still be useful, but the fixed-count balance argument no longer applies directly. Nor is SDF identical to cyclo-static dataflow: cyclo-static actors may use a predictable cycle of different per-firing rates, whereas an SDF actor uses one constant set of rates every firing. Cyclo-static models can also have static schedules under their own conditions; “not SDF” does not mean “not analyzable.”[3]
A fixed-rate graph is not automatically a valid periodic program. First seek a positive integer balance vector. Then ask whether the complete cycle can actually execute from its initial tokens. Failure of either test defeats the claimed repeatable bounded-memory implementation, while the graph's fixed-rate syntax can still be described as SDF. Likewise, a static order on a processor is an execution choice, not the defining rate restriction itself.[3][5]
“Synchronous” here does not require actors to share a physical clock tick or all fire simultaneously. It names the predictability of token exchange in this dataflow model. The processor, FPGA, programming language, and a particular digital filter are carriers of an SDF graph, not its constitutive parts.[1][2]
Scope of Application¶
The literal scope is concurrent or streaming computation whose actor boundaries and per-firing channel rates can be specified ahead of time. Lee and Messerschmitt describe multirate digital signal processing and static schedules for one or multiple programmable processors. Their SDF publication also describes static buffering and code generation for DSP microcomputers; these broad claims appear in the author-hosted abstract.[1][2]
An HDSL2 modem Simulation supplies a communication-system realization. Jackson and Koohrangpour modeled coding and equalization components with Ptolemy SDF blocks. They implemented startup and data modes as separate simulations because parameter exchange across the transition was not readily represented in their chosen SDF implementation. This is evidence of the fixed-rate model's use and of a practical modeling boundary, not a claim that a deployed modem or every possible one-graph encoding was tested.[4]
Image-processing graphs supply a different realization. Schlaak, Fakih, and Stemmer executed Sobel edge-filter and JPEG encoder SDF applications on an FPGA-based multiprocessor. Their actors communicated through FIFO buffers in shared memory; actors assigned to each processor followed a static order while the researchers varied the actor-to-processor mapping and measured time and power. The article identifies the applications as SDF graphs, but does not give a complete numeric per-edge token-rate table for both graphs in its rendered text.[5]
These are unlike computations within computer science. Their commonality is the actor/channel/fixed-rate model, not the same algorithm or hardware. Outside computation, phrases such as “fixed flow” or “balanced exchange” are analogies until their own roles and validity conditions are established.
Clarity¶
An SDF description should state four things separately. What fires? Identify each actor and the work of one firing. What flows? Name each directed channel and its token type. At what rate? State the number produced and consumed on every edge per firing. What was established? Distinguish a fixed-rate graph, a graph with a positive repetition vector, an executable complete cycle, and an actual chosen schedule with finite buffers.[3]
For a directed edge, write the balance condition in words: the producer's token count per firing times its repetition count must equal the consumer's token count per firing times its repetition count. Apply it to every edge. A positive solution restores aggregate token counts; it does not say that all actors have enough input tokens at the moments they need to fire. The initial tokens and firing order are therefore part of a schedulability claim, not optional decoration.[3]
Source precision also matters. The HDSL2 report says its Simulation used SDF blocks and split the modes; it does not publish a token-rate table or a compiled schedule for each modem block. The FPGA image paper reports SDF graphs and static within-processor order, but the seven processor mappings are measurements of implementation choices, not seven new definitions of SDF.[4][5]
Manages Complexity¶
Without the fixed-rate restriction, a scheduler may need to observe changing token availability and actor behavior while the program runs. SDF makes one part of that problem finite before execution: the rates supply equations for how frequently actors must fire relative to one another. An engineer can reject an inconsistent graph, seek an executable periodic cycle, and plan channel capacity for that schedule. The resulting compilation can reduce general runtime scheduling overhead where the graph is suitable.[2][3]
The simplification is not free. Rate declarations are assumptions about the computation. If a modem changes modes or an actor chooses a different number of outputs from a token value, forcing it into one unqualified fixed-rate graph can hide behavior that matters. A more expressive model may recover that behavior but give up some static guarantees. The useful compression is therefore a precise contract—constant counts per firing—paired with explicit tests of consistency and progress.[3][4]
Abstract Reasoning¶
Take a source actor U producing three tokens on an edge each time it fires and a downstream actor D consuming two. Balance requires two firings of U for every three of D, because both sides then account for six tokens. That ratio is an arithmetic candidate for one edge's repetition counts. A larger graph may impose additional, conflicting edge ratios; even if a common positive vector exists, a feedback cycle without the required initial tokens may prevent the first enabled firing.[3]
The reusable reasoning sequence is: establish fixed rates; solve the simultaneous edge balances; inspect initial tokens and dependencies for a complete executable cycle; then evaluate schedules and buffer occupancy. A claim made at a later step cannot be pulled back to the earlier step. “This graph is SDF” says less than “this graph has a bounded-memory periodic implementation.”[3]
Knowledge Transfer¶
Once the rate rule is learned, a reader can recognize it in a modem simulation, an image-processing graph, or a multirate filter without importing the details of one application into another. In each case, look for identifiable firings, directed token channels, and a stable consume/produce count for each firing. Then apply the same balance-versus-executability distinction. In the modem, mode transition is the warning boundary; in the image experiment, actor mapping changes timing and power while the graph's SDF classification remains a model statement.[4][5]
Transfer stops when those roles are only metaphorical. A factory line may have stations and material flow, but this entry does not thereby supply a model of its inventories, choices, and stochastic delays. A different abstraction may capture local conservation or flow balance there. SDF remains a claim about actor firings and token channels in computation.
Examples¶
Canonical: FIR filter and 1:3 downsampler¶
Parks, Pino, and Lee present a finite-impulse-response anti-aliasing filter feeding a downsampler. In their SDF form, the downsampler consumes three input samples and produces one output sample for each firing. Three preceding filter firings are needed before that downsampler firing can consume its three inputs. Their comparison with a cyclo-static form illustrates how changing the firing rule changes precedence and can expose work that the coarser SDF firing waits to collect. This is a published analytical graph, not an observed deployment.[3]
Mapped back: The filter and downsampler are actors; samples are tokens; the connection is the channel; the downsampler's fixed three-in/one-out count is the rate rule. The relative firing counts and available tokens determine when its output can appear. No particular processor is required for the graph to have this identity.
Applied/practice: modem and image computations¶
In the HDSL2 project, scrambler, mapper, equalizer, precoder, and coding blocks formed a Ptolemy simulation built from SDF blocks. The startup and data modes were separate models because their parameter handoff was not readily modeled within the authors' SDF implementation.[4]
Mapped back: The modem blocks fill the actor role; directed data connections fill the channel role; the authors' SDF-block choice supplies fixed-count semantics. The report does not provide each edge's numerical rate or a schedule table, so those values are not inferred. The mode transition marks a limit of this documented implementation.
In the FPGA experiment, one SDF graph used Sobel actors getPixel, GX, GY, and ABS; another used JPEG actors getMB, CC, DCT, and VLC. FIFO buffers connected the actors through shared memory. The researchers tested seven mappings of those actors to processor tiles while keeping a static actor order within each processor.[5]
Mapped back: The named image operations are actors; the FIFO buffers carry tokens; the authors present the graphs as SDF applications, so fixed-rate per-firing semantics are attributed at the model level without inventing a complete numeric rate table. The measured mapping alternatives concern implementation performance, not whether the fixed-rate model exists.
Structural Tensions¶
T1: Fixed-rate analyzability vs. changing-rate expressiveness. Keep each actor's token rates constant and balance and periodic scheduling can be analyzed ahead of time, with a bounded-memory repeatable cycle when the additional feasibility conditions hold. This choice cannot directly express an actor whose token count depends on the current data. Move to a more general dynamic model and that behavior becomes expressible, but a finite periodic schedule or channel bound may no longer be available in general. Jackson and Koohrangpour's separate startup/data simulations show a narrower practical mode-handoff difficulty in their chosen implementation, not a theorem that every such handoff is impossible in every SDF encoding.[3][4]
Diagnostic: Do the actual consume/produce counts stay fixed on every firing, and does the application need a runtime mode transition that this particular SDF model cannot conveniently represent?
T2: Compact actor composition vs. external token progress. Combining several actors into one SDF firing can give the composite actor all of its inputs at the start and leave flexibility for its internal schedule. Yet the surrounding graph must now provide all those inputs before any internal step can run. Parks, Pino, and Lee show a case where this added precedence introduces deadlock, while finer cyclic firings can preserve progress. Keeping those finer firings can make the representation and scheduling analysis more involved; grouping can be useful when its external dependencies remain feasible. This comparison does not imply that every grouping deadlocks or that a particular buffer-size trade-off was measured.[3]
Diagnostic: If these operations are grouped, will some input be withheld until an output that the grouped actor cannot now produce early enough?
Structural–Framed Character¶
SDF has a highly formal structural center: an actor graph, fixed integer rates, balance equations, and a conditional execution theorem. Its name still belongs to a particular practice of modeling computations, not to every situation in which something flows.
Evaluative weight: Predictability, low runtime scheduling overhead, and bounded storage are reasons engineers choose SDF. They are advantages to seek and test, not part of the minimum test for whether a graph has fixed per-firing rates. An inconsistent SDF graph has failed an analysis without ceasing to exhibit the fixed-rate syntax.[2][3]
Human-practice dependence: Designers decide where actor boundaries lie and which behavior to model. Those choices can make a mode handoff awkward or make a composite actor wait for more tokens than its parts would need. Once the graph and rates are fixed, however, whether a repetition vector balances the edges is a mathematical question, not a preference.[3][4]
Institutional origin: The name and theory come from dataflow and signal-processing research, and implementations use particular tools such as Ptolemy. No single tool licenses the category: the FPGA image experiment has different code and hardware while retaining the SDF actor/channel/rate rule.[1][4][5]
Vocabulary travel: The term travels literally from modem modeling to image processing because actors fire and tokens cross fixed-rate channels in both. Calling a supply chain “synchronous data flow” merely because goods move at a planned rate would require independent proof of the same constitutive roles and analysis; word resemblance is not enough.
Import versus recognition: One may recognize SDF in a new computing graph by checking its per-firing counts. One cannot import its bounded-buffer conclusion into a graph just by drawing boxes and arrows: consistency, initial tokens, and executable ordering still need proof.[3]
Its character: SDF is structurally precise within a framed computing practice. Its portable fixed-exchange skeleton suggests a broader comparison, while the named identity and its guarantees remain tied to actor firings, token channels, and computation schedules.
Structural Core vs. Domain Accent¶
The skeletal relation is fixed local exchange counts permit a global balance test. A producer's and consumer's counts constrain their relative repetitions, and the constraints must fit across the whole graph. A future broader abstraction could ask whether the same necessary-role relation recurs in unlike noncomputing settings. That is a research question, not an approved Prime here: generic conservation arithmetic and metaphorical “flow” do not establish the full relation.[3]
The domain accent is constitutive, not cosmetic. The counts are tokens per actor firing on directed computational channels. Feasibility asks whether those firings can execute from initial tokens without deadlock; the resulting schedule concerns processors and channel memory. Replace firings with vague “steps” or tokens with any conserved substance and the SDF-specific inference no longer follows. Until at least two unlike noncomputing settings establish the same necessary roles and consequences, the named model stays domain-specific.
Instantiates / Related Primes¶
SDF is a directed actor network: that description captures its connected nodes and channels, but does not supply fixed per-firing rates, token balance, or an executable-cycle test. Many feed-forward SDF graphs are also pipelines, while feedback and multirate graphs need not be simple linear pipelines. Neither broader word alone establishes the conditions under which a periodic SDF schedule exists.[1][3]
The live Kahn Process Networks entry shares process-and-FIFO vocabulary but defines schedule-independent stream semantics with semantically unbounded channels and blocking reads; it explicitly distinguishes SDF's fixed firing rates. That is a comparison target, not a synonym or automatically the broader abstraction. The live Stream Processing entry concerns event-time arrival, watermarks, windows, and latency contracts rather than compile-time token-rate balance. These neighbors help locate SDF without replacing its rate rule.
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
Not to Be Confused With¶
- Kahn process networks: The live entry's central claim is deterministic stream behavior under its process/channel semantics; fixed token counts per actor firing are not its defining test.
- Cyclo-static dataflow: Rates follow a predictable cycle rather than remaining identical on every firing. It can also be statically scheduled in suitable cases.[3]
- Stream processing: A stream processor may handle unbounded event arrivals with windows and watermarks without fixed per-firing token rates.
- Functional reactive programming: Reactive behaviors and events expressed with functional composition do not, by that fact alone, impose SDF token counts.
- Signal-flow graph: Nodes and weighted branches represent variables and functional gains in system equations, not computational actor firings and token balance.
- A particular DSP or FPGA implementation: The modem, filter, and image graphs are realizations or worked examples; no one of them defines the whole model.
References¶
[1] 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; it supports fixed a-priori token rates, multirate DSP, static scheduling, code generation and static buffering. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g
[2] 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; it supports the fixed-rate scheduling distinction and single/multiple-processor context. registry ↩a ↩b ↩c ↩d ↩e ↩f
[3] 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 seven-page paper inspected; sections 1–2 cover firing rules, topology matrix, balance, deadlock and bounded cycles; section 5 gives the FIR/1:3 downsampler; section 1.2 and Figure 4 analyze composition-induced deadlock. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v ↩w ↩x
[4] 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. Original university-hosted nine-page student-project report inspected; section 3, PDF pp. 6–8, documents the Ptolemy SDF-block simulation and separate startup/data models; section 4, PDF p. 9, states limitations. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i
[5] 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 author-paper HTML inspected; sections 1, 3 and 4, Figure 1, Table 2 and Figure 6 describe Sobel/JPEG SDF applications, shared-memory FIFO channels, static actor order, and seven implementation mappings. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h