О глубине и площади клеточных схем тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М. В. ЛОМОНОСОВА Механико-математический факультет

На правах рукописи УДК 519.7

Жуков Дмитрий Александрович

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

Специальность 01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

Москва — 2004

Работа выполнена на кафедре дискретной математики механико-математического факультета Московского государственного университета им. М. В. Ломоносова.

Научныйруководитель: доктор физико-математических наук,

профессор А. В. Чашкин

Официальные оппоненты: доктор физико-математических наук,

профессор В. М. Сидельников

кандидат физико-математических наук Н. А. Карпова

Ведущая организация: Московский педагогический

государственный университет

Защита состоится 5 ноября 2004 г. в 16 час. 15 мин. на заседании диссертационного совета Д.501.001.84 в Московском государственном университете им. М. В. Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан 5 октября 2004 г.

Учёный секретарь диссертационного совета Д.501.001.84 в МГУ, доктор физико-математических наук, профессор

В. Н. Чубариков

Общая характеристика работы

Актуальность темы. С ростом возможностей реализации всё более сложных вычислительных структур растёт интерес и к изучению таких мер сложности, которые учитывают их пространственные параметры, особенно размеры и расположение элементов и каналов связи. Один из возможных способов формализации этой задачи — клеточные схемы (схемы из клеточных элементов), рассмотренные С. С. Кравцовым1. В его работе были построены клеточные схемы для всюду определённых булевых функций и было показано, что их площадь минимальна по порядку для почти всех функций. Затем изучение клеточных схем было продолжено другими авторами. А. Альбрехт2 установил, что функция Шеннона для площади клеточных схем, вычисляющих функции п аргументов, при имеет асимптотику, где а — некоторая постоянная, точное значение которой пока остаётся неизвестным. При п, равном степени двух, точную величину функции Шеннона в близкой клеточным схемам модели нашёл Н. П. Редькин3). В цикле работ Н. А. Шкаликовой4) найдены точные по порядку оценки площади, необходимой и достаточной для реализации клеточными схемами всех булевых функций п переменных, всех элементарных конъюнкций п переменных, операторов сложения и умножения, самой сложной симметрической функции, некоторых универсальных множеств функций.

Сложность вычисления частичных булевых функций и частичных

г) Кравцов С. С. О реализации функций алгебры логики в одном классе схем из функциональных и коммутационных элементов // Проблемы кибернетики. Вып. 19. М.: Наука, 1967. С. 285-293.

2) Альбрехт А. О схемах из клеточных элементов // Проблемы кибернетики. Вып. 33. М.: Наука, 1977. С. 209-214.

3) Редъкин Н. П. Однородные структуры из двухканальных элементов // Автоматика и телемеханика, 4. М., 1972. С. 84-89.

4) Шпаликова Н.А.О сложности реализации некоторых функций клеточными схемами // Сборник работ по математической кибернетике. Вып. 1. М-, 1976. С. 102-115; Шпаликова Н. А. О соотношении сложностей плоских и объёмных схем из функциональных элементов // Методы дискретного анализа в оценках сложности управляющих систем. Вып. 38. Новосибирск, 1982. С. 87-107; Шпаликова Н. А. О сложности реализации универсальных булевских функций схемами из клеточных элементов // Вести. Моск. ун-та. Сер. 15. Вычислительная математика и кибернетика. 1987. ДО4. С. 50-54; Шпаликова Н. А. О реализации булевых функций схемами из клеточных элементов // Математические вопросы кибернетики. Вып. 2. М.: Наука, 1989. С. 177197.

РОС. НАЦИОНАЛЬНАЯ 1 еиБлиотекА

функций данного веса схемами из функциональных элементов изучалась в большом числе работ, среди которых отметим результаты Л. А. Шоло-мова5), А. Е. Андреева6 и П. Б. Милтерсена7). В итоге этих исследований было найдено асимптотически точное поведение функции Шеннона для множества всех частичных функций данного веса, определённых на областях данного размера. В работе А. В. Чашкина8) предложен метод построения схем из функциональных элементов для частичных функций данного веса, позволяющий сделать их сложность и глубину одновременно минимальными по порядку, а глубину — и асимптотически минимальной при более чем полиномиальных размерах областей определения функций.

Особый интерес в силу своего прикладного характера вызывает реализация арифметических операций в различных моделях вычислений. Обзор многочисленных результатов в этой области можно найти в монографиях С. Акля9), А. Ахо, Дж. Хопкрофта и Дж. Ульмана10), И. Вегене-рап), Дж. Сэвиджа12) и многих других. Отметим, что для всех основных арифметических операций достаточно давно известны схемы из функциональных элементов логарифмической глубины и линейной (сложение, вычитание) либо близкой к линейной (умножение, деление) сложности135.

3) Шоломов Л. А. О функционалах, характеризующих сложность систем недоопре-делённых булевых функций // Проблемы кибернетики. Вып. 19. М.: Наука, 1967. С. 123-140; Шоломов Л. А. О реализации недоопределённых булевых функций схемами из функциональных элементов // Проблемы кибернетики. Вып. 21. М.: Наука, 1969. С. 215-226.

в) Андреев А. Е. О сложности реализации частичных булевых функций схемами из функциональных элементов // Дискретная математика. Т. 1, вып. 4,1989. С. 36-45.

7) Miltersen P. В. On the Shannon Function for Partially Defined Boolean Functions // ICALP Satellite Workshops 2000. P. 253-258, http://www.brics.dk /~bromille/Papers/shannon6.ps

8) Чашкин А. В. Об одном методе вычисления частичных булевых функций // Математические вопросы кибернетики. Вып. 12. М.: Физматгиз, 2003. С. 231-246.

9> АН S. G. Parallel computation: models and methods. Prentice-Hall, 1997. l0) Aho A., Hopcroft J., Ullman J. The design and analysis of computer algorithms. Ad-dison-Wesley, Reading, Massachusets, 1974. ") Wegener I. The complexity of Boolean functions. Stuttgart, 1987.

12) Savage J. E. The Complexity of Computing. John Wiley and Sons, 1976; Kreiger Publishing Company, 1987.

13) Храпченко В. М. Об асимптотической оценке времени сложения параллельного сумматора // Проблемы кибернетики. Вып. 19. М.: Наука, 1967. С. 107-122; Шенха-ге А., Штрассен В. Быстрое умножение больших чисел // Кибернетический сборник. Вып. 10. М.: Мир, 1973. С. 87-98; ShankarN., Ramachandran V. Effficient parallel circuits and algorithms for division // Information Processing Letters, Vol. 29, 1988. P. 307-313.

При этом до сих пор не получены нелинейные нижние оценки сложности умножения и деления, и оптимальность найденных схем остаётся недоказанной.

Реализация арифметических операций клеточными схемами изучена меньше. Здесь основные результаты принадлежат Н. А. Шкаликовой14), доказавшей, что площадь, необходимая и достаточная для реализации операторов сложения и умножения двух n-разрядных чисел клеточной схемой, равна по порядку п и п2 соответственно.

Обзор методов доказательства нижних оценок в родственных клеточным схемам моделях можно найти в книге Дж. Ульмана15). Для специально подобранных функций рекордные квадратичные нижние оценки площади удаётся получать через коммуникативную сложность16. Р. Брент и X. Кунг17) доказали нелинейную нижнюю оценку для суммы длин рёбер укладки полного двоичного дерева в произвольную плоскую выпуклую область. С. А. Ложкин и Ли Да Мин18) установили асимптотику площади вложения полного двоичного (троичного) дерева в плоскую прямоугольную решётку. Эти результаты позволяют получать нижние оценки площади клеточных схем, обладающих полными поддеревьями, однако для деревьев общего вида подобных нижних оценок до настоящего времени известно не было.

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

и> Шпаликова Н. A. Op. cit.

15> Ullman J. D. Computational aspects of VLSI. Computer Science Press, Rockville, Maryland, 1984.

16) Hromkovich J., Lozhkin S. A., Rybko A. I., Sapozhenko A. A., Shkalikova N. A. Lower bounds on the area complexity of Boolean circuits // Theoretical Computer Science. Vol. 97, № 2, 1992. P. 285-300.

17) Brent R. P., Kung H. T. On the area of binary tree layouts // Information Processing Letters. Vol. 11, №1,1980. P. 46-48.

18 Ложкин С. А., Ли Да Мин. О некоторых оптимальных вложениях двоичных и троичных деревьев в плоские прямоугольные решётки // Вестн. Моск. ун-та. Сер. 15. Вычислительная математика и кибернетика. 1995. №4. С. 49-55.

Целью работы является построение клеточных схем с минимальными по порядку параметрами для частичных функций и арифметических операций.

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

Научная новизна. Все основные результаты диссертации являются новыми и состоят в следующем:

- для почти всех всюду определённых, частичных и частичных с данным весом булевых функций построены реализующие их клеточные схемы, площадь и глубина которых неулучшаемы по порядку;

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

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

Приложения. Работа носит теоретический характер. Её результаты могут быть использованы в ходе дальнейшего изучения плоских схем. Результаты диссертации могут быть полезны специалистам Московского государственного университета им. М. В. Ломоносова, Института прикладной математики им. М. В. Келдыша РАН, Вычислительного центра им. А. А. Дородницына РАН, Института математики им. С. Л. Соболева СО РАН, Нижегородского государственного университета им. М. В. Лобачевского, Новосибирского государственного университета, Санкт-Петер -бургского государственного университета.

Апробация работы. Результаты диссертации неоднократно докладывались на семинарах механико-математического факультета МГУ под руководством академика РАН О. Б. Лупанова «Математические вопросы кибернетики» и «Синтез управляющих систем» (2001, 2003, 2004 гг.), на

четвёртой (18-23 сентября 2000 г.) и пятой (12-17 ноября 2001 г.) молодёжных научных школах по дискретной математике и её приложениям (Москва, механико-математический факультет МГУ), на XIII Международной конференции «Проблемы теоретической кибернетики» в Казани (2002 г.), XIV Международной школе-семинаре «Синтез и сложность управляющих систем» в Нижнем Новгороде (2003 г.), VIII Международном семинаре «Дискретная математика и её приложения» в Москве (2004 г.).

Публикации. Полный список работ автора по теме диссертации приведён в конце автореферата [1 - 8].

Структура работы. Диссертация состоит из введения, трёх глав и списка литературы, содержащего 67 наименований. Общий объём диссертации — 77 страниц.

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

Во введении дан краткий обзор работ, связанных с темой диссертации, приведены основные определения и сформулированы результаты. В работе приняты следующие термины и обозначения: частичная булева функция, определённая на наборах из множества D С {0,1 }n, A(S) — площадь клеточной схемы 5, d(S) — глубина как клеточной схемы, так и схемы из функциональных элементов, (п,т)-преобразованием19 названо получение из п слагаемых т чисел с той же суммой, (п,т) -преобразователем — всякая схема (клеточная или из функциональных элементов), осуществляющая (п,т)-преобразование; при этом считается, что входы и выходы клеточного (п,т)-преобразователя не обязательно находятся на его границе. Весом частичной булевой функции называется число наборов в её области определения, на которых значение функции равно единице.

Результаты главы 1 носят вспомогательный характер и использованы далее в главе 3. Ниже приведены только наиболее важные из них.

В разделе 1.1 доказан ряд утверждений о реализации (п, 2)-пре-образований схемами из fc-ичных функциональных элементов. В булевом случае базиса из двоичных элементов наилучшая известная глубина (п, 2)-преобразователя составляет асимптотически 3,48 1og2n20). Следую-

19 Храпченко В. М. Некоторые оценки для времени умножения // Проблемы кибернетики. Вып. 33. М.: Наука, 1978. С. 221-227.

PatersonM.S., PippengerN., ZwickU. Optimal carry save networks // Boolean function complexity. Cambridge: Cambridge Univ. Press, 1992. P. 174-201. (London Mathematical Society Lecture Note Series 169); Paterson M. S., Zwick U. Shallow circuits and concise formulae for multiple addition and multiplication // Computational

щее утверждение показывает, что при использовании ¿-ичных элементов она может быть ещё уменьшена.

Теорема 1. Пусть к = 2г+1, г ^ 1. Тогда в базисе {®, &} существует (п, 2)-преобразователь Sk,n N-разрядных к-ичных чисел с глубиной

d(Sk^ < 1 iL Jog2n- (1 + 0(1)),

1 - log2 a

где a — наибольший из модулей корней многочлена xr+1 — zr — 1,

о-«. .*»-{£

Отсюда, в частности, следует, что е?(«!?з,п) < 3,271og2n и d(Sg,n) < l,87Iog2n. При условии, что га < 2°^, сложность схемы Sk,n по порядку равна nN.

В разделе 1.2 построен двоичный клеточный (п, 2)-преобразователь.

Лемма 3. При N = 0(п) в базисе двоичных клеточных элементов существует клеточный (п, 2)-преобразователь N-разрядных слагаемых с глубиной O(logn) и площадью 0(n2logn).

В главе 2 рассмотрены общие вопросы соотношения площади и глубины клеточных схем. Глава состоит из трёх разделов.

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

Теорема 2. Для всякой всюду определённой п-местной булевой функции f существует реализующая её клеточная схема S/ с параметрами A{Sj) < 9 • 2П + о(2") и d(Sf) < 2n + 1.

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

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

Complexity, 3,1993. P. 262-291.

Из теоремы 3 можно получить аналогичное утверждение о частичных функциях данного веса w, определённых на m-элементных областях, и его следствие для полностью определённых функций.

Теорема 4. Пусть D С {0,1}п, |D| = m, w = iî(n2) иш ^ Тогда для каждой частичной п-местной булевой функции fo веса w, определённой на области D, можно построить такую клеточную схему S) , реализующую функцию fD, что A(S}D) = 0(ttflog^) u d(S}D) = dflogiu + loglog*).

Следствие теоремы 4. Пусть w — fi(n2) и w ^ 2n_l. Тогда для каждой всюду определённой п-местной булевой функции f веса w можно построить клеточную схему S'j, реализующую функцию f, с параметрами A(S'f) = О (log (2J)) и d(S'f) = О (log log Q).

Отметим, что площадь и глубина схем Sf, SfD, SjD и S'j из теорем 2-4 и следствия теоремы 4 неулучшаемы по порядку для почти всех функций, что легко следует из мощностных соображений.

Раздел 2.2 посвящён моделированию схем из функциональных элементов клеточными схемами.

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

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

Следствие теоремы 5. Для всякого положительного е существует клеточная схема глубины С7(1/е2 • log тг) и площади 0(п2+е), решающая задачу деления для двух п-разрядных чисел.

В разделе 2.3 рассмотрен класс клеточных схем, для которого удалось связать нижнюю оценку площади с глубиной. В начале раздела напоминаются необходимые определения из теории графов и дано определение вложения, образом которого является клеточная схема (2-вложение1^). Затем Т-вложением орграфа G названо такое его 2-вложение / в

21) Ложкин С. А., Ли Да Мин. Op. cit.

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

Основным утверждением раздела 2.3 является лемма 9.

Лемма 9. Пусть D — произвольное ориентированное к корню двоичное дерево глубины den листьями. Тогда площадь решётки, в которую возможно Т-вложение дерева D, равна Q •

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

Теорема 6. Если Т-схема глубины d реализует существенно зависящую от п аргументов функцию, то её площадь должна быть по порядку не меньше, чем (n log га)/log

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

Таким образом, теорема 6 и её следствие связывают параметры Т-схемы следующим образом: если у схемы небольшая глубина, то у неё должна быть сравнительно большая площадь.

Глава 3 посвящена реализации основных арифметических операций клеточными схемами. Клеточная схема Sen входами xi,x2,.. .,хп и п выходами У1,У2,---,Уп названа префиксной, если она вычисляет префиксные суммы22' входных значений относительно ассоциативной операции то есть yk = xi ® ... ® Xk при всех к, 1 ^ к ^ п (при построении схемы S используются клеточные элементы, реализующие операцию В разделе 3.1 построены префиксные схемы логарифмической глубины.

Теорема 7. Для всякого натурального числа п существует префиксная Т-схема Рп, такая, что d(Pn) = ¡"log п] и А(Рп) < 4n flogn].

С привлечением теоремы 6 отсюда можно сделать вывод, что площадь схемы Рп минимальна по порядку среди всех префиксных Т-схем глубины G(logn), или, иначе говоря, минимизировать оба её параметра одновременно невозможно.

и> Ladner R. Е., Fischer М. J. Parallel prefix computation // Journal of the ACM. Vol. 27, 1980. P. 831-838.

Далее в разделах 3.2 — 3.4 доказаны следующие утверждения.

Теорема 8. При к ^ 3 существует такой k-ичный п-разрядный клеточный СуММйТТЬОр ¿¿и, являющийся Т-схемой, что d{£„) ^ [log2(n + 1)1+2 и A(Sn) < 6n(|"log2(n +1)1 + 2).

Из данной теоремы далее получены схемы для вычитания fc-ичных чисел и двоичный сумматор логарифмической глубины.

Следствие 1 теоремы 8. Существует двоичный п-разрядный клеточный сумматор глубины 21og2n + 0(1) и площади O(nlogn).

Следствие 2 теоремы 8. При k ^ 3 существует клеточная к-ичная Т-схема Еп, находящая разность п-разрядных чисел X и Y при условии X ^ Y, для глубины которой справедливо равенство d(£n) = log2n + 0(1). В базисе из двоичных клеточных элементов существует схема вычитания глубины 2 log2n + 0( 1). Площади этих схем равны O(nlogn).

Учитывая теорему 6, можно убедиться, что площади схем из теоремы 8 и её следствий минимальны по порядку среди всех Т-схем глубины О (log п). Следствия теоремы 8 вместе с леммой 3 из главы 1 позволяют получить схему логарифмической глубины и для умножения, причём её площадь отличается от нижней оценки ii(n2) лишь на множитель log п.

Теорема 9. Произведение двух п-разрядных целых чисел может быть вычислено клеточной схемой с глубиной C?(logn) и площадью 0(п2 log тг).

Наконец, в последней теореме главы 3 — теореме 10 — показано, что всякая клеточная схема, которая вычисляет неполное частное при делении двух двоичных п-разрядных чисел, имеет площадь по порядку не менее чем п2, и приведена схема площади 0(п2) для этой задачи. Заметим, что её глубина намного больше глубины схемы из следствия теоремы 5.

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

Автор выражает искреннюю благодарность своему научному руководителю — профессору Александру Викторовичу Чашкину — за постановку задачи, многочисленные полезные обсуждения и всемерную поддержку на всех этапах данной работы.

Работы автора по теме диссертации

1. Жуков Д. А. О вычислении частичных булевых функций клеточными схемами // Дискретный анализ и исследование операций. Сер. 1. Т. 11, №2, 2004. С. 3 2 0.

2. Жуков Д. А. Быстрые клеточные схемы для умножения // Дискретный анализ и исследование операций. Сер. 1. Т. 9, №3, 2002. С. 40-47.

3. Жуков Д. А. О времени параллельного сложения нескольких чисел // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2001. №6. С. 52-54.

4. Жуков Д. А. Об одном классе клеточных схем // Материалы XIV Международной школы-семинара «Синтез и сложность управляющих систем» (Нижний Новгород, 27 октября - 1 ноября 2003 г.). — Нижний Новгород: Изд-во НГПУ, 2003. С. 33-37.

5. Жуков Д. А. О вычислении частичных булевых функций клеточными схемами // Материалы VIII Международного семинара «Дискретная математика и её приложения» (Москва, 2-6 февраля 2004 г.). - М.: Изд-во мех.-мат. фак. МГУ, 2004. С. 63-66.

6. Жуков Д. А. Клеточные схемы для умножения // Проблемы теоретической кибернетики. Тезисы докладов XIII Международной конференции (Казань, 27-31 мая 2002 г.). Часть I. — М.: Изд-во Центра прикладных исследований при механико-математическом факультете МГУ, 2002. С. 64.

7. Жуков Д. А. Клеточные схемы для арифметических операций // Материалы пятой молодёжной научной школы по дискретной математике и её приложениям (МГУ, ноябрь 2001). — М.: Изд-во мех.-мат. фак. МГУ, 2002. С. 50-52.

8. Жуков Д. А. О времени параллельного сложения нескольких чисел // Материалы четвёртой молодёжной научной школы по дискретной математике и её приложениям (МГУ, ноябрь 2000). М.: Изд-во мех.-мат. фак. МГУ, 2000. С. 39-47.

Издательство ЦПИ при механико-математическом факультете МГУ им М В. Ломоносова

Подписано в печать 23 09 04

Формат 60 х 90 1 /16 . Уел печ л 0,75

Тираж 100 экз Эаказ30

Лицензия на издательскую деятельность ИД В 04059, от20 02 2001г

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета и Франко-русского центра им. А.М Ляпунова

^24 0 44

Введение

Глава 1 к-нчшле (п, 2)-преобразователи.

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

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

Глава 2 Оценки общего типа.

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

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

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

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

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

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

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

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

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

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

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

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

Формальное определе-У ние схем из клеточных

-Ц элементов было дано в у-Г работе [9]. Затем кле-у точные схемы были рассмотрены в [1, 29, 30]. Клеточная схема имеет | вид прямоугольника на плоскости, составленного из клеточных элементов. Мы будем называть схему правильной, если все её входы и выходы расположены по краям. Везде далее клеточные схемы предполагаются правильными. Будем считать, что длина клеточной схемы измеряется по горизонтали, а ширина — по вертикали. Длину схемы 5 обозначим ¿(5), а ширину — /г(5). Тогда площадь Л(5") схемы в равна произведению 1(Б) х /г(5).

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

У х х ху X хУу х

V "Г У

-*-х\/у и выходы — не более одного на каждой стороне. Клеточный элемент называется функциональным, если он реализует нетождественную функцию, и коммутационным, если он реализует тождественные функции. Кроме функциональных и коммутационных элементов имеется изолирующий клеточный элемент без входов и выходов. В работах [1, 9, 29, 30] исследовались схемы, построенные из двоичных клеточных элементов в базисе } (рис. 1). Будем обозначать этот базис Б^у,- . В последней главе будут также рассмотрены клеточные схемы, реализующие функции Аьзначной логики. Используемые при их построении &-ичные элементы изображены на рис. 2. В верхнем ряду приведены изолирующий элемент и четыре функциональных элемента (реализующие константу с, одноместную функцию д 6 Рк и двуместную функцию / € Рд;). В нижнем ряду изображены коммутационные элементы. Будем обозначать этот базис Б*. При построении схемы допускаются повороты клеточных элементов на углы, кратные |. Чтобы подчеркнуть, что в базис Б* входят элементы, реализующие функции /1,., /т, будем писать Бд).>/то- Базис Б^у,-, дополненный функциональными элементами со входами на соседних сторонах (рис. 2, справа в верхнем ряду), реализующими функции двух переменных /ь ., /т из Р2, обозначим Б&ЛЛ-/1 ,.,/»•

9(х)

Цх,у) 1(х,у) с - X — 9 -д(х) ж- / -У / я, у) $0*0 я, у) у х X X X X X X X X X

Рис. 2

Прямоугольник, составленный из клеточных элементов, будем называть клеточной схемой в том и только том случае, когда при замене клеточных функциональных элементов на соответствующие им обычные функциональные и при их соединении, определяемом коммутационными элементами, получается некоторая структура, удовлетворяющая обычному определению СФЭ. Так всякой клеточной схеме ¿> единственным с точностью до изоморфизма образом соответствует некоторая схема из функциональных элементов Схема 5 реализует тот же оператор, что и схема Б'. В терминологии работы [10] схема 5 является 2-вложением схемы 5'.

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

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

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

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

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

А а В /з

С В а)

Рис. 3

5"

Ь) рой совпадают с глубиной и площадью схемы 3*. Элемент типа У в базисе Б можно смоделировать схемой размера 2x3, использовав один элемент типа Z. Значит, для произвольной схемы 3* в базисе Б* найдётся схема 5 в базисе Б, вычисляющая тот же оператор, такая, что ¿(Б) = «¿(5*) и А(Б) ^ 6^4(5*). Таким образом, порядок площади функций в базисах Б и Б* одинаков. Использование базиса Б* вместо Б оправдано тем, что во многих случаях конструкция схем в нём оказывается прозрачней, чем в Б.

В дальнейшем мы часто будем собирать схемы из подсхем. Клеточную схему 5, состоящую из частей клеточных схем ., 5т назовём композицией схем 51,., Зт. Приведём пример, поясняющий это определение. Пусть даны схемы 3, 5" и пусть в схеме 3 каким-либо образом выбраны горизонтальный и вертикальный отрезки а и /3. Они делят схему 3 на четыре прямоугольника — подсхемы А, В, С, И (см. рис. 3, о). Раздвинем части А, В, С и I) на такое расстояние, чтобы между ними поместилась схема 3' (рис. 3, 6). Лежащие на границах схем А, В, С, В клеточные элементы соединяются друг с другом коммутационными элементами по тем же правилам, что и в схеме 3. Так, например, вертикальные проводники соединяют те элементы подсхем А и С, которые были смежными в схеме 3. В зависимости от задачи на входы схемы 3/ могут подаваться как пограничные выходы подсхем А, В, С, И, так и выходы внутренних клеточных элементов. На рис. 3, Ь изображён пример соединения одного из входов схемы и внутренней вершины х подсхемы А. При этом должно выполняться условие: в схеме на вертикальном участке от точки х до точки а находятся только горизонтальные коммутационные элементы либо изолирующие, а на отрезке аЬ находятся только вертикальные или изолирующие элементы. Заменим мостом каждый элемент, лежащий на пунктирной линии xah, при необходимости поворачивая его. Тогда последовательность элементов, лежащих на линии xab, станет проводником, не нарушающим других цепей в подсхеме А.

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

В работе используются обозначения о, (9, Q и ©: /(п) = о(д(п)), если limn->oo f{n)/g{n) = 0; /(п) = 0(д(п)), если найдутся константа с > 0 и число по, такие, что для всех n ^ щ справедливо неравенство 0 ^ f(n) ^ сд(п); /(п) = Г2(р(п)), если и только если g(n) = G(f(n)); f(n) = в(д(п)), если и только если /(п) = 0(д(п)) и /(n) = fi(g(n)). Логарифмы далее берутся по основанию 2. Все дальнейшие определения и обозначения будем вводить в тексте по мере необходимости.

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

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

Сложность вычисления частичных булевых функций и частичных булевых функций данного веса схемами из функциональных элементов изучалась в большом числе работ, в том числе [2, 31, 33, 53]. В результате было найдено асимптотически точное равенство Ь(п, ?тг, т) ~ 1о§2 (")/ (™) +0(п) для сложностной функции

Шеннона Ь(п,т, т) множества всех частичных п-местных булевых функций /, определённых на т-элементных областях и имеющих вес IV. Это равенство справедливо для всех значений т пк^2п и всех таких ги, что ш ^ глубина схем при этом не рассматривалась. Кроме того, в [33] предложен метод синтеза, позволяющий для почти всех частичных функций / веса -ш получать схемы, глубина и сложность которых одновременно оптимальны по порядку. Сложность этих схем не превышает 4Ь(п, т, ю), глубина не превышает Ь(п, т, ии) + п ~ ии + log2 5 + 1оё2 п-ив случае, когда т растёт сверхполиномиально с ростом п, является асимптотически минимальной.

Большое внимание в литературе уделено и схемам с ограничениями, наложенными на некоторые их характеристики. Так, например, получены оценки сложности схем, имеющих ограниченное ветвление [15]. Возник интерес и к пространственным параметрам схем. Первыми существенными результатами в этой области являются работа А. Д. Коршунова [8], где рассмотрена задача синтеза схем из функциональных элементов при некоторых ограничениях на длину соединительных проводников, и работа С. С. Кравцова [9], где вводятся схемы из клеточных элементов. С. С. Кравцов показал, что для любой булевой функции п аргументов можно построить реализующую её клеточную схему площади < | ■ 2П, и что для почти всех функций п аргументов площадь их реализации клеточными схемами не менее | • 2п. Позднее А. Альбрехт [1] установил, что функция Шеннона А(п) = тах/ тт^ где максимум берётся по всем функциям / от п переменных, а минимум — по всем вычисляющим / клеточным схемам 5, имеет асимптотику А(п) а • 2П, где константа и удовлетворяет неравенству | ^ а ^ |. Точное значение <т остаётся неизвестным. В близкой клеточным схемам модели точную величину функции Шеннона при п, равном степени двух, нашёл Н. П. Редькин [21]. Н. А. Шкаликова [30] показала, что площадь универсального клеточного многополюсника, реализующего все булевы функции п переменных, равна 0(п22") и неулучшаема по порядку. Глубина клеточных схем ранее не рассматривалась; у построенной методом Кравцова схемы она оказывается экспоненциальной. Ранее в литературе не рассматривалась также и реализация клеточными схемами частичных функций.

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

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

В конце 70-х — начале 80-х годов была осознана общность ряда распространённых задач: построение сумматоров, поиск в базах данных, организация вычислений в синхронных и асинхронных параллельных моделях, и др. Результатом стало понятие префикса последовательности {хг}"=1 элементов Х{ из некоторой полугруппы М с операцией ® и рассмотрение вычисления всех префиксных сумм этой последовательности как отдельной базовой задачи [49]. Мы будем называть префиксной схему, вычисляющую префиксные суммы входов и построенную из функциональных элеменtob <g>. От операции <g> требуется лишь ассоциативность. Сведения о результатах в области префиксных вычислений можно почерпнуть, например, из монографий [37, 50]. За последние 10-15 лет в области синтеза префиксных схем достигнуты значительные успехи. В числе прочих уже известны схемы линейной по п сложности и глубины log2 n + ö(l), где п — число входов. К сожалению, на данный момент подобные публикации недоступны отечественному читателю даже в глобальной сети Internet.

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

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим плоскую область £>, у которой на границе дИ выбраны п точек х^,. ,хп с попарным расстоянием не меньше единицы. Р. Брент и X. Кунг [43] доказали, что если х\,.,хп — листья полного двоичного дерева Т, лежащего на плоскости внутри £>, а область ~ выпуклая, то сумма длин рёбер дерева Т не меньше чем £2(пк^7г). Эта теорема непосредственно переносится на прямоугольные укладки и клеточные схемы. Требование выпуклости является существенным: дерево [58] с п листьями имеет сумму длин рёбер и площадь укладки одновременно равные ©(п). Ю. Громкович и Б. Шустер [4] привели пример такой последовательности булевых функций дп = дп(х 1,.жп), что площадь реализации функции дп правильной клеточной схемой равна 0(пз), а неправильной (то есть такой схемой, у которой входы не обязательно лежат на границе) — О(п). Эти результаты показывают, что правильная и неправильная клеточные модели существенно различны.

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

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

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

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

Лемма 1. В базисе Qk существует (N,2)-преобразователь S поразрядных к-ичных чисел с глубиной d(S) К + У + iy*»(fc + i)11. log2 N+ö(log2 fc) log2(A; + 1) - 1 и сложностью L(S) = 0{Nn\ogk) при условии N = Ö(kn).

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

Теорема 1. Пусть к = 2Г + 1, г ^ 1. Тогда в базисе Qk существует (N,2) -преобразователь Skд п-разрядных к-ичных чисел с глубиной d(SKN) ^ 1 * q log2 N • (1 + о(1)), где а — наибольший из модулей корней многочлена яг+1 — хг — 1.

В частности, d(Sz,N) ^ 3,271og2iV и d{S^N) S l,871og2iV. При этом L(S^n) x L(Sq^) x niV; npw условии что N ^

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

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

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

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

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

A(Sf) < 9 • Т + о(2"), d(Sf) ^ 2п + 1.

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

Теорема 3. Пусть D С {0,1}п и |D| = Q(n2). Тогда для каждой частичной п-местной булевой функции fo, определённой в D, можно построить такую клеточную схему SfD, реализующую функцию Jd, что A(SfD) = 0(\D\) и d(SfD) = 0(log|D|). Площадь и глубина схемы SfD оптимальны по порядку для почти всех функций fD.

Теорема 4. Пусть D С {0,1}п, \D\ = т, w = uw ^ f.

Тогда для каждой частичной п-местной булевой функции fp веса w, определённой на области D, можно построить такую клеточную схему SJD, реализующую функцию fo, что тп тп

A(S}d) = Q(w log -) u d(S}D) = С?(log w + log log

Площадь и глубина схемы SJD оптимальны по порядку для почти всех функций /вСледствие теоремы 4. Пусть w = £2(п2) и w ^ 2п~1. Тогда для каждой всюду определённой п-местной булевой функции f веса w можно построить клеточную схему S'j, реализующую функцию /, с параметрами A{S'f) = <3(log(2J)) и d(S'f) = C?(loglog (2J)). Площадь и глубина схемы S'j оптимальны по порядку для почти всех функций /.

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

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

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

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

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

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

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

Лемма 9. Пусть D — произвольное двоичное дерево глубины d с п листьями. Тогда At{D) = ГЦ , п ).

V°S logn /

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

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

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

Глава 3 посвящена реализации основных арифметических операций (сложение, вычитание, умножение и деление) клеточными схемами. Назовём префиксной клеточную схему Sen входами х\, Х2,., хп и п выходами yi, y<i,. • •, уп, если схема S вычисляет префиксные суммы входных значений относительно ассоциативной операции (8), то есть у к = х\ ® •. • ® Xk при всех к, 1 ^ к ^ п (при построении S используются функциональные элементы, реализующие операцию

Теорема 7. Для всякого натурального числа п существует префиксная Т-схема Рп, для глубины и площади которой справедливы оценки d(Pn) — [logn] , А(Рп) ^ 4n [logn].

Построенная схема Рп оптимальна в следующем смысле: всякая префиксная Т-схема с п входами и глубиной O(logn) имеет площадь (nlogn) по теореме 6.

Далее в разделах 3.2 — 3.4 доказаны следующие результаты.

Теорема 8. При к ^ 3 существует к-ичный п-разрядный клеточный сумматор Еп глубины d(En) ^ [log2(n -j- 1)] -f- 2, являющийся Т-схемой. Его площадь удовлетворяет неравенству A(En) ^ 6n(|~log2(n + 1)"] -Ь 2) и минимальна по порядку в классе Т-схем логарифмической глубины.

Следствие 1 теоремы 8. Существует двоичный п-разрядный клеточный сумматор глубины 21og2n + 0(l) и площади ©(nlogn минимальной по порядку в классе Т-схем логарифмической глубины.

Следствие 2 теоремы 8. Для k ^ 3 существует клеточная k-ичная Т-схема ЕП; находящая разность п-разрядных чисел X и Y при условии X ^ Y, для глубины которой справедливо равенство d(En) = log2n + 0( 1). В базисе из всех двоичных клеточных элементов существует схема вычитания глубины 21og2n-f- 0(1). Площади этих схем равны ©(nlogn) и минимальны по порядку в классе Т-схем логарифмической глубины.

Теорема 9. Произведение двух п-разрядных целых чисел, заданных в двоичной системе счисления, может быть вычислено клеточной схемой в базисе {&,V,—, ф}, с глубиной 0(logn) и площадью 0(n2logn).

Наконец, в последней теореме главы 3 — теореме 10 — показано, что всякая правильная клеточная схема, которая вычисляет неполное частное при делении двух двоичных п-разрядных чисел, имеет площадь по порядку не менее чем п2, и приведена схема оптимальной площади 0(п2). Следует отметить, что глубина этой схемы намного больше глубины схемы из следствия теоремы 5.

Автор выражает искреннюю благодарность своему научному руководителю — профессору Александру Викторовичу Чашкину — за постановку задачи, многочисленные полезные обсуждения и всемерную поддержку на всех этапах данной работы.

1. Альбрехт А. О схемах из клеточных элементов // Проблемы кибернетики. Вып. 33. М.: Наука, 1977. С. 209-214.

2. Андреев А. Е. О сложности реализации частичных булевых функций схемами из функциональных элементов // Дискретная математика. Т. 1, вып. 4, 1989. С. 36-45.

3. Гашков С. Б. О глубине булевых функций // Проблемы кибернетики. Вып. 34. М.: Наука, 1978. С. 265-268.

4. ГромковичЮ., Шустер Б. О соотношении сложностей двух видов плоских схем из функциональных элементов // Дискретная математика. Т. 2, вып. 2, 1990. С. 121-126.

5. КарацубаА. А. Сложность вычислений // Труды МИ РАН им. В. А. Стеклова. Т. 211, 1995. С. 186-202.

6. Карацуба А. А., Офман Ю. П. Умножение многозначных чисел на автоматах // Докл. АН СССР, т. 145, №2,1962. С. 293-294.

7. Колмогоров А. Н., БарздиньЯ. М. О реализации сетей в 3-мерном пространстве // Проблемы кибернетики. Вып. 19. М.: Наука, 1967. С. 261-268.

8. Коршунов А. Д. Об оценках сложности схем из объёмных функциональных элементов и объёмных схем из функциональных элементов // Проблемы кибернетики. Вып. 19. М.: Наука, 1967. С. 275-283.

9. Кравцов С. С. О реализации функций алгебры логики в одном классе схем из функциональных и коммутационных элементов // Проблемы кибернетики. Вып. 19. М.: Наука, 1967. С. 285-293.

10. Ложкин С. А., Ли Да Мин. О некоторых оптимальных вложениях двоичных и троичных деревьев в плоские прямоугольные решётки // Вестн. Моск. ун-та. Сер. 15. Вычислительная математика и кибернетика. 1995. №4. С. 49-55.

11. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: МГУ, 1984.

12. Лупанов О. Б. О синтезе некоторых управляющих систем // Проблемы кибернетики. Вып. 10. М.: Физматгиз, 1963. С. 6397.

13. Лупанов О. Б. О схемах из функциональных элементов с задержками // Проблемы кибернетики. Вып. 23. М.: Наука, 1970. С. 43-81.

14. Лупанов О. Б. Об одном классе схем из функциональных элементов // Проблемы кибернетики. Вып. 7. М.: Физматгиз, 1962. С. 6-115.

15. Лупанов О. Б. Об одном методе синтеза схем // Известия ВУЗов. Радиофизика. 1, 1, 1958. С. 120-140.

16. Лупанов О. Б. Об одном подходе к синтезу управляющих систем — принципе локального кодирования // Проблемы кибернетики. Вып. 14. М.: Физматгиз, 1965. С. 31-110.

17. Нигматуллин Р. Г. Сложность булевых функций. М.: Наука, 1991.

18. Нигматуллин Р. Г. Нижние оценки сложности и сложность универсальных схем. Казань: изд-во КГУ, 1990.

19. Редькин Н. П. О минимальной реализации двоичного сумматора // Проблемы кибернетики. Вып. 38. М.: Наука, 1981. С. 181-216.

20. Редькин Н. П. Однородные структуры из двухканальных элементов // Автоматика и телемеханика, 4. М., 1972. С. 84-89.

21. СэвиджДж. Э. Сложность вычислений. М.: Факториал, 1998.

22. ТоомА. Л. О сложности схем из функциональных элементов, реализующих умножение целых чисел // Докл. АН СССР, т. 149, №4, 1963. С. 496-498.

23. Храпченко В. М. Некоторые оценки для времени умножения // Проблемы кибернетики. Вып. 33. М.: Наука, 1978. С. 221-227.

24. Храпченко В. М. Об асимптотической оценке времени сложения параллельного сумматора // Проблемы кибернетики. Вып. 19. М.: Наука, 1967. С. 107-122.

25. Храпченко В. М. Различие и сходство между задержкой и глубиной // Проблемы кибернетики. Вып. 35. М.: Наука, 1979. С. 141-168.

26. Шеннон К. Работы по теории информации и кибернетике. М.: ИЛ, 1963.

27. ШенхагеА., ШтрассенВ. Быстрое умножение больших чисел // Кибернетический сборник (нов. сер.). Вып. 10. М.: Мир, 1973. С. 87-98.

28. Шкаликова Н. А. О реализации булевых функций схемами из клеточных элементов // Математические вопросы кибернетики. Вып. 2. М.: Наука, 1989. С. 177-197.

29. Шкаликова Н. А. О сложности реализации некоторых функций клеточными схемами // Сборник работ по математической кибернетике. Вып. 1. М., 1976. С. 102-115.

30. Шоломов Л. А. О реализации недоопределённых булевых функций схемами из функциональных элементов // Проблемы кибернетики. Вып. 21. М.: Наука, 1969. С. 215-226.

31. ЧашкинА. В. Об одном методе вычисления частичных булевых функций // Математические вопросы кибернетики. Вып. 12. М.: Физматгиз, 2003. С. 231-246.

32. Яблонский С. В. Введение в дискретную математику. Изд. 3-е. М.: Высш. школа, 2001.

33. Яблонский С. В. Основные понятия кибернетики // Проблемы кибернетики. Вып. 2. М.: Физматгиз, 1959. С. 7-38.

34. AhoA., HopcroftJ., UllmanJ. The design and analysis of computer algorithms. Addison-Wesley, Reading, Massachusets, 1974. Имеется перевод: АхоА., ХопкрофтДж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.]

35. AklS.G. Parallel computation: models and methods. Prentice-Hall, 1997.

36. AllenderE., BarringtonD. A. M., Hesse W. Uniform circuits for division: consequences and problems // Proceedings of the 17th Annual IEEE Conference on Computational Complexity (CCC 2001).ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/2001/TR33

37. Avior A., CalamoneriT., EvenS., LitmanA., Rosenberg А.A tight layout of the butterfly network // 8th ACM Symp. on Parallel Algorithms and Architectures. June 23-26, 1996, Padua, Italy. P. 170-175.

38. Brent R. P. On the addition of binary numbers // IEEE Transactions on Computers. Vol. 19, 1970. P. 758-759.

39. Brent R. P., KungH. T. A regular layout for parallel adders // IEEE Transactions on Computers. Vol. 31, 1982. P. 260-264.

40. Brent R. P., KungH. T. On the area of binary tree layouts // Information Processing Letters. Vol. 11, №1, 1980. P. 46-48.

41. Chiu A., Davida G., Litow B. Division in logspace-uniform NC1 // Theoretical Informatics and Applications. Vol. 35, № 3, 2001. P. 259-275.http: //www. cs.j cu. edu. au/~bruce/papers/crr003ps. gz

42. Fich F. E. New bounds for parallel prefix circuits // Proceedings of the ACM Symposium on Theory of Computing. 1983. P. 100-109.

43. Hastad J., LeightonT. Division in O(logn) depth using (9(n1+£) processors. Неопубликованная работа, 1986.http: //www. nada. kth. se/~ j ohanh/paraldivision. ps

44. Hesse W. Division is in uniform TC° // Proceedings of the 28th International Colloquium on Automata Languages and Programming (ICALP 2001).http: //loki. cs. umass. edu/~whesse/div. ps

45. HromkovichJ., LozhkinS.A., RybkoA.I., Sapozhen-ko A. A., ShkalikovaN. A. Lower bounds on the area complexity of Boolean circuits // Theoretical Computer Science. Vol. 97, № 2, 1992. P. 285-300.

46. LadnerR. E., Fischer M.J. Parallel prefix computation // Journal of the ACM. Vol. 27, 1980. P. 831-838.

47. LakshmivarahanS., DhallS.K. Parallel computing using the prefix problem. Oxford University Press, New York, 1994.

48. LakshmivarahanS., Yang C.M., DhallS.K. Optimal parallel prefix circuits with (size + depth) = 2n + 2 and logn] ^ depth ^ [21ogn] — 3 // Proceedings of the International Conference on Parallel Processing, 1987. P. 58-65.

49. MeadC., Conway L. Introduction to VLSI Systems. Addison-Wesley, Reading, Massachusetts, 1980.

50. Milter sen P. B. On the Shannon Function for Partially Defined Boolean Functions // ICALP Satellite Workshops 2000. P. 253-258, http://www.brics.dk /~bromille/Papers/shannon6.ps

51. PatersonM. S., PippengerN., ZwickU. Optimal carry save networks // Boolean function complexity. Cambridge: Cambridge Univ. Press, 1992. P. 174-201. (London Mathematical Society Lecture Note Series 169)

52. ReifJ.H., TateS.R. Optimal size integer division circuits // SIAM Journal on Computing. Vol. 19, No. 5, 1990. P. 912-924. http: //www. cs. duke. edu/~reif/paper/tate/div. pdf

53. ShankarN., Ramachandran V. Efficient parallel circuits and algorithms for division // Information Processing Letters, Vol. 29, 1988. P. 307-313.

54. UllmanJ. D. Computational aspects of VLSI. Computer Science Press, Rockville, Maryland, 1984. Имеется перевод: Ульман Дж. Д. Вычислительные аспекты СБИС. М.: Радио и связь, 1990.]

55. Wegener I. The complexity of Boolean functions. Wiley-Teubner Series in Computer Science (John Wiley and Sons Ltd., and B. G. Teubner), Stuttgart, 1987.Публикации автора по теме диссертации

56. Жуков Д. А. О времени параллельного сложения нескольких чисел // Материалы четвёртой молодёжной научной школы по дискретной математике и её приложениям (МГУ, ноябрь 2000). М.: Изд-во мех.-мат. фак. МГУ, 2000. С. 39-47.

57. Жуков Д. А. О времени параллельного сложения нескольких чисел // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2001. №6. С. 52-54.

58. Жуков Д. А. Клеточные схемы для арифметических операций // Материалы пятой молодёжной научной школы по дискретной математике и её приложениям (МГУ, ноябрь 2001). — М.: Изд-во мех.-мат. фак. МГУ, 2002. С. 50-52.

59. Жуков Д. А. Быстрые клеточные схемы для умножения // Дискретный анализ и исследование операций. Сер. 1. Т. 9, №3, 2002. С. 40-47.

60. Жуков Д. А. Об одном классе клеточных схем // Материалы XIV Международной школы-семинара «Синтез и сложность управляющих систем» (Нижний Новгород, 27 октября 1 ноября 2003 г.). - Нижний Новгород: Изд-во НГПУ, 2003. С. 33-37.

61. Жуков Д. А. О вычислении частичных булевых функций клеточными схемами // Материалы VIII Международного семинара «Дискретная математика и её приложения» (Москва, 26 февраля 2004 г.). — М.: Изд-во мех.-мат. фак. МГУ, 2004. С. 63-66.

62. Жуков Д. А. О вычислении частичных булевых функций клеточными схемами // Дискретный анализ и исследование операций. Сер. 1. Т. 11, №2, 2004. С. 32-40.