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

• Грибок, Сергей Владимирович
• кандидат физико-математических наук
• 2003

Оглавление диссертации кандидат физико-математических наук Грибок, Сергей Владимирович

Глава 1. Введение

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

§1.2 Постановка задачи и формулировка полученных результатов

§1.3 Критерий полноты программ

Глава 2. Одномодульные программы

§2.1 Структура одномодульных программ

§2.2 Нижние оценки функций Шеннона

§2.3 Верхние оценки функций Шеннона

Глава 3. Мультимодульные программы

§3.1 Программы с легкими константами.

§3.2 Поведение функции Шеннона для унарной сложности рекурсивных схем из функциональных элементов.

§3.3 Поведение функции Шеннона для сигнатурной сложности рекурсивных схем из функциональных элементов.

• §3.4 Синтез невырожденных мультимодульных программ

Введение диссертации (часть автореферата) на тему «О реализации функций алгебры логики в некоторых классах программ»

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

Задача синтеза получила строгую математическую постановку в работе К. Шеннона [30]. Обычно задача синтеза рассматривается для какого-либо класса управляющих систем, то есть множества схем, наделенных определенной структурой и характеризующихся функционированием (см. например [25]). Функционирование схемы, как правило, описывается булевской функцией или системой булевских функций. Вводится понятие сложности схемы, обычно равной сумме сложностей всех элементов, составляющих ее, после чего определяется сложность булевской функции, как сложность самой простой схемы, реализующей эту функцию, и функция Шеннона, зависящая от натурального аргумента п, которая равна максимальной сложности булевских функций от п переменных. Задача массового синтеза состоит в изучении поведения (установлении асимптотики) функции Шеннона при растущем значении аргумента п.

Первые оценки для функций Шеннона, характеризующих сложность реализации функций в некоторых основных классах управляющих систем, таких как контактные схемы, релейно-контактные схемы, формулы, схемы из функциональных элементов в произвольном полном конечном базисе, были получены в работах К.Шеннона и О.Б.Лупанова [30,18,19,20,21]. К.Шенноном был установлен порядок функции Шеннона для класса контактных схем, а О.Б.Лупановым для всех основных классов управляющих систем была найдена асимптотика соответствующих функций Шеннона. В дальнейшем, усилиями многих авторов была установлена асимптотика сложностных функций Шеннона для различных задач массового синтеза.

Вместе с тем до появления работ С.А.Ложкина [8-15] не были известны оценки функций Шеннона с точностью до более чем одного члена их асимптотических разложений. Первый результат был получен в [8], где доказывается, что для функции Шеннона Ьк(п), характеризующей сложность реализации булевских функций ориентированными контактными схемами, выполняется равенство 1 п) = -( 1 + п \

21ogn±0(iy п

В последующих работах [9-17] приводится универсальный метод получения верхних оценок функции Шеннона, позволяющий установить оценки высокой степени точности для функций Шеннона в других основных классах управляющих систем, таких как формулы и схемы из функциональных элементов, построенные в произвольном конечном полном базисе, контактные схемы из обобщенных контактов, и многих других.

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

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

Устройство с произвольным доступом к памяти является естественной моделью вычислений и различные типы таких устройств изучались многими авторами (например [27,28]).

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

В работе [7] рассмотрены так называемые бинарные программы. В этой модели существует два типа команд:

Основание 2 у логарифмов опускается.

1) вычислительные команды, которые записывают в заданную ячейку памяти гпз результат применения заданной двуместной логической функции f{x 1,^2) к содержимому двух заданных ячеек памяти т\ и гаг;.

2) переадресующие команды, которые осуществляют переход на команду с номером к\ или на команду с номером к-i в зависимости от содержимого заданной ячейки памяти т.

Кроме того, имеются две так называемые команды останова, при выполнении которых программа завершает работу и выдает то или иное значение, в зависимости от типа команды останова.

Сложность бинарной программы считается равной общему числу команд в программе. Естественным образом вводится сложность функции алгебры логики L(f) и функция Шеннона L(n).

В работе [6] установлена асимптотика функции Шеннона для данного класса программ:

L°(n) = £(l±o(l)).

Если накладывать определенные ограничения на структуру программ из описанного выше класса, можно получить разнообразные и интересные вычислительные модели, которые рассматривались многими авторами. Перечислим некоторые из этих моделей.

1) Программы, состоящие только из вычислительных команд. Как показано в [7], этот класс управляющих систем эквивалентен классу схем из функциональных элементов (см., например, [26]), поэтому для соответствующей функции Шеннона справедливы оценки, полученные в [15] для класса схем из функциональных элементов:

2) Бинарные программы, где все ячейки памяти в вычислительных командах, в которые происходит запись результата вычисления, различны. В [7] показано, что этот класс управляющих систем эквивалентен одному из видов релейно-контактных схем, рассмотренному в [21], и установлена асимптотика соответствующей функции Шеннона:

2 п

3) Бинарные программы, состоящие только из переадресующих команд. Этот класс управляющих систем впервые был рассмотрен в работе [29]. Обычно рассматривается графическое представление данного типа бинарных программ в виде контактных схем из ориентированных контактов (см., например, [22]), в которых отсутствуют ориентированные циклы, имеется один исток, являющийся входом схемы, и два стока, являющиеся ее выходами. При этом выходы помечены символами 0 и 1, а из каждой невыходной вершины выходит ровно два контакта, один из которых помечен символом входной переменной, а другой - символом ее отрицания. В современных публикациях этот класс управляющих систем носит название BDD - 'Binary Decision Diagram' (Бинарная Решающая Диаграмма) и изучается многими авторами (см., например, [26]). В работе [7] установлена асимптотика функции Шеннона для этого класса: i3(n) = ^( 1+0(1)), п а из результатов работы [16] вытекает следующая асимптотическая оценка высокой степени точности для этой функции Шеннона:

Также рассматривались некоторые частные случаи BDD: а) Свободные бинарные решающие диаграммы (Free BDD) - бинарные решающие диаграммы, в которых никакой путь от корня к листу не содержит двух контактов, помеченных символами одинаковых переменных (см., например, [26,32]). б) Упорядоченные бинарные решающие диаграммы (Ordered BDD) -бинарные решающие диаграммы, в которых переменные упорядочены таким образом, что ни на одном пути от корня к листу переменная с большим номером не может встретиться раньше переменной, номер которой меньше (см., например, [26,32]). в) Строго упорядоченные бинарные решающие диаграммы с кратностью считывания к (k-SOBDD), то есть бинарные решающие диаграммы, в которых все переменные xi,.,xn упорядочены некоторым образом, и любой путь от корня к листу содержит ровно пк контактов и все эти переменные встречаются в нем в указанном порядке сначала один раз, потом второй раз и т.д. (см., например, [17,26,32]). г) Упорядоченные бинарные решающие диаграммы с кратностью считывания к (к-ОВББ) определяются аналогично к-ЗОВББ, с той лишь разницей, что в вычисляющих путях возможны пропуски переменных (см., например, [17,26,32]).

Для двух последних классов программ в [17] в случае к > 2 получены следующие оценки для соответствующих функций Шеннона:

Также рассматривались классы программ, состоящие из вычислительных команд и команд условной остановки. Команда условной остановки содержит номер некоторой ячейки памяти и прекращает выполнение программы, если содержимое этой ячейки равно определенному фиксированному числу. В работе [23] получены оценки функции Шеннона для среднего времени вычисления булевских функций в этом классе программ.

Программная реализация функций алгебры логики широко используется для моделирования и тестирования интегральных схем [32], а также может служить исходными данными для программ автоматизированного синтеза интегральных схем (см. например [31]).

Существенным обобщением модели, введенной в работе [7], послужила модель, рассмотренная в работе [6]. Основные отличия этой модели от предыдущей заключаются в следующем:

1) в модели рассмотрены вектор-функции к-значной логики;

2) вычислительные команды могут реализовать произвольные функции (не только двуместные, как в [7]) из заданного конечного множества базисных функций В;

3) вычислительные команды могут иметь несколько выходов, то есть одна команда может записывать в несколько ячеек памяти результаты вычисления нескольких функций;

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

Каждой команде ш приписан некоторый вес Л(о;) Сложность программы определяется как сумма весов всех команд в программе.

Введено понятие удельного веса команды. Для вычислительной команды и удельный вес команды ж(и>) равен Л(а>)/б?(а>), где - это суммарное число входов и выходов данной команды. Для переадресующей команды Т удельный вес команды А(Т) равен Л(Т)/2.

Для этой модели в [6] установлена асимптотика функции Шеннона:

Ьв{п) ~ 8{В)кп/щ где 6(В) - это минимальной удельный вес команд. Для случая вектор-функций /г-значной логики, состоящих из тп функций от п переменных, в [6] также представлена асимптотика соответствующей функции Шеннона следующего вида:

Ьв(п,тп) ~ 8(В)тпкп/ \о%к{тпкп).

В настоящей работе исследована модель, обобщающая модель [7] и расширяющая возможности программ модели [б], применительно к реализации функций алгебры логики.

Следующие характеристики рассматриваемой модели ограничивают ее, по сравнению с моделью в [6]:

1) рассмотрена реализация функций алгебры логики (в отличие от [6], где рассмотрены вектор-функции в /г-значной логике);

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

Следующие характеристики обобщают рассматриваемую модель, по сравнению с моделью в [6]:

1) программа представлена в виде набора подпрограмм, каждой из которых соответствует отдельное множество ячеек памяти;

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

Вес и удельный вес вычислительных и переадресующих команд определяются аналогично [6]. Вес в (и) команды вызова подпрограммы ш линейно зависит от числа входов к в этой команде и определяется по формуле: з(и>) = ¡1к + и, где ¡1 > 0, и > 0.

Таким образом, введены 4 основных весовых характеристики программ: минимальный удельный вес вычислительных команд 7Гудельный вес переадресующих команд Л, а также весовые коэффициенты команд вызова подпрограмм /¿их/.

Можно выделить 4 различных класса программ, в зависимости от того, какая из четырех основных весовых характеристик является наименьшей. Кроме того, можно выделить различные классы программ, в зависимости от того, какие типы команд разрешено использовать в программе и какие весовые характеристики равны нулю.

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

В данной работе исследована массовая задача синтеза для всех классов программ с произвольными неотрицательными весовыми характеристиками (при условии 7Гб > 0) и получены асимптотические оценки для соответствующих функций Шеннона.

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

Работа состоит из трех глав.

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

Во второй главе рассмотрены одномодульные программы, то есть программы, не содержащие команд вызова подпрограмм и состоящие таким образом из единственного модуля. Эту модель можно рассматривать, как частный случай модели, описанной в [6], для случая функций алгебры логики. Исследовано асимптотическое поведение функции Шеннона для сложности программ с минимальной весовой характеристикой 7гб (программы с легкими вычислительными командами) и программ с минимальной весовой характеристикой Л (программы с легкими переадресующими командами). Для каждой модели построены асимптотически совпадающие верхние и нижние оценки функции Шеннона, причем для программ с минимальной весовой характеристикой 7гб эти оценки совпадают с точностью до второго члена асимптотического разложения.

В третьей главе рассмотрены мультимодульные программы, то есть программы, содержащие команды вызова подпрограмм. Вначале рассмотрены так называемые программы с легкими константами, то есть программы с минимальной весовой характеристикой I/, в которых команды вызова подпрограмм не содержат входных параметров. Для этой модели верхние и нижние оценки функции Шеннона совпадают с точностью до второго члена асимптотического разложения. Отдельно рассмотрен частный случай, когда 1/ = 0. Оказалось, что в этом случае функция Шеннона растет по порядку как 2П/2. Также изучены программы с минимальной весовой характеристикой /л, не содержащие переадресующих команд. Изучение этого класса программ проведено в терминах рекурсивных схем из функциональных элементов. Отдельно рассмотрен частный случай, когда ¡1 = 0. Оказалось, что в этом случае функция Шеннона имеет линейную относительно п асимптотику. В последней части главы получено общее выражение для асимптотики функции Шеннона в классах программ, содержащих команды всех типов с произвольными положительными весовыми характеристиками.

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

Основные результаты диссертации опубликованы в [1]-[5].

Список литературы диссертационного исследования кандидат физико-математических наук Грибок, Сергей Владимирович, 2003 год

1. Грибок C.B. О поведении функции Шеннона для бинарных программ. Материалы X межгосударственной школы-семинара "Синтез и сложность управляющих систем", Издательство центра прикладных исследований при механико-математическом факультете МГУ, 2000. - С.4-7.

2. Грибок C.B. Об одной модели рекурсивных схем из функциональных элементов. Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 2002. N 4. С. 31-36

3. Грибок C.B. О построении нижних оценок для функции Шеннона. Материалы V международной конференции "Дискретные модели в теории управляющих систем", Издательский отдел факультета вычислительной математики и кибернетики МГУ, 2003. С.25.

4. Касим-Заде О.М. О сложности реализации функций в одном классе алгоритмов. Материалы IX межгосударственной школы-семинара "Синтез и сложность управляющих систем", Издательство механико-математического факультета МГУ, 1999. С.25-30.

5. Кузьмин В.А., Оценка сложности реализации функций алгебры логики простейшими видами бинарных программ. Методы дискретного анализа в теории кодов и схем. Сборник трудов Института математики СО АН СССР. Вып. 29, Новосибирск, 1976. С. 11-39.

6. Ложкин С.А., О синтезе ориентированных контактных схем. Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 1995. N 2. С. 36-42

7. Ложкин С.А., Новые, более точные оценки функций Шеннона для сложности управляющих систем. Дискретный анализ и исследование операций. 1995. Т.2, N 3. С. 77-78

8. Ложкин С.А., О синтезе некоторых типов схем на основе сдвиговых разбиений, порожденных универсальными матрицами. Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 1996. N 1. С. 62-69

9. Ложкин С.А., Оценки высокой степени точности управляющих систем из некоторых классов. М., 1996.-(Препр./ИПМ РАН; N 36)

10. Ложкин С.А., Оценки высокой степени точности управляющих систем из некоторых классов. Проблемы теоретической кибернетики. -Тезисы докладов XI Международной конференции 10-14 июня 1996 г. М., 1996. - С. 123-125

11. Ложкин С.А., Оценки высокой степени точности управляющих систем из некоторых классов. Математические вопросы кибернетики. Вып. 6. М.: Наука, 1996. - С. 189-214

12. Ложкин С.А., Асимптотические оценки высокой степени точности для сложности управляющих систем. Диссертация на соискание ученой степени доктора физико-математических наук. М., 1997

13. Ложкин С.А., О сложности реализации произвольных булевых функций в некоторых классах BDD. Труды Международной школы-семинара "Дискретная математика и математическая кибернетика" М.: МАКС Пресс, 2001. С.18-19

14. Лупанов О.Б., О синтезе контактных схем. ДАН СССР, 1958. -Т.119, N.1. С.23-26

15. Лупанов О.Б., Об одном методе синтеза схем. Изв. вузов, М.: Радиофизика, 1958. - T.l, N.l. - С.120-140

16. Лупанов О.Б., О сложности реализации функций алгебры логики формулами. Проблемы кибернетики. Вып.З. М.: Физматгиз, 1960. - С.61-80

17. Лупанов О.Б., О сложности реализации функций алгебры логики релейно-контактными схемами. Проблемы кибернетики, Вып. 11, М.: Наука, 1968. С.25-47.

18. Лупанов О.Б., Асимптотические оценки сложности управляющих систем. М.: Издательство Московского университета, 1984.

19. Чашкин А.В., О среднем времени вычисления значений булевых функций. Дискретный анализ и исследование операций. 1997. 4, N 1, 1997. С.60-78

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

21. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986

22. Chakravarty S., A characterization of Binary Decision Diagrams. IEEE Transactions on Computers, vol.42, no.2, (1993), 129-137.

23. S. Cook and R. Reckhow. Time bounded random access machines. J. Сотр. Sys. Sci., 7:354-375, 1973.

24. J. Katajainen, J. van Leeuwen, and M. Penttonen. Fast simulation of Turing machines by random access machines. SIAM J. Comput., 17:7788, 1988.

25. Lee C., Representation of switching circuits by binary decision programs. Bell Syst. Tech. J., no.7, (1959), 985-999.

26. Shannon C.E. The synthesis of two-terminal switching circuits Bell Syst. Techn. V.28, N1., 1949, P.59-98.

27. Wegener I. Branching programs and binary decision diagrams. SIAM Publishers, 2000. 408 p.

28. Zilic Z., Vranesic Z.G., Using decision diagrams to design ULMs for FPGAs. IEEE Transactions on Computers, vol.47, no.9, (1998), 971981