Okay. So, let's look at these scenarios and figure out what the right choice would be.
So for the first, we're looking at a small input vector, and you've got plenty of processors.
So, you're not really worried so much about work efficiency.
You have more than enough processors to do the work that you need to do.
Thus, you're probably going to be concerned with the
step efficiency of the algorithm that you pick.
And the one with the greatest step efficiency is Hillis and Steele.
Now conversely, when you have an enormous amount of work to do,
and not nearly enough processors to do it, you're going to be looking for the
algorithm that is going to have the best work complexity.
And so, for this, if you have parallel processors, you're absolutely going to want to run the
work-efficient algorithm, Blelloch's algorithm.
Now, if you only have 1 processor to work with, you're stuck with a serial algorithm no matter what.
好的 让我们看一下这几种情况 然后判断哪个选择是正确的
首先 我们看到的是一个小的输入向量 同时我们有许多处理器
所以 你不用太过担心工作效率
你有足够的处理器来做这些需要处理的工作
因此 你很可能会关心
你选择的算法的步骤效率
那么步骤效率最佳的算法是“Hillis and Steele”算法
现在反过来 当你拥有大量的工作需要处理
却没有足够的处理器来处理 你要找的是
拥有最佳工作复杂度的算法
所以 对这个问题 如果你拥有并行处理器 你当然想要运行
工作高效算法 Blelloch算法
现在 假如你只有1个处理器来做工作 无论如何你就只能选择串行算法