Параллельная реализация алгоритма уменьшения - PullRequest
Новая
       16

Параллельная реализация алгоритма уменьшения

4 голосов
/ 17 июля 2011

Я изучал реализации функций Redu [inject, fold, как вы хотите это называть] в Objective-C, используя блоки, и мне было интересно, есть ли какие-либо методы для распараллеливания вычислений, где применяемая функция равна ассоциативно (например, сумма набора целых чисел)?

т.е. Можно ли распараллелить или улучшить что-то подобное на 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;
}

Используя грандиозно-центральную диспетчеризацию?

РЕДАКТИРОВАТЬ: я предпринял вторую попытку, разделив массив на более мелкие порции и сократив их в отдельных очередях отправки, но в моем тестировании заметного прироста производительности нет: (суть здесь)

Ответы [ 2 ]

6 голосов
/ 17 июля 2011

Вы можете использовать dispatch_apply с Dispatch Global Queue для его распараллеливания, но ваш код кажется не таким эффективным при одновременной работе. Поскольку объект-аккумулятор требует монопольного доступа, и он плотно используется блоком, он вызовет гигантскую блокировку объекта-аккумулятора.

Например, этот код почти не работает одновременно, даже если использовать dispatch_apply с Dispatch Global Queue. 

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. */
1 голос
/ 23 июля 2011

Я реализовал параллельный алгоритм «разделяй и властвуй», который работает с ассоциативными функциями здесь . К сожалению, я не смог получить никакого ощутимого ускорения от этого, поэтому я пока придерживаюсь простой последовательной версии. Я считаю, что мой базовый случай нуждается в оптимизации - я где-то читал, что должно выполняться неравенство n >= p^2, где n - количество заданий, а p - число процессоров.

Очевидно, что много времени теряется на разбиение и повторение массивов, если у кого-то есть предложения, они будут высоко оценены.

...