же Бэтчер придумал битонический сортировщик глубины О (lgra), аналогичную описанному в разделе 28.3. Согласно Кнуту, правило нуля и единицы Кнут доказал Буриций (W.G. Bouricius, 1954) в контексте разрешающих деревьев.

Долгое время оставался открытым вопрос о существрвании сортирующей сети глубины О (lgra). В 1983 году на него был дан положительный ответ: Айтай, Комлос и Семереди [8] построили сортирующую сеть для га чисел глубины О (lgra) из О (га lgra) компараторов. К сожалению, константы в этой (З(га)-оценке (многие тысячи, если не больше) препятствуют практическому использованию этой сети.

Арифметические схемы

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

В этой главе рассматриваются схемы для арифметических действий. При последовательной реализации любое действие с двумя га-разрядными числами требует Г2(га) битовых операций (за меньшее время мы даже не прочтём входы). Уменьшения времени можно достичь при использовании схем, элементы которых работают параллельно. В этой главе мы построим такие схемы для сложения и умножения (вычитание аналогично сложению; по поводу деления см. задачу 29.1). Предполагается, что на входы поступают га-значные числа в двоичной системе.

Мы начнём в разделе 29.1 с определения и примеров схем из функциональных элементов; время работы будет определяться глубиной схемы. Нашим первым примером будет сумматор - базовый элемент для конструкций этой главы. Раздел 29.2 посвящен двум схемам для сложения: схеме каскадного сложения (время работы в (га)) и схеме сложения с предвычислением переносов, (время О (lgra)). Там же рассмотрена схема сложения с запоминанием переносов, позволяющая свести (за время 0(1)) сложение трёх чисел к сложению двух. В разделе 29.3 строятся две схемы для умножения: матричный умножитель (время работы 0(га)) и умножитель с помощью дерева Wallacea (время O(lgra)). Наконец, в разделе 29.4 рассказано о схемах с элементами задержки, которые позволяют многократно использовать одни и те же функциональные элементы (и тем самым уменьшить общее количество элементов в схеме).

29.1. Схемы из функциональных элементов

Как и сортирующие сети в главе 28, схемы из функциональных элементов являются параллельной моделью вычислений: несколько элементов схемы могут работать одновременно. В этом разделе мы дадим определение схемы из функциональных элементов и приведём примеры.

29.1.1. Функциональные элементы

Ариифметические схемы строятся из функциональных элементов, соединенных проводниками. Функциональный элемент (combinational element) имеет входы и выходы; его выходной сигнал является функцией входных. Если входные и выходные значения являются нулями и единицами, элемент называется логическим (boolean combinational element, logic gate); как обычно, 0 обозначает «ложь», а 1 - «истину» .

Четыре основных логических элемента, используемые в этой главе, показаны на рис. 29.1 : NOT (отрицание), AND (логическое И), OR (логическое ИЛИ) и X0R (исключающее ИЛИ); ещё два - NAND и NOR - используются в некоторых упражнениях). Элемент NOT имеет один вход ж, на который подается 0 или 1, и один выход z, значение на котором противоположно значению на входе. Остальные три элемента имеют по два входа (ж и у) и по одному выходу (z).

Рис. 29.1 29.1 Шесть основных логических элементов и соответствующие таблицы, (а) Элемент NOT. (b) Элемент AND. (с) Элемент OR. (d) Элемент XOR. (е) Элемент NAND (Not-AND), (е) Элемент NOR (Not-OR).

Работа элемента (как и любой схемы, составленной из них) может быть описана таблицей, которая указывает выходные значения для всех наборов значений на входах. Например, из таблицы для XOR видно, что входы ж = 0 и у = 1 дают на выходе z = 1. Для обозначения операции NOT традиционно используется символ ->, для AND - символ Л, для OR - символ V, а для XOR - символ ©. Например, 0 © 1 = 1.

Реальные функциональные элементы работают не мгновенно. Правильное значение на выходе появляется лишь через некоторое время после того, как значения на входах установятся. Это время называется задержкой (propagation delay). Мы предполагаем, что задержка одна и та же для всех элементов.