并行化约简算法的实现

Question

我一直在研究使用块实现 Objective-C 中的 reduce [inject，fold 或者你想叫它什么] 函数，并且想知道是否有任何技术可以并行计算应用的函数是可结合的（例如整数集合的总和）？

也就是说，是否可能并行化或改进类似于下面对 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;
}

使用Grand Central Dispatch吗？

编辑：我进行了第二次尝试，将数组分成较小的块并在单独的调度队列中进行减少，但在我的测试中没有明显的性能提升：（此处为代码）

- Chris Mowforth

Answer 1

你可以使用Dispatch Global Queue和dispatch_apply来实现并行化，但是你的代码似乎在并发工作方面并不那么高效。因为累加器对象需要独占访问，并且它被块密切使用，因此会导致累加器对象的巨大锁定。

例如，即使使用Dispatch Global Queue和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. */

- Kazuki Sakamoto

---

谢谢，我已经追求过了。当我重新分配acc和semaphores的值时，dispatch_apply似乎不喜欢它，而信号量只会使整个过程变慢。我的上述一般模式可以在Github上的几个库中找到。我想知道是否有任何已知的算法（用任何语言）可以并行执行此操作。 - Chris Mowforth

谢谢你提醒我关于DISPATCH_QUEUE_CONCURRENT常量的事情，我没有看过Lion中libdispatch的更新，现在我获得了大概45%的速度提升，这看起来很合理。 - Chris Mowforth

太厉害了！这是我在这里找到的最好的关于并行性的答案。 - Gustavo Barbosa

Answer 2

我实现了一个并行分治算法，它可以与关联函数这里一起工作。不幸的是，我无法从中获得任何明显的加速效果，所以现在我仍然使用简单的串行版本。我相信我的基本情况需要优化-我在某个地方读到过这个不等式n >= p^2应该成立，其中n是作业数，p是处理器数。

显然，在数组拆分和递归上浪费了很多时间，如果有人有建议，将不胜感激。

- Chris Mowforth