30.3. Теорема Брента и эффективность по затратам

Теорема Брента даёт способ эффективно моделировать схемы из функциональных элементов с помощью параллельных машин с произвольным доступом (PRAM). С её помощью многие результаты о сортирующих сетях (глава 28) и схемах из функциональных элементов (глава 29) переносятся на модель PRAM.

Рассмотрим схему из функциональных элементов (combinational circuit), которая состоит из функциональных элементов (combinational element), соединённых так, что не образуется циклов. В этом разделе предполагается, что функциональные элементы имеют любое количество входов, но ровно один выход (элемент с несколькими выходами можно заменить на несколько элементов с одним выходом). Число входов называется входной степенью (fan-in) элемента, а число входов, к которым подключён выход элемента - его выходной степенью (fan-out). Как правило, в этом разделе предполагается, что входные степени всех используемых элементов ограничены сверху. Выходные степени могут быть любыми.

Размером (size) схемы называется количество элементов в ней. Наибольшее число элементов на путях от входов схемы к выходу элемента называется глубиной (depth) этого элемента. Глубиной схемы называется наибольшая из глубин её элементов.

Теорема 30.2 (теорема Брента)

При моделировании работы схемы глубины d и размера п с ограниченными входными степенями элементов с помощью CREW-алгоритма, использующего р процессоров, достаточно времени 0(n/p + d).

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

Отведём в памяти место для входных значений схемы и для выходных значений всех функциональных элементов. Работу каждого элемента можно смоделировать с помощью одного процессора за время 0(1): процессор читает входные значения и вычисляет требуемую функцию, записывая результат на нужное место; поскольку входные степени всех элементов ограничены сверху, функцию, соответствующую любому элементу, можно вычислить за время 0(1).

Теперь требуется указать, в какой последовательности следует моделировать работу функциональных элементов с помощью р процессоров, чтобы обеспечить время работы 0(n/p-\- d). Проблема состоит в том, что выходное значение элемента можно вычислить лишь когда известны все его входные значения. (Большие выходные степени элементов не создают проблем, поскольку одновременное чтение разрешено).

Сначала мы можем моделировать лишь элементы глубины 1 (их

Рис. 30.8 30.8. Теорема Брента. Схему размера 15 и глубины 5 можно смоделировать на CREW-машине с двумя процессорами за 9 15/2 + 5 шагов. Элементы моделируются сверху вниз (в порядке возрастания глубины). Элементы, которые моделируются одновременно, объединены в группы (показаны серым цветом); для каждой группы указано, на каком шаге моделируются её элементы.

входные значения известны с самого начала). После этого можно моделировать элементы глубины 2, затем глубины 3 и т. д., до глубины d. Заметим, что если элементы глубины 1,... , г уже смоделированы, то элементы глубины г + 1 можно моделировать одновременно, так как они не используют выходные значения друг друга.

Элементы моделируются в порядке возрастания глубины, а на одной глубине - по р штук за раз. На рис. 30.8 показано, как происходит моделирование в примере с р = 2.

Если число элементов глубины г равно гаг-, на их моделирование уйдёт не более (гаг-/р) + 1 шагов (единица прибавляется, если последняя группа неполная). Всего получается не более

Ef- + 1) = - + rf ii v р р

шагов. Теорема доказана.

Теорема Брента справедлива и для моделирования схем на EREW-машине (при дополнительном условии, что выходные степени всех элементов также ограничены сверху):

Следствие 30.3. Любая схема глубины d и размера га, у которой элементы имеют ограниченные сверху входные и выходные степени, может быть смоделирована с помощью EREW-алгоритма, использующего р процессоров, со временем работы 0(n/p-\- d).

Доказательство. Моделирование производится так же, как и при доказательстве теоремы Брента. Единственная разница состоит в том, что выходное значение следует скопировать в 0(1) ячеек (их количество равно максимальной выходной степени элемента), чтобы процессоры впоследствии могли одновременно прочесть это значение, не используя одновременное чтение из одной ячейки.

Если выходные степени не ограничены сверху, копирование не укладывается в 0(1) шагов, так что требуется одновременное чтение. Если входные степени не ограничены сверху, то в некоторых случаях (когда функциональные элементы достаточно просты) схему всё же можно смоделировать на CRCW-машине с аналогичной оценкой времени работы (упр. 30.3-1).

В замечаниях к главе 28 указано, что существует сортирующая AKS-сеть, которая сортирует га чисел за время О (lgra), используя О (га lgra) компараторов. Поскольку входные степени компара-

торов ограничены сверху, для га процессоров существует EREW-алгоритм сортировки со временем работы О ((га lg га)/га + lg га) = О (lgra) (следствие 30.3). Этот результат был использован при доказательстве теоремы 30.1. К сожалению, множитель при логарифме столь велик, что такой алгоритм сортировки представляет лишь теоретический интерес. Однако существуют более практичные EREW-алгоритмы сортировки, например, параллельный алгоритм сортировки слиянием, принадлежащий Коулу [46].

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

Теорема 30.4. Пусть алгоритм А использует р процессоров и имеет время работы t. Тогда для любого р < р существует алгоритм А для той же задачи, использующий р процессоров и имеющий время работы 0(pt/p).

Доказательство. Занумеруем шаги алгоритма А числами 1,2,Алгоритм А будет моделировать каждый шаг за

время 0(\р/р]) (это делается как в теореме Брента). Тогда общее время работы алгоритма А будет равно Ю(\р/р]) = 0(t\p/p]) = 0(pt/p), так как р < р.

Общие затраты алгоритма А равны pt, а общие затраты алгоритма А равны 0(pt/p)p = O(pt), поэтому если алгоритм А эффективен по затратам, то А также эффективен по затратам.

Идея доказательства проста: процессор моделирует работу нескольких процессоров в режиме «разделения времени». Напротив, «распараллеливание» - разделение работы одного процессора между несколькими - дело трудное и для каждой конкретной задачи требует специального рассмотрения.

Следующее соображение позволяет иногда решить вопрос о существовании эффективного по затратам алгоритма с данным числом процессоров. Пусть доказано, что при любом количестве процессоров время работы алгоритма не может быть меньше t, а затраты наилучшего однопроцессорного алгоритма равны w (следовательно, затраты любого алгоритма не меньше w). Если в этой ситуации удастся найти эффективный по затратам алгоритм, использующий р = Q(w/t) процессоров, то тем самым будут найдены эффективные алгоритмы для любого количества процессоров, при котором они существуют. Действительно, для меньшего числа процессоров такой алгоритм получается из теоремы Брента, а эффективный алгоритм для существенно большего числа процессоров р не может существовать, поскольку время работы такого алгоритма не меньше t, а затраты не меньше pt = oj(pt) = uj(w).