Содержание к диссертации
Список обозначений 6
Введение 7
Часть 1. Основные математические модели
цифровых интегральных схем 21
Глава 1. Вычислительные и управляющие логические
устройства: основные понятия, определения, задачи . . 21
1.1. Основные модели 22
Булевы функции 22
Конечные автоматы. Схемы из функциональных элементов и управляющие программы 24
Декомпозиция и минимизация булевых функций .... 25
Монотонные системы и надежность 27
Базисы 31
Общие вопросы синтеза дискретных логических устройств 33
Методы синтеза схем из функциональных элементов . . 35
1.7. Постановка задач 44
Глава 2. Методы многошаговой декомпозиции булевых
функций. Функционалы качества 46
Основные модели 46
Методы декомпозиции булевых функций 48
Основные функционалы качества. Оптимизация 50
Глава 3. Булевы функции и их математико-информационные
модели 57
Формулы, их строение и компьютерное представление . 57
Отношения на множестве канонических формул. Разбиение множества формул на классы эквивалентности. Упорядочивание формул 64
Конструктивные операции над формулами 66
Порождающие и порожденные формулы 70
Точные оценки мощности некоторых подклассов бесповторных формул, порожденных данной 71
Часть 2. Многокритериальная оптимизация синтеза
цифровых интегральных схем. Аналитическое
решение
Глава 4. Структурно-функциональная декомпозиция
в классах функций &, v, Ф и <-> 76
Параллельная декомпозиция. Функционалы качества... 76
Последовательная декомпозиция. Функционалы качества 85
Анализ показателей качества параллельной
и последовательной декомпозиции 87
Глава 5. Структурно-функциональная параллельная
декомпозиция в классах полиномов Жегалкина, ДНФ
и КНФ 92
5.1. Моделирование одного шага декомпозиции
произвольной булевой функции 92
5.2. Функционалы качества 94
5.3 Принцип двойственности и декомпозиция 104
Минимизация числа функций отрицания в классе ДНФ.. 105
Способы декомпозиции. Математическая модель декомпозиции одной функции 106
Исследование математической модели (базовый случай). Области минимизации показателей качества декомпозиции 108
Глава 6. Анализ глубины произвольных булевых функций в
стандартных базисах на основе параллельной
декомпозиции 119
Конструктивные операции над строением булевой формулы 119
Зависимость между значениями сложности и минимальной глубины бесповторной булевой формулы . 122
Минимальная глубина бесповторной формулы и разбиения числа ее переменных на положительные
целые слагаемые 132
Продолжение исследования минимальной глубины бесповторной булевой формулы 134
Основная зависимость минимальной глубины произвольной булевой формулы от ее сложности .... 141
Глубина некоторых симметрических функций 144
Верхние оценки показателей качества декомпозиции в произвольном базисе 146
Глава 7. Синтез схем из функциональных элементов и
управляющих программ на основе структурно- 149
функциональной декомпозиции
Минимизация схем по сложности и глубине 149
Минимизация числа транзисторов и времени задержки
схем и числа команд в управляющих программах .... 153
7.3. Надежность схем из функциональных элементов.
Математические модели 158
Часть 3. Многокритериальная оптимизация синтеза
цифровых интегральных схем на основе
математического моделирования 175
Глава 8. Моделирование структурно-функциональной
параллельной декомпозиции системы булевых
функций. Алгоритмы 175
8.1. Оптимизирующие логико-комбинаторные
преобразования 176
Удаление фиктивных переменных 176
Минимизация булевых функций. Скобочные формулы 177
Частичные булевы функции 183
Моделирование декомпозиции произвольной булевой функции на основе функционалов качества 184
Моделирование совместной декомпозиции систем булевых функций в базисе общего вида. Минимизация сложности 194
Моделирование декомпозиции булевой функции в двухместном базисе. Минимизация глубины 199
8.5. Анализ глубины схемы в различных базисах 204
Глава 9. Математическое моделирование синтеза в базисе
микросхем 206
Математические модели микросхем 206
Минимизация числа логических элементов 210
Минимизация глубины схемы 214
Синтез комбинационных автоматов в базисе ПЛМ .... 215
Методика программной реализации алгоритмов логического управления 218
Описание программ 220
Результаты вычислительного эксперимента 223
Часть 4. Приложения теории цифровых автоматов . . . 227
Глава 10. Логическое управление цикловым манипулятором . . 227
Основные понятия 227
Цикловой манипулятор 231
Принцип геометрического кодирования положения звеньев манипулятора 231
Управление манипулятором 233
Цикловой манипулятор как конечный автомат 235
Регулятор как конечный автомат 235
Простейший манипулятор 238
Глава 11. Основные дискретные математические модели для обеспечения безопасности движения летательных
аппаратов 248
Историческая справка 248
Основные понятия и обозначения 250
Математическая модель оптимального разведения в пространстве двух летательных аппаратов 251
Классификация случаев для установившегося полета ... 255
Движение по одной прямой 255
Движение по пересекающимся траекториям
(без прямого столкновения) 258
11.4.3. Движение по пересекающимся траекториям
(с возможным столкновением) 260
Общий случай разведения 262
Классификация случаев для ситуации взлет-посадка . . 264
Цифровой автомат для управления движением летательного аппарата 264
Заключение 269
Литература 274
Приложения 297
Приложение 1. Некоторые числовые функции 297
Приложение 2. Тексты программ декомпозиции булевых функций . 302
Приложение 3. Технические материалы по внедрению результатов
диссертационной работы 319
УКАЗАТЕЛЬ ОБОЗНАЧЕНИЙ
X=(xj,...,xnJ, neN- множество булевых переменных; W- множество конструктивных операций; w - имеющийся, единственный способ;
wt - способ проведения декомпозиции для отдельного і-го шага; w - упорядоченный набор, состоящий из применяемых способов для отдельных шагов (У, є W)\
W* - множество способов проведения полной декомпозиции (упорядоченных наборов конечной длины);
G* - множество упорядоченных наборов конечной длины базисных функций, из которых состоит суперпозиция;
y=f(X), f(xi,...,xn), f(n} или/- булева функция, зависящих от п переменных.
/ - формула, представляющая булеву функцию у —f(X) F - суперпозиционная формула, получаемая в результате декомпозиции функции /
Lp(f,g,w) imuL(F) - число функций в суперпозиции (число подформул в суперпозиционной формуле F), получаемой при помощи декомпозиции способом W.
Depf(f,g,w) или Dep(F) - глубина получаемой суперпозиционной формулы F; Ььф - число вхождений символов переменных в формулу;
L*s(f>8) число букв формулы /, которые при ее декомпозиции используются в записи формулы g ( характеристика шага декомпозиции);
G = {g0 = 0, gl = 1, (2П2)...,В(кПк)}-бэзис.
Введение к работе
Актуальность темы. Системы автоматического управления сложнейшими объектами и процессами, интеллектуальные пакеты прикладных программ, системы планирования вычислений, системы автоматизированного проектирования, экспертные системы - вот далеко не полный перечень аппаратных и программных систем, без которых немыслим сейчас научно-технический прогресс. Для всех таких и многих остальных систем общим является то, что они содержат или используют дискретные устройства обработки информации и управления (вычислительные и управляющие, логические устройства). Основная черта, выделяющая эти системы из остальных, состоит в том, что они содержат знания о проблемной области, в которой работают, и о своих возможностях по решению задач в ней [89].
Особое место в указанном списке занимают вычислительные системы. Взаимоотношения выше перечисленных систем с вычислительной техникой имеют две различные стороны: ЭВМ является основным инструментом исследований, включая моделирование, и будучи сами сложными системами выступают важными объектами исследований, при этом обязательно рассматриваются вопросы организации управления вычислительным процессом [52-55].
В значительной мере для описания, анализа и проектирования этих систем (устройств) используется аппарат математической кибернетики [26, 53-55, 116, 184, 196], из которого в диссертации, в основном, делается акцент на: формулы алгебры логики, реализующие булевы функции в данном базисе; схемы из функциональных элементов, реализующие системы булевых функций в данном базисе; конечные автоматы, реализующие преобразования входных последовательностей в выходные; программы (алго-
ритмы), вычисляющие заданные формулы по исходным данным. Поэтому этот математический аппарат является мощным средством для моделирования, при котором достаточно точно копируется не только функция объекта (процесса), но также и его структура, схема.
Заметим, что проектирование (аппаратное и программное) устройств обработки информации и систем логического управления в настоящее время характеризуется широким использованием достижений микроэлектроники. Элементной базой синтеза являются интегральные схемы малой, средней, большой, сверхбольшой и улыраболыпой степени интеграции (МИС, СИС, БИС, СБИС, УБИС). Тенденция к увеличению степени интеграции микросхем, сохраняющаяся в микроэлектронике, привела к созданию уже ультрабольших интегральных схем [3, 6, 16, 17, 24, 26, 64, 65, 81, 88,98-100, 118, 137, 138, 140,141,184, 189,215-219,291,293].
Создалась парадоксальная ситуация. Стремительное развитие микроэлектроники, проявляющееся в постоянном совершенствовании и в создании новых элементов базиса, содержащего микросхемы различной степени интеграции и различные микропроцессорные средства, с одной стороны, создает благоприятные предпосылки для разработки новых высокопроизводительных ЭВМ, вычислительных и управляющих систем с высокой степенью параллелизма обработки данных, а с другой стороны, ставит ряд трудно решаемых проблем перед разработчиками этой техники в отношении рационального использования всех имеющихся возможностей этого базиса [3, 16, 24, 26, 61, 63-65, 80, 88, 98, 99, 118, 127, 144, 154, 198, 213, 215, 216, 217, 291]. Алгоритмы функционирования управляющих устройств (алгоритмы логического управления - АЛУ) реализуются также программно на основе программируемых логических контроллеров [7, 116, 117,137,138,140,141, 247, 284, 285].
В практике все шире применяются БИС, СБИС и УБИС. Это объясняется их возможностями и технико-экономическими характеристиками.
Но чтобы не принять необоснованную позицию в отношении использования БИС и других интегральных схем, в проектировании вычислительной и управляющей техники, обратимся к рекомендациям американского специалиста S.Muroga в монографии, посвященной проектированию БИС и СБИС, [144]: "...В некоторых случаях при создании цифровых систем предпочтительнее использовать схемы малой и средней степени интеграции, а не большой и сверхбольшой.
... Решение об использовании МИС, СИС или БИС принимается с учетом многих факторов.
... Благодаря гибкости и другим свойствам МИС и дискретных устройств потребность в них вряд ли исчезнет.
... Использование программируемых логических матриц (ПЛМ) существенно уменьшает время разработки благодаря применению процедуры минимизации, которая поддается автоматизации и может быть осуществлена с помощью САПР. Упрощается в этом случае и топологическая схема, что связано с регулярной структурой ПЛМ. В противоположность этому при логическом проектировании на основе нерегулярных логических схем временные затраты больше, но характеристики ИС, изготовленных подобным образом, лучше, а размеры кристалла меньше. При логическом проектировании в каждом случае необходимо сравнивать различные подходы к проектированию, оценивая, что мы выигрываем и что теряем".
Чтобы спроектировать эффективную интегральную схему, разработчик должен продумать широкий спектр вопросов - от исходного алгоритма работы интегральной схемы до ее топологии на кристалле [328], т.е. получить решение ряда задач аппаратной реализации булевых функций (синтеза логических схем). Ситуацию, сложившуюся в этой области, можно охарактеризовать следующим образом: "Нет способов приемлемой трудоемкости, позволяющих оптимальным образом реализовать каждую схе-
му" [292]. Причиной этому является возрастающая сложность проектируемых систем.
Отметим еще мнение авторов монографии [292]: "... В практике разработки АСУ наметилась эволюция традиционных методов проектирования, постепенно, по мере усложнения систем, адаптирующаяся к новым особенностям задач и возможностям используемой дискретной техники.
...На смену эволюционному подходу к проектированию должен прийти более прогрессивный, учитывающий новое качество - сложность проектируемых систем".
Вначале уточним, что мы понимаем под термином "сложность" с тем, чтобы получить возможность измерять или сравнивать сложности различных классов систем (объектов, процессов) [292]. Сложность задачи может характеризоваться размерностью - числом переменных, необходимых для описания функционирования системы. Сложность функционирования системы определяется минимальным временем, минимальной памятью или предельными значениями других характеристик. Задачи проектирования порождают и другие показатели сложности: уменьшение площади кристалла; уменьшение глубины схемы; уменьшение суммарной длины проводников между БИС и в них между элементами и числа пересечений этих проводников; увеличение плотности упаковки элементов в больших интегральных схемах; повышение надежности схем и др. При логическом проектировании комбинационных схем под сложностью схемы понимают минимальное число элементов заданного базиса, позволяющее реализовать любую булеву функцию [120-123]. Для логического проектирования БИС можно минимизировать сложность проектированного устройства при заданном быстродействии или минимизировать время выполнения операций при заданной сложности [118], а также число транзисторов в схеме [91, 189]. При программной реализации булевых функций, как
правило, минимизируются показатели сложности программ: время их работы и память [69-71, 109-112].
Метод решения, реализующий сложность, является в некотором смысле наилучшим, наиболее экономным, наиболее простым из методов, решающих все задачи рассматриваемого класса [292].
Оценивание тех или иных показателей сложности, компонент вектора сложности класса систем (или класса задач), зависит от огромного числа факторов, с которыми каким-либо образом связаны исследуемые сложные системы. Это представляет собой необозримую задачу. Еще сложнее обстоит дело с проектированием. Вряд ли можно рассчитывать на разработку универсальных методов проектирования достаточно широких классов систем, об оптимизации уже не говорят [292].
В то же время "идея оптимизации, стремление к оптимальным, а не к любым допустимым решениям глубоко пронизывают современное проектирование. ... Оптимизация решения на этапе организации проектирования экономит время и средства "[292].
Быстродействие (составляющая производительности) является одной из тех важнейших характеристик, которые служат для сравнения и выбора той или иной ЭВМ. Повышение быстродействия достигается разными средствами. Если рассматривать методы и алгоритмы, то последнее время характеризуется значительным числом работ, посвященных методам синтеза и оптимизации многоуровневой комбинационной логики [59, 61, 64, 65, 328]. Если рассматривать технические средства, то, например, наблюдается повышенный и обоснованный интерес к использованию оптических элементов, реализующих функции И, ИЛИ, НЕ-И или НЕ-ИЛИ, для синтеза комбинационных схем [329].
"При проектировании СБИС невозможно скомпенсировать на более поздних этапах все дефекты, которые были допущены на ранних этапах.
При этом проблему быстродействия необходимо учитывать и решать на всех уровнях и этапах проектирования" [328].
Трудоемкость решения экстремальных задач различных классов часто оценивается минимальным числом операций, необходимых для решения с заданной точностью любой задачи класса. Теория сложности, основанная на подобных оценках, носит название машиннозависимой. Машин-нонезависимую оценку трудоемкости решения экстремальных задач непрерывных классов получают в терминах информационной сложности. Классы дискретных экстремальных задач разделяют по вычислительной сложности на две группы: с полиномиальной и с экспоненциальной сложностью. Можно ожидать, что рассматриваемые задачи характеризуются экспоненциальной сложностью. Трудоемкость их решения астрономически растет с размерностью (числом переменных) этих задач, что, в свою очередь, негативно сказывается на качестве решения. Поэтому необходимо раньше вводить и тщательно изучать различные показатели, характеризующие качество решения.
В подтверждение этому в [118] отмечается, что функциональная избыточность современных базисов и большая размерность практических задач в большинстве случаев не позволяет получить точное решение одно-критериальной задачи за приемлемое время даже на высокопроизводительных ЭВМ.
Тем не менее, целью разработчиков больших интегральных схем является создание эффективных методов синтеза схем как наиболее экономных (в смысле, определяемом выбранным показателем сложности) методов, гарантирующих требуемое качество решения любой задачи класса. Построение методов эффективного синтеза класса систем предполагает умение вычислять или оценивать сложность соответствующего класса задач. Оценка сложности класса задач или систем трудоемкая работа, сохраняющая свою актуальность в настоящее время [292].
Цель работы. Оптимальная (по различным показателям качества и по трудоемкости) реализация систем булевых функций в разных базисах представляет собой несомненно актуальную проблему, решение которой теснейшим образом связано с синтезом вычислительных и управляющих логических устройств в базисах микросхем различной степени интеграции и, можно сказать, обобщая другие приложения, прямо или косвенно положительно влияет на успехи в научно-производственной человеческой деятельности. Решение проблемы связывается с проведением исследований в следующих направлениях, определяющих тематические рамки диссертации.
Разработка математических моделей для компьютерного представления булевых функций и на их основе различных преобразований, включая декомпозицию в разных базисах.
Создание математических моделей, которые позволили бы, не синтезируя самой булевой формулы (или схемы из логических элементов), дать оценку возможности синтеза для различных показателей качества в зависимости от исходных данных.
Исследование множества всех булевых функций с целью их экономного представления в различных базисах, включая минимизацию по сложности и глубине, а также установление зависимости между сложностью булевых формул (с повторением и без повторения переменных) и их минимальной глубиной.
Разработка методов многокритериальной оптимизации (по сложности, по быстродействию и другим показателям качества; с ограниченной трудоемкостью) синтеза вычислительных и управляющих логических устройств в базисе микросхем на основе математического моделирования и проведение вычислительных экспериментов.
Научная новизна. Стержневую роль в диссертации играет разработка математических моделей для различных объектов и процессов, начи-
нающаяся с представления исходных данных в виде определенных структур, на основе которых определяются операции и проводятся все исследования, и завершающаяся на этапе синтеза устройств.
В диссертации можно выделить два фундаментальных понятия общей теории систем - это структура (строение) и декомпозиция [88, 136], благодаря которым в определенных рамках получено решение проблемы оптимальной или близкой к ней (по числу транзисторов, логических элементов, микросхем; глубине и др.) реализации булевых функций в базисе микросхем. Использовались эти понятия по-новому. В диссертации строение это основа математико-информационного (многоуровневого) описания булевой формулы (и бесповторной функции); многоуровневое описание булевых формул, предполагающее использование всех или определенных уровней для решения той или иной поставленной задачи, является новым [232, 252, 279]. Например, для нахождения глубины бесповторной булевой функции в двухместном базисе (конъюнкция и сложение по модулю два) достаточно знать ее строение [279, 280].
Методы синтеза схем на основе функциональной декомпозиции известны [16, 26-28, 39, 55, 70, 159, 164]. Отличие их (и других) от методов, предлагаемых в диссертации, состоит в подходе к самой декомпозиции и отсутствием достаточной степени (уровней) формализации функций. Как следствие, в них вопросы оптимизации качества по сложности (числу базисных элементов), глубине и другим показателям качества схем для вычислительных и управляющих логических систем остаются открытыми.
В диссертации определен принципиально иной подход к декомпозиции, т.е. декомпозиция есть явный многошаговый процесс преобразования функции (в суперпозицию функций) в заданном базисе и выполняемая она на основе строения функции или формулы становится структурно-функциональной декомпозицией. Таким образом, результат декомпозиции зависит от конкретной функции, базиса и способа преобразования. Это
позволило для основных показателей сложности - числа подформул и глубины - определить функционалы (показатели качества декомпозиции) для каждой конкретной булевой функции из множества всех булевых функций (зависящих от любого конечного числа переменных), на множестве базисов и способов декомпозиции (вариантов преобразований). Из других методов, характеризующихся получением оценок, являются асимптотические методы [8-13, 120-123, 210-212]. Однако данный подход к получению оценок сложности отличается от подходов, характеризующихся получением асимптотических оценок уже тем, что в них функционалы качества используют функцию Шеннона и определяются они не для конкретной функции, а для множества всех функций от п переменных. Особо отметим, что для методов, развиваемых в диссертации, функционалы качества определяются для каждой конкретной функции, но результат (минимальный или близкий к нему, аналитически или на основе математического моделирования) получается для отдельных классов функций. При этом в основу данного подхода заложены различные модели декомпозиции булевых функций, которые можно сравнивать и выбирать требуемую модель на основе значений их показателей качества.
Перечислим по главам полученные впервые и освещенные в диссертации научные результаты.
