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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложение А. Общие формулы для вычисления нижних мощностных оценок функции Шеннона 75

• Постановка задачи и формулировка полученных результатов
• Нижние оценки функций Шеннона
• Поведение функции Шеннона для унарной сложности рекурсивных схем из функциональных элементов
• Синтез невырожденных мультимодульных программ

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

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

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

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

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

П \ П J

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

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

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

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

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

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

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

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

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

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

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

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

L\n) = (1 ± о(1)).

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

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

L\n) = - (l + п \

log п ± О (log log п)

п

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

L2(n) = J (1 + 0(1)).

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

L3(n) - (1 + 0(1)), п

а из результатов работы [16] вытекает следующая асимптотическая оценка высокой степени точности для этой функции Шеннона:

Также рассматривались некоторые частные случаи BDD:

а) Свободные бинарные решающие диаграммы (Free BDD) - бинар ные решающие диаграммы, в которых никакой путь от корня к листу не содержит двух контактов, помеченных символами одинаковых пере менных (см., например, [26,32]).

б) Упорядоченные бинарные решающие диаграммы (Ordered BDD) - бинарные решающие диаграммы, в которых переменные упорядочены таким образом, что ни на одном пути от корня к листу переменная с большим номером не может встретиться раньше переменной, номер которой меньше (см., например, [26,32]).

в) Строго упорядоченные бинарные решающие диаграммы с крат ностью считывания к (k-SOBDD), то есть бинарные решающие диа граммы, в которых все переменные а?і,...,ж„ упорядочены некоторым образом, и любой путь от корня к листу содержит ровно пк контактов и все эти переменные встречаются в нем в указанном порядке сначала один раз, потом второй раз и т.д. (см., например, [17,26,32]).

г) Упорядоченные бинарные решающие диаграммы с кратностью считывания к (k-OBDD) определяются аналогично k-SOBDD, с той лишь разницей, что в вычисляющих путях возможны пропуски переменных (см., например, [17,26,32]).

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

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

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

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

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

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

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

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

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

Введено понятие удельного веса команды. Для вычислительной команды и удельный вес команды 7г(о ) равен A(u;)/d(w), где d(u ) - это суммарное число входов и выходов данной команды. Для переадресующей команды Т удельный вес команды Л(Т) равен Л (Г)/2.

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

LB(n) 5{В)кп/щ

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

LB(n,mn) 5(B)mnkn/\ogk(mnkn).

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

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

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

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

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

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

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

Вес и удельный вес вычислительных и переадресующих команд определяются аналогично [6]. Вес s(u) команды вызова подпрограммы

w линейно зависит от числа входов к в этой команде и определяется по формуле:

s(w) = fik + 2/,

где ji 0, v 0.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Существенным обобщением модели, введенной в работе [7], послужила модель, рассмотренная в работе [6]. Основные отличия этой модели от предыдущей заключаются в следующем: 1) в модели рассмотрены вектор-функции /г-значной логики; 2) вычислительные команды могут реализовать произвольные функции (не только двуместные, как в [7]) из заданного конечного множества базисных функций В; 3) вычислительные команды могут иметь несколько выходов, то есть одна команда может записывать в несколько ячеек памяти результаты вычисления нескольких функций; 4) имеется только одна команда останова, а выходное значение (набор выходных значений) программы определяется значением (набором значений), которое к моменту останова оказалось в специальной выделенной ячейке памяти (наборе ячеек памяти). Каждой команде ш приписан некоторый вес Л (о;) Сложность программы определяется как сумма весов всех команд в программе. Введено понятие удельного веса команды. Для вычислительной команды и удельный вес команды 7г(о ) равен A(u;)/d(w), где d(u ) - это суммарное число входов и выходов данной команды. Для переадресующей команды Т удельный вес команды Л(Т) равен Л (Г)/2. Для этой модели в [6] установлена асимптотика функции Шеннона: LB(n) 5{В)кп/щ где 5(B) - это минимальной удельный вес команд. Для случая вектор-функций /:-значной логики, состоящих из тп функций от п переменных, в [6] также представлена асимптотика соответствующей функции Шеннона следующего вида: LB(n,mn) 5(B)mnkn/\ogk(mnkn). В настоящей работе исследована модель, обобщающая модель [7] и расширяющая возможности программ модели [6], применительно к реализации функций алгебры логики. Следующие характеристики рассматриваемой модели ограничивают ее, по сравнению с моделью в [6]: 1) рассмотрена реализация функций алгебры логики (в отличие от [6], где рассмотрены вектор-функции в /г-значной логике); 2) каждая вычислительная команда имеет ровно один выход, и реализует ровно одну функцию из заданного конечного множества базисных функций алгебры логики Б (в отличие от [6], где возможна реализация нескольких функций с помощью одной вычислительной команды); Следующие характеристики обобщают рассматриваемую модель, по сравнению с моделью в [6]: 1) программа представлена в виде набора подпрограмм, каждой из которых соответствует отдельное множество ячеек памяти; 2) вводится новый тип команд - команда вызова подпрограммы, которая записывает в заданную ячейку памяти результат работы заданной ранее определенной подпрограммы, входные переменные которой инициализируются значениями из заданных ячеек памяти. Вес и удельный вес вычислительных и переадресующих команд определяются аналогично [6]. Вес s(u) команды вызова подпрограммы w линейно зависит от числа входов к в этой команде и определяется по формуле: Таким образом, введены 4 основных весовых характеристики программ: минимальный удельный вес вычислительных команд я , удельный вес переадресующих команд Л, а также весовые коэффициенты команд вызова подпрограмм fi и и. Можно выделить 4 различных класса программ, в зависимости от того, какая из четырех основных весовых характеристик является наименьшей. Кроме того, можно выделить различные классы программ, в зависимости от того, какие типы команд разрешено использовать в программе и какие весовые характеристики равны нулю. Если в программе разрешены только вычислительные (переадресующие) команды, то мы, по существу, имеем дело с обычными схемами из функциональных элементов (соответственно BDD), которые достаточно хорошо изучены и в данной работе специально не рассматриваются. В работе не рассматриваются также вырожденные случаи, при которых 7Г = 0 или А = 0. В то же время подробно рассматривается случай, когда программа не может содержать переадресующих команд, который приводит нас к модели так называемых рекурсивных схем из функциональных элементов (РСФЭ). Эта модель управляющих систем расширяет обычные схемы из функциональных элементов, позволяя определять новые функциональные элементы в процессе синтеза и использовать эти элементы в дальнейшем наравне с базисными. В данной работе исследована массовая задача синтеза для всех классов программ с произвольными неотрицательными весовыми характеристиками (при условии 7ГБ 0) и получены асимптотические оценки для соответствующих функций Шеннона. Для некоторых из этих классов в работе устанавливаются асимптотические оценки высокой степени точности для функции Шеннона, то есть оценки функции Шеннона на уровне асимптотики второго члена ее асимптотического разложения. Работа состоит из трех глав. В первой главе описывается рассматриваемая модель, даются основные определения и формулируются полученные результаты. Кроме того, исследован вопрос о возможности реализации произвольной функции алгебры логики с помощью программ из различных классов и установлен соответствующий критерий полноты программ. В дальнейшем предполагается, что рассматриваемые классы программ удовлетворяют этому критерию.

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

Выполнение вычислительной команды вида Г = { р,mo, mi,...,тг} СОСТОИТ из следующих шагов: 1) вычисляется значение функции (р(а\,... ,аг) на вход которой подано содержимое ячеек памяти с номерами mi,...,тТ\ 2) значение функции записывается в ячейку с номером то; 3) происходит передача управления на команду, номер которой на единицу больше номера команды Г. Выполнение переадресующей команды вида Г = { о, #o,(7i} состоит из следующих шагов: 1) выбирается значение из ячейки памяти с номером то; 2) если это значение равно нулю, то происходит передача управления на команду с номером go, в противном случае происходит передача управления на команду с номером q\. Выполнение команды вызова подпрограммы вида Г = {so;mo,mi,.. .тщ, }, расположенной в подпрограмме П, СОСТОИТ ИЗ следующих шагов: 1) в первые t8o ячеек памяти подпрограммы П3о записываются значения из ячеек памяти с номерами mi,..., mtf текущей подпрограммы П; 2) выполняется подпрограмма Пв0; 3) В ячейку памяти с номером то в текущей подпрограмме П записывается значение из последней ячейки памяти в подпрограмме П8о. Считается, что подпрограмма П = {fi,T,t,m, g}, где Q = {Л і,..., AJ, Л",..., Л 4_ _і, Л "}, Т = {Гі,..., Г9}, реализует ФАЛ /(#1,.. -, ), которая вычисляется следующим способом: 1) значения ai,..., at входных переменных a?i,..., xt помещаются в ячейки памяти {А[,..., A J; 2) на 1-м шаге выполняется команда Г і, а на (г + 1)-м шаге, где і 0, - команда, на которую было передано управление на г-м шаге (в процессе выполнения подпрограммы П управление может быть передано в другие различные и отличные от П подпрограммы, то есть могут происходить нерекурсивные вызовы одних подпрограмм из других); 3) выполнение подпрограммы завершается когда в ячейку памяти Л " записывается значение; 4) значением /(c i,.. .,at) является значение, которое после окончания работы подпрограммы будет записано в ячейке Л ". Будем считать, что программа Е = {Пі,...,П8} реализует ту же функцию /і(#і,...,ж ), которую реализует ее первая подпрограмма Щ. Каждому элементу Е{ из базиса Б поставим в соответствие его вес Pi, где pi 0 и определим удельный вес этого элемента: где г І - число входов элемента Д-. Заметим, что понятие удельного веса отличается от обычно используемого определения приведенного веса, равного отношению РІ/(ГІ — 1). Определим удельный вес базиса Б : и введем величину Т, равную максимальному числу входов у элементов с минимальным приведенным весом. Будем считать, что вычислительная команда {у»,mo,mi,.. . ,тг} имеет вес pi, равный весу ее базисного элемента ЕІ. Введем весовые коэффициенты Л, Л 0, /і, ц 0 и и, v О, и сопоставим каждой переадресующей команде одинаковый вес 2Л, а каждой команде вызова подпрограммы вида {so;mo,mi,.. .77 } - вес /it + v. Будем говорить, что набор j = (Л, /г, г/) является весовым набором рассматриваемого класса программ. Программы над базисом Б с заданным весовым набором 7 будем называть (Б, у)-программами или 7-программами над Б. Чтобы обобщить данные определения на классы программ, не содержащие некоторые типы команд, будем считать, что для этих классов программ соответствующие коэффициенты в наборе 7 равны со. Программы, для которых fi = 00, то есть программы, не содержащие команд вызова подпрограмм, будем называть одномодульными програм мами. Программы, для которых ji со, будем называть му льтижо дульными программами. Будем называть класс (,7)-программ полным, если с помощью программ из этого класса можно реализовать произвольную функцию алгебры логики. Критерий полноты произвольного класса программ дан в следующей теореме, которая доказывается в 1.3 1) Для того чтобы класс программ над базисом Б, не содержащий переадресующих команд, был полон, необходимо и достаточно, чтобы система функций базиса Б не содержалось целиком ни в одном из классов То, Ті, 5, М, L. 1 2) Для того чтобы класс программ над базисом Б, содержащий переадресующие команды, был полон, необходимо и достаточно, чтобы система функций в базисе Б не содержалось целиком ни в одном из классов То, Гь Далее рассматриваются вопросы сложности реализации функций алгебры логики в полных классах программ, где 0 ПБ со. Сумма весов всех команд, входящих в программу Е над базисом Б, называется ее сложностью и обозначается ЬБ(Е). Под сложностью LE(f(xi,..., хп)) функции алгебры логики f(x\,...,хп) понимается минимальная из сложностей Ljj(), где минимум берется по всем программам Е над юазисом Б с весовым набором "у, реализующим функцию f(x\,.. .,хп). Функцией Шеннона ЬБ(п) называется максимальная из сложностей LE(f), где максимум берется по всем функциям алгебры логики /, зависящим от переменных xi,..., хп. Используя введенные определения и обозначения можно классифицировать некоторые известные типы программ и выписать известные оценки соответствующих функций Шеннона. Бинарные программы общего вида, описанные в [7], в рамках введенных обозначений, являются (1 2,1/2,оо,оо)-программами над базисом Бъ, состоящим из всех двухвходовых функций алгебры логики веса 1. Из [6] следует асимптотическая оценка функции Шеннона в этом классе 1 Определения предполных классов То, Т\у 5, М, L и теорему о функциональной полноте в Рг можно найти, например, в [25]. программ: Если ограничить модель, описанную в [6], функциями 2-значной логики и потребовать дополнительно, чтобы вычислительные команды имели не более одного выхода, то полученная модель соответствует классу (2 , А,оо,оо)-программ. Из [6] следует асимптотическая оценка функции Шеннона в этом классе программ:

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

Будем рассматривать одномодульные (Л, оо, со)-программы над базисом Б. Будем говорить, что команда Г является достижимой, если найдется такой набор входных переменных {х\,..., хп}, при обработке которого эта команда будет выполнена. Легко видеть, что если команда не является достижимой, то ее можно удалить из программы, поэтому в дальнейшем будем рассматривать программы, все команды которых достижимы.

Если не оговорено противное, то далее в данном параграфе (до леммы 2.1.5 включительно) под командой будем понимать вычислительную команду.

Пусть А - множество адресов памяти. Будем говорить, что последовательности команд Pi и Рг являются А-эквивалентнымщ если при любом исходном содержимом памяти выполняется условие: содержимое ячеек памяти с номерами из А после выполнения последовательности команд Pi будет точно таким же, как после выполнения последовательности команд Рг.

Будем называть последовательности Pi и Рг эквивалентными, если все ячейки памяти, которые используются в последовательностях Pi и Рг, принадлежат множеству Л, и последовательности Pi и Рг являются -эквивалентными.

Через А(Р) обозначим множество адресов памяти, которые упоминаются в командах последовательности Р. Через Р обозначим число команд в Р. Последовательность команд Р будем называть правильной, если для любых двух различных команд К Є Р, К = {/, то, гаї,..., гаГ} и К Є Р, К = {/ , т 0, ra i,..., т г,}, выполняется условие гао Ф га 0. Лемма 2.1.1 Для любой последовательности команд Р существует правильная последовательность команд Р , такая что Р и Р являются А(Р)-эквивалентными, и при этом \Р\ = Р , L(P) = L(P ). Доказательство. Рассмотрим произвольную последовательность команд Р = {К\,... ,Кт}. Если Р является правильной, то возьмем Р = Р. Допустим теперь, что Р не является правильной. Тогда существуют числа г,j, 1 г j m, такие что К{ = {/,mo,mi,.. .,гаГ} и Я - = {/ , то, m j,..., т г,}. Введем новую ячейку памяти с номером т 0 Л(Р) и заменим команду КІ на команду К[ = {/, т 0,7711,7712}. Кроме этого, во всех командах, номера которых больше г, но меньше j, заменим все упоминания адреса то на т 0. Полученная последовательность Р" является Л(Р)-эквивалентной последовательности Р, причем \Р\ = Р", L(P) = L(P"). Если Р" не является правильной, будем повторять описанные преобразования (не более m раз) до тех пор, пока полученная последовательность Р " не будет правильной. Легко видеть, что Р " и Р являются А(Р)-эквивалентными, причем \Р\ = Р" , L{P) = L(P "). Рассмотрим последовательность команд Р = {К\,... ,Кт}. Будем говорить, что команда КІ = {/,mo,mi,...,mr} непосредственно следует за командой Kj = {/ ,т0,ті,.. .,m./}, если і j и найдется такое &, 1 А; г, что тп = т 0. Команды ІІГ = {/,7no,mi,.. .,7nr} и К = {/ ,m0,mi,.. . ,m r,} будем называть смежными, если либо К непосредственно следует за К\ либо К непосредственно следует за К. Правильную последовательность команд Р будем называть связной группой, если для любых двух команд К Є Р и К Є Р найдется число п и такие команды КІХ Є Р,. , І І„ Є Р, что в наборе команд К, К{х,..., -K"in, К любые соседние команды являются смежными в Р. Заметим, что в СФЭ, соответствующей связной группе команд, подграф, растянутый на все отличные от входов вершины, является слабо связным графом. Будем говорить, что последовательность команд Р разбита на связные группы Р\,..., Pjt, если Pi U... U РА: = М и для любых 1 г j к справедливо условие Р;ПР,- = 0 и не существует смежных команд К Є Pi и К Є Pj. Разбиение последовательности команд на связные группы можно интерпретировать, как разбиение множества элементов соответствующей схемы из функциональных элементов на слабо связные компоненты. Справедливость следующей леммы непосредственно вытекает из определения связной группы. Лемма 2.1.2. Любую правильную последовательность вычислительных команд Р можно разбить на связные группы и притом един ственным образом Рассмотрим следующий алгоритм приведения связной группы команд к "стандартному" виду. Алгоритм 2.1.1 Пусть задана связная группа команд Р. Алгоритм строит связную группу команд Р, последовательно добавляя в нее команды из Р и помечая уже добавленные команды. Будем говорить, что непомеченная команда К является открытой, если все команды, из которых следует К, уже помечены. Шаг 0. В начальный момент времени Р пуста, а все команды из Р являются непомеченными. Шаг 1. Находим в Р первую непомеченную команду К, которая не следует непосредственно ни из одной другой команды в Р. Помечаем К и добавляем ее в Р. Шаг 2. Находим в Р все открытые команды, которые следуют из К, и добавляем их в Р в порядке возрастания номеров этих команд. Шаг 3. Находим в Р все открытые команды, которые следуют из команд, добавленных на предыдущем шаге, помечаем их и добавляем их в Р. При этом если на предыдущем шаге команда К\ была добавлена раньше команды Кг, то на этом шаге сначала добавляются команды, которые следуют за командой К\, а потом те команды, которые следуют за командой Кг. Повторяем шаг 3, пока на нем добавляется хотя бы одна команда. Шаг 4. Если в Р остались непомеченные команды, возвращаемся к шагу 1, иначе алгоритм прекращает работу. Нетрудно убедиться в том, что по окончании работы алгоритма мы получим связную группу команд Р , эквивалентную исходной связной группе Р. При этом, если применить алгоритм 2.1.1 к Р , то полученная связная группа Р" будет совпадать с Р. Будем говорить, что связная группа команд Р = {К\, .,Кт} является упорядоченной, если она переводится сама в себя с помощью алгоритма 2.1.1. Обозначим через а Б максимальное число входов в элементах из базиса Б. Заметим, что если и Б = 0, то любая связная группа содержит ровно одну команду.

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

Установим сначала требуемую нижнюю оценку. Рассмотрим произвольную (Б, А, со, Сопрограмму Е, которая реализует функцию /(жі,... ,хп) и сложность которой не превышает L, причем не существует эквивалентной программы, имеющей меньшую сложность, либо программы, имеющей ту же сложность, но меньшее число команд.

Легко видеть, что количество адресов памяти, которые могут упоминаться в вычислительных и переадресующих командах программы , не превышает L/тіп(7Г, А/2). Другими словами, программа использует не более C\L ячеек памяти, где С\ = 1/ min(7T, А/2) 0, среди которых должны быть ячейки, содержащие значения всех существенных переменных функции /. Следовательно, если в группе последовательно расположенных команд встречаются только команды записи констант, то количество команд в этой группе не превышает (C\L — к), где к - число существенных переменных функции /. В противном случае в группе нашлись бы две команды, записывающие константы в одну и ту же ячейку памяти и при удалении команды с меньшим номером получилась бы эквивалентная программа той же сложности но с меньшим числом команд.

Таким образом, программу можно представить, как совокупность нескольких групп, состоящих только из команд записи констант, которые разделены либо вычислительными, либо переадресующими командами. Пусть Сг 0 - минимальная сложность команды среди всех вычислительных и переадресующих команд. Следовательно, общее число указанных выше групп не превышает (L/C2 +1), а общее число команд Е не больше, чем {C\L — k)(L/C2 + 1) Из приведенных рассуждений следует, что число д 00 (L,n) неэквивалентных (Б, А,оо,0)-программ, которые реализуют функции от п переменных и сложность которых не превышает L, оценивается следующим образом:

Проведя стандартное мощностное преобразование, получим следующую нижнюю оценку рассматриваемой функции Шеннона: Перейдем теперь к получению верхней оценки функции Шеннона для (Б, Л, со, (З)-программ. Пусть задана произвольная функция алгебры логики /(жі,...,жп). Построим (Б, А,оо,0)-программу Е, реализующую эту функцию. Разложим функцию /(жі,..., хп) по последним п — q переменным: На первом піаге построим две вспомогательные подпрограммы, реализующие функции "константа 0" и "константа 1". Обозначим суммарную сложность этих подпрограмм через Сб. Очевидно, CQ не зависит от п. Реализация функции / происходит в третьей основной подпрограмме, которая строится следующим образом. Первые 2n q — 1 команд в основной подпрограмме - это переадресующие команды. Эти команды образуют полное (п — q — 1)-ярусное двоичное дерево, с помощью которого происходит передача управления на одну из 2n q команд с номерами из множества {&(,,... ,/ -, ), к\ — (2я + 1)г + 2n q — 1, в зависимости от набора значений переменных жд+і,... ,х„. Суммарная сложность этой группы команд равна (2П « - 1)Л. Следующие 2й-9(2q + 1) команд образуют 2n q последовательных групп команд. Каждая группа содержит (2я + 1) команду, г-я группа, і = 0, ...,2n q — 1, содержит команды с номерами Ц,..., k i+1 — 1. Первые 2q команд г-й группы - это команды вызова подпрограмм, которые записывают константы 0 и 1 в ячейки памяти с номерами О,..., 2q — 1. При этом в ячейку памяти с номером j записывается значение функции /сг,+1,.„, т1,(ог1» с9) где crq+i,..., 7„ - это двоичная запись числа г, a 7i,..., сг9 - это двоичная запись числа j. Последняя команда каждой группы - это переадресующая команда (одинаковая для всех групп), которая осуществляет безусловный переход на команду с номером к" — (2q + 1)2П_9 + 2п ч — 1. Суммарная сложность всех этих групп команд равна 2n q\.

Следующие 2q{2q l + 1) команд образуют q групп команд. Каждая группа содержит (2q + 2) команд и состоит из двух последовательных подгрупп одинаковой длины (29-1 + 1). Пусть к\ - номер первой команды в г-й группе, к" - номер первой команды во второй подгруппе г-й группы. Первая команда первой подгруппы г-й группы является переадресую-щей и имеет вид (k j) : {xq+i k { + 1,А;"}. Если xq+i — О, то эта команда передает управление на следующую команду программы, иначе происходит передача управления на вторую команду второй подгруппы. Остальные команды первой подгруппы записывают константу 0 в те ячейки памяти, номера которых принадлежат множеству {0,..., 2Ч — 1} и г -я компонента двоичной записи номера ячейки равна единице. Первая команда второй подгруппы г-й группы осуществляет передачу управ-ления на команду с номером к і+1і то есть на первую команду следующей группы. Остальные команды второй подгруппы записывают константу 0 в те ячейки памяти, номера которых принадлежат множеству {О,.. .,29 — 1} и г -я компонента двоичной записи номера ячейки равна нулю. Суммарная сложность всех этих групп команд равна 2q\. Следующие 2q команд являются переадресующими. Если г -я ячейка памяти равна 1, то г -я из этих команд передает управление на команду, которая записывает единицу в ячейку Л ", таким образом программа завершается и выдает единицу. В противном случае г -я из этих команд передает управление на следующую команду. Суммарная сложность всех этих групп команд равна 29Х. Последняя команда подпрограммы записывает 0 в ячейку Л ", таким образом программа завершается и выдает ноль. Построенная программа реализует функцию /(жі,.. .,а:п). Нетрудно убедиться в том, что сначала построенная программа записывает 2q констант соответствующих столбцу значений функции fXq+1 жп(жі,..., xq), в ячейки {0,..., 2q — 1}. Затем во все ячейки, кроме ячейки, двоичная запись номера которой равна (жі,...,ж9), программа записывает нули. Если после всех проделанных операций найдется ячейка, содержащая единицу, значит значение функции / на заданном наборе равно единице, иначе значение функции / равно нулю. Поэтому программа проверяет все 2q ячеек памяти. Если очередная ячейка содержит 1, программа завершается и выдает 1, в противном случае происходит обработка следующей ячейки. Когда проверены все ячейки, программа завершается и выдает 0.