[MUSIC PLAYING]
Hi.
I'm Kurt Keutzer, a professor of EECS at UC Berkeley
and today I'm going to talk about structural patterns
in parallelism.
So to put this in context, we've been teaching our pattern
language for some time.
The first step was we give a high level overview
OPL and software architecture.
Then we give a deep dive down to a subset
of the pattern language.
Then we give a complete overview of structural patterns
and how to paralyze them and that's what I'll do today
later we'll have another video where
we give a complete overview of computational patterns
and how to paralellize them.
A review of implementation patterns from their execution
targets and then we'll give a couple detailed case studies.
So let's do a review, a quick look at our pattern language.
At the top we have applications going down
to structural patterns, computational patterns,
a layer of parallel argument strategy patterns.
And we'll be looking at these two layers today.
Later we'll talk about implementation patterns
and execution targets.
Terms of patterns and architecting software,
once again, we go back and forth between identifying
the software structure, identifying
the key computations, we do this hierarchically
to arrive at the overall software architecture
of the application.
For example, here we have the software architecture
of a real large vocabulary continuous speech recognition,
which is again analogous to the design
of an entire manufacturing plant.
OK.
Hold onto your hat, here's a complete presentation
of our structural patterns.
Here's the inventory of the 10 structural patterns.
In previous videos, we've talked about pipe and filter,
iterated, MapReduce, but let's quickly review those again.
So once again, pipe and filter, her
we have pipes embodying communication,
filters are where the computation occurs.
Remember that the filters only see their inputs and outputs
and have no global state.
Examples of pipe and filter include the compiler
that you perhaps use every day, for me a logic
optimizer that I spent a number of years working on,
and in a previous video, we talked an image retrieval
system.
Second pattern is iterator pattern.
We begin with initialization condition.
We have a body, which a variety of functions
are performed asynchronously.
Before exiting the body, we synchronize
results of iteration and we then test an exit condition.
If we met this, we simply continue.
If we've not, then we iterate again.
Examples of this included are training and classifier
in our support vector machine training.
Thirdly MapProduce, again to us, it
means a map stage where computations are mapped
onto independent data sets.
And reduced stage for the results of the map stage
are summarized or produced.
Examples of this were included on the actual evaluation,
the distance from the frontier for feature vectors
and support-vector machine training.
Now a new pattern for us is agent and repository.
Now, the key to understanding agent
repository is to focus on the repository.
The repository is essentially where all the action happens.
It's also known as the blackboard.
So all the data initially begins in the repository
and the results of the computation
when using the agent repository are left in the repository.
Blackboard is also an interesting way
of thinking about it, in which a series of agents
come and write asynchronously on a blackboard
and whatever is left on the blackboard
at the end of the computation that's the result.
So these agents do not communicate among themselves,
but only communicate through the repository itself.
And finally to orchestrate all the actions of these agents
on the shared repository, we have a repository manager.
This schedules the access to this shared repository
and also aggregates results.
Some examples of this are--
if you look at the global optimization
and other optimizations with compiler,
we often see them operating on a single internal representation,
some individual internal program representation.
And there we might find a number of optimizations
such as common-sub expression elimination,
strength-reduction, dead-code elimination, constant folding,
loop fusion, software pipelining and so forth,
all acting as independent agents.
And which can in such compilers as the SWF
compiler from Stanford can be ordered asynchronously.
Another structural pattern is the process control.
Here, the action is in the process.
It's sensed by an individual sensor,
that sensor provides input back to a controller,
the controller then chooses certain manipulated variables,
and then those are chosen to actuate the process.
So your process an actuator, sensors, and controller.
Now, there are obvious examples of this,
such as any kind of process control system,
like something as simple as a thermostat,
but I like to think of much more sophisticated examples.
For example, working for many years on logic optimization,
I like to think of an individual logic
optimizer in this way in which the circuit is being
sensed for its speed or power.
That information gives back to a controller,
the controller then gives basically guidance
to launch individual optimization
transformations on the circuit, and all
that is under the guidance of, say,
individual timing constraints provided by the user.
Another common pattern in web applications
is model-view-controller.
In the model-view-controller, we have a model,
which is where the essentially the business
logic, or in some sense the database is contained.
We have a view which gives a representation,
or a view of that data and controller, which
interacts between the model and chooses views.
As an example of this, we see a very simple illustrative
example from [INAUDIBLE] design patterns.
Where we have a model, just simple data values,
we have views, which can be selected,
such as a bar chart or pie chart,
and then we have a controller, which
can be used to set data in the model,
or can be used to arbitrate among the different--
or choose different views.
Common pattern for structuring systems is layered systems.
In a layered system, the individual layers
communicate only with paired layers.
And this-- non-adjacent layers in the system cannot
communicate directly.
Some examples of this are such as an OSI network protocol.
So here we see the physical layers, the data link layer,
and the network layer.
But the physical layer can only interact with the data link
layer.
The data link player separates the network layer
in the physical layer and the network layer only interacts
with the data link layer.
This allows the details--
the implementation network layer to be entirely isolated
from the details physical layer, and then the physical layer
can change without having to change the network layer.
For more asynchronous event-based systems,
we have the event-based system where
we have a medium kind of a sea in which events take place.
We have a more centralized event manager,
and then we have a wide variety of agents.
What's unique about this pattern is
that these agents within this medium
can be added dynamically.
And this is the only structural pattern
for which that is the case.
So examples of this are the internet itself.
The internet is the medium, these signals are IP packets,
and the control plane of the router is the event manager.
And as we know from the operation, the internet,
individual computers can go on or off
the internet dynamically.
And again, this is unlike any other structural patterns
that we have considered.
The puppeteer pattern arose from the need
to manage and control interaction
of multiple submitters or computational agents.
The puppeteer itself guides the interaction from among,
say simulation codes to guarantee the correctness
of the overall simulation.
Problems where the puppeteer pattern is used
are often confounded with uses of agent repository.
And the key thing to remember here,
is that there is no central repository
and all the data transfer is between the individual puppets,
or simulators.
So for an example of this, this is a real example
that we use it with, is the modeling
of blood moving in blood vessels.
So there was a significant amount
of code devoted to the fluid dynamics simulation in blood,
and at some point, it was thought,
perhaps we should add this together
with another simulator which had been independently developed
to simulate the blood vessel.
Now these are both very large code bodies,
and there was no practical way in which
one could share the same underlying data structures.
So instead what was developed was a data broker interface,
and the state of broker interface does two things.
Number one, it schedules the relative simulation
of the blood vessel, or of the blood itself.
And we'll notice that if we look in the red and blue
here, that the simulation in the blood
occurs with a 10 times higher frequency than the simulation
the blood vessel.
This reflects the fact that the blood vessel
changes relatively slowly compared to the actual blood
flow.
Then in between the simulation blood vessels,
and the simulation of the blood itself, some data
needs to be passed.
And again, the data broker handles this.
Static task graph has the last of our structural patterns.
Here, it's very simple.
Tasks receive inputs and produce outputs,
and all data sharing is through explicit message passing, which
is explicitly shown in arrows below.
The task configuration, though, is statically defined,
and may not be changed at runtime.
Examples of this is, one way of approaching a video game
architecture.
Here, for example, we have in the input,
the artificial intelligence, the physics,
other physical effects, and graphics of the game
all expressed as independent, asynchronously interacting
tasks.
Now, one thing to think about the arbitrary static task graph
is it's a bit analogous to the Garlan and Shaw call-and-return
architecture and object-oriented programming.
And as a developer, we haven't got--
when we know that someone has used a static task graph,
we haven't got much insight in the application.
And for future generations maintaining the code,
they also don't know much a priori about the code
if we see in documentation that they're using an arbitrary
static test graph.
So we listed this as the last structural pattern,
and our general advice is to use this
as the last alternative for those reasons.