Синхронизация: поиск максимального элемента массива
Рассмотрим другую задачу, которая требует синхронизации процессов. Она состоит в поиске максимального элемента массива а [п]. Предположим, что п положительно и все элементы массива — положительные целые числа.
Поиск максимального элемента в массиве а — это пример задачи накопления (сведения). В данном случае сохраняется (накапливается) максимальный из просмотренных элементов, или, иными словами, все значения сводятся к их максимуму. Пусть m — переменная для хранения максимального значения. Цель программы в логике предикатов можно описать так. (V j: 1<= j <= n: m >= a[j]) (3 j: 1<= j <= n: m = = a[j]).
Первая строка гласит, что при завершении программы значение переменной m должно быть не меньше любого значения в массиве а. Вторая строка означает, что переменная m должна быть равна некоторому значению в массиве а.
Глава 2. Процессы и синхронизация 55
Для решения данной задачи можно использовать такую последовательную программу.
int m = 0;
for [i = 0 to n-1] { if (a[i] > m)
m = a [ i ] ; }
Эта программа итеративно просматривает все значения в массиве а; если находится какое-нибудь значение больше текущего максимума, оно присваивается т. Поскольку предполагается, что значения элементов массива положительны, можно без опасений инициализировать переменную m значением 0.
Теперь рассмотрим способы распараллеливания приведенной программы. Предположим, что цикл полностью распараллелен с помощью параллельной проверки всех элементов массива.
int m = 0,-co [i = О to n-1] if (a[i] > m) m = a [ i ] ;
Эта программа некорректна, поскольку процессы не являются независимыми: каждый из них и читает, и записывает переменную т. В частности, допустим, что все процессы выполняются с одинаковой скоростью, и, следовательно, каждый из них сравнивает свой элемент массива а [ i ] с переменной m в одно и то же время.
Все процессы определят, что неравенство выполняется (поскольку все элементы массива а больше начального значения переменной т, равного нулю). Следовательно, все процессы попытаются обновить значение переменной т. Аппаратное обеспечение памяти будет выполнять обновление в порядке некоторой очереди, поскольку запись элемента в память— неделимая операция. Окончательным значением переменной m будет значение а [ i ], присвоенное ей последним процессом.
В программе, показанной выше, чтение и запись переменной m являются отдельными операциями. Для работы с таким уровнем параллельности можно использовать синхронизацию для совмещения отдельных действий в одной неделимой операции. Это делает следующая программа.
int m = 0; со [i = 0 to n-1] (if <a[i] > m) m = a [ i ] ;}
Угловые скобки в этом фрагменте кода указывают, что каждый оператор i f выполняется как неделимая операция, т.е. проверяет текущее значение m и в соответствии с условием обновляет его в одном, неделимом действии. (Подробно нотация с угловыми скобками будет описана в следующем разделе.)
К сожалению, последняя программа — это почти то же самое, что и последовательная. В последовательной программе элементы массива а проверяются в установленном порядке — от а[0] до а[п-1]. В последней же программе элементы массива а проверяются в произвольном порядке, поскольку в произвольном порядке выполняются процессы. Но из-за синхронизации проверки все еще выполняются по одной.
Основные задачи в данном приложении — обеспечить, чтобы обновления переменной m были неделимыми операциями, а значение m было действительно максимальным. Допустим, что сравнения выполняются параллельно, но обновления производятся по одному, как в следующей программе.
int m = 0 ; со [i = 0 to n-1] if (a[i] > m) (m = a[i];>
56 Часть 1. Программирование с разделяемыми переменными
Правильна ли эта версия? Нет, поскольку эта программа в действительности является тем же, что и первая параллельная программа: каждый процесс может сравнить свое значение элемента массива а с переменной m и затем обновить значение переменной т.
И хотя здесь указано, что обновление m является неделимой операцией, фактически это осуществляется аппаратным обеспечением памяти.
Итак, как же лучше всего решить эту задачу? Выход состоит в сочетании последних двух программ. Можно безопасно выполнять параллельные сравнения, поскольку это действия, которые только читают переменные. Но необходимо обеспечить, чтобы при завершении программы значение m действительно было максимальным. Это достигается в следующей программе.
int m = 0;
со [i = 0 to n-1]
if (a[i] > m) #проверка значения m
{if (a[i] > m) # перепроверка значения m m = a [ i ] ; >
Идея состоит в том, чтобы сначала проверить неравенство, а затем, если оно выполняется, провести еще одну проверку перед обновлением значения переменной. Она может показаться лишней, но это не так. Например, если некоторый процесс обновил значение т, то часть других процессов определит, что их значение а [ i ] меньше нового значения т, и не будет выполнять тело оператора if. После дальнейших обновлений еще меньше процессов определят, что условие в первой проверке истинно. Следовательно, если проверки сами по себе вы-, полняются в некотором случайном порядке, а не параллельно, это повышает вероятность того, что процессам не нужно будет производить вторую проверку.
Эта частная задача — не из тех, которые выгодно решать с помощью параллельной программы, если только она не выполняется на SIMD-машине, построенной специально для эффективного выполнения мелкомодульных программ. Однако в данном разделе есть три ключевых момента. Во-первых, синхронизация необходима для получения правильных результатов, если процессы и считывают, и записывают разделяемые переменные. Во-вторых, неделимость действий задана угловыми скобками; это рассмотрено подробно в следующем разделе, а затем показано, как реализовать неделимые действия (фактически это пример критических секций). В-третьих, описанный здесь метод двойной проверки перед обновлением разделяемой переменной весьма полезен, как мы увидим в дальнейших примерах, особенно когда существует вероятность, что первая проверка дает ложный результат, и, следовательно, вторая проверка не нужна.
