Кратчайшие допустимые разбиения в синтезе и компоновке схем логического управления тема диссертации и автореферата по ВАК РФ 05.13.01, доктор технических наук Оранов, Александр Михайлович

• Оранов, Александр Михайлович
• доктор технических наук
• 1999

Оглавление диссертации доктор технических наук Оранов, Александр Михайлович

Введение.

1. Обзор методов синтеза и компоновки схем на современной элементной и конструктивной базе.

1.1. Обзор методов синтеза цифровых схем на базе ПЛИС.

1.2. Обзор методов компоновки схем в заданные ячейки.

2. Допустимые разбиения и проектирование схем на современной элементной и конструктивной базе.

2 1. ЗКДР, ее приложения и метод решения.

2.1.1. ЗКДР и ее приложения.

2 1.2. Возможные методы решения ЗКДР.

2.1.2.1. Метод полного перебора.

2.1.2.2. Методы 0-1 программирования.

2.1.2.3. Метод ветвей и границ.

2.1.2.4. Метод сокращенного обхода дерева поиска.

2.1.3. Обоснование выбора метода решения ЗКДР.

2.1.4. Особенности построения иерархии подзадач ЗКДР и изложения алгоритмов их решения.

2.2. Построение кратчайших монотонно-допустимых разбиений.

2.2.1. Постановка задачи.

2.2.2. Параметры метода.

2.2.2.1. Алгоритмы начального разбиения.

2.2.2.2. Алгоритм перечисления допустимых подмножеств.

2.2.2.3. Операция сокращения.

2.2.2.4. Граничная функция.

2.2.2.5. Доказательство допустимости алгоритма перечисления и операции сокращения.

Допустимые разбиения и синтез одноярусных комбинационных схем в базисах ПМВ, ПЗУ, ПЛМ.

3.1. Построение допустимых разбиений.

3.1.1. Постановка задачи.

3.1.2. Параметры метода.

3.1.2.1. Алгоритмы начального разбиения.

3.1.2.2. Алгоритм перечисления допустимых подмножеств.

3.1.2.3. Операция сокращения.

3.1.2.4. Граничная функция.

3.1.2.5. Доказательство допустимости алгоритма перечисления и операции сокращения.

3.1.3. Пример построения кратчайшего допустимого разбиения.

3.2. Синтез одноярусных комбинационных схем в базисах

П.МВ, ПЗУ, ПЛМ.

3.2.1. Постановка задали.

3.2.2. Метод решения.

Допустимые разбиения и синтез цифровых схем в базисе неоднородных НМЛ.

4,1. Построение допустимых разбиений.

4.1.1. Постановка задачи.-.

4.1.2. Параметры метода.

4.1.2.1. Алгоритмы начального разбиения.

4.1.2.2. Алгоритм перечисления допустимых

I ¡одмножеств. 7В

4.1.2.3. Операция сокращения.

4.1.2.4. Граничная функция.

4.1.2.5. Доказательство допустимости алгоритма перечисления и операции сокращения.

4,13, Пример построения кратчайшего допустимого разбиения.

Л 2. Синтез цифровых схем в базисе неоднородных ПМЛ.

4.2.1. Постановка задачи.

4.2.2. Метод решения.

5. Допустимые разбиения и синтез цифровых схем в базисе однородных ПМЛ с универсальными макроячейками.

5.1. Построение допустимых разбиений.

5.1.1. Постановка задачи.

5.1.2. Параметры метода.

5,1.2.1. Алгоритмы начального разбиения.

5.! 2.2. Алгоритм перечисления допустимых подмножеств.

5 1.2.3. Операция сокращения.

5.1.2.4. Граничная функция.

5.1.2.5. Доказательство допустимости алгоритма перечисления и операции сокращения.

5.1.3. Пример построения кратчайшего допустимого раз биения. —.

5.2. Синтез цифровых схем в базисе однородных ПМЛ с универсальными макроячейками.

5.2.1. Постановка задачи.

5.2.2. Метод решения.

6. Допустимые разбиения и компоновка схем в ячейки, различные по вместимости или по числу выводов.

6 .1. Построение допустимых разбиений.

6.1.1. Постановка задачи.

6 « 2. Параметры метода.

6.1.2.1. Алгоритмы начального разбиения.

6.1.2.2. Алгоритм перечисления допустимых подмножеств.

6.1.2.3. Операция сокращения.

6.1.2.4. Граничная функция.

6.1.2.5. Доказательство допустимости алгоритма перечисления и операции сокращения.

6Л.З. Пример построения кратчайшего допустимого разбиения.

6.2. Компоновка схем в ячейки, различные по вместимости или по числу выводов.

6.2.1. Постановка задачи.

6.2.2. Метод решения.

7. Допустимые разбиения и компоновка схем в ячейки с заданным элементным составом.Л

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

7,1 1. Постановка задачи.

7.1.2. Параметры метода.

7.1.2.1. Алгоритм начального разбиения.

7.1.2.2. Алгоритм перечисления допустимых подмножеств.

7.1.2.3. Операция сокращения.

7.1.2.4. Граничная функция.

7.1.2.5. Доказательство допустимости алгоритма перечисления к операции сокращения.

7.1.3. Пример построения кратчайшего разбиения, допустимого д.,н частично упорядоченного допускающего множества.

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

7.2.1. Постановка задачи. 2.2. Параметры метода.

7:2.2.1. Алгоритм начального разбиения.

7.2.2.2. Алгоритм перечисления допустимых подмножеств.

72 2.3. Операция сокращения.

7.2.2-4. Граничная функция.

7.2.2.5. Доказательство допустимости алгоритма перечисления и операции сокращения.

7.2.3. Примеры построения кратчайших разбиений, допустимых д ня линейно упорядоченных допускающих множеств. 144 , 3. Построение разбиений, допустимых для специального допускающего множества.

73.1. Постановка задачи.

7.3.2. Параметры метода.

7.3.2.1. Алгоритм начального разбиения.

7.3.2.2. Алгоритм перечисления допустимых подмножеств.

13.23. Операция сокращения.

7-3-2.4. Граничная. Функция.

• • • I А л

7,3.2.5. Доказательство допустимости алгоритма перечисления и операции сокращения.

-77.3.3. Пример построения кратчайшего разбиения, допустимого для специального допускающего множества.

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

7.5. Компоновка схем в ячейки с заданным элементным составом.

7.5.1. Постановка задачи.

7.5.2. Метод решения.

8. Сложность задач разбиения, и качество алгоритмов их решения.

8 1. Сложность задач.

8,2. Оценки погрешности алгоритмов начального разбиения.

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

авгоматизированного проектирования (САПР) УЛУ, представляющая собой современный инструмент проектирования УЛУ. САПР призвана обеспечить быстрое и качественное проектирование конкурентоспособных устройств. Для этого она должна обладать многими полезными, часто противоречивыми, свойствами (качествами), в том числе: высоким быстродействием и высокой степенью приближения доставляемых проектных решений к оптимальным, быть простой в освоении и эксплуатации, осуществлять проектирование на современной элементной и конструктивной базе УЛУ и быть относительно устойчивой к изменениям этой базы, т.е. количество целиком или частично обновляемых алгоритмов и программ в САПР при таких изменениях должно быть невелико и работа по их обновлению должна быть технологичной и быстрой. Все эти свойства, и в первую очередь перечисленные, определяются, главным образом, структурой подзадач задачи проектирования и алгоритмами их решения. Многие из них в значительной степени определяются выбранной средой программирования алгоритмов и техническими средствами выполнения программ и лишь некоторые из них в какой-то мере определяются искусством и квалификацией программистов, создающих отдельные программы САПР и организующих их взаимодействие. Таким образом, глубокая фундаментальная разработка структуры подзадач задачи проектирования и алгоритмов их решения с целью создания, совершенствования и развития САПР, как инструмента проектирования, обладающего всеми перечисленными свойствами, и, в конечном счете, с целью сокращения сроков проектирования, повышения качества и конкурентноспособности создаваемых управляющих устройств представляется вполне актуальной проблемой.

Традиционно важными подзадачами задачи проектирования УЛУ являются задачи синтеза и компоновки их схем. Именно они и алгоритмы их решения подвержены наибольшим изменениям при изменении элементной и конструктивной базы УЛУ, что, в свою очередь, ведет к необходимости существенных изменений в САПР УЛУ.

За последние десятилетия элементная база УЛУ при относительной стабильности конструктивной базы УЛУ прошла в своем развитии путь от элементов малой степени интеграции, примером которых могут служить интегральные микросхемы серий К133, К155 и т.п. [1,2], до интегральных микросхем большой и сверхбольшой степени интеграции, т.е. до БИС и СБИС, среди которых видное место занимают программируемые логические интегральные схемы (ПЛИС) [3-7] или, другими словами, программируемые логические устройства (ПЛУ) - Programmable Logic Devices (PLD), в том числе такие их разновидности, как программируемые логические матрицы (Г1ЛМ) - Programmable Logic Arrays (PLA), программируемые постоянные запоминающие устройства (ППЗУ), или просто (ПЗУ), - Programmable Read Gnly Memory (PROM) и программируемые матрицы логики (ПМЛ) -Programmable Array Logics (PAL).

Относительная стабильность конструктивной базы УЛУ состоит в том, что набор основных характеристик того или иного современного конструктивного узла, несмотря на миниатюризацию, стандартизацию и унификацию, остается таким же, как и десятилетия назад, и включает такие характеристики, как вместимость узла, число его внешних выводов (контактов в разъеме) и номенклатура (элементный состав) узла. Обобщающим понятием для обозначения всего многообразия конструктивных узлов обычно служит понятие "ячейка". Различаются ячейки двух типов: 1) ячейки ограниченной вместимости и с ограниченным числом выводов и 2) ячейки с заданным элементным составом (с заданной номенклатурой). Примером ячеек первого типа могут служить типовые элементы замены (ТЭЗ), панели, рамы, стойки и т.п., а примером ячеек второго типа - микросхемы серий К133, К155 и т.п. [1,2], а также базовые ячейки на кристалле, составленные из нескоммутированных компонент - транзисторов, резисторов, диодов и т.п. [8-10]. Кроме того, условно, ячейкой с заданным элементным составом можно считать любую площадку с посадочными гнездами различной (в частности, прямоугольной) формы и квадратуры, а также любое помещение с отсеками различной (в частности, прямоугольной) формы и кубатуры.

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

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

В данной работе в качестве элементов заданного базиса в задаче синтеза наряду с ПЛИС указанных выше разновидностей допускаются причисляемые к ним здесь программируемые матрицы вентилей (11МВ), критерием качества синтезируемой схемы является число элементов в ней (чем оно меньше, тем лучше схема), а исходной формой описания оператора схемы служит система ДНФ булевых функций ограниченной параметрами базисных ПЛИС сложности. Выделяемое таким образом многообразие вариантов задачи синтеза, вместе с уже известными вариантами этой задачи, включает и некоторые впервые формулируемые варианты, в которых, в отличие от известных, базис состоит из нескольких, в том числе разнотипных ПЛИС, с различными значениями своих параметров и число принимаемых во внимание параметров базисных ПЛИС, а также параметров оператора синтезируемой схемы, теоретически не ограничено. В задаче компоновки в качестве ячеек заданного конструктивного базиса допускаются ячейки какого-либо одного из двух указанных выше типов ячеек и критерием качества компоновки является число затраченных ячеек (чем оно меньше, тем лучше компоновка). Выделяемое таким образом многообразие вариантов задачи компоновки, наряду с уже известными вариантами этой задачи, включает и некоторые впервые формулируемые варианты, в которых, в отличие от известных, конструктивный базис состоит из нескольких ячеек, различных по значениям своих параметров и число принимаемых во внимание параметров базисных ячеек, а также параметров элементов компонуемой схемы, теоретически не ограничено.

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

Методы исследования. Для достижения поставленной цели используются средства и методы дискретной математики (теории множеств, булевой алгебры, математической логики, комбинаторного анализа, теории синтеза управляющих систем), теории реляционных баз данных и теории ИР-полноты.

Научная новизна. Для всего многообразия выделенных вариантов задач синтеза и компоновки схем предлагается единая математическая модель - комбинаторная оптимизационная задача кратчайшего допустимого разбиения (ЗКДР) конечного множества (набора объектов), в рамках которой каждый конкретный вариант формулируется как подзадача ЗКДР. При этом казалось бы различные варианты задач синтеза и компоновки схем иногда сводятся к одной и той же подзадаче ЗКДР. Этим полностью подтверждается и проясняется в некоторых деталях высказанное в [11] предположение о комбинаторном сходстве задач синтеза и компоновки схем. Обсуждаются возможные методы решения ЗКДР, среди которых аргументированно выбирается метод сокращенного обхода дерева поиска [12-14], называемый далее для краткости Г-методом, и указываются способы его алгоритмизации применительно к различным подзадачам ЗКДР, имеющим прикладное значение. Тем самым предлагаются, как правило, точные алгоритмы решения этих подзадач ЗКДР и всех сводимых к ним вариантов задач синтеза и компоновки схем. ЗКДР, Г-метод ее решения и способ сведения к

ЗКДР того или иного варианта задачи синтеза или компоновки схем составляют суть предлагаемого общего подхода к решению обширного многообразия вариантов задач синтеза и компоновки схем. Этот подход, по сравнению с известными, позволяет шире и полнее использовать возможности современной элементной и конструктивной базы УЛУ для повышения качества проектируемых устройств и может служить основой для разработки все новых и новых стандартных (основанных на Г-методе) алгоритмов синтеза и компоновки схем при сохранении современных тенденций развития элементной и конструктивной базы УЛУ, в частности, при сохранении в составе элементной базы УЛУ "РАЬ-подобных" функциональных блоков, как это характерно для развития БИС СРЬО-семейства фирмы ХИЛЫХ [7]. Кроме того, есть основания полагать, что он применим не только в разработке УЛУ. Полученные в работе результаты по решению конкретных подзадач ЗКДР и, следовательно, всех сводимых к ним вариантов задач синтеза и компоновки схем демонстрируют собой примеры успешного применения этого подхода в проектировании УЛУ. С применением средств и методов теории ЫР-полноты [15] исследуется сложность всех сформулированных подзадач ЗКДР и качество предложенных алгоритмов их решения. В процессе этого исследования дополнительно выясняется, что сформулированные в данной работе подзадачи ЗКДР, в свою очередь, содержат подзадачи, эквивалентные таким известным задачам, как УПАКОВКА В КОНТЕЙНЕРЫ, МИНИМАЛЬНОЕ ПОКРЫТИЕ [15], О МАКСИМАЛЬНОМ ПАРОСОЧЕТАНИИ В ГРАФЕ [16] и др.

Практическая ценность. В целом можно утверждать, что в данной работе предлагается принципиально новое математическое и отчасти информационное обеспечение системы автоматического синтеза и компоновки схем на современной элементной и конструктивной базе, как части потенциальной САПР, обладающей в должной мере всеми перечисленными выше свойствами, в том числе высокоустойчивой к изменениям элементной и конструктивной базы УЛУ при сохранении современных тенденций ее развития. Все последующее изложение является детальной аргументацией этого тезиса, посредством систематизации и обобщения результатов, опубликованных ранее в [51-76] и составивших основу данной работы.

Реализация полученных результатов. Все полученные в диссертационной работе результаты можно разделить на две части: 1) результаты, полученные до 1995 г. и послужившие заделом для получения гранта РФФИ, и 2) результаты, полученные в течение 1995-1997 г.г., при финансовой поддержке РФФИ (грант 95-0100705). Наиболее ранние результаты по компоновке схем в ячейки с заданным элементным составом, относящиеся к первой части, были реализованы в САПР УЛУ ЦКБ "Алмаз" (г. Москва). Следующие за ними (по времени получения) результаты по синтезу одноярусных комбинационных схем в различных базисах ПЛИС типов ПМВ, ПЗУ, ПЛМ, также относящиеся к первой части, реализованы в настоящее время в виде экспериментальной распределенной САПР, в которой подзадача ЗКДР решается на удаленном компьютере высокой производительности, а сведение задачи синтеза к подзадаче ЗКДР и преобразование получаемого от удаленного компьютера разбиения набора объектов в схему осуществляется на местном компьютере меньшей производительности. Программа разбиения в составе этой САПР (программа решения подзадачи ЗКДР) испытана на нескольких десятках примеров различной сложности, в том числе, соответствующих примерам синтеза реальных устройств (так называемых "benchmarks"), что говорит о практической пригодности этой программы. Результаты, относящиеся ко второй части, отражены (реализованы) в промежуточных и итоговом отчетах по гранту, одобрены РФФИ и рекомендованы им для использования в промышленном производстве УЛУ.

Апробация работы. Все результаты [51-76], составившие основу данной работы, по мере их получения обсуждались на совместных семинарах кафедры математической логики и проектирования, кафедры программирования Томского государственного университета (ТГУ) и лаборатории синтеза дискретных автоматов Сибирского физико-технического института (СФТИ) при ТГУ. Кроме того, в разные годы они докладывались на всесоюзных или международных конференциях в г.г. Риге, Киеве, Москве, Минске, Новосибирске и Томске, что подтверждается соответствующими публикациями докладов [51,55,60,69,71-73] и тезисов докладов [62,66,67,70,76]. Прохождение отчетности по линии РФФИ и частичное использование результатов диссертации в учебном процессе при подготовке студентов соответствующих специальностей в ТГУ также можно считать апробацией диссертационной работы.

Структура и объем диссертации. Диссертация состоит из введения, восьми глав, заключения и списка цитированной литературы. Объем диссертации составляет 200 страниц текста, набранного в Word 6.0 (Шрифт - Times New Roman Суг, размер шрифта - 14 pi, межстрочный интервал - 1.5 строки), в том числе, титульный лист - 1 стр., оглавление - 6 стр., основной текст, включающий 6 рис. и 12 таблиц, - 183 стр., библиография из 76 наименований - 10 стр.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Оранов, Александр Михайлович

III. Результаты исследования сложности рассмотренных в работе задач, полученные с применением теории ЛУ-полноты [15] и сформулированные в главе 8 в виде пяти теорем о сильной МР~ трудности задач 2-6 и девяти утверждений о полиномиальной сложности одиннадцати частных случаев (подзадач [15]) задач 2-6.

IV. Оценки погрешности двух алгоритмов начального разбиения, установленные в главе 8 посредством двух теорем.

Каждый из алгоритмов решения задач 2-6 или их подзадач изложен как подробная "инструкция" для программистов, предусматривающая разделение труда между программистами разной квалификации. Так программирование алгоритма решения задачи разбиения (того или иного частного случая ЗКДР) не требует от программиста знаний в прикладной области (в данном случае в области проектирования схем логического управления), а программирование алгоритма представления прикладной задачи в виде ЗКДР и алгоритма преобразования разбиения в схему требует в той или иной мере наличия таких знаний.

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

-186-ЗАКЛЮЧЕНИЕ

В диссертации разработан общий подход к решению широкого класса задач синтеза и компоновки схем логического управления на современной элементной и конструктивной базе. Под современнной элементной базой понимаются программируемые пользователем логические устройства (Eield Programmable Logic Devices) или, другими словами, программируемые логические интегральные схемы (ПЛИС) такие, как программируемые логические матрицы (ПЛМ), программируемые постоянные запоминающие устройства (ППЗУ), программируемые матрицы логики (ПМЛ), а также программируемые матрицы вентилей (ПМВ). Под современной конструктивной базой понимаются ячейки ограниченной вместимости и с ограниченным числом выводов, а также ячейки с заданным элементным составом (номенклатурой). В роли первых могут выступать типовые элементы замены, панели, рамы, стойки и т.п., а в роли вторых - интегральные микросхемы отечественных промышленных серий таких, как К133, К155 и т.п. [1,2], базовые ячейки на кристалле, составленные из нескоммутированных компонент таких, как резисторы, транзисторы, диоды и т.п. [8-10], а также любые площадки с посадочными гнездами различной формы и квадратуры и любые помещения с отсеками различной формы и кубатуры. Подход ориентирован на автоматический синтез и компоновку схем логического управления и включает три основных элемента: 1 ) оригинальную общую математическую модель всех рассматриваемых в работе задач синтеза и компоновки схем - комбинаторную оптимизационную [15] задачу кратчайшего допустимого разбиения (ЗКДР) набора объектов, 2) известный метод сокращенного обхода дерева поиска [12-14], называемый здесь для краткости Г-методом, - как метод решения

ЗК'ДР; 3) оригинальный способ представления в виде ЗКДР различных задач синтеза и компоновки схем. В отличие от других подходов к решению этих задач, он обеспечивает более широкое использование возможностей современной элементной и конструктивной базы для уменьшения числа затрачиваемых на синтез и компоновку схем ПЛИС и ячеек, допуская наличие в базисе синтеза нескольких (в том числе разнотипных) ПЛИС с несравнимыми наборами значений их параметров и допуская в конструктивном базисе задачи компоновки несколько ячеек с несравнимыми парами значений вместимости и числа выводов. При этом не ограничивается число принимаемых во внимание параметров фигурирующих в задачах объектов (оператора синтезируемой схемы, представляемого системой ДНФ структурных функций выходов и функций возбуждения триггеров, базисных ПЛИС, схем, элементов схем, ячеек) и теоретически всегда гарантируется минимум числа затрачиваемых ПЛИС и ячеек. Решение той или иной конкретной задачи синтеза или компоновки схем на основе данного подхода, т.е. разработка алгоритма ее решения, состоит в выделении частного случая (подзадачи [15]) ЗКДР, алгоритмизации Г-метода применительно к этому частному случаю посредством подходящего определения значений (выражений) его параметров (множества алгоритмов начального разбиения, алгоритма перечисления, операции сокращения, граничной функции) и в указании способа представления решаемой задачи в виде выделенного частного случая ЗКДР, а также способа преобразования получаемого допустимого разбиения в схему. Подход может служить основой для разработки все новых и новых стандартных (основанных на /-методе) алгоритмов синтеза и компоновки схем при сохранении современных тенденций развития элементной и конструктивной базы, в частности, при сохранении в составе элементной базы цифровых устройств "РАЬ-подобных" функциональных блоков, как это характерно для развития БИС СРЬВ-семейства фирмы ХИЛЫХ [7]. Кроме того, есть основания г гола гать, что он применим не только в проектировании устройств логического управления.

На защиту выносятся:

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

II. Разработанные на его основе алгоритмы решения следующих задач:

1) построения кратчайших монотонно-допустимых разбиений наборов объектов;

2) синтеза минимальных по числу элементов одноярусных комбинационных схем, как допускающих, так и не допускающих объединение выходов своих элементов по схеме ИЛИ, в некоторых базисах ПЛИС типов ПМВ, ППЗУ, ПЛМ;

3) синтеза минимальных по числу элементов цифровых схем в базисе так называемых неоднородных ПМЛ (неоднородная ПМЛ -это предложенная в данной работе обобщенная структура (модель) некоторых реальных ПМЛ таких, как ПМЛ семейства РА1Л6К8 [6]);

4) синтеза цифровых схем в базисе гак называемых однородных ПМЛ с универсальными макроячейками (однородная НМЛ (ПЛИС) с универсальными макроячейками - это предложенная в [23] обобщенная структура (модель) реальных ПМЛ, выпускаемых фирмой АНега [3,4]);

-1895) компоновки схем в ячейки ограниченной вместимости и с ограниченным числом выводов;

6) компоновки схем в минимальное количество ячеек с заданным элементным составом.

Список литературы диссертационного исследования доктор технических наук Оранов, Александр Михайлович, 1999 год

1. Справочник по интегральным микросхемам/ В.В. Тарабрин, С В. Якубовский, Н.А Барканов и др. - 2-е изд., нерераб. и доп. - М.: Энергия, 1981. - 816 с.

2. Интегральные микросхемы: Справочник/ Б.В. Тарабрин, Л.Ф. Лунин, Ю.Н. Смирнов и др. М.: Радио и связь, 1983. - 528 с.

3. Коул Б.К. Второе поколение программируемых логических интегральных схем// Электроника. 1988. - №10. - С. 18-22.

4. Коул Б.К. Фирма А Нега готовит производство стираемых ПЛИС на 5000 логических вентилей 60 Мщ/У Электроника. 1988. - №10. -С 22-25.

5. Шипулин С. ПЛИС ~ новый класс микросхем// Радио. 1993. -№11.-С. 2Д13.

6. Соловьев В.В. Проектирование функциональных узлов цифровых систем на программируемых логических устройствах. ~ Мн.: ПКООО "Бестпринт", 1996.-252 с.

7. XILINX. The Programmable Logic Date Book. 2100 Logic Drive San Jose, California 95124 Unated States of America. 1998.

8. Ватанабэ M,., Асада К., Кани К. Проектирование СБИС. М.: Мшх, 1988.-304 с.9, Киносита К., Асада К., Карацу О. Логическое проектирование СБИС. М.: Мир, 1988. - 309 с.

9. Мурога С. Системное проектирование сверхбольших интегральных схем. В двух книгах. М.: Мир, .1985. -- Кн.1 288 с. -Ки.2 290 с.

10. П. Баранов С.Н., Скляров В.А. Цифровые устройства на программируемых БИС с матричной структурой. М.: Радио и связь, 1986. - 272 с.

11. J 2. Агибалов Г.П., Беляев В.А. Метод сокращенного обхода дерева поиска, и его применение в синтезе интегральных схем// Управляющие системы и машины. 1977. - №6. - С. 99-103.

12. Агибалов Г.Г1., Беляев В.А. Технология решения комбинаторно-логических задач методом сокращенного обхода дерева поиска. Томск: Изд-во Томск, ун-та, 1981. 125 с.

13. Агибалов Г.П. Дискретные автоматы на. полурешетках. -Томск: Изд-во Томск, ун-та, 1993. 227 с.

14. Гэри М., Джонсон Д. Вычислительные машины и fруднорешаемые задачи. М.: Мир, 1982. - 416 с.

15. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. - 512 с.

16. Закревский А.Д. Логический синтез каскадных схем. М.: Наука, 1981.-414 с.

17. Бибило П.Н. Синтез комбинационных ПЛМ-структур для СБИС. Мн.: Навука i тэхшка, 1992. - 232 с.

18. Дудкин A.A. Логический синтез одноярусных комбинационных схем в базисе Г1ЛМ/У Теория и методы автоматизации проектирования. Минск: Ин-т техн. кибернетики АН БССР, 1984. - Вып.4. - С. 135-140.

19. Бибило П.й. Анализ и классификация декомпозиционных методов синтеза комбинационных схем на ПЛМ и ПЗУ// Автоматика и вычислительная техника. 1990. -Xsl. - С. 95.

20. Палаше A.B., Баркалов A.A., Юсифов С.И., Стародубов К.Е., Швец А.Г. Реализация микропрограммных автоматов на ПЛИС/7 Управляющие системы и машины. 1991. - №8. - С. 18-22.

21. Палагин A.B., Опанасенко В.Н., Чигирик Л.Г. К синтезу адаптивных структур на ПЛИС// Управляющие системы и машины. -1993.-№5.- С. 1247.

22. Соловьев В.В. Использование программируемых матриц логики при синтезе комбинационных схем// Управляющие системы и машины. 1995. - №4/5. - С. 53-56.

23. Я. Соловьев В.В. Сложность реализации устройств логического управления на ПЛИС// Известия РАН. Теория и системы управления. . 1995. №5. -- С. 248-256.

24. Holland J.H. Adaptation in natural, and Artificial Systems. A Bradford Book The MIT Press Cambridge, Massachusetts London England, 1994. -21 Ip.

25. Goldberg D.E. Genetic Algorithms in Search, Optimization & Machine Learning. Addison-Wesley Publishing Company, Inc., 1989. -4 i 2p.

26. Soldek J., Yanushkevich S. Genetic Algorithms in Logic Design// Proceedings of the International Conference on Computer-Aided Design of Discrete Devices (CAD'95)* v2, Minsk-Szeczcin, 1995. P. 17-25.

27. Doiidkm A.A., Shcstakov E.A. Construction of multilevel PLA networks by using one-level synthesis methods// Proceedings of the Second International Conference on Computer-Aided Design of Discrete Devices (CAD DD'97), vi, Minsk, 1997. P. 86-93.

28. Штейн M.E., Штейн Б.Е. Методы машинного проектирования цифровой аппаратуры. ~ М.: Советское радио, 1973. 296 с.

29. Мелихов А.Ы., Берштейн Л.С., Курейчик В.М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974. - 304 с.

30. Ландау И,Я. Применение ЦВМ для проектирования ЦВМ. -М.: Энергия, 1974. 152. с.

31. Селютин В .А. Машинное конструирование электронных устройств. M.I Радио и связь, 1977. - 383 с.

32. Теория и методы автоматизации проектирования вычислительных систем/ Под ред. М. Брейера. М.: Мир, 1977. -284 с.

33. Фридман А., Менон П. Теория и проектирование переключательных схем. М.: Мир, 1978. - 582 с.

34. Geoffrion A.M., Marsten R.E. Integer programming: a framework rid state-of-the-art survey// Management Science, 1972. vol.18. - №9.

35. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. М.: Наука, 1987. - 248 с.

36. Михалевич B.C., Сергиенко И.В. и др. Пакет прикладных программ для решения задач дискретной и нелинейной оптимизации (пакет ДИСНЭЛ)// Кибернетика. 1991. - №3. - С. 36-45.

37. Корбут A.A., Финкелыптейн Ю.Ю. Дискретное программирование. М.: Наука, 1969. - 368 с.

38. Литтл ДЖ., Мурти К., Суини Д., Кэрел К. Алгоритм для решения задачи коммивояжера// Экономика и математические методы. М.: Наука, 1965. -№1.~ С. 94-107.

39. Кристофидес Н. Теория графов. Алгоритмический подход. -М.: Мир, 1978.-432 с.

40. Рейнгольд, Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. - 476 с.

41. Закревский А.Д., Анищенко А.Н., Балаклей Л.И., Елисеева H.A., Оранов А.М. и др. Синтез асинхронных автоматов на ЭВМ/ Под общей ред. Закревского А.Д. Минск, Наука и техника, 1975. - 184 с.

42. Агибалов Г.П., Оранов А.М. Лекции по теории конечных автоматов. Томск: Изд-во Томск, ун-та, 1984. - 185 с.

43. Оранов A.M. Алгоритм кодирования состояний автомата, реализуемого на 11ЛМ// ВИНИТИ, №2149-85 Деп. от28.03.85. -7 с.

44. Агибалов Т.П., Оранов A.M. Покрытие логических схем модулями некоторых серийных систем// ВИНИТИ, № 5860-85 Деп. от 07.08.85. 19 с.

45. Агибалов Т.П., Оранов A.M. Покрытие логических схем модулями некоторых серийных систему/ Кибернетика. 1986. - №2. -С. 34-38,43.

46. Панкратова И.А., Быкова C.B., Николаева Л.А., Оранов А.М. Система автоматического синтеза комбинационных схем СИНТЕЗ-Ф/У Управляющие системы и машины. 1991, №1. - С. 3-9.

47. Оранов А.М., Андреева JI.H. Алгоритм минимального разбиения системы множеств// Автоматика и вычислительная техника. 1992. - №2. - С. 37-44.

48. Оранов A.M., Андреева Л.Н. Алгоритм синтеза и компоновки одноярусных схем в некоторых базисах// Автоматика и вычислительная техника. 1992. - №5. - С. 57-63.

49. Оранов А.М., Андреева Л.Н. Алгоритм минимального разбиения некоторого набора объектов// Автоматика и вычислительная техника. 1993. - №2. - С. 27-35.

50. Oranov А.М., Andreeva L.N. Complexity of some subproblems of partitioning objects set problem. Proceedings of the International Conference "Computer- Aided Design of Discrete Devices" (CAD DD'95), vl, Minsk, 1995, p.48.

51. Oranov A.M. On synthesis of sequential PLD circuits. -Proceedings of the International Conference "Computer- Aided Design of Discrete Devices" (CAD DD'95), vl, Minsk, 1995, p.49.

52. Оранов A.M. К синтезу комбинационных схем в базисе ПЛИС// Автоматика и вычислительная техника. 1996. - №1. - С. 2735.

53. Оранов A.M. Допустимые разбиения в проектировании РЭС// Труды третьей международной научно-технической конференции feАктуальные проблемы электронного приборостроения" (АПЭП-96). -т.6. 4.2. - Новосибирск. - 1996. - С. 49-52.

54. Оранов A.M. О сложности задачи кратчайшего допустимого разбиения// Международная конференция "Всесибирские чтения поматематике и механике": Тез. докл. т. 1. Математика. Томск: Изд-во Том. ун-та. - 1997. - С. 161-162.

55. Андреева Л.Н., Оранов A.M. О сложности некоторых задач разбиения// Известия РАН. Теория и системы управления. 1997. -№2. - С. 114-116.

56. Андреева Л.Н., Оранов A.M. Оценки погрешности двух приближенных алгоритмов разбиения// Известия РАН. Теория и системы управления. 1999. - №1. - С. 85-33.