并行约简算法实现

Question

我一直在研究implementations、折叠的实现，不管你想把它称为Objective中使用块的函数，我想知道是否有任何技术来并行计算，其中应用的函数是关联(例如，整数集合的和)？

例如，在NSArray上可以并行化或改进这样的东西吗：

- (id)reduceWithBlock:(id (^)(id memo, id obj))block andAccumulator:(id)accumulator
{
  id acc = [[accumulator copy] autorelease];

  for (id obj in self) {
    acc = block(acc, obj);
  }
  return acc;
}

用中央调度吗？

编辑:我做了第二次尝试，将数组划分成更小的块，并在单独的分派队列中减少它们，但是在我的测试中没有明显的性能提高：(要点在此)

Answer 1

您可以在Dispatch中使用应用来并行化它，但是您的代码似乎在并发工作中效率不高。因为累加器对象需要独占访问，而且它被块紧紧地使用，因此它将给累加器对象造成巨大的锁定。

例如，即使在调度全局队列中使用dispatch_apply，此代码几乎是非并发工作。

dispatch_semaphore_t sema = dispatch_semaphore_create(1);
dispatch_queue_t queue =
    dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
dispatch_apply([array count], queue, ^(size_t index) {
    dispatch_semaphore_wait(sema, DISPATCH_TIME_FOREVER);
    acc = block(acc, [array objectAtIndex:index]);
    dispatch_semaphore_signal(sema);
});
dispatch_release(sema);

您需要拆分块和累加器实现高效的并行化。

编辑：

(我没有检查您的代码的算法。)

dispatch_queue_t result_queue = dispatch_queue_create(NULL, NULL);

您正在使用串行队列。串行队列一次执行一个块。因此，它可能是

dispatch_queue_t result_queue =
    dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);

或

dispatch_queue_t result_queue = dispatch_queue_create(NULL, DISPATCH_QUEUE_CONCURRENT);
/* DISPATCH_QUEUE_CONCURRENT is only available OS X 10.7/iOS 4.3 or later. */

Answer 2

实现了一种并行分而治之算法，它与关联函数这里一起工作。不幸的是，我无法从它得到任何明显的加速，所以我现在坚持一个简单的串行版本。我认为我的基本情况需要优化--我在某个地方读到了n >= p^2应该保持的不等式，其中n是作业的数量，p是处理器的数量。

显然，在数组分割和递归上浪费了很多时间，如果有人有建议的话，他们会非常感激的。