Исследование и разработка методов трассировки проводящих покрытий БИС на основе стратегии эволюционного поиска

В настоящее время основным фактором ускорения научно-технического прогресса, повышения качества общественного производства, является полная автоматизация производственных процессов, одним из главных направлений которой является широкое и повсеместное использование средств вычислительной техники /1/. В то же время появление новых разработок в области вычислительной техники, создание компьютерных современных моделей, обладающих высокой степенью быстродействия, являются основными предпосылками для разработок новых технологий производства основных узлов электронно-вычислительной аппаратуры (ЭВА), основными элементами которых являются БИС и СБИС. В настоящее время вследствие постоянного роста степени интеграции элементной базы ЭВА и повышения требований к параметрам узлов ЭВА актуальной становится проблема создания методов проектирования БИС, выполняемых без участия человека /2/. Одним из решений этой проблемы в наши дни является использование систем автоматизированного проектирования (САПР). Как отмечено в /164/, теоретические исследования математических методов и разработка на их основе эффективных алгоритмов, методик и средств позволяют обоснованно решать сложные задачи сокращения сроков проектирования оптимальных дискретных систем, что резко повысит их экономическую эффективность. Поэтому основной проблемой развития вычислительной техники яв^ ляется создание высокопроизводительных вычислительных средств, способных решать поставленные задачи. В области создания эффективных САПР в настоящее время на первый план выходит задача разработки новейших САПР, учитывающих специфику различных методов проектирования /9−12/, т. е. главная цель — разработка САПР, осуществляющих оптимальное проектирование элементной базы ЭВА, в т. ч. при минимуме временных затрат /160/.

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

Под проблемой автоматизированного проектирования топологии БИС будем в соответствие с /2,153,154/ понимать решение ряда задач, включающих представление исходной электрической схемы в виде математических или матричных моделей, размещение типовых фрагментов топологии на поле кристалла, проектирование коммутационных связей между отдельными элементами, распределение фрагментов трасс в проводящих слоях, контроль топологии. В качестве предварительного шага, предшествующего этапу размещения элементов /152/, решается задача компоновки /5/. Среди работ, представляющих описание методов и алгоритмов, разработанных к настоящему времени для реализации основных этапов проектирования, отметим работы /147,153,154/. Заметим также, что использование в качестве элементной базы БИС и СБИС высокой степени интеграции требует создания эффективных САПР, имеющих полный набор проектных процедур для организации цикла проектирования, но, в ряде случаев, обладающих быстродействием, недоступным для классических однопроцессорных ЭВМ. В частности, применение высокопроизводительных суперЭВМ с параллельной архитектурой создает возможности для реализации таких алгоритмов проектирования, которые не могут быть эффективно реализованы на классических однопроцессорных ЭВМ, например, алгоритмы, связанные с комбинаторным перебором, необходимым для определения вариантов расположения соединений. В работе /146/, посвященной проблемам создания эффективных САПР БИС на базе МВС, отмечается, что «проектирование БИС высокой степени интеграции требует создания эффективных САПР для организации сквозного цикла проектирования БИС за приемлемое сточки зрения пользователя время. К вычислительным системам, которые могут в полной мере удовлетворить этим требованиям, относятся многопроцессорные вычислительные системы (МВС). Положительный эффект при решении задач автоматизации проектирования на МВС может быть достигнут, в основном, за счет их распараллеливания, что в общем случае может привести к значительному сокращению временных затрат» .

Существенный вклад в решение проблемы разработки теоретических и прикладных вопросов построения высокопроизводительных вычислительных систем и эффективных САПР внесли работы таких ученых, как Каляев A.B., Курейчик В. М., Мелихов А. Н., Селютин В. И., Корячко В. П., Норенков И. П., Батищев Д. И., Лошаков В. Н., Бершадский A.M., Зайцева Ж. Н., Баталов Б. В., ГлушковВ.М., Закревский А. Д., Коган Б. М., Карцев М. А., Марчук Г. И., Поспелов Д. А., Прангишвили И. В., Пухов Г. Е., Шилейко A.B., Абрайтис Л.Б.

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

Следует заметить, что задачи оптимальной организации вычислительных устройств на различных этапах проектирования в общем случае имеют комбинаторный тип и формулируются в виде задач о покрытии, раскраске, устойчивых множествах и др. Поскольку большинство из этих задач 1ЧР полные, то это в ряде случаев создает определенные трудности, связанные с большими временными затратами при получении оптимального варианта и увеличении размерности задачи. Как отмечено в /164,165/, для повышения размерности существует ряд путей, основными из которых являются: отмеченная выше возможная замена «ручного» проектирования машинным, т. е. использование систем автоматизации проектированиязамена точных алгоритмов проектирования приближенными, что может позволить получить решения, достаточно близкие к оптимальным за допустимое время. Таким образом, когда точные эффективные алгоритмы для трудных дискретных задач неизвестны, особое значение приобретают для них приближенные эффективные методы, в которых трудоемкость снижается за счет ослабления требований к точности решения /168/.

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

Автор считает своим долгом выразить глубокую признательность засл. деятелю науки и техники РФ, д.т.н., проф. Курейчику В. М., д.ф.-м. наук, проф. Сухинову А. И. без помощи которых невозможно было бы проведение исследований и написание данной работы.

ЦЕЛЬЮ ДАННОЙ РАБОТЫ ЯВЛЯЕТСЯ разработка и исследование методов решения задачи трассировки, позволяющих устранить основные недостатки локально-оптимальных методов, ориентированных на реализацию на различных типах ЭВМ и супер-ЭВМ, а также использующих эволюционную оптимизацию для получения оптимальных и квазиоптимальных вариантов разводки при реализации на коммутационном поле (КП). Для достижения цели решены следующие задачи: разработан алгоритм формирования сети трасс (ФСТ) и алгоритм подсчета числа трасс в сети, произведено сравнение трудоемкости алгоритмов ФСТ и Дейкстрыразработан эвристический алгоритм построения множества кратчайших вариантов деревьев цепей на основе алгоритма ФСТразработана методика получения множества оптимальных и квазиоптимальных вариантов размещения деревьев на поле кристалла, в т. ч. с использованием эволюционной оптимизации, разработаны модификации основных генетических операторов для решения задачи формирования оптимальной клики графа пересеченийразработан алгоритм формирования сети соединений произвольной длины, ориентированный для реализации на многопроцессорной системеразработан метод оптимального отображения монтажной поверхности в распределенной памяти МВСразработан пакет прикладных программ, проведены экспериментальные исследования, получены результаты решения тестовых примеров, не уступающие по качеству известным результатам.

МЕТОДЫ ИССЛЕДОВАНИЙ. При решении поставленных задач в работе использовались, в основном, теоретико-графовые методы и алгоритмы, элементы теории параллельных алгоритмов и параллельных вычислительных систем, методы аналитической геометрии. Для экспериментальной реализации представленных в работе параллельных алгоритмов была использована сопроцессорная многопользовательская станция проектирования НР9000 серии 700.

НАУЧНАЯ НОВИЗНА РАБОТЫ заключается в разработке алгоритмов, позволяющих получить решение задачи трассировки соединений, ликвидирующих основные недостатки локально-оптимальных методов, осуществляющих формирование множества оптимальных и квазиоптимальных вариантов прокладки с помощью генетической оптимизации, ориентированных для реализации на многопроцессорных и однопроцессорных ЭВМразработке методики построения и размещения кратчайших связывающих деревьев цепей на основе выделения клик графа пересечений, в т. ч. с использованием эволюционной оптимизации, разработке модификаций основных генетических операторов для решения задачи определения оптимальной кликиразработке алгоритма формирования сети трасс кратчайшей длины и подсчета их числа, а также параллельного алгоритма ФСТ, методики параллельной реализации основных операций на МВСразработке метода отображения дискретной монтажной поверхности в распределенной памяти МВС для различных конфигураций дискретов.

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ работы определяется решением ряда задач, использующих разработанные алгоритмы, программы для сокращения сроков проектирования, повышения размерности и числа получаемых оптимальных и квазиоптимальных вариантов. ^.

Исследования автора проводились в рамках госбюджетной НИР «Создать систему конструкторского проектирования заказных БИС и исследовать эффективность ее реализации на МВС», выполняемой в НИИ МВС при ТРТУ/166,167/. Научные и практические результаты данной работы использованы при разработке БИС и СБИС в ТРТУ, а также при проектировании двухслойных гидроакустических печатных плат в НИИ «Бриз» г. Таганрога.

В СКБ «Виброприбор» внедрены алгоритмы оптимального размещения графовой модели схемы при минимизации пересечений в процессе проектирования эскиза схемы электрического ключа управления гидравликой комбайна.

В научно-производственном объединении «Интеграл» г. Минска при разработке специальной телевизионной и видеотехники использованы методы построения деревьев цепей и их оптимального размещения на основе алгоритма формирования сети трасс.

Экспериментальная реализация параллельных алгоритмов, представленных в работе, производилась на сопроцессорной многопользовательской станции проектирования НР9000 серии 700 модель 712/60 Минского завода «Транзистор». Разработанные в работе параллельные методы включены в состав библиотеки матобеспечения многопользовательской системы НР9000.

Акты об использовании результатов работы в промышленности приведены в приложении.

НА ЗАЩИТУ ВЫНОСЯТСЯ: алгоритм формирования сети кратчайших трасс на КП, алгоритм подсчета их числаприменение алгоритма ФСТ для построения кратчайших связывающих деревьев цепей, методика оптимального размещения цепей на основе формирования оптимальной клики графа пересеченийразработка основных генетических операций, реализующих процесс эволюционного поиска оптимальной кликипараллельный алгоритм ФСТ и методика его реализации на МВСметодика отображения дискретного КП в распределенной памяти МВСрезультаты экспериментальной реализации генетического алгоритма и сравнительные характеристики тестовых примеров.

АПРОБАЦИЯ. Результаты данных исследований докладывались на 33, 34 студ. НТК в 1986, 1987 г., на межреспубликанской СНТК в г. Омске в 1987 г., на 1 межреспубликанской СНТК «Разработка АСУ», в г. Киеве в 1987 г., на научно-технической школе молодых ученых и специалистов «Организационно-экономические вопросы создания вычислительных комплексов и систем» в 1988 г. в Москве, на 35 и 36 НТК Таганрогского радиотехнического института в 1989 и 1990 г., на Международной НТК молодых ученых и специалистов «Молодые ученые в решении комплексной программы НТП стран — членов СЭВ» в 1989 г. в г. Киеве, на НТК молодых ученых и специалистов Таганрогского радиотехнического института «Архитектура ЭВМ и машинное моделирование» в 1989 г., на межреспубликанской НТК молодых ученых и аспирантов «Микропроцессорные системы и средства автоматики» в г. Новосибирске в 1990 г., на Всесоюзном семинаре «САПР в машиностроении и приборостроении» в г. Ульяновске в 1990 г., на 4 Международной конференции молодых ученых «Актуальные проблемы разработки АСУ» в г. Паланге в 1990 г., на 7 НТС «Математическое обеспечение систем с машинной графикой» в 1990 г. в Тюмени, на 37 и 38 НТК ТРТИ в 1991 и 1992 г., на школе-семинаре «Методы автоматизированного проектирования РЭА и СБИС» в г. Киеве в 1991 г., на 16 НТК НИИ приборостроения в г. Жуковском в 1991 г., на НТК «Автоматизация проектирования РЭА и ЭВА» в г. Пензе в 1991 и 1992 г., на НТК «Информационные технологии и системы. Технологические задачи механики сплошных сред» в 1992 г. в Воронеже, на 2 Международной НТК «Актуальные проблемы фундаментальных наук» в Москве в 1994 г, на 4 Всероссийской научной конференции молодых ученых «Техническая кибернетика, радиоэлектроника и системы управления» в Таганроге в 1998 г, на 4 Всероссийской НТК «Новые информационные технологии в научных исследованиях и образовании» в Рязани в 1999 г., на Международной НТК «Проблемы совершенство.

10 вания зерноуборочной техники: конструирование, организация производства, эксплуатация и ремонт" в Ростове-на-Дону в 1999 г.

ПУБЛИКАЦИИ. По теме диссертации опубликованы 22 работы (статьи и тезисы докладов на конференциях, отмеченных выше). В ВНТИЦ зарегистрировано 2 отчета по госбюджетной НИР, выполненных при участии автора.

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

4.3. ВЫВОДЫ.

В данной главе получены следующие результаты.

1. Разработан пакет прикладных программ, осуществляющий реализацию на ЭВМ представленных в работе методов и алгоритмов.

2. Проведено экспериментальное исследование разработанного генетического алгоритма с использованием тестовых схем Burstein difficult channel, Burstein difficult switchbox, показавшее возможность получения результатов разводки, не уступающих по качеству известным, а для схемы Burstein difficult channel число пересечений цепей минимизировано на 1, длина параллельных прокладок в слоях уменьшена на 3 единицы.

3. Представлены графические и табличные зависимости ЦФ от числа генераций при использовании элитной и «рулеточной» селекции. Экспериментальные результаты показали целесообразность применения элитной селекции, при которой достигается более высокая частота сходимости к оптимальному значению. Показано также изменение отношения частоты сходимости в зависимости от размера популяции. При минимальном размере п = 50 частота для элитной и «рулеточной» селекции составляет 1 и 0,6, а при максимальном размере п = 200 1 и 1 для схемы Burstein difficult channel, для схемы Burstein difficult switchbox данные значения при п = 50 составляют 0 и 0 (т. е. сходимость не дает ни один тип селекции), при п = 250 0,90 и 0,75 (т.е. частота сходимости достаточно высока).

5.

ЗАКЛЮЧЕНИЕ

.

В заключение сформулируем и обобщим основные научные и практические результаты данной работы.

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

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

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

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

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

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

7. Получены оценки трудоемкости: для алгоритма ФСТ от числа вершин N сети 0(N), для алгоритма построения ДШ от числа вершин ДШ N 0(N). Представлены соотношения и графические зависимости, определяющие возможность получения качественного выигрыша по трудоемкости и числу операций. Для алгоритма ФСТ данное соотношение имеет вид N>3+6C (ST), где C (ST) — число маршрутов в сетидля алгоритма построения ДШ величина качественного выигрыша возрастает с увеличением N вследствие различия в степени оценок трудоемкости (кубическая у алгоритма Ханана и квадратичная).

8. Разработан пакет прикладных программ, включающий программу трассировки дискретного КП. Проведено экспериментальное исследование генетического алгоритма, что позволило для тестовых схем получить результаты, не уступающие по качеству известным и превосходящие их. Представлены также графические и табличные зависимости ЦФ от числа генераций при использовании селекции типа «колесо рулетки» и элитной, при которой была достигнута более высокая частота сходимости к оптимальному значению. Получены результаты, показывающие изменение частоты сходимости в зависимости от размера популяции. В частности, при максимальном размере 250 для схемы Burstein difficult switchbox частота сходимости достаточно высока и составляет для элитной и рулеточной селекции соответственно 0,90 и 0,75.