число удаляемых? Для этого нужно, чтобы на этапе 2 он был помечен (вероятность 1/2) и чтобы чтобы объект next[i] не был помечен (это независимое событие, имеющее вероятность не меньше 1/2 - лишь один процессор может пометить next[i], и с вероятностью 1/2 он бездействует). Таким образом, вероятность удаления объекта г нее меньше 1/4.

Таким образом, ситуацию можно описать так. Имеется га/lgra групп по lg га элементов в каждой (для простоты мы будем считать, что элементы делятся на группы без остатка). На каждом шаге число элементов в группе может уменьшится на 1 или остаться прежним, при этом вероятность уменьшения не менее 1/4. Уменьшения в разных группах на одном шаге могут не быть независимыми, но уменьшения на разных шагах в одной группе независимы.

Нам надо доказать, что математическое ожидание времени полного исчезновения всех групп есть О (lg га). Анализа для одной группы тут недостаточно, поскольку даже один долго работающий процессор уже увеличивает общее время работы.

Мы покажем, что с вероятностью не менее 1 - 1/га список станет пустым через время с lgra для некоторой константы с. Полное доказательство оценки в (lgra) для математического ожидания времени работы оставляется читателю (упр. 30.4-4 и 30.4-5).

Поскольку нас интересует верхняя оценка времени, когда список станет пустым, будем считать, что вероятность уменьшения данной группы на каждом шаге в точности равна 1/4 (хотя на самом деле она может быть больше); формальное обоснование законности такого допущения даётся в упр. 6.4-8 и 6.4-9.

Рассмотрим ситуацию для одной фиксированной группы. Взяв какое-то значение с, посмотрим на вероятность того, что среди с lgra независимых испытаний с вероятностью успеха 1/4 в каждом будет меньше lg га успехов. (Это и будет вероятностью того, что группа останется непустой после с lgra испытаний.) Обозначив число успехов через X, оценим вероятность события {X < lgra} с помощью следствия 6.3:

Р{А < lgra} <С СХптУЫп-Ып ()Sn(3/4)(c-1)1 = (ec(3/4)c-1)lgn (1/4)

(последнее неравенство верно при с 20; второе неравенство следует из (6.9)). Таким образом, вероятность того, что через с lgra шагов не все объекты данного процессора исключены, не превышает 1/га2.

Всего имеется га/lgra процессоров, поэтому вероятность «неудачи» (остаются неудалённые) одного процессора надо ещё умножить на га/lgra, (неравенство Буля, 6.22) получается не больше

га 1 1

]---2 "

lg га пг га

Поэтому с вероятностью не менее 1 - 1/га алгоритм закончит работу за время 0(lg га).

Константа 20 не отражает реального быстродействия алгоритма - на самом деле наша оценки довольно грубые, и среднее время значительно меньше.

30.4.4. Упражнения

30.4-1. Нарисуйте пример, показывающий, почему нельзя исключать из списка два соседних объекта.

30.4-2*. Вероятностный алгоритм можно слегка изменить так, чтобы время работы в худшем случае составляло О (га). Как? Докажите, что математическое ожидание времени работы модифицированного алгоритма равно О (lgra).

30.4-3*. Измените вероятностный алгоритм так, чтобы он использовал 0(п/р) памяти (в расчёте на один процессор) независимо от глубины рекурсии.

30.4-4*. Докажите, что для любого к 1 найдётся такая константа с, что время работы алгоритма меньше с lgra с вероятностью 1 - 1/пк или больше. Как зависит константа с от к?

30.4-5*. Докажите, используя предыдущее упражнение, что математическое ожидание времени работы вероятностного алгоритма есть 0(lgга).

30.5. Нарушение симметрии (детерминированный алгоритм)

Рассмотрим ситуацию, когда два процессора одновременно хотят получить доступ к объекту. При отсутствии механизма одновременного доступа к памяти один из процессоров должен получить доступ первым - но какой? Задача выбора ровно одного из двух процессоров является частным случаем задачи о нарушении симметрии (symmetry breaking). Именно с такой задачей столкнулись Чичиков и Манилов, уступая друг другу дорогу. Подобные задачи постоянно возникают при реализации параллельных алгоритмов.

Для решения такой задачи можно просто бросать монетку (использовать случайные числа). Например, в случае двух процессоров каждый из них бросает монетку, и доступ получает тот, у кого орёл (если два орла или две решки - бросают ещё раз). При этом симметрия будет нарушена за время 0(1) (имеется в виду математическое ожидание, см. упр. 30.5-1).

Использование случайности часто оказывается полезным - мы видели, что вероятностном алгоритме обработки префиксов (раздел 30.4) использование случайности позволяет выбрать достаточ-

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

В этом разделе рассматривается детерминированный метод нарушения симметрии. Он основан не на бросании монеты, а на использовании номеров процессоров (или адресов в памяти). Например, в случае двух процессоров можно предоставить доступ процессору с меньшим номером. При этом задача решается за постоянное время.

Мы используем ту же идею для решения более сложной задачи: как выделить (достаточно большую) часть объектов списка, если нельзя выделять два соседних объекта. Для этой задачи будет построен параллельный алгоритм (в EREW-модели), время работы которого составляет 0(lg* п), если номера процессоров берутся из промежутка 1..п. Поскольку lg* п 5 при п 265536, на практике время работы этого алгоритма можно считать постоянным (см. стр. 00).

Алгоритм состоит из двух частей. Сначала за время 0(lg* п) мы находим «6-раскраску» списка. Затем (за время 0(1)) мы получаем из неё «максимальное независимое подмножество»списка; оно содержит не менее трети объектов списка и не содержит соседних объектов.

30.5.1. Раскраски и максимальные независимые множества

Раскраской (coloring) неориентированного графа G = (V, Е) называется отображение С : V -> N, для которого С (и) ф С (у) при (и, v) G Е. Если называть С [у) цветом вершины v, то можно сказать, что концы любого ребра должны иметь разные цвета. Мы ищем 6-раскраску списка, то есть хотим поставить в соответствие каждой вершине некоторый цвет из множества {0,1,2,3,4,5}, причём так, что соседние в списке вершины имеют разные цвета.

Такая раскраска существует; более того, ясно, что достаточно двух цветов. В самом деле, можно покрасить все чётные вершины в один цвет, а все нечётные - в другой. Но находясь в середине списка, не так просто понять, чётная вершина или нечётная - для этого нужно отсчитать её номер от начала списка, что можно сделать за время O(lgra) (раздел 30.1). Разрешив больше цветов (как мы увидим, достаточно 6), раскраску можно построить быстрее - за время 0(lg*ra), при этом алгоритм остаётся детерминированным.

Множество V С V вершин графа G = (V, Е) назовём независимым множеством (independent set), если никакие две вершины из V не соединены ребром. Независимое множество V называется максимальным (maximal independent set, MIS), если при добавле-