списка, поскольку меняются поля указателей. Если необходимо сохранить список, необходимо сделать копии полей указателей и производить действия с копиями.

30.1.2.Корректность

Цикл в строках 5-9 имеет следующий инвариант: для любого объекта г либо next[i] указывает на объект, находящийся в списке на расстоянии d[i], либо next[i] = nil и d[i] есть расстояние до конца списка.

Заметьте, что для правильной работы алгоритма необходима синхронизация: чтение всех указателей next[next[i]] (в строке 9) должно произойти до записи их новых значений.

Теперь покажем, что программа List-Rank не использует одновременного обращения к памяти (и поэтому может выполняться на EREW-машине). Ясно, что в строках 2-7, а также при записи в строках 8 и 9 не происходит одновременного обращения к одной ячейке, так как за каждый элемент списка отвечает свой процессор. Кроме того, переход по указателям сохраняет следующий инвариант: для любых двух различных объектов t и j либо next[i] ф next[j], либо next[i] = next[j] = nil. Действительно, вначале это условие выполнено; оно сохраняется при исполнении строки 9. Поэтому при чтении в строке 9 не происходит одновременного обращения к одной ячейке.

В строке 8 не происходит одновременного чтения благодаря синхронизации: мы считаем, что сначала все процессоры читают d[i], и лишь затем с?[пеж£[г]]. В результате при г = next[j] содержимое d[i] сначала прочитывается г-м процессором, а затем j-m. При такой синхронизации алгоритм может работать на EREW-машине.

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

30.1.3.Анализ

Пусть список L содержит га элементов. Покажем, что время работы алгоритма составляет О (lgra). Поскольку инициализация и каждое выполнение цикла while занимают время 0(1), достаточно показать, что цикл выполняется lgra раз. Это следует из того, что при каждом выполнении цикла значения d[i] для тех элементов г, для которых next[i] ф nil, увеличиваются вдвое.

Мы предполагаем, что проверка условия в строке 5 занимает время 0(1) (при использовании управляющей сети). В упражнении 30.1-8 предлагается реализовать эту проверку без такой сети, сохранив время работы программы О (lgra).

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

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

Говорят, что алгоритм А не менее эффективен по затратам, чем алгоритм В (A is work-efficient with respect to В), если общие затраты А превышают общие затраты В не более чем в константу раз. Алгоритм А называется эффективным по затратам (work-efficient), если он не менее эффективен, чем любой однопроцессорный алгоритм. (В этом случае он не менее эффективен, чем любой алгоритм, поскольку многопроцессорный алгоритм можно моделировать на одном процессоре, последовательно моделируя работу каждого процессора.) Рассмотренный выше алгоритм отыскания номера в списке не является эффективным по затратам, поскольку существует алгоритм с затратами О (га). Эффективный по затратам вероятностный алгоритм для этой задачи строится в разделе 30.4.

30.1.4. Параллельная обработка префиксов списка

Метод переходов по указателям применяется не только для определения порядковых номеров элементов списка. Как показано в разделе 29.2.2, обработка префиксов позволяет быстро складывать числа. Здесь будет показано, как использовать метод переходов по указателям для обработки префиксов. Алгоритм обрабатывает префиксы га-элементного списка на EREW-машине за время О (lgra).

Пусть <g> - ассоциативная бинарная операция. Задача обработки префиксов (prefix computation) состоит в следующем: по данной последовательности (х\, х2, , хп) построить последовательность (У1,У2, , Уп), Для которой г/1 = xt и

Ук = Ук-i <S> хк = xt <g) х2 <8> ... <8> хк

для к = 2, 3,... , га. Другими словами, ук есть «©-произведение» первых к элементов последовательности.

Мы будем считать, что элементы хг, , хп, подлежащие обработке, связаны в односторонний список. (Аналогичная задача для

массива рассматривается в упражнении 30-1.2). Заметим для начала, что задачу о номере в списке можно рассматривать как частный случай задачи о параллельной обработке префиксов. Действительно, пусть каждый элемент списка равен 1, а операция <g> - обычное сложение. Тогда ук = к, то есть мы вычислили расстояние до начала списка. Поэтому обработку префиксов можно использовать для решения задачи о номере в списке - нужно лишь сначала обратить список (что можно сделать за время 0(1)).

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

= Xi <g) Xi+1 <g) ... <g) Xj

при 1 i j п. В частности, [к, к] = хк и

[i,k] = [i,j]®\j + l,k]

при l.i.j<k.n. Наша цель - вычислить ук = [1, к] для всех к = 1,... , п.

В программе через x[i] обозначается значение объекта г. (Напоминаем, г есть адрес в памяти, а также номер ответственного за эту ячейку процессора, и никак не связан с к - порядковым номером в списке!) Алгоритм вычисляет y[i] = ук = [1,к], где x[i] = хк есть к-ъ с начала элемент списка.

List-Prefix(L)

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

2do y[i] <- x[i]

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

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

5do if next[i] ф nil

6then у[пеж£[г]] <- y[i] <8> у[гаеж[г]]

7next[i] <- next[next[i]]

Видно, что алгоритм похож на алгоритм определения порядковых номеров элементов. Отличаются лишь инициализация и изменение значений у (в предыдущем алгоритме d). В алгоритме List-Rank процессор г изменяет значение y[i], соответствующее своему объекту, тогда как в алгоритме List-Prefix г-й процессор изменяет «чужое» значение г/[пеж£[г]]. (Если бы мы обрабатывали не префиксы, а суффиксы, то этой разницы бы не было.) Как и алгоритм List-Rank, алгоритм List-Prefix поддерживает следующий инвариант: для любых двух различных объектов г и j либо next[i] ф next[j], либо next[i] = next[j] = nil. Поэтому не происходит одновременного обращения к памяти, так что алгоритм можно реализовать на EREW-машине.

На рис. 30.3 показано состояние списка перед каждым выполнением цикла while. Цикл имеет следующий инвариант: после £-го повторения цикла указатели охватывают 2* звеньев списка (или