пись (хотя бы одно из двух) предназначены для CRCW-машины. Мы вернёмся к сравнению различных моделей в в разделе 30.2.

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

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

•приоритеты (priority): сохраняется значение, поступившее от процессора с наименьшим номером;

•комбинация (combinational): сохраняется некоторая комбинация (например, сумма или максимум) поступивших на запись значений.

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

30.0.3. Синхронизация

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

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

30.0.4. План главы

В разделе 30.1 рассматривается метод переходов по указателям и его использование для обработки префиксов списка, а также ана-

логичные методы для работы с деревьями. Раздел 30.2 посвящен сравнению CRCW- и EREW-машин и преимуществам одновременного доступа к памяти.

В разделе 30.3 доказывается теорема Брента о моделировании схем из функциональных элементов в модели PRAM. Кроме этого, в этом разделе рассматривается понятие эффективности по затратам и даются условия, при которых число процессоров может быть уменьшено без потери эффективности. В разделе 30.4 вновь рассматривается задача обработки префиксов списка и описывается эффективный по затратам вероятностный алгоритм для этой задачи. Наконец, раздел 30.5 посвящен задаче о нарушении симметрии. Приводится детерминированный алгоритм, который позволяет решить эту задачу за время, существенно меньшее логарифмического.

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

30.1. Переходы по указателям

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

30.1.1. Номер в списке

Список в PRAM-машине хранится обычным образом. При этом мы будем считать, что за каждый элемент списка отвечает свой процессор, то есть что г-ый процессор отвечает за элемент списка, хранящийся в г-ой ячейке памяти. (Порядковый номер этого элемента в списке может быть любым.) На рис. 30.2(a) показан пример списка из объектов (3,4,6,0,1,5). Поскольку для каждого элемента имеется собственный процессор, все элементы списка можно обрабатывать параллельно.

Пусть дан односторонне связанный список L из га элементов, и

Рис. 30.2 30.2. Использование метода переходов по указателям для вычисления расстояний до конца списка за время O(lgn). (а). Начальное состояние: все значения d равны 1. (b)-(d). Состояния списка после каждого выполнения цикла while в алгоритме List-Rank. В конце значение d совпадает с расстоянием до конца списка.

для каждого его элемента требуется найти расстояние до конца списка. Более формально, если next[i] - указатель объекта г на следующий объект, то расстояние до конца списка задаётся индуктивно следующим образом:

ГОесли next[i] = nil

L i у d[next[i]] + 1 если next[i] ф nil

Эта задача называется задачей о номере в списке (list-ranking problem).

Тривиальное решение состоит в вычислении расстояний последовательно, начиная с конца списка. При этом время работы составляет в (га), поскольку k-ъ с конца объект может быть обработан лишь после к - 1 следующих за ним объектов. Такое решение по сути является последовательным, а не параллельным - в каждый момент активен только один процессор. Рассмотрим теперь алгоритм с временем работы в (lgra).

List-Rank(L)

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

2do if next[i] = nil

3then d[i] f- 0

4else d[i] <- 1

5while существует объект i, для которого next[i] ф nil

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

7do if next[i] ф nil

8then d[i] <- d[i] + с?[пеж£[г]]

9next[i] <- next[next[i]]

На рис. 30.2 показаны состояния списка перед каждым повторением цикла while в строках 5-9. Состояние списка после заполнения полей d[i] (строки 1-4) показано на рис. 30.2(a). На первом шаге у всех объектов, кроме последнего, указатели не равны nil, поэтому строки 8-9 выполняются для первых пяти процессоров. Получается состояние списка, показанное на рис. 30-2(Ь). На следующем шаге строки 8-9 выполняются только для первых четырёх процессоров (у двух последних объектов указатели уже равны nil). Результат показан на рис. 30-2(с). При третьем (и последнем) выполнении цикла работают только два первых процессора. Конечный результат показан на рис. 30-2(d).

Идея композиции переходов по указателям (pointer jumping) реализована в строке 9, где производится операция next[i] <- next[next[i]]. Заметьте, что эти действия нарушают структуру