Определенные задачи, подобно обработке изображений низкого уровня, легко поддаются распараллеливанию, поскольку они требуют, чтобы выполнялось большое число независимых вычислений. Кроме того, определенные аспекты компьютерного проектирования естественно ведут к вопросу, какие задачи могут быть распараллелены. Рассмотрим пример: один из первых параллельных алгоритмов, который разрабатывался и применялся. Он был разработан Левиалди, чтобы решить проблему компьютерного зрения - распознавание четких объектов в поле зрения. Хотя этот алгоритм имеет некоторые приложения, мы представляем это здесь только, чтобы показать характер многих параллельных алгоритмов.

Пусть нам дан двумерный массив, данные в котором – все 0 или 1. Массив представляет пиксели черного и белого цвета и 1 означает черный пиксель. В одном из исходных приложений, массив пикселей представлял отцифрованные образы красных кровяных телец. Алгоритм решает следующую проблему: как мы эффективно различаем связанные группы черных пикселей?

Заметим, что это более тонкая проблема, чем просто счет количества темных пикселей. Этот параллельный алгоритм для обработки массива, которая уменьшает объекты в образе на каждом шаге:

Предположим, обозначаeт (i,j)-ый пиксель в данном массиве в течение шага алгоритма. (i,j)-ый элемент массива на следующем шаге вычисляется как

,

где h - функция, определяемая следующим образом:

Этот алгоритм производит сжатие связанных групп темных пикселей, пока они, наконец, не будут содержать только единственный пиксель. В этот момент вызывается алгоритм для удаления изолированных пикселей и увеличения счетчика. Мы предполагаем, что каждый элемент массива (или пиксель) имеет процессор, обозначаемый и связанный с ним, и что эти процессоры могут общаться со своими соседями. Они могут быть очень простыми процессорами - они могут иметь очень ограниченную память и выполнять простые вычисления - по существу вычисления, содержащиеся в уравнении для вычисления элементов массива на следующем шаге, и простые логические операции. Каждый процессор должен иметь возможность сообщаться со своими соседями в массиве. Этот алгоритм может выполняться в цикле, где каждый цикл должен включать:

• Обмен информацией с соседними процессорами; или

• Выполнение простых вычислений с данными, которые хранятся в локальной памяти процессора.

Более детально, алгоритм выглядит так:

C ← 0

for i ← 1 to n do

for всех процессоров do in parallel

получают значения

от своих соседей (они уже содержат значение )

if ( и все соседние элементы равны 0) then

C← C+1

Выполнить вычисление в уравнении (1)

end do in parallel

end for

В этом примере ось i горизонтальна (увеличение индекса слева направо), а ось j вертикальна. Предположим, что начальное изображение подобно изображенному на рисунке 1.5. Результат первой итерации алгоритма дан на рисунке 1.5а. На следующем шаге пиксель слева вверху удаляется, и счетчик увеличивается на единицу. Результаты второго и третьего шагов изображены на рисунках 1.5б,в. После достаточного количества шагов (фактически n шагов, где n - размер самой большой стороны прямоугольника) экран будет чист, и все связанные компоненты будут сосчитаны. Эта реализация – пример особенно простой формы параллельного алгоритма, называемого систолическим алгоритмом.

Рис. 1.5

в

а

б

Рассмотрим другой пример такого алгоритма:

Предположим у нас есть одномерный массив (с n элементами), компоненты которого процессорные элементы. Мы предполагаем, что эти процессорные элементы могут выполнять основные операции компьютера. В данном случае они должны иметь возможность хранить по крайней мере два числа и их сравнивать. Каждый элемент этого массива связан со своими двумя соседями линиями связи так, что они могут посылать числа соседям (рис. 1.6).

Рис. 1.6

Теперь предположим, что каждый процессор имеет число, хранимое в нем, и мы хотим отсортировать эти числа. Существует параллельный алгоритм для выполнения сортировки за n шагов. Заметим, что последовательная сортировка требует порядка шагов. На нечетно нумерованных шагах нечетно нумерованные процессоры сравнивают свои числа с числами следующих четных процессоров и обмениваются ими, если они не в нужной последовательности. На четных шагах четные процессоры выполняют аналогичную операцию с их нечетно нумерованными соседями. На рисунке 1.7 дан пример такого процесса.

Рис. 1.7

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

Для параллельного обобщения выделенной базовой операции сортировки рассмотрим ситуацию, когда количество процессоров совпадает с числом сортируемых значений (p=n). Тогда сравнение элементов и , располагаемых на процессорах и , можно организовать следующим образом:

• выполнить взаимообмен имеющихся на процессорах и значений (при этом исходные элементы на этих процессорах сохраняются);

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

Адаптируем рассмотренный алгоритм для случая p<n, когда количество процессоров меньше числа упорядочиваемых элементов. В этом случае каждый процессор будет содержать часть сортируемого набора данных (блок размера n/p). Эти блоки обычно упорядочиваются в самом начале сортировки на каждом процессоре с помощью какого-либо быстрого последовательного алгоритма. Далее, следуя по рассмотренной выше схеме, осуществляется взаимодействие пары процессоров и для совместного упорядочивания содержимого блоков и :

• выполняется взаимообмен блоками между процессорами и ;

• объединяются блоки и на каждом процессоре в один отсортированный блок двойного размера (при исходной упорядоченности блоков и процедура их объединения сводится к быстрой операции слияния упорядоченных наборов данных);

• полученный двойной блок разделяется на две равные части; одна из этих частей (например, с наименьшими значениями данных) сохраняется на процессоре , а другая часть – на процессоре .

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