У меня есть вложенный цикл. Я хотел бы знать, можно ли распараллелить внешний и внутренний циклы с помощью openmp?
for (col = n-1; col >= 0; col--) {
x[col] /= A[col][col];
for (row = 0; row < col; row++)
x[row] -= A[row][col] * x[col];
}
Я думаю, что внешний цикл можно распараллелить, поскольку внутренний цикл зависит только от фиксированного значения столбца или столбца.
@Wyck - Да, это правильный ответ, но я не совсем понял твое объяснение. x[col] не зависит от x[col+1]. Если col = 3 (если n = 4), то x[3],x[2],x[1],x[0] вычисляются в своей отдельной итерации цикла как значение col итераций. Может быть, я где-то ошибаюсь.
Представьте, что вы находитесь на итерации, где col == 5
. и row == 4
. Вы выступаете x[4] -= A[4][5] * x[5]
. У вас есть x[4]
слева от =
и x[5]
справа от =
. Итак, x[4]
зависит от x[5]
. Это означает, что x[5]
должно быть вычислено до x[4]
. И, вообще говоря, x[i]
зависит от x[i+1]
(так как он вычислялся в итерации внешнего цикла, где col
= i+1
). Таким образом, значения x должны быть вычислены последовательно в порядке убывания.
Спасибо за подробное объяснение! Я проанализировал ваш ответ и увидел, что если мы распараллелим внешний цикл, то это не проблема. Если я рассмотрю ваш пример выше с col==5 и row==5, я понимаю, что x[4]-=A[4]*A[5]*x[5]... поэтому x[4] зависит от x[5], но x[5] уже вычислено в приведенном выше выражении x[5] /=A[5][5]... так что x[5] всегда вычисляется в текущей итерации. Поэтому каждый раз, когда зависимость уже вычисляется вне внутреннего цикла...
Вы упускаете важный аспект изменчивости. Когда у вас есть x += c
(то есть просто x = x + c
), вы мутируете переменную. Для проведения анализа зависимостей следует заменить все изменяемые символы неизменяемыми константами. например x_1 = x_0 + c
. Исходное значение x
обозначается x_0
. И если мы хотим изменить x
, то мы создаем новый символ x_1
, а если мы хотим изменить x
еще раз, мы создаем еще один новый символ x_2
, увеличивая «номер поколения» после подчеркивания, чтобы отслеживать каждую модификацию изменяемого x
, заменив их неизменяемыми x_i
константами.
Еще один отличный способ быстро проанализировать, можно ли его распараллелить: если вы можете запустить цикл в противоположном направлении (или в случайном порядке), его можно распараллелить. Ваш внутренний цикл работает нормально, если вы измените направление итерации. Но ваш внешний цикл сломается, если вы измените порядок итерации, потому что у вас есть зависимость от цикла. Это означает, что состояние в конце цикла зависит от порядка выполнения итераций внутри цикла.
Достаточным условием (но не необходимым!) распараллеливания является
В таком случае итерации i1
и i2
не могут записывать в конфликтующие места, поэтому записи могут выполняться в любом порядке, то есть параллельно.
В вашем коде внутренний цикл удовлетворяет этому условию; ваш внешний нет. Это потому, что внутренний цикл записывает целую кучу индексов, а не только [col]
. Таким образом, два разных значения col
будут записываться в одинаковые места. Иногда вы можете исправить это с помощью директивы atomic
, но это 1. не очень хорошо для производительности 2. даже невозможно в вашем конкретном случае из-за неассоциативности выполняемых вами операций.
Я думаю, что атомарные операции решают только гонку данных, но результат также зависит от порядка внешнего цикла (потому что порядок деления и вычитания нельзя поменять местами).
@Laci Ты абсолютно прав. Я изменил свой ответ.
Что касается внешнего цикла, вычисленное значение
x[i]
зависит от вычисленного значенияx[i+1]
, поэтому мне кажется, что его нужно вычислять последовательно. Однако внутренний цикл может выполняться параллельно. Не уверен, что вы много сэкономите на этом, хотя это такой крошечный объем работы.