Содержание
1 Общая характеристика работы. 2
1.1 Введение.............................................. 2
1.2 Постановка задачи и формулировка полученных результатов................................................... 14
2 Оценки объема памяти, необходимой для реализации функций конвейерными схемами, синтез схем с минимальным объемом памяти. 26
2 Л Нижние оценки функций Шеннона для объема памяти. . 26
2.2 Верхние оценки функций Шеннона для объема памяти. . 31
2.3 Сложность конвейерных схем, использующих минимальный объем памяти........................................ 40
3 Синтез конвейерных схем с эксклюзивным доступом к результатам вычислений. 46
3.1 Верхние оценки функций Шеннона для сложности схем
с эксклюзивным доступом к результатам вычислений и множественным доступом к памяти...................... 46
3.2 Нижние оценки функций Шеннона для сложности схем
с эксклюзивным доступом к результатам вычислений и множественным доступом к памяти...................... 56
3.3 Схемы с эксклюзивным доступом к памяти............... ТО
4 Конвейерные схемы с множественным доступом к результатам вычислений. 77
4.1 Поведение функции Шеннона для сложности схем с
множественным доступом к результатам вычислений. . . 77
4.2 Синтез схем с множественным доступом к результатам
вычислений, реализующих функции из некоторых классов. 79
5 Список литературы 87
1
1 Общая характеристика работы
1.1 Введение.
Задача синтеза управляющих систем является одной из основных задач математической кибернетики. Она возникла естественным образом на основе ряда задач, связанных с логическим описанием и проектированием реальных устройств, занимающихся переработкой информации. К числу подобных устройств относятся, например, интегральные схемы, сети нейронов, некоторые виды вычислительных алгоритмов.
Задача синтеза впервые получила строгую математическую постановку в работе К. Шеннона [39]. Обычно задача синтеза рассматривается для какого-либо класса управляющих систем, т.е. множества схем, наделенных определенной структурой и характеризующихся функционированием (см., например, [36]). Функционирование схемы, как правило, описывается булевской функцией (системой булевских функций). Вводится понятие сложности схемы, обычно равной сумме сложностей всех элементов, составляющих ее, после чего определяются сложность булевской функции как сложность самой простой схемы, реализующей эту функцию, и функция Шеннона, зависящая от натурального аргумента п и равная максимальной сложности булевской функции от п переменных. Задача массового синтеза состоит в изучении поведения (асимптотики) функции Шеннона, при растущем значении аргумента п.
В настоящей работе рассматривается специальный класс управляющих систем, а именно класс так называемых конвейерных схем, моделирующих дискретные вычислительные устройства, в которых входные данные подаются на входы не одновременно, а в течение некоторого интервала времени. Эти вычислительные устройства функционируют в дискретные моменты времени. В каждый момент времени они получают на вход некоторый набор данных и, преобразовав его согласно некоторым правилам, записывают промежуточные результаты вычислений в память. Подобная операция производится на протяжении определенного конечного числа тактов, в результате чего на завершающем такте на выходе устройства образуется некоторое значение как функция от значений, полученных устройством во все предшествующие моменты времени. Как видно, описанное выше вычислительное устройство функционирует как конечный автомат (см., например, [12]).
2
Данная работа посвящена изучению вопросов, связанных с массовым синтезом конвейерных схем, реализующих функции алгебры логики от произвольного числа переменных. В качестве меры сложности конвейерной схемы рассматриваются такие ее характеристики как сложность, т.е. сумма сложностей (весов) элементов, составляющих схему, объем памяти, представляющий собой число элементов памяти, входящих в схему, и время вычислений, т.е. число тактов, которые должны пройти с момента поступления на входы схемы первого входного значения до появления на выходе схемы результатов вычислений. Исследуется асимптотическое поведение функций Шеннона как для сложности реализации функций алгебры логики конвейерными схемами, так и для минимального объема памяти, необходимого при вычислении произвольной функции алгебры логики конвейерными схемами. Кроме того, рассматривается задача одновременной оптимизации сложности схем и объема памяти, задействованной в них. В результате получены асимптотические оценки высокой степени точности для функции Шеннона, характеризующей сложность реализации функций алгебры логики в классах конвейерных схем, допускающих ограничения на объем используемой памяти.
Модели, описывающие поведение вычислительных устройств, построенных ”по принципу конвейера”, исследовались разными авторами.
В [35] Редькиным Н.П. исследовалась задача построения матричных (решетчатых) структур из элементов с двухканальными связями, реализующих функции алгебры логики. Матричную структуру из двухканальных элементов можно рассматривать как устройство с ”конвейерным” входом и с памятью. Его суть сводится к распределению вычислений, производимых в ”памяти” устройства, во времени. В каждый момент времени ’’активной” является только одна входная булевская переменная, и в этот момент значение именно этой переменной определяет изменение содержимого памяти. Таким образом, матричные структуры из двухканальных элементов позволяют не использовать одновременно сразу все входные данные, а, наоборот, предполагают их поочередную подачу на вход структуры. В этой работе предложен метод синтеза структур рассматриваемого вида, приводятся верхняя и нижняя оценки функции Шеннона, совпадающие при числе переменных, равном степени двойки.
В )13] Кудрявцевым В.Б. рассматривается понятие прямоугольной логической сети, ориентированной на реализацию одной и той же вычислительной процедуры, применяемой к различным входным
3
данным, подаваемым на входы логической сети в последовательные моменты времени. Прямоугольные логические сети представляют собой сети из простейших автоматов (автоматов, реализующих элементы дизъюнкции, конъюнкции, отрицания, срабатывающие с задержкой в один такт, и элемент единичной задержки с нулевым начальным состоянием). Входы одних простейших автоматов подключаются к выходам других автоматов или к входам всей схемы при помощи мгновенно срабатывающих проводников, после чего вся сеть укладывается на плоскую прямоугольную целочисленную решетку таким образом, чтобы простейшие автоматы были размещены в узлах решетки, а проводящие элементы проходили по вертикальным и горизонтальным линиям, параллельным ее сторонам. Выходы некоторых элементов сети объявляются выходами всей сети, и считается, что прямоугольная логическая сеть реализует оператор Р, если при подаче в моменты времени £ = 0,1,2,... на входы сети наборов сто, ах, сг2,..на ее выходах в моменты времени Ь = £о, £о + 1, £о + 2,... будут вычисляться значения ^((7о), /г(<т1), Р(ог), — Таким образом, прямоугольные логические сети функционируют в ’’конвейерном” режиме, при котором на. ”конвейерный” вход сети подаются входные данные, а через некоторое время £о на ”конвейерном” выходе вычисляются результаты применения оператора Р к этим входным данным. Кроме времени задержки £о рассматриваются и другие сложностные характеристики сети, а именно площадь, занимаемая сетью, и радиус мгновенного действия, т.с. длина максимальной проводящей цени, связывающей вход одного простейшего автомата с выходом другого. В [13] построены примеры реализации простейших математических операций прямоугольными логическими сетями.
Модель конвейерного вычислительного устройства, аналогичная модели из [13], исследовалась в работах [1, 2, 3]. В этих работах рассматривалась задача реализации последовательностных операторов посредством автоматных схем, функционирующих в режиме конвейера. Эти автоматные схемы, т.е. схемы из функциональных элементов и единичных задержек, в последовательные моменты времени получают на свои входы наборы входных значений, применяют к ним один и тот же оператор и через некоторое время (время вычисления) также последовательно выдают результаты вычислений. В [1, 2, 3] была предпринята попытка оценить характеристики сложности автоматной реализации для двух конкретных операторов, а именно оператора умножения двух У-разрядных чисел и оператора сортировки
4
N К~разрядных чисел. В частности, рассматривались две меры сложности автоматных схем: время вычислений и число элементов (т.е. сложность автоматной схемы), и была выявлена взаимосвязь между временной и объемной характеристиками сложности для вышеуказанных операторов. Для операторов умножения и сортировки была получена функция, определяющая зависимость времени работы схемы от ее объема (числа ее элементов). В указанных работах приведены методы синтеза, позволяющие получать как схемы с большой сложностью и малым временем вычисления, так и схемы с малой сложностью и большим временем вычисления.
Многокритериальная оптимизация неоднократно встречалась в различных исследованиях, касающихся сложности управляющих систем.
Классической работой в этой области можно считать работу Лупа-нова О.Б. [28]. В ней рассматривается задача массового синтеза схем из функциональных элементов, реализующих функции алгебры логики и построенных в произвольном полном конечном базисе. Каждому элементу из базиса поставлены в соответствие две положительные характеристики: вес и задержка. Сложностью L(S) и задержкой T(Sj схемы S объявляются соответственно сумма весов всех ее элементов и сумма задержек элементов, лежащих на любой цепи, соединяющей любой из входов схемы с выходом. Корректность определения задержки схемы следует из того, что автором рассматриваются только ’’правильные” схемы, т.е. схемы, у которых все цепи, соединяющие какой-либо вход с выходом, имеют одну и ту же задержку. Вводятся функции L(n) и Т(п), являющиеся функциями Шеннона для сложности и задержки реализации функций алгебры логики ’’правильными” схемами из функциональных элементов. В работе доказано, что для любого € > О И любой функции алгебры ЛОГИКИ f(x 1,Х2,...,Хп)
от достаточно большого числа аргументов существует ’’правильная” схема 5, реализующая / и такая, что
L(S) < (1 + e)L(n), T(S) < (1 + e)T(n).
Таким образом, в рассматриваемой задаче массового синтеза с двумя параметрами оптимизации: сложностью и глубиной, удается достичь одновременно как асимптотически паи лучшей сложности, так и асимптотически наилучшей глубины.
Однако одновременной оптимизации сразу нескольких параметров управляющих систем удается достичь далеко не всегда. В частности, такой эффект был выявлен в работе Альбрехта [38]. Автором исследовались схемы из функциональных элементов, реализующие функции
5
алгебры логики. В качестве параметров оптимизации рассматривались число функциональных элементов, составляющих схему, и площадь, занимаемая схемой, и было выявлено, что наилучшие по сложности схемы нс всегда могут быть компактно размещены на плоскости и наоборот.
Как правило случается так, что путем увеличения одной из сложностных характеристик управляющих систем можно добиваться уменьшения других. В этом случае характеристики сложности управляющих систем выступают как параметры-антагонисты, и задачу массовой) синтеза можно сформулировать несколько иным образом. Задачу массового синтеза можно поставить как изучение поведения (асимптотики) функции Шеннона 1/(п,Г1,г2)... ,гт) для той или иной характеристики сложности при растущем значении аргумента п и при различных ограничениях п,Г2,... ,гт на другие меры сложности.
Решению подобных задач было посвящено немало работ.
В [4] Власкиным В.М. исследовалась связь между сложностью и глубиной схем из функциональных элементов, реализующих так называемые ступенчатые функции в базисе, состоящем из элементов конъюнкции и дизъюнкции. Как оказалось, при синтезе схем, вычисляющих ступенчатые функции, сложность и глубина схемы выступают как параметры-антагонисты. Под сложностью схемы подразумевалось количество элементов в ней, а под глубиной - длина максимальной ориентированной цепи. Ступенчатая функция была определена как функция, которая равна нулю на каком-либо числе первых наборов значений своих переменных (если их лексикографически упорядочить) и равна единице на остальных наборах. Пусть а - некоторый набор из 0 и 1 длины п. Обозначим через На(х\,..., хп) ступенчатую функцию, которая равна нулю на тех и только тех наборах значений переменных хп, которые лексикографически меньше, чем а.
Обозначим через К (а) число групп подряд идущих нулей в наборе а, а через Т(На) и Ь(1га,Т) соотвестветшо минимальную глубину схемы из функциональных элементов, реализующей функцию На, и сложность реализации этой функции схемами с глубиной, не превышающей Т. Автором было доказано, что для любой ступенчатой функции /га, существенно зависящей от всех своих переменных, и для любого Т > Т(Иа) выполняется нижняя оценка
£(/1*,Т) + 0.5Т > п + К (а) - 1.
С другой стороны, им была получена верхняя оценка: для любой последовательности ступенчатых функций /^*(яъ • • • > хп), п —> ос, при
6
- Київ+380960830922