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

Введение.

1. Проблемы, методы, состояние и практика решения задач автоматизированного проектирования СБИС.

1.1. Основные задачи, решаемые при конструкторском проектировании СБИС

1.2. Методы оптимизации при решении задач конструкторского проектирования СБИС.

1.2.1. Традиционные методы оптимизации

1.2.2. Основные понятия и определения адаптации.'.

1.2.3. Моделирование отжига.

1.2.4. Альтернативная поисковая адаптации на основе вероятностных обучающихся автоматов.

1.2.5. Генетические алгоритмы.

1.3. Задачи, методы и алгоритмы поисковой адаптации.

1.3.1.Структура поискового алгоритма оптимизации.

1.3.2. Проблема представления в адаптивных алгоритмах оптимизации

1.3.3. Поисковая адаптация на основе сочетания самообучения, самоорганизации и генетического поиска

Выводы.

2. Разработка алгоритмов и моделей поисковой адаптации для решения задачи покрытия

2.1. Проблемная формулировка, термины и определения.

2.2. Формирование пространства решений.

2.3. Организация поисковой процедуры на основе коллективной адаптации для решения задачи покрытия.

2.4. Структура, принципы кодирования и декодирования хромосомы

2.5. Генетические операторы при покрытии

2.6. Организация процедуры генетического поиска для решения задачи покрытия.

2.7. Экспериментальные исследования.

Выводы

3. Построение оптимизационных процедур разбиения на основе моделирования поисковой адаптации.

3.1. Введение.

3.2. Постановка задачи разбиения.

3.3. Механизмы адаптации при разбиении.

ЗАСтруктура, принципы кодирования и декодирования хромосом при разбиении

3.5. Генетические операторы при разбиении

3.6. Организация процедуры генетического поиска при разбиении

3.7. Экспериментальные исследования

Выводы

4. Формирование поисковых оптимизационных процедур на основе эволюционного моделирования для решения задачи размещения

4.1. Проблемная формулировка, термины и обозначения

4.2. Формирование моделей среды и объекта адаптации

4.3. Организация процесса переразмещения

4.4. Общая структура адаптивного поиска при размещении

4.5. Структура, принципы кодирования и декодирования хромосом при размещении.

4.6. Генетические операторы

4.7. Организация процедуры генетического поиска при размещении

4.8. Экспериментальные исследования

Вывод ы

5. Разработка интеллектуальных адаптивных поисковых алгоритмов глобальной трассировки

5.1. Проблемная формулировка, термины и обозначения

5.2. Распределение ресурсов коммутационного поля

5.3. Организация процесса коллективной адаптации при глобальной трассировке

5.4. Структура, принципы кодирования и декодирования хромосом

5.5. Генетические операторы

5.6. Организация процедуры генетического поиска

5.7. Интеллектуальная система построения дерева Штейнера на основе процедур отсечки и сужения пространства решений

5.7.1. Постановка задачи построения дерева Штейнера

5.7.2. Подход к построению дерева Штейнера.

5.7.3. Организация процесса построения дерева Штейнера на основе отсечек

5.7.4. Метод сужения пространства решений

5.8. Экспериментальные исследования

Выводы

6. Построение поисковых оптимизационных процедур распределения соединений между выводами на основе моделирования адаптивных процессов

6.1. Проблемная формулировка, термины и обозначения

6.2. Переключение соединений в канале

6.3. Организация процесса коллективной адаптации при перераспределении соединений между выводами в канале

6.4. Механизмы генетического поиска при перекоммутации соединений

6.5. Динамическое распределение инвариантных контактов

6.6. Экспериментальные исследования

Выводы

7. Синтез интеллектуальных, адаптивных и динамических поисковых процедур детальной трассировки.

7.1. Формулировка проблемы канальной трассировки

7.2. Расчет нижних оценок

7.3. Процедуры сужения и отсечения

7.4. Динамический канальный трассировщик

7.5. Трассировка в канале методом ветвей и границ

7.6. Трассировка в коммутационном блоке на основе генетических процедур

7.6.1. Формулировка задачи, основные термины и обозначения

7.6.2. Генетический алгоритм трассировки в коммутационном блоке

7.6.2.1. Структура хромосом, их кодирование и декодирование

7.6.2.2. Генетические операторы

7.7. Канальная трассировка на основе генетических процедур

7.7.1. Формулировка задачи, основные термины и обозначения

7.7.2. Алгоритм генетической канальной трассировки

7.7.2.1. Кодирование и декодирование хромосом

7.7.2.2. Исходная популяция

7.7.2.3. Генетические операторы

7.8. Однослойная трассировка в приканальной надъячеечной области

7.8.1. Проблемная формулировка, термины и обозначения

7.8.2. Алгоритм надъячеечной трассировки

7.8. Экспериментальные исследования

Выводы

8. Разработка, на основе моделирования поисковой адаптации. оптимизационных процедур разнесения соединений по слоям.

8.1. Проблемная формулировка, термины, определения

8.2. Разбиение цепей на фрагменты

8.3. Формирование пространства решений

8.4. Организация процесса коллективной адаптации при разнесении соединений по слоям.

8.5. Организация процесса генетического поиска при разнесении соединений по слоям

8.6. Экспериментальные исследования

Выводы

Основу элементной базы современных радиоэлектронных устройств (РЭА) составляют сверхбольшие интегральные схемы (СБИС), которые выполняют определенную функцию преобразования сигнала и (или) накапливания информации и имеют сверхвысокую плотность упаковки электрически соединенных элементов. С момента появления интегральных схем резко изменились их основные характеристики - быстродействие, размеры, стоимость. Современные СБИС содержат порядка 10-15 миллионов на кристалле размером 25*25 мм с минимальным топологическим размером 0,18м.

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

В связи с возросшими технологическими возможностями изготовления в настоящее время в СБИС произошло увеличение области межсоединений. Рост размера области, отводимой для межсоединений , опережает рост размера области, предназначенной для активных элементов (транзисторов). В современной СБИС, содержащей 10 миллионов транзисторов, использующей 4 слоя металлизации, около 40% площади отводится под межсоединения. Возрастает число переходов из слоя в слой, что вырастает в отдельную проблему, и тенденция эта растет. В связи с этим особо актуальна разработка новых эффективных методов решения задач конструкторского проектирования: покрытия, разбиения, размещения, трассировки и т.д.[1].

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

Основные задачи синтеза и формирования топологии СБИС - покрытие, разбиение, размещение, глобальная трассировка, перераспределение соединений между выводами, распределение соединений между слоями и т.д. являются КР-полными. Из теории алгоритмов известно, что для задач класса ЫР в природе не существует алгоритма, кроме алгоритма "полного перебора ", который бы гарантировал нахождение глобального оптимума. Понятно, что для задач большой размерности этот алгоритм неприемлем. Поэтому очень большой класс разработанных к настоящему времени алгоритмов проектирования СБИС основан на различных эвристиках, обеспечивающих получение решений в полиномиальное время. Основным недостатком этих алгоритмов (последовательных и итерационных) является невысокое качество результатов из-за попадания в "локальные ямы", малая пригодность для задач большой размерности, плохая приспособленность для реализации на современных технических средствах, отсутствие альтернатив. Одним из возможных методов решений этой проблемы является использование методов случайного направленного поиска, основанного на моделирование естественных процессов. К таким относятся бурно развивающиеся в последнее время методы поисковой адаптации на основе механизмов самоорганизации, генетического поиска и эволюционного развития. Слово адаптация, широко используемое в современной научно-технической литературе, заимствовано из биологии, где оно означает приспособление живых организмов к изменяющимся окружающим условиям. Адаптация многолика и разнообразна. Известны такие проявления адаптации, как эволюция, привыкание, обучение и самообучение, организация и самоорганизация и т.д. [2,3].

Изучение законов биологической эволюции показало, что в их основе лежит закон взаимной адаптации. Существование и развитие живой системы (в том числе человека) суть процесс взаимной опережающей многоуровневой адаптации компонентов системы между собой и системы с внешней средой [4]. Наблюдения в области адаптации живых организмов привели к идее "наделить" указанным свойством технические системы. Это достигается введением в конструкцию технической системы возможности приспособления к новым ситуациям, заранее не предвиденным с тем, чтобы в процессе функционирования эта система изменялась и улучшала свои характеристики.

Значительный вклад в разработку технических устройств и моделей, имитирующих процессы подобной адаптации, внесли M.JI. Цетлин, JI.A. Растри-гин, A.A. Красовский, Д.А. Поспелов, Г.С.Поспелов, В.Ф. Венда, A.A. Самарский, Я.З. Цыпкин, П.В. Куропаткин, В.Г. Срагович, Б.И. Кузьмин, В.П.Сигорский и др.

В настоящее время в технических системах существует два подхода к организации адаптационных процессов [5].

При первом подходе адаптивные процессы поддерживают объект в состоянии, определяемом целью и, в этом смысле, адаптация является управлением.

При втором подходе адаптивные процессы связанны с максимизацией эффективности функционирования некоторого объекта. Здесь адаптация рассматривается как оптимизация.

В адаптивных системах управления информация об объекте и внешних воздействиях собирается в ходе эксплуатации, сразу же обрабатывается и используется для выработки управляющих воздействий. Это позволяет повысить качество управления в условиях неопределенности и нестабильности объекта и среды функционирования. Методы адаптивного управления в сложных системах на сегодняшний день уже достаточно развиты [6,7].

При втором подходе решение задачи адаптации сводится к определению такого управляющего воздействия, при котором достигается максимальная эффективность работы объекта и одновременно выполняются все жесткие требования, предъявляемые к этому объекту [8,9]. Такая задача является задачей оптимизации (максимизации эффективности) в обстановке ограничений.

Обычно, адаптация в системах автоматизированного проектирования (САПР) [10] рассматривается как адаптация в сложной системе состоящей из 4х основных компонентов: комплекса программных средств (КПС), комплекса технических средств (КТС), объекта проектирования (ОП) и пользователя (П).

Основным объектом адаптации является КПС и, следовательно, и математическое обеспечение, на основе которого разработаны прикладные программы, входящие в состав КПС.

В качестве внешней среды, к которой адаптируется КПС, в основном рассматривается множество ОП, хотя в общем случае могут также рассматриваться и другие компоненты.

Адаптация КПС к ОП означает способность САПР приспосабливаться к потоку ОП в изменяющихся условиях с целью достижения оптимального проектирования на основе поступающей априорной и апостериорной информации. Достижение цели адаптации осуществляется путем изменения структуры и параметров программного обеспечения и пакетов прикладных программ, входящих в состав КПС.

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

В этом случае в качестве объекта адаптации выступает сам ОП. Внешняя среда определяется на основе анализа проблемной области и специфики решаемой задачи.

Объект адаптации рассматривается как обучающаяся система, помещенная в среду, характеризующуюся вероятностной реакцией.

Значительным шагом в развитии технических устройств, для имитации адаптации, был предложенный М.Л. Цетлиным подход, основанный на использовании вероятностных обучающихся автоматов [11].

Представим работу адаптивной системы как функционирование некоторого вероятностного автомата, действующего в случайной среде. Тогда адаптивная система распадается на два компонента - среду и управляющее устройство.

Под средой понимается объект управления (объект оптимизации), а управляющее устройство работает в соответствии с алгоритмом случайного поиска.

Основываясь на этой идее, М.Л. Цетлин поместил в среду, характеризующуюся случайной реакцией, вероятностный автомат адаптации (АА) для реализации функции управляющего устройства. Адаптация автомата производится путем самообучения в процессе его функционирования.

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

Идеи использования методов естественной генетики появились в результате работ Холланда [12]. Генетический алгоритм (ГА) есть адаптивный поисковый метод, который основан на селекции лучших индивидуальностей в популяции, подобно эволюционной теории Дарвина. Отличительной особенностью генетических алгоритмов является следующее:

-генетические алгоритмы работают на основе популяции, т.е. на множестве индивидуальностей;

- оперирование производится не с решениями, а с их кодами. Каждому решению соответствует одна или несколько хромосом, которые представляют собой закодированный генетический материал. Хромосомы состоят из генов. Каждый ген имеет свой локус или позицию в хромосоме. Гены могут иметь различные значения: число, строка, сектор, массив и т.д. Решение получается на основе декодирования хромосом.

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

Однако эти подходы в задачах конструкторского проектирования СБИС еще не получили достаточного развития и обобщения.

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

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

- проведение сравнительного анализа методов оптимизации и выработка общего подхода и структуры к организации оптимизационных процедур на основе методов поисковой адаптации и интеллектуализации процедур поиска;

- разработка новых критериев, моделей и подходов к решению основных задач синтеза топологии СБИС;

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

-разработка представлений исходных формулировок задач конструкторского проектирования СБИС в виде адаптивных процессов на основе самообучения и самоорганизации, моделируемых вероятностными автоматами адаптации (АА), и механизмов их функционирования, что предполагает: a) формирование моделей среды и объекта адаптации, локальных целей объектов адаптации и глобальной цели коллектива; b) разработку структуры обучающегося АА и механизмов переходов в АА; c) разработка общей структуры процесса адаптивного поиска;

-разработка представлений исходных формулировок задач конструкторского проектирования СБИС в виде адаптивных поисковых процессов на основе генетической эволюции, что предполагает: а) разработку и модификацию механизмов генетического поиска; b) разработку, модификацию и адаптацию к решаемой задаче генетических операторов; c) формирование структур и принципов кодирования хромосом с учетом специфики решаемых задач, оптимизирующих процесс генетического поиска;

- разработка и исследование алгоритмов топологического синтеза на базе общего подхода к построению адаптивных поисковых процедур, опирающихся на сочетание принципов адаптации на основе самообучения, самоорганизации и генетического поиска;

-разработка программных средств на основе проведенных исследований для решения задач топологического синтеза.

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

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

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

2. Разработаны и исследованы механизмы альтернативной и коллективной адаптации для решения задач покрытия, разбиения, размещения, глобальной трассировки, перекоммутации соединений, распределения соединений по слоям.

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

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

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

6. Разработаны и теоретически обоснованы методы и алгоритмы усечения и сужения пространства решений при решении задач трассировки и построения дерева Штейнера и сформированы на их основе интеллектуальные динамические процедуры поиска решений.

7. Разработаны и экспериментально исследованы адаптивные поисковые алгоритмы для решения оптимизационных задач синтеза топологии СБИС на основе самообучения, самоорганизации и генетического поиска и предложены технологии как их совместного, так и автономного использования.

Достоверность результатов диссертационной работы.

Достоверность результатов, полученных в работе, подтверждаются работой вычислительных экспериментов на ЭВМ, публикациями, апробацией работы на ряде международных, всероссийских и всесоюзных конференций, результатами практического использования предложенных в диссертации моделей, методов и алгоритмов, подтвержденных актами о внедрении и использовании.

Основные научные результаты, выносимые на защиту.

1. Новые концепция и архитектура алгоритмов решения оптимизационных задач топологического синтеза методами поисковой адаптации на основе самообучения, самоорганизации и генетического поиска.

2. Модели, методы и алгоритмы альтернативной коллективной адаптации для решения задач покрытия, разбиения, размещения, глобальной трассировки, перекоммутации соединений, разнесения соединений по слоям.

3. Новые технологии и средства повышения эффективности процесса альтернативной поисковой адаптации для усиления способности выхода из "локальных ям".

4. Модели, методы и алгоритмы решения задач покрытия, разбиения, размещения, глобальной трассировки, канальной трассировки, трассировки в трассировки в коммутационном блоке, перекоммутации соединений, разнесения соединений по слоям на основе генетической адаптации.

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

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

7. Методы и алгоритмы усечения и сужения пространства решений при решении задач трассировки и построения дерева Штейнера и сформированные на их основе интеллектуальные динамические процедуры поиска решений.

8. Программные средства, реализующие предложенные методы и алгоритмы.

Практическая ценность работы состоит в том, что основные теоретические положения доведены до конкретных методик и алгоритмов. Предложенные методы поисковой адаптации, опирающиеся на сочетание принципов адаптации на основе самообучения, самоорганизации, генетического и интеллектуального поиска, являются мощным средством выхода их "локальных ям", приводящим к синтезу решений, близких к оптимальным. 19 разработанных алгоритмов синтеза топологии методами адаптивного и интеллектуального поиска реализованы в виде программ на языке Borland С++ для Windows. Созданный комплекс программ позволяет при решении задач синтеза топологии СБИС осуществлять выбор метода решения: только методами генетического поиска; методами коллективной, альтернативной адаптации, моделируемой вероятностными обучающимися автоматами адаптации; либо их совместное использование. Предложенные методы позволяют достигнуть улучшенных показателей объектов проектирования. Кроме того, предложенные алгоритмы и программы носят достаточно универсальный характер и могут быть использованы для решения широкого круга задач.

Теоретические и практические результаты, полученные в диссертационной работе, использованы в ряде научно-исследовательских работ, проводимых в Таганрогском государственном радиотехническом университете руководителем или исполнителем которых являлся автор.

В рамках научно-технических программ Минобразования РФ "Научные исследования ВШ по приоритетным направлениям науки и техники": "Разработка теории и методов построения интегрированных САПР СБИС с элементами искусственного интеллекта" (№ ГР 01.950004188); "Разработка интеллектуальных систем проектирования на основе эволюционной адаптации" (№ ГР. 01.960004346).

В рамках государственной научно-технической программы "Университеты России"(1995-1996г.): "Разработка методов и моделей генетического поиска в интеллектуальных САПР", "Исследование генетических методов оптимизации".

Поддержана грантами РФФИ: "Генетические алгоритмы в интеллектуальных САПР" (шифр 99-01-00050); "Символьные информационные технологии проектирования на основе эволюционной адаптации" (шифр 00-01-00125); "Эволюционное проектирование с адаптацией" (шифр 01-01-00044). Поддержана грантом Минобразования РФ на проведение фундаментальных исследований в области технических наук (Исследование и разработка методов трассировки СБИС на основе эволюционной адаптации). В работе, выполняемой по ЕЗН Минобразования РФ (Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений )

В работе "Учебно-методический комплекс, Применение экспертных систем в инженерной практике", выполненой в рамках научно-технической программы "Компьютеризация образования^ 995 г.)";

Теоретические и практические результаты, полученные в диссертационной работе, использованы в Ростовском филиале Всесоюзного научно исследовательского института автоматизированных систем в системах расчета параметров внешней среды и выработке оптимального управляющего воздействия. В НКБ "Миус" и НИИ МВС применение предложенных в диссертационной работе алгоритмов и разработанных программ позволило уменьшить время проектирования элементов вычислительных систем.

За разработку САПР двухслойных и многослойных схем автор награжден серебренной и бронзовой медалями ВДНХ.

Научные результаты и разработанное программное обеспечение диссертационной работы внедрены в учебный процесс по курсам "Искусственный интеллект", "Прикладные интеллектуальные системы", "Проблемы разработки и перспективы интеллектуальных САПР", "Методы оптимизации", "Исследование операций", обобщены в изданных учебных пособиях. Акты внедрения и использования научных результатов прилагаются.

Апробация работы. Основные положения и результаты докладывались и обсуждались на: Всероссийской НТК с международным участием "Интеллектуальные САПР", (Геленджик, 1992-2001гг); Международной НТК "Новые информационные технологии в науке образования и бизнесе»", (Крым, Гурзуф, 1991-1995 г.г.); Всероссийской конференции "Интеллектуальные информационные системы" (Воронеж, 1999 г.); 1 Международной НТК "Проблемы реального управления, экономики, права и инновационных процессов в образовании" (Таганрог, 1999 г.); Международной конференции и школе молодых ученых и специалистов "САПР-92, новые информационные технологии в науке, образовании и бизнесе" (Воронеж ,1992 г.); Всесоюзной конференции "Создание интеллектуальных САПР БИС и электронных средств" (Москва, 1990 г.); 3 International Conference "Interactive System: The problems of Human Computer Interaction" ( Ulyanovsk, 1999 г.); Всесоюзном совещании "Методы и программы решения оптимизационных задач на графах и сетях" (Новосибирск, 1980, 1983, 1989 г.г.); XXX Всесоюзной школе-семинаре им. М.А. Гаврилова "Развитие теории дискретных систем и проблемы логического проектирования" (Кишинев, 1988 г.); Всесоюзной конференции "Автоматизация технического проектирования цифровой аппаратуры" (Каунас, 1981, 1984, 1985, 1987, 1988, 1989 г.г.); Межреспубликанском семинаре "Интеллектуальные САПР СБИС" (Ереван, 1988 г.); Всесоюзной конференции "Проблемы адаптации алгоритмического и информационного обеспечения САПР" (Киев, 1987 г.); НТК "Автоматизация проектирования РЭА и ЭВА" (Пенза, 1983-1988 г.г.); Всесоюзной конференции "Автоматизация поискового конструирования и подготовки инженерных кадров" (Иваново, 1983 г.); Всесоюзной НТК "Теория и практика конструирования и обеспечения надежности и качества электроаппаратуры и приборов" (Москва, 1984 г.); Всесоюзной конференции "Микропроцессоры 85. Методы и микроэлектронные устройства цифрового преобразования и обработки информации" (Москва, 1985 г.); Всесоюзной конференции "Проблемы создания и развития интегрированных систем в проектировании и производстве" (Москва, 1987 г.); Международном НТС "Интегрированные модели и мягкие вычисления в искусственном интеллекте" (Коломна, 2001 г.); Международном конгрессе "Искусственный интеллект в XXI веке" (Дивноморское, 2001 г.);

Научно-технических конференциях профессорско-преподавательского состава ТРТУ (1980-2001 г.г.) и других конференциях.

По теме диссертации опубликовано 68 печатных работ, среди которых 4 монографии и 3 учебных пособия.

Структура и объем диссертационной работы. Диссертация состоит из введения, 8 глав, заключения, списка использованной литературы и приложения. Объем диссертации 376 страниц, включая список литературы из 172 наименований. В приложении вынесены акты об использовании и внедрении результатов диссертационной работы.

Выводы

1. Приведена проблемная формулировка задачи разнесения соединений по слоям и описана методика формирования пространства решений и представления решения в виде бинарного вектора, что упрощает процесс поиска.

2. Разработаны основные компоненты, необходимые для организации процесса коллективной адаптации при разнесении соединений по слоям.

3. Для ускорения достижения объектом адаптации состояния с минимальным числом межслойных переходов разработан вероятностный механизм формирования откликов среды.

4. Для усиления способности выхода из локальных оптимумов при работе адаптивной системы автомат адаптации модернизирован введением вероятностных механизмов перехода из одной группы состояний в другую.

363

5. Исходя из эвристических соображений, множество объектов в зависимости от мощности разбито на классы. Для каждого класса вводятся индивидуальные значения параметра - глубина памяти. Это позволяет избежать резких изменений и более тщательно просматривать решения в некоторой окрестности.

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

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

8. Экспериментальные исследования процедур поисковой адаптации при их совместной работе показал, что вероятность получения оптимальных решений при одном прогоне программы составила 0,96, а среднее отклонение решений от глобального оптимума менее 1%.

8. Для основных задач синтеза топологии СБИС с учетом их специфики и с ориентацией на большие размерности разработаны и исследованы структуры хромосом и принципы их декодирования, отличающиеся отсутствием сложных элементов, линейной оценкой пространственной и временной сложности, гомологичной структурой хромосом и генов, возможностью формирования виртуального множества популяций для распараллеливания генетического поиска. Разработанные структуры и принципы кодирования гомологичных хромосом могут быть успешно использованы для задач, решения которых представимы в виде векторов и матриц с неповторяемыми элементами.

9. На основе двухуровневого представления объекта оптимизации и идеи коллективной адаптации, позволяющих сочетать эволюционную и альтернативную адаптации, разработаны с учетом специфики решаемых задач структуры вероятностных обучающихся АА, механизмы переходов, выработки откликов среды, реализации альтернатив.

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

11. Разработанные в диссертации теоретические положения, методы, алгоритмы и программные средства позволяют решать задачи по созданию эффективных средств синтеза топологии СБИС с учетом современных тенденций, обладающих улучшенными характеристиками. Большинство разработанных алгоритмов имеют линейную оценку ВСА и ПСА при фиксированных значениях управляющих параметров. В среднем вероятность получения глобального оптимума составила 0.9-0.96. Эксплуатация и исследования разработанных средств подтвердили их высокую эффективность. В сравнении с известными алгоритмами на стандартных бенчмарках полученные результаты были лучше на 5-10% при меньших затратах времени.

Заключение

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

2. На основе механизмов генетического поиска разработаны адаптивные поисковые алгоритмы синтеза топологии СБИС - покрытия, разбиения, размещения, глобальной трассировки, канальной трассировки, трассировки в коммутационном блоке, перекоммутации соединений, разнесения соединений по слоям.

3. На основе механизмов альтернативной коллективной адаптации, моделируемых вероятностными обучающимися автоматами адаптации, разработаны алгоритмы синтеза топологии СБИС - покрытия, разбиения, размещения, глобальной трассировки, перекоммутации соединений, разнесения соединений по слоям.

4. На основе интеллектуальных процедур отсечки и сужения пространства решений разработаны интеллектуальные динамические алгоритмы канальной трассировки, построения дерева Штейнера, перекоммутации соединений.

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

6. Разработана и теоретически обоснована новая технология генетического поиска на базе виртуального набора популяций на одном наборе генотипов для распараллеливания генетического поиска без увеличения сложности алгоритма.

7. При распараллеливании генетического поиска с целью повышения его эффективности предложена и исследована процедура адаптации набора популяций.

1. Naveed Sherwani. Algorithms for VLS1.physical design automation. Kluwer academic publishers. Boston /Dordrecht/ London. 1995.

2. Цыпкин Я.З. Адаптация и обучение в автоматических системах. -М.: Наука, 1975.

3. Поспелов Д.А. Фантазия или наука: на пути к искусственному интеллекту. М.: Наука, 1982. - 224 с.

4. Венда В.Ф. Системы гибридного интеллекта. Эволюция, психология, информатика. М.: Машиностроение, 1990. - 448 с.

5. Растригин Л.А. Адаптивные компьютерные системы. М.: Знание, 1987.-64 с.

6. Срагович В.Г. Адаптивное управление. М.: Наука, 1981.

7. Справочник по теории автоматического управления. Под ред. A.A. Красовкого. М.: Наука, 1987. - 712 с.

8. Куропаткин П.В. Оптимальные и адаптивные системы. М.: Высшая школа, 1980.

9. Растригин Л.А. Адаптация сложных систем. Рига: Зинатне, 1981. -375с.

10. Holland J.H. Adaptation in Natural and Artificial Systems. An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. University of Michigan, 1975, 210 p.

11. Системы автоматизированного проектирования в радиоэлектронике: Справочник / Е.В. Авдеев, А.Т. Еремин, И.П. Норенков, М.И. Песков; Под ред. И.П. Норенкова. М.: Радио и связь, 1986. 368 с.

12. Конструирование аппаратуры на БИС и СБИС / Под ред. Б.Ф. Высоцкого и В.П. Сретенского. М.: Радио и связь, 1989.

13. Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. М.: Радио и связь, 1990. 352с.

14. Автоматизация проектирования СБИС. В 6 кн.: Практ.пособие / Под. ред. Г.Г. Казеннова. М.: Высш. шк., 1990.

15. Быстродействующие матричные БИС и СБИС. Теория и проектирование. Под общей редакцией Б. Н. Файзулаева и И.П. Шагурина. М., Радио и связь, 1989.

16. Селютин В.А. Автоматизированное проектирование топологии БИС. М., Радио и связь, 1983. 112 с .

17. Селютин В.А. Машинное конструирование электронных устройств. М.: Сов.радио, 1977. 384 с.

18. Курейчик В.М., Калашников В.А., Лебедев Б.К. Автоматизация проектирования печатных плат. Ростов н/Д: Изд-во Ростовского университета, 1984. 80с.

19. Проектирование монтажных плат на ЭВМ / К.К. Морозов, А.Н. Мелихов, В.Г. Одиноков, В.М. Курейчик, В.А. Калашников, Б.К. Лебедев; Под ред. К.К. Морозова. М.: Сов.радио, 1979. 224 с.

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

21. Панадимитриу X., Стайглиц К. Комбинаторная оптимизация. М.: Мир, 1985.512 с.

22. Исследование операций. В 2-х томах / Под ред. Дж. Моудера, С. Элмаграби. М.: Мир, 1981.

23. Петухов Г.А., Смолич Г.Г., Юлин Б.И. Алгоритмические методы конструкторского проектирования узлов с печатным монтажом. М., Радио и связь, 1987, с. 157.

24. Сорокопуд В.А. Автоматизированное конструирование микроэлектронных блоков с помощью малых ЭВМ. М., Радио и связь, 1988. с. 128.

25. Вермишев Ю.Х. Основы автоматизации проектирования. М., Радио и связь, 1988.

26. D.F.Wong, H.W.Leong, and C.L.Lin . Simulated Annealing for VLSI Design. Boston, MA : Kluwer Academic, 1988.

27. Курейчик B.M., Лебедев Б.К., Лях A.B. Проблемы эволюционной адаптации в САПР. Новинтех, №3. 1991.

28. Растригин Л.А., Рипа К.К., Тарасенко Г.С. Адаптация случайного поиска. Рига: Зинатне, 1978.

29. Курейчик В.М., Лебедев Б.К. Искусственный интеллект в САПР: Текст лекций. Таганрог: ТРТИ, 1989. 48 с

30. Букатова И.Л. Эволюционное моделирование и его приложения. -М.: Наука, 1979.

31. Букатова И.Л. и др. Эвоинформатика. Теория и практика эволюционного моделирования. -М.: Наука, 1991.

32. Князева E.H., Курдюмов С.П. Законы эволюции и самоорганизации сложных систем.-М. .'Наука, 1994.

33. Handbook of Genetic Algorithms, Edited by Lowrence Davis, Van Nostrand Reinhold, New York, 1991. 385p.

34. Цетлин МЛ. О поведении конечных автоматов в случайной среде. -Автоматика и телемеханика, 1961, Т.22, №10.

35. Крылов В.Я., Цетлин МЛ. Игры между автоматами. Автоматика и телемеханика, 1963, Т.24, №7.

36. Надин A.B., Поздняк A.C. Адаптивный выбор вариантов. М.: Наука, 1986.-288 с.

37. Приобретение знаний. / Под ред. С.Осуги, Ю.Саэки. М.: Мир, 1990.-304 с.

38. Лебедев Б.К. Поисковый алгоритм трассировки. // "Автоматизированное проектирование в радиоэлектронике и приборостроении". Л., ЛЭТИ, 1984, Вып.347. с. 94-98.

39. Лебедев Б.К., Мухлаев А.В. Элементы адаптации в алгоритмах мон-тажно-коммутационного проектирования //Автоматизация проектирования электронной аппаратуры. Таганрог: ТРТИ, 1988, Вып.5, с.67-71.

40. Лебедев Б.К., Мухлаев А.В. Размещение элементов БИС с использованием принципов адаптации.// Проблемы создания и развития интегрированных автоматизированных систем в проектировании и производстве. М.: Радио и связь, 1987, с. 97-98.

41. Курейчик В.М. Генетические алгоритмы: Монография. Таганрог: Изд-во ТРТУ, 1998, 242 с.

42. Батищев Д.И. Генетические алгоритмы решения экстремальных задач: Учебное пособие. Воронеж: ВГТУ, 1995. 65 с.

43. Лебедев Б.К. Методы поисковой адаптации в задачах автоматизированного проектирования СБИС: Монография. Таганрог: Изд-во ТРТУ, 2000. 192 с.

44. Лебедев Б.К. Методы поисковой адаптации для решения оптимизационных задач. // Новости искусственного интеллекта, М., 2000, №3, с.66-79.

45. Лебедев Б.К. Адаптация в САПР: Монография. Таганрог: Изд-во ТРТУ, 1999, 160с.

46. Поспелов Г.С. Искусственный интеллект основа новой информационной технологии. - М.: Наука, 1988, 280 с.

47. Курейчик В.М., Лебедев Б.К., Нужное Е.В. .Применение экспертных систем в инженерной практике: Учебное пособие. Таганрог: ТРТУ, 1996. 135с.

48. Лебедев Б.К. Методы оптимизации при решении задач проектирования СБИС. // Известия ТРТУ. Таганрог: Изд-во ТРТУ, 2001. №1. с. 56-60.

49. Компьютер и задачи выбора. М.: Наука, 1989. 208 с.

50. Деньдобренко Б.П., Малика А.С. Автоматизация проектирования радиоэлектронной аппаратуры. М., Высш. шк., 1980. с.384.

51. Лебедев Б.К. Покрытие на основе генетической адаптации. // Сборник трудов международного конгресса "Искусственный интеллект в XXI веке", Дивноморское, 3-8 сентября, 2001.-М.: Наука. Физматлит, 2001, с. 622630.

52. R. В. Hitchcock. Partitioning of logic graphs: A theoretical analysis of pin reduction. Proceedings of Design Automation Conference, pp.54-63, 1970.

53. B. Krishnamurthy. An improved mincut algorithm for partitioning vlsi networks. IEEE Transactions on Computers, pp.43 8-446, 1984.

54. Y. Wei, C. Cheng. Towards efficient hierarchical designs by ratiocut partitioning. Proceedings if IEEE International Conference on Computer-Aided Design, pp.298-301, 1989.

55. Андреева JI.H., Оранов A.M. Оценки погрешности двух приближенных алгоритмов разбиения./УИзвестия РАН. Теория и системы управления. 1997.№2.

56. Youssef G. Saab, Vasant В. Rao. "Fast Effective Heuristics for the Graph Bisectioning Problem" , IEEE, vol.9 N1, January 1990, Transaction on computer-aided design.

57. Y.C.Wei, C.K.Cheng. "A two-level two-way Partitioning Algorithm", Tech. report CH2924-9, University of California, San Diego, IEEE, 1990.

58. Ching-Wei Yeh, Chung-Kuan Cheng, Ting-Ting Y. Lin. "A general purpose multiple way Partitioning Algorithm", 28th ACM/IEEE Desighn Automation Conference, paper 25/1, pp.421-425.,1991.

59. B.Kernighan, S.Lin. "An efficient heuristic procedure for partitioning graphs" , Bell Syst. Tech.J., vol 49, pp. 291-307, Feb, 1970.

60. C.Fiduccia, R.Mattheyses. "A linear time heuristics for improving network partitions", in 19th ACM/IEEE Design automation conference, 1982, pp. 175-181.

61. C.J.Alpert, A.B.Kahng. "Geometric Embeddings for Faster and Better Multi-Way Netlist Partitioning", in 30th ACM/IEEE Design automation conference, 1993, pp. 743-748.

62. D.Schweikert, B.Kernighan, "A proper model for partitioning of electrical circuits", in 19th Desighn automation workshop, 1972, pp. 57-62.

63. Thang Nguyen Bui, Byung-Ro Moon. "GRCA: A Hybrid Genetic Algorithm for Circuit Ratio-Cut Partitioning". IEEE Transactions on computer-aided desighn of integrated circuits and systems, vol.17, No.3, March 1998. , pp.193204.

64. A Chatterjee and R. Hartley. A new simultaneous circuit partitioning and chip placemant approach based on semulated annealing. Proceedings of design Automation Conference, pages 36-39. 1990.

65. Saab and Y.Rao. An evolution based approach to partitioning asic system. Proceedings of Design Automation Conference, pages 767-770, 1989.

66. Chandraserharam R., Subharamanian S., Chaundhury S. Genetic algorithm for node partitioning problem and application VLSI design. IEEE Proceedings E, Vol. 140, №5, 1993, p.255-260.

67. Лебедев Б.К. Разбиение на основе эволюционной адаптации // Известия ТРТУ. Тематический выпуск "Интеллектуальные САПР". Таганрог: Изд-во ТРТУ, 1999. №3. С.308-309.

68. Лебедев Б К, Золотько А. Ю. Применение гиперграфов для решения задач компоновки БИС// В кн. Сборник материалов конференции молодых ученых и специалистов по проблемам микроэлектроники. Москва, 1980,с 167-168 .

69. Лебедев Б.К, Золотько А.Ю. Метод оптимального разбиения гипер-графов.//В кн. Методы и программы решения оптимизационных задач на графах и сетях. Новосибирск, 1980, с 45 46 .

70. Thang Nguyen Bui, Byung-Ro Moon. "GRCA: A Hybrid Genetic Algorithm for Circuit Ratio-Cut Partitioning". IEEE Transactions on computer-aided desighn of integrated circuits and systems, vol.17, No.3, March 1998, pp. 193-204.

71. Рябец M. H. Применение генетических алгоритмов в задаче К-кусочного разбиения. Известия ТРТУ №3, 1999. Материалы международной научно-технической конференции "Интеллектуальные САПР", стр.116.

72. Курейчик В. М., Курейчик В. В. Генетический алгоритм разбиения графа. Известия Академии наук. Теория и системы управления, №4, 1999.

73. Т. N. Bui, В. R. Moon. "Genetic algorithm and graph partitioning", IEEE Trans. Comput., vol.45, pp. 841-855,1996.

74. D. Levine. "A genetic algorithm for the set partitioning problem", in 5th Int. Conf. Genetic Algorithms, 1993, pp.481 -487.

75. D. R. Jones, M. A. Beltramo. "Solving Partitioning Problem with Genetic Algorithms". Proceed, of 4th Int. Conf. on Genetic Algorithms, San Diego, July 1991.

76. Апанович 3.B., Марчук А.Г. Современные стили проектирования и алгоритмы размещения при проектировании СБИС. // Системная информатика. Проблемы современного программирования.Вып.1.-Новосибирск: Наука, Сибирское отделение, 1997. С. 260-292.

77. Xu J., Guo P. -N., Cheng С. -К., Cheng С. -К. Sequence-Pair Approach for Rectiliner Module Placement / IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, april 1999.-vol.18, №4.-pp. 484-493.

78. Курейчик B.M., Лебедев Б.К., Марков B.B. О решении задач размещения специализированной подсистемы САПР электронных конструктивных узлов // Электронное моделирование. 1986. №3. С.66-71.

79. Murata Н., Fujiyoshi К., Nakatake К., Kajatani Y. Restangular -Packing- Based Module Placement, ICCAD, 1995.-pp. 472-479.

80. Лебедев Б.К, Меркухин E.H. Оптимизация тепловых характеристик при размещении элементов. // Вопросы радиоэлектроники. Серия: "Электронная вычислительная техника (ЭВТ), 1988, вып. 11, с. 186-194.

81. Курейчик В.М., Лебедев Б.К. Математическое обеспечение конструкторского и технологического проектирования с применением САПР: Учебное пособие. Таганрог: ТРТИ, 1986, 53с.

82. Лебедев Б.К. Размещение разногабаритных элементов с минимизацией требуемых для трассировки ресурсов коммутационного поля // Автоматизированное проектирование в радиоэлектронике и приборостроении. Л.: ЛЭТИ, 1989.С.100-105.

83. Лебедев Б.К., Кобыляцкий И.А. Интеллектуальный модуль апрок-снмации разногабаритных элементов и формирования позиций на коммутационном поле. //Создание интеллектуальных САПР СБИС и электронных средств. Москва. Радио и связь. 1980, с. 23-24.

84. Лебедев Б.К. Архитектура гибкой САПР монтажа и коммутации. //Автоматизация проектирования в радиоэлектронике и приборостроении. Л.ЛЭТИ,1987, с. 105-110.

85. Лебедев Б.К., Лях А.В., Мухлаев А.В. Алгоритм эволюционного размещения и эволюционной трассировки кристалла СБИС. // Тезисы докладов Всесоюзной НТК "Проектирования вычислительных средств". Каунас,1989, с. 219-221.

86. Курейчик В.М., Глушань В.М., Щербаков Л.И. Комбинаторные аппаратные модели и алгоритмы в САПР. М., Радио и связь, 1990 г. 216 с.

87. Ковал ев А.В., Коноплев Б.Г. Метод мозаичного синтеза топологии заказных СБИС.// Известия вузов. Электроника.- М.: Радиоэлектроника, №4, 1999.-е. 52-57.

88. Лебедев Б.К. Размещение на основе коллективной адаптации. //Интеллектуальные САПР. Таганрог.ТРТИ.1994. Выпуск 4, с. 67 74.

89. Лебедев Б.К. Методы размещения на основе коллективной эволюционной адаптации.//Тезисы докладов международной конференции "Новые информационные технологии в науке образовании и бизнесе". Крым. 1993, с. 51-52.

90. Eisenmann Н., Johanes F,M. Genetic Global Placement and Floorplan-ning. DAC. San Francisko, California, 1998.

91. R.M.KIing . Placement by simulated evolution . Ms thesis , Coordinated Seine Lab .,College of Engn ,,Univ.of Illinois at Urbane -Champaign, 1987.

92. Батищев Д И., Власов C.E. ,Булгаков И.В. Плотное размещение разногабаритных объектов на плоскости с помощью генетических алгоритмов .-XXIII International School and Conference on Computer Aided Design.-Yalta- Gurzuff, 1996.-354 с

93. K.Shahoolkar and P. Mazumder. A genetic approach to standard cell placement. Proceedings of First European Design Automation Conference, March1990.

94. Sechen С. VLSI Placement and Global Routing Using Simulated Annealing. Kluwer, B.V., Devenler, The Netherlands.

95. C.Sechen and A.Sangiovanni Vincentelli, " The Timberwolf placement and routing package," IEEE J. Solid.State Circuits, Vol. SC-20, p.p.510-522, 1985.

96. D.Hill and D.Shugerd. Global Routing Considerations in a Cell Synthesis system. Proceedings of Design Automation Conference, 1990.

97. J.Cong and B.Preas. A new algorithm for standard cell global routing. Proceedings of IEEE International Conference on Computer-Aided Design, pp. 176-179, 1988.

98. Burman, H. Chen, and N. Sherwani. Improved global routing using X-geometry. Proceedings of 29th Annual Allerton Conference on Communications, Computing, and Control, October 1991.

99. C.Chang , M.Sarrafzadeh, and C.K. Wong. A powerful global router .-Based on sterner min-max trees. Proceedings of IEEE International Conference on Computer Aided Design, November 7-10 1989. pp. 2-5.

100. K.W.Lee and C.Sechen. A new global ronter for row based layout. Proceedings of IEEE International Conference on Computer - Aided Design, November,1998.

101. C.Chiang, M.Sarrafraden, C.K.Wong. A Weighted Steiner - Tree -Based Global Router, Manuscript, 1992.

102. J.Huang, X.Hong, C.Cheng and E. Kuh. An Efficient Timing Driven Global Routing Algorithm. Proceedings of 30th Design Automation Conference, p.p. 596 - 600, June, 1993.

103. Лебедев Б.К. Метод оптимального распределения ресурсов платы // Техническая кибернетика. 1980. №1. С.217.

104. Лебедев Б.К. Распределение ресурсов коммутационного поля // Автоматизация проектирования электронной аппаратуры. Таганрог: ТРТИ, 1988. Вып.1. С. 89-92.

105. Лебедев Б.К. Глобальная трассировка как процесс коллективной адаптации // Интеллектуальные САПР. Таганрог, 1995, Вып.5. с.134-136.

106. Лебедев Б.К. Глобальная трассировка на основе генетической эволюции // Известия ТРТУ. Тематический выпуск "Интеллектуальные САПР". Таганрог: Изд-во ТРТУ, 2000. №2. С.93-102.

107. Лебедев Б.К. Трассировка на основе коллективной адаптации, рефлексии и генетической эволюции.// Тезисы докладов 22 международной конференции» « CAD-95». Крым, Гурзуф, 1995, с. 330-331.

108. J-M. Но, G. Vijayan, and C.K. Wong, "New algorithms for the rectilinear Steiner tree problem," IEEE Trans. Computer Aided Design, vjl.9,pp.l85-193, Feb. 1990.

109. Ting-Hai Chao and Yu-Chin Hsu. Rectilinear steiner tree construction by local and global refinement. IEEE Transactions on CAD of Integrated Circuits and Systems, 13:303-309, March 1994.

110. F.K. Hwang, D.S. Richards,, and P. Winter, The Steiner Tree Problem. North-Holland, 1992.

111. J.L. Ganley, and J.P.Cohoon, " Improved computation of optimal . rectilinear Steiner minimal trees," Int. J. Comput. Geometry and Appl., vol.7, pp.457-472,1997.

112. M.Zachariasen, Rectilinear full Steiner tree generation," Networks, vol. 33, pp. 125-143,1999.

113. G. Robins and A. Zelikovsky, "Improved Steiner tree approximations in graphs," in Proc. 11th ACM-SIAM Ann. Symp. Discret. Algorithms,2000, pp.770779.

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

115. Gilbert E.W., Pollan И.О. Steiner minimal trees. "SIAM J. Appl. Math.", 1968, v/16, No 1, p.1-29.

116. Hohah M. On Steiner problem with rectiliner distanse. "SIAM J. Appl. Math.", 1966, v/14, No 2, p.255-265.

117. Лебедев Б.К. Интеллектуальная процедура построения дерева Штей-нера //Методы и программы решения оптимизационных задач на графах и сетях. Часть 1 .Новосибирск, 1989, с. 108 109.

118. Лебедев Б.К. Интеллектуальный модуль построения кратчайших связывающих сетей.//Создание интеллектуальных САПР СБИС и электронных средств. Тезисы докладов. Москва. Радио и связь, 1990.С 69-70.

119. Лебедев Б.К. Интеллектуальная процедура построения дерева Штей-нера на основе процедур отсечки и сужения.//Известия Таганрог. Издательство ТРТУ. № 1, 2000, с. 89 94.

120. Курейчик В.М., Лебедев Б.К., Витмайер М.Я. Построение улучшающих алгоритмов компоновки размещения и трассировки на основе метода адекватного преобразования логических функций // Управляющие системы и машины. 1986. №6. С.38-49.

121. Лебедев Б.К., Витмаер М.Я. Об одном подходе к решению вопроса улучшения топологии соединений. //Вопросы радиоэлектроники. Серия: "Электронная вычислительная техника (ЭВТ). Вып. 9, 1987,с. 117-123.

122. Лебедев Б.К. Перекоммутация соединений в канале на основе коллективной адаптации // Известия ТРТУ. Материалы XLIII научно-технической конференции. Таганрог: ТРТУ, 1998, №3(9), с.95-100.

123. C.Y. Roger Chen and Cliff Yungchin Hou. A Pin Permutation IEFF Transactions on Computer Aided Design of Integrated Circuits and Systems, Vol. 14, No. 8, 1995, pp. 1033-1037.

124. C.Yang and D.F.Wong, "Optimal channel pin assignment", IEEE Trans. Computer-Aided Design, CADlO(ll): 1413-1423, November, 1991.

125. Y.Cai, D.F.Wong, "Minimizing channel density by shifting blocks and terminals," in Proc. IEEE Int. Conf. on Computer-Aided Design, 1991, pp524-527.

126. T. W. Her, Ting-Chi Wang, D.F. Wong, "Performance-Driven Channel Pin Assignment Algoritms", IEEE Trans. Computer-Aided Design of Integrated Circuits and Syst., vol. 14, №7, pp. 851-857, July, 1995.

127. Лебедев Б.К. Динамическое распределение инвариантных контактов. //Автоматизация технического проектирования цифровой аппаратуры Каунас, 1985.

128. Лебедев Б.К. Динамический канальный трассировщик. // Автоматизированное проектирование в радиоэлектронике и приборостроении. Л.ЛЭТИ, 1990, с 80 -84.

129. Лебедев Б К. Канальная трассировка на основе динамических принципов и методов минимизации комбинаторной размерности. //Интеллектуальные САПР. Таганрог, ТРТИ,1995,с. 11 20.

130. Лебедев Б.К. Канальная трассировка на основе генетических процедур // Известия ТРТУ. Тематический выпуск "Интеллектуальные САПР". Таганрог: Изд-во ТРТУ, 1997. №3. С.53-60.

131. Давиденко В.Н. Алгоритм задачи канальной трассировки, основанный на методе генетического поиска / Интеллектуальные САПР, Таганрог, 1996, Вып. 3, с.46-49.

132. Taniguch N., Liu X., Sakamoto А.& Shimomoto Т. "An Approach to channel routing using genetic algorithms", Bulletin of Faculty of Engineering, To-kyshima University, no. 38, pp. 99-112,1993.

133. Liu, X., Sakamoto, A., Shimamoto, T. Restrictive Channel Routing with Evolution Programs. Trans. IEICE, vol.E76-A, no.10, 1993. pp.1738-1745.

134. Rahmani, A.T. and Ono N. A Genetic Algorithm for Channel Routing Problem, in Proc. 5th Intl. Conf. on GAs, 1993. pp. 494-498.

135. Y.L. Lyn, Y.C. Hsu, and Tsai. Silk: A simulated evolution router. IEEE Transactions on Computer-Aided Design, 8:1108-1114,October,1989.

136. T.Cho, S. Pyo, and J. Heath. Parallex: A parallel approach to switch box routing.IEEE Transactions on CAD of Integrated Circuits and Systems, 13:684-693, June 1994.

137. M.Marek-Sadowska. Switch box routing: a retrospective. NTEGRA-TION, the VLCI Journal, 13, pp. 36-65, 1992.

138. W.K.Luk. A greedy switch box router. INTEGRATION, the VLCI Journal, 3: pp. 129-149, 1985.

139. J.P.Cohoon and P.L.Heek. Beaver: A computational geometry based tool for switch box routing. IEEE Transactions on Computer-Aided Design, 7:684-697,June,1988.

140. Щемелинин B.M. Данилин A.A. Многоуровневая модель трассировки свичбокса. Известия вузов. ЭЛЕКТРОНИКА. №3.1999. С.65-72.

141. B.M Kureichic ,В.К. Lebedev, E.V, Nuzhnov. Approach to genetic switch box gridles routing. Известия ТРТУ.Тематический выпуск "Интеллектуальные САПР. Таганрог. Издательство ТРТУ,1999, №3. С.89-95.

142. V.M. Kureichik, B.K. Lebedev, E.V. Nuzhnov. Apporatch to genetic switch box intellectual maze routing. Известия ТРТУ. Интеллектуальные САПР. Таганрог, Издательство ТРТУ, №3. С.9-14.

143. Лебедев Б.К. Трассировка в коммутационном блоке на основе генетических процедур // Известия ТРТУ. Тематический выпуск "Интеллектуальные САПР". Таганрог: Изд-во ТРТУ, 1998. №2 . С.7-21.

144. Лебедев Б.К, Цыбуля К.В. Математическая модель топологии матричных БИС и ее простая укладка. Автоматизация проектирования средств вычислительной техники и радиоэлектроники.Каунас,1985 с 66-67.

145. Курейчик В.М.,Лебедев Б.К., Цыбуля К.В. Математическая модель топологии матричных БИС одноуровневой металлизации. Электронное моделирование, 1988 №10 с.83-87.

146. Cong J., and Liu C.L. Over-the-Cell Channel Routing, IEEE Trans. Computer Aided Design , vol. 9,1 4, 1990. pp. 408 418.

147. B. Wu, N.A. Sherwani, N.D. Holmes, and M. Sarratzaden, "Over-thetbcell Routers for new cell model," in Proc.29 ACM/IEEE Design Automation Conf.l992, pp. 604-607

148. S. Bhingarde, A. Panyam, and N.A. Sherwani, "Middle terminal cell models for efficient over-the-cell routing in hign performance circuits," IEEE Trans. VLSI Syst.Dtc 1993, pp.462-472.

149. J. Cong, B. Preas, and C.L. Liu, "Physical models and efficient algorithms for over-the-cell routing in standard cell design," IEEE Trans. Computer-Aided Design, vol. 12, pp.723-734, May, 1993.

150. S.Danda, X.Liu, S. Madhwapathy, A. Panyam, Naveed Shervani, and I. G. Tollis, "Optimal Algorithms for Planar Over-The-Cell Routing Problems," IEEE Trans. Computer-Aided Design of Integrated Circuits and Syst., vol. 15, №11, pp. 1365-1377, Nov. 1996.

151. T. W. Her and D.F. Wong, "On Over-the-Cell Channel Routing with Cell Orientations Consideration", IEEE Trans. Computer-Aided Design of Integrated Circuits and Syst., vol. 14, №16, pp. 766-772, June, 1995.

152. Лебедев Б.К. Однослойная трассировка в приканальной надъячееч-ной области. // Известия ТРТУ: Интеллектуальные САПР, Изд-во ТРТУ, 1997, №3, с. 184-193.

153. Каляев А.В. и др. Автоматизация проектирования вычислительных структур. Ростов н/Д: Изд-во Ростовского университета, 1983. 224 с.

154. Карелин В.П., Калашников В.А. Применение метода бивалентного программирования для решения некоторых задач технического проектирования. Микроэлектроника. 1979. Вып. 5. Т. 8.

155. N.J. Naclerio, S. Masuda, and К. Nakajima, "The via minimization problem is NP-complete," IEEE Trans. Comput. Vol.38, pp.1604-1608, Nov., 1989.

156. C.-P. Hsu, "Minimum-via topological routing," IEEE Trans. Computer-Aided Design of Integrated Circuits Syst., vol. CAD-2, pp.235 246, Oct. 1983.376

157. M.Marek-Sadowska, "An unconstrained topological via minimizaition problem for two-layer routing, IEEE Trans. Computer-Aided Design of Integrated Circuits Syst., vol. CAD-3, pp. 184-190, July 1984.

158. H.-A.Choi, K. Nakajima, and C.S. Rim, " Graph bipartization and via minimization," SIAM J. Appl. Math., vol. 2, no. 1 pp. 38-47, Feb. 1989.

159. K. Ahn and S. Sahni, "Constrained via minimization," IEEE Trans. Computer-Aided Design of Integrated Circuits Syst., vol. 12, pp. 273-282, Feb. 1993.

160. C.-C. Chang and J. Cong, "An efficient approach to multi-layer layer assignment with an application to via minimization," in Proc. 34th ACM/IEEE Design Automation Conf., 1997, pp. 600-603.

161. Лебедев Б.К. Разнесение по слоям соединений на основе коллективной адаптации. Известия ТРТУ. Таганрог, Изд-во ТРТУ, 1996, №3, c.l 11.

162. Лебедев Б.К. Разнесение соединений по слоям на основе коллективной адаптации Известия ТРТУ, Интеллектуальные САПР, Таганрог Издательство ТРТУ,1999,№3, с.176-187.

163. Лебедев Б.К. Адаптивный алгоритм разнесения соединений по слоям. // Известия ТРТУ: Интеллектуальные САПР, Изд-во ТРТУ, 2001, №4, с.115-124.