Основы многопоточного и распределенного программирования

       

Синхронизация: поиск максимального элемента массива


Рассмотрим другую задачу, которая требует синхронизации процессов. Она состоит в по­иске максимального элемента массива а [п]. Предположим, что п положительно и все эле­менты массива — положительные целые числа.

Поиск максимального элемента в массиве а — это пример задачи накопления (сведения). В данном случае сохраняется (накапливается) максимальный из просмотренных элементов, или, иными словами, все значения сводятся к их максимуму. Пусть 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-машине, построенной специально для эффек­тивного выполнения мелкомодульных программ. Однако в данном разделе есть три ключевых момента. Во-первых, синхронизация необходима для получения правильных результатов, если процессы и считывают, и записывают разделяемые переменные. Во-вторых, неделимость дейст­вий задана угловыми скобками; это рассмотрено подробно в следующем разделе, а затем пока­зано, как реализовать неделимые действия (фактически это пример критических секций). В-третьих, описанный здесь метод двойной проверки перед обновлением разделяемой перемен­ной весьма полезен, как мы увидим в дальнейших примерах, особенно когда существует вероят­ность, что первая проверка дает ложный результат, и, следовательно, вторая проверка не нужна.


Содержание раздела