►
From YouTube: Dataflow Programming
Description
In dataflow programming, programs are represented as directed graphs (and are often assembled visually); data “flows” through arcs and is processed by nodes.
In this presentation, we’ll compare dataflow against the imperative and functional programming paradigms, and explore the suitability of dataflow for two tasks: big data analysis and DSP.
Presenter: Marvin Humphrey
Video introduction to dataflow programming: https://www.youtube.com/watch?v=iFlT93wakVo
Paper: “Advances in Dataflow Programming Languages”, by Johnston, Hanna, and Millar (2004)
http://www.cs.ucf.edu/~dcm/Teaching/COT4810-Spring2011/Literature/DataFlowProgrammingLanguages.pdf
---
How to read the paper, in four optional steps:
0. Skip it and attend anyway - the presentation won't assume attendees have read the paper.
1. Watch the video.
2. Read section 2.1 "The Pure Dataflow Model" on pages 3-4.
3. Read the sections on "hybrid dataflow", "coarse-grained dataflow", and "synchonous dataflow".
A
B
This
is
a
dataflow
program
which
performs
a
simple
arithmetic
computation.
It
takes
an
input
X
and
an
input.
Y
sums
x
and
y
together
divides
Y
by
10
and
then
multiplies
the
results
of
those
operations
to
get
a
final
output.
This
program
is
not
in
any
particular
dataflow
programming
language.
Instead,
it's
an
idealized
representation
that
you
might
think
of
as
pseudocode.
B
Here
we
have
a
somewhat
more
sophisticated
program
written
in
pure
data
or
PD,
a
dataflow
ish
programming,
language
used
primarily
for
audio
DSP.
What
this
program
does
is
take
input
theoretically
from
a
theremin.
That's
basically,
it
will
take
any
monophonic
input.
The
theremin
is
that
spooky
science
fiction
instrument
because
like
and
it
quantizes
the
pitch
and
amplitude
from
the
theremin
or
monophonic
input
and
converts
those
values
to
a
stream
of
MIDI
messages.
I
say
that
PD
is
dataflow
ish,
because,
despite
the
name
pure
data,
it
is
not
a
pure
dataflow
programming.
B
B
This
is
also
a
dataflow
program
and
it
also
describes
a
directed
graph.
It
just
uses
text
to
specify
that
directed
graph,
and
that
is
not
unusual
in
the
slightest
dataflow
programming
has
been
around
since
the
1970s,
but
dataflow
visual
programming
didn't
become
popular
until
the
1990s,
when
reasonably
priced
workstations
became
powerful
enough
to
run
visual
editors.
B
B
Yes,
this
is
utter
and
complete
overkill
in
terms
of
the
resources
you're
bringing
to
bear
in
order
to
count
the
words
and
mary
had
a
little
lamb',
but
we'll
explore
later
why
dataflow
algorithms
are
conducive
to
scaling
through
parallelism,
parallelization,
of
which
this
is
an
illustration
I
mentioned
earlier,
that
the
dataflow
programming
paradigm
is
to
represent
the
program
as
a
directed
graph.
I
didn't
explain
what
a
directed
graph
is
so
for
the
benefit
of
those
who
may
be
less
familiar.
B
Here's
a
little
review
a
graph
is
a
data
structure,
a
collection
of
nodes
and
vertexes,
which
are
nodes
or
vertexes
which
are
connected
by
edges
or
arcs,
and
a
directed
graph
is
a
specialization
of
that.
Where
the
connections
have
direction,
it
is
differentiated
from
an
undirected
graph
where
the
connections,
our
bidirectional,
the
connections
in
these
visualizations
on
the
left,
we
have
several
directed
graphs
on
the
left.
I'll
have
arrowheads
indicating
the
direction
of
information
flow
or
token
flow
in
an
undirected
graph.
They
would
typically
be
bare
lines.
B
Instead,
the
term
node
can
be
substituted
with
vertex
or
point
or
Junction.
Similarly,
edge
might
be,
or
arc
might
be,
linked
or
line
or
connection
or
wire
or
cable
in
popular
usage
in
computer
science
and
graph
theory,
vertex
and
edge
tend
to
win
out
when
you're
talking
about
graphs
of
unspecified
type
or
about
undirected
graphs.
But
if
you're
talking
about
directed
graphs,
people
tend
to
use
node
and
arc
more
commonly
and
since
in
dataflow,
we're
talking
about
directed
graphs
exclusively
we're
going
to
stick
with
node
and
arc.
B
Here
is
a
programmatic
representation
on
the
right
of
a
directed
graph.
There
are
two
collections.
The
first
is
a
bag
of
nodes,
just
named
one
two,
three
four
and
five.
The
second
is
a
bag
of
directed
edges.
The
first
directed
edge
points
from
one,
the
two
second
one
from
two
to
three,
then
from
3
1,
2,
/,
5,
4,
oh
to
5,
and
then
that
loop
at
the
end
is
5
pointing
to
itself.
B
So
in
these
directed
graphs,
modeling
dataflow
programs.
What
do
the
elements
represent?
Well,
for
starters,
the
node
stands
in
for
a
unit
of
computation,
which
could
be
as
small
as
a
machine
level.
Instruction
such
as
this
Moulton
ode
that
we
have
on
the
left,
they're
symbolized
by
the
asterisk
or
in
more
coarse-grained
data
flows
we'll
get
to
later.
It
could
be
a
function
of
arbitrary
complexity.
A
node
takes
one
or
more
inputs
in
this
case
it's
taking
two
and
it
produces
one
or
more
outputs
in
pure
dataflow.
B
The
only
way
to
get
information
into
or
out
of
a
node
is
through
its
ports
or
its
arcs
global
variables
are
aloud
in
pure
dataflow
and
arc.
You
can
think
of
as
a
pipe
or
a
path
through
which
data
passes.
That's
the
obvious
visual
metaphor,
but,
more
importantly,
there's
a
conceptual
insight
here.
Arcs
Express
data
dependencies
between
nodes,
token
is
a
unit
of
data
of
unspecified
type
or
and
value
or
more
precisely,
of.
B
Without
regards
to
its
type
and
value
and
a
port
refers
to
the
boundary
between
a
node
and
an
arc,
so
there's
two
types
here:
the
input
ports
which
are
at
the
top
of
that
thing
where
the
input
tokens
are
being
received
and
the
output
port,
where
the
output
is
placed.
Not
everyone
uses
the
term
port.
B
This
is
a
pseudocode
multnomah
indicated
by
asterisk
and
it
performs
multiplication.
It
has
two
input:
ports
and
one
output
port.
When
the
program
starts,
the
node
is
in
a
state
of
waiting
to
become
fireable
after
some
unspecified
amount
of
time.
The
token
arrives
at
one
or
the
other
of
the
input
ports.
It
doesn't
matter
which
one
after
some
unspecified
amount
of
time,
a
token
arrives
at
the
other
input
port.
B
At
this
point,
the
node
has
acquired
the
quality
fireable
after
some
unspecified
amount
of
time,
the
node
fires,
which
involves
a
few
steps.
First,
the
node
absorbs
the
tokens
from
its
input
ports.
Then
it
performs
its
defined
calculation
or
computation
that
takes
the
output
of
that
pop
of
computation
and
places
it
on
the
output
port.
At
this
point,
it
is
ceased
firing
and
has
returned
to
the
state
of
waiting
to
become
fireable
once
more.
B
Let's
explore
what
that
means.
On
the
Left,
we
have
the
data
flow
pseudocode
for
the
arithmetic,
computation
on
the
right.
We
have
the
equivalent
program
expressing
the
same
thing
in
an
imperative
von
neumann
style
pseudocode,
which
is
a
sequence
of
instructions
for
the
computer
to
follow
in
excruciating
detail
so
in
time
unit
1
of
the
von
Neumann
program
X&Y,
are
some
than
a
result
assigned
to
a
in
time
unit
2.
We
have
Y
divided
by
10
and
assigned
to
B,
etc.
B
So
it
takes
three
discrete
time
units
for
the
program
to
generate
its
result
and
the
execution
is
assigned
to
each
of
those
time.
Units
must
be
executed
in
order,
but
when
those
program
at
least
theoretically
and
optimizations
not
withstanding,
but
when
these
programs
start
up,
they
have
to
wait
for
the
input
values
to
arrive,
and
arguably
the
von
Neumann
program
can't
even
start
before.
Input
is
ready,
but
let's
finesse
that
for
now
and
just
proceed
with
the
thought
experiment.
B
What
if
Y
shows
up
before
the
value
for
X
shows
up
the
say
again,
it
will
be
divided
this.
The
programs
will
behave
differently
at
this
point,
so
the
the
imperative
program
cannot
proceed
because
the
instruction
which
is
cued
that
first
one
still
has
a
data
dependency
on
X,
which
has
not
yet
been
satisfied.
B
However,
the
dataflow
program
on
the
Left
can
distribute
Y
to
the
input
ports
of
both
the
some
and
the
divide
nodes
and
the
divide.
Node
has
already
received
the
input.
Token
4:10,
since
that
was
prepared
to
begin
with,
and
now
that
the
divide
node
has
received
input
tokens
at
both
of
its
input,
ports.
It
has
become
fireable
and
it
can
proceed
with
its
step.
So,
meanwhile,
the
imperative
program
is
continuing
to
block,
but
the
divide,
node
can
then
finish
its
computation
and
place
its
result
on
the
output
port
and
prepare
it.
B
So
it's
now
at
the
input
port
for
the
multi
X
is
going
to
show
up.
Both
programs
are
going
to
finish,
but
the
dataflow
program
had
a
head
start,
and
this
doesn't
sound
like
much
in
the
context
of
simple
integers.
But,
let's
imagine
for
a
moment
that,
rather
than
simple,
integers,
x
and
y
are
instead
extremely
large
vectors,
so
that
now
those
some
divide
and
multi-vector
operations
now
we're
talking
about
real
savings.
B
If
you
can
get
every
element
in
that
giant,
Y
vector
divided
by
10,
while
the
X
vector
is
taking
its
own
sweet
time
showing
up-
and
this
illustrates
an
inherent
strength
of
dataflow
programs
over
von
Neumann
style
programs.
Data
flow
naturally
reveals
opportunities
for
parallelism,
and
this
arrives
arises
from
two
factors.
B
B
B
B
So
in
a
sense
you
can
think
of
dataflow
programming
is
a
subtype
of
functional
programming,
although
really
it's
the
nodes
themselves
that
are
functional,
that
the
complete
data
flow
graph
is
not
necessarily
with
all
of
the
advantages
of
functional
programming,
or
at
least
some
of
the
advantages
of
functional
programming
in
terms
of
provable
isolation
and
immunity
from
side-effects,
the
nodes
represent
functions.
The
input
ports
represent
the
formal
parameters,
so
this
programming
paradigm,
where
we
represent
programs,
is
directed
graphs.
Why
call
that
dataflow?
B
As
we
talked
about
before
we
got
started
a
that
is
flowing
everywhere
in
every
program?
But
perhaps
let
me
flip
that
on
its
head
and
say
why
not
dataflow?
We
have
this
powerful
programming
paradigm,
where
we
represent
programs
as
two
directed
graphs,
because
directed
graphs
are
a
fantastic
construct
for
representing
data
dependencies
and
many
advantages
flow
from
having
this
capability.
So
we
need
a
name
for
this
paradigm
and
well
this
technique
of
specifying
how
data
flows
seems
to
be
a
compliment
to
the
von
Neumann
paradigm
of
specifying
how
control
flows.
B
So
why
not
contrast
it
with
control
flow
and
call
it
data
flow,
because
arguably
dataflow,
programming
and
von
Neumann
style
programming
are
two
extremes
of
a
continuum
we
have.
The
program
is
directed
graph
versus
the
program
of
seek
as
a
sequence
of
instructions.
We
have
execution
following
the
satisfaction
of
data
dependencies
versus
execution
following
the
advance
of
a
program
counter.
We
have
maximum
memory
isolation
thanks
to
the
constraints
of
elements
within
the
graph
versus
a
starting
point
of
globally
updatable
memory.
B
So
this
continuum
is
similar
to
the
continuum
between
imperative
and
declarative
paradigms,
similar,
but
not
quite
in
an
imperative
paradigm.
You
tell
the
computer
exactly
what
the
sequence
of
events
instructions
that
should
execute.
Well,
the
clarity
of
paradigm.
You
give
it
a
set
of
goals
and
let
the
computer
figure
out
the
details.
The
declarative
programming
is
really
a
higher
level
of
abstraction,
but
a
data
flow
graph.
A
data
flow
directed
graph
is
not
necessarily
a
high
level
of
abstraction.
B
Data
flow
was
in
fact,
originally
conceived
to
be
at
the
instruction
level
and
the
original
purposes
of
dataflow
programming
languages
was
to
power
data
flow
hardware
in
the
1970s,
which
would
compete
with
von
Neumann
hardware
and
for
which
data
flow
graphs
would
serve
as
machine
code
in
his
1977
Turing
award
lecture,
John
Backus,
the
designer
of
for
Fortran
posed.
The
question
can
programming
be
liberated
from
the
von
Neumann
style
and
Backus,
whose
aim
was
primarily
to
advocate
for
the
functional
programming
paradigm
but
dataflow
hardware.
B
It
was
mentioned
multiple
times
in
his
paper
as
an
alternative,
contemporary
alternative
and
competitor
to
the
von
Neumann
architecture,
and
this
is
how
early
dataflow
programming
languages
developed
as
support
for
dataflow
Hardware
conventional
imperative
languages
were
modified
by
limiting
support
for
variable
assignment
by
fiddling
with
scope
and
locality
and
when
the
results
could
be
compiled
down
to
data
flow
graphs.
Again,
data
flow
graphs
as
the
machine
code
of
dataflow
Hardware,
those
programs
acquired
wondrous
properties.
B
Regrettably,
though,
one
answer
to
backus's
tormented
question
is
dataflow
ain't,
gonna
save
ya,
because
designers
in
the
1970s
ran
into
seemingly
intractable
problems
with
dataflow
hardware,
and
this
is
why
you
don't
see
dataflow
hardware's,
competitor
2,
if
I'm
not
even
Hardware.
Today,
one
of
the
biggest
problems
was
that,
although
directed
graphs
could
reveal
potential.
Fourth,
theoretically,
infinite
parallelism,
of
course.
In
reality,
the
number
of
parallel
operations
that
Hardware
can
support
is
always
finite.
B
B
How
you
know
when
your
input
tokens
have
arrived
and
a
node
has
become
fireable-
is
a
complicated
story
that
I've
chosen
to
skip
over
tonight.
For
the
sake
of
brevity,
they
describe
a
couple
of
systems
in
the
paper
for
actually
doing
that
they
don't
describe
the
hardware
that
actually
implemented
those
instructions,
but
they
are
rather
elaborate
systems
that
say
free
require
a
stream
of
information
to
be
flowing
the
other
direction
to
allow
nodes
to
know
when
they
are
becoming
fireable.
B
A
different
sort
of
problem
arose
in
that
the
constructs
for
iteration
in
dataflow
programming
languages
were
often
verbose
and
awkward.
This
really
becomes
obvious
when
you
try
to
represent
iteration
visually
as
we'll
see
in
a
moment,
and
that
meant
that
programmers
accustomed
to
imperative
constructs,
they
found
it
challenging
to
adapt
themselves
to
the
looping
idioms
in
dataflow
programming
languages,
but
the
biggest
problem
was
really
the
success
of
the
competition
von
Neumann
processors
were
increasing
at
the
pace
of
Moore's
law.
B
Pipelining
speculative
execution,
optimizing
compilers
all
made
it
possible
to
discover
and
exploit
parallelism
within
the
context
of
von
Neumann
and
dataflow.
Just
couldn't
keep
up,
and
so
data
flowed
development
flagged
for
a
few
years
during
the
1980s.
Until
some
new
areas
of
interest
rose
to
prominence
in
the
1990s
coarse-grained,
what
we
call
coarse-grained,
dataflow
and
hybrid
dataflow,
so
on
the
left,
we
have
an
implementation
of
the
factorial
function
in
a
data
flow
directed
graph
with
nodes
representing
machine
level
instructions.
B
B
Actual
control
flow
in
general
is
a
weakness
of
or
control
flow,
is
a
weakness
of
visual
programming
languages
in
general.
It's
not
just
data
flow,
but
data
flow
has
this
problem
along
with
many
other
visual
programming
languages,
but
looking,
but
looping
works
just
fine
in
text-based
imperative
languages
or
for
that
matter
and
text-based
functional
languages.
B
Indeed,
the
task
of
writing
a
reliable
factorial
algorithm
is
perfectly
well
suited
to
imperative
languages.
So
why
not
just
code
that
node
up
in
an
imperative
language,
instead
of
fiddling
with
something
like
that
monstrosity
on
the
left
and
then
let
some
high-powered
von
Norman
compiler
optimize?
It
to
within
an
inch
of
its
life
and
then
why
not
just
stuff
the
result
of
that
into
that
abstracted.
Factorial
node
there
on
the
right
that
node
on
the
right.
There
is
still
a
well-behaved
dataflow
node.
There
is
no
global
memory.
B
Access,
well-behaved,
local
variable,
isolation,
parallel
instances
that
are
always
possible,
so
we
can
still
apply
data
flow
analysis
at
levels
above
that
factorial
node,
and
we
don't
need
to
apply
fine-grained
analysis
and
these
techniques
of
hybrid
data
flow,
and
course
great,
hybrid
data
flow
referring
to
inserting
nodes
which
are
written
in
imperative
languages
or
other
languages
into
data
flow
graphs
and
coarse-grained
data
flow
where
the
nodes
represent
something
greater
than
machine
instructions.
Those
concepts
are
what,
along
with
improved
visual
programming,
editors,
revitalized,
data,
low
flow
research
and
development
in
the
1990s.
B
So
with
that
in
mind,
let's
return
to
our
Pig
program
and
putting
data
flow
to
work
in
the
problem,
space
of
crunching
big
data.
So
what
this
pig
program
does
is
read.
N
lines
of
text
from
a
text
file
like
Pat
was
complaining
about
earlier.
A
lot
of
these
programs
are
designed
to
take
text
input
and
it
tokin
eise's.
Those
tokenize
is
those
lines
at
word
boundaries
and
then
updates.
A
global
mapping
of
words
to
word
counts.
That's
the
representation
of
the
dataflow
program
on
the
right
there.
B
That
actually
is
not
the
full
data
flow
graph.
It
would
be
more
complicated
than
you
see
here.
Mutating
a
data
structure
is
disallowed
in
pure
data
flow.
In
the
same
way,
it
is
in
functional
programming,
so
you
would
have
to
employ
in
order
to
get
looping
constructs
and
data
flow.
You
have
to
employ
a
trick
like
what
they
described
in
the
paper.
Is
your
your
doing
in
what
looks
like
a
for
loop,
but
instead
of
updating
the
program
they
actually
say?
B
A
B
So
I'm
not
showing
that
here
in
there,
but
so
now,
let's,
but
this
is
enough,
so
we
can
look
at
how
Pig
implemented
this
program.
What
it's
done
is
assigned
along
the
top
there
one
worker
per
line
to
the
task
of
tokenization,
because
it
is
recognized
that
the
task
of
tokenization
is
parallelizable
and
then
the
output
from
that
tokenization
gets
sent
to
one
of
two
counting
workers.
B
The
one
on
the
left
is
handling
the
words
from
the
front
side
of
the
alphabet,
and
they
weren't
on
the
right
is
handling
the
words
from
the
back
side
of
the
output
alphabet.
So
we
have
had
a
little
lamb'
on
the
left
and
we
have
Mary
was
white
snow
on
the
right,
and
what
this
example
program
and
illustration
illustrates
is
how
dataflow
the
dataflow
paradigm
lends
itself
to
programming
in
a
cluster
nodes
in
a
cluster
like
nose
in
pure
dataflow
directed
graph.
Do
not
share
global
state,
at
least
not.
B
Naturally,
you
have
to
have
you
know
they
don't
have
the
they're
on
different
machines,
so
they
don't
have
to.
They
have
to
pass
messages
between
them
and
the
arrival
of
data
at
a
node.
In
a
cluster
typically
activates
that
node,
which
is
the
same
model
as
we
have
in
dataflow
with
the
activation
of
a
notice,
the
data
arrives
that
it
is
input
ports,
so
in
a
pure
model
of
dataflow,
the
nodes
are
considered
to
be
FIFO
queues
of
infinite
capacity.
That
doesn't
work
well
in
practice,
because
execution
is
too
controlled
by
external
events.
B
If
too
many
events
arrive
too
many
events,
meaning
tokens,
then
you
exceed
the
capacity
of
the
queue
and
your
slowest
node
bunches
up,
but
nevertheless,
dataflow
analysis
reveals
opportunities
for
parallelism
and
that
works
well
for
managed
workers
operating
in
a
cluster,
and
this
is
truly
coarse-grained
dataflow
extremely
coarse-grained
data
flow,
since
the
operations
are
entire
service
workers,
it's
also
hybrid
data
flow,
since
it's
not
Turtles
all
the
way
down.
It's
not
data
flow.
All
the
way
down.
Some
of
the
innards
of
these
workers
are
implemented
using
the
fundament
languages.
B
Summerall.
Ok,
so
now
going
from
Big
Data
now
we're
going
gonna,
zoom
down
and
level
we're
now.
Looking
at
DSP
systems
here
is
a
simplified
version
of
the
pure
data
theremin
to
MIDI
program.
I
showed
you
earlier
on.
The
left
is
a
version
assembled
in
the
PD
visual
editor,
which
is
what
people
are
expected
to
work
in
on.
The
right
is
the
source
code
which
is
generated
by
that
editor.
When
we
examine
the
source
code,
we
find
that
it
is
pretty
much
a
traditional
representation
of
a
directed
graph
at
the
top.
B
We
have
a
number
of
elements
which
correspond
the
nodes
and
at
the
bottom
we
have
connect
elements
which
represent
arcs
between
the
nodes.
So,
just
looking
at
those
that
connect
the
that
first
one
says
oo,
1
Oh.
What
that
represents
is
the
first
2.
The
first
number
is
the
first,
the
identifier
for
the
first
element.
Then
the
second
number
is
the
port
number
on
that
element.
The
third
number
is
the
identifier
of
the
element
that's
pointing
at,
and
the
fourth
number
is
the
port
on
that
element.
B
So
we
are
moving
from
the
first
in
that
that
first
connector
of
corresponds
that
first
vertical
line
there
and
there
would
be
an
arrow
if
this
was
a
directed
graph,
but
that
all
of
the
flow-
and
this
thing
is
from
top
to
bottom.
We
start
at
the
analog
to
digital
converter,
which
is
that
ADC
at
the
top,
and
then
it
passes
data
via
that
first
connect
arc
to
the
fiddle,
object
there
and
that's
what
that
Connect
does
it's
connecting
from
the
object
0
at
the
first
port
to
object
1
at
the
first
port?
B
Ok,
then,
we've
got
this.
What
the
fiddle
object
does
is
it's
actually
doing
all
the
heavy
lifting
in
this
program?
It's
generally
using
FFTs
internally
that
generate
raw
pitch
and
amplitude
information
converting
from
the
time
domain
to
the
frequency
domain.
The
after
that
we
have
an
unpack
object
which
does
destructuring.
Basically,
a
utility
node.
The
Moses
object
is
a
gate.
It's
you,
the
is
it
parts
things
it's
a
threshold.
B
B
Then
we
have
that
node
and
amplitude.
Those
are
actually
slightly
different.
Those
are
basically
just
readouts.
If
I
add
PD
running
you
would
send.
I
was
actually
doing
that.
You
would
see
the
note
that
would
be
changing
as
the
input
changed
and
then
control
out.
That's
just
outputs
for
MIDI
channels.
B
So,
while
these
objects
are
nowhere
near
the
size
of
a
worker
in
our
pig
powered
cluster,
they
are
still
much
larger
and
more
complex
compared
to
the
machine
level.
Instructions
of
that
fine-grained
data
flow,
and
just
like
that
Pig
example.
These
nodes
are
not
just
coarse-grained
data
flow,
but
they're
hybrid
data
flow
as
well,
because
pure
data
is
fiddle,
unpack,
Moses,
etcetera.
Those
are
all
implemented
using
good
ole
von
Neumann
C.
B
So
dataflow
has
found
a
niche
in
DSP
specification
for
a
few
reasons.
One
is
that
the
directed
graph
is
an
apt
physical
met
or
a
metaphor
for
the
physical
elect
for
electrical
signals
flowing
in
a
physical
circuit
in
electrical
circuit.
The
signals
only
flow
through
wires,
or
at
least
in
a
well-behaved
electrical
circuit.
The
nodes
only
and
flow
through
wires,
there's
no
analog
for
mutable
global
variables.
B
And
another
reason
that
dataflow
is
copasetic
with
DSP
is
that
dataflow
lends
itself
to
a
particular
kind
of
analysis,
called
synchronous,
dataflow
and
under
synchronous
dataflow.
The
data
flow
graph
is
compiled
to
a
fixed
schedule
where
every
node
takes
the
fixed
number
of
cycles
and
the
number
of
tokens
consumed
is
with
each
cycle
is
also
known
in
advance.
B
Not
all
dataflow
programs
can
actually
be
expressed
within
the
constraints
of
synchronous
dataflow,
and
this
is
more
a
general
thing
that
there's
there's
different
flavors
of
dataflow
there's
a
number
of
them,
including
synchronous,
dataflow
and
the
various
programming
languages.
I
heard
LabVIEW
mentioned
earlier,
that
they,
some
of
them,
require
that
the
directed
graphs
be
acyclic.
Some
of
them
have
are
not
pure
data
flow
like
PD
with
its
global
variables,
but
nevertheless
they
allow
greater
and
lower
amounts
of
lesser
amounts
of
expressivity.
B
So
you
know
if
you're
gonna
do
synchronous
dataflow.
That
means
you're
gonna
exclude
some
number
of
potential
potential
data
flow
programs,
but
it's
a
powerful
technique
for
creating
hard
real-time
applications
and
audio
DSP
is
such
an
application
with
hard
real
time
constraints.
So
the
hard
work
is
all
done
at
compile
time.
You
find
a
provisional
schedule,
you
simulate
execution,
you
analyze
for
deadlocks
and
so
on,
and
then
at
runtime.
There
just
needs
to
be
pre
allocated
space
to
accommodate
a
fixed
quantity
of
tokens.
B
You
can
compile
data
flow
down
to
if
something
which
is
fairly
predictable,
but
again,
this
is
a
hybrid
technique.
Dsp
operations,
like
the
one
in
the
PD
program
that
I
just
showed
you
are
typically
written
in
a
von
neumann
language,
but
because
the
higher-level
program
can
still
be
represented
as
a
true,
pure
dataflow
directed
graph.
We
enjoy
all
the
benefits
of
data
flow
analysis,
and
this
is
the
thought
that
I'd
like
to
leave
us
with
this
evening.
B
The
von
Neumann
architecture
has
held
on
stubbornly
and
is
not
going
anywhere
anytime
soon,
yet
with
Moore's
law,
tailing
down
and
new
performance
coming
from
additional
parallelism,
whether
that's
from
cores
or
clusters,
we're
all
scrambling
for
ways
to
adapt
our
programming
paradigms
to
better
take
advantage
of
those
parallelized
resources.
It's
been
becoming
painfully
obvious
that
parallelism,
which
is
not
provably
correct,
does
not
scale
well
to
complex
projects.
You
inevitably
wind
up
infested
with
heisenbugs
and
other
vermin.