Как узнать, можно ли распараллелить циклы для многопоточности с помощью openmp?

У меня есть вложенный цикл. Я хотел бы знать, можно ли распараллелить внешний и внутренний циклы с помощью 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];
}

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

Что касается внешнего цикла, вычисленное значение x[i] зависит от вычисленного значения x[i+1], поэтому мне кажется, что его нужно вычислять последовательно. Однако внутренний цикл может выполняться параллельно. Не уверен, что вы много сэкономите на этом, хотя это такой крошечный объем работы.

Wyck 15.01.2023 18:00

@Wyck - Да, это правильный ответ, но я не совсем понял твое объяснение. x[col] не зависит от x[col+1]. Если col = 3 (если n = 4), то x[3],x[2],x[1],x[0] вычисляются в своей отдельной итерации цикла как значение col итераций. Может быть, я где-то ошибаюсь.

Jeet 15.01.2023 18:27

Представьте, что вы находитесь на итерации, где 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 должны быть вычислены последовательно в порядке убывания.

Wyck 15.01.2023 18:34

Спасибо за подробное объяснение! Я проанализировал ваш ответ и увидел, что если мы распараллелим внешний цикл, то это не проблема. Если я рассмотрю ваш пример выше с 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] всегда вычисляется в текущей итерации. Поэтому каждый раз, когда зависимость уже вычисляется вне внутреннего цикла...

Jeet 15.01.2023 20:40

Вы упускаете важный аспект изменчивости. Когда у вас есть x += c (то есть просто x = x + c), вы мутируете переменную. Для проведения анализа зависимостей следует заменить все изменяемые символы неизменяемыми константами. например x_1 = x_0 + c. Исходное значение x обозначается x_0. И если мы хотим изменить x, то мы создаем новый символ x_1, а если мы хотим изменить x еще раз, мы создаем еще один новый символ x_2, увеличивая «номер поколения» после подчеркивания, чтобы отслеживать каждую модификацию изменяемого x , заменив их неизменяемыми x_i константами.

Wyck 15.01.2023 21:48

Еще один отличный способ быстро проанализировать, можно ли его распараллелить: если вы можете запустить цикл в противоположном направлении (или в случайном порядке), его можно распараллелить. Ваш внутренний цикл работает нормально, если вы измените направление итерации. Но ваш внешний цикл сломается, если вы измените порядок итерации, потому что у вас есть зависимость от цикла. Это означает, что состояние в конце цикла зависит от порядка выполнения итераций внутри цикла.

Wyck 15.01.2023 21:57
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
6
58
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Достаточным условием (но не необходимым!) распараллеливания является

  • для каждого значения переменной цикла
  • изменяются только местоположения массива с этим индексом.

В таком случае итерации i1 и i2 не могут записывать в конфликтующие места, поэтому записи могут выполняться в любом порядке, то есть параллельно.

В вашем коде внутренний цикл удовлетворяет этому условию; ваш внешний нет. Это потому, что внутренний цикл записывает целую кучу индексов, а не только [col]. Таким образом, два разных значения col будут записываться в одинаковые места. Иногда вы можете исправить это с помощью директивы atomic, но это 1. не очень хорошо для производительности 2. даже невозможно в вашем конкретном случае из-за неассоциативности выполняемых вами операций.

Я думаю, что атомарные операции решают только гонку данных, но результат также зависит от порядка внешнего цикла (потому что порядок деления и вычитания нельзя поменять местами).

Laci 16.01.2023 08:45

@Laci Ты абсолютно прав. Я изменил свой ответ.

Victor Eijkhout 16.01.2023 14:22

Другие вопросы по теме