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

005531гьо

Бегляров Вадим Валерьевич

На правах рукописи

............

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ ДЛЯ МОДЕЛИРОВАНИЯ СХЕМОТЕХНИЧЕСКИХ РЕШЕНИЙ

Специальность 05.13.12 - Системы автоматизации проектирования (вычислительная техника и информатика)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

- 4 ИЮЛ Ш

Таганрог - 2013

005531265

Работа выполнена на кафедре «Информационные системы и радиотехника» Южно-Российского государственного университета экономики и сервиса

Научный руководитель: Берёза Андрей Николаевич, кандидат

технических наук, доцент

Официальные оппоненты: Лебедев Борис Константинович,

доктор технических наук, профессор, Южный федеральный университет, профессор кафедры «Системы автоматизированного проектирования»

Галушкин Николай Ефимович, доктор технических наук, профессор, ЮжноРоссийский государственный университет экономики и сервиса, профессор кафедры «Радиоэлектронные

системы»

Ведущая организация: Федеральное государственное уни-

тарное предприятие «Государственное конструкторское бюро аппаратно-программных систем

«СВЯЗЬ», г.Ростов-на-Дону

Защита диссертации состоится «13» июня 2013г. в 14-20 на заседании диссертационного совета Д212.208.22 при Южном федеральном университете по адресу: 347928, Таганрог, пер. Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344000, Ростов-на-Дону, ул. Пушкинская, 148.

Автореферат разослан «30» апреля 2013г.

Ученый секретарь ,

диссертационного совета {/У! Целых Александр Николаевич

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

Разработке новых методов решения уравнений математических моделей и увеличению эффективности схемотехнического проектирования в настоящее время посвящено множество как отечественных, так и зарубежных публикаций. Среди публикаций по теме исследования можно выделить труды Русакова, С.Г., Норенкова, И.П., Анисимова, В.И., Дмитриевича, Г.Д., Петренко, А.И., Сигорского, В.П., Перминова, В.Н., Денисенко, В.В., Kuh, E.S., Sangiovanni-Vincentelli, A.L., Kuehlmann, A., Nelson, V.P., Kundert, K.S. и т.д. Следовательно, задача разработки модифицированных методов решения уравнений математических моделей схемотехнических решений, способных увеличить общую производительность САПР ЭВТ, является АКТУАЛЬНОЙ.

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

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

1. Провести анализ эффективности существующих методов решения уравнений математических моделей, применяющихся в САПР ЭВТ.

2. Разработать модифицированные методы решения систем линейных алгебраических уравнений (СЛАУ) и систем нелинейных уравнений большой размерности, полученных на схемотехническом этапе моделирования СБИС.

3. Разработать методику решения уравнений математических моделей СБИС.

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

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

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

Положения, выносимые на защиту:

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

2. Методика решения уравнений математических моделей подсхем СБИС.

3. Гибридный эволюционный алгоритм, ориентированный на решение уравнений математических моделей схемотехнических решений.

4. Инструментальная среда разработки и исследования эволюционных алгоритмов для подсистемы схемотехнического проектирования ЭВТ.

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

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

4

Научная новизна работы состоит в:

- разработке модифицированного метода, способного повысить эффективность решения систем линейных алгебраических уравнений (СЛАУ) большой размерности, полученных на этапе моделирования схемотехнических решений за счет улучшения соотношения времени выполнения и погрешности решения (стр. 67);

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

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

- разработке гибридного эволюционного алгоритма, ориентированного на решение уравнений математических моделей подсхем СБИС, полученных на этапе моделирования схемотехнических решений (стр. 73-106).

Практическую ценность работы представляют:

- кроссплатформенный подключаемый модуль, основанный на модифицированных методах решения уравнений математических моделей схемотехнических решений. Данный модуль может быть использован в индустриальных САПР ЭВТ (стр. 109-110);

- инструментальная среда разработки и исследования эволюционных алгоритмов (стр. 110-124).

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

- аналитической ведомственной целевой программе «Развитие научного потенциала высшей школы» (2009-2011 годы)» по теме «Разработка и исследование бионических алгоритмов вычислительной математики для подсистемы схемотехнического проектирования РЭА» (код проекта 2.1.2/9625);

- аналитической ведомственной целевой программе «Развитие научного потенциала высшей школы» (2009-2011 годы)» по теме «Разработка и исследование реконфигурируемых гибридных эволюционных аппаратных средств» (код проекта 2.1.2/9981);

- в рамках госзадания Минобрнауки РФ по проекту 8.3383.2011 «Теоретические основы проектирования нового поколения СФ блоков систем связи, телекоммуникаций и технической диагностики на основе радиационно-стойких технологий (БЮе, АБМК13/4 и др.)» (ЮРГУЭС-02.12.ГЗ) (2012-2013 гг.).

Материалы диссертации также использованы в учебном процессе:

- на кафедре «Информационные системы и радиотехника» в ЮжноРоссийском государственном университете экономики и сервиса;

- на кафедре «Информационные технологии» в Волгодонском институте сервиса Южно-Российского государственного университета экономики и сервиса.

5

Результаты диссертационной работы были использованы:

- в проектно-конструкторской и производственной деятельности ООО «Лайт-09» (р.п. Каменоломни, Октябрьский р-н, Ростовская обл.) при изготовлении, пуско-наладке и эксплуатации элементов системы управления наружным освещением;

- в деятельности Научно-исследовательской лаборатории автоматизации проектирования (НИЛ АП, ООО) при разработке алгоритмов автоматической настройки ПИД-регуляторов для автоматизированных систем управления технологическим процессом.

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

- международные конгрессы по интеллектуальным системам и информационным технологиям «IS&IT'09», «IS&IT'IO», «IS&IT'l 1», «IS&IT12».

- международные научно-практические конференции «CAD-2009», «CAD-2010», «CAD-2011», «CAD-2012;

- международная научная конференция «Теория операторов. Комплексный анализ и математическое моделирование» (г. Волгодонск, 24-29 августа 2009г.);

- международная научно-практическая интернет-конференция «Информационные технологии в науке и образовании» (декабрь-2009 - март 2010);

- межрегиональные научно-практические конференции молодых ученых и студентов «Научный потенциал молодежи - будущему России» (г.Волгодонск, 23 апреля 2010г., 29 апреля 2011 года, 20 апреля 2012 года, 19 апреля 2012 года,);

- всероссийские научно-практические конференции «Актуальные проблемы техники и технологии» (г. Шахты, 16.05.2008г. и 19.05.2011г.).

Публикации. По материалам диссертационной работы опубликовано 11 печатных работ, в том числе 4 статьи в изданиях, входящих в «Перечень ведущих научных журналов и изданий, выпускаемых в Российской Федерации», утверждённых ВАК. Получено 8 свидетельств о государственной регистрации программ для ЭВМ. Материалы вошли в 6 отчетов по НИР.

Структура и объем диссертационной работы. Диссертационное исследование состоит из введения, четырех разделов, заключения, списка литературы из 126 источников, содержит 3 приложения. Работа изложена на 188 страницах, содержит 50 рисунков и 17 таблиц.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первом разделе рассмотрены основные проблемы, задачи схемотехнического проектирования, проанализированы математические модели

6

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

Согласно матрично-топологическому представлению законов теории электрических цепей математическая модель схемы приводится к двум типам:

х' = f{x, О = 0, х(0) = х0, (1)

Р(х',х,0 = 0, х(0) =х0, (2)

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

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

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

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

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

Рисунок 1 - Типовая структура матрицы с окаймлением

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

Система линейных алгебраических уравнений (СЛАУ) выглядит следующим образом:

Ах = Ь, (3)

где х и Ъ - векторы, х = (_х1, х2,... хп) е ß"; b = (blt b2,... bn) S Rn.

Псевдорешением системы (3) называют вектор х, минимизирующий невязку ||Ах — Ь|| на всем пространстве Rn. Система может иметь не одно псевдорешение. Нормальным решением называется псевдорешение z с минимальной евклидовой нормой ||z||. Для любой системы вида (3) нормальное решение существует и единственно. Это говорит о неустойчивости задачи нахождения нормального решения системы.

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

||Ах — Ь|| + 0.1||д:|| -» min. (4)

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

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

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

СЛАУ и ростом погрешности при увеличении размерности системы для плохо обусловленных СЛАУ.

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

Модифицированный метод решения систем нелинейных уравнений тогда будет выглядеть следующим образом: стандартный метод Ньютона для решения систем нелинейных уравнений, в котором для решения СЛАУ будет использоваться разработанный модифицированный метод.

Ниже приведем описание предложенного модифицированного метода решения систем нелинейных уравнений. Система нелинейных уравнений имеет следующий вид:

= О,

где х = {*;} - вектор искомых переменных (токов и/или напряжений) х^еЯ,

Введем следующие обозначения:

£ - допустимая погрешность,

А = {аг;-} - матрица с элементами а^еЯ, матрица Якоби, (,) = 1,2 ...,п; п — количество уравнений.

Ь = {Ь;} - известный вектор с координатами Ь(е/?.

Лх - вектор решений системы линейных уравнений Ах^еИ, Ах = {Дх^}.

Шаг 1. Начало цикла.

Шаг 2. Определение А и Ь.

Шаг 3. Решение Акх = Ь разработанным модифицированным методом решения СЛАУ.

Шаг 4. Определение нового вектора * = :*: +Длги5 = £™=1|Д:!С{| < е.

Шаг 5. Если 5 < е, то переходим к шагу 6, иначе переходим к шагу 2.

Шаг 6. Вывод х.

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

На рисунке 2 представлена схема методики решения уравнений математических моделей подсхем СБИС. Косой штриховкой показаны этапы модифицированного метода решения систем нелинейных уравнений, вертикальной — этапы модифицированного метода решения СЛАУ.

Методика решения уравнений математической модели СБИС выглядит следующим образом:

Этап 1. Анализ системы уравнений, описывающей математическую модель электрической схемы. Определение типа системы уравнений математической

модели: системы дифференциальных уравнений, системы нелинейных уравнений, СЛАУ.

Этап 2. Решение системы уравнений математической модели:

— если уравнения математической модели представляют собой систему дифференциальных уравнений, то на каждом шаге интегрирования неявного метода Рунге-Кутты решается система уравнений разработанным модифицированным методом, представляющим собой метод Ньютона, на каждой итерации которого решается СЛАУ предложенным модифицированным методом. В случае линейных дифференциальных уравнений модифицированный метод решения систем нелинейных уравнений будет сходиться за одну итерацию;

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

— если уравнения математической модели представляют собой СЛАУ, то данная система решается разработанным модифицированным методом.

Этап 3. Вывод результата.

ю

(продолжение)

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

Для предложенного эволюционного алгоритма была разработана структура хромосомы, включающая в себя гены, содержащие вектор неизвестных х = (х1,х2, ...xn) Е Rn, и служебные гены Sk = (Sk1,Sk2, ...Skm) £ N, Sm = (Sm1,Sm2, ...Srtii) E N, необходимые для сбора статистической информации об эффективности операторов кроссинговера и мутации соответственно, где т и / -количество операторов кроссинговера и мутации соответственно. Для обеспечения малой погрешности вычисления было выбрано вещественное кодирование хромосомы.

Для разработанного алгоритма была построена следующая целевая функция:

F = \\Ах - Ь\\ + 0Д||х|| + Fp -> min, (4)

где Fp - значение эффективности, полученное по принципу Парето.

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

Целевая функция состоит из трех слагаемых:

- \\Ах — Ь || - евклидова норма невязки,

- Цх|| -евклидова норма векторах,

-Ир— значение эффективности, полученное по принципу Парето.

Суммарная погрешность /-ого блока определяется по формуле:

^ = И^х-^Н л = 1..ш, (5)

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

Для увеличения скорости расчета эффективности по принципу Парето (Рр) исходная система разбивается на блоки. Значения невязок полученных блоков используется для вычисления значения Рр. Увеличение скорости расчета достигается за счет уменьшения числа сравнений.

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

Разработанный алгоритм работает с набором решений, полученных на этапе инициализации популяции.

Для пояснения определения эффективности возможного решения по принципу Парето рассмотрим следующее неравенство, связывающее два вектора х' и х2\

/¡(х1) </г(х2),1 = 1..П,

где у; — значение евклидовой нормы невязки /'-ого блока уравнений.

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

Для определения значения эффективности Рр для текущего вектора х воспользуемся следующей формулой:

^Р = £ аес-^,

где О-множество более эффективных векторов х; g - вектор, являющийся членом множества (7, ^-количество менее эффективных векторов g.

Способ определения значения эффективности по принципу Парето можно пояснить на следующем примере. Определим СЛАУ:

2 1 0 1 "4"

3 2 4 1 10

*Х =

1 1 1 2 5

_2 5 1 1 9

Разобьем для примера данную систему уравнений на два блока:

2 1 0 1 "4"

, v, =

3 2 4 1 10_

Р,=

1112 2 5 11

Выбираем случайным образом три вектора X. Считаем невязки блоков по формуле (5).

Г = о, ^ = О; х, =

= 10, 2 =8.94; х3 =

Д, = 3.16,Г2 =2.23

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

X Более эффективные X Количество более эффективных X Менее эффективные X Количество менее эффективных X Значение эффективности

X 1 - 0 2,3 2 0

X 2 X , X 1' 3 2 - 0 3

хз X 1 1 1 1 2

Разработанный алгоритм решения СЛАУ может быть описан следующей последовательностью действий:

Шаг 1. Ввод параметров работы алгоритма

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

Шаг 3. Инициализация начальной популяции, кодирование и внесение в популяцию решения, полученного на шаге 2. Оптимальный размер популяции, полученный экспериментальным путем в процессе исследования гибридного эволюционного алгоритма, равен 100. Определение начальной приспособленности хромосом популяции и их сортировка.

Шаг 4. Определение счетчика поколений к-0, используемого для определения момента применения редукции популяции и критерия выбора генетических операторов. Определение общего счетчика поколений /=0.

Шаг 5. Если к меньше параметра случайной вероятности определения генетических операторов, то переход к шагу 6, иначе к шагу 8.

Шаг 6. Определение кандидатов для применения генетических операторов с помощью турнирной селекции.

Шаг 7. Случайный выбор генетических операторов и их применение. Переход к шагу 10.

Шаг 8. Определение кандидатов для применения генетических операторов с помощью турнирной селекции.

Шаг 9. Выбор генетических операторов на основе анализа эффективности и их выполнение.

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

Шаг 11. Если потомки были добавлены в популяцию, то переход к шагу 12, иначе к шагу 13.

Шаг 12. Определение приспособленности популяции, расстояний между хромосомами и упорядочение.

Шаг 13. Если к равно параметру редукции, то переход к шагу 14, иначе к шагу

17.

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

Шаг 15. Обнуление счетчика к~0.

Шаг 16. Определение приспособленности популяции, расстояний между хромосомами и упорядочение.

Шаг 17. Формирование новой популяции с помощью элитной селекции. Определение лучшей, средней и худшей хромосомы.

Шаг 18. Если улучшение лучшей хромосомы произошло, то переход к шагу 19, иначе к шагу 21.

Шаг 19. Если значения параметров мутации обобщенных минимальных невязок и бисопряженных градиентов равны установленным перед началом работы алгоритма, то переход к шагу 23, иначе к шагу 20.

Шаг 20. Уменьшение на 1 значений параметров мутации обобщенных минимальных невязок и бисопряженных градиентов (данные параметры отражают количество итераций и размер внешнего цикла для метода бисопряженных градиентов и метода обобщенных минимальных невязок соответственно). Переход к шагу 23.

Шаг 21. Если предел застоя достигнут, т.е. в течение определенного количества поколений не происходило улучшение лучшей хромосомы, то переход к шагу 22, иначе к шагу 23.

Шаг 22. Увеличение значений параметров для мутации обобщенных минимальных невязок и бисопряженных градиентов на 1.

Шаг 23. Если размерность популяции меньше 1/3 от исходной, то приведение популяции к исходному размеру.

Шаг 24. Если приспособленность лучшей хромосомы меньше установленной, т.е. найдено решение с заданной погрешностью, то переход к шагу 26, иначе к шагу 25.

Шаг 25. Если / меньше количества поколений, то 1=1+1 и к=к+1 переход к шагу 5, иначе к шагу 26.

Шаг 26. Вывод результата.

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

Определена сложность разработанного алгоритма. Теоретическая оценка временной сложности данного алгоритма составляет 0(№).

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

100 150 200 250 | 300 | 350 400 ! •150 ] 500 600 700 | 800 ] 900

всс 8 45 200 1468 '- - — ; — 1 — ! - — -: |

- с.мк1 ь 214 217 ! 265 989 | 1070 1376 1478 | 1258 1789 3403 3528 4932 | 108831

;* рел 500 597 620 1357 1251 1433 1255 | 1576 2201 4062 4703 1 8343 | 1466;:

Рисунок 3 - Сводная диаграмма зависимости времени выполнения от размерности

системы

3 а 00Е-С4 ! '

100 150 ' 200 Г 250 ] 300 '' 350 400 450 500 600 700 800 ! 900

(«¡'век" ! л.79е-10 9.46е-10 8.46е-09 1 7.77е-07

реа 0.000101 1д7е-0б ; 1.77е-06 2.72е-05 8.84е-05 6.02е-04 9.40е-05 7.25е-05 ] 2.28е-05 1.66е04 1,63е^34 1.94е-04 1.09е-04 :

'»гмйй 0.00533 3.97е-03 8д9е-03 3.05е-01 2.6ле-01 7.63е 01 | 8.55е-с1 ! 7.21е-01 1д8е»00 5.44е-01 ! 7.58е-01 : 5.23е-01 6.52е-с1

Рисунок 4 - Сводная диаграмма зависимости погрешности вычислений от

размерности системы

На рисунках 3 и 4 представлены сводные диаграммы зависимости времени выполнения и погрешности вычислений от размерности системы соответственно. На диаграммах представлены результаты сравнения наиболее эффективных алгоритмов решения СЛАУ большой размерности (алгоритма бисопряженных градиентов (ВСО) и обобщенных минимальных невязок (GMR.ES)) и предлагаемого гибридного эволюционного алгоритма.

В заключении изложены основные выводы и результаты диссертационной работы.

В приложениях представлены копии актов внедрения, свидетельства о государственной регистрации программ для ЭВМ и схемы алгоритмов методов решения СЛАУ крыловского типа ОМЯЕЗ и ВСО.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

выполнения диссертационной работы получены

следующие

В ходе результаты:

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

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

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

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

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

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

6. Анализ экспериментальных исследований показал эффективность гибридного эволюционного алгоритма решения СЛАУ и подтвердил теоретическую оценку временной сложности. По сравнению с традиционными алгоритмами, разработанный алгоритм не испытывает проблем с ростом погрешности при увеличении размерности системы. При этом он обладает квадратичной временной сложностью, что также является достоинством алгоритма. Данный алгоритм увеличивает эффективность решения СЛАУ, полученных на этапе схемотехнического проектирования, за счет уменьшении погрешности более чем в 10000 раз при незначительном увеличении времени выполнения (менее 1.5 раз для СЛАУ размером 900x900). Гибридизация позволила расширить область применения мощных проекционных методов и увеличить их эффективность при решении плохо обусловленных систем уравнений большой размерности. Проведенные экспериментальные исследования также доказывают эффективность модифицированного метода решения систем нелинейных уравнений, в котором СЛАУ решается разработанным модифицированным методом на каждой итерации метода Ньютона. Так как задача моделирования является самой трудоемкой на схемотехническом этапе проектирования СБИС, то можно говорить, что

17

увеличение эффективности решения уравнений математических моделей электрических цепей приведет к росту эффективности всего процесса схемотехнического проектирования.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

Публикации в ведущих рецензируемых изданиях, рекомендованных ВАК РФ

1. Бегляров, В.В. Берёза, А.Н. Бионический алгоритм решения систем линейных алгебраических уравнений [Текст] /В.В.Бегляров, А.Н.Берёза // Известия ЮФУ. Технические науки - Таганрог: Технологический институт Федерального государственного образовательного учреждения высшего профессионального образования "Южный федеральный университет" в г.Таганроге, 2009. - №12-46-53 стр.

2. Бегляров, В.В., Берёза, А.Н., Стороженко, A.C. Гибридный многопопуляционный муравьиный генетический алгоритм [Текст] / В.В.Бегляров,

A.Н.Берёза, А.С.Стороженко // Известия ЮФУ. Технические науки - Таганрог: Технологический институт Федерального государственного образовательного учреждения высшего профессионального образования "Южный федеральный университет" в г.Таганроге. - 2010. - №7. - 39-45 стр.

3. Бегляров, В.В., Берёза, А.Н. Эволюционный многопопуляционный алгоритм решения СЛАУ (PEREKRESTOK) [Текст] / В.В.Бегляров, А.Н.Берёза // Известия ЮФУ. Технические науки - Таганрог: Технологический институт Федерального государственного образовательного учреждения высшего профессионального образования "Южный федеральный университет" в г.Таганроге. — 2012, - №11, 193-198 стр.

4. Бегляров, В.В., Берёза, А.Н. Гибридный эволюционный алгоритм решения систем линейных алгебраических уравнений, описывающих электрические цепи /

B.В. Бегляров, А.Н. Берёза, A.C. Электронный научный журнал. Инженерный вестник Дона. URL: http://ivdon.ru/magazine/archive/nly2013/1540, 2013, - №1.

Публикации в других изданиях

5. Применение бионических методов при разработке бионических процедур параметрической оптимизации в САПР [Текст] / В.В.Бегляров, А.Н.Береза, А.С.Стороженко // Информационные технологии в науке и образовании. Международная научно-практическая интернет-конференция (октябрь 2007г. -март 2008г.) II Всероссийский семинар «Применение MOODLE в сетевом обучении» (Железноводск, 26-28 марта 2008г). VI Всероссийский научно-практический семинар «Автоматизированные системы управления учебным процессом в вузе: опыт, решения, возможности». Шахты, октябрь 2007г. - 238 с. -227 - 230 стр.

6. Применение муравьиных алгоритмов для анализа развития популяций в многопопуляционных алгоритмах [Текст] / В.В.Бегляров, А.Н.Берёза, А.С.Стороженко // Информационные системы и технологии. Теория и практика: сб. науч. тр. / под. ред. А.Н.Берёза. - Шахты: Изд-во ЮРГУЭС, 2008. - 188 с. - 33-39 стр.

7. Бегляров, В.В., Берёза, А.Н. Эволюционный алгоритм решения систем линейных уравнений (тезисы) [Текст] / В.В.Бегляров, А.Н.Берёза //

18

Информационные технологии, системный анализ и управление: VI всероссийская научная конференция молодых ученых, аспирантов и студентов, сб. тр. - Таганрог: Изд-во ТТИ ЮФУ, 2008 - 149-151 стр.

8. Бегляров, В.В. Бионические методы разработки интеллектуальных систем [Текст] / В.В. Бегляров // Информационные системы и технологии. Теория и практика: сб. науч. тр. / редкол.: А.Н.Береза [и др.]. - Шахты: ГОУ ВПО «ЮРГУЭС», 2009. - 209 е., 33-44 стр.

9. Бегляров, В.В., Берёза, А.Н. Программная система конструирования генетических алгоритмов GA Builder [Текст] / В.В.Бегляров, А.Н.Береза // Информационные технологии в науке и образовании. Международная научно-практическая интернет-конференция (декабрь-2009 - март 2010.). IV Всероссийский семинар «Применение MOODLE в сетевом обучении» (Железноводск, 6-9 апреля 2010г). - Шахты: ГОУ ВПО «ЮРГУЭС», 2010. - 221с., 153-159 стр.

10. Бегляров В.В. Систематический анализ принципов эволюционного моделирования [Текст] / В.В.Бегляров // Информационные системы и технологии. Теория и практика: сб. науч. тр. / редкол.: А.Н. Береза [и др.]. - Шахты: ФГБОУ «ЮРГУЭС», 2011. - 283с., стр. 49-68.

11. Бегляров, В.В. Гибридный многопопуляционный алгоритм решения СЛАУ (PEREKRESTOK) [Текст] / В.В.Бегляров // «Научный потенциал молодёжи - будущему России»: межрегион, науч.-практ. конф. (2012; Волгодонск). Межрегиональная научно-практическая конференция «Научный потенциал молодёжи - будущему России», 20 апр. 2012 г.: материалы и доклады / редкол.: П.Д. Кравченко [и др.]; Волгодонский ин-т сервиса (филиал) Федер. гос. бюдж. образоват. учреждения высш. проф. образования «Южно-Рос. гос. ун-т экономики и сервиса» (ВИС ФГБОУ ВПО «ЮРГУЭС»), - Шахты: ФГБОУ ВПО «ЮРГУЭС», 2012.- 199 е., 10-13стр.

Свидетельства о регистрации программ па ЭВМ

12. Свидетельство о государственной регистрации программ для ЭВМ «Библиотека функций линейной алгебры (LAB)». В.В. Бегляров, А.Н.Береза, № 2008614246. Зарегистрирована 5.09.2008.

13. Свидетельство о государственной регистрации программ для ЭВМ «Библиотека функций нелинейной алгебры (NLAB)». В.В. Бегляров, А.Н.Береза, № 2008614245. Зарегистрирована 5.09.2008.

14. Свидетельство о государственной регистрации программ для ЭВМ «Бионический алгоритм решения систем линейных алгебраических уравнений». В.В. Бегляров, А.Н.Береза, М.В.Ляшов. № 2010612753. Зарегистрирована 22.04.2010.

15. Свидетельство о государственной регистрации программ для ЭВМ «Библиотека оптимизационных алгоритмов для подсистемы схемотехнического проектирования ЭВТ». В.В.Бегляров, А.Н.Береза, М.В.Ляшов, А.С.Стороженко. №20110612081. Зарегистрирована 17.05.2011.

16. Свидетельство о государственной регистрации программ для ЭВМ «Инструментальная среда проектирования и исследования генетических

\:>

алгоритмов ОАВшЫег». В.В. Бегляров, А.Н. Береза, М.В. Ляшов. № 2011611810. Зарегистрирована 18.03.2011.

17. Свидетельство о государственной регистрации программ для ЭВМ «Библиотека алгоритмов вычислительной математики для подсистемы схемотехнического моделирования ЭВТ». В.В. Бегляров, А.Н. Береза, М.В. Ляшов. № 20116112082. Зарегистрирована 26.05.2011.

18. Свидетельство о государственной регистрации программ для ЭВМ «Библиотека эволюционных алгоритмов решения СЛАУ для подсистемы схемотехнического моделирования РЭА». В.В. Бегляров, А.Н. Береза, № 2012617815. Зарегистрирована 29.08.2012.

19. Свидетельство о государственной регистрации программ для ЭВМ «Программа решения уравнений математических моделей, полученных на этапе схемотехнического проектирования СБИС, на основе гибридного парето-эволюционного алгоритма». В.В. Бегляров, А.Н. Берёза, № 2013610324. Зарегистрирована 9.01.2013.

Личный вклад автора. Все результаты, изложенные в диссертации, получены лично автором. Автору также принадлежит ведущая роль в проектировании и создании подключаемого модуля и инструментальной среды разработки и исследования эволюционных алгоритмов. Автором были разработаны эволюционные алгоритмы и модифицированные генетические операторы [1,2,3,4,5,7]; исследование критериев, по которым проводится анализ развития популяций в многопопуляционных алгоритмах [6]; разработка состава и структуры системы конструирования генетических алгоритмов [9]; проведение реализации и разработка структуры классов [12-19].

Научному руководителю к.т.н., доценту Берёзе А.Н. принадлежит постановка задачи диссертационной работы, участие в обсуждении и интерпретации результатов экспериментальных исследований.

Соискатель г В.В. Бегляров

Подписано в печать 26.04.2013г. Формат 60x84/16. Бумага офсетная. Ризография. Усл.п.л.1,0. Тираж 100 экз. 3ак.83.

Отпечатано в типографии: ИП Бурыхин Б.М., Ростовская область, г.Шахты, ул.Шевченко, 143.

МИНОБРНАУКИ РОССИИ Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования Южно-Российский государственный университет экономики и сервиса

(ФГБОУ ВПО «ЮРГУЭС»)

На правах рукописи

04201'356 618

Бегляров Вадим Валерьевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ ДЛЯ МОДЕЛИРОВАНИЯ СХЕМОТЕХНИЧЕСКИХ РЕШЕНИЙ

Специальность: 05.13.12 -Системы автоматизации проектирования (вычислительная техника и информатика)

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель: к.т.н., доцент Берёза А.Н.

Таганрог - 2013 г.

СОДЕРЖАНИЕ

Введение..........................................................................................................4

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

1.1 Анализ особенностей проектирования СБИС...............................14

1.2 Анализ математических моделей электронных схем...................22

1.3 Задачи и проблемы схемотехнического проектирования............28

1.4 Исследование особенностей процедур экстракции паразитных параметров, используемых в современных САПР ЭВТ...........................38

1.5 Постановка задачи решения уравнений математических моделей схемотехнических решений.........................................................................47

2 Исследование и разработка элементов математического аппарата для подсистемы схемотехнического проектирования САПР ЭВТ.....................51

2.1 Исследование численных методов решения уравнений математических моделей схемотехнических решений.............................51

2.2 Исследование оценки погрешности решения СЛАУ....................63

2.3 Разработка методики решения уравнений математических моделей схемотехнических решений.........................................................66

3 Разработка гибридного эволюционного алгоритма решения уравнений математических моделей СБИС.......................................................................73

3.1 Разработка процедуры кодирования решения...............................73

3.2 Разработка целевой функции...........................................................76

3.3 Разработка модифицированных генетических операторов.........83

3.4 Разработка гибридного эволюционного алгоритма решения СЛАУ большой размерности (РЕА)...........................................................99

3.5 Теоретическая оценка сложности гибридного эволюционного алгоритма.....................................................................................................106

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

4.1 Описание структуры подключаемого модуля.............................109

4.2 Описание инструментальной среды конструирования и исследования эволюционных алгоритмов...............................................110

4.3 Цели и методы проводимых исследований.................................123

4.4 Экспериментальные исследования разработанного гибридного

эволюционного алгоритма.........................................................................124

ЗАКЛЮЧЕНИЕ...........................................................................................150

Список литературы.....................................................................................153

Приложение А.............................................................................................168

Приложение Б..............................................................................................174

Приложение В.............................................................................................183

Введение

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

Современные САПР являются:

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

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

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

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

Согласно принципам блочно-иерархического проектирования объектов выделяются следующие уровни декомпозиции [4]:

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

- структурный уровень - описывается структура объекта;

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

- схемотехнический уровень;

- конструкторский уровень;

- компонентный уровень - содержит подробный выбор и описание элементов системы (объекта) [5].

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

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

произошло увеличении роли схемотехнического проектирования в общем маршруте проектирования СБИС [1-3].

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

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

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

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

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

Разработке новых методов решения уравнений математических моделей и увеличению эффективности схемотехнического проектирования в настоящее время посвящено множество как зарубежных, так и отечественных публикаций. Среди отечественных и зарубежных публикаций можно выделить труды Русакова, С.Г., Норенкова, И.П., Анисимова, В.И., Дмитриевича, Г.Д., Петренко, А.И., Сигорского, В.П., Перминова, В.Н., Денисенко, В.В., Kuh, E.S., Sangiovanni-Vincentelli, A.L., Kuehlmann, А., Nelson, V.P., Kundert, K.S. и т.д. Следовательно, задача разработки модифицированных методов решения уравнений математических моделей схемотехнических решений, способных увеличить общую производительность САПР ЭВТ, является АКТУАЛЬНОЙ.

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

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

1. Провести анализ эффективности существующих методов решения уравнений математических моделей, применяющихся в САПР ЭВТ.

2. Разработать модифицированные методы решения систем линейных алгебраических уравнений (СЛАУ) и систем нелинейных уравнений большой размерности, полученных на схемотехническом этапе моделирования СБИС.

3. Разработать методику решения уравнений математических моделей СБИС.

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

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

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

Положения, выносимые на защиту:

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

2. Методика решения уравнений математических моделей подсхем СБИС.

3. Гибридный эволюционный алгоритм, ориентированный на решение уравнений математических моделей схемотехнических решений.

4. Инструментальная среда разработки и исследования эволюционных алгоритмов для подсистемы схемотехнического проектирования ЭВТ.

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

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

Научная новизна работы состоит в:

- разработке модифицированного метода, способного повысить эффективность решения систем линейных алгебраических уравнений (СЛАУ) большой размерности, полученных на этапе моделирования схемотехнических решений, за счет улучшения соотношения времени выполнения и погрешности решения (стр. 67);

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

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

- разработке гибридного эволюционного алгоритма, ориентированного на решение уравнений математических моделей подсхем СБИС, полученных на этапе моделирования схемотехнических решений (стр. 73-106).

Практическую ценность работы представляют:

- кроссплатформенный подключаемый модуль, основанный на модифицированных методах решения уравнений математических моделей схемотехнических решений. Данный модуль может быть использован в индустриальных САПР ЭВТ (стр. 109-110);

- инструментальная среда разработки и исследования эволюционных алгоритмов (стр. 110-124).

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

- аналитической ведомственной целевой программе «Развитие научного потенциала высшей школы» (2009-2011 годы)» по теме «Разработка и исследование бионических алгоритмов вычислительной математики для подсистемы схемотехнического проектирования РЭА» (код проекта 2.1.2/9625);

- аналитической ведомственной целевой программе «Развитие научного потенциала высшей школы» (2009-2011 годы)» по теме «Разработка и

исследование реконфигурируемых гибридных эволюционных аппаратных средств» (код проекта 2.1.2/9981);

- в рамках госзадания Минобрнауки РФ по проекту 8.3383.2011 «Теоретические основы проектирования нового поколения СФ блоков систем связи, телекоммуникаций и технической диагностики на основе радиационно-стойких технологий (8Юе, АБМК13/4 и др.)» (ЮРГУЭС-02.12.ГЗ) (2012-2013 гг.).

Материалы диссертации также использованы в учебном процессе:

- на кафедре «Информационные системы и радиотехника» в ЮжноРоссийском государственном университете экономики и сервиса;

- на кафедре «Информационные технологии» в Волгодонском институте сервиса Южно-Российского государственного университета экономики и сервиса.

Результаты диссертационной работы были использованы:

- в проектно-конструкторской и производственной деятельности ООО «Лайт-09» (р.п. Каменоломни, Октябрьский р-н, Ростовская обл.) при изготовлении, пуско-наладке и эксплуатации элементов системы управления наружным освещением;

- в деятельности Научно-исследовательской лаборатории автоматизации проектирования (НИЛ АП, ООО) при разработке алгоритмов автоматической настройки ПИД-регуляторов для автоматизированных систем управления технологическим процессом.

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

- международные конгрессы по интеллектуальным системам и информационным технологиям «18&ГГ09», «18&1Т'10», «18&1Т'11», «18&ГГ12».

- международные научно-практические конференции «САЕ)-2009», «СА1)-2010», «САО-2011», «САБ-2012;

- международная научная конференция «Теория операторов. Комплексный анализ и математическое моделирование» (г. Волгодонск, 2429 августа 2009г.);

- международная научно-практическая интернет-конференция «Информационные технологии в науке и образовании» (декабрь-2009 - март 2010);

- межрегиональные научно-практические конференции молодых ученых и студентов «Научный потенциал молодежи - будущему России» (г.Волгодонск, 23 апреля 2010г., 29 апреля 2011 года, 20 апреля 2012 года, 19 апреля 2012 года,);

- всероссийские научно-практические конференции «Актуальные проблемы техники и технологии» (г. Шахты, 16.05.2008г. и 19.05.2011г.).

Публикации. По материалам диссертационной работы опубликовано 11 печатных работ, в том числе 4 статьи в изданиях, входящих в «Перечень ведущих научных журналов и изданий, выпускаемых в Российской Федерации», утверждённых ВАК. Получено 8 свидетельств о государственной регистрации программ для ЭВМ. Материалы вошли в 6 отчетов по НИР.

Структура и объем диссертационной работы. Диссертационное исследование состоит из введения, четырех разделов, заключения, списка литературы из 126 источников, содержит 3 приложения. Работа изложена на 188 страницах, содержит 50 рисунков и 17 таблиц.

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

В первом разделе рассмотрены основные проблемы, задачи схемотехнического проектировани�