О глубине и площади клеточных схем Жуков Дмитрий Александрович

Содержание к диссертации

Введение

1 Типичные (п, 2)-преобразователи 20

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

1.2 Клеточные схемы 31

2 Оценки общего типа 36

2.1 Клеточные схемы для частичных функций 36

2.2 Моделирование СФЭ клеточными схемами 49

2.3 Нижние оценки площади в классе Т-схем 52

3 Клеточные схемы для арифметических операций 60

3.1 Префиксные клеточные схемы 60

3.2 Клеточные схемы для сложения 63

3.3 Клеточные схемы для вычитания 67

3.4 Клеточные схемы для умножения 67

3.5 Клеточные схемы для деления 69

Литература 71

• Клеточные схемы
• Моделирование СФЭ клеточными схемами
• Клеточные схемы для сложения
• Клеточные схемы для деления

Введение к работе

Результаты диссертации относятся к математической теории синтеза и сложности управляющих систем [35]. Предметом исследования являются схемы из клеточных элементов (СКЭ, клеточные схемы) [9, 30] и схемы из функциональных элементов (СФЭ) [12, 34]. В диссертации изучаются площадь и глубина клеточных схем для всюду определённых и частичных булевых функций, а также схем, реализующих основные арифметические операции.

Определения и обозначения

Сложность L(S) и глубина d(S) схемы из функциональных элементов S, как обычно, понимаются как число элементов в схеме и число элементов в самой длинной ориентированной цепи между её входами и выходами [12, 34]. Сведения о глубине и сложности арифметических схем из функциональных элементов можно найти, например, в [22, 32, 59].

-*xVy х

-X

У х

Формальное определение схем из клеточных элементов было дано в работе [9]. Затем клеточные схемы были рассмотрены в [1, 29, 30]. Клеточная схема имеет

вид прямоугольника на плоскости, составленного из клеточных элементов. Мы будем называть схему правильной, если все её входы и выходы расположены по краям. Везде далее клеточные схемы предполагаются правильными. Будем считать, что длина клеточной схемы измеряется по горизонтали, а ширина — по вертикали. Длину схемы S обозначим l(S), а ширину — h(S). Тогда площадь A(S) схемы S равна произведению l(S) х h(S).

Напомним основные определения [9]. Клеточный элемент имеет вид единичного квадрата. На его сторонах расположены входы

и выходы — не более одного на каждой стороне. Клеточный эле
мент называется функциональным, если он реализует нетождествен
ную функцию, и коммутационным., если он реализует тождествен
ные функции. Кроме функциональных и коммутационных элементов
имеется изолирующий клеточный элемент без входов и выходов. В
работах [1, 9, 29, 30] исследовались схемы, построенные из двоичных
клеточных элементов в базисе {&,V,^—} (рис. 1). Будем обозначать
этот базис B&_jV - . В последней главе будут также рассмотрены кле
точные схемы, реализующие функции Аг-значной логики. Использу
емые при их построении fc-ичные элементы изображены на рис. 2.
В верхнем ряду приведены изолирующий элемент и четыре функци
ональных элемента (реализующие константу с, одноместную функ
цию д Є Р* и двуместную функцию / Є Pfc). В нижнем ряду изобра
жены коммутационные элементы. Будем обозначать этот базис Б*.
При построении схемы допускаются повороты клеточных элементов
на углы, кратные |. Чтобы подчеркнуть, что в базис Б* входят эле
менты, реализующие функции /і,.. -, /_т, будем писать Ъд_r..j_TTl- -Ь^а_
зис Б&^у,^- і дополненный функциональными элементами со входами
на соседних сторонах (рис. 2, справа в верхнем ряду), реализующими
функции двух переменных /i,..., f_m из Р₂, обозначим B&,_v-,a /_m-

с h*

9(х)

-9{х)

Рту /О, у)

f{x,y) ±

^{х- / -/fa, у)}

У

х

х--*

*х

Рис. 2

Прямоугольник, составленный из клеточных элементов, будем называть клеточной схемой в том и только том случае, когда при замене клеточных функциональных элементов на соответствующие им обычные функциональные и при их соединении, определяемом коммутационными элементами, получается некоторая структура, удовлетворяющая обычному определению СФЭ. Так всякой клеточной

схеме S единственным с точностью до изоморфизма образом соответствует некоторая схема из функциональных элементов S^r. Схема S реализует тот же оператор, что и схема S". В терминологии работы [10] схема S является 2-вложением схемы 3'.

Важный параметр схемы — время её работы (задержка). Обычно оно оценивается глубиной, хотя задержка схемы может быть много меньше глубины [26]. Глубину клеточной схемы определим так.

Цепью в клеточной схеме назовём всякую последовательность клеточных элементов, в которой выход каждого элемента, кроме последнего, соединён с входом следующего. Длиной цепи будем называть число содержащихся в ней клеточных элементов, глубиной — число содержащихся в ней функциональных элементов. Цепь наибольшей глубины среди цепей, соединяющих входы и выходы схемы, назовём максимальной. Глубиной клеточной схемы назовём глубину её максимальной цепи. Глубину схемы S будем обозначать d(S). По нашему определению, глубина клеточной схемы равна глубине соответствующей ей схемы из функциональных элементов.

Цепь из коммутационных элементов назовём проводником. Отметим, что всякий проводник имеет нулевую глубину. Если в цепи 7 все элементы лежат на одной горизонтальной (вертикальной) прямой, то 7 будем называть горизонтальной {вертикальной) цепью. Клеточную схему назовём повторяющей, если напротив каждого её входа х на противоположной границе симметрично расположен выход г/, на котором реализуется тождественная функция у(х) = х.

Рассмотрим элемент X, изображённый на рис. 2 в центре нижнего ряда. Назовём горизонтальными элементами X и элемент, полученный из него поворотом на угол 7г. Полученные поворотами X на углы | и Щ- коммутационные элементы будем называть вертикальными элементами. Изображённый на рис. 2 вторым справа в нижнем ряду коммутационный элемент будем называть разветви-телем, крайним справа — мостом, вторым справа в верхнем ряду — элементом типа Y, крайним справа — элементом типа Z.

Основное различие двоичных базисов Б = ^Sz,v,~,h,-Jm ^и Б* = Biw-/ f — это наличие в Б* элементов типа Y. Наличие трёх лишних коммутационных элементов (рис. 2, нижний ряд) несущественно: если в схеме 5* в базисе Б* нет элементов типа У, то заменой всех коммутационных элементов разветвителями из неё можно получить некоторую схему S в базисе Б, глубина и площадь кото-

У

а)

5" 6)

Рис. 3

рой совпадают с глубиной и площадью схемы 5*. Элемент типа Y в базисе Б можно смоделировать схемой размера 2x3, использовав один элемент типа Z. Значит, для произвольной схемы S* в базисе Б* найдётся схема S в базисе Б, вычисляющая тот же оператор, такая, что d(S) = d(S*) и A(S) = QA(S*). Таким образом, порядок площади функций в базисах Б и Б* одинаков. Использование базиса Б* вместо Б оправдано тем, что во многих случаях конструкция схем в нём оказывается прозрачней, чем в Б.

В дальнейшем мы часто будем собирать схемы из подсхем. Клеточную схему S, состоящую из частей клеточных схем Si,..., S_m назовём композицией схем Si,..., S_m. Приведём пример, поясняющий это определение. Пусть даны схемы S, S' и пусть в схеме S каким-либо образом выбраны горизонтальный и вертикальный отрезки а и (3. Они делят схему S на четыре прямоугольника — подсхемы А, В, С, D (см. рис. 3, а). Раздвинем части А, В, С и D на такое расстояние, чтобы между ними поместилась схема S' (рис. 3, Ь). Лежащие на границах схем А, В, С, D клеточные элементы соединяются друг с другом коммутационными элементами по тем же правилам, что и в схеме 5. Так, например, вертикальные проводники соединяют те элементы подсхем Л и С, которые были смежными в схеме S. В зависимости от задачи на входы схемы S' могут подаваться как пограничные выходы подсхем Л, і?, С, j>, так и выходы внутренних клеточных элементов. На рис. З, Ь изображён пример соединения одного из входов схемы 5' и внутренней вершины х подсхемы А. При этом должно выполняться условие: в схеме S на вертикальном участке от точки х до точки а находятся только горизонтальные

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

Полученную схему S" будем называть композицией схем S и 3'. Выходами схемы S" могут быть как выходы схемы S — они по построению находятся на границе схемы S" — так и выходы схемы S', например отмеченный на рис. 3, b выход у. Отметим также, что 1{S") = 1(3) + l(S') и k(S") = k(S) + h{S'). Если две точки были концами некоторой цепи -у в схеме 5, то и в схеме S" также найдётся цепь У, связывающая их. Причём, так как добавлялись только коммутационные элементы, то глубина цепи 7' не превышает глубины цепи 7- Схему S можно разрезать на две, а не на четыре части, или не разрезать вовсе, добавляя к ней схему S' сбоку. Аналогично можно рассмотреть композицию более чем двух схем.

В работе используются обозначения о, О, Q и 0: f(n) = о(д(п)), если Нгпп^оо f(n)/g(n) = 0; f(n) = 0(д{п)), если найдутся константа с > 0 и число щ, такие, что для всех п ^ щ справедливо неравенство 0 ^ f(n) ^ сд(п); /(n) = &(д(п)), если и только если д(п) = 0(f(n)); f(n) = 6(f(n) = 0(д(п)) и f(n) = Q(g(n)). Логарифмы далее берутся по основанию 2. Все дальнейшие определения и обозначения будем вводить в тексте по мере необходимости.

Обзор литературы

Асимптотический подход к синтезу схем предложен К. Шенноном [27]. Он состоит в нахождении метода синтеза, трудоёмкость которого меньше трудоёмкости полного перебора, и такого, что параметры получаемых схем близки к минимальным для почти всех функций данного класса. Для всюду определённых функций в модели схем из функциональных элементов этот вопрос полностью исследован О. Б. Лупановым [14, 16, 17]. Из результата [14] следует, в частности, что в базисе {&, V,^—} почти всякая булева функция п аргументов / = f(x\y..., х_п) может быть реализована схемой 5, сложность и глубина которой одновременно асимптотически минималь-

ны. Точнее, L(S) < и rf(5) < п, причём доля функций, имеющих более простую реализацию, стремится к нулю с ростом п. С. Б. Гаш-ков [3] уточнил поведение функции Шеннона для глубины схем с точностью до постоянного слагаемого, показав, что во всяком базисе из двуместных функций, содержащем отрицание и либо конъюнкцию, либо дизъюнкцию, минимальная глубина реализующей функцию /(оті,..., ж„) схемы не превышает \п~ log₂ log₂n + o(l)] +2, что всего на 2 отличается от мощностной нижней оценки. В работе [17] найдена асимптотика сложностной функции Шеннона для множества всех полностью определённых булевых функций данного веса.

Сложность вычисления частичных булевых функций и частичных булевых функций данного веса схемами из функциональных элементов изучалась в большом числе работ, в том числе [2, 31, 33, 53]. В результате было найдено асимптотически точное равенство Цп, m, w) ~ log₂ () / log₂ log₂ () +0(п) для сложностной функции Шеннона L(n_tm,w) множества всех частичных n-местных булевых функций /, определённых на m-элементных областях и имеющих вес w. Это равенство справедливо для всех значений m Э> nlog₂n и всех таких w, что w ^ у; глубина схем при этом не рассматривалась. Кроме того, в [33] предложен метод синтеза, позволяющий для почти всех частичных функций / веса w получать схемы, глубина и сложность которых одновременно оптимальны по порядку. Сложность этих схем не превышает 4L(n, m, w), глубина не превышает log₂ L(n, т, w) + log₂ n ~ log₂ w + log₂ log₂ g + log₂ n, и в случае, когда w растёт сверхполиномиально с ростом п, является асимптотически минимальной.

Большое внимание в литературе уделено и схемам с ограничениями, наложенными на некоторые их характеристики. Так, например, получены оценки сложности схем, имеющих ограниченное ветвление [15]. Возник интерес и к пространственным параметрам схем. Первыми существенными результатами в этой области являются работа А. Д. Коршунова [8], где рассмотрена задача синтеза схем из функциональных элементов при некоторых ограничениях на длину соединительных проводников, и работа С. С. Кравцова [9], где вводятся схемы из клеточных элементов. С. С. Кравцов показал, что для любой булевой функции п аргументов можно построить реализующую её клеточную схему площади < | 2^П, и что для почти всех функций п аргументов площадь их реализации клеточными схема-

ми не менее і 2. Позднее А. Альбрехт [1] установил, что функция
Шеннона А(п) — maxj min^ A(S), где максимум берётся по всем
функциям f от п переменных, а минимум — по всем вычисляющим
/ клеточным схемам 5", имеет асимптотику А{п) ~ а - 2^П, где кон
станта а удовлетворяет неравенству \ = а ^ |. Точное значение
а остаётся неизвестным. В близкой клеточным схемам модели точ
ную величину функции Шеннона при п, равном степени двух, нашёл
Н. П. Редькин [21]. Н. А. Шкаликова [30] показала, что площадь уни
версального клеточного многополюсника, реализующего все булевы
функции п переменных, равна и неулучшаема по порядку.

Глубина клеточных схем ранее не рассматривалась; у построенной методом Кравцова схемы она оказывается экспоненциальной. Ранее в литературе не рассматривалась также и реализация клеточными схемами частичных функций.

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

Н. П. Редькин в [20] установил, что для реализации п-разрядно-го двоичного сумматора в базисе, состоящем из всех булевых функций двух переменных, необходимо и достаточно 5п — 3 элементов. Это один из крайне редких результатов теории вычислений, когда сложность задачи найдена точно. К сожалению, глубина известных сумматоров сложности 5п — 3 линейна, и при больших п далека от нижней оценки [log₂ п].

В конце 70-х — начале 80-х годов была осознана общность ряда распространённых задач: построение сумматоров, поиск в базах данных, организация вычислений в синхронных и асинхронных параллельных моделях, и др. Результатом стало понятие префикса {жі}*-і последовательности {a:i}"₌₁ элементов хі из некоторой полугруппы М с операцией и рассмотрение вычисления всех префиксных сумм {iLi^i}fc₌i этой последовательности как отдельной базовой задачи [49]. Мы будем называть префиксной схему, вычисляющую префиксные суммы входов и построенную из функциональных элемен-

тов . От операции требуется лишь ассоциативность. Сведения о результатах в области префиксных вычислений можно почерпнуть, например, из монографий [37, 50]. За последние 10-15 лет в области синтеза префиксных схем достигнуты значительные успехи. В числе прочих уже известны схемы линейной по п сложности и глубины log₂ п+ 0(1), где п — число входов. К сожалению, на данный момент подобные публикации недоступны отечественному читателю даже в глобальной сети Internet.

К префиксным вычислениям относится и вычисление переносов при поразрядном сложении чисел. У каждого разряда есть ровно три альтернативы: перенос х из него равен 0 или 1 вне зависимости от переноса у из предыдущего разряда, либо х зависит от у, и тогда х = 1 в том и только том случае, когда у = 1. Поэтому при к ^ 3 сумму двух n-разрядных чисел можно вычислить префиксной схемой сложности 0(п) и глубины log₂n + 0{1), построенной из двуместных fc-ичных функциональных элементов. В случае к — 2 непосредственно к префиксному суммированию сложение свести не удаётся и требуется более изощрённая техника. Двоичный сумматор асимптотически минимальной глубины и одновременно минимальной по порядку сложности построил В. М. Храпченко в работе [25]. В монографии Дж. Сэвиджа [22] уточнены константы в оценке сложности и на основе построений В. М. Храпченко показано, что глубина такого n-разрядного сумматора не превышает |"log₂n] + 7y^2["log₂n] + 14, а сложность — Зп+6'2^^[о&^2П\ При условии, что уменьшаемое не меньше вычитаемого схема для вычитания re-разрядных чисел может быть построена на основе сумматора, при этом глубина увеличивается на небольшую константу, а сложность — не более чем на линейное слагаемое Зп (см., напр., [32]). Таким образом, в модели схем из функциональных элементов вопрос о сложности сложения и вычитания в известном смысле решён окончательно: получена схема асимптотически минимальной глубины и оптимальной по порядку сложности (так как всякая схема, построенная из элементов с не более чем двумя входами и реализующая существенно зависящую от п аргументов функцию должна состоять из не менее чем п — 1 элементов).

Для операции умножения также известен ряд схем логарифмической глубины. А. Шёнхаге и В. Штрассен [28] доказали, что существует схема из функциональных элементов, умножающая два п-раз-рядных числа со сложностью 0(п log п log log п) и глубиной С? (log п).

Этот результат, являющийся развитием стратегии дробления сомножителей А. А. Карацубы [6] и А. Л. Тоома [23], получен при рекурсивном применении быстрого преобразования Фурье в специально подобранных кольцах вычетов. Методы такого типа ориентированы скорее на минимизацию сложности, чем глубины. Другой подход, восходящий к идеям А. А. Карацубы и Ю. П. Офмана [6], развил В. М. Храпченко [24]. Следуя ему, будем называть {п,т)-преобразователем всякую схему (клеточную или из функциональных элементов), у которой сумма т чисел на её выходах равна сумме п чисел на её входах. Предложенная схема умножения двух п-разрядных чисел строится в три этапа. Сначала произведение представляется, как в «школьном» алгоритме умножения в столбик, в виде суммы п чисел (глубина этой подсхемы не зависит от п). Затем к ним применяется (п, 2)-преобразование. На втором этапе решающую роль играет то, что глубина (п, 2)-преобразователя не зависит от числа разрядов в слагаемых. Наконец, на последнем этапе применяется подсхема — сумматор, вычисляющая сумму двух оставшихся не более чем 2п-разрядных слагаемых. Как уже говорилось, глубина сумматора может быть сделана по крайней мере асимптотически минимальной, не превышающей log₂n + 0{\J\og₂ⁿ) при линейной по п сложности, и на его выходах мы получим разряды искомого произведения.

Основную роль при таком подходе играет выбор счётчика разрядов. Это схема, у которой выходы являются разрядами суммы входов, то есть счётчик — частный случай преобразователя. В базисе {&,V,~} В. М. Храпченко привёл пример счётчика 7 разрядов с 3 выходами, и на его основе построил (тг,2)-преобразователь с глубиной, асимптотически не превышающей 5,121og₂ п. Эта оценка влечёт асимптотическую верхнюю оценку глубины умножения 6,121og₂n. В [24] также найдена нетривиальная нижняя оценка 2 log₂ п для глубины схемы умножения в базисе {&,V,^—}. Отметим, что константа 6,12 по-видимому значительно меньше константы, стоящей перед логарифмом в оценке глубины схемы Шёнхаге-Штрассена, но сложность схемы умножения, построенной из (п,2)-преобразователя, всегда будет по порядку равна п². Развивая идею В. М. Храпченко [24], М. Патерсон, Н. Пиппенджер и У. Цвиг [54] предложили более экономный способ соединения счётчиков. Выбрав счётчик с достаточно большим числом входов и хорошими параметрами, они построили в базисе, состоящем из всех булевых функций двух переменных, схему

умножения асимптотической глубины 4,571og₂n и сложности 0{гг). Этот результат является наилучшей верхней оценкой глубины умножения из известных на данный момент. Проблема синтеза неглубокого счётчика разрядов тесно связана с сортировкой и вычислением симметрических функций. Точная асимптотика глубины этих задач также пока неизвестна.

В отличие от остальных арифметических операций, для деления схемы логарифмической глубины долгое время были неизвестны. Первый результат в этой области появился в 1986 году, когда П. Бим, С. Кук и Г. Гувер [39] привели пример схемы из функциональных элементов, находящей неполное частное двух п-разрядных чисел с глубиной O(logn) и сложностью 0(n⁴log³n). Эта схема имеет два недостатка. Во-первых, её сложность значительно превосходит сложность схем для умножения с такой же по порядку глубиной. Во-вторых, при изготовлении схемы существенно используется китайская теорема об остатках с трудоёмкими вычислениями в конечных полях типа возведения в большую степень и взятия дискретного логарифма, для которых до сих пор не известно эффективных параллельных алгоритмов (для логарифмирования — даже в последовательных моделях) . Поэтому схема Бима, Кука и Гувера не удовлетворяет важному с теоретической точки зрения требованию равномерности, то есть неизвестно, существует ли машина Тьюринга, кодирующая схему с логарифмической ёмкостью ленты.

Вскоре появились работы, улучшающие оценку сложности. Й. Ха-стад и Т. Лейтон [46] предложили схему с улучшенными характеристиками, вычисляющую прямое и обратное преобразование китайской теоремы об остатках. Используя её, они показали, что для задачи деления двух га-разрядных чисел для всякого є > 0 можно построить схему из функциональных элементов с оптимальной по порядку глубиной 0(1/є² -logn) и сложностью 0(п^1+є). Схожий результат независимо получен в работе Н. Шанкара и В. Рамачанд-ры [57]. Построенные схемы не являются равномерными.

Равномерные схемы деления для различных определений равномерности найдены в работах [44, 47, 56]. А. Чиу, Г. Давида, Б. Ли-тоу [44] и В. Хессе [47] доказали принадлежность деления параллельным сложностным классам NC¹ и ТС. Их схемы имеют логарифмическую глубину и полиномиальную сложность, причём степень этого полинома достаточно велика. Хорошо известно [36], что во мно-

гих последовательных моделях (например, машины с произвольным доступом к памяти) деление и умножение имеют одинаковую битовую сложность. Дж. Рейф и С. Тейт [56] нашли схемы для деления глубины О (log п log log п) и сложности О [п log n log log п). Их схемы удовлетворяют любому разумному определению равномерности, в частности, принадлежат классу NC¹. Более того, в их работе доказано, что если существует схема сложности М_п и глубины (9(logn), определяющая произведение двух n-разрядных чисел, то существует схема сложности 0{М_п) и глубины O(lognloglogn), определяющая неполное частное при их делении. Для схем деления с логарифмической глубиной подобные результаты пока неизвестны.

Сложность реализации арифметических операций в клеточной модели пока мало изучена. Основные результаты в этой области принадлежат Н. А. Шкаликовой [30]. Она, в частности, доказала, что площадь каждой клеточной схемы, осуществляющей умножение двух двоичных n-разрядных чисел, по порядку не меньше чем п², и привела пример схемы умножения с площадью 0(п²) и глубиной П(п). Нижняя оценка площади Q(n²) была доказана в предположении двоичности клеточных элементов из базиса, однако может быть распространена и на fc-ичные базисы при к ^ 3. Также в работе [30] указан способ построения клеточного двоичного п-разрядного сумматора площади 0(п) и глубины 0(п). Аналогично можно построить и &-ичныЙ сумматор с площадью и глубиной 0(п). Очевидно, что площадь таких сумматоров оптимальна по порядку.

В модели СФЭ верхняя оценка Шёнхаге - Штрассена сложности умножения до сих пор не улучшена, точно так же как неизвестны и нелинейные нижние оценки. Таким образом, пока непонятно, действительно ли умножение более сложная операция, чем сложение. Заметим, что, с другой стороны, для модели клеточных схем теорема Шкаликовой утвердительно отвечает на этот вопрос, поставленный А. Н. Колмогоровым в конце 1950-х годов и послуживший толчком для целой серии исследований в области быстрых вычислений [5].

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

гарифму количества информации.

С другой стороны, всякую клеточную схему S можно рассматривать как укладку некоторой схемы из функциональных элементов 5" в прямоугольную решетку. Произвольный узел решётки может либо не принадлежать схеме, либо быть функциональным элементом, либо быть вершиной пути, соединяющего какой-то вход (схемы или её функционального элемента) с каким-то выходом (схемы или её функционального элемента). Если базисный набор клеточных элементов содержит реализующий две тождественные функции коммутационный элемент - мост (рис. 2, крайний справа в нижнем ряду), то через не являющийся функциональным элементом узел решётки допускается прохождение не более двух путей из укладки. Отображение, соответствующее такой укладке, в работе [10] названо 2~вложением. Если же все базисные коммутационные элементы реализуют не более одной тождественной функции, то через каждый узел решётки может проходить не более одного пути, и соответствующее отображение схемы 5 в прямоугольную решётку будет гомеоморфизмом [1-вложение [10]). Укладки схем везде ниже будут правильными 2-вложениями. Длина и ширина укладки равны длине и ширине схемы.

Укладкам графов в прямоугольные решётки посвящена обширная литература (см., напр., обзор в монографии Дж. Ульмана [58]). Универсальные нижние оценки площади как правило используют обилие рёбер графа схемы. Известны нетривиальные результаты и для разреженных графов, в частности, для деревьев.

Рассмотрим плоскую область D, у которой на границе 0D выбраны п точек xi,... ,х_п с попарным расстоянием не меньше единицы. Р. Брент и X. Кунг [43] доказали, что если хь ... ,х_п — листья полного двоичного дерева Т, лежащего на плоскости внутри Z), а область D — выпуклая, то сумма длин ребер дерева Т не меньше чем Q{n\ogn). Эта теорема непосредственно переносится на прямоугольные укладки и клеточные схемы. Требование выпуклости является существенным: if-дерево [58] с п листьями имеет сумму длин рёбер и площадь укладки одновременно равные 0(п). Ю. Громкович и Б. Шустер [4] привели пример такой последовательности булевых функций д_п = g_n(xi,,..x_n), что площадь реализации функции д_п правильной клеточной схемой равна 6(пг), а неправильной (то есть такой схемой, у которой входы не обязательно лежат на границе) — 0(п). Эти результаты показывают, что правильная и неправильная

клеточные модели существенно различны.

Теорема Брента - Кунга уточнена в работе [10], где С. А. Ложкин и Ли Да Мин доказали, что наименьший линейный размер прямоугольной решетки, куда правильно 2-вложено полное двоичное дерево с 2^я листьями, равен f¹^]- Они также построили вложение, у которого один из линейных размеров минимален, а площадь асимптотически равна \п2^п и доказали её минимальность. Позднее С. А. Ложкин [11] установил аналогичный результат ^п2^п для площади 1-вложений.

Из результатов [10, 11, 43] следует нижняя оценка H(nlogn) для площади клеточных схем, обладающих полными поддеревьями с п = 2^т листьями по периметру схемы. Для неполных деревьев общего вида нижние оценки площади укладки пока неизвестны.

Обзор содержания диссертации

Результаты главы 1 носят вспомогательный характер и используются далее в главе 3. В первом разделе главы 1 рассматриваются способы реализации (N, 2)-преобразователей в модели схем из функциональных элементов. Выбранный базис Q = {ф,&} С Pit состоит из функции сложения по модулю к, хфу — х + у (mod fc), и функции переноса х Sz у, где х к у = 1, если х + у > fc, а иначе х к у = 0 (здесь х,у Є {0,1,..., к — 1}). Мы будем интересоваться минимизацией глубины fc-ичного (N, 2)-преобразователя.

Лемма 1. В базисе П^ существует (N,2)-преобразователь S п-разрядных k-ичных чисел с глубиной

d(s) < Г^(* ₊ і)1|Г^у ₊ і)11. _{1о& N + 0(log2 к)}

log₂(fc + 1)-1

и сложностью L[S) — O(Nnlogk) при условии N ~ 0(к^п).

Ещё уменьшить глубину (N, 2 ^преобразования для небольших к позволяет следующая

Теорема 1. Пусть к = 2^Г + 1, г > 1. Тогда в базисе Qk существует (Лґ, 2) -преобразователь Sk_tN п-разрядных к-ичных чисел с глубиной

^'^ ^ 1 L г, ^l0g2 ^N ' (¹ + W>

1 - Jog₂ a

где a — наибольший из модулей корней многочлена х^г — x^r ~ 1.

В частности, oI(Sz,n) ^ 3,271og₂iV и й(5э,лг) ;$ l,871og₂iV. При этом L(Ss,n) х L(S$,n) х nN', при условии что N ^ 2^^п\

Второй раздел главы 1 посвящен клеточным булевым (iV, 2)-пре-образователям. Будем считать, что входы и выходы клеточного преобразователя не обязательно находятся на его границе, то есть что клеточный преобразователь — не обязательно правильная клеточная схема. Счётчиком разрядов будем, как обычно, называть (правильную) схему, выходы которой являются разрядами суммы входов. Иначе говоря, счётчик с п входами — это (п, [log₂(n + 1)]^преобразователь одноразрядных чисел. В этом разделе доказаны два вспомогательных утверждения.

Лемма 2. Пусть имеется клеточная схема S, внутри которой на выходах клеточных элементов, расположенных в узлах прямоугольной решётки размера п х 3, находятся разряды трёх целых поразрядных чисел х, у и z. Тогда композицией схемы Sun трёх-разрядных счётчиков можно получить клеточный (3,2) -преобразователь S', на выходах клеточных элементов которого будут вычисляться разряды двух таких (п + 1)-разрядных чисел а и Ь, что а + Ь — х - z. Длина и ширина схемы S' удовлетворяют неравенствам l(S') = l(S) + 8 и h(S') : h(S) + 8п + 4, а её глубина превышает глубину схемы S не более чем на 5.

Лемма 3. Существует клеточный (п, 2) -преобразователь, получающий из п штук т-разрядных слагаемых, т = 0(п), два слагаемых с той же суммой, и обладающий следующими параметрами: его глубина равна 0(logn), длина — 0(п), ширина — 0(n\ogn), и, следовательно, площадь равна 0{n²logn).

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

Теорема 2. Для всякой всюду определённой п-местной булевой функции f существует реализующая её клеточная схема Sf с параметрами

A(S_f) < 9 2^п + о(2^и), d(S_f) < 2n + 1.

Площадь и глубина схемы Sj нсулучшаемы по порядку для почти всех функций /.

Теорема 3- Пусть D С {0,1}^п и \D\ = Q(n²). Тогда для каждой частичной п-местной булевой функции /д, определённой в D, можно построить такую клеточную схему Sf_D, реализующую функцию fo, что A(Sf_D) = 0(\D\) и d(Sf_D) = <9(log|D|). Площадь и глубина схемы S/_D оптимальны по порядку для почти всех функций f_D.

Теорема 4. Пусть D С {0,1}", |D| = т, w = П{п²) и w < f. Тогда для каждой частичной п-местной булевой функции /д веса w, определённой на области D, можно построить такую клеточную схему Sj , реализующую функцию /д, что

ТП тп

A(S}J = 0(w log -) и d(S}_D) = O(\ogw + log log -).

Площадь и глубина схемы S} оптимальны по порядку для почти всех функций /д.

Следствие теоремы 4. Пусть w — Q(n²) и w ^ 2^n_1. Тогда для каждой всюду определённой п-местной булевой функции f веса w можно построить клеточную схему S'*, реализующую функцию

f, с параметрами A(S'_f) = C(log(^)) it d{S'_f) = C(logIog (²J)). Площадь и глубина схемы St оптимальны по порядку для почти всех функций f.

Схемы теорем 2-4 строятся в каноническом базисе {&, V,"} [9].

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

Теорема 5. Пусть схема из функциональных элементов S построена в некотором базисе 21 не более чем двуместных функций из J?2i имеет п входов, т выходов и вычисляет некоторый оператор F : {0,1}" н+ {0,1}^т со сложностью L и глубиной d. Тогда в базисе 21 можно построить клеточную схему S', вычисляющую тот же оператор F и также имеющую п входов и т выходов, которые расположены на её границе. При этом глубина схемы S' равна d, а занимаемая ею площадь — (L + п)².

Следствие теоремы 5. Для всякого положительного є существует клеточная схема глубины Q(l/e²-\ogn) и площади 0(п^2+Е) при растущем п, решающая задачу деления для двух п-разрядных чисел,

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

В начале раздела даны определения произвольного вложения графа в граф, и вложения графа в прямоугольную решётку, образом которого является клеточная схема (2-вложение [10]). Т-вложени-ем затем названо произвольное 2-вложение / орграфа G в плоскую прямоугольную решётку, при котором образы входных полюсов G лежат на верхней стороне решётки, образы выходных полюсов — на нижней, и среди транзитных рёбер в образе /(G) нет рёбер вида f, направленных вертикально вверх, а могут быть только рёбра вида 4, —> и -<—. Т-схемами названы клеточные схемы, являющиеся образами схем из функциональных элементов как помеченных орграфов при Х-вложениях. Иначе говоря, у каждого из клеточных элементов в Т-схеме ни один из его входов не расположен на его нижней границе.

Обозначим At(G) минимальную площадь решётки, в которую возможно Т-вложение графа G. Основным утверждением раздела 2.3 является лемма 9.

Лемма 9. Пусть D — произвольное двоичное дерево глубины d

с п листьями. Тогда At(D) = П(р^^г)

Из основной леммы 9 вытекает теорема 6.

Теорема 6. Площадь всякой Т-схемы глубины d, реализующей существенно зависящую от п аргументов функцию, по порядку не меньше, чем (п log n)/ log ^d"^g|ⁿ

Следствие теоремы 6. Каждая Т-схема, которая реализует существенно зависящую от п аргументов функцию с глубиной О (log п)_} имеет площадь по порядку не меньшую, чем nlogn.

Клеточные схемы

Замечание 2. Наилучший с асимптотической точки зрения двоичный сумматор n-разрядных чисел обладает линейной по п сложностью и глубиной, не превышающей log2n + 0(y/log2n) [25]. Для получения Ат-ичного сумматора при к 3 можно использовать как его, так и префиксные схемы [49]. В настоящее время известны схемы вычисления п префиксных сумм с глубиной log2 п + 0(ї) и сложностью 0(п). Это позволяет построить &-ичный п-разрядный сумматор S3, обладающий такими же параметрами (глубиной log2 п+0(1) и сложностью 0(п)). При использовании сумматора Е в схеме умножения, построенной на основе (п, 2)-преобразователя глубины clog2n, получим, что глубина схемы умножения асимптотически не превышает (1 + c)log2n. В частности, отсюда можно заключить, что существует девятиричная схема умножения n-разрядных чисел глубины 2,871og2n и сложности 0(п2). Будем считать, что входы и выходы клеточного (тг, к)-преобразователя не обязательно находятся на его границе, то есть клеточный преобразователь — не обязательно правильная клеточная схема. Рассмотрим счётчик разрядов F с тремя входами и двумя выходами, выходы которого являются разрядами суммы входов. Иначе говоря, F — это (3, 2)-преобразователь одноразрядных чисел. Можно легко убедиться, что счётчик F в базисе Б& г реализуется клеточной схемой длины 7, ширины 7 и глубины 5 (рис. 4), а в базисе Б&,у, Ф — клеточной схемой длины 5, ширины 5 и глубины 3. Можно показать, что глубина этих схем (в базисах {&, V, } и {&, V, , } соответственно) неулучшаема. Указанные константы для дальнейшего изложения несущественны. Способ построения простейшего (п, 2)-преобразователя глубины 0(logn) восходит к работе А. А. Карацубы и Ю. П. Офмана [6]. Он основан на использовании схемы F. Объединим разряды одного номера у трёх m-разрядных чисел. Возьмём т экземпляров счётчика F и подадим на вход каждого экземпляра соответствующую тройку разрядов. Тогда множество выходов всех счётчиков будет множеством разрядов двух чисел, сумма которых равна сумме трёх исходных. Иначе говоря, мы получили m-разрядный (3, 2)-пре-образователь. Его особенность — линейная по т сложность и не зависящая от m глубина. С помощью (3, 2)-преобразователя (п, 2)-преобразователь легко строится по индукции. На первом шаге исходные п штук m-разрядных слагаемых разбиваются на группы по три, за исключением последней группы, которая может быть неполной. К каждой полной группе параллельно с другими применяется (3, 2)-преобразование.

В результате число слагаемых уменьшается примерно в 1,5 раза. Аналогично выполняется второй шаг, третий, и т. д. Когда останется два слагаемых, алгоритм оканчивает работу. Очевидно, что построенная схема будет (п,2)-преобразователем и её глубина равна O(logn). При её построении используется 0(тп) С(п2) функциональных элементов, если т = 0(п). Перенесём этот метод на плоские схемы, стараясь использовать как можно меньше коммутационных элементов. Лемма 2. Пусть имеется клеточная схема S, внутри которой на выходах клеточных элементов, расположенных в узлах прямоугольной решетки размера пхЗ, находятся разряды трёх целых п-разрядных чисел х, у и z. Тогда композицией схемы Sun экземпляров счётчика F можно получить клеточный (3,2) -преобразователь S , на выходах клеточных элементов которого будут вычисляться разряды двух таких (п + 1) -разрядных чисел а и Ъ, что а + Ъ = х + у + z. Длина и ширина схемы S удовлетворяют неравенствам a её глубина превышает глубину схемы S не более чем на 5. Доказательство. Процесс построения схемы S приведён на рис. 5. По условию разряды чисел х, у и z расположены внутри схемы 5 так, что разряды с одинаковыми номерами лежат на одной горизонтальной прямой (рис. 5, а, разряды слагаемых отмечены жирными точками). Разрежем схему S на п не обязательно равных частей-подсхем так, чтобы в каждой подсхеме было по три разряда и они лежали на её границе (рис. 5, 6). Объединим эти части с п экземплярами схемы F, соединив каждые три разряда со входами схемы F коммутационными элементами (рис. 5, с, проводники между подсхемами для простоты не указаны). На выходах схем F получим In разрядов двух чисел, сумма которых равна сумме трёх исходных. Младшие разряды на выходах схем F находятся слева, а старшие — справа. Теперь сделаем так, чтобы, как и в исходной схеме, те разряды слагаемых, которые имеют одинаковые номера, лежали на одной горизонтальной прямой (рис. 5, d, полученные разряды отмечены незакрашенными кружочками). При этом первый и последний разряды получившихся чисел оказываются непарными. Чтобы этого избежать, добавим к ним в пару фиктивные нулевые разряды (на рис. 5, d два незакрашенных кружочка, к которым не подходят коммутационные элементы, обозначают функциональные элементы, реализующие константу 0 в базисе Б& v - , или реализующие её подсхемы размера 2 х 2 в базисе В ). На рис. 5, е представлен общий вид полученной схемы S . Так можно встроить (3,2)-преобразователь в любую схему, если внутри неё разряды слагаемых расположены указанным образом. Оценки длины, ширины и глубины схемы S следуют из приведённых рассуждений с учётом параметров схемы F. Лемма 2 доказана. Лемма 3. Существует клеточный (п, 2)-преобразователь, получающий из п штук т-разрядных слагаемых, т — 0(п), два слагаемых с той снсе суммой, и обладающий следующими параметрами; его глубина равна C(logn), длина — 0(п), ширина — Q(nlogn), и, следовательно, площадь равна 0(n2logn). Доказательство. Искомую схему построим пошагово. Пусть на 1-м шаге построена схема 5/. Она осуществляет (тг, iV(i) преобразование, где N(1) — число слагаемых на шаге Z, JV(0) = п. На её основе построим схему Si+i- По предположению индукции разряды слагаемых расположены внутри схемы Si в узлах прямоугольной решётки так, как показано на рис. 6, а.

Разрежем Si вдоль пунктирных линий на подсхемы так, чтобы в каждой подсхеме было по три слагаемых (в последней подсхеме их может быть меньше). К каждой подсхеме, за исключением, быть может, последней, применим (3,2)-преобразование, описанное в лемме 2. Если в последней подсхеме имеется менее трёх слагаемых, то выведем их разряды коммутационными элементами на соответствующие горизонтали как в доказательстве леммы 2. Полученная схема Si+i (см, рис. 6, Ь) имеет то же расположение выходов, что и схема Sf разряды каждого слагаемого лежат на одной вертикальной прямой, разряды разных слагаемых с одинаковыми номерами — на одной горизонтальной. К схеме 5(+i снова можно применить шаг индукции. Пусть N(1) — число слагаемых в схеме St на 1-м шаге. С ростом / число N(1) уменьшается, и для некоторого I = log3у2 п + 0(1) станет равным двум. Полученная в этот момент схема Si реализует (n, 2)-преобразование. Отметим, что эта схема не является клеточной в строгом смысле, так как её входы и выходы не расположены на границе. Тем не менее, её можно использовать как подсхему. Оценим параметры полученной схемы. Нетрудно видеть, что Глубина построенного (п,2)-преобразователя будет пропорциональной logn, так как на очередном шаге построенная до того схема объединяется с подсхемой, глубина которой не зависит от п, и число шагов равно 0(logn). По построению на каждом шаге для длины и ширины схемы 5(+i выполнены неравенства (здесь используются конкретные размеры счетчика разрядов F, не влияющие на порядок роста результата) где M(l) — наибольшее число разрядов в слагаемых на 1-м шаге. На нулевом шаге схема SQ содержит п слагаемых пот = (п) разрядов в каждом. Следовательно, /(,) = 0(п) и h(So) = 0(п). Также ясно, что М(1) — 0(п) для рассматриваемых значений /. Отсюда следует, что l(Si) — 0(п) и k(Si) = 0{n\ogn) при / = Oilogn). Поэтому площадь (п, 2)-преобразователя не превосходит 0(п2 logn). Лемма 3 доказана. Эта глава посвящена различным общим оценкам площади клеточных схем, учитывающим глубину. В первом разделе устанавливается, что большинство всюду определённых и частичных булевых функций можно реализовать клеточными схемами с одновременно оптимальными по порядку глубиной и сложностью. Второй раздел посвящен моделированию схем из функциональных элементов клеточными схемами. В третьем разделе этой главы рассмотрен класс клеточных схем, названных Т-схемами, для которого удалось связать нижнюю оценку площади с глубиной — чем меньше глубина Т-схемы, тем больше должна быть её площадь.

Моделирование СФЭ клеточными схемами

Теорема 5, Пусть схема из функциональных элементов S построена в некотором базисе 01 не более чем двуместных функций из Рг, имеет п входов, т выходов и вычисляет, некоторый оператор F : {0,1}п н-у {0,1}т со сложностью L и глубиной d. Тогда в базисе клеточных функциональных элементное, реализующих функции ба-зиса%, можно построить клеточную схему S , вычисляющую тот же оператор F и также имеющую п входов и т выходов, которые расположены на её границе. При этом глубина схемы S равна d, а занимаемая ею площадь — (L + п)2. Доказательство. Рассмотрим схему 5 как помеченный орграф без ориентированных циклов. В силу выбора базиса в каждую его вершину входит не более двух ориентированных рёбер. Известно, что у всякого орграфа без циклов вершины можно так занумеровать натуральными числами, что каждое ориентированное ребро будет вести от вершины с меньшим номером к вершине с ббльшим. Пусть х\,Х2,... ,хп и /і, /2,.. ., fb — входы и функциональные элементы схемы S, занумерованные по такому принципу. Каждому функциональному элементу fi поставим в соответствие клеточный элемент /, , который реализует ту же функцию из Рг, что и элемент /г-. Возьмём на плоскости квадратную область D размера (n + L) х (п + L), разделённую на единичные квадраты. Её левый нижний угол поместим в начало координат. По диагонали области D расположим клеточные элементы, соответствующие вершинам орграфа S. В ячейку с координатами (г, г), 1 г п поместим коммутационный элемент — разветвитель, изображённый на рис. 2 вторым справа в нижнем ряду. Соединим его горизонтальным проводником из мостов (элемент-мост изображён на рис. 2 крайним справа в нижнем ряду) с левой стороной области D. Переменную Х{ подадим на вход пограничного элемента с координатами (1,г). По построению она реализуется на выходах элемента с координатами (і, г). Функциональный элемент //, 1 : і L поместим в ячейку (п + г,п + г). Ориентируем элемент Д так, чтобы его входы находились на его левой и нижней сторонах, а выходы — сверху и справа. Соединим диагональные элементы с координатами (г,г),1 г п + Ь горизонтальными проводниками из горизонтальных коммутационных элементов с правой стороной области D. Вертикальными проводниками соединим с верхней стороной области D ячейки (г, г), п + 1 г .п + L я (г, п), 1 г п. Таким образом, на выходах верхней и правой сторон области D реализуются все функции, реализуемые её диагональными элементами.

Построенная система ячеек обладает ещё одним свойством: в силу выбора нумерации функциональных элементов, на одной горизонтали левее каждого элемента /t , 1 г L находятся коммутационные элементы, реализующие все переменные и выходы других функциональных элементов, которые могут подаваться на его вход. То же самое можно сказать об элементах, лежащих ниже элемента /$ на одной вертикали с ним. Воспользуемся этим наблюдением. Пусть в схеме S входы двуместного функционального элемента fa соединены с некоторыми вершинами а и Ь, где а,Ь Є {х\,.. ., хП7 /х,..., fi-i}- Этим вершинам соответствуют диагональные ячейки ае и У из области D, с координатами (к, к) и (1,1) соответственно. Без ограничения общности можно считать, что к $С / п + г. По построению коммутационные элементы (kt п + г) и (п -f і, I) реализуют те же функции, что и элементы в ячейках а! и Ь . Соединим коммутационный элемент (fc,n+i) горизонтальным проводником 71 с ячейкой (п + i,n + г), в которой расположен функциональный элемент //. Соединим элемент (тг+г, I) с ячейкой (п + г,гг + г) вертикальным проводником 72- Ясно, что проводники 7і и 72 пересекают другие проводники только под прямым углом. Все коммутационные элементы в точках пересечения заменим мостами. Это не нарушит никаких цепей в D. Аналогично поступим, если элемент fi реализует одноместную функцию. Проделаем эту процедуру для всех г, 1 і L. В итоге получим структуру из клеточных элементов S , которая является вложени ем схемы S в прямоугольную решётку, а значит, реализует тот же оператор. К тому же по построению схема Sr — правильная. Оче видно, она обладает всеми заявленными в утверждении свойствами. Теорема 5 доказана. П Замечание 1. В доказательстве теоремы 5 не использовалась двоичность оператора F, а учитывалось только то, что все функциональные элементы схемы S имеют не более двух входов. Отметим, что хотя эта теорема не будет далее применяться к fc-ичным операторам, она справедлива и для них. Также отметим, что она справедлива и для не всюду определённых операторов. Замечание 2. На теорему 5 можно посмотреть и с теоретико-графовой точки зрения. При её доказательстве фактически было построено 2-вложение [10] в плоскую прямоугольную решётку площади тп2 произвольного орграфа 5cm вершинами и без ориентированных циклов. При этом образ каждой вершины оказался соединён с границей укладки некоторым ориентированным путём. От орграфа 5 требуется лишь, чтобы в каждую его внутреннюю вершину входило не более двух рёбер (выходная степень ветвления может быть неограниченной). Для планарных графов оценку площади вложения можно улучшить. В частности, если граф с m вершинами планарен и степень каждой его вершины не превышает 4, то его можно вложить в решётку площади 0(m\og2тп) [58]. Замечание 3. Используя метод А. Н. Колмогорова и Я. М. Барз-диня [7] можно показать, что по схеме из функциональных элементов глубины d и размера L можно построить клеточную схему площади порядка L2 с такой же глубиной d, реализующую тот же булев оператор.

Эта оценка сильнее оценки из теоремы 5, но её доказательство требует несколько больших усилий. Более того, рассматриваемые в настоящей работе функции и операторы существенно зависят от всех своих аргументов. Как нетрудно убедиться, всякая существенно зависящая от всех своих п входов схема имеет сложность не менее п — 1. Следовательно, оценка (L-\-n)2 для площади укладки такой схемы на плоскость отличается от оценки L2 не более чем на постоянный множитель, а для нелинейно растущей сложности L эти оценки вообще совпадают в главном члене. Замечание 4. Интересен также вопрос, насколько груба оценка теоремы 5. В настоящее время известны результаты, показывающие, что для некоторых булевых функций и операторов сложность их вычисления плоскими схемами значительно больше традиционной схемной сложности, учитывающей лишь количество функциональных элементов. Н. А. Шкаликова в [30] доказала, что площадь всякой клеточной схемы, осуществляющей умножение двух п-раз-рядных чисел, заданных в двоичной системе счисления, не может быть меньше Q(n2). С другой стороны, из работы А. Шёнхаге и В. Штрассена [28] (см. также [59]) известно, что существует схема из функциональных элементов, умножающая два поразрядных числа со сложностью О (п log п log log п) и глубиной C?(logn). Из теоремы Шёнхаге — Штрассена и теоремы 5 следует существование клеточ- ной схемы для умножения га-разрядных чисел с глубиной C(logn) и площадью 0(п2 log nlog log га), С учётом нижней оценки П(п2) площадь этой схемы почти оптимальна. В разделе 3.4 будет построена схема умножения с логарифмической глубиной и ещё меньшей площадью 0(n2logn). Другой пример можно привести, если вглянуть на теорему 5 со стороны теории графов. Из литературы по проблемам вложения в прямоугольные решётки известны квадратичные нижние оценки для разнообразных графов. Например, площадь вложения сети быстрого преобразования Фурье (БПФ) порядка п, которую называют ещё сетью-бабочкой (butterfly network), равна П(п2) (напр. [40], см. также [58]). С другой стороны, сеть ВПФ порядка п содержит 0(n\ogn) вершин, поэтому по теореме 5 площадь её вложения заведомо не превышает 0(п2 log п) (на самом деле можно показать, что 0(п2) [58]). Из этих примеров видно, что для некоторых задач теорема 5 предлагает близкие к оптимальным решения. Замечание 5. И. Хастад и Т. Лейтон [46] показали, что для задачи деления двух n-разрядных чисел для всякого є 0 можно построить схему из функциональных элементов с оптимальной по порядку глубиной 0(1/є2 logn) и сложностью 0(п1+є). Позднее аналогичный результат был независимо получен Н. Шанкаром и В. Рамачандрой [57]. Это утверждение и теорема 5 дают следующее полезное следствие.

Клеточные схемы для сложения

Пусть два n-разрядные числа X и Y записаны в позиционной системе счисления с основанием к В этом разделе мы построим клеточную схему, определяющую разряды их суммы В дальнейшем (клеточную) схему, вычисляющую оператор будем называть (клеточным) к-ичным п-разрядным сумматором. Очередной разряд Zi суммы Z можно получить из соответствующих разрядов Х{ и у І слагаемых X и Y, учитывая перенос гиг из предыдущего (г — 1) го разряда в следующий г-й по формулам: Здесь ф обозначает сложение по модулю к; &д. — пороговую функцию, равную 1 если сумма аргументов превышает (к — 1) и 0 в противном случае; Vfc — пороговую функцию, равную 1 если сумма аргументов превышает (к — 2): Знаки & и V обозначают традиционные конъюнкцию и дизъюнкцию (отметим, что при всяком к перенос из разряда в разряд не может превышать единицу, т. е. он булева величина). Будем считать, что w\ = 0. Н. А. Шкаликова в работе [30] привела пример клеточного двоичного п-разрядного сумматора площади 0(п) и глубины 0(п). Аналогично можно построить и fc-ичный сумматор с площадью и глубиной 0(n) для A; 3. Очевидно, что площадь таких сумматоров оптимальна по порядку. Глубина, однако, далека от минимально возможной. Известно [25, 59], что в модели схем из функциональных элементов существуют тг-разрядные сумматоры, у которых глубина и сложность оптимальны по порядку одновременно: глубина равна 0(logn), а сложность — 9(п). Следствие теоремы 6 (раздел 2.3) показывает, что в модели Т-схем это невозможно: всякая схема глубины O(logn) имеет площадь fi(nlogn). Иначе говоря, теорему 6 можно рассматривать как утверждение о невозможности одновременно оптимизировать и площадь, и глубину в классе клеточных Т"-схем. Теорема 8. При к 3 существует к-ичный п-разрядный клеточный сумматор Е„ глубины d(Tin) [log2(ri + 1)] + 2, являющийся Т-схемой. Его площадь, удовлетворяющая неравенству минимальна по порядку в классе Т-схем логарифмической глубины. Доказательство. Пусть для простоты k = 3 (при ббльших к всё аналогично). Сумматор логарифмической глубины основан на хорошо известной конструкции под названием «предвычисление переноса» (carry look ahead) [37, 59]. Если в формуле (3.6) известны перенос « и величина ХІ Ф уі} то разряды суммы Z{ для всех г можно вычислить подсхемой глубины 1, и задача сводится к нахождению быстрой Каждая пара разрядов слагаемых ХІ и уі характеризуется числом Xii равным 0,1 или 2.

Паре {ХІ,УІ) сопоставим х = 0, если ХІ+УІ = 1. Такая пара разрядов не создаёт перенос в следующий разряд, даже если предыдущая пара дала перенос в г-й разряд (то есть Wi+i — О при любом Wi). Двойка сопоставляется паре, если х\ + у І — 2. Такая пара при сложении передаст перенос из предыдущего в следующий разряд (то есть Wi+i = 1 тогда и только тогда, когда щ — 1). Наконец, в случае Х{ + уі 3 сопоставим паре (ХІ, УІ) число Хг = 1 — перенос wi+i равен единице вне зависимости от W{. Величину \г назовём характеристикой г -ro разряда. Определить для разряда с номером г, чему равен перенос ги;, можно с помощью характеристик предыдущих разрядов. Предыдущие разряды создадут перенос ш,- = 1, если первая (начиная с Xi-i) сРе ди характеристик младших разрядов Хг-ъ - Х2, Хі отличная от 2 характеристика равна 1. Аналогично, переноса не будет (wi = 0), если первая отличная от 2 характеристика младшего разряда равна 0. Рассмотрим две функции трёхзначной логики х 0 у и Легко видеть, что функция , рассматриваемая как операция на множестве {0,1,2}, ассоциативна, то есть х (у г) = (ж г/) z ДЛЯ ПРОИЗВОЛЬНЫХ X,y,Z. В СИЛУ СКазаННОГО ВЫШе Хг хг 3/гэ а перенос гУі можно вычислить по формуле (здесь мы учли, что w\ = 0). Из равенства (3.7) заключаем, что вычисление совокупности переносов {гУі}" 1 сводится к нахождению префиксных сумм характеристик Хп- , Хі по отношению к операции . Для этого можно применить какую-нибудь префиксную схему. Полученные на её выходах переносы сложим с разрядами слагаемых одновременно и независимо, и найдём Z{. Таким образом, клеточный сумматор 2П состоит из трёх подсхем А, В и С. Подсхема А находит характеристики ХІ = %І У І И суммы Хг у І всех пар разрядов, 1 г п. Подсхема В является экземпляром схемы Рп+\ из теоремы 7, на её входы подаются выходы х% схемы А и константа 0. У подсхемы В есть также п вспомогательных входов, с которых величины ХІ Ф уі поступают к вспомогательным выходам, соединённым с подсхемой С. Наконец, подсхема С независимо вычисляет разряды суммы Z = X + Y по формуле (3.6). Пример 7-разрядного сумматора 7 приведен на рис. 14. Оценим параметры схемы „. Очевидно, d{A) = d(C) = 1, d(B) = [log2(n +1)]. Как нетрудно убедиться, схемы А, В, С можно построить так, что f(E„) = 1(A) = (В) = Z(C) = 3(п + 1), Л(Л) = 3, h{B) = h(Pn+i) 2[log2(n + 1)1, и h(C) = 1. Отсюда получаем оценки глубины d(S„) = d(A) + d() + d(C) [bg2(7i + 1)] + 2, и площади В случае к = 2 информационная ёмкость одного разряда слишком мала, чтобы учесть все три альтернативы для характеристики пары разрядов слагаемых — создавать перенос, обнулять и передавать из предыдущего разряда. Каждое из её возможных значений 0, 1, 2 можно закодировать парой битов. В двоичных базисах B&,v,- и B&v- нетрудно построить двоичную клеточную Т-схему размера 4 х 4 и глубины 2, моделирующую троичный клеточный элемент . Заменяя все клеточные элементы троичного сумматора Еп на соответствующие двоичные схемы (с очевидным изменением подсхем А и С), получим двоичный сумматор . По построению d(Si) = 2с (п) и A(SJ) - 16А(„). Следствие. Существует двоичный п-разрядный клеточный сумматор глубины 21og2n + 0(1) и площади 0(nlogn), минимальной по порядку в классе Т-схем логарифмической глубины.

Известно (напр., [32]), что разность двоичных n-разрядных чисел можно вычислить с помощью сумматора. Этот способ можно обобщить и на fc-ичный случай, когда к 3. Пусть числа X и Y записаны в системе счисления с основанием к (см. (3.5)) и пусть X Y. Обозначим через X такое число, что X + X = кп — 1. Иначе говоря, X — X/iLi k -1) гДе %i обозначает отрицание г-го разряда числа X по Лукашевичу: х к — 1 — х. Очевидно, что X — Y = X + Y. Следовательно, если заранее известно, что разность неотрицательна, то для её вычисления можно использовать любой сумматор. Достаточно обратить разряды уменьшаемого числа X и разряды результата X+Y. Отсюда получаем ещё одно следствие теоремы 8. Следствие. При к 3 существует клеточная k-ичная Т-схема Т П} находящая разность поразрядных чисел X uY при условии X Y, для глубины которой справедливо равенство d(T.n) — log2n + 0(1), В базисе из двоичных клеточных элементов существует схема вычитания глубины 2Iog2Ti + 0(1). Площади этих схем равны 0(n\ogn) и минимальны по порядку в классе Т-схем логарифмической глубины. Н. А. Шкаликова в работе [30] доказала, что площадь каждой клеточной схемы, осуществляющей умножение двух двоичных п-раз-рядных чисел, по порядку не меньше чем п2, и привела пример схемы площади 0(п2) и глубины Q(n). Здесь мы рассмотрим способ построения клеточной схемы для умножения n-разрядных чисел с глубиной G(logn). Теорема 9. В клеточных базисах B&v,- и Б& v- произведение двух n-разрядных целых чисел, заданных в двоичной системе счисления, может быть вычислено клеточной схемой с глубиной Q(logn) и площадью 0(n2logn). Доказательство. Напомним, что (п, &)-преобразователем мы называли всякую схему (клеточную или из функциональных элементов), у которой сумма к чисел на её выходах равна сумме п чисел на её входах. Входы и выходы клеточного (п, &)-преобразователя не обязательно находятся на его границе, то есть клеточный преобразователь — не обязательно правильная клеточная схема. Клеточный (га, 2)-преобразователь был построен в лемме 3 разде ла 1.2. Для завершения доказательства теоремы осталось заметить, что произведение n-разрядных чисел х и у можно найти в три эта па. На первом этапе произведение представляется в виде суммы п штук 2га-разрядных чисел, как в алгоритме умножения «в столбик» (рис. 15). Полученная схема имеет размеры 0(п) х 0(п) и единич ную глубину. Места недостающих разрядов заполняются нулями, и на следующем этапе к ней применяется (га, 2)-преобразование, опи санное в лемме 3. На завершающем этапе надо сложить два получен ных числа, сумма которых равна произведению ху. Как и в доказа тельстве леммы 2, соединим выходы (п, 2)-преобразователя горизон тальными коммутационными элементами с его правой вертикальной стороной, и он станет полноценной клеточной схемой.

Клеточные схемы для деления

Напомним, что под задачей деления понимается нахождение неполного частного х от деления гг-разрядных целых чисел у и z: х = \_z/y\! У Ф О- В разделе 2.2 было показано, что для произвольного є О существует правильная клеточная схема Sn(e), решающая задачу деления, с глубиной 0(1/е2 logn) и площадью 0(п2+) (следствие теоремы 5). В этом разделе будет доказана нижняя оценка П(п2) для площади произвольной схемы деления. Таким образом, площадь схемы Sn{e) почти оптимальна. Обозначим через A&v{n) минимальное число клеточных элементов, достаточное для вычисления неполного частного двух п-разряд-ных чисел. Теорема 10. Aiiv(n) = Є(п2). Доказательство. Нижняя оценка. Воспользуемся методом рассечения, предложенным Н. А. ШкаликовоЙ [30] и получившим дальнейшее развитие в работе [48]. Рассмотрим произвольную правильную схему S, решающую задачу деления n-разрядных чисел у и z. Разряды чисел у и z являются входами, разряды числа х — \_zfy\ — выходами, и потому расположены по краям схемы. Будем рассматривать только такие значения входов, при которых ху — z. Пусть у — 2d, cf=0,l,...,n— 1. Тогда частное х будет результатом сдвига на d разрядов вправо разрядов делимого z. Будем рассматривать только 2т — 1 младших разрядов числа гит младших разрядов числа х. Параметр т можно выбрать так, что т = [п/2\. Очевидно, что в схеме S найдётся сторона а, содержащая по крайней мере разрядов числа х. Также ясно, что найдётся отрезок Ъ, перпендикулярный стороне а и рассекающий схему S на подсхемы Si и 5г так, чтобы каждая подсхема имела не менее Щ из т рассматриваемых разрядов числа х. Без ограничения общности можно считать, что подсхема 52 содержит по крайней мере т — 1 разрядов числа z. Пусть А и В — такие подмножества натурального ряда, что А С {0,1,..., m - 1}, В С {0,1,..., 2т - 2} и \В\ = т - 1. Обозначим через Ma число таких пар (г, j), что і Є A, j Є В и і + d = j. Можно показать, что каковы бы ни были множества А и В, найдётся такое целое d, О d т - 1, что Мд {\А\ — 1)2/(8т) [29, лемма 1]. Это означает, что если А — множество номеров произвольно выбранных разрядов числа х из подсхемы Si, В — множество номеров произвольно выбранных т—1 разрядов числа z из подсхемы Si и к тому же у = 2d, то среди выходов с номерами из множества А найдётся Мл (j — l)2/(8m) р — 1 выходов, на которые при сдвиге передаётся поднабор, поданный на М входов с номерами из множества В. Рассмотрим теперь 2Ы& различных входных наборов подсхемы 5ь отличающихся только этими разрядами. Все остальные входы положим равными нулю, и пусть у = 2d, Очевидно, что наборы, появляющиеся на выходах подсхемы 52, также будут различны. Различные выходные наборы могут получиться только при различных входных, следовательно, отрезок Ь содержит не менее log2 2Md входов подсхемы 5 2, и поэтому его длина равна по крайней мере Md — Q(n). Следовательно, площадь всей схемы S, равная произведению длин отрезков а и Ъ, по порядку не меньше п2.

Верхняя оценка. Схема минимальной по порядку площади легко строится с использованием известного алгоритма деления «в стол бик». Вычисление частного z/y = z 1/у сводится к нахождению об ратной к у величины. «Школьный» метод даёт разряды двоичного приближения к 1/у пошагово, один за другим. На каждом шаге вы полняется сравнение очередного делимого с делителем и, в зависимо сти от результата, вычитание. Нетрудно убедиться, что вычисления одного шага можно выполнить клеточной схемой, площадь и глуби на которой по порядку равны п. Число шагов не превосходит 0{п), и мы получим искомую схему площади 0(п2). На этой схеме дости гается нижняя оценка площади, однако её глубина, совпадающая по порядку с площадью, очевидно, далека от минимально возможной. Теорема 10 доказана. Прямоугольник, составленный из клеточных элементов, будем называть клеточной схемой в том и только том случае, когда при замене клеточных функциональных элементов на соответствующие им обычные функциональные и при их соединении, определяемом коммутационными элементами, получается некоторая структура, удовлетворяющая обычному определению СФЭ. Так всякой клеточной схеме S единственным с точностью до изоморфизма образом соответствует некоторая схема из функциональных элементов Sr. Схема S реализует тот же оператор, что и схема S". В терминологии работы [10] схема S является 2-вложением схемы 3 . Важный параметр схемы — время её работы (задержка). Обычно оно оценивается глубиной, хотя задержка схемы может быть много меньше глубины [26]. Глубину клеточной схемы определим так. Цепью в клеточной схеме назовём всякую последовательность клеточных элементов, в которой выход каждого элемента, кроме последнего, соединён с входом следующего. Длиной цепи будем называть число содержащихся в ней клеточных элементов, глубиной — число содержащихся в ней функциональных элементов. Цепь наибольшей глубины среди цепей, соединяющих входы и выходы схемы, назовём максимальной. Глубиной клеточной схемы назовём глубину её максимальной цепи. Глубину схемы S будем обозначать d(S). По нашему определению, глубина клеточной схемы равна глубине соответствующей ей схемы из функциональных элементов. Цепь из коммутационных элементов назовём проводником. Отметим, что всякий проводник имеет нулевую глубину. Если в цепи 7 все элементы лежат на одной горизонтальной (вертикальной) прямой, то 7 будем называть горизонтальной {вертикальной) цепью. Клеточную схему назовём повторяющей, если напротив каждого её входа х на противоположной границе симметрично расположен выход г/, на котором реализуется тождественная функция у(х) = х. Рассмотрим элемент X, изображённый на рис. 2 в центре нижнего ряда. Назовём горизонтальными элементами X и элемент, полученный из него поворотом на угол 7г.

Полученные поворотами X на углы и Щ- коммутационные элементы будем называть вертикальными элементами. Изображённый на рис. 2 вторым справа в нижнем ряду коммутационный элемент будем называть разветви-телем, крайним справа — мостом, вторым справа в верхнем ряду — элементом типа Y, крайним справа — элементом типа Z. Основное различие двоичных базисов Б = Sz,v, ,h,-Jm и Б = Biw-/ f — это наличие в Б элементов типа Y. Наличие трёх лишних коммутационных элементов (рис. 2, нижний ряд) несущественно: если в схеме 5 в базисе Б нет элементов типа У, то заменой всех коммутационных элементов разветвителями из неё можно получить некоторую схему S в базисе Б, глубина и площадь кото- рой совпадают с глубиной и площадью схемы 5 . Элемент типа Y в базисе Б можно смоделировать схемой размера 2x3, использовав один элемент типа Z. Значит, для произвольной схемы S в базисе Б найдётся схема S в базисе Б, вычисляющая тот же оператор, такая, что d(S) = d(S ) и A(S) = QA(S ). Таким образом, порядок площади функций в базисах Б и Б одинаков. Использование базиса Б вместо Б оправдано тем, что во многих случаях конструкция схем в нём оказывается прозрачней, чем в Б. В дальнейшем мы часто будем собирать схемы из подсхем. Клеточную схему S, состоящую из частей клеточных схем Si,..., Sm назовём композицией схем Si,..., Sm. Приведём пример, поясняющий это определение. Пусть даны схемы S, S и пусть в схеме S каким-либо образом выбраны горизонтальный и вертикальный отрезки а и (3. Они делят схему S на четыре прямоугольника — подсхемы А, В, С, D (см. рис. 3, а). Раздвинем части А, В, С и D на такое расстояние, чтобы между ними поместилась схема S (рис. 3, Ь). Лежащие на границах схем А, В, С, D клеточные элементы соединяются друг с другом коммутационными элементами по тем же правилам, что и в схеме 5. Так, например, вертикальные проводники соединяют те элементы подсхем Л и С, которые были смежными в схеме S. В зависимости от задачи на входы схемы S могут подаваться как пограничные выходы подсхем Л, І?, С, J , так и выходы внутренних клеточных элементов. На рис. З, Ь изображён пример соединения одного из входов схемы 5 и внутренней вершины х подсхемы А.

Похожие диссертации на О глубине и площади клеточных схем

О реализации некоторых операций в конечных полях схемами логарифмической глубиныСергеев Игорь Сергеевич

Оптимизация структуры посевных площадей и схемы полевых севооборотов на светло-каштановых почвах Волго-Донского междуречьяХолод Анатолий Александрович

Обоснование схем многоштрековой подготовки выемочных участков газоносных угольных пластов на больших глубинахКазанин Олег Иванович