Распараллеливание алгоритма со многими точками выхода? - PullRequest
Новая
       2

Распараллеливание алгоритма со многими точками выхода?

5 голосов
/ 31 марта 2012

Я столкнулся с распараллеливанием алгоритма, который в своей последовательной реализации проверяет шесть граней куба мест расположения массива в гораздо большем трехмерном массиве. (То есть выберите элемент массива, а затем определите куб или кубоид вокруг этого элемента 'n' элементов, удаленных по x, y и z, ограниченных границами массива.

Каждая рабочая единица выглядит примерно так (псевдокод Fortran; последовательный алгоритм в Fortran): 

do n1=nlo,nhi
  do o1=olo,ohi          
    if (somecondition(n1,o1) .eq. .TRUE.) then
       retval =.TRUE.
       RETURN
    endif    
  end do 
end do

Или псевдокод C: 

for (n1=nlo,n1<=nhi,n++) {
  for (o1=olo,o1<=ohi,o++) {
    if(somecondition(n1,o1)!=0) {
      return (bool)true;
    }
  }
}

В общем алгоритме есть шесть таких рабочих единиц, где значения 'lo' и 'hi' обычно находятся в диапазоне от 10 до 300.

Я думаю, что лучше всего было бы запланировать шесть или более потоков выполнения, циклически, если не так много ядер ЦП, в идеале с циклами, выполняющимися параллельно, с целью, аналогичной последовательному алгоритму. : somecondition() становится True, выполнение среди всех потоков должно быть немедленно остановлено, и значение True устанавливается в общей папке.

Какие методы существуют в компиляторе Windows для облегчения распараллеливания таких задач? Очевидно, что мне нужен главный поток, который ожидает семафор или завершение рабочих потоков, поэтому существует необходимость во вложении и передаче сигналов, но мой опыт работы с OpenMP является вводным на данном этапе.

Существуют ли механизмы передачи сообщений в OpenMP?

РЕДАКТИРОВАТЬ: Если наибольшая разница между "nlo" и "nhi" или "olo" и "ohi" составляет от восьми до десяти, это будет означать не более 64-100 итераций для этого вложенного цикла и не более 384 до 600 итераций для шести рабочих блоков вместе. Исходя из этого, стоит ли вообще распараллеливать?

Ответы [ 5 ]

3 голосов
/ 08 апреля 2012

Было бы лучше распараллелить цикл над элементами массива и оставить этот алгоритм последовательным, когда несколько потоков запускают алгоритм на разных элементах массива? Я думаю об этом из вашего комментария: «Расход времени обусловлен тем фактом, что каждый элемент в массиве должен быть проверен следующим образом. Массивы обычно содержат от четырех миллионов до двадцати миллионов элементов». Проект реализации параллелелизации элементов массива также гибок с точки зрения количества потоков. Разве есть причина, по которой элементы массива должны проверяться в каком-то порядке?

Похоже, что часть, которую вы показываете нам, не занимает много времени, поэтому выполнение ее требует меньше времени, поскольку параллельное выполнение может быть непростым ... всегда есть некоторые издержки для нескольких потоков, и если не так уж много времени, параллельный код не может быть быстрее.

1 голос
/ 12 апреля 2012

Одной из возможностей является использование OpenMP для распараллеливания по 6 циклам - объявите logical :: array(6), разрешите выполнение каждого цикла до завершения, а затем retval = any(array).Затем вы можете проверить это значение и вернуться за пределы параллельного цикла.Добавьте schedule(dynamic) в параллельный оператор do, если вы делаете это.Или выделите !$omp parallel, а затем поместите !$omp do schedule(dynamic) ... !$omp end do nowait вокруг каждой из 6 петель.

Или вы можете следовать совету @MSB и распараллеливать внешний цикл по всему массиву.Проблема здесь в том, что вы не можете иметь RETURN внутри параллельного цикла, поэтому пометьте второй самый внешний цикл (самый большой в параллельной части) и EXIT этот цикл - что-то вроде 

retval = .FALSE.
!$omp parallel do default(private) shared(BIGARRAY,retval) schedule(dynamic,1)
do k=1,NN
   if(.not. retval) then
      outer2: do j=1,NN
         do i=1,NN
            ! --- your loop #1
            do n1=nlo,nhi
               do o1=olo,ohi
                  if (somecondition(BIGARRAY(i,j,k),n1,o1)) then
                     retval =.TRUE.
                     exit outer2
                  endif
               end do
            end do
            ! --- your loops #2 ... #6 go here
         end do
      end do outer2
   end if
end do 
!$omp end parallel do

[править: оператор if предполагает, что вам нужно выяснить, есть ли хотя бы один такой элемент в большом массиве.Если вам нужно вычислить условие для каждого элемента, вы также можете добавить фиктивный цикл выхода или goto, пропуская оставшуюся обработку для этого элемента.Опять же, используйте расписание (динамическое) или расписание (управляемое).]

В качестве отдельной точки, вы также можете проверить, может ли быть хорошей идеей пройти внутренний цикл на более крупный шаг (в зависимости отпо размеру с плавающей запятой), вычисляет вектор логики на каждой итерации и затем агрегирует результаты, например.что-то вроде if(count(somecondition(x(o1:o1+step,n1,k)))>0);в этом случае компилятор может векторизовать somecondition.

1 голос
/ 09 апреля 2012

Вы уже упомянули очевидный способ остановить все потоки, как только какой-либо поток найдет конечное условие: каждый из них проверяет некоторую общую переменную, которая дает статус конечного условия, определяя, таким образом, выходить ли из циклов.Очевидно, что это накладные расходы, поэтому, если вы решите воспользоваться этим подходом, я бы предложил несколько вещей:

  1. Использование атомарных элементов для проверки конечного условия, это позволяет избежать дорогостоящей очистки памяти как переменной.под вопросом покраснел.Переходите к OpenMP 3.1, поддерживаются некоторые новые атомарные операции.

  2. Проверяйте нечасто, возможно, как один раз за внешнюю итерацию.Вы должны распараллеливать только большие случаи, чтобы преодолеть издержки многопоточности.

  3. Это необязательно, но вы можете попробовать добавить подсказки компилятора, например, если вы ожидаете, что определенное условие будет ложнымвремени компилятор соответствующим образом оптимизирует код.

Другой (несколько грязный) подход заключается в использовании общих переменных для диапазонов цикла для каждого потока, возможно, использование общего массива, где индексn для потока n.Когда один поток находит конечное условие, он изменяет диапазоны цикла всех других потоков так, что они останавливаются.Вам понадобится соответствующая синхронизация памяти.По существу, накладные расходы теперь перешли от проверки фиктивной переменной к синхронизации / проверке условий цикла.Опять же, возможно, не так хорошо делать это часто, поэтому, возможно, используйте переменные общего внешнего цикла и переменные частного внутреннего цикла.

С другой стороны, это напоминает мне классическую проблему опроса и прерывания.К сожалению, я не думаю, что OpenMP поддерживает прерывания, когда вы можете посылать какой-либо сигнал уничтожения каждому потоку.

Есть хакерские обходные пути, такие как использование дочернего процесса только для этой параллельной работы и вызов планировщика операционной системы.эмулировать прерывания, однако это довольно сложно получить корректно и сделать ваш код крайне непереносимым.

Обновление в ответ на комментарий:

Попробуйте что-то вроде этого: 

char shared_var = 0;
#pragma omp parallel
{
  //you should have some method for setting loop ranges for each thread
  for (n1=nlo; n1<=nhi; n1++) {
    for (o1=olo; o1<=ohi; o1++) {
      if (somecondition(n1,o1)!=0) {
        #pragma omp atomic write
        shared_var = 1;  //done marker, this will also trigger the other break below
        break;           //could instead use goto to break out of both loops in 1 go
      }
    }
    #pragma omp atomic read
    private_var = shared_var;
    if (private_var!=0) break;
  }
}
1 голос
/ 31 марта 2012

Полагаю, вы можете делать то, что хотите, с помощью конструкции задачи, представленной в OpenMP 3; Intel Fortran поддерживает работу с задачами в OpenMP. Я не часто использую задачи, поэтому я не буду предлагать вам какой-нибудь вонючий псевдокод.

0 голосов
/ 04 апреля 2012

Подходящий параллельный подход может заключаться в том, чтобы позволить каждому работнику изучить часть общей проблемы, точно так же, как в последовательном случае, и использовать локальную (не разделяемую) переменную для результата (retval).Наконец, сделайте сокращение всех рабочих по этим локальным переменным в общий общий результат.

...