Разработка и исследование биоинспирированных алгоритмов диверсификации трассировочных ресурсов СБИС на основе стандартных ячеек тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат наук Пурчина Ольга Андреевна

• Пурчина Ольга Андреевна
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Пурчина Ольга Андреевна

ВВЕДЕНИЕ

1 АНАЛИЗ ПРОБЛЕМ И МЕТОДОВ ПРОЕКТИРОВАНИЯ СБИС

1.1 Современные технологии и задачи конструкторского проектирования

СБИС

1.2. Общая структура процесса трассировки

1.3. Анализ подходов и методов повышения трассируемости коммутационной среды ячеечных СБИС

1.4 Анализ методов бионспирированной оптимизации

1.4.1 Классификация методов оптимизации

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

1.4.3 Альтернативная поисковая адаптация

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

1.4.5 Методы роевого интеллекта

1.4.6 Муравьиный алгоритм

1.5 Выводы

2 БИОИНСПИРИРОВАННЫЙ ПОДХОД К РЕШЕНИЮ ЗАДАЧИ ПЕРЕРАСПРЕДЕЛЕНИЯ СОЕДИНЕНИЙ МЕЖДУ ВЫВОДАМИ НА ОСНОВЕ МОДЕЛЕЙ КОЛЛЕКТИВНОЙ АДАПТАЦИИ БИОИНСПИРИРОВАННЫХ СИСТЕМ

2.1 Основные положения

2.2 Постановка задачи перераспределения соединений между выводами

2.3 Биоинспирированный алгоритм перераспределения выводов на основе моделирования адаптивного поведения муравьиной колонии

2.4 Биоинспирированный адаптивный алгоритм перераспределения соединений между выводами на основе интеграции механизмов коллективной альтернативной адаптации и моделирования отжига

2.5 Гибридный бионспирированный алгоритм перераспределения соединений на основе интеграции моделей адаптивного поведения муравьиной колонии и коллективной альтернативной адаптации

2.6 Выводы

3 БИОНСПИРИРОВАННЫЙ АЛГОРИТМ ТРАССИРОВКИ В ПРИКАНАЛЬНОЙ НАДЪЯЧЕЕЧНОЙ ОБЛАСТИ

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

3.2 Построение модифицированного графа поиска решений

3.3 Построение эскиза однослойной трассировки на основе комбинаторной оптимизации «муравьиное дерево»

3.4 Интеграция процедур повышения трассируемости коммутационной сети и моделироваия отжига с процедурами канальной трассировки

3.5 Выводы

4 РАЗРАБОТКА ПРОГРАММНОГО КОМПЛЕКСА И

ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ

4.1 Структура представления данных

4.2 Описание особенностей программной системы

4.3 Выводы

ЗАКЛЮЧЕНИЕ

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

ПРИЛОЖЕНИЕ А Акты об использовании и внедрение результатов

диссертационной работы

ПРИЛОЖЕНИЕ Б Свидетельства о государственной регистрации программ для ЭВМ

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

ВВЕДЕНИЕ

Возникшая в 60-х годах прошлого века технология производства интегральных схем развилась от схем, которые объединяли несколько транзисторов до схем, в которые интегрируются миллионы транзисторов. Вначале интегральные схемы представляли собой диоды, транзисторы и набор резисторов, данные схемы предназначались для выполнения определенной логической операции. Сегодня интегральные схемы позволяют реализовывать сложнейшие функции, их минимальные геометрические размеры достигают 0,16 нанометра. Сверхбольшие интегральные схемы (СБИС) составляют основу элементной базы радиоэлектронной аппаратуры. Современные технологии позволяют осуществлять проектирование схем с очень высоким быстродействием, минимальными размерами и низкой стоимостью. В связи с постоянным ростом сложности решаемых задач, при проектировании СБИС ведущим производителям микросхем в США пришлось объединиться и разработать новый совместный план развития технологий микроэлектроники. Позднее план развития перерос в программу, которая стала международной и к её реализации были подключены основные мировые компании, занимающиеся полупроводниками. Название данной программы: «International Technology Roadmap for Semiconductors, ITRS» (Международная маршрутная карта для полупроводниковой промышленности). Один раз в два года составляется и публикуется квалифицированный прогноз развития полупроводниковой технологии, данный прогноз составляется членами экспертного совета, помимо этого редакция выпускает дополнения к ITRS [1]. В ближайшие годы ожидается уменьшение размеров интегральных схем вплоть до одного слоя атомов. Современные технологии позволяют размещать порядка пятнадцати миллионов транзисторов на одной схеме размерамом около 25 миллиметров. Добиться больших успехов в эволюции производства интегральных схем позволила автоматизация различных этапов проектирования [2]. При проектировании топологий СБИС повсеместно применяются системы автоматизации, в которых большинство этапов полностью или частично автоматизированы [3].

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

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

Основные подзадачи, решаемые в процессе построения топологии, относится к классу МР-полных, время решения которых растет экспоненциально.

Таким образом, разработка новых полиномиальных методов решения этих задач является актуальной проблемой [6,8].

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

5

Задача трассировки достаточно трудоемка и размерна, в связи, с чем для ее решения используется иеррархичечкий подход. Уровни трассировки принято подразделять на 2 вида: детальная и глобальная [1,3,6]. При глобальной трассировке происходит разделение всей области на небольшие подобласти, а ключевая задача заключается в размещении соединений по полученным подобластям. Необходимо отметить, что во внимание должны приниматься: временные задержки и реализуемость соединений. Детальная трассировка заключается в реализации соединений в каждой подобласти. Детальная трассировка разделяется на трассировку блоков (switchbox - англ., блок) и канальную трассировку, а также известна задача надъячеечной трассировки [29].

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

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

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

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

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

В работе задача повышения трассируемости КС путем диверсификации трассировочных ресурсов решается двумя способами.

При первом способе трассировочные ресурсы КС увеличиваются путем введения дополнительной надъячеечной области (НЯО) для трассировки.

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

Ключевым принципом первого подхода выступает дополнительное использование для трассировки областей, которые подключаются к каналу сверху и снизу. Эти области имеют один трассировочный слой. Они размещаются непосредственно над ячейками (over the cell), которые ограничивают канал. На основе анализа загрузки канала некоторые соединения могут из канала направляться в надъ-ячеечную область, что уменьшит плотность канала. Задачей «надъячеечных» трассировщиков является построение в надъячеечных областях максимальных пла-нарных эскизов топологий, что приводит к разгрузке в каналах и приводит к повышению трассировочной способности [1,2].

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

Главным принципом второго подхода является перераспределение соединений между эквивалентными выводами. Ключевым условием в данном случае выступает постоянность логических функций схем. Будем считать функционально эквивалентными две совокупности выводов лишь тогда, когда переключение взаимосвязанных с ними соединений, не будет приводить к нарушениям в логике схемы. Решение задачи, связанной с подсоединением соединений к выводам может осуществляться [2]:

- в процессе планирования кристаллов;

7

- при расположении на них блоков;

- в случае глобальной трассировки;

- при канальной трассировке.

Цель переназначения в первую очередь заключается в снижении плотностей зон трассировок, уменьшении протяженности соединений и т.д.

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

Для решения трудоемких задач канальной трассировки в наши дни все большую популярность приобретают различные методы, базирующиеся на использовании методов искусственного интеллекта [5]. Достаточно интенсивно развивается научное направление Natural Computing (природные вычисления). Данное направление объединяет известные математические методы, созданные на основе принципов природных механизмов принятия решений [9-14].

Использование эволюционного моделирования при решении задач канальной трассировки было весьма успешным [1,15,21-23]. Но, несмотря на успешность, имелись и определенные недостатки. Они заключались в следующем:

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

- получение целого ряда схожих решений;

- получение ряда «плохих» решений.

Сейчас наблюдается рост интереса к разработкам методов инспирированных природными системами [7]. Основное их направление - роевые мультиа-гентные методы интеллектуальной оптимизации [10-12]. Рой агентов рассматривают в качестве многоагентной системы. Каждый агент данной системы функционирует по очень простым правилам и автономно, в данном случае можно говорить о роевом интеллекте (swarm intelligence) - например, муравьинным. Данные методы показывают «хорошие» результаты при решении комбинаторных задач [13,14].

Основными достоинствами муравьиных алгоритмов являются:

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

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

- применение жадной эвристики, которая способствует нахождению «хороших» решений на ранних стадиях поиска.

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

Подходы к организации адаптационных процессов рассматриваются в работе [4]. Труды М.Л. Цетлина, Д.А. Поспелова способствовали возникновению направления «Адаптивное поведение», связанного с конструированием и исследованиями искусственных агентов, приспосабливающихся к среде обитания.

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

Объектом исследования является топология наноразмерных компонентов библиотечных элементов, 1Р-блоков платформы для реализации целого класса систем на кристалле ^оС), в виде полузаказной СБИС на основе базовых стандартных библиотечных элементов.

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

Целью диссертационной работы является повышение трассируемости

КС при проектировании топологии СБИС путем диверсификации трассировочных ресурсов КС.

Для достижения поставленной цели в работе решены следующие основные задачи:

1. Разработан биоинспирированный алгоритм перераспределения соединений между выводами на основе моделей адаптивного поведения МК.

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

3. Разработан гибридный биоинспирированный алгоритм перераспределения цепей между выводами, в основе которого лежит интеграция моделей адаптивного поведения МК и КАА.

4. Разработан биоинспирированный алгоритм планарной надъячеечной трассировки на основе парадигмы метода поиска решений «муравьиного дерева».

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

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

Научная новизна. В работе получены следующие новые научные результаты, которые выносятся на защиту:

1. Биоинспирированный алгоритм перераспределения соединений между выводами на основе модифицированной метоэвристики роевого интеллекта, отличающейся тем, что МК разбивается на кластеры, и поиск решения задачи осуществляется коллективом кластеров муравьёв, что позволяет улучшить качество

получаемых решений. Предложена, в отличие от канонической парадигмы, мо-

10

дифицированная жадная стратегия построения ориентированного маршрута. (Пункты 1,3 паспорта специальности 05.13.12, страницы 56-63 диссертационной работы).

2. Биоинспирированный алгоритм перераспределения соединений между выводами на основе модели КАА, отличающейся от канонической постановки использованием нерегулярной структуры расположения выводов на коммутационном поле, использованием иерархической структуры эквивалентных групп цепей как внутри канала, так и на всем пространстве коммутационного поля, что позволяет снизить комбинаторную сложность задачи. (Пункты 1,3 паспорта специальности 05.13.12, страницы 64-74 диссертационной работы).

3. Гибридный биоинспирированный алгоритм перераспределения соединений между выводами, в основе которого лежит интеграция моделей адаптивного поведения МК, а также КАА, отличающийся повышенной сходимостью и позволяющий увеличить способность алгоритма выходить из локальных оптимумов. (Пункты 1,3 паспорта специальности 05.13.12 страницы 75-76 диссертационной работы).

4. Биоинспирированный алгоритм трассировки в надъячеечной области, который, в отличие от канонической метоэвристики муравьиного алгоритма, в качестве модели для представления решений использует дерево решений, что исключает использование «нелегальных» решений и дополнительных трансформаций при декодировании результатов и позволяет повысить их качество. (Пункты 1,3 паспорта специальности 05.13.12, страницы 86-95 диссертационной работы).

К числу наиболее важных научных результатов диссертации относятся:

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

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

3. Новая архитектура гибридного алгоритма перераспределения соединений между выводами на основе интеграции моделей адаптивного поведения МК и КАА.

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

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

Практическая значимость. Основные теоретические и практические результаты диссертационной работы использованы в фундаментальных госбюджетных научно-исследовательских работах, выполненных по грантам, финансируемых РФФИ, в которых автор участвовал в качестве исполнителя: №13-01-00343 -«Разработка адаптивных алгоритмов доступа к удаленным данным»; №14-01-00634 - «Разработка теоретических основ криптоаналитических алгоритмов в системах защиты информации на основе биоинспирированных методов»; №15-01-05129 - «Разработка алгоритмов адаптивного решения задач оптимизации на основе методов искусственных иммунных систем»; №17-01-00375 - «Раз-

12

витие теории криптоаналитических алгоритмов в системах защиты информации на основе комбинированных биоинспирированных методов и иммунных технологий искусственного интеллекта»; № 17-07-00997 - «Разработка гибридных моделей роевого интеллекта на основе интеграции модифицированных методов и алгоритмов колонии муравьев, пчелиного роя и коллективной альтернативной адаптации для решения задач интеллектуального анализа данных и принятия решений».

Разработанные биоинспирированные алгоритмы используются в Научно-производственном предприятии «Дон» (г. Ростов-на-Дону) и в ООО «ЭнергоПлюс» (г. Аксай). Кроме того, полученные результаты применяются в учебном процессе Донского государственного технического университета на кафедре «Автоматизация и математическое моделирование в нефтегазовом комплексе» при чтении курсов лекций по дисциплинам «Программирование и алгоритмизация», «Моделирование систем и процессов». Акты об использовании и внедрении результатов работы прилагаются.

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

Апробация работы. Основные результаты диссертации обсуждались и были одобрены на Международных научно-технических конференцих: «Интеллектуальные системы» (AIS-12,13,15,17,20) (с. Дивноморское, 2012,2013,2015,2017,2020 гг.), «Всероссийской конференции молодых ученых, аспирантов и студентов» (г. Таганрог, 2012 г, 2013г), VIII Международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (г. Коломна, 2015г), «Всероссийской научно-технической конференции: Студенческая наука для развития информационного

общества» (г.Ставрополь, 2015), Physics and Mechanics of New Materials and Their

13

Applications (Phenma 2016, 2017): abstracts and schedule of the International Conference, Surabaya, Indonesia; International Conference on Information Technologiess in Business and Industry 2018, 2019; ITBI 2018; Tomsk Polytechnic University Tomsk; Russian Federation; VIII International Scientific Conference Transport of Siberia -2020.

Публикации. По материалам диссертации опубликовано 28 печатных работ, в том числе, 5 статей в издании, входящем в базу цитирования SCOPUS, 5 статей в рецензируемых научных журналах, входящих в перечень ВАК, 2 свидетельства о государственной регистрации программы для ЭВМ в Федеральной службе по интеллектуальной собственности.

Структура и объем диссертационной работы. Диссертационная работа состоит из введения, четырех разделов, заключения, библиографического списка из 119 наименований, 10 страниц приложений. Работа содержит 137 страниц и включает 47 рисунков и 5 таблиц.

Во введении приводится обоснование актуальности темы диссертационной работы, её научной новизны и практической значимости, а также формулируется цель и задачи работы.

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

14

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

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

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

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

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

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

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

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

1 АНАЛИЗ ПРОБЛЕМ И МЕТОДОВ ПРОЕКТИРОВАНИЯ СБИС

1.1 Современные технологии и задачи конструкторского проектирования

СБИС

Такой термин как СБИС используется людьми уже на протяжении более 30 лет, с момента расположения на кристалле нескольких десятков тысяч транзисторов [1,2]. На данный момент общее количество транзисторов, размещаемых на больших кристаллах, достигает миллиарда. В результате этого был предложен новый термин УБИС (Ультра большие интегральные схемы) [3].

Список литературы диссертационного исследования кандидат наук Пурчина Ольга Андреевна, 2022 год

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. C. Spanos G. May, Fundamentals of Semiconductor Manufacturing and Process Control.: IEEE: John Wiley and Sones, 2008.

2. H. Kaeslin, Digital Integrated Circuit Design. Cambridge: Cambridge University Press, 2008.

3. Гулякович Г.Н. и др. Перспективы и проблемы полупроводниковой наноэлек-троники // Инженерный Вестник Дона, №2. 2012.

4. Kahng B. Wong, Nano-CMOS Design for Manufacturability. New York: John Wiley & Sons, 2009.

5. J.Kawa, C.Chiang, Design for Manufacturability and Yield for Nano-Scale CMOS.: IEEE: Springer, 2007.

6. В. Стешенко., "Программируемые логические интегральные схемы: обзор архитектур и особенности применения," Схемотехника, №2, 2001.

7. Малышев И. В. Немудров В. Г., "Состояние и перспективы отечественных разработок СБИС типа «система на кристалле»". Системы и средства связи, телевидения и радиовещания, №1,2, 2003.

8. Немудров В.Г., "Основные проблемы, задачи и этапы формирования современной инфраструктуры проектирования СБИС «система на кристалле»". Электронная промышленность, №1, 2003.

9. Марченко А. «Современные проблемы автоматизации проектирования топологии СБИС», МЭС - 2006.

10. Норенков И.П. Основы автоматизированного проектирования. - М.: Изд-во МГТУ имени Н.Э.Баумана, 2006.-360с.

11. Sherwani N.A. Algorithms for VLSI Physical Design Automation. Norwell, Kluwer Academic Publishers, 1995. - Р. 538.

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

13. Палташев, Т.Т. Введение в проблему разработки и производства СБИС. Gatch-

ina Nanoelectronics, Phoenics, Arizona. 2009.

117

14. D. Mehta, S. Sapatnekar, C. Alpert, Handbook of Algorithms for Physical Design Automation. NY: CRC Press, 2009.

15. Щемелинин В. М., Автоматизация топологического проектирования БИС. Москва: МИЭТ, 2001.

16. Charles J. Alpert, Dinesh P. Mehta, Sachin S. Sapatnekar. Handbook of algorithms for physical design automation. CRC Press, New York, USA, 2009.

17. Roy J.A. High-Performance routing at the nanometer scale, IEEE Trans.Comput. -Aided Design Integr. Syst., vol. 27, issue. 6, pp. 1066-1077, June 2008.

18. Немудров В., Мартин Г. Системы-на-кристалле. Проектирование и развитие. -М: Техносфера, 2004.

19. Казеннов Г. Основы проектирования интегральных схем и систем. - М.: Бином. Лаборатория знаний, 2005. - 295с.

20. Cong, C. Wu, 'Global Clustering-Based Performance-Driven Circuit Partitioning', Proc. ISPD, 2002.

21. Andrew B. Kahng, "Layout decomposition for double patterning lithography," in ICCAD, 2008.

22. Лебедев Б.К., Лебедев В.Б., Лебедев О.Б., Методы, модели и алгоритмы размещения - Ростон-на-Дону: Изд-во ЮФУ, 2015 - 150с.

23. Лебедев Б.К. Интеллектуальные процедуры синтеза топологии СБИС. - Таганрог: Изд-во ТРТУ, 2003.

24. Pan D., Cho M., Yuan K. Manufacturability Aware Routing. Foundations and Trends in Electronic Design Automation № 4(1). 2010.

25. Ho T.-Y., Chang Y.-W., Chen S.-J. Full-Chip Nanometer Routing Techniques. Springer 2007.

26. Sun W., Cong R., Chen X., Qin Z. R-CA: A Routing-Based Dynamic Channel Assignment Algorithm in Wireless Mesh Networks. International Conference.

27. Kureichik V.V., Kureichik V.M., Malioukov S.P., Malioukov A.S. Algorithms for Applied CAD Problems. - Berlin Heidelberg: Springer-Verlag, 2009. - 487 p.

28. Alpert, C. J., Dinesh P. M., Sachin, S. S.: Handbook of Algorithms for Physical design Automation, Auerbach Publications Taylor & Francis Group, USA, 2009. on UIC/ATC. 2010. - P. 228-232.

29. Лебедев Б.К., Лебедев В.Б. Глобальная трассировка на основе роевого интеллекта // Известия ЮФУ. Изд-во ТТИ ЮФУ, 2010, №7. С. 32-39.

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

31. Лебедев Б.К., Воронин Е.И. Генетический алгоритм распределения соединений по слоям при многослойной глобальной трассировке СБИС. // Известия Южного федерального университета. Технический науки. — Таганрог: 2012, Т.132.

32. Лебедев Б.К., Лебедев О.Б. Многослойная глобальная трассировка методом коллективной адаптации //МЭС-2012. V Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем - 2012». Сборник трудов.- М.:ИППМ РАН, 2012. - С.251-257.

33. Yoshimura, T. And Kuh, E.S. Efficient algorithms for channel routing. IEEE Trans. Computer Aided Design Integrated Circuits & Syst., vol.1, no.1, 1982. - pp.25-35.

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

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

36. Курейчик В.М. Кныш Д.С., "Генетический алгоритм трассировки коммутационных блоков Известия вузов," Электроника № 5(79). Схемотехника и проектирование, 2009. - С. 28 - 34.

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

38. 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, Nov. 1996. - P. 1365-1377.

39. 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, June, 1995. №16. - P. 766-772.

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

41. C.Yang and D.F. Wong. Optimal channel pin assignment// IEEE Transactions Computer - Aided Design, CAD 10(11):1413-1423,November 1991.

42. 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. July, 1995. - Р. 851-857.

43. Shashank Prasad, "Fast Congestion Aware Routing for Pin Assignment", VLSI Design 2008. VLSID 2008. 21st International Conference on, - pp. 343-347, 2008.

44. Fei He, W.N.N. Hung, Xiaoyu Song, Ming Gu, Jiaguang Sun, "Segmented channel routing with pin rearrangements via satisfiability", Circuits and Systems 2005. ISCAS 2005. IEEE International Symposium on, - pp. 6248-6251 Vol. 6, 2005.

45. Лебедев О.Б. Генетический алгоритм перекоммутации выводов для улучшения канальной трассировки. Известия ТРТУ, Интеллектуальные САПР, Таганрог, 1997, - С.64 - 71.

46. F. He, W. N. N. Hung, X. Song, M. Gu, J. Sun, "A satisfiability formulation for FPGA routing with pin rearrangements", International Journal of Electronics, vol. 94, -pp. 857, 2007.

47. Алексеев В.Ю. Комплексное применение методов дискретной оптимизации. Москва, "Наука", 1987 г.

48. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М. : Мир, 1979.

49. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — Пер. с англ.- М. 2004.

50. Грэхем И. Объектно-ориентированные методы. Принципы и практика: Пер. с

англ. - М.: Издательский дом «Вильямс», 2004. - 880 с.

120

51. Макконел Дж.. Основы современных алгоритмов, 2-е дополненное издание.: Пер. с англ.- М.: Техносфера, 2004.

52. Csiszar S. Optimization Approaches for Logistic Problems -Vehicle Routing Problem with Time Windows // PhD Dissertation. - Budapest, Hungary, submitted: August 2006.

53. Концепция поиска оптимальных решений при проектировании. Научное издание. Под ред. Б.К.Лебедева. Таганрог: Изд-во ТТИ ЮФУ, 2010.

54. Корниенко В.П. Методы оптимизации. - М.: Высш.шк., 2007.

55. M. Sh. Levin, "Combinatorial optimization in system configuration design," in Automation and Remote Control, vol. 3, 2009, - С. 519-561.

56. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой: учебное пособие - М: Издательство МГТУ им. Н.Э. Баумана, 2014. - 446 с.

57. Курейчик В.В., Курейчик В.М., Гладков Л.А., Сороколетов П.В. Бионспирированные методы в оптимизации.- М.: Физмалит, 2009.

58. S.Kirkpatrick, C.D.Gellat and M.P.Vecchi. Optimization by simulated annealing. Science, 220:671-680, May, 1983.

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

60. Holland John H., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. USA: University of Michigan, 1975.

61. Goldberg David E. Genetic Algorithms in Search, Optimization and Machine Learning. USA: Addison-Wesley Publishing Company, Inc., 1989.

62. Гладков Л. А., Курейчик В.В. , Курейчик В.М. Генетические алгоритмы. Под ред. В.М. Курейчика. М.: Физматлит, 2006. - 320 c.

63. В.Б. Лебедев Нечеткое планирование СБИС на основе эволюционной адаптации. Известия Южного федерального университета. Технические науки. 2003.

64. В.М. Курейчик, Лебедев Б.К., Лебедев О.Б. Поисковая адаптация. - М.: Физ-матлит, 2006.

65. Редько В.Г. Эволюция, нейронные сети, интеллект: модели и концепции эволюционной кибернетики. - М.: Комкнига, 2005.

66. От моделей поведения к искусственному интеллекту. Под ред. В.Г. Редько -М.: КомКнига, 2006.

67. Гладков Л.А., Курейчик В.В., Курейчик В.М. и д.р. Оптимизация на основе эволюционного и нейросетевого моделирования: Монография. - Таганрог: Изд-во ТРТУ, 2004.

68. Бионические информационные системы и их практические применения / под ред. Л.А. Зинченко, В.М. Курейчика, В.Г. Редько. - М.: ФИЗМАТЛИТ, 2011. -288 с.

69. Цетлин М.Л. Исследования по теории автоматов и моделированию биологических систем.- М.: Наука. 1969.

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

71. Курейчик В.М., Лебедев Б.К., Лебедев В.Б. Адаптация в задачах проектирования топологии. Проблемы разработки перспективных микро- и наноэлектронных систем - 2010 // Сборник научных трудов/ под ред. А.Л. Стемпковского. - М.: ИППМ РАН, 2010. - С.170-177.

72. Курейчик В.М., Лебедев Б.К., Лебедев О.Б., Чернышев Ю.О. Адаптация на основе самообучения. - Ростов-на-Дону: РГАСХМ ГОУ 2004. - 146 с.

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

74. Сигорский В.Г. Проблемная адаптация в системах автоматизированного проектирования. Известия высших учебных заведений: Радиоэлектроника. Т. 31, №6, 1988.

75. Курейчик В.В., Курейчик В.М., Родзин С.И. Теория эволюционных вычислений.- М.: Физмалит. 2012.

76. G. Lamont D. van Veldhuizen C. Coello, Evolutionary Algorithms for Solving Multi-Objective Problems. New York: Springer, 2007.

122

77. Норенков И. П., Арутюнян Н.М. Эволюционные методы в задачах выбора проектных решений // Электронное научно-техническое издание "Наука и образование". 2007.URL: http://technomag.edu.ru/doc/68376.html.

78. Гладков Л.А., Кравченко Ю.А., Курейчик В.В., Курейчик В.М, Лебедев Б.К, Лебедев О.Б., Нужнов Е.В., Полупанов А.А., Сороколетов П.В. Интеллектуальные системы проектирования СБИС на основе эволюционных методов: Монография.-Таганрог: Изд-во Технологического института ЮФУ, 2008.-184 с. 200 экз.

79. J. P. Cohoon, "Evolutionary Algorithms for the Physical Design of VLSI Circuits," Advances in Evolutionary Computing: Theory and Applications, - pp. 683-712, 2003.

80. Пурчина О.А. Применение эволюционных алгоритмов анализа функционирования искусственных нейронных сетей. / О.А. Пурчина, А.Ю. Полуян, Д.В. Маршаков // Известия ЮФУ. - 2013. - №3. - С. 55-58.

81. Engelbrecht A. P. Fundamentals of Computational Swarm Intelligence. John Wiley & Sons, Chichester, UK, 2005.

82. R. Poli, J. Kennedy, and T. Blackwell. Particle swarm optimization. An overview. Swarm Intelligence, 1(1):33-57, 2007.

83. M. Clerc. Particle Swarm Optimization. ISTE, London, UK, 2006.

84. В.Ю.Карлусов «Моделирование роя частиц в задаче поиска на дискретной плоскости с заданными ограничениями». Международный научный журнал «Инновационная наука» №04-3/2017.

85. Курейчик В.М., Кажаров A.A. Роевой интеллект в решении графовых задач // Сборник трудов XVI Международной конференции по мягким вычислениям и измерениям. Санкт-Петербург. 2013.

86. Курейчик В.В., Запорожец Д.Ю. Роевой алгоритм в задачах оптимизации. Известия ЮФУ. Технические науки. 2010. № 7 (108). - С. 28-32.

87. Курейчик В.М., Кажаров А.А. Использование роевого интеллекта в решении NP-трудных задач // Известия ЮФУ. Технические науки. - 2011. - № 7. -С. 30-36.

88. Б.К. Лебедев, В.Б. Лебедев Процедуры канальной трассировки, на основе гибридизации роевого интеллекта с генетическим поиском //Проблемы разработки

123

перспективных микро- и наноэлектронных систем - 2010 /Сборник научных трудов / под ред. А.Л. Стемпковского. - М.: ИППМ РАН, 2010. - С.214-220.

89. Б.К. Лебедев, В.Б. Лебедев Поисковые процедуры канальной трассировки, базирующиеся на моделировании адаптивного поведения роя частиц в пространстве решений с неупорядоченным лингвистическим шкалированием. //Известия ЮФУ. Изд-во ТТИ ЮФУ, 2009, №12. - С. 15-22.

90. M. Dorigo and T. Stützle. Ant Colony Optimization. MIT Press, Cambridge, MA, 2004.

91. M. Dorigo, T. Stützle, Ant Colony Optimization: Overview and Recent Advances. M. Gendreau and Y. Potvin, editors, Handbook of Metaheuristics, 2nd edition. Vol. 146 in International Series in Operations Research & Management Science, pp. 227-263. Springer, Verlag, New York, 2010.

92. Лебедев О.Б. Модели адаптивного поведения муравьиной колонии в задачах проектирования. - Таганрог: Изд-во ЮФУ, 2013.

93. Курейчик В.М., Кажаров А.А. О некоторых модификациях муравьиного алгоритма. //Известия ЮФУ. Изд-во ТТИ ЮФУ, 2008, №4(81). - C .5-11.

94. LuciC P., Teodorovic D. Computing with Bees: Attacking Complex Transportation Engineering Problems // International Journal on Artificial Intelligence Tools. - 2003. -№12. - P. 375- 394.

95. Teodorovic D., Dell'Orco M. Bee Colony Optimization - a Cooperative Learning Approach to Complex Transportation Problems // Advanced OR and AI Methods in Transportation: Proceedings of 16th Mini-EURO Conference and 10th Meeting of EWGT (13-16 September 2005). - Poznan: Publishing House of the Polish Operational and System Research, 2005. - P. 51-60.

96. Лебедев В.Б. Метод пчелиной колонии в комбинаторных задач на графах //Тринадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-212. Труды конференции. Т. 2. М.: Физматлит, 2012. - с. 414-422.

97. J. Kennedy. Swarm Intelligence. In Handbook of Nature-Inspired and Innovative Computing: Integrating Classical Models with Emerging Technologies. A. Y. Zomaya (Ed.), pages 187-219, Springer US, Secaucus, NJ, 2006.

98. Alpert C. J., Mehta D. P., and Sapatnekar S. S., Handbook of Algorithms for Physical Design Automation. Boston, MA: Auerbach, 2009.

99. J.Cong. Pin Assignment With Global Routing. Proceedings Of International Conference on Computer-Aided Design, pp. 302-305, 1989.

100. 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. P. 1033-1037.

101. 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, July, 1995. №7. - P. 851-857.

102. Jian Sun, Yinghai Lu, Hai Zhou, Changhao Yan, Xuan Zeng, "Post-routing layer assignment for double patterning with timing critical paths consideration", Integration, vol. 46, - pp. 153, 2013.

103. Xu He, Sheqin Dong Pin assignment for wire length minimization after floorplan-ning phase//2009 IEEE 8th International Conference on ASICPage s: 1294 - 1297.

104. Черепнина. (Пурчина) О.А. Перераспределение соединений между выводами в канале методами роевого интеллекта / Черепнина. (Пурчина) О.А., Лебедев О.Б //Труды Конгресса по интеллектуальным системам и информационным технологиям "AIS-IT'12".T.1. М: Изд-во Физматлит. 2012. - C. 191-197.

105. Пурчина О.А. Муравьиный алгоритм перераспределение соединений между выводами. / О.А. Пурчина // Информационные технологии, системный анализ и управление: материалы Х Всерос. науч.-конф. Молодых ученых, аспирантов и студентов/ ЮФУ (ТРТИ).-Таганрог, 2012. - Т.2. - С. 28-34.

106. Пурчина О.А. Адаптивный алгоритм перераспределения соединений между выводами. / О.А. Пурчина // Конгресс по интеллектуальным системам и информационным технологиям (IS&IT'13), п. Дивноморское, 2-9 сент. /ЮФУ (ТРТИ) -Таганрог, 2013. - C. 199-208.

107. Пурчина О.А. Биоинспирированный алгоритм перераспределения соединений между выводами / О.А. Пурчина //Электронный журнал. Информатика, вычислительная техника и инженерное образование. Св. № ФС77-39729 от 29.04.2010г. - Таганрог: ТТИ ЮФУ, 2014, №3(18).

108. Пурчина О.А. Перекоммутация соединений между эквивалентными выводами методами роевого интеллекта/ Пурчина О.А.,Чернышев Ю.О., // Конгресс по интеллектуальным системам и информационным технологиям (IS&IT'15), п. Дивноморское, 2-9 сент. /ЮФУ(ТРТИ) - Таганрог, 2015. - C. 247-254.

109. Пурчина О.А. Algorithm of redistribution of connections between conclusions on the basis of royevy intelligence. / O.A. Purchina, A.Y. Poluyan D. D. Fugarov // Schedule of international conference on "physics and mechanics of new materials and their applications" (Phenma-2015): abst. Azov, Russia, 2015.

110. Пурчина О.А. Smart-intelligence-based algorithm of connections permutation between pins. / O.A. Purchina, Yu. O. Chernyshev, A. Yu. Poluyan, D. D. Fugarov // Journal of Theoretical and Applied Information Technology.-2015.-Vol.80, №1. Р.15-20.-Режим доступа: http://www.jatit.org/volumes/Vol 180No1/2Vol80No 1.

111. Пурчина О.А. Гибридный алгоритм перераспределение соединений между выводами. / О.А. Пурчина // //Информационные технологии, системный анализ и управление - ИТС АиУ-2013/ Сборник трудов XI Всероссийской конференции молодых ученых. Таганрог: Изд-во ЮФУ.2013 - Т.1. - C. 147-152.

112. Raidl G. R. A Unified View On Hybrid Metaheuristics. In: Lecture Notes In Computer Science, 2006. - Springer, Verlag. - P. 1-12.

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

114. 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, May, 1993. - P. 723-734.

115. Лебедев Б.К., Лебедев О.Б. Моделирование адаптивного поведения муравьиной колонии при поиске решений, интерпретируемых деревьями // Известия

ЮФУ. Изд-во ТТИ ЮФУ, 2012, №7. - С. 27-35.

126

116. Пурчина О.А. Однослойная трассировка в приканальной надъячеечной области на основе алгоритма муравьиного дерева /Лебедев Б.К., Пурчина О.А. //Труды конгресса по интеллектуальным системам и информационным технологиям «К-ГГ'14». Научное издание в 4-х томах. - М.: Физматлит, 2014. - Т.1. - С. 58-69.

117. Пурчина О.А.Роевой алгоритм трассировки в приканальной надъячеечной области. / О.А. Пурчина, О.Б. Лебедев // Известия ЮФУ, 2015, №6, С.125-138.

118.Пурчина О.А Роевой алгоритм повышения плотности топологии СБИС/ Лебедев Б.К., Лебедев О. Б., Пурчина О.А.//Сборник научных трудов УШ Международной научно-практической конференции "Интегрированные модели и мягкие вычисления в искусственном интеллекте". Т.2. М.: Изд-во Физматлит, 2015. - С. 624-634.

119. Лебедев Б.К. Модифицированный роевой алгоритм "муравьиное дерево" в задаче диверсификации трассировочных ресурсов / Б.К. Лебедев, О.Б. Лебедев, О.А. Пурчина // Информационные технологии. 2019. Т. 25. № 11. - С. 670-678.

ПРИЛОЖЕНИЕ А Акты об использовании и внедрение результатов диссертационной работы

ООО НПП «Дон»

344010, г. Ростов-на-Дону. ул. Малюгиной. 163/72, к.З тел. [phone]-74 fax . [phone] I lex. № öbfccn от CJ CL.lt г.

АКТ

об использовании научных результатов диссертационной работы на соискание ученой степени кандидата технических наук Пурчиной O.A., выполненной на тему: «Разработка и исследование биоинспирированных алгоритмов диверсификации трассировочных ресурсов СБИС на основе

стандартных ячеек»

11астоящий акт составлен в том, что в НПО «Дон» используются перечисленные ниже материалы диссертационной работы Пурчиной O.A. «Разработка и исследование биоинспирированных алгоритмов диверсификации трассировочных ресурсов СБИС на основе стандартных ячеек» представленной на соискание ученой степени кандидата технических наук по специальности 05.13.12 - Системы автоматизации проектирования.

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

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

В связи с этим особо актуальна разработка новых эффективных методов решения задач конструкторского проектирования.

Конкретно использованы следующие исследования и разработки:

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

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

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

исключаем использование дополпитель.....х трансформаций при декодировании

решений, позволяет отбросить большое количество "нелегальных" решений и тем самым повысить качество получаемых решений. Алгоритм был реализован па языке Воткни! С I I для 1Г)1Ш типа 1ИМ Р(\

Энерго

Плюс

ООО «Энерго Плюс»

Р/с 40702810300100001534 в филиале Xsl ОАО КБ «Центр-инвест» г. Аксай к/с 3 0101810600000000786, БИК 046027786, КПП 610201001, ИНН 6102018992 Юридический адрес: 346720, Ростовская область, г. Аксай, ул. Западная За Фактический адрес: 346720, Ростовская область, г. Аксай, ул. Западная За тел. [phone], E-mail: [e-mail]

Утверждаю:

Директор ООО «Энерго Плюс»

^М'Шлл Ys J

'_A.A. Лудов

' JO » "/S 20 /£

АКТ

внедрения результатов кандидатской диссертации O.A. Пурчиной.

Настоящий акт составлен в том, что в ООО «Энерго Плюс» используются перечисленные ниже материалы диссертационной работы Пурчиной O.A. - «Разработка и исследование биоинспирированных алгоритмов диверсификации трассировочных ресурсов СБИС на основе стандартных ячеек», представленной на соискание ученой степени кандидата технических наук.

В частности были использованы следующие результаты кандидатской диссертации Пурчиной О. А.:

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

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

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

Применение указанных материалов диссертационной работы Пурчиной O.A. в виде алгоритмов и программ способствовало снижению суммарной плотности каналов.

Технический директор

ООО «Энерго Плюс»

А.Я. Яковлев

АКТ

об использовании результатов диссертационной работы Пурчиной O.A. в учебном процессе кафедры «Автоматизация и математическое моделирование в нефтегазовом комплексе»

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

1 .Описанный в первой главе диссертационной работы анализ классических методов оптимизации используется в курсах «Программирование и алгоритмизация», «Моделирование систем и процессов», в качестве учебного материала и тематики курсовых и выпускных квалификационных работ.

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

Декан ф-та «Энергетика и нефтегазопромышленность» д.т.н., проф

Зав. каф. «АММ НГК» д.т.н., проф.

B.JI. Талонов кУ-tfe «у Ю.я. Герасименко

АКТ

об использовании научных результатов диссертационной работы на соискание ученой степени кандидата технических наук Пурчиной O.A., на

тему: «Разработка и исследование биоинспирированных алгоритмов диверсификации трассировочных ресурсов СБИС на основе стандартных ячеек» при работе над фундаментальной госбюджетной НИР, выполненной по гранту, финансируемой РФФИ, № 17-07-00997

Настоящий акт составлен в том, что ниже перечисленные результаты диссертационной работы использованы в фундаментальной госбюджетной научно-исследовательской работе, выполненной по гранту, финансируемой РФФИ, в которых автор участвовал в качестве исполнителя № 17-07-00997 «Разработка гибридных моделей роевого интеллекта на основе интеграции модифицированных методов и алгоритмов колонии муравьев, пчелиного роя и коллективной альтернативной адаптации для решения задач интеллектуального анализа данных и принятия решений»:

1. Использована новая архитектура роевого алгоритма перераспределения соединений между выводами на основе интеграции моделей адаптивного поведения муравьиной колонии и коллективной альтернативной адаптации.

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

3. Использована программа однослойной трассировки в приканальной надъячеечной области на основе алгоритма муравьиного дерева.

Декан ф-та Энергетика и нефтегазопромышленность

Зав. кафедрой Автоматизация и математическое моделирование в нефтегазовом комплексе

^ ^ Ю.Я. Герасименко

ПРИЛОЖЕНИЕ Б Свидетельства о государственной регистрации программ для ЭВМ