[MUSIC PLAYING]
So now I'm going to proceed in looking at the parallelism
in the structural patterns.
Now when we first did these structural patterns,
we really didn't necessarily think
that there was any direct relationship
between parallelism and structural patterns.
We thought they might be entirely independent.
But as we had more experience in implementing
structural patterns in parallel, we
saw that, in fact, each structural pattern tended
to be implemented using [INAUDIBLE]
were parallel algorithm strategies.
So let's move on to the parallel algorithm strategy
slice of our pattern language.
So the parallel algorithm strategies
define the high-level strategies used
to exploit the concurrency within a computation
when it executes on a parallel computer.
And they address different ways with the concurrency
is naturally expressed within the problem application.
Or, to put another way, how do we take the high-level software
architecture that we have developed and map that
onto a parallel computer?
So we see our palette here is of seven parallel algorithm
strategies.
Again, for beginners, they're happy to have
some kind of particular organized way of approaching
how to parallelize a problem.
And for much more experienced parallel software developers,
they're happy to see, oh, consider all or some
of these ways to parallelize in this application
than, in fact, I've considered all
the appropriate alternatives.
So let's take a look at pipe and filter
and ask ourselves, which of these seven parallel algorithm
strategies best fits?
Well, the pipeline parallelism pattern
seems to be the most appropriate one.
We use the pipeline parallelism pattern
when we can describe the system as data
flowing through a sequence of computational stages.
So we define a set of stages with dataflow connections
between them.
And parallelism comes from the fact
that we can have multiple stages active at one time.
Now just as every application typically
has pipe and filter at the top level,
almost every streaming parallel program
will have some sort of pipeline parallelism at the top level.
But of course, this is only true if the data is continuously
or periodically streaming.
If not, then we may not be able to pipeline.
So how much parallelism do we find from this pipe and filter?
Well, basically, we can get, at the top level, one task
for each filter.
That's about as much parallelism as we can get.
And if we need more parallelism to effectively use
our computational resources, we have to look deeper
inside the individual filters.
OK.
What about the parallel algorithm strategy
for the iterator pattern?
Among our seven different parallel algorithm strategies,
which one is most appropriate?
Well, it's kind of a trick question.
In fact, the iterator pattern is the only inherently
serial structural pattern in our list of 10 structural patterns.
So where is the parallelism likely to be?
If we're looking for parallelism in something that's
described as an iterator pattern,
we've got to look inside the blocks,
inside the iterator loop.
And in fact, we may often find there
are opportunities for data parallelism or pipeline
parallelism.
Data parallelism if the blocks are entirely independent,
and pipeline parallelism if intermediate results from one
can be passed to another.
Or, at the very least, we may find some opportunities
for task parallelism.
Parallel algorithm strategy for mapreduce.
What kind of parallel algorithm strategy can we find there?
Well, this is the natural place for applying the data
parallelism pattern.
We can use this when we have independent collections of data
which are operated on by a similar, if not identical,
sequence of instructions.
And we define the questions if data elements
can be dated in parallel.
And then we define the computation
as a sequence of collective operations applied together
to each data element.
This is very natural for the mapreduce structural pattern.
So how much parallelism can we find there?
Well, this is the motherlode in parallelism.
The potential for parallelism is as much
as the independent number of data sets that we can map onto.
Let's look at the agent and repository.
What kind of parallel algorithm strategy best maps here?
So it's natural to find task parallelism here.
We have each of the agents as an independent task,
as well as the repository manager of the task.
We can also find data parallelism latent
in the repository.
So how much parallelism does that net us?
Well, again, we get about as much task parallelism
as there are independent agents.
We get task parallelism associated
with repository manager.
All these can operate independently.
And then, of course, if we can, if we have an integrated
circuit as our database, as I have worked in the past,
then we may actually have quite a lot
of latent data parallelism inside that repository.
How about process control?
What kind of parallel algorithm strategy
can we apply to process control?
Well, process control is naturally task parallelism.
We can look at the controller, the actuator, the process,
and sensors, all as independent tasks.
Can we think of any other variety here?
Well, this may be one of our cases
where we have a natural mapping on to discrete event.
So the way I think about discrete event
is it's simply task parallelism, which we already
identified in the process control,
together with some sort of time ordering and a timestamp.
How much parallelism do we get?
Again, we essentially get as much
as there are individual tasks.
One for the controller, one for the actuator,
for the process, and the sensors.
Moving on to look at parallelism in the model-view-controller.
What kind of parallel algorithm strategy
looks most appropriate here?
Well, we see the model is naturally a task.
The controller is a task.
The view is a task.
And how much parallelism is that?
Well, that's just one task each.
But there may be more parallelism inside.
How about layered systems?
What kind of parallel algorithm strategy
is most appropriate here?
Well, there's a natural kind of organization
into task parallelism.
How much parallelism do we find?
Well, one task for each layer in the layered system.
Although, layers themselves may again
have more opportunities for parallelism.
What about event-based systems?
Well, event-based systems naturally
lend themselves to an approach of task parallelism.
Each agent can be an independent task.
An event manager can be a task.
Just how much parallelism is that?
Well, that can be quite a lot of parallelism
if we have a lot of agents in our medium.
And again, this is the one case where
we get an opportunity for a dynamic creation
and retirement.
How about the puppeteer?
What kind of parallel algorithm strategy
is most appropriate here?
Well, task parallelism seems to be natural.
Task for the puppeteer, as well each of the individual puppets,
how much parallelism is that?
Well, again, it's essentially a one-to-one mapping.
We have tasks for each of the individual puppets,
as well as for the puppeteer.
But here we should be looking a little more carefully at each
of the individual tasks for greater parallelism.
Remember, most likely the fact that we're using the puppeteer
is because we have quite monolithic pieces of code,
and we're using the puppeteer to just synchronize and put them
all together.
And so there should be more opportunities
for parallelism in the individual puppets themselves.
Static task graph.
What kind of parallel algorithm strategy
is most appropriate here?
And how much parallelism?
Well, as many as there are tasks.
So this is a little bit like asking who's [INAUDIBLE]..
In task parallelism, we naturally
have one task for each element of the static task graph.
So as we've seen in some of our examples,
such as speech recognition, typical application
has layers of parallelism.
If you look at our speech recognition system
here, at the very top level we have an iterator, which
has essentially no parallelism.
At the next level, we see a pipe and filter structure.
And again, we may be rather disappointed
because we found only a modest level of parallelism.
And yet, in fact, we found quite a lot of parallelism
in this application when we looked at the next level, where
we were able to apply mapreduce and find massive data
parallelism.
Let's review structural patterns and parallelism.
So in some sense, structural patterns
at this top level of the pattern layering language
are above the concerns of parallelism.
They may be used either for serial or parallel
implementations.
When we attempt to parallelize the software architecture,
in fact, our experience in the description
in structural patterns may give us only a modest amount
of parallelism.
There are a few exceptions.
Mapreduce, agent and repository, static task
graphs, and event-based.
All these may give us more parallelism.
Generally, mapreduce is the only one
which will give us a great amount of parallelism.
Nevertheless, we found that's important to use
the structural patterns to peel the onion, so to speak.
We peel off so that we can deconstruct the architecture
so it may reveal deeper levels of parallelism
in the application.
So I'd like to take a step back and overall look
at the relationship between structural patterns
and parallel algorithm strategy.
So this is a tree that you've seem in an earlier lecture.
At the top, we have an application.
We can organize this according to flow of data,
we can organize this according to tasks,
or organize this according to the data itself.
And we see each the seven parallel algorithm strategies
at the leaves of this tree.
And what we can see is, for these 10 structural patterns,
we see a natural organization of how they map onto the seven
parallel algorithm strategies here below, with the bulk
of them being task parallelism.
Not surprising because it's the most general.
Pipeline parallelism being used by pipe and filter.
Discrete event being used by iterator and process control.
We didn't find any natural matching to speculation
or divide and conquer.
Mapreduce can often go on to geometric decomposition,
or more generally, to data parallelism,
as can also agent and repository.
So again, to review, structural patterns
make me feel organized.
The modularity provided by structural patterns
makes me feel that even the most complex
application can be broken down into manageable modules.
The result of that is that looking
into the underlying structure exposes the parallelism.
In summary, again, structural patterns
make me feel organized.
Understanding your palette of structural patterns
is critical to becoming a good software architect.
Some structural patterns will help
us to identify significant parallelism directly,
like mapreduce, agent and repository,
arbitrary static task graph.
Other structural parents will just
help us reveal opportunities for parallelism.
You can read more about this at the website provided here.