So what we learned last week was that scan can be computed efficiently
on n elements with run time proportion to n.
And we also learned that it can be completed with a number of steps proportional to log n.
This is something we can implement very efficiently on the GPU.
And because we can implement it efficiently, what we'll find today
is that it's the core of a significant number of interesting parallel parameters.
And we're going to start with one called compact.
我们上周学到的是, 扫描可以有效地
对 n 个元素进行计算,运行时间与n成比例。
我们也知道它可以通过与log n成比例的步数来完成。
这是我们可以在 GPU 上非常有效地实现的。
因为我们可以有效地执行,我们今天就会发现,
这是相当多的有趣的并行参数的核心所在。
我们将要开始讲的一个,叫做压缩。