двух га-разрядных чисел за время O(lgra) с элементами, имеющими фиксированное число входов, указал Офман [152]

Идею использовать сложение с запоминанием переносов для умножения высказали Эстрин, Гилхрист и Померен [64]. Атрубин [13] построил бесконечный линейно-матричный умножитель для чисел любой длины (га-й бит произведения выдаётся сразу после поступления га-ых битов сомножителей). Дерево Уоллеса описал Уоллес [197] (независимо его идея была открыта Офманом [152]).

Алгоритмы деления восходят к И. Ньютону (придумавшему свой метод итераций около 1665 года). В задаче 29.1 строится схема для деления, имеющая глубину глубины 0(lg2ra). В действительности можно построить схему глубины всего O(lgra) (Бим, Кук и Хувер [19]).

Алгоритмы параллельных вычислений

С появлением многопроцессорных компьютеров возникла необходимость в разработке параллельных алгоритмов (parallel algorithms), которые используют возможность одновременного выполнения нескольких действий. Усилиями многих исследователей такие алгоритмы разработаны для множества задач, в том числе и для задач, рассмотренных в предыдущих главах. В этой главе мы рассмотрим несколько простых параллельных алгоритмов в качестве иллюстрации основных идей.

Сортирующие сети и схемы из функциональных элементов (главы 28, 29) представляют собой модель параллельных вычислений, но недостаточно общую. В этой главе в качестве модели используются «параллельные машины с произвольным доступом». Они удобны для описания алгоритмов работы со структурами данных (массивами, деревьями, списками и т. д.). Эта модель достаточно близка к практике в том смысле, что если один алгоритм оказывается эффективнее другого для этой модели, то, как правило, он будет эффективнее и при практической реализации.

30.0.1. Параллельная машина с произвольным доступом (PRAM)

Устройство параллельной машины с произвольным доступом (parallel random-access machine, PRAM) показано на рис. 30.1. Процессоры Ро,... , Pp-i используют общую память (shared memory). Все р процессоров могут одновременно записывать информацию в память или читать из памяти, а также параллельно выполнять арифметические и логические операции.

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

Рис. 30.1 30.1. Устройство PRAM-машины. Процессоры Po,Pi,... , Pp-i используют общую память. Каждый процессор может получить доступ к любой ячейке памяти за единичное время.

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

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

30.0.2. Параллельный и исключительный доступ к памяти

Существует несколько подходов к использованию общей памяти. В алгоритмах с одновременным чтением (concurrent-read algorithms) несколько процессоров могут одновременно считывать информацию из одной ячейки. В алгоритмах с исключающим чтением (exclusive-read algorithms) одновременное чтение (из одной ячейки памяти) запрещено. Подобным же образом алгоритмы делятся на алгоритмы с одновременной записью (concurrent-write algorithms) и алгоритмы с исключающей записью (exclusive-write algorithms). Таким образом, возможно четыре вида общей памяти, для которых традиционно употребляются следующие названия:

•EREW (exclusive-read exclusive-write): исключающее чтение и исключающая запись,

•CREW: одновременное чтение и исключающая запись,

•ERCW: исключающее чтение и одновременная запись,

•CRCW: одновременное чтение и одновременная запись.

Далее мы будем говорить, например, о EREW-машине или CREW-алгоритме, имея в виду соответствующий тип общей памяти.

Наиболее употребительны модели EREW и CRCW. Ясно, что все алгоритмы, которые могут выполняться на EREW-машине, могут выполняться и на CRCW-машине, но не наоборот. Аппаратная поддержка модели EREW проще и быстрее (из-за отсутствия конфликтов при записи и чтении). Реализация модели CRCW более сложна, если мы хотим обеспечить хотя бы примерно одинаковое время доступа к памяти для всех вариантов доступа, но с точки зрения программиста эта модель значительно проще и удобнее.

Из двух оставшихся типов (CREW, ERCW) более популярна модель CREW, хотя на практике реализовать одновременную запись не сложнее, чем одновременное чтение. В этой главе считается, что все алгоритмы, использующие одновременное чтение или за-