[MUSIC PLAYING]
I'm Kurt Keutzer, Professor of EECS at UC Berkeley.
And today I'm going to be talking about creating
a high-level architecture.
So here's a quick look at our pattern language.
We go from an application through structural and
computational patterns.
And today, I'm going to be focused on this highest
level of the pattern language.
When we architect parallel software,
we look at 10 structural patterns
and 13 computational patterns.
Then we hierarchically refine one in terms of the other.
We're going to focus today on just three structural patterns.
But first let's talk about what are the elements
of structural patterns.
So it's very simple.
They're just components, which is
where the computation happens.
And they're connectors, where the communication happens.
This is a slight variation on [? Garwin & Shaw, ?] said
connectors are where the interaction happens.
Here we see the interaction happening by way
of explicit communication.
This is a set, or inventory, of structural patterns.
And I stand here today and claim that we
can build arbitrary complex software structures
out of simply these 10 software patterns.
Today, I'm going to focus on pipe and filter, iterator,
and map and reduce.
So first type and filter.
So in a pipe and filter structural pattern,
we have a set of pipes embodying the communication,
and filters embodying the computation.
Each filter only sees inputs and produces outputs,
and there's no global, or shared, state.
So what are some examples of that?
Well, almost every large software program
has pipe and filter structure at the top level.
Other examples are compilers.
We'll see an image retrieval system later.
And one that I worked with for many years, a logic optimizer,
had at its top level a pipe and filter structure.
The second structural pattern we consider
is the iterator pattern.
This is another very simple pattern.
We have initialization condition.
We go into a large body where a variety of functions
can be formed asynchronously.
At the end of that body, the results are synchronized.
Then we typically ask an exit condition.
Is that exit condition met?
If so, then we simply continue.
If not, then we iterate again.
Some examples of this.
Here is a training a classifier in support vector machine
training.
So imagine we're kind of building
a fence in n-dimensional space.
In one iteration, we update the service.
Then we identify all the outliers, basically
feature vectors that are on the wrong side of the fence.
If they're within an acceptable error range, then we continue.
Otherwise, we iterate it again and update the surface.
The third structural pattern we consider is MapReduce.
Now, I understand that Google has, to a certain extent,
redefined MapReduce in cluster of scale computing.
But we're going to hearken back to the early days of lists.
And for us, MapReduce means a map stage,
where computations are mapped onto sets of independent data,
and a reduce stage, where the results of the map stage
are summarized, i.e. reduced.
What are examples of this?
Well, again, with our generalized notion of this,
we see this applied to many data parallel applications.
And so for example, in that same support vector
machine computation I was talking about,
that computation associated with identifying the outliers, that
is itself mapped on.
And then the greatest outliers are then
the result of the reduction.
So a quick summary on structural patterns.
So identifying the structural pattern
for a portion of an application is the key
to creating program modularity.
And creating program modularity is, in turn,
the key to improving correctness, manageability,
and maintainability.
Personally, I'd say structural patterns
help me to feel organized.
I show you just three structural patterns.
But we have been able to build significant applications
in machine learning and multimedia
analysis with just these three.
Next let's consider computational patterns.
So here again is our inventory of computations.
Today, we're going to be talking about structured grid and two
varieties of matrix operation-- dense matrix and sparse matrix.
So when I first tried to present overviews
of computational patterns, I got really nervous.
How can you possibly talk about all linear algebra
in just a few slides?
And then I realized it's actually quite easy.
Linear algebra fundamentally operates
on three data types-- scalars, vectors, and matrices.
Here's a scalar.
Here's a vector.
Here's a matrix.
It has a few basic operations--
vector-vector multiply, matrix-vector multiply,
and matrix-matrix multiply.
What are some examples of this?
Well, we can do a simple linear map.
We can marginally solve linear equations.
Or we can compute eigenvalues or eigenvectors.
In general, these are kind of canonized
in the set of basic linear algebra subroutines.
These three levels, known as BLAS,
are characterized by their intrinsic ratio of computation
to memory movement.
In BLAS 1, we have simple vector-vector operations.
In BLAS 2, we have matrix-vector.
And in BLAS 3, matrix-matrix with the most intense
computation to memory movement.
Now an important thing is, as simple
as it may seem to identify that one
is doing a matrix-matrix or matrix-vector operation,
the key thing is that this allows
us to capitalize on a broad range of resources
of linear algebra, some of which are depicted here.
Next let's look at the computation of structured grid.
So structured grid, first we imagine
our data is arranged in a multidimensional grid,
and computation is composed of one or more steps.
In one step, every vertex on the grid--
and here we're highlighting the red vertex--
is updated by a small number of neighborhood
vertices around that vertex--
here in blue.
What are some examples of this?
Well, here's a [INAUDIBLE] convolution.
So on the left side here, we see we're
computing one pixel in the context of several neighboring
pixels.
On the right side, we're seeing we're
being more economical in data movement
by computing four pixels in a larger neighborhood.
We can use this for doing something
like edge detection on an image.
Applying that simple filter, we're
able to identify horizontal edges in an image.
Other applications include heat diffusion,
where the temperature of a vertex
will be influenced by the temperature of its neighbors,
or fluid dynamics, where the movement of a single particle
will be influenced by its neighboring particles.
Now again, our support when we identify something
as a structured grid computation is not
nearly as strong as in the case of linear algebra.
However, we do have a Cactus programming
framework which is focused on the structured grid model.
So here is a quick summary on the computational patterns.
Identifying the computational patterns
for a portion of the application is the key
to identifying the right library or framework,
identifying the right parallel algorithm.
But again, maybe more important to
me is the personal perspective is,
computational patterns make me feel smart.
Why is that?
Well Allan Kay said the right perspective
is worth 100 IQ points.
What computational patterns do for me is they
give me an invaluable perspective
on the world of applications.
Computational patterns have enabled my research group
to publish on machine learning, speech recognition, computer
vision, medical imaging processing,
computational finance, as well as other areas.
We could have never done this if we
got into the details of these application areas
without the organizing principle of the computational patterns.
So briefly, structural patterns help me feel organized.
Computational patterns help me feel smart.
So as an example, we're going to look at classification
using support vector machines.
So Mrs. Catanzaro has a problem.
She has hundreds of gigabytes of photos.
Most of them are of her children, some are flowers.
She'd like to be able to find her children without sorting
through all the flower photos.
Sounds like a job for a support vector machine classifier.
In the support vector machine classifier, what we do is,
we take examples of children, extract their features,
and train a classifier in examples of flowers.
Extract the features and train the classifier.
In some sense, we reduce each photo to a vector in n-space.
And then we build a fence in n-space
which separates, on one side, her children,
on the other side, her flowers.
So let's go through the architecture of this.
At the top level, looking at this example,
what's the structural pattern?
It's kind of obvious to see its pipe and filter.
As a matter of fact, as we mentioned earlier,
almost all sophisticated software programs
are, at the top level, pipe and filter.
So now let's go through each of the individual filters
in this pipe and filter design, starting
with feature extraction.
So on the left hand side, we've expanded feature
extraction down to build scale space representation,
selecting interest points, and building descriptors.
What's the structural pattern of this?
Again, it's pipe and filter.
Now looking at each of the individual filters,
we see, for the build scale space representation, that's
a computation structured grid.
For selecting interest points and support regions,
we actually have another structural pattern map reduce,
and each of those functions being
mapped as dense linear algebra.
And then finally, for building the descriptors,
we have a map reduce again for a structural pattern
inside that filter.
And then the computation inside of the maps
are their structured grid.
Looking next to train classifier,
what's the structural pattern of this?
Well it's two really.
At the outer loop, we can see it's iterative refinement.
Inside, we can see a simple pipe and filter structure
with the updating optimality conditions
and selecting the working set, and solving
the quadratic program.
Looking inside each of the filters of the pipe and filter,
we see a map reduce and dense linear algebra for each.
Now let's look at the actual exercise in the classifier.
So what's the structural pattern for this?
It's again pipe and filter.
Looking inside each of the filters of the pipe and filter,
we see first we have first computing the dot products
using dense linear algebra.
In the second, computing the kernel
values, summing and scaling.
This is essentially when we're exercising the classifier,
we're taking a vector in n-space,
and we're seeing on which side of the fence did it land.
Here to see which side of fence it landed,
we're looking at map reduce with mapping a dense linear algebra
formula.
So altogether, this puts together a real support vector
machine mini framework.
So this is not a toy example, as simple as that may seem.
The support vector machine framework was able--
when results compared to a libsvm,
the standard support vector machine tool--
to achieve a 9 to 35x speedup for training, 81 to 138
for classification.
And we've had over 3,000 downloads
of the software since its release
a few years ago, and over 200 citations
since its publication.
So in summary, we believe the key to productive and efficient
parallel programming is creating a good software architecture,
which is a hierarchical composition
of structural patterns, which enforce modularity.
And I showed you just three of these.
But seven more will be all you need.
Computational patterns, which provide efficiency and help
us to identify key computations to be parallelized.
Again, I showed you three.
And 10 more of those will be all you need.
In following this approach, we have felt smart
and organized, and thus have been
able to get impressive performance
results on many applications.
I showed you just one.
There are many more.
If you'd like to see more about the patterns,
we have a web address.
And then publications I've described here
can be found at this web address.
[MUSIC PLAYING]