We're going to introduce one of the most important parallel primitives--scan.
Let me give you a very short example of a scan operation.
The input to scan is a list of numbers, such as 1, 2, 3, 4,
and an operation, such as add,
and the output is the running sum of those numbers.
So each output is the sum of all the numbers in the input up to that given point.
6 is the sum of 1, 2, and 3.
Scan is important because it allows us to address a set of problems
that seem difficult to parallelize.
At first glance it might seem difficult to compute this output from this input in parallel
because each element in the output depends on the previous element.
So 1st we compute this, add 2 and get 3, add 3 and get 6, add 4 and get 10.
That doesn't seem like a very parallel operation.
But this style of operation turns out to be incredibly useful.
It's also interesting because scan is just not a very useful operation in the serial world.
It's really only useful when you're doing parallel computation.
But once you know it and use it, you'll wonder what you ever did without it.
There's lots of uses for scan, with compaction and allocation being 2 of the most popular.
Later in this lecture we'll discuss histogram, which uses scan.
And our research group has used scan for quick sort, for sparse matrix computation,
and for data compression, among others. It's a very useful parallel primitive.
But for this part of the lecture I'm only going to concentrate on what scan does
and how it works rather than how it's useful.
We'll learn about some more general scan applications in the next unit.
我们将要介绍一种最重要的并行原语--扫描
让我给大家举一个简短的扫描运算例子
需要扫描的输入是一列数字,比如1、2、3、4,
以及一个运算,比如,加,
输出则为那些数字的当前和。
所以每个输出都是运行到指定点的数字之和。
6是1、2、3相加的总和。
扫描很重要因为它允许我们解决一组
看起来难以并行化的问题。
乍看之下 可能很难以并行方式从这个输入计算这个输出
因为输出的每个元素都依赖之前的元素。
所以首先我们计算这个,加2得到数字3,
再加3得到6,再加4得到10。
这看起来不十分像一个并行计算。
但这种运算的方式被证实是异常有用的。
它同样也非常有趣,因为扫描在串行世界中不是一个非常有用的运算。
它实际上仅在你做并行计算时才会变得有用。
但一旦你掌握并使用它 你会发现你该早点接触到它的。
扫描有很多用处,其中压缩和分配是最普遍2个。
在本课程的稍后部分,我们会讨论直方图,它会使用扫描。
而且我们的研究小组已经使用扫描用于快速分类,
以及稀疏矩阵计算,
还有数据压缩,及其他地方。它是非常有用的并行原语。
但对于本课程座的这部分来说 我只打算集中精力阐述扫描能做什么
以及它如何工作,而非它有多大用处。
我们将在下面的单元中学习一些更普遍的扫描应用程序。