Введение к работе
Актуальность проблемы. Успехи в области интегральной технологии, достигнутые за последние 10-15 лет привели к созданию больших штегральных схем (БИС), содержащих десятки и сотни тысяч элемент» іа одном кристалле. Быстрый рост размерности решаемых при разработке эИС задач приводит к необходимости постоянного развития теории и тактики автоматизированного проектирования.
Одним из наиболее трудоемких этапов проектирования цифровой аи-іаратурьі является этап функционально-логического проектирования, теоретической основой которого является задача минимизации булевых функций.
Задача минимизации булевых функций в классе дизъюнктивных нор-и.ъ.ьных форм (ДНФ) состоит в построении по произвольно заданной бу-іевой функции реализующей ее формулы вида " дизъюнкция конъюнкций", содержащей минимальное число букв.
Несмотря на значительное количество публикаций, посвященных юпросам минимизации булевых функций, практически отсутствуют заботы, в которых наряду с описанием алгоритмов был бы дан анализ ос-товных показателей их эффективности. Большинство авторов, в том числе л предлагающих новые подходы к решению проблемы минимизации буле-зых функций, ограничиваются лишь описанием метода и демонстрацией ;го преимуществ на каком-либо конкретном примере, что не может считаться достаточным обоснованием эффективности подхода. В то же время, выбор какого-либо метода для практического использования обычно эсуществляется на основе анализа характеристик, определяющих его эффективность, а это в первую очередь быстродействие и требуемый объем памяти.
Наличие информации о параметрах алгоритмов, позволяет осуществить обоснованный выбор конкретного метода из некоторого множества, при этом учесть осооенности данных, конфигурацию вычислительных средств и т.д. Другим важным результатом анализа является рельефное выделение достоинсів и недостатков конкретного метода в целом и его отдельных этапов, и, как следствие, определение "узких мест" и поиск возможных направлений повышения его эффективности.
Эффективность решения той или иной задачи существенно зависит от степени адекватности математического описания (модели) объекта:
степени адекватности математической модели процесса (задачи-прототи па); эффективности выбранного метода решения.
Применение универсальных моделей и методов позволяет вое пользоваться арсеналом разработанных средств, однако в большинстві случаев приводит к неэффективному решению. Напротив, знание особен ностей, присущих данному объекту, позволяет либо существенно сокра тить пространство решений, либо предложить менее универсальный ме> год, дающий эффективное решение для объектов данного класса.
Новая микпоэлектронная технология практически исключает прак гику натурных испытаний проектируемых схем с целью последовательно го нахождения и устранения логических ошибок в схеме. Это ужесточав! требования к надежности процесса проектирования и приводит к необхо димости его автоматизации, возможной, как известно, лишь при достаточ но высоком уровне формализации. Дополнительным стимулом к ориента ции на машинную реализацию процессов логического проектированиі является их большая трудоемкость - следствие сложности проектируемы; устройств и высоких требований к их качеству.
Непрерывной рост степени интеграции аппаратуры при одновремен ном требовании существенного сокращения сроков ее разработки показы вают, что сущность целесообразного подхода к проектированию РЭС за ключается в конечном счете в разработке и внедрении интегрированноі VAIIP, позволяющей,оперативно создавать проекты модулей различной уровня иерархий и базирующейся на результатах анализа и разработю действительно эффективных методов минимизации ДНФ булевых функ ций как теоретическсйг'еснбвы логического синтеза'цифровых устройств.
Цель и задачи работы. Целью диссертационной работы является ис следование и разработка автоматизированных методов логического проек тирования цифровых устройств на базе программируемых логических мат риц, а также создание программных компонентов автоматизированноі системы логического синтеза. В соответствии с этим в работе ставились і решались следующие задачи:
системное исследование возможностей современных методов логи ческого синтеза, определение границ их ггоименимости, необходимых дл реализации ючных алгоритмов вычислительных ресурсов (комбинаторно! сложности, объема памяти) и возможной погоешности эвристических ме тодов как функции размерности задачи, а также выявление резервов _пс вышения их эффективности;
выявление и анализ комплекса действующих факторов, определяю щих специфику логического проектирования узлов РЭС различного на
начения, и Формирование rtfl огрессивных требований к ним с учетом сиовных тенденций развития отечественных и зарубежных разработок;
поиск эффективных критериев и разработка математических моде-ей решения задач основных этапов логического синтеза;
разработка экономичных методов минимизации булевых функций и истем булевых функций, обеспечивающих решение задач большой раз-[ерности при минимуме используемых вычислительных ресурсов;
создание и адаптация к промышленным условиям эксплуатации бы-гродействующих программных средств автоматизированного логического ннтеза дискретных устройств, выполненных на основе программируемых огических интегральных схем;
разработка программных компонентов перспективной интегрирован-ой САПР РЭС;
определение и исследование на основе машинного эксперимента эф-ективности разработанных в диссертации моделей и алгоритмов, опреде-гние границ применимости и областей юиболее эффективного их ис-ользования.
Методы исследования. Теоретические исследования диссертацион-ой работы строятся на основе методов анализа сложных систем, исследо-шия операций, математического моделирования, булевой алгебры, дис-зетного программирования, методов вычислительной математики и ис-^сственного интеллекта.
Научная новизна. В диссертационной работе предложен, разработан исследован новый класс методов и средств автоматизированного ло-іческого синтеза узлов РЭС, а также оптимизации структуры и параметре логических схем. Принципиальный вклад в развитие исследований области автоматизированного логического проектирования РЭС состав-дат следующие новые научные результаты, полученные автором:
аналитические оценки эффективности (комбинаторной сложности и >ебуемого объема памяти) известных алгоритмов получения простых им-" гіикант булевых функций, а также асимптотические оценки точности эв-«тических методов решения задачи о покрытии;
эффективные алгоритмы получения простых импликант булевых ункций, в частности асимптотически оптимальный в смысле быстродей-вия и требуемого объема памяти алгоритм, названный методом пораз-ідчого выращивания;
комплексные критерии и алгоритмы решения комбинаторной задачи кратчайшем покрытии, обеспечнрзюшне эффективней поиск оптималь-
JV туеЧ'ем^Й-
характеризация булевых функций на основе рас::,-"деления терме по индексам и исследование его свойств;
критерий эффективности минимизации ДНФ булевых функций, и< пользующий свойства распределения термов по индексам,
принципы и алгоритмы оптимизации многовыходных комбинацией ных автоматов, в том числе определение оптимальной полярности выхо/ ных сигналов;
поинципы организации и состав специального программного обе< печения автоматизированной системы логического синтеза цифровых уч; ройств.
На защиту выносятся следующие новые научные положения:
-
Метод "поразрядного выращивания" простых импликант булевы функций, основанный на поэтапном разбиении множества импликант и непересекающиеся подклассы с фиксированным значением общей част кода импликанты и отсечении классов, содержащих импликанты, участве вавшие в склеивании на каком-либо из предыдущих этапов, являете асимптотически оптимальным в смысле минимума комбинаторной слоя ности и требуемого объема памяти ЭВМ.
-
Метол решения комбинаторной задачи о кратчайшем покрыта] основанный на вычислении оценки совокупности строк-претендентов отсечении бесперспективных вариантов путем выбора только одного і претендент» инцидентных каждому из столбцов, образующих минимаш
ное по мощности внешне устойчивое множество, позволяет организовал направленный выбор вариантов и эффективный поиск оптимальных реші ний.
3. Распоеделение термов по индексам (РТИ) некоторой булево
функции может быть представлено в виде композиции аналогичных раї
пределений (РТИ) составляющих ее интервалов, при этом каждое из РТ
интервалов и их пересечений оудет представлять собой кортеж биномі
альных коэффициентов.
4. Характеризация булевых функций на основе РТИ и использован»
свойств РТИ совокупности термов, представляющих собой интервал, п<
зволяют получить оценку эффективности минимизации булевых функциі
в частности позволяет оез решения собственно задачи минимизации опрі
делить кратчайшая ДНФ какой из реализаций функции прямой или иі
верснои будет содержать меньшее число теомо»»
5. Использование саойыв РТИ интервалов и их пересечений да<
возможность синтезигювать РТИ, подобное заданному, что позволяет ре
пщовать. ч(Ь{Ьектцвный ялгопитм мицим-зации булевых функций, оси
ванный на синтезе подобных распределений термов по индексам и идентификации составляющих их интервалов.
-
Комплексное использование метода "поразрядного выращивания", оценки эффективности минимизации, используюшей свойства распределения термов по индексам, и выбора порядка нумерации независимых переменных дает возможность организовать действительно эффективный поиск с ограничением типа "ветвей и границ", что позволяет за практически приемлемое время получать оптимальные решения задач синтеза комбинационных автоматов, отличающихся высокой размерностью.
-
Общесистемное применение прогрессивных принципов структурного построения специального программного обеспечения САПР ПЛУ (программируемых логических устройств) позволяет практически реализовать действительно системный подход к оптимальному проектированию логических устройств и благодаря этому существенно повысить технический уровень, качество и экономическую эффективность разработки перспективной аппаратуры различного схемотехнического и эксплуатационного назначения.
Практическая ценность диссертационной работы заключается в создании методов и быстродействующих средств (машинных программ), позволяющих значительно расширить возможности современных средств автоматизированного логического синтеза РЭС, а также существенно увеличить диапазон решаемых задач. Применение разработанных программ обеспечивает улучшение качества и сокращение сроков проектирования цифровых узлов радиоэлектронных средств (РЭС), позволяет сосредоточить внимание разработчика на поиске действительно оптимальных вариантов реализации аппаратуры.
Реализация в промышленности. Результаты диссертационной работы в виде конкретных положений, выводов, методов, алгоритмов, машинных программ и расчетных данных внедрены в инженерную практику и используются на промышленных предприятиях в гг. Санкт-Петербурге и Одессе, а также в учебном процессе СПбГУТ им. проф. М.А.Бонч-Бруевича, Балтийском ГТУ и Северо-Западном политехническом имнсти-гуте.
Апробация работы. Основные положения и результаты диссертационной работы докладывались и были одобрены на Всесоюзном совещании-семинаре "Автоматизация проектирования устройств и сие і см СВЧ", г. Красноярск, 1982 г.; Всесоюзном совещании-семинаре "Гиокис автоматизированные производственные системы", г. Ленинград, 1984 г.: Всесоюзном ггаещании-семинаре "Теоретические и прикладные вопросы
разработки, внедрения и эксплуатации САПР РЭА", г. Одесса, 1984 (2 доклада); III Всесоюзном совещании-семинаре "Методы решения от мизационных задач на графах и сетях", г. Ташкент, 1984 г.; IX Всесоюзне симпозиуме по проблеме избыточности в информационных систем? г. Ленинград, 1986 г.; Всесоюзном совещании-семинаре "Теория и практ ка построения интеллектуальных интегрированных САПР РЭА и БИС г. Алушта, 1987 г.; Всесоюзной научно-технической конференции "Сове шенствование технических средств связи для решения проблем информ тизации общества в новых условиях хозяйствования", г. Ленинград, 1991 (2 доклада); научно-технических конференциях (НТК)"Автоматизация пр ектирования радиоэлектронной и электронно-вычислительной аппарат ры", Пенза, 1982-1992 гг. (14 докладов); на 4-й и 5-й межотраслевых НІ (г. Уфа, 16-17 марта 1983 г., 11-13 апреля 1989 г.); на республиканец НТК (г. Севастополь, 21-22 апреля 1986 г.); отраслевой НІ "Совершенствование технических средств для развития цифровых сисп и сетей передачи информации", Ленинград, 1990г.; научно-техннчесю семинаре "Использование универсальной вычислительной техники п моделировании систем обработки информации", Усть-Нарва, 1990г.; НІ профессорско-преподавательского состава ЛЭИС им. проф. М.А.Боь Бруевича, 1984-1989, 1996 гг.
Публикации. Основное содержание диссертации отражено в 35 і чатных работах (в том числе в монографии) и в 16-и научно-техническ отчетах по НИР и ОКР, выполненных под научным руководством и п непосредственном участии автора.
Структура и объем работы. Диссертация состоит из введения, шее разделов, заключения и приложения. Основной материал работы излож на 194 машинописных страницах. Работа содержит 22 таблицы и 6 рис] ков. Список литературы включает 146 наименований отечественных и рубежных публикаций.
