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

30.3-1. Докажите результат, аналогичный теореме Брента, для моделирования на CRCW-машине схем, содержащих элементы И и ИЛИ с любой входной степенью. (Указание: в качестве размера следует рассмотреть общее количество входов элементов).

30.3-2. Докажите, что существует EREW-алгоритм для параллельной обработки префиксов массива из га элементов, использующий О (га/ lgra) процессоров и имеющий время работы О (lgra). Почему этот алгоритм нельзя использовать для списков?

30.3-3. Постройте эффективный по затратам алгоритм для умножения матрицы размера га X га на вектор размера га со временем работы О (lgra). (Указание: Постройте сначала схему из функциональных элементов.)

30.3-4. Постройте CRCW-алгоритм для умножения двух матриц размера га X га, использующий га2 процессоров и не менее эффективный по затратам, чем стандартный алгоритм со временем работы 0(га3). Будет ли он EREW-алгоритмом?

30.3-5. В некоторых моделях параллельных вычислений процессоры могут отключаться на некоторых шагах, так что число активных процессоров уменьшается. При подсчёте затрат на каждом шаге учитываются только активные процессоры. Докажите, что CRCW-алгоритм в такой модели со временем работы t, затратами w и любым начальным числом процессоров может быть смоделирован на EREW-машине с р процессорами за время 0((w/p-\-t) lgp). (Основная сложность состоит в том, что заранее неизвестно, какие процессоры будут активны.)

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

В разделе 30.1.2 был рассмотрен EREW-алгоритм параллельной обработки префиксов для списка из га элементов за время О (lgra). Он использует га процессоров, поэтому затраты составляют ©(ralg га), что больше, чем затраты О (га) однопроцессорного алгоритма. Следовательно, алгоритм List-Prefix не является эффективным по затратам.

В этом разделе описывается вероятностный EREW-алгоритм параллельной обработки префиксов, который использует ©(га/lgra) процессоров и в большинстве случаев (с большой вероятностью) работает за время О (lgra). Таким образом, этот (вероятностный) алгоритм можно считать эффективным по затратам. Конструкция теоремы 30.4 позволяет указать такой алгоритм для любого числа процессоров р = 0(п/ lg га).

splice out = удаление

splice in = возвращение удалённых

рекурсивный вызов процедуры Randomized-List-Prefix

Рис. 30.9 30.9. Рекурсивный вероятностный алгоритм обработки префиксов списка на примере списка из 9 объектов, (а) Чёрные объекты намечены для удаления. (Среди них нет соседних.) (Ь) Значение каждого удаляемого объекта соединяется со значением следующего; алгоритм рекурсивно вызывается на уменьшенном списке, (c)-(d) В результате уцелевшие элементы получают правильные значения, а удалённые объекты вычисляют свои префиксы с помощью предыдущих.

splice out удаление splice in возвращение stage 1 уровень 1 (bottom) (внутренний) (top) (внешний)

Рис. 30.10 30.10. Уровни рекурсии для алгоритма Randomized-List-Prefix. Вначале список содержит 9 объектов. Рекурсивные вызовы осуществляются до тех пор, пока список не станет пустым.

30.4.1. Рекурсивная параллельная обработка префиксов

Алгоритм Randomized-List-Prefix использует для га-элементного списка р = 0(ra/lgra) процессоров, так что каждый процессор отвечает за п/р = в (lgra) элементов. Распределение объектов по процессорам происходит произвольным образом (не обязательно подряд) в начале работы алгоритма и более не меняется. Для удобства будем считать, что список является двунаправленным, поскольку такой список можно изготовить из однонаправленного за время 0(1).

Идея алгоритма состоит в том, чтобы исключить из списка некоторые объекты (присоединив их к следующим за ними), произвести обработку префиксов для получившегося списка, а затем обработать пропущенные префиксы, учтя исключённые элементы. Один уровень рекурсии показан на рис. 30.9, а весь процесс - на рис. 30.10.

При выборе исключаемых элементов мы будем соблюдать такие правила::

1.Нельзя одновременно исключать два элемента, за которые отвечает один и тот же процессор.

2.Нельзя исключать два соседних в списке объекта.

Перед тем как описывать механизм выбора исключаемых элементов, рассмотрим подробнее сам процесс исключения. Пусть решено исключить /г-й объект. Тогда (/г + 1)-й объект запоминает значение [к, /г+1] = [к, к] <g> [к + 1, к + 1] (после чего /г-й объект удаляется). Если /г-й объект является последним, то он просто удаляется из списка.

После удаления процедура Randomized-List-Prefix вызывает саму себя на уменьшенном списке, если он ещё не пуст. После этого

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

Это сделать легко: если /г-й объект был исключён, то (к - 1)-й объект остался в списке и после рекурсивного вызова содержит значение [1, к - 1]. Остаётся лишь вычислить [1, к] = [1, к - 1]®[/г, к].

Условие 1 гарантирует, что для каждого исключённого объекта найдётся процессор, который будет производить вычисления. Условие 2 обеспечивает возможность обработать недостающий префикс, произведя всего одну операцию <g> (см. упр. 30-4.1). Итак, при выполнении требований 1 и 2 каждый шаг алгоритма требует времени 0(1).

30.4.2.Выбор удаляемых объектов

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

Укажем способ удовлетворить всем этим требованиям.

1.Каждый процессор случайно выбирает один из подведомственных ему объектов (из числа оставшихся в списке).

2.Каждый процессор бросает монету и с вероятностью 1/2 помечает выбранный им на предыдущем шаге объект (а с вероятностью 1/2 не делает ничего).

3.К удалению назначаются помеченные объекты, у которых следующий объект не помечен: объект г удаляется, если он помечен, a next[i] не помечен (никаким другим процессором).

Описанные действия выполняются за время 0(1) и не используют одновременный доступ к памяти.

Очевидно, что требование 1 выполнено (каждый процессор выбирает не более одного элемента). Требование 2 также выполнено, так как объекты г и next[i] не могут быть выбраны одновременно - если next[i] выбран, то он должен быть помечен - а тогда объект г не выбирается.

30.4.3.Анализ

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