[MUSIC PLAYING]
On behalf of the MIT summer session,
let me indicate how happy we are to be participating
in this edition of the university video communications
Distinguished Lecture series.
Our speaker tonight, Guy Steele, received his PhD
in computer science here at MIT in 1980.
He's probably best known to those of us
here as the co-developer of scheme and of common lisp,
or perhaps as the editor and chief organizer
behind the hackers dictionary.
He, however, has many talents outside computer science.
He is, for example, a composer and singer
with the distinction, probably the unique distinction
of having his sheet music published in the communications
of the ACM.
He also has demonstrated his programming skills
by becoming an outstanding Chinese chef.
He is a senior scientist of Thinking Machines Corporation
where he is responsible for the design and implementation
of parallel programming languages
and other system software for the Connection Machine computer
system.
He will be talking to us this evening
about data parallel algorithms.
Guy.
The data parallel programming style
is an approach to organizing programs
suitable for execution on massively parallel computer
systems.
In this talk, we're going to characterize the data
parallel programming style, we're
going to examine the building blocks used
to construct data parallel programs,
and we will see how to fit these building blocks together
to make useful algorithms.
All programs consist of code and data working together,
and there's usually some processing agency, a processor,
which using the code as instructions operates
upon the data to compute some useful result.
Now, there are different ways of building this processor.
If you have a single large processor, or perhaps even
a single small processor, operating upon the code
and operating on a single data item at a time,
you have a typical serial sequential Von Neumann
computer.
On the other hand, you might have many individual processing
elements interpreting the code and acting upon
the data in which case, we have a parallel computing system
and there are different ways of organizing this parallelism
In control parallelism the emphasis
is on organizing the program so that the processing
elements can take advantage of parallelism in the code.
Typically, in this style, different processing elements
might be at different places in the program text
so that you have different pieces of the program being
executed all at the same time.
Now, of course, you don't simply operate
by executing instructions without regard to the data.
Each of the processing elements must
have some access to the data, and this
may be in a regular or irregular pattern.
But the emphasis is on extracting parallelism
by orienting the program's organization
around the parallelism in the code.
In the data parallel programming style,
by contrast, the emphasis is on organizing
the programs to extract parallelism
from the organization of the data.
And the underlying metaphor is to think
of there being enough processing elements
that for every data item of interest,
there's a processor that can be attached to it.
And again, it's not that the processing elements
are operating on the data without regard to the code.
There almost must be some means of having the processors
interpret the code.
Now, typically, but not necessarily,
all of the processors will be at roughly the same point
in the program.
This is characteristic of the data parallel programming
style.
But it's not a necessary feature.
It is possible to organize a program into data parallel way,
and yet, have the processors be at different points
in the code.
But having a single locus of control most of the time
is a typical characteristic of this style.
Now, I want to draw a distinction here
between control parallelism and data parallelism.
That distinction on the one hand,
and a slightly different distinction
about architectural styles about the design of hardware, which
are usually labeled SIMD, for single instruction,
multiple data organizations, versus
MIMD, multiple instruction, multiple data organizations.
I think it's important to draw the distinction
between the style in which a program is written
and the way in which the underlying hardware is
organized because the two don't necessarily
have to be the same.
It is perfectly reasonable to write a data parallel
program which is then executed on a MIMD computer,
or for that matter, on a sequential computer.
And similarly, a control parallel program
can be executed on a sequential or a SIMD kind of computer.
And so my emphasis in this talk is
going to be on styles of organizing programs rather than
styles of organizing hardware.
It then becomes an engineering issue
of whether it's worthwhile to match the hardware style
to the program style or not.
Now, the sequential programming style
is typified by programming languages,
such as C and Pascal, has certain standard themes
and certain standard building blocks
which you see all the time.
Examples of these are scalar arithmetic operators,
control structures, such as loops and if then else
statements, and subscripted array references.
And the experienced sequential programmer
knows a great many standard and useful ways
of fitting these building blocks together
to make useful algorithms.
And furthermore, he has a good idea
of the costs of these individual building blocks.
While it's nowhere cast in stone,
most of us as sequential programmers
know that an addition and subtraction and perhaps
a comparison all cost roughly the same,
whereas a multiplication or division might
cost a little bit more, depending
on the underlying hardware.
Similarly, a procedure called be a little bit more costly
than an if then else statement.
And the precise costs depend upon the implementation
of the programming language and on the implementation
of the hardware.
But still, it's important to have a good idea, a reasonably
good model, a set of expectations
about the underlying cost of the primitives
before you can expect to write effective and efficient
algorithms in a sequential programming language.
Similarly, in order to write good data parallel programs,
we need to become familiar with the appropriate building
blocks for building data parallel programs
and we need to have a good idea of their relative costs.
So now, let us examine certain standard themes that
arise naturally in data parallel programs
and consider specific building blocks that are
used to implement those themes.
The most common themes that I see
popping up over and over again in data parallel programs
are elementwise operations.
And these are operations which can be carried on
by the individual processors independently
each on their own pieces of data without communication
among the processors.
And typically, these are arithmetic operations and tests
of various kinds.
They're also conditional operations,
which are also elementwise, but in which some of the processors
perhaps do not participate or perhaps
act in slightly different ways depending
on the content of the data.
Then, there are various forms of communications
among the processors, which include replication, reduction,
permutations, both regular and irregular, and parallel prefix
operations.
These are by no means the only themes,
but these are the ones that I want
to focus particular attention on tonight.
Let's take a look at an example of an elementwise operation.
Here, we have what looks like an ordinary Fortran assay
or C assignment statement, C gets
A plus B. The interpretation here that is intended
is that A and B represent arrays.
And here, we see eight processors.
And each processor has its own value for A
and its own value for B. And the direction is for each processor
to execute an addition and store the result in C.
And so you can see that the first processor has
added 3 and 6 to get 9.
The second processor has different data.
It has added 1 and 2 to get 3 and so on.
Similarly, conditional operations
can be carried out elementwise.
Here, we are comparing the contents of the array
A and the array B element by element
and setting a flag, shown at the top of the graphic,
to indicate whether or not the test succeeded.
And so we can see that in the first column,
the test failed because 3 is not greater than 6.
Whereas, in the third column, the test succeeded because 4
is greater than 1.
And the result is a series of Boolean
result-- a series of bits one per processor,
which can then be used to conditionalize
further operations.
Here, we have an example of using
the results of that test to perform a conditional addition.
Only processors whose test succeeded in the previous step
will execute the addition step.
And so we can see that only the third, fourth, fifth,
and seventh processors actually performed the addition
and scored the result in C.
The set of bits, which is used to conditionalize
the operation, is frequently called a condition mask
or a context for the execution of further operations.
And in this way, each processor can
perform different computations based on the particular data
that it happens to contain.
Now, let's look at some communications operations.
One that happens very frequently is to have a single quantity
and want to get a copy out to all the processors.
This we call broadcasting.
Here, we have a single number 43 and we
would like to get it out to all the other processors.
Now, there a variety of ways of doing this,
depending on the particular hardware you have to support it
and the particular algorithms you want to use.
This operation occurs so frequently in data parallel
programming that it's worthwhile and easy to support it directly
in hardware.
And so it's not unusual to see a hardware bus of some kind
to carry a single value out to all the multiple processors.
On the other hand, there are other ways of doing it as well.
If there are many things to be copied
rather than a single thing, a more complex algorithm
is called for.
Here, we have a typical example in which we have a vector which
occupies a row of a matrix.
We would like to copy that vector
to all the rows of the matrix.
So we don't have a single quantity to be copied, rather,
we have many quantities.
But they are to be copied in a reasonably regular pattern.
Now, one very simple way to do this,
if each processor associated with a piece of data
in this matrix is able to communicate with its nearest
neighbors, is to copy the row step
by step down the matrix each copying to its nearest neighbor
until the entire matrix is filled.
This operation is called spreading.
And here, we have managed to copy the first row down
to all of the others in seven steps
because this is an 8 by 8 matrix and 7 is 8 minus 1.
But there are other ways of doing it
which are faster if you have additional communications
links among the processes you can exploit.
Here, we will assume that a row of a matrix,
in fact, can be communicated not only to the next row down,
but, in fact, to a road down that is a power of two away.
And we will see that we can do the operation much faster.
First, we take the first row and copy it to the second row.
But now, each of those rows can send copies
to their neighbors that are two rows down.
And then, each of those rows can send copies
to neighbors that are four rows down.
And by jumping in increasing steps like this,
we can fill the array in only three steps, which
is logarithmic in the size of the array, 3
being the base 2 logarithm of 8.
And so we have another way of executing the same spread
operation, which is logarithmic in the number of processors
rather than linear.
And this is typical of a lot of interesting parallel operations
that can be carried out in the data parallel style.
You see logarithmic execution times
popping up all over the place.
Reduction is another very common operation that is essentially
the inverse of broadcasting.
In broadcasting, you take a single value
and make copies for all of the processing elements.
In the case of reduction, each processing element has a value
and you're trying to accumulate a single result
by combining them in some interesting way
to produce a single result.
Again, I've shown here how you might
want to have some kind of hard wired facility for doing
some reduction.
In this picture, the eight processors
shown at the bottom of the screen each
have different numbers and there some is 27.
So the number 27 shows up centrally.
There are other ways of doing that as well.
Let us take a look at an algorithm that
can be used to sum a vector in logarithmic time.
We start out with a vector that has eight elements,
x sub 0 through x sub 7.
In the first step, we add them pairwise so that x sub 0
and x sub 1 are added by the second processor,
x sub 2 and x sub 3 by the fourth processor, x sub 4
and x sub 5 by the sixth processor,
and x sub 6 and x sub 7 by the last processor.
And so four of the processors, by doing these additions,
have produced partial sums towards the work
of reducing total sum.
In the second step, we add these partial results pairwise again.
And then, in the last step, again, another pair.
And we see that the last processor
has received the sum of elements 0 through 7.
Notice in this diagram that we've used the notation
sigma with a lower and upper bound to indicate exactly
which elements have been summed so far.
Please also note that most of the time
during the course of this algorithm, most
of the processors have not been particularly busy.
In the first set of additions, only half of the processors
have been occupied doing editions.
In the next step, only a quarter of them.
And in the last step, only one eighth of them.
And so we can see that while this is fast,
we haven't made use of all of the processors.
Interesting question arises.
What would happen if you didn't turn off the processors
and let some of the other processors also do additions?
You would actually get another very interesting building block
for data parallel algorithms, which
is parallel prefix algorithms.
We're going to carry out the same sort of computations again
but leave more processors active.
We start out with x sub 0 through x sub 7 laid out.
And in the first step, we sum pairs,
but notice that they're overlapping.
We sum x sub 0 and x sub 1.
We also sum x sub 1 and x sub 2 and so forth.
And so each of the processors except the first
is computed to sum.
Then, in the next step, we compute more sums.
All but the first two processors participate.
And then, in the last step, all but four processors
participate.
The result has a very interesting property
that each processor has received the sum of what
it contained plus all the processors preceding it.
In other words, if we regard the original input as an array,
then we've computed the sums of all prefixes of the array.
That is, all initial segments of the array.
I sometimes call this the checkbook operation
because if the numbers that were in the array elements
were a series of credits and debits
against your checkbook, the checks you'd written
and the deposits you'd made, then
the result of the sum prefix operation
is the series of running balances that should
appear in your checkbook.
And we will see examples of how this operation can
be useful in other ways later as a building
block of the algorithms.
A very simple example is an operation known as enumeration.
In this operation, we wish to assign a different number
to each processor.
And this can be accomplished easily
in two steps using building blocks we've already seen.
The first being broadcasting.
We take the number one and broadcast that
to all the processors.
We then apply a sum prefix operation
so that each processor receives the sum of the one
that it contains plus all the ones preceding it in the line.
And the result is that each processor
gets a different number from 1 through 8.
Sometimes this is called the bakery operation
because it's like all these processors have walked
into the bakery each one has gone up to the little machine
and taken a ticket and each one has gotten a different number.
But it's happened very fast rather than doing
it sequentially one at a time.
Another very important operation is various kinds
of motion of data without particularly
performing any kind of arithmetic operation.
And most of the interesting ones are permutations.
Here's an example of shifting a linear array of data.
This is an end around shift one place.
One could imagine shifts of other distances.
But in this case, the entire array
has been shifted one place to the right
and the rightmost element has been brought back around
to the front.
And of course, one can do shifting
not only on one-dimensional arrays,
but also on two-dimensional arrays.
You might have a two-dimensional matrix
and want to shift it one position to the North or three
positions to the East or 4,096 positions to the South.
Another kind of permutation is an odd even swap, shown here
for eight elements, in which A and B have exchanged places
and C and D have exchanged places.
One might also imagine more general forms
of swap or one swaps with a neighbor that is
a power of two distance away.
Permutations of this form are very often
seen as steps in algorithms such as the fast Fourier transform
and in various sorting algorithms.
The hardware architecture that is
capable of performing all distance 2 to the k swaps
turns out to be equivalent to a hypercube, which
is one of the reasons why the hypercube is
very popular as an underlying hardware
architecture for algorithms of this style
because it can easily achieve many
of the interesting permutations on data
that are necessary building blocks for these algorithms.
Some algorithms call for performing irregular
permutations on the data.
Most often this comes up when the permutation to be performed
is dependent upon the content of the data.
In this graphic, we've illustrated a sorting
algorithm.
And in fact, here it's as if the sort has been computed
magically all at once and every processor has figured out
exactly where to send its data.
The data sent from the top row to the bottom row,
and poof, it's ended up sorted.
In practice, real sorting algorithms
undergo a number of intermediate stages
where they calculate intermediate places to send
the data and after a number of steps the data ends up sorted.
But the point is that the particular permutation involved
is dependent upon the content of the data.
Therefore, it cannot be predicted in advance,
and therefore, it cannot be pre-wired into the hardware.
We can see this by considering an example
from image processing.
Let's suppose that we have an image of, say,
1,000 by 1,000 pixels, a picture that we've taken of a spaceship
and we want to do processing on this image
until we've assigned a processor to each
of the pixels of the image.
And the question is, where is the rocket ship?
Well, some of the operations we need to perform on this image
are local.
And so we might focus in on a particular region of the image
and have each processor look not only at its own pixel value,
but also at the pixel values of its neighbor.
And from this determine, for example,
whether a particular pixel is on the boundary of an object
or somewhere in the middle.
And this is a local piece of processing.
It involves a fixed pattern of communication.
It involves regular permutations,
which involves shifting the array back and forth so
that each processor can look at its neighbor
in a particular fixed direction.
On the other hand, when it comes time
to assemble this boundary information
and put it together into a single global object,
we can see that the particular patterns of communications
are going to be dependent upon the content of the image data.
That is, which processors have to communicate with which
other ones so they can all agree that they
are part of the image of the same object.
Depends upon where the rocket actually
happened to be in the image.
Most of the building blocks that we've
looked at so far concern themselves
with operations on arrays, which are very rigidly organized
kinds of data.
It is also possible to have very irregularly organized
kinds of data.
For example, one might have a graph structure in which nodes
are organized not by being neighbors within some fixed
geometry, but by being connected through pointers instead.
In this graphic, we have shown the nodes
as being lined up side by side just for ease
of seeing what's going on.
But in fact, you should imagine them
as being eight processors in completely different parts
of the machine known to each other
only by an address indicate that uniquely identifies
the processor.
And we've indicated these addresses by pointers.
So we can see that the first processor knows the address
of the second processor.
The second processor knows the address of the third.
And I had originally thought that nothing
could be more essentially sequential than the need
to follow a linked list of pointers.
Because you just can't find the third one without going
through the second one.
But I was wrong.
I forgot that there is processing power
at each node of the linked list.
And you can take advantage of that to do things faster.
The most important technique is known as pointer doubling.
And this is the pointer analog of the spreading operation
that we looked at earlier in order
to make a copy of a vector into a matrix
in a logarithmic number of steps.
In the pointer doubling method, each processor
first makes a copy of the point it has to its neighbor.
Then, in a repeated series of steps,
each processor looks at the processor
that it's pointing to with this extra pointer
and gets a copy of its pointer.
So at the first step, each processor
has a pointer to its neighbor one away in the linked chain.
But as the first processor looks into the second process
and gets the pointer to the third processor
and each of the other processors do the same thing,
we see that the next step, each process
will have a pointer to a processor
two steps away in the linked chain.
And as this operation is repeated,
each processor can then have a pointer to a processor
four steps away in the chain, except that if you fall off
the end of the chain then you don't update your pointer.
And if you keep doing this, then after a number of steps
logarithmic in the length of the chain,
every processor will have gotten a pointer
to the end of the chain.
And this happens in only logarithmic number of steps
rather than a linear number of steps.
I think this is sort of an interesting and surprising
result.
Now, let's see how that can be used
by considering nodes that not only have pointers
to their successors, but also numbers.
And we're going to compute a parallel prefix,
a set of partial sums, on this linked list.
And the algorithm is very similar to the one
we saw before on a vector except we're
taking advantage of the pointer doubling technique.
At the first step, each processor
simply takes a pointer to its neighbor.
At the next step, each processor takes the value
that it holds and adds it into the place pointed to.
So for example, in this diagram, the first processor
is going to add its x sub 0 into the x sub
1 in the next processor.
Whereas, the x sub 1 is going to be added into and x sub 2.
And x sub 2 into the x sub 3 all in parallel.
And then, it will take a pointer double step.
And the result looks like this.
The first processor still contains
x sub 0, which can also be noted as sigma 0 to 0,
which is just the sum of x sub 0 through x sub0, which is simply
x sub 0.
The second processor has the sum of x sub 0 through x sub 1.
The third processor has x sub 1 through x sub 2 and so forth.
And we've doubled the pointers.
Now, we do this again and we see that, for example,
the fourth processor now has the sum of s sub 0 through x sub 3.
And the seventh processor has x sub 3 through x sub 6.
Now, notice in this last step that the third processor will
add its sigma 0 to 2 into the seventh processors sigma 3
through 6.
This will cause processor 7 to have the sum of 0 through 6.
And after the third step, in fact,
if you carefully trace through it all,
you will find that each of the processors
has gotten some of its own number plus all the preceding
ones in the list.
And again, in a logarithmic number of time steps.
So we see that we can do interesting things
not only with arrays, but with linked lists in this data
parallel programming style.
Now, let's talk a little bit about the distinction
between speed and efficiency.
In sequential programming, usually these terms
are considered anonymous.
If a program is fast, then it must be efficient.
If it's efficient, it must be fast.
But this coincidence of terms comes about
only because you have a single processor to work with
and you're trying to get the most
horsepower you can out of it and it's the only one doing things.
But in a parallel case, it's not so
because sometimes you can make it go faster by, in some sense,
doing extra work more than you had to
by taking advantage of the fact you've got
extra processors to work with.
Let's consider, for example, the algorithm that we saw earlier
for summing a vector and let's compare that
with a serial algorithm.
With a serial algorithm, you would write a loop,
and within the loop, you would have
indexed subscripted accesses to the array.
And you set up an accumulator, initialize it to 0,
or perhaps initialize it to the first element of the vector
to save an addition, and then add
in successive elements of the array.
So you would do this using one processor.
You would take N minus 1 time steps.
And you would have to do N minus 1 additions--
pairwise additions because that's the minimum number
you can get away with.
So we say that the work involved was
N minus 1, that was the number of additions performed.
The cost, which is the number of processors times the number
of time steps is N minus 1.
And the efficiency, which is the amount of work
you got done-- the number of additions divided by the cost
is 1.
Now, let's compare that with the parallel algorithm.
In the parallel vector sum algorithm,
we used N processors to do it, one for each data element.
We did it in log N time steps and we still accomplished
N minus 1 additions.
The cost of this, the number of processors
times the number of time steps instead of being N minus 1
was N log N. We used a lot of processors.
And as we noted earlier, most of the processors
weren't busy most of the time.
And so we wasted a lot of cycles.
And so the efficiency, which is the number of additions divided
by the cost, was approximately 1 over log N.
So as the size of the problem gets bigger,
the efficiency goes down.
But still, the speed compares quite favorably
with the serial algorithm as log N versus N minus 1.
Now, let's compare this to the vector sum prefix algorithm.
And again, consider a serial version.
Just as the data parallel vector sum prefix
looked like the data parallel sum reduction,
so the serial prefix algorithm looks like the serial sum
algorithm, except you save out all the partial results.
You start with the first element of the array and you save it.
Then, you add in the next element.
You save that sum.
You add in the next element.
You save that sum.
And so after N minus 1 time steps and N minus 1 additions,
you computed to sum prefix with the additional cost of simply
storing the results out to memory.
And so, again, you've achieved N minus 1 additions
with N minus 1 cost until the efficiency is 1.
Now, let's compare that to the parallel version.
We've used N processors and done it in log N time steps.
But the number of additions is much greater.
If you work out the numbers, it turns out
to be N times log N minus 1.
Because you used N processors and use them
at log N time steps and nearly all of them were busy.
So you did N times log N minus 1 additions at a cost of N
log N. Dividing those, the efficiency
was log N minus 1 over log N, which as N gets very large
is very close to 1.
So we can claim that this is a very efficient algorithm
because it then gets large as efficiency approaches 1.
And yet, this efficiency is somehow bogus.
We achieve this efficiency by keeping the processors busy
doing more than they really had to do in some sense.
Because only N minus 1 additions are really
required to compute a sum prefix.
On the other hand, it appears that more than that
are required in order to do it fast.
And so we have this curious trade-off
that as the speed goes up, the efficiency goes down,
in some sense.
But that's masked by this particular efficiency cost
by the fact that we actually did more additions than we really
had to.
So the business of measuring the speed of a parallel algorithm
and the efficiency of a parallel algorithm
is a very tricky business.
And in fact, I think the particular measures
that I used in these graphics are a bit naive.
And we need to develop a better theory of how
to measure the goodness, the efficiency, and the speed
of parallel algorithms.
We've seen a useful set of building blocks
for constructing data parallel algorithms.
Now, let's build some algorithms with those building blocks.
For our first example, let's consider matrix multiplication.
This can be done in a large variety of ways.
But abstractly, there's a single operation
to be performed, which is that given two matrices,
we regard one as being composed of rows and the other
as being composed of columns.
And each row of the first must meet
every column of the second.
And each interaction of a row and a column
will produce a result element in the result array
by performing an inner product on the two vectors, the row
and the column.
One way of doing this very quickly
by a sort of brute force approach
is to use order of n cubed processors.
We'll assume that each of these three matrices, the source--
first source, the second source, and the result
are n by n matrices.
And we will use n cubed processors
and we will organize the matrices
by putting the first source on one
face of the cube, the second source on a different face,
and have the result come out a third face.
And we will see that we can do this very quickly in a fairly
short number of steps.
The first thing we will do is make copies of the first source
array using a spread operation to replicate that matrix
through the cube.
Then, we will do the same thing with the second source
making copies and spreading those down the cube.
Each of these spreading operations
takes a logarithmic number of steps.
So so far, we've used O of log n time.
Next, we do a lot of elementwise operations.
You can see 16 of the multiplications
here in this graphic shown on the outer face of the cube.
But in fact, these elementwise operations
are happening throughout the cube
and so we have n cubed multiplications going on
in a constant amount of time because we're
using O of n cubed processors.
Then, in the last step, we perform a parallel sum
operation using the doubling reduction method
that we saw earlier on each of the rows
coming up through the array toward the result matrix.
And that takes a logarithm amount of time.
And so, in four simple steps, we've
managed to multiply two n by n matrices in log n time,
but at the cost of using O of n cubed processors.
It should also be pointed out that if the very next thing we
wanted to do was to take this product
and add it to one of the source of arrays,
the result is in the wrong place and we're
going to incur yet an additional cost
to move it to the right place so that we
could perform that addition.
And so that should also be factored
into the cost of the operation.
Here is another method for doing matrix multiplication that only
requires n squared processors.
In this arrangement, we take the two source arrays
and put them in the same set of n squared processors.
And the result will also show up in the same n
by n matrix of processors.
And we're going to use a very clever technique
due to Cannon, which involves pre-skewing the two source
arrays.
The first source array has its rows skewed
and you'll see that each row is skewed by a different amount,
depending on its row number.
And similarly, the columns of the second array
are skewed depending on their column number.
Now, we will take these to skewed arrays and overlay them
and the result looks like this.
The essence of the algorithm-- this is a systolic algorithm--
is to rotate both of the source matrices at the same time.
We're going to rotate the first source matrix horizontally
and the second one vertically like this.
And so at each time step, each of the two source arrays
will be shifted by one position and the result
looks something like this.
And after four time steps, where in at each step,
the two source elements that arrived to the processor
are multiplied together and added into a running sum.
And magically, the result has been
computed after n time steps.
Now, let's look at that a little more closely.
Pay attention to the intersection point
at the upper left.
You will see that at the first time step,
the second element of the first row and the second element
of the first column have met in the upper left corner.
They are then multiplied and accumulated.
Then, at the next time step, the third elements
of the row and column meet are multiplied together
and added in.
At the next time step, the fourth element
of the first row and the first column meet.
And at the last step, finally, the first elements
meet and are accumulated.
And the same thing is going on at all the other points
of the matrix.
And the purpose of the pre-skewing
is to ensure that each element of each row
meets the corresponding element of each column at just
the right time.
And if you don't believe that, you'll just have to trust me.
It works.
It's really amazing.
And so the net effect is that using only n
squared processors, we've managed to do it in time n.
Add an additional benefit is that the matrix ends up
in the right place if you want to do yet other things
with the other matrices.
Finally, let us consider a really big example.
We're going to go back to the question of labeling regions
in an image.
Here instead of showing you a rocket ship,
I showed you a somewhat more abstract image
in order to keep the example small.
This is one of the difficulties of describing
data parallel algorithms is that they
are inherently algorithms oriented
toward large amounts of data.
But if I try to show you a large amount of data,
it won't fit on the screen.
So I'm going to do my best here.
We have a number of regions in this image shown here
by different colors.
We see a large central green region.
This little squiggly reddish orange region up
in the left corner.
And notice that not every region is a different color.
There may be several regions that are the same color.
But as long as they're disconnected,
we want to consider them to be separate regions.
We would like to compute a result that looks something
like this in which each region has been
assigned a distinct number.
We don't particularly care which number gets assigned
to it as long as each region gets a different number
and all contiguous elements of a single image
have received the same number.
So we can see here that in the sample result,
the central green region has had all its pixels assigned a value
19.
And the squiggly region in the upper left corner
has received a value 0 in all its pixels.
The region in the upper right corner,
which although the same initial color as the central region
has received a different number.
It's gotten all fives instead of 19s because it's disjoint.
And we proceed a number of steps.
And at each step, we'll see how the particular themes
and building blocks we've discussed fit together to make
an interesting algorithm.
The first thing we're going to do
is assign a different number to each processor.
And in fact, here, I've shown the numbers
as progressing across the rows and then down to matrix.
But for the purposes of this algorithm,
any organization would do provided
we can reasonably quickly assign a different number
to each processor.
And we've seen how the enumeration technique
can do this in a logarithmic number of time steps.
So we'll assume this particular numbering of the processors.
The next thing we do is to have each of the pixels in the image
examine the pixel values of the neighbors.
And this is easily accomplished by using regular permutations,
namely shifts of the matrix.
We take the matrix and we shift it up,
we shift it down, left and right, and also
to the Northeast, Northwest, Southeast, and Southwest.
And as a result of these shifting operations,
each neighbor now knows its own pixel value
plus the pixel values of its eight neighbors.
This is then enough information for each processor
to do elementwise computations and decide--
each processor can decide whether its pixel value
is on the border of its region or not.
There are lots of special cases.
And the details get rather messy and I'm not
going to talk about them too much here because they're not
central to the ideas involved.
But be aware that there are messy details.
In this example, we have darkened the border square
so you can see them.
And the next several computations to be carried out
will be carried out only by pixel processors that
are on the border.
So this will be an example of conditional operation,
only some of the processors will be participating.
We have each processor, again, consider the pixel values
that came from its neighbors.
And also inquire again using shifting of its neighbors
whether its neighbors are border elements.
This is, then, enough information to figure out
which of your neighbors are border elements
in the same region so that you can construct pointers to them.
And so what we've done here is to stitch together
the border of each region in a linked
list that runs around the perimeter of the region.
So you can see a linked list running around the perimeter
of the central green region.
And you can see a linked list running
through the squiggly region in the upper left.
And each region has had its boundary connected up
with linked pointers.
We are not going to use pointer doubling algorithms.
Each pixel processor considers the number
that it was assigned in the enumeration step.
And the pixels that are not on the borders
do not participate in this consideration.
We then use a pointer doubling algorithm, first of all,
to do a reduction step using not summation,
but the minimum operation.
Min is as good an operation for combining numbers as summation
is for this purpose.
And pointer doubling works just fine for that.
So each linked border list will perform pointer doubling
around that list and determine what is the smallest
number in that list.
And then, by using another pointer doubling step,
send that smallest number and make copies of it
all around the perimeter.
So now, every border pixel knows the smallest number
that was on a border element in its region.
So for example, the number 19 has
been propagated around the border
of the central green region.
And the number 0 has been propagated down
the squiggly region in the upper left.
Finally, we can use scan operations, not
on the linked lists anymore, we can abandon those now,
but by operating on the columns or what
amounts to the same thing in the rows, either one will do.
By doing a scan operation in each direction,
we can copy the processor labels from the borders
to the interior points of the region.
So for example, in the interior green region,
it actually suffices to copy from the upper edge
of the region downward, thereby propagating the label
into the interior.
Other regions, particularly those
that are on the edge of the image,
may need the numbers propagated up instead of down.
So you do a scan in both directions doing copying.
And this is done by essentially a variant
of the parallel prefix operation.
But instead of using an operation such as summing
or min uses a more complicated operation that
is, in fact, not commutative, but fairly simple,
which is essentially if you've come across a new number,
take a copy of that and otherwise copy
the old number that came in from your neighbor.
But it's a legitimate variant.
This method of labeling regions in an image
is known as LIM's method after Willie Lim.
And if you use n squared processors
to represent the image in n by n array,
it accomplishes the labeling in log n time.
Because each of the steps that was involved
took either constant time or time logarithmic
in the number of processors.
It was given that you had n squared processors
to process n squared pixels.
Data parallel programming makes it
easy to organize computations on large quantities of data
for massively parallel computer systems.
It differs from sequential programming
in that its emphasis is on operations
on entire collections of data rather than single elements
of the data one at a time.
In a data parallel program, you typically
find fewer loops and fewer subscripted references
to arrays than you do in a sequential program.
On the other hand, data parallel programs
are typically very similar to sequential programs
in containing a single thread of control.
At any given point in time, there's
conceptually execution control at only one
point in the program text.
Sometimes this restriction is loosened a little bit,
but it's characteristic of the data programming style.
This can make data parallel programs easier
to understand than control parallel programs.
In order to write good data parallel programs,
we must become familiar with the necessary building
blocks for the construction of data parallel algorithms.
And we need to have a good idea as to what
the relative costs are.
Given one processor data element,
there are many interesting operations
that can be performed in constant time
on an entire array of data and other operations
which take a logarithmic amount of time
or perhaps a linear amount of time in the amount of data.
And this depends not only on the inherent complexity
of the operation, but also sometimes upon the underlying
implementation.
If a particular piece of hardware
doesn't support sufficient connectivity
among the processors, for example,
a communication's bound operation
may take more time than would otherwise be required.
Once you become familiar with these building
blocks and learn how to fit them together
in standard and conventional ways,
writing a data parallel program is
just as easy as and just as hard as writing
a sequential program.
And given a suitable underlying hardware,
your programs may run much faster.
I'm Burt Halstead, DEC Cambridge Research Lab.
I thought your examples were very interesting,
but I was curious whether you ever get into problems when
you have highly data dependent computations
and it's difficult to keep more than a very small fraction
of the processors actually doing the same operation
at the same time.
Yes, you do.
That's a very interesting problem.
And that's one reason for making the distinction
between the data parallel style and the question of whether you
got SIMD or MIMD style hardware supporting it underneath.
It's perfectly possible to have hardware
that is capable of giving you some more
choice than doing the same thing at the same time.
Now, the precisely best method of designing a total system
that gives you flexibility without making it extremely
difficult to control I think is still an open research
question.
I'm Franklyn Turbak from MIT.
You indicated that a number of your algorithms
took time that was logarithmic in the size of the problem.
And this seems to be based on the assumption
that you actually have a large enough number of processors
to match the size of your problem.
Yet, for any real machine that you're
going to be running these algorithms on
there's going to be, in fact, a limited number of processors.
And if the size of your problem exceeds
the number of processors, it seems that the logarithmic time
growth is no longer justified.
Can you explain that please?
You're absolutely correct and I'm glad you brought that up.
There is no free lunch.
And for a fixed amount of hardware,
making a problem bigger is going to make
the whole thing run slower.
It's a question of whether you regard the size of the hardware
to be fixed.
If you have a much larger problem so big that it's not
going to fit in the computer you have,
you're simply going to have to buy a bigger computer.
And that's all there is to it.
Within the range of problems that your computer can handle,
then you will, indeed, tend to get linear kinds of trade-offs
rather than logarithmic ones.
It's a question of what you choose
to hold fixed in your analysis and what
you choose to let vary.
I'm [INAUDIBLE] from Holland.
I want to ask you the following question.
Is there something to say about the portability of the programs
to different machines?
Yes, there is.
There is a great deal to say about portability.
And one is that right now it's very difficult because we have
not come to terms on standards.
We haven't agreed on what are the right kinds of building
blocks to support.
And as a result, you end up with different architectures
that are being built in hardware lending
support to different ones of these operations,
but not supporting them all in a uniform fashion.
We're still trying to discover which ones are important.
And this is why you end up with non-portability of efficiencies
and running times.
This is completely aside from the question of,
will the code run at all, which I
think is merely a matter of agreeing
to implement compilers.
It's a difficult problem.
And I think that's part of the point of this talk,
is to bring forward one particular set of building
blocks that I think can be treated as a universal
and to try to get hardware architects
as well as language designers to pay attention
to these particular building blocks
as exemplars of important things that need to be supported well
in both software and hardware.
And there are probably others that I haven't touched on,
such as sorting.
I'm Jim [INAUDIBLE] from Howard University in Washington, DC.
I have a number of questions that
came out of the lecture and some of other personal professional
interest with respect to this important topic.
For dealing with large matrices that
are highly dense and sparse, there are [INAUDIBLE] metals
that we normally will use to reduce
the so-called computational [INAUDIBLE]
And thus far, as you give the very good presentation,
it looks to me that there will be opportunities
for evolving or solving problems [INAUDIBLE] that
might involve sparsity.
If this is true, how do you justify
the overhead cost in terms of the cost of parallel processing
as well as the cost of operations?
I know that there's advantages in terms
of the operational cost.
But the overhead cost in terms of implementing such machines,
especially where budgetary constraints
might be significant.
Is the gist of your question that the kinds of matrix
algorithms that I showed in this lecture are not
suitable for sparse matrices because so
much of the processing power will be wasted?
Yes.
Yes, that is a very good criticism.
And it would not be appropriate to use that kind of algorithm
on a sparse matrix, just as you wouldn't
use the usual sequential triply nested loop you
use for dense matrix on a sparse one.
Sparse matrix processing on a data parallel computer
calls for very different approaches
that I did not illustrate in this talk.
And they are more difficult and typically
call for the kinds of irregular permutations and communications
techniques that I illustrated before.
Because the particular patterns of communication
in the processing of sparse matrices
depend so much on the particular content of the matrix.
I'd just like you to make a comment
on the combination of hierarchical structures
in problem solving rather than just plane parallel
processing or sequential.
Using hierarchical structures to enhance some of the approaches
that you've discussed.
What will that give you?
Could you be more specific please?
To have a hierarchical structure is
where you have the main task master that
control the sequence of operations that
is done at the lower level of the sequence of activities that
is being done in parallel.
Where we are the local members or local elements
have a chance to communicate among themselves
as well as direct information to the higher level task master.
Oh, I think I see.
I've shown simply two level hierarchy.
At most, I've shown a single global force for, for example,
broadcasting.
And then, sort of homogeneous array of processes.
One might imagine a more complex hierarchical structuring
of the processing elements.
Yes.
Is that your suggestion?
Yes.
I think that is a largely unexplored area.
That's another thing that I would
regard as an open research topic as to the best way
to organize that.
And the difficulty is providing the flexibility
at the programming level to be able to organize
the hierarchy in a way demanded by the problem.
We have seen a number of hardware architectures
that organize hardware processing elements
hierarchically, but with more or less ability to reorganize
those processors.
Because I don't think it's well enough
understood how to make a sufficiently flexible
communication system that allows you to restructure
the hierarchy unless, of course, you provide a completely
general communication system.
In which case, the hierarchy, again,
disappears to the hardware level.
And it's up to the language implementer to provide
that hierarchical organization at the language level.
And we have not yet seen that emerging either.
And that's a very good point.
So thus far, the algorithms for solving mixed integer--
say, maybe linear programming.
But when you have nonlinear [INAUDIBLE]
integer programming, one of the topics you covered
include enumeration.
So which suggests that if we really
want to solve the class of branch unbound problems
that you require either deep search or [INAUDIBLE] search.
This parallel processing might be a very important tool
to solve some-- to solve the problem of mixing
nonlinear type programming with branch and bounding.
Yeah, it may well be.
It is sometimes possible to use data parallel techniques to do
what look like unstructured searches in, for example,
a tree, for example, a game tree using branch
and bound techniques or other techniques related
to it by maintaining a work queue,
very much as you might in a more controlled parallel
oriented style.
And at every step, taking a large number of task items
off that work queue simultaneously
by using an enumeration step and using
the result of that enumeration to assign
[INAUDIBLE] processors.
Sometimes it's effective providing the rest of the work
to be done each of these tasks is sufficiently similar.
If it's not, then control parallelism
may be more suited to a task like that.
[INAUDIBLE] the Netherlands.
With the current expertise-- software expertise in 4GL,
four generation languages for sequential machines,
I would like to know your view if developing of data parallel
programming languages will it and at least that for 4GL
level or up.
I have seen the development of software
based on the data parallel paradigm.
I was about to say parallel.
Let me say reenact the history of the development
of sequential programming languages and software systems.
And I think we are now at the point
where we understand how to make data parallel
languages at about the level of expressiveness
of C Fortran, possibly lisp.
And I think it's going to take a while before we can rework
our understanding of this to raise
the level of expressiveness to that of fourth generation
languages.
I think it's just a matter of time and learning.
We still don't understand how to fit these building
blocks together to make abstractions at that level.
And I think that's great because it
would be no fun if there weren't interesting new problems
to work on.
[MUSIC PLAYING]