0

我有一个设计如下的功能：

int brutesearch(startNumber,endNumber);

如果通过执行线性搜索与我的条件匹配，则此函数返回正确的数字，如果在搜索的数字中未找到，则返回 null。

比如说：

  • 我想搜索所有 6 位数字以找到一个做我想做的事情的数字
  • 我可以多线程运行 brutesearch() 函数
  • 我有一台 4 核的笔记本电脑

我的问题如下：

优化此搜索的最佳选择是什么？将数字空间划分为 4 个段并在每个内核上运行 4 个函数 1 实例？或者例如划分为 10 个段并一起运行，或者划分为 12 个段并使用队列以 4 个为一组运行它们？

有任何想法吗？

4

2 回答 2

0

没有普遍的答案。您需要提供更多信息。

如果您的每个比较完全独立于其他比较，并且没有机会在全局资源中保存计算，则说不涉及全局哈希表，并且您的操作都在一个阶段完成，

那么您最好的选择是将您的问题空间划分为您可用的核心数量，在这种情况下为 4，并将 1/4 的数据发送到每个核心。

例如，如果您有 1000 万个唯一数字要测试素数。或者，如果您有 1000 万个密码试图散列以找到匹配项，则只需除以 4。

如果你有一个现实世界的问题，那么你需要更多地了解底层操作以获得一个好的解决方案。例如，如果涉及全局资源，那么除非您以某种方式隔离全局资源上的操作，否则您不会从并行性中获得任何改进。

于 2013-05-31T13:18:18.337 回答
0

对您的搜索条件一无所知（内存子系统可能会产生其他考虑），这里的权衡是让某些处理器比其他处理器做更多工作的成本（例如，因为搜索谓词在某些值上比其他值更快，或者因为安排了其他线程）以及协调工作的成本。一个对我来说效果很好的策略是有一个工作队列，线程每次都从该队列中获取剩余任务的常量/#threads 部分，但是只有四个处理器，虽然运行时间真的很长，但很难出错胜利在于算法。

于 2013-05-31T13:01:49.417 回答