並列削減アルゴリズムの実装

Question

私はブロックを使ってObjective-Cのreduce [inject、fold、何でもそれを呼び出す]関数の実装を調査していましたが、関数が適用された計算を並列化する技術があるのか​​疑問に思っていましたassociative（例えば、整数の集合）？

- (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; 
} 

壮大-中央派遣の使用：

すなわちそれは、並列化やNSArrayの上でこのような何かを改善することは可能ですか？

編集：私は小さいチャンクに配列を分割して別々のディスパッチキューにそれらを減らすこと、第二の試みを行ってきましたが、私のテストで認識可能なパフォーマンスの向上もありません：(gist here)

Answer 1

あなたが派遣グローバルキューで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); 

効率的な並列化のためにブロックとアキュムレータの実装を分割する必要があります。

EDITED：

（私はあなたのコードのアルゴリズムを確認していない。）あなたは、シリアルキューを使用している

dispatch_queue_t result_queue = dispatch_queue_create(NULL, NULL); 

。シリアルキューは一度に1ブロックを実行します。したがって、それは

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

かもしれない私は連想機能hereで動作する並列分割&統治アルゴリズムを実装します。残念ながら、私はそれから識別できるスピードアップを得ることができませんでしたので、私は今は単純なシリアルバージョンを採用しています。私はベースケースが最適化を必要としていると信じています。不等式n >= p^2が成り立つはずのどこかを読んでいます。ここで、nはジョブの数、pはプロセッサの数です。

明らかに、配列分割と再帰で多くの時間が失われています。もし誰かが示唆を持っていれば、大いに感謝するでしょう。