[MUSIC PLAYING]
Hello, my name is Craig Upson from Silicon Graphics,
and I'm here to talk today about visual programming and data
flow environments.
Visual programming is not a new technique--
it's been around for quite a while--
nor is data flow a new technique.
But the application of the two of them,
the combination of the two of them
together is something that has, in the last four or five years,
become quite prevalent in computer usage,
defining new paradigms and in computer programming
environments, and in addition, new paradigms
in computer usage environments.
So the contents of this talk are a brief background
to visual programming, a background
on data flow with more specific details
about certain implementations, and examples
that illustrate the application of these techniques.
So this is not an exhaustive survey of the field,
but more of an introduction.
A survey would take, of course, several lectures.
So what is visual programming?
Visual programming is really one of two major techniques.
One is the application of visual languages to traditional
computer programming, meaning that instead
of, as an alternative to using a traditional computer language
like C or C+ or Fortran, using a visual language
in the programming step.
The other application of visual programming
is the application of visual languages
to traditional computer usage.
How do end users--
how do users use computers without programming?
And that is through a new paradigm,
through this different paradigm, which is visual programming.
Well, why is visual programming of interest,
or why is it becoming more popular as the years go by?
The reasons primarily are that the computing environment
in which we live is really becoming much more complicated.
Computers are getting much more complicated.
The environments in which we compute
are much more complicated.
We're now very much used to having several computers
that we are all networked together.
And so running processes on a variety of different machines
is very commonplace.
This makes the environment much more complicated,
especially in a heterogeneous environment,
where one machine is substantially
different than another.
In addition to that, there is now a large application
backlog, meaning that the number of computer users
have greatly outstripped the ability of computer programmers
and application developers to provide applications
that meet their needs.
So these three reasons really give rise
to this last point, which is this need
for reusable components of applications,
the ability to rapidly build an application by plugging
together little, smaller pieces, the final result of which
is a usable application.
This is more of a plug and play technique of combining
some function which is a piece of a program,
plugging it into another component which
is another piece of a program, and together, this collection
of pieces form an application.
And by doing so, we essentially deal with the application
backlog by empowering end users to build
customized applications for their needs
without having to program.
So let's talk about the basic types of visual programming
systems.
They fall into, primarily, three categories.
The first is diagrammatic systems.
These sort of evolved from old flowcharts
from the '50s and '60s and '70s even.
And they represent systems that, or language that is,
or an application that's built with this diagrammatic language
where you might have blocks that you plug together
that are if-then-else statements, et cetera.
There are also iconic systems.
The second type is iconic systems.
And now, these aren't necessarily flowchart-based,
but they're more building blocks that
have iconic representations.
And the third one is form-based systems.
They are outcomes of the big emphasis
toward form-based interfaces from the 1970s,
and early '80s, for that matter.
And the uses of each of these three systems
are primarily in two different ways.
One is as a substitute for traditional language.
And as I said before, the second is to create new applications.
So one is a lower level kind of language substitute,
and the other one is much higher level application substitute.
So let's look now at each of those three systems--
diagrammatic systems, iconic systems,
and form-based systems.
In this example, we see a diagrammatic system,
basically the Nassi-Schneiderman representation of--
in this case, it happens to be, how do you represent
diagrammatically n factorial?
So this is basically a computing strategy
for how to represent n factorial.
You see on the top of the diagram,
this top wedge is basically an if statement.
Is the number n-- where n is replaced
with a number, obviously-- greater than 1?
If not, you take the left branch,
which is the false branch, and the factorial is equal to 1.
And you return that value for the factorial calculation.
If, indeed, it is greater than 1,
then you take the right branch of this diagram.
And you start off, and you initialize
the factorial variable, n fact equal to 2,
and then do a loop from 3 to n, accumulating n as you go,
accumulating i as you go, and then you return n factorial.
So it is, instead of a text-based language,
I mean, it's actually a combination
of a text-based and diagram-based language.
This is just one glyph of this language
in a diagrammatic system.
If we look at the next base, the next type of system,
these are iconic systems.
This is an example from IRIS Explorer, which
is the demonstration application that we're going to be
using throughout the talk.
In this diagram, you can see a series
of boxes that are connected together with wires.
Each of these boxes represents some computational function.
A box or module executes and sends its data downstream
to other modules that are connected
from a left-to-right representation.
So if we look at this image, you'll
see on the far right a box that has--
which you probably can't read on your screen--
the word render, which is the renderer in this system.
It contains an image, which is the product of this data flow
environment.
So here the level of the language is much higher.
It's now not individual assignment statements
or operators, but more functions or perhaps even applications
that are embedded into each one of these boxes.
So each box now has ports--
that means places to connect data into and connect data out
of--
in addition to controls, and we'll talk about that later.
The last, the third system, is a form-based system.
And probably the best example of that
are spreadsheets, which are probably
the widest used application on all computers.
Again, it's a two-dimensional language.
In this case, it's a 2D or two-dimensional array of cells,
and one performs arithmetic on cells,
performs calculations on cells.
And this is a simple example of a spreadsheet.
As I said before, there are two basic uses
of visual programming.
One is as a programming language itself,
and the other one is as a vehicle
for building applications.
So let's look at the first one, which
is as a programming language.
And here the goal is really to simplify
the act of programming.
Again, as computers get more and more
complex as large multiprocessors become more and more prevalent,
the task of programming becomes more and more difficult
and, in fact, excludes more and more people from programming.
So the goal here is to simplify the whole process
of programming.
That means, typically, these are used
for small program development.
And I think you'll see why that is as we go to the next slide.
But they're also used as a programming teaching tool
for teaching people that have little or no programming
background, and that was indeed the first usage of them.
So these systems have been around for probably
the last 15 years or so, and they
represent the first application of visual programming usage.
And as I said, they're basically replacements
for a text-based language.
The grain size is something that we're
going to talk about quite a bit in the next few slides.
Grain size is really, what is the atom of a visual language?
What's the smallest thing that can
be connected to something else to form some syntactically
correct statement?
And the grain size for a programming language
is really the assignment statement or an operator.
And that's exactly what it is for visual programming
and programming language also.
Frequently, these systems are language-centered,
meaning there's been a fair amount of effort to build
visual languages around specific computer
languages such as Lisp.
And that's where a lot of the work has gone on in the past.
So some relevant examples here are Prograph, Tinkertoy,
VennLISP, which is basically a list Lisp-centered language,
and Hi-VISUAL.
This is, by all means, a short list,
because there's a lot of examples of visual programming
languages of this type.
And there are some references included with this tape,
so you can check that out too.
So let's look at one example from a system called Tinkertoy.
If we want to do the following operation--
which is add two numbers, A and B,
multiply that times a third number, C,
and then divide the whole thing by D--
in this particular language, in Tinkertoy,
you would build the structure as following.
A and B are integers that are both plugged
into this plus operator.
The result of that comes out the right-hand side
of that plus operator.
It is then multiplied by C, which is another integer.
The result of that is then sent to the divide operator
and divided by D. So as you can see in the slide,
on the top of the slide you see the traditional computer
language representation of the statement, A plus B
times C divided by D.
On the bottom, you see this visual representation.
And clearly, compactness is not one
of the goals of this system.
It's a very-- visual languages in general
consume an incredible amount of screen space.
And in this simple example, you can
see the ramifications of that.
So primarily, again, this is used for teaching tools, not
necessarily as a full-blown programming language.
Some of the problems that occur in systems such as this
are that it's very difficult to devise a visual representation
for complex operations.
How do you really represent a matrix multiply
or a matrix inversion?
With an icon.
In this case, the plus star operator and divide operator
are very well-known by everyone.
But it gets much harder as you get more complicated operators.
So let's look at the other side of this,
which is the application of visual programming
for application creation systems.
And here, the goals are much different.
The goals are, how do you simplify the application
building environment, how to build applications
easy, or at least easier.
And again, the reasons why these tools are more and more in use
are because the environments in which we compete
are much more complicated.
Multiprocessors-- massively parallel
processors add tremendous complications
to the programming paradigm.
Graphical workstations can add complications
to the programming paradigm if you
wish to adequately use them.
And then finally, how do you build
an application that will run in a distributed
environment on several machines, several potentially
dissimilar machines, machines that
have different floating point representations, et cetera?
So again, the goal here is to empower non-programmers
to create applications for themselves.
The distinction between this application
of visual programming and the previous application
is grain size.
Here the atom of composition-- when you build an application
system such as the [INAUDIBLE] [? Atom ?] of composition--
is using the function or subroutine level.
Now, each function or subroutine then
is connected together with some graph editor
to build a directed graph, which then is your application.
So some good examples of this are primarily from the Unix
domain; aPE, which came out of Ohio State University
and now is marketed by a company called
T-ara Visual; AVS, or the Application Visualization
System, marketed from ABS, Inc.; IRIS Explorer,
which is a system that we're going to use here
for demonstration; and Khoros from the University
of New Mexico.
There has been an awful lot of work lately, at least of late,
in the Unix world, although there are some notable examples
in the PC and Macintosh world, primarily LabVIEW
from National Instruments.
So let's look at an example from Khoros
again, from the University of New Mexico.
And in this diagram, we see a closeup
of the Khoros graph editor, which is called Cantata.
So as you'll notice, there are a number
of boxes that are connected together.
Boxes have glyphs on them.
They have ports, which are probably
impossible to see in the view that you see on your screen.
And these are all connected together with wires
to form a data flow diagram.
And in this example, we're looking
at acquiring an in utero sonogram
and looking at the processing of that
to isolate the left and right ventricle of a premature baby,
which are the two green items that you see
in the center of your screen, or the two red, small items
that you see in the bottom right.
So in other words, this is a graph-based system.
There is a graph editor, a graph creator,
in this case called Cantata, that
builds this directed graph.
You then instruct the system to fire, and in this case,
modules execute, deriving data in each of the processes
and sending data to the bottom, to the last glyph in the chain
to produce the data that you've requested.
So there is another term, which is different,
although quite close and conceptually quite related
to visual programming, and that's program visualization.
In this case, the goal of program visualization
is to really understand the execution of an existing
program.
So a program that's written in a traditional language,
such as C or C++ or Fortran, is then instrumented.
And the structure of this program
is represented visually to aid in the comprehension
of the calling order, et cetera, or where a program has
been an awful lot of its time.
So it's really meant to take existing programs
and to use program visualization to understand the execution
of the program itself.
Now in addition, the reason it's quite related
is that in addition to this, most visual programming systems
do incorporate program visualization.
And you'll see that in the examples
that we have in just a little bit.
So that's the background on visual programming.
Now I want to talk a little bit more about data flow
and how it relates to visual programming.
So let's get a little bit of background on data flow.
Data flow is, again, something that's
been around for quite a while.
It's nothing new.
In fact, there have been computers
that have been built around data flow architectures.
But in the software systems, essentially, data flow
is a graph that consists of modules.
Modules are, in general, functions
with inputs and outputs.
The inputs are gathered and are processed by the function
to produce outputs.
All these modules or functions are connected together
into a directed graph, typically an acyclic graph,
and build an application.
So modules typically, as I said before,
have inputs and outputs.
They also have interactive controls,
at least in the systems that we'll talk about today.
These controls modify the operation of the algorithm
that the module has on its inputs to produce its outputs.
Data is transported between modules via connections that
are built in a graph editor.
In the previous example from Khoros,
you saw lines connecting modules.
Those were created-- basically, that is the data flow itself.
So it is essentially, in general, a monopartite graph
where you have modules which are represented as icons, wires,
which are the data transport mechanisms.
Now, there's a myriad of complications
and different ways of doing this.
But it sort of all boils down to, when do modules execute,
and how do they transport, and how is data transported?
So typically, modules execute when their inputs
are fully satisfied.
The question is, who determines when
inputs are fully satisfied?
And we'll talk quite a bit about that to come.
So from this point on in the talk,
I'd like to kind of narrow down on a specific class
of application creation systems.
And it's not really a general presentation
of the whole topic, but more one focused
on systems such as these.
The major components in an application creation system--
it's data flow based--
are the following.
There is a graph editor, as we've talked about before,
and I'll show you how that works in a little bit.
There is what I call the life support system or the execution
environment of how modules execute.
Typically, modules are not--
even if they are separate processes,
they are not processes that are really self-sustaining,
in that they have to be connected to someone else,
or connections have to be made for them to really form
a full-fledged application.
So there is this kind of life support
system that is used, which we call the execution environment.
It also helps to determine when modules fire and when they
don't.
There's also a component library.
In the visual language there are these atoms or modules.
There may be 50 of them, there may be hundreds of them,
there may be several thousands of them.
And that is what is the component library
is used to select modules from.
So it's essentially a database where
you might want to make queries on the component library
to say, give me all the modules that accept this type of data
on their inputs, or et cetera, or give me
all the modules that were made by this institution, et cetera.
The last major component is extension tools,
that is, how are new modules built,
how they add it to the system.
Do you need to be the developer of the system,
or can end users add new modules to the system?
The issues that come into play here
are, do you need to program in a traditional programming
language to add new modules to the system?
Or are you even prevented from using a traditional programming
language?
Can you get access to a programming language,
or are you kept in the same visual programming paradigm,
in which case, if you are using a traditional programming
language, then there is, indeed, a paradigm
shift going from the visual programming environment
to this traditional programming language.
And then the other aspect of extension tools are,
how does one import and export data?
These systems tend to be quite isolated,
and getting data into the system or getting
data out of the system can at times
be difficult for non-programmers to do.
So let's talk about the graph editor now.
Again, this is what is used to create
these data for the graphs.
The goal of a graph editor is to be
able to provide you with components from a component
library that you can grab with a mouse,
drop down on the graph editor pallet,
connect modules up to form this graph.
So typically, modules have a variety
of different representations as you go from system to system.
From its simplest representation,
a module could be just a name, the name of the function
that you want to use, with ports that allow you to connect it
to other modules in the system.
Or it can have an icon that represents
more of a step in a visual language,
some iconic representation of the operation
that that module performs.
Or it may even have controls on that icon
itself, on that box itself, that allow you to manipulate
the algorithm of the module.
So modules are wired together to build these directed graphs.
And in general, the graph editor is a very interactive support
utility, in that you can modify the graph at any time.
It's always live, it's always running.
So you can add a new module to the system, take a module away,
and the graph will automatically recompute,
or the environment will automatically
recompute the application.
So let's go to an example here, which
is from IRIS Explorer from Silicon Graphics.
So what you see on the screen now,
on the upper portion of the screen,
is a graph editor on the right-hand side,
and on the left-hand side, a component
library where all the components that we wire together reside.
So you grab a module from the component library,
and you see this--
they just have names on them.
Drop it down on the palette of the map editor.
You can grab another one and drop it down also.
In this system, modules--
and I'll just move it around here so we can zoom
in on the upper right-hand quadrant--
you can see that a module has a name, which is, again,
probably not readable here.
But it also has widgets attached to it.
In this case, there is a text type-in,
and I'll type in the name for a file,
assuming that I get the right file name.
And now, the way modules are connected
to each other are by clicking on a port button
to select the port that you want.
This particular module reads an image from disk.
We select that, come over here and select an input port
from the module that's going to display
that image to the screen.
So here we have the image, and it
happens to be this image of Africa shot from a satellite.
Zoom in on it a bit, and you can see
the image of what is the simplest data flow
diagram possible, one module reading data from disk,
executing, firing, sending that data to another module which
displays it.
So in this example--
let's go back in and re-execute the module
that reads data from disk by selecting a Fire Now menu item.
So you notice that the module lights up yellow when it fires.
The next module downstream fires after the first module
is completed, and the whole graph executes.
So that's an easy example of, or a very trivial example
of what we're talking about.
Now let's add another collection of modules that have been
preconfigured to perform some--
not image processing, but rendering capabilities,
and so we can connect from that existing module that reads data
off of disk into other modules.
And we're going to make one more connection.
And now that entire chain of modules
executes, fires, and displays now
what appears to be an image, but indeed
is really a three-dimensional entity
that we can rotate and zoom in on.
So what we're seeing here is the ability
of the system to allow you to modify the graph at runtime.
And essentially, everything is live.
In fact, it's difficult to make things not live.
So in this example, we have the graph executing.
One branch of the graph is just displaying an image on disk.
The second branch of the graph is taking that image,
displacing it in a normal direction based
on the luminance of the image, and building this height field.
So if we look edge-on on this image,
you can see that there is actually displacement.
And in fact, we can modify the amount of displacement
by changing a dial on the graph.
New models execute downstream from that dial change.
And now you can see a little bit more vertical displacement
of that map.
Let's talk a little bit about the implications of the graph
editor itself.
When does this work?
When doesn't it work?
What are the limitations of, in this case, visual programming?
So the graph editor is a very useful entity
when the number of items that you're going to connect to
is relatively small, meaning that when
you're talking about somewhere around 10 or 15 modules.
That's probably the upper limit of really the visual complexity
that one wants to really deal with in a visual programming
language.
From the earlier example that you
saw of the language-based example from Tinkertoy,
there were four atoms that were connected together.
And you could imagine that if you had 50 of those,
it would be very difficult to understand what's going on.
And that is indeed the problem here also.
If you have 50 modules connected together in a graph,
it resembles spaghetti and is pretty much uninterpretable.
So somewhere around 15--
10 to 20 modules is basically the upper limit
of visual complexity.
If you have atoms or modules that
are too primitive, then building a usable graph
requires too many of them.
If you have atoms or modules that are too specialized,
then it's very difficult to interconnect modules together.
So this kind of seven plus or minus
two rule really applies here, in that around seven to 10 modules
is a very comfortable feel.
So essentially, what you're trying to do
is always balance this visual complexity
with the functionality that you need for an application.
And this leads the next point of, basically, hierarchy.
Is the graph editor--
does it support the ability to take a collection of modules,
abstract them, group them together, abstract them,
and build a single visual representation?
So let's go back to that example that we were using before.
So read in the image that's going to be read from disk.
Now read in the other, the next collection of modules
that we had previously saved.
Connect everything up again.
Again, when the module executes, it
turns yellow, indicating execution.
So here we have a data flow diagram
that is relatively simple.
There are only five modules in it.
The question is now, can we take individual modules and group
them together?
So let's take all the modules except for the last renderer
and group them together, building
a much simpler diagram.
And so now we still have the data flow paradigm.
And this new group, which is right here,
shows you that you can collapse all these things, all
these modules, into any groups and build
a hierarchical representation of your data for the diagram.
This case is a rather trivial example,
but we'll talk about some others later
on that are much more complex.
So what happens when you connect two modules together?
There are two different possibilities in graph editors.
One is, does the graph editor help you
in deciding what is a valid connection,
or does it permit any connection whatsoever between two modules?
So this is basically the strong typing issue.
Some graph editors are strongly typed,
mean that they will permit only legal connections between two
modules.
So not only does the graph editor
prevent you from making illegal connections, but in most cases,
it will direct you visually as to what connections
are permissible in which case.
This is all done at connect time.
Most systems also have verification at runtime
when the data flow environment is actually
executing, in which case, there is runtime checking of data.
And in this case, the data has to be self-describing.
So when a module receives it, it knows that this
is data of the wrong type.
The other possibility is no type checking whatsoever.
And this is, of course, much easier
to implement a system of this type.
It's certainly much more flexible
for advanced users, in that they can do all kinds of things.
You can always find a hack for what you're looking to do,
but it is always--
it's error-prone for all users.
So let's talk about data types now for a moment.
This determines really when connections are legal.
In data flow environments or in visual programming-based data
flow environments, there are a couple of different choices.
One is you can have a restricted environment, which
means you probably have a smaller number of data
types, which the graph editor uses for type checking
at connect time.
In this case, you can shield end users
from all the details of these, the data type itself.
Or you can have a system which is completely open
and has no data types whatsoever, which
means that any two modules can be connected together,
but they won't necessarily be able to share data.
So most systems rely on restricted data types
for ease of use issues.
And again, just like the grain size of the modules,
there's another issue about how many data types are there.
If you have a system that has a very small number of data
types, then you have maximum interconnectivity.
If you can imagine a system that had only one data type,
then every module would be able to talk to,
communicate with every other module.
If you have a system that has hundreds of data types,
then the chance of being able to connect module A to module B
is a very small chance, and so you lose
this maximum interconnectivity.
But it's a very rich system.
So there's always this trade-off between a small number
of data types and large number of data types.
The more successful data flow application billing systems
around typically have a small number of data types,
perhaps, at most, 10.
These types are typically very abstracted also.
One common data type is an array,
a multidimensional array, that can be
used in its most abstract form.
So a module might produce a floating point
two-dimensional array on its output port,
and the module downstream might accept any type of array,
regardless of whether it's floating point
or two-dimensional or three-dimensional.
So these are more abstracted data types.
So now that we've covered the data type issue,
we need to talk about what really
is the structure of a module.
Is a module a separate process, separate Unix process?
Or are all the modules bound into a single substrate,
which then a controller determines
which modules execute?
So there's two issues here--
I mean, there's two possibilities here.
One is a monolithic approach, which
is all modules bound into the same process.
And it has its advantages and disadvantages.
In general, it can be much more efficient,
especially on machines where processes are expensive
or context which is expensive, in that there
is no context, which is simply basically
a function table of modules.
Modules become a function table.
In this case, it becomes much more
difficult to add new modules to the system, in that you have
to relink the entire system or rely on dynamic linking to add
a new module to the system.
And in general, parallelization is somewhat problematic also,
in that it's difficult to decide when modules
should be firing in parallel.
The other possibility is to have a separate process per module.
And in this case, the trade-offs are different.
Now you have to deal with context switching,
switching in one module over the next.
And that can be a killer on some machines like PCs, which really
don't support multi-processes.
The advantages are that parallelism is much easier.
In an operating system, such as Unix,
Unix will basically schedule modules for you.
And you no longer have the dynamic linking problem.
That is, when you as a user write a new module
and add it to the system, you simply
compile and link that module while the rest of the system
is in place.
So now, if we go down this path of picking one of these two
alternatives of monolithic versus separate processes,
we're going to go down--
the bulk of the rest of the talk is targeted
toward separate processes.
So then you need to talk about what is the data and control
mechanism of sending information between modules.
So there are two types of information
that are sent between modules.
One is control information, which says
you should execute right now.
You have your slot at the CPU, so now is the right time
to execute.
And the other one is, here's data
that I want you to execute on.
So in general, control is very low-volume data,
low-volume information.
It is simply, execute with some parameters, perhaps.
Data potentially could be a very high volume.
And the example that we saw before
of the image of Africa, that's an image that is probably
300 pixels squared.
When we turn that into polygons, it
ends up being, in that case, several hundred
thousand polygons.
And now, the motion of that data becomes a very relevant issue
in data flow in general.
The goal is minimum data motion, meaning
that you don't want to make extra copies of data
if you can avoid it.
And you don't want to transport data between processes
unless you can avoid it.
So the choices are now, do you piggyback the data
on the control, or do you use separate paths
for data and control messages?
If you piggyback data on control,
then the bottleneck becomes really
this large data transmission, if there is a central controller.
In that case, the data and the control
would need to be transferred back to a central controller
and then transferred back to the next process downstream.
Or do you use separate paths for data and control information,
in which case, you have more messaging,
but you now can allow for direct module-to-module communication
for data passing, and in fact, for control passing too.
So if we look at the next slide, here is a diagram of one data
producer, module A, in the center of the screen,
sending data downstream to module B and C. Now,
these may be separate ports on the output of module A,
or they may indeed be the same port.
So in essence, we see, in this case,
separate independent paths for control,
which is going between A and B and data, which
is along the yellow lines.
It could be that there is a central controller
in a system such as this.
And many data flow environments do have central controllers
that the controller would go from module
A-- module A would fire.
It would send control information back
to the controller.
The controller would then send that back down
to module B and say, OK, now it is time for you
to execute and do the same thing with module C.
So this brings up the next central question--
when do modules fire?
There are two possibilities here.
One is a central controller, and the other
is a control-free or asynchronous model.
In a central controller, the central controller
then monitors all data transmissions and all control
transmissions from modules.
So it is a party to all communication.
In this case, it's very easy to prevent extra firings
from modules.
But in general, it becomes the bottleneck in large graphs.
So if you have a graph that consists of 10 modules,
and you have one central controller--
if we're talking about separate processes now--
every time a module fires, it sends information back
to that central controller and does context switching,
maps out controller, and the controller sends a message now,
broadcasts a message down to all the modules
downstream from that first module,
telling them that they can execute.
So you can get an awful lot of communication.
Let's talk a little bit about extra firings.
In this very simple diagram of module A
communicating its data to module B and C, which both then
communicate their data to module D,
let's assume that module B is a slow module,
and module C is a fast module.
When A fires, B and C both get information about firing.
B is slow, and so it cranks and cranks and cranks.
C, if it's computing in parallel, is fast.
It finishes its data.
It sends it to D. D potentially fires,
because it has received new data,
and its inputs may be satisfied enough to fire.
When B finally finishes firing, it sends its information down
to D, and then D executes again.
But clearly, in this example, D should only
execute once whenever A fires.
So in a multi-process application,
it can be very difficult to determine,
and especially in a control-free application
environment can be very difficult to eliminate
these extra firings.
So let's look at what a central controller does.
When A executes, it sends its information,
its control information, down to a central controller.
That controller sends back--
sends a message now to B and says,
OK, now it's your slot at the CPU.
You can execute.
It sends a message to C. When B and C finish firing,
they send a message back to the controller,
and then the controller sends a message
to D saying that you can fire.
So you can see that, even in the simple diagram,
the central controller could easily be the bottleneck.
So what are the alternatives here?
The alternative is distributed control.
That means giving each module enough information
to decide when it should indeed fire itself.
This means that the execution algorithm or the firing
algorithm is much more complex.
Each module needs to know when its inputs are fully satisfied,
when it can expect new data on other ports that
may be related to ports that have already executed
and then fire, execute itself.
This minimizes the bottleneck of the center controller problem.
So if we look at this simple example, again, of A producing
data and sending it to B and C, and both
of them producing data and sending to D, when A fires,
it sends data and control to both B and C.
Both B and C then need to know--
need to be smart enough to know when they have enough data
and that no other data would be coming in on any other ports.
They then fire.
They send data down to D.
Let's again assume that B is a slow one, and the data from C
arrives to D first.
This means that now D has two ports, has two input ports,
one from C and one from B. It needs to decide,
am I ready to execute now or not?
So in some systems, data is tagged along with,
not only control information, but heritage information.
Now the data coming to D on the C port
would have tags saying that this data was produced by firings
of A and C. D would then look on its other ports to see,
are there any other dependencies on those ports
for data from C or A?
And it does.
It finds that it has one other port, which
has a dependency on B and A. So it invalidates the data
on that port and waits until new data comes in from B, because D
has enough information on the upstream topology
to know that that new data will be coming in on the B port.
And again, this ends up being a large complication
for distributed control algorithms.
But it more than pays off for itself,
due to the reducing of the central controller bottleneck.
So let's quickly talk about some details
and what are the issues that one needs
to be very careful about in building data flow
environments such as this and, primarily, the execution
environment.
The first and paramount is memory usage.
Data must be reference counted, meaning that when--
in that prior example, when A fires and sends the same data
to B and C, A needs to know, or the system needs to know,
when it can throw away that data.
If A was to fire again, it needs to know
that B and C have already consumed that data
and that A can replace that data with a new copy.
Memory usage in data flow systems is, by all means,
the most difficult thing to work with.
As you saw in the prior example, there was both fan-out
from-- the output of A was fanning out to two consumers,
and D had a fan-in on one port from two producers.
So you have to correctly deal with synchronization
on fanning in and out.
You have to eliminate the extra firings
that we just talked about.
And you have to minimize the context switching,
if there is a central controller or if the entire data flow
environment is all separate processes.
And again, to reemphasize, the big problem
in data flow environments is how do you
minimize data motion, how do you make sure
that no superfluous copies have been made, et cetera.
In our prior example, it's potentially--
it's possible that A could retain a copy of the data
that it sends to B, and B could retain a copy of that.
C could also retain a copy of that.
So you could potentially have three copies
of data floating around in that environment, when, in fact,
really only one is necessary, a shared version from all three
of those.
So you really have to minimize data copies and data motion.
Finally, other issues such as cycles--
how is it possible to connect the output of one module
back upstream to one of its ancestors' inputs,
and how do you deal with termination sequences
and initiation sequences for cycles?
And that also gets back to bidirectional data flow,
which is the last point.
Did two modules communicate with each other
in a bidirectional sense, or is data always
flowing in one direction?
Almost all the examples built so far
have single, unidirectional data flow.
So now, let's look at an example,
one final example of the system that we're demonstrating today.
Here is an initial data flow diagram, reading data
from a tornado simulation.
As we look in the bottom, in the lower right,
we'll see this data set, which is a contour surface,
and isosurface of a tornado.
This kind of yellowish structure here
is the locus of all points that have the same value
within this data set.
And on top of it is this blue, kind of fuzzy representation,
which is buoyancy information, throughout the simulation.
So what does it take to build this diagram, this application,
and how do we customize that?
So in this example, if we look at the upper right,
there are three modules on the left-hand side,
which are read data from disk.
One, the module on the lower bottom,
generates a color map to map the scalar field of buoyancy
into color space.
That then goes through a module which
creates a volume biometric data set of that
and sends that off to the renderer.
On the top half is another module that
reads another set of data from disk, creates the box
wireframe that you saw a second ago, and then also
that isosurface, that tan ISO-valued surface beneath it,
and also sends out to the renderer.
So for example, in this example, we
want to demonstrate the system to show how you can collapse
an entire application, this data flow diagram,
into a smaller collection of modules, which can then
be viewed in a much simpler context.
So let's take three modules-- the isosurface,
the wireframe, and the renderer-- group them together,
such as this.
Now we have a single group which contains output
from those three.
We'll edit that to build a user interface for the system
by exposing parameters or widgets that we want
to have controls on the system.
We'll layout those controls into a new control
panel, essentially a new face for the module, such as this.
Here is the rendering window, followed by one control
here, which controls the isosurface.
We then apply those changes.
And now we have a new module which
looks like the previous one, has the same interaction
paradigms as the previous example,
and now allows us to interact with the output
simulation in the same manner.
So now let's talk about how does this
apply to distributed heterogeneous environments.
What happens when we want to have
modules executing on a whole collection of machines?
This means we now have to deal with different data
representations, different floating point, different word
lengths, different alignment, for that matter.
We also have different shared resources now.
We can no longer use simply shared memory communication
for data on different machines, because there are no shared
memory representations.
And now we also have to worry about having brokers
on remote machines that deal with transporting
data, transporting control, or point-to-point operations.
And also we still have to deal with this issue
of, we have individual user interfaces,
graphical user interfaces per module.
How are those transported back to the local machine?
If we look at this example, here is now
a slightly more complex example from the other diagrams
that we've seen.
Module A and C are computing on your local workstation,
modules B and D are computed on some other machine, and E and F
on a third, remote machine.
Now in Explorer, modules all on the same machine
can communicate through shared memory,
therefore, minimizing data motion on a particular machine.
But, for example, the data that A communicates with B
must be transported across the machine, and a data
copy results.
Also some machines don't have shared
memory, machines like Cray.
Cray computers don't have shared memory.
So data copies are imperative between two modules
on the same machine.
So in reality, systems like this typically
have local agents and perhaps a central broker
that establishes communication between modules
and perhaps monitors data transmission.
So the blue boxes here, there is a separate process
which is a graph editor, which is
very important in maintaining interactivity
with the entire system, and then a central broker
on the local machine, which establishes local agents
on remote machines.
And those local agents are used for connecting two modules
together, killing a module, disconnecting two modules.
So let's conclude now by some discussion about,
does visual programming really work?
And it works in certain situations.
It works when the graphs are relatively simple
or if hierarchy is fully supported.
It also works when the datatyping is really effective,
meaning that typically this works
best for domain-specific, discipline-specific
applications.
This occurs in the computational sciences,
scientific visualization, image processing.
Some database systems have been built on visual programming.
When doesn't it work very well?
Well, it doesn't work very well for very
high-performance systems.
You'll never really be able to build a system that
will perform as high as a specialized application
by using data flow and visual programming.
It also does not work well for fixed functionality
applications.
Again, visual programming is best
used for applications where the configuration
of the application is not known by the original developer,
but is determined by the end user.
And finally, as a conclusion, what
are the limitations of visual programming?
Well, typically, it's difficult to scale a visual programming
graph to large applications.
And here, hierarchy is essential for any of this to work.
Once you have a large number of modules or atoms
that you're composing together, say in the thousands,
the component interface really becomes a limitation.
How do you find the module that you're really looking for?
You need a good component library paradigm.
You also, as I said before--
the efficient memory utilization is
very important for data flow.
Is there one copy of data per module per port?
Is data shared between modules?
These become crucial issues in data flow environments.
And finally, the issue is, there's
always a difference between prototyping versus production.
While data flow and visual programming
is typically very good for this exploration process,
as exploratory, how do I combine these things
in order to meet this one particular need?
It sometimes is difficult to transition
from this exploration process and the very flexible needs
of that to very specific needs of production of,
now that I've got the image that I want, how do I get a thousand
more of them and fast?
So those are the primary issues that one
needs to deal with in terms of limitations
for visual programming and data flow environments.
Thank you.
[MUSIC PLAYING]