Блог

Главная - Вопросы по программированию - распараллеливание с использованием openmp

распараллеливание с использованием openmp

#c #parallel-processing #openmp

#c #параллельная обработка #openmp

Вопрос:

У меня есть эта функция, которую я хотел бы распараллелить с помощью openmp:

 for(i=len-1;i>=0;i--){
  if(bin[i]==49) // bin is a binary number amp; is
                 // stored in a string. 49 is ascii value of 1
  {
     s=(s*x)%n;    
  }
  x=(x*x)%n;
}

Я пытался использовать #pragma omp parallel for , но это не сработало. Я тоже пробовал с функцией сокращения, но все же получил неправильные ответы.
Я думаю, причина в том, что значение s зависит от x (которое зависит от значения каждого шага).

Ответ №1:

Вы правы, что зависимость от x вызывает проблемы. Эта зависимость существует между итерациями. Для каждой итерации требуется x из предыдущей итерации. Таким образом, он делает весь цикл не распараллеливаемым.

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

Итак, вкратце: нет, вы не сможете его распараллелить. Зависимость заложена в используемом вами алгоритме.

Комментарии:

1. Итак, есть ли какой-либо другой способ реализовать это, чтобы сделать это чрезвычайно быстрым? Я пытаюсь реализовать алгоритм RSA для больших чисел. Но, скажем, для простого числа из 50 цифр, для расшифровки требуется около 1 часа. Эта функция занимает слишком много времени.

2. Поскольку вы не можете выполнить распараллеливание здесь, вам нужно будет сделать это на более высоком уровне. Если у вас есть несколько из этих powermods для выполнения (и они независимы), вы можете выполнять их параллельно. Хотя я не слишком знаком с алгоритмом RSA, поэтому я не знаю, насколько велик параллелизм на более высоких уровнях.

3. Хорошо, я проверю это. Большое вам спасибо. Что насчет этого цикла? Возможно ли распараллелить? для(i=0,k=0;i

4. Пока msg() выполняется повторный ввод, тогда да, это можно распараллелить. (также убедитесь, что a и b не перекрываются)

5. На самом деле, никакого сокращения не требуется. Так что просто используйте #pragma omp parallel for . Сокращения необходимы только тогда, когда результат итераций будет «уменьшен» до переменной. (например, суммирование всех элементов) Но в вашем примере вы этого не делаете. Вы записываете в разные элементы массива b . Таким образом, сокращения нет.