п-1

т[г\ = д (А[г] > АЦ]) j=o

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

EREW-машина не обладает такими возможностями: любой EREW-алгоритм нахождения максимального элемента в массиве требует времени Q(lgn). Причина тут в том, что после каждого шага алгоритма число потенциально максимальных элементов уменьшается не более чем вдвое, поскольку для того, чтобы исключить элемент из числа «подозреваемых», нужно, чтобы он оказался меньше какого-то другого. Следовательно, каждое сравнение отбрасывает максимум один элемент, а число сравнений за один шаг не может быть больше половины числа оставшихся под подозрением элементов.

Интересно, что нижняя оценка Q(lgn) сохраняется, даже если разрешить одновременное чтение, то есть любой CREW-алгоритм также требует времени Q(lgn). Кук, Дворк и Райшук [50] показали, что время работы CREW-алгоритма не может быть меньше fi(lgn) даже при наличии неограниченного числа процессоров и неограниченной памяти. Те же оценки верны и для задачи вычисления логического И от га аргументов.

30.2.3. Моделирование CRCW-машины с помощью EREW-машины

Мы видели, что CRCW-алгоритмы иногда работают быстрее соответствующих EREW-алгоритмов (но не наоборот: любой EREW-алгоритм может выполняться CRCW-машиной без изменений). Итак, CRCW-машина обладает большими возможностями, но насколько они больше? Оказывается, что если число процессоров ограничено, то можно оценить сверху преимущество CRCW-машины перед EREW-машиной:

Теорема 30.1. Для любого CRCW-алгоритма (в модели одновременной записи общего значения), использующего р процессоров, существует EREW-алгоритм для той же задачи, время работы которого больше времени работы исходного алгоритма не более чем в O(lgp) раз.

Доказательство

для г = О,1,... , га - 1 вычисляется

Рис. 30.7 30.7. Моделирование одновременной записи на EREW-машине. (а) Шаг алгоритма в CRCW-модели с одновременной записью общего значения, когда процессоры осуществляют одновременную запись (процессоры Ро, Р2 и Ps). (Ь) Моделирование этого шага на EREW-машине. Вначале пара (ячейка, значение) записывается в массив А. Затем массив сортируется по первой компоненте, и записывается лишь первое из последовательности одинаковых значений.

использует факт, рассматриваемый в разделе 30.3: существует EREW-алгоритм сортировки р элементов, который использует р процессоров и работает за время O(lgp).

Достаточно указать EREW-алгоритм, который моделирует каждый шаг CRCW-алгоритма за время O(lgp). Поскольку число процессоров в обоих случаях одно и то же, нужно лишь смоделировать одновременный доступ к памяти. Мы рассмотрим вопрос об одновременной записи, оставив одновременное чтение читателю (упр. 30.2-7).

Для моделирования одновременной записи используется дополнительный массив А размера р. Рис. 30.7 демонстрирует основную идею. Если процессор Рг- (при г = 0,1,... , п - 1) направляет для записи в ячейку с номером /г- значение жг-, то в соответствующем EREW-алгоритме пара (/;, жг) записывается в ячейку А [г]. При этом записи оказываются исключающими. Затем массив А сортируется по первой координате за время O(lgp). После этого все данные, поступившие для записи в данную ячейку, оказываются рядом.

надписи на картинке:

общая память CRCW-машины

содержимое CRCW-памяти [вместо simulated CRCW global memory]

сортировка

Затем каждый процессор Рг- (при г = 1, 2,... , п - 1) сравнивает первые координаты своего и предшествующего элементов, то есть А [г] = (lj,Xj) и А [г - 1] = (1к,хк)- Если lj ф 1к или г = 0, то процессор Pi записывает значение Xj в ячейку lj, а в противном случае не делает ничего. Другими словами, записывается первое из подряд идущих значений, поступивших на запись в данную ячейку. Результат всего процесса моделирует одновременную запись, а общее время составляет O(lgp).

Можно смоделировать и другие варианты одновременной записи (упр. 30.2-9).

Какая же модель предпочтительней - EREW или CRCW? И если CRCW, то какой из вариантов одновременной записи использовать? Сторонники модели CRCW ссылаются на то, что программы для CRCW проще и быстрее. Противники говорят, что оборудование для обеспечения одновременного доступа к памяти замедляет этот доступ, поэтому на практике выигрыш во времени является

мнимым. На самом-то деле невозможно найти максимум в массиве за время 0(1), говорят они.

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

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

Упражнения

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

30.2-2. Укажите EREW-алгоритм для поиска корней со временем работы О (lgra), где га - общее количество узлов в деревьях.

30.2-3. Найдите CRCW-алгоритм, который, используя га процессоров, за время 0(1) вычисляет логическое ИЛИ от га аргументов.

30.2-4. Опишите эффективный CRCW-алгоритм, который умножает две булевы матрицы размера гахга, используя га3 процессоров.

30.2-5. Опишите EREW-алгоритм для умножения двух вещественных матриц размера га X га за время О (lgra), использующий га3 процессоров. Можете ли вы найти алгоритм для CRCW-машины с записью общего значения, работающий быстрее? А для какой-либо другой модели CRCW-машины?

30.2-6*. Докажите, что для любого е > 0 существует CRCW-алгоритм для поиска максимального элемента в массиве размера га со временем работы 0(1), использующий 0(га1+е) процессоров.

30.2-7*. Опишите алгоритм для CRCW-машины с приоритетами, позволяющий слить два отсортированных массива за время 0(1). Объясните, как с помощью этого алгоритма отсортировать массив за время О (lgra). Является ли полученный алгоритм сортировки эффективным по затратам?

30.2-8. Объясните, как смоделировать одновременное чтение CRCW-машины с р процессорами на EREW-машине за время O(lgp) (пропущенная часть доказательства теоремы 30-1).

30.2-9. Объясните, как с помощью EREW-машины смоделировать CRCW-машину с записью комбинации значений. Для р процессоров время работы должно увеличиться не более чем в O(lgp) раз. (Указание: используйте параллельное вычисление префиксов).