0

我有这个数组（A），其中有 n 个元素，这些元素保证被排序，我需要在并行系统中对它们执行二进制搜索。我从制作这个二分搜索算法开始。它是迭代的，因为我还不确定如何将递归合并到并行处理中。

/* Looking for element k in array A of length n */
min = 0;
max = n - 1;
while(min <= max)
{
    midpoint = min + ((max-min)/2); //index
    if(A[midpoint] > k) //discard upper half
        max = midpoint - 1;
    else if(A[midpoint] < k) //discard lower half
        min = midpoint + 1;
    else
        return midpoint; //Found k, return index
}
return -1; //not found

在并行算法中，我可以访问 p 个处理器，它是一个允许并发读取但独占写入的系统。真正的问题是我仍在按顺序思考。也就是说，我似乎看不出有任何方法可以使用多个处理器来完成，因为您不能在不首先知道您在中点值方面的位置的情况下“丢弃”阵列中不需要的部分。它似乎天生是顺序的。

伪代码：

Global:  //Variables accessible by all processors
  index; //index of k
  p;     //number of processors
  i;     //the i^th processor
  n;     //number elements in array A
  A[0, 1, ... , (n-1)];
local:   //Variables accessible by only the owning processor
         //Not sure what I need yet
Begin
  Spawn(P1, P2 . . . P(p-1)); //"create" the p processors
  for all P where 0 <= i <= (p-1) do //each processor does the following code
    //I'm stuck here
  endfor
End

最后一件事：我看到一个用户发布的问题，询问是否有办法通过并行处理进行二进制搜索。这个问题没有真正决定性的答案，因为两个相关的答案都获得了 1 票。一个人说这实际上是不可能的，因为这是一个循序渐进的过程，而另一个人似乎非常有信心它会很容易实施。你觉得呢？你有没有什么想法？

上一个并行二分搜索问题

4

2 回答 2

3

虽然在技术上可以使二进制搜索并行运行，但我不建议这样做。

并行运行的最佳算法是那些具有彼此分离的离散元素并且可以同时运行的算法。例如，将 3d 图形渲染到视频中是很好的，因为每一帧都是独立的，并且可以提供给单独的处理器。

您可以将树分成多个段，以便每个处理器都有工作要做，但考虑到二进制搜索的性质，只有许多处理器中的一个会找到答案，因此浪费了所有其他处理器的计算工作在他们的段中有搜索元素。这甚至没有考虑线程的开销。

现在，如果另一方面您要对单个二叉树进行一系列搜索，那将是另一回事。您可以有一个作业队列，您的所有线程都从中提供，执行二进制搜索并响应。这样，您可以并行运行许多搜索，而不是搜索的一部分。如果您希望进一步优化它，您还可以实现缓存。

简而言之，不要尝试跨处理器拆分单独的二进制搜索，因为除了浪费处理器时间之外，您不会获得任何收益。但是，如果您正在执行许多搜索，则可以通过并行运行许多搜索来获得收益。

于 2012-11-27T03:42:42.783 回答
3

与并行解决的所有问题一样……这在很大程度上取决于您的数据大小、消息/共享内存的速度以及您的要求。

写锁有多快，同步有多快？如果它们足够快（例如，在单台机器上使用共享内存）并且您的数据量足够大，那么特定类型的“拆分并运行”技术可能会起作用。你可以这样想：

二进制搜索是一种分而治之的方法，您在每次迭代后更新您正在检查的范围 - 每次迭代时范围减半。与其将当前范围划分为 2，不如将其划分为多个p部分，其中每个进程负责其中一个部分；在每次迭代中，“获胜”部分（目标值在其范围内的部分）将要搜索的新范围写入内存，并在开始下一次迭代之前同步进程。如果您有足够的数据，那么从将数据减半到p每次都减少数据可能是一个胜利。你会从 $O(log_2(x))$ 到 $O(log_p(x))$。

这种方法只有在写入和同步足够快的情况下才有效，因为它依赖于大量的写入和同步。如果您在集群中执行此操作，这些将变得昂贵。如果进程之间的通信很困难，也许你能做的最好的就是你链接到的另一篇文章中建议的“拆分并运行”。具体来说，获取p排序列表的每个元素，并将其放在不同的节点上。然后，当请求进来时，在所有节点上进行二进制搜索。如果数组中的值是唯一的，则只有一个节点会找到答案，并且该节点可以返回结果。这是一个相对较差的并行性，因为你重复了很多工作——你忽略了之间存在的顺序不同节点上的数组。但它会让你从 $O(log_2(x))$ 加速到 $O(log_2(x/p))$。

在实践中，很难提前知道哪种方法在您的硬件上运行良好。通常，您必须在确保所有进程始终处于活动状态和确保不会因通信开销而浪费太多时间之间取得经验平衡。

于 2012-11-27T03:44:52.017 回答