О реализации функций алгебры логики автоматными конвейерными схемами

• Автор: Никитин, Андрей Анатольевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Москва
• Количество страниц: 90 с.

Содержание
1 Общая характеристика работы
1.1 Введение
1.2 Постановка задачи и формулировка полученных результатов
2 Оценки объема памяти, необходимой для реализации функций конвейерными схемами, синтез схем с минимальным объемом памяти
2.1 Нижние оценки функций Шеннона для объема памяти
2.2 Верхние оценки функций Шеннона для объема памяти
2.3 Сложность конвейерных схем, использующих минимальный объем памяти
3 Синтез конвейерных схем с эксклюзивным доступом к результатам вычислений
3.1 Верхние оценки функций Шеннона для сложности схем с эксклюзивным доступом к результатам вычислений и множественным доступом к памяти
3.2 Нижние оценки функций Шеннона для сложности схем с эксклюзивным доступом к результатам вычислений и множественным доступом к памяти
3.3 Схемы с эксклюзивным доступом к памяти
4 Конвейерные схемы с множественным доступом к результатам вычислений
4.1 Поведение функции Шеннона для сложности схем с множественным доступом к результатам вычислений
4.2 Синтез схем с множественным доступом к результатам вычислений, реализующих функции из некоторых классов
5 Список литературы

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

Данная работа посвящена изучению вопросов, связанных с массовым синтезом конвейерных схем, реализующих функции алгебры логики от произвольного числа переменных. В качестве меры сложности конвейерной схемы рассматриваются такие ее характеристики как сложность, т.е. сумма сложностей (весов) элементов, составляющих схему, объем памяти, представляющий собой число элементов памяти, входящих в схему, и время вычислений, т.е. число тактов, которые должны пройти с момента поступления на входы схемы первого входного значения до появления на выходе схемы результатов вычислений. Исследуется асимптотическое поведение функций Шеннона как для сложности реализации функций алгебры логики конвейерными схемами, так и для минимального объема памяти, необходимого при вычислении произвольной функции алгебры логики конвейерными схемами. Кроме того, рассматривается задача одновременной оптимизации сложности схем и объема памяти, задействованной в них. В результате получены асимптотические оценки высокой степени точности для функции Шеннона, характеризующей сложность реализации функций алгебры логики в классах конвейерных схем, допускающих ограничения на объем используемой памяти.
Модели, описывающие поведение вычислительных устройств, построенных ”по принципу конвейера”, исследовались разными авторами.
В [35] Редькиным Н.П. исследовалась задача построения матричных (решетчатых) структур из элементов с двухканальными связями, реализующих функции алгебры логики. Матричную структуру из двухканальных элементов можно рассматривать как устройство с ’’конвейерным” входом и с памятью. Его суть сводится к распределению вычислений, производимых в ’’памяти” устройства, во времени. В каждый момент времени ’’активной” является только одна входная булевская переменная, и в этот момент значение именно этой переменной определяет изменение содержимого памяти. Таким образом, матричные структуры из двухканальных элементов позволяют не использовать одновременно сразу все входные данные, а, наоборот, предполагают их поочередную подачу на вход структуры. В этой работе предложен метод синтеза структур рассматриваемого вида, приводятся верхняя и нижняя оценки функции Шеннона, совпадающие при числе переменных, равном степени двойки.
В [13] Кудрявцевым В.Б. рассматривается понятие прямоугольной логической сети, ориентированной на реализацию одной и той же вычислительной процедуры, применяемой к различным входным

Если дг(/ — 1) = дг+і (/ — 1) = 0, то:
Яі(і) = Чі+уп{ь - 1), г = 0,1
Чуп—1)+*() = %и,п+і+1()) І — 0, 1, 1),
дг(/) = 0, г = д„/°
Чт+і(/) = дг+і(/ - 1) V дг(/); ї/(<) = 0;
Если дг(/ — 1) = 1, д,-+і(/ — 1) = 0, то:
I Л<(г!(і)
Чі{і) = | гип+і{ї) >> гип+уп{і)) 1 5 > 1;
[ о, 5 = 1;
і = О,1
Чг+1(0 — і)
/г0(гі (/)
//(/) — ‘ 2ип+і(ї): , ип+ї'п(і0)’ 5 = 1;
О, 5 > 1;
Если дГ+і (/ — 1) = 1,то:
ф(<) = 0і(®(* -!), ,?«-і(* - 1),2ип+і(/)
* = 0,1
?*(*) = °.
і = в
дг+і(/) = 1;
//(/) = 0о($о(<- 1)
®>(°) = 91 (0) = ... = д-мй-2(0) = ад(0) = дг+і(0) = 0;
9«„*»-і(0) = 1.
Покажем, что построенная схема действительно вычисляет функцию /(жі, ж2
Пусть (<л
Рассмотрим моменты времени / = 1,2
Ситуация меняется в момент времени / = /® + 1. Начальное