[MUSIC PLAYING]
So I think it is an important question.
Is a software program running on a computer more
like a building or a factory?
I think it's more like a factory.
A software program takes input, warehouses
intermediate results, and produces output.
So in this way, Garlan and Shaw's architectural styles
can be thought of as describing the layout of a factory plant.
In fact, the layout of the factory--
that is analogous to the structure of the software--
has a big impact on the efficiency of the factory.
But then, so does the machinery.
So if a software program is like a factory,
and the architectural styles are like the layout of the factory,
then what is analogous to the machinery the factory?
I think it's the computations.
Now, over the last 40 years we have thought quite holistically
about the overall construction of software.
We've thought quite a bit about individual algorithms,
like the shortest path between two vertices in the graph.
But we have tended to think of computations
as a huge ball of yarn with individual threads, known
as algorithms.
Now, one advance over this was developed very incidentally
by Phil Colella.
He's with Lawrence Berkeley National Labs.
And in a relatively informal presentation to the DARPA
High-Performance Computing Systems Group,
he talked that all simulations in physical sciences could be
broken down to seven--
he said algorithms.
I would say computational families-- structured grids,
unstructured grids, fast Fourier transform,
dense and sparse linear algebra, particles, and Monte Carlo.
So when you hear this, it sounds like perhaps
these high-performance computing people
have a big advance on how to think about holistic software.
Perhaps they can help us with parallel computing.
Well, a little investigation shows
that the high-performance computing
approach to architecting software
begins with a computation, and then however complex
that computation is, for structure, it simply
puts a Quonset hut over it.
Technically, they've even got a term
for this, which is known as a monolithic architecture.
So I'm afraid they can't help us much there.
Nevertheless, Colella got us off to a good start,
and beginning in 2004, we researchers at Berkeley Par Lab
went on from his work to identify
13 fundamental computational families.
So you'll see a variety of application areas,
such as embedded computing, spec benchmarks, databases,
and so forth.
You'll also see individual applications
like health, image processing, speech, music,
and computer browser.
And then what you'll see is a set of computations.
All in all, 13 computations, which we felt
was sufficient to span the computations
across these broad areas.
Red here in an individual cell indicates that this computation
is quite prevalent.
So for example, graph algorithms are
quite prevalent in embedded computing.
Orange means somewhat less so.
So for example, graphical models show up somewhat less
in databases.
Green even less so-- so backtrack
branch and bound are only partially showing up in games.
And blue shows that these computations hardly
show up at all.
These 13 computational families, called dwarves,
were published in the Berkeley View shortly thereafter.
So now we do have a description, a concise description,
of the machinery of the factory.
So how can we pull this all together?
We would like to be able to architect software
with a single, integrated vocabulary design.
We'd like the vocabulary to be sufficiently
formal to be meaningful, and yet flexible enough
to incorporate the diverse set of design decisions associated
with a sophisticated software program.
So how can we do that?
We're looking for a single vocabulary
for architecting software.
We'd like to be able to architect software
within a single vocabulary of design.
And we'd like that to be flexible and formal.
So we found the most useful mechanism
from [INAUDIBLE] was going back to Alexander's pattern
language.
So again, a pattern describes a recurrent problem
with a generalizable solution.
Alexander described 253 patterns ranging
at all levels of design, and he described a pattern language
as an organized way of tackling an architectural problem using
patterns.
So to go a little bit more in detail
and to give an example, one of his groups of patterns
addresses the overall layout of a group of buildings--
the height, the number of these buildings, the entrances
of the site, the main parking areas,
and lines of movement through the complex.
Now, the fundamental problem that he's
trying to address with these set of patterns
is one that's very familiar with this.
We go to a particular address, we're
looking for a particular office, for a particular shop
in a shopping center, and we're often confused looking linearly
through each individual shop.
The solution that he says is to lay out the set of entrances
to form a family.
They all form a group, they're all visible together
from a single vantage point, and they're broadly similar--
something that looks like this.
So what is the value of patterns for software?
Well, they're flexible enough to incorporate
both the mathematical and the artistic elements of design.
Giving names improves communication,
gives a common vocabulary among developers.
It improves the documentation.
It also aids the design process in a number of ways.
For beginners, it's often they're
unclear about how to get started.
It gives them a palette of choices
with which to get started.
For veterans, they often wonder, when am I ever finished?
The palette says, this is the set of design decisions
you need to consider.
It articulates very big design decisions very succinctly
and codifies good design practices.
Moreover, each pattern distills and disseminates
a vast amount of experience.
These also facilitate, in addition to design,
the processes of maintenance, restructuring, and refactoring.
So with this notion of patterns, we
can refine the definition of software architecture.
A software architecture describes the overall structure
of a software system as a hierarchical assemblage
of computational components chosen from among the 13
computational patterns composed by structural components chosen
from among the 10 structural patterns.
Now, there are two key elements of this definition.
The first is that it addresses simultaneously
computation and structure, but also that it gives
a finite palette for each.
It gives 13 computational patterns
and 10 structural patterns.
And although it certainly seemed like a bold notion
when we first got started on this,
we do-- we really do stand here and believe
that all computational programs can
be broken down and described with these 13
computational patterns and 10 structural patterns.
So taking it from the top, we identify the software structure
using the 10 structural patterns.
These describe the structure of our software,
but they don't describe what is computed.
The analogy here, again, is the layout of a factory plant.
Then we identify the key computations
from among our 13 computational patterns.
This is analogous to the machinery of the factory.
We go back and forth among these hierarchically
until we have a complete software architecture
of something that, say, is the large vocabulary
of a continuous speech recognition system which
I described here, which is analogous to a design
of an entire manufacturing plant.
Now, when I first thought of this notion of software
as factory, I was immediately excited,
and I ran over to the engineering library thinking,
there must have been a lot of thought as to how to actually
build and optimize factories.
And in fact, they do, and they consider
things which are very relevant to parallel computing,
like scheduling, latency, throughput, workflow, resource
management capacity, and so forth.
So again, we have a set of 10 structural patterns
and 13 computational patterns.
We go back and forth between these two,
analogous to both the layout and the machinery of the factory.
Now note that a pattern language is more than just patterns.
So there's Christopher Alexander.
Oftentimes, I feel he-- if you ever meet him,
he's such an influential man, he kind of
gets his way into your mind.
He becomes your conscience forever.
And I kind of hear him saying, a pattern language
is an organized way of tackling an architecture using patterns.
It's not a pattern language.
It's not just a set of patterns.
So our goal here was to provide a single integrated pattern
language which goes all the way from application
through high-level architecture, which I've described today
with structural and computational patterns,
down into parallel algorithm strategy patterns,
implementation in software, and execution targets.
This is our pattern language as a whole,
consisting of less than 50 patterns.
If we look at where this began, there
is a set of 13 computational patterns-- or 13 dwarves,
from the Berkeley View paper.
There were Garlan and Shaw architectural styles
generalized into our structural patterns,
and all this sits on top of Tim Mattson
of Intel's book, Patterns for Parallel Programming.
So let's review the key points of today's talk.
First, software is like a factory.
A software program takes its input, warehouses
intermediate results and produces output,
and this raises the relevant issues of scheduling, resource
allocation, and workflow.
Second, a software architecture must include both computation
and structure--
our 10 structural patterns, our 13 computational patterns.
A pattern language is more than just patterns.
Pattern language is an organized way
of tackling an entire architectural problem
using patterns, analogous to our tackling an entire software
application.
Here's our pattern language overview.
Here's our entire pattern language.
And this is me presenting our pattern language in 2010
to Christopher Alexander, and it's
been a very enjoyable afternoon discussing.
Got quite a lot of interesting questions
and engagement from him on our pattern language.
In subsequent lectures, we'll be going through in more detail
our entire pattern language.
[INTEL THEME PLAYING]