Возможность неоднозначности вычислений в параллельных программах

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

Данный эффект может проявляться в силу изменения каких-либо условий выполнения программы, что может повлиять на временные соотношения между потоками (рис. 6.5). Взаиморасположение потоков по области расчетов может быть различным: одни потоки могут опережать другие и, обратно, часть потоков могут отставать (при этом, характер взаиморасположения может меняться в ходе вычислений).

 

Такое поведение параллельных участков программы называют состязанием потоков (race condition) и оно отражает важный принцип параллельного программирования – временная динамика выполнения параллельных потоков не должна учитываться при разработке параллельных алгоритмов и программ.

Рис. 6.5. Возможные различные варианты взаиморасположения параллельных потоков (состязание потоков)

В рассматриваемом примере при вычислении нового значения в зависимости от условий выполнения могут использоваться разные (от предыдущей или текущей итераций) оценки соседних значений по вертикали. А количество итераций метода до выполнения условия остановки и конечное решение задачи может различаться при повторных запусках программы. Получаемые оценки величин будут соответствовать точному решению задачи в пределах задаваемой точности, но могут различаться. Использование вычислений такого типа для сеточных алгоритмов получило наименование метода хаотической релаксации (chaotic relaxation).

Проблема взаимоблокировки

Возможный подход для получения однозначных результатов (уход от состязания потоков) может состоять в ограничении доступа к узлам сетки, которые обрабатываются в параллельных потоках программы. Для этого можно ввести набор семафоров row_lock[N], который позволит потокам закрывать доступ к "своим" строкам сетки:

// поток обрабатывает i строку сетки omp_set_lock(row_lock[i]); omp_set_lock(row_lock[i+1]); omp_set_lock(row_lock[i-1]); // <обработка i строки сетки> omp_unset_lock(row_lock[i]); omp_unset_lock(row_lock[i+1]); omp_unset_lock(row_lock[i-1]);

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

Данный подход демонстрирует еще одну проблему, которая может возникать в ходе параллельных вычислений. Эта проблема состоит в том, что при организации доступа к множественным общим переменным может возникать конфликт между параллельными потоками и этот конфликт не может быть разрешен успешно. Так, в приведенном фрагменте программного кода при обработке потоками двух последовательных строк (например, строк 1 и 2) может сложиться ситуация, когда потоки блокируют сначала строки 1 и 2 и только затем переходят к блокировке оставшихся строк (рис. 6.6). В этом случае доступ к необходимым строкам не может быть обеспечен ни для одного потока – возникает неразрешимая ситуация, обычно именуемая тупиком. Как отмечалось в главе 5 пособия, необходимым условием тупика является наличие цикла в графе распределения и запросов ресурсов. В данном примере уход от цикла может состоять в последовательной схеме блокировки строк потока

// поток обрабатывает i строку сетки omp_set_lock(row_lock[i+1]); omp_set_lock(row_lock[i]); omp_set_lock(row_lock[i-1]); // <обработка i строки сетки> omp_unset_lock(row_lock[i+1]); omp_unset_lock(row_lock[i]); omp_unset_lock(row_lock[i-1]);

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

Рис. 6.6. Ситуация тупика при доступе к строкам сетки (поток 1 владеет строкой 1 и запрашивает строку 2, поток 2 владеет строкой 2 и запрашивает строку 1)