30.2. CRCW- и EREW-алгоритмы

Одновременный доступ к памяти в параллельных компьютерах имеет свои плюсы и минусы. Недостатком является сложность аппаратной поддержки такого доступа. Кроме того, возможности одновременного доступа используются не так часто. С другой стороны, в некоторых случаях без этих возможностей трудно обойтись. На практике часто выбирается один из промежуточных вариантов.

В этом разделе рассматриваются преимущества одновременного доступа. Существуют задачи, для которых наилучший CRCW-алгоритм работает быстрее наилучшего EREW-алгоритма. Такова, например, задача отыскания корней деревьев в графе, являющемся лесом, а также задача поиска максимального элемента в массиве. Эти задачи рассмотрены ниже.

30.2.1. Польза параллельного чтения

Пусть дано несколько двоичных деревьев, заданных следующим образом: каждая вершина г имеет указатель parent[i] на родителя (если вершина является корнем, то parent[i] = nil). Требуется для каждой вершины г найти корень гоо£[г] дерева, которому она принадлежит. С каждой вершиной мы связываем один процессор.

Find-Roots(F)

1for (для) каждого процессора г

2do if parent[i] = nil

3then гоо£[г] <- г

4while существует узел г, для которого parent[i] ф nil

5do for (для) каждого процессора г

6do if parent[i] ф nil

7then гоо£[г] <- root[parent[i]]

8parent[i] <- parent[parent[i]]

Работа алгоритма показана на рис. 30.5. После инициализации (строки 1-3) корни известны только для корневых вершин (рис. 30.5 (а)). В цикле while (строки 4-8) происходят переходы по указателям и заполняются поля root у вершин следующих (по глубине) уровней. На рис. 30.5 (b)-(d) показаны состояния деревьев после первого, второго и третьего выполнений цикла. Цикл имеет следующий инвариант: после t повторений цикла либо parent[i] = nil и гоо£[г] содержит правильный указатель на корень, либо parent[i] есть предок на расстоянии 2*.

Алгоритм Find-Roots можно реализовать на CREW-машине; время работы составляет О (lg cf), где d - максимальная из глубин деревьев. Действительно, все записи являются исключающими - каждый процессор производит запись только в поля своей вер-

Рис. 30.5 30.5. CREW-алгоритм нахождения корней деревьев. Номера вершин расположены рядом с ними. Внутри вершин показаны значения root. Стрелки обозначают ссылки parent, (a)-(d) Состояние дерева перед каждым выполнением цикла while (строки 4-8). Заметим, что максимальная длина пути по стрелкам на каждом шаге уменьшается вдвое.

шины. Однако чтение в строках 7 и 8 является одновременным, поскольку одна вершина может быть предком сразу для нескольких других. Например, на рис. 30.5 (Ь) при втором выполнении цикла значения гоо£[4] и parent[4] читаются процессорами 18, 2 и 7 одновременно.

Время работы составляет 0(lg d) по тем же причинам, что и для алгоритма List-Rank.

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

Если максимальная высота деревьев мала, то алгоритм FlND-Roots работает асимптотически быстрее, чем любой EREW-алгоритм. Например, при высоте дерева d = O(lgra) (пусть, скажем, имеется всего одно полное дерево), CREW-алгоритм работает за время О (lg lg тг), а любой EREW-алгоритм требует времени O(lgn).

Другой (более простой) пример выигрыша от параллельного чтения см. в упр. 30.2-1.

30.2.2. Польза параллельной записи

Рассмотрим задачу о нахождении максимального элемента в массиве из п действительных чисел. Можно доказать, что для этой задачи наилучший EREW-алгоритм требует времени Q(lgn) и что одновременное чтение не позволяет уменьшить время работы. Однако существует CRCW-алгоритм со временем работы 0(1). Напомним, что мы рассматриваем CRCW-модель, в которой все процессоры, производящие запись в данную ячейку, должны записывать туда одно и то же.

Пусть А[0 .. .п - 1] - входной массив. Наш CRCW-алгоритм использует п2 процессоров. Каждый процессор сравнивает какие-то два элемента A[i] и A[j], где 0 i,j п - 1, и нумеруется парой индексов

Fast-Max(A)

1п <- length[A]

2for г <- 0 to п - 1

Рис. 30.6 30.6. Отыскание максимума в массиве за время O(l) с помощью алгоритма Fast-Max. Для каждой (упорядоченной) парыэлементов массива А = (5, 6, 9, 2, 9} в таблице показан результат сравнения А[г] < A[j] (Т означает true, F - false). Если в строке есть хотя бы одна буква Т, то соответствующий элемент т равен false, иначе - true. Элементы массива, для которых в столбце т стоит значение true, являются максимальными (и записываются в ячейку max).

10 return max

В строке 1 определяется длина массива А (каким-то из процессоров). В строках 2-3 каждым элементом массива т занимается какой-то один процессор (их у нас достаточно - га2) и помещает туда значение TRUE. (Будущий смысл массива т таков: m[i] истинно, когда A[i] - максимальный элемент в массиве).

Дальнейшая работа алгоритма показана на рис. 30.6. В строках 4-6 происходит сравнение всех возможных пар A[i] и A[j]. Если A[i] < A[j], то A[i] не может быть максимальным элементом, поэтому мы записываем в га [г] значение FALSE (строка 6). Несколько различных процессоров могут одновременно производить запись в ячейку га [г], но все они записывают одно и то же значение - FALSE.

Таким образом, после выполнения строк 4-6 га [г] истинно для тех и только тех индексов г, для которых А [г] - максимальный элемент. В строках 7-9 максимальное значение помещается в переменную max, которая является выходным значением (строка 10). К переменной max могут обращаться сразу несколько процессоров, но все они присваивают ей одно и то же значение, как и требуется в модели одновременной записи общего значения.

Поскольку выполнение каждого из циклов занимает время 0(1) (все процессоры работают одновременно), общее время работы алгоритма составляет 0(1). Алгоритм не является эффективным по затратам: общие затраты составляют га2 -0(1) = О (га2), а простейший однопроцессорный алгоритм работает за время в (га). Более эффективный алгоритм рассматривается в упражнении 30.2-6.

В сущности, алгоритм поиска максимума основан на возможности вычислить логическое И от га аргументов за время 0(1) при наличии га процессоров в модели с одновременной записью общего значения (и в других, более мощных CRCW-моделях). Фактически