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

• Кулиев, Эльмар Валерьевич
• кандидат технических наук
• 2013

Оглавление диссертации кандидат технических наук Кулиев, Эльмар Валерьевич

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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

1.1 Анализ проблемы размещения компонентов СБИС

1.1.1 Развитие полузаказных матричных СБИС

1.1.2 Иерархический подход к проектированию ЭВА

1.2 Построение математической модели задачи размещения

1.3 Постановка задачи размещения компонентов СБИС

1.4 Классификация и анализ методов размещения

1.4.1 Классификация традиционных методов размещения

1.4.2 Анализ методов эволюционного моделирования

1.4.3 Анализ модели муравьиной колонии

1.4.4 Анализ модели пчелиного роя

1.5 Выводы

2 РАЗРАБОТКА МОДЕЛИ АДАПТИВНОГО ПОВЕДЕНИЯ БИОЛОГИЧЕСКИХ СИСТЕМ

2.1 Архитектура модифицированного гибридного алгоритма размещения

2.2 Построение схемы гибридного поиска

2.3 Построение модифицированной структуры гибридного поиска

2.4 Метод биоинспирированного поиска

2.5 Разработка гибридного двухуровневого подхода размещения компонентов СБИС

2.6 Модели адаптивного поведения биологических систем

2.6.1 Метод пчелиной колонии

2.6.2. Алгоритм работы колонии пчел

2.6.3 Метод генетического алгоритма

2.7 Разработка модифицированного генетического оператора

2.8 Многоагентный подход к описанию разработанных моделей

2.9 Выводы

3 РАЗРАБОТКА МОДИФИЦИРОВАННОГО ГИБРИДНОГО АЛГОРИТМА РАЗМЕЩЕНИЯ КОМПОНЕНТОВ СБИС

3.1 Модифицированный гибридный алгоритм размещения компонентов СБИС

3.2 Гибридный алгоритм размещения компонентов СБИС

3.3 Модель модифицированного гибридного алгоритма размещения компонентов СБИС

3.4 Разработка генетического алгоритма размещения компонентов СБИС

3.5 Применение гибридного механизма для решения задач размещения компонентов СБИС

3.6 Разработка роевого алгоритма размещения

3.6.1 Формирование окрестности поиска методом колонии пчел

3.7 Процедура кодирования - декодирования

3.8 Выводы

4 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ МОДИФИЦИРОВАННОГО ГИБРИДНОГО АЛГОРИТМА В ЗАДАЧЕ РАЗМЕЩЕНИЯ

4.1 Цели экспериментальных исследований

4.2 Описание программного комплекса

4.3 Результаты экспериментальных исследований

4.3.1 Определение временной сложности разработанного гибридного алгоритма

4.4 Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ

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

ВВЕДЕНИЕ

Одной из сложнейших и наиболее важных задач при создании средств микроэлектронной техники является синтез юпологий СБИС. Синтез - создание проектного решения в виде его конструктивных особенностей, функциональной или структурной. О тличи тельной особенностью современного этапа является высокая сложное ib и размерность проектирования устройств. Методы автоматизированного проектирования, технологической подготовки проектирования и консфуировапия позволяют создавав высоконадежные сверхбольшие ишегральные схемы (СБИС) в короткие сроки и при сравни!ельно низких затратах [1].

Проектирование СБИС производится на паномегровом диапазоне, чю ipe6yci новых методов и подходов.

В настоящее время вопросы развития методов, моделей, а также стратегий и алгоритмов автоматизированного проектирования сверхбольших интегральных схем нашло отображены в работах Норепкова И.П., Бершадского A.M., Курейчика В.М., Морозова К.К., Казепнова Г.Г., Селютипа В.А., Шервани Н., и др. В большинстве случаев, алгоритмы, методы и модели разрабатываемые специалистами направлены па формирования базового плана кристалла, а также на оптимизацию этапа трассировки. А именно этапа трассировки соединений по критерию минимизации длины связей и занимаемой площади [1 - 7].

Большую роль в стратегию развития эволюционного поиска внесли такие учёные, как: Гольдберг Д.Е., Растригин JI.A., Холланд Д.Х., Курейчик В.М., Норенков И.П., Букатова И.Л., БатищевД.И., и др. Генетические алгоритмы, эволюционные алгоритмы, а также алгоритмы роевою ишсллекта являются фундаментальными направлениями научных исследований в области случайно-направленного поиска.

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

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

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

В последнее время активно развивается научное направление Natural Computing, основанное на принципах природных механизмов пришпия решений и включающее генетические алгоритмы, иейросехевые вычисления, муравьиные алгоритмы, метод роящихся часшц, табуироваппый поиск и др АСО-алгори1мы обладают способностью находи ib более высококачсс1 венные решения за приемлемое время.

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

Ввиду вышеизложенного, разработка алгоритмов, позволяющих пайш приемлемое по качеству и по трудоемкости решение задачи размещения, являе1ся важной и АКТУАЛЬНОЙ ПРОБЛЕМОЙ, стоящей перед разрабо1чиками САПР.

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

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

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

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

3.Разработка обобщенной архитектуры модифицированного 1ибридпою алгоритма размещения компонентов СБИС.

4 Разработка роевого алгоритма размещения компонешов СБИС па основе построенной модели адаптивного поведения.

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

6. Создание программного комплекса, реализующего разработанные алгоритмы решения задачи размещения.

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

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

Научная новизна диссертационной работы заключается в следующем

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

2. Посфоена модифицированная модель адаптивного поведения пчелиной колонии применительно к задачи размещения, отличающаяся принципами формирования окрестностей.

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

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

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

6. Разработана двухуровневая архитектура эволюционного алгоритма размещения шементов СБИС.

Решение поставленных задач позволяет автору защищать следующие новые научные результаты:

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

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

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

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

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

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

При носLроении программы использовались пакеты программ в среде Borland С++ Builder 6.0. Отладка и тестирование проводилось на ЭВМ шла IBM PC с процессором Intel Core 13. Экспериментальные данные разработанных алгоритмов превосходят данные извесшых ал гори imob, в качсове решения задачи размещения компонентов СБИС. Разрабо1анные алюришы размещения позволяют получать набор квазиогпимальных альтернативных решений за полиномиальное время.

Реализации результатов работы. Материалы диссер1 анионной рабопл использованы в НИР № 301.38-11/2013-14 «Разрабопса i сори и и принципов )волюциошюй оптимизации и принятия решений на основе меюдов и моделей адаптивного поведения биологических сис1ем», а также Граш РФФИ (№ 12 - 07 - 00058) «Разработка теоретических основ информационных технологий поддержки принятия решений при оптимизации и проектировании на основе методов, инспирированных природными системами», Грант РФФИ (№ 12 - 01 - 00100) «Разработка 1сории и принципов коллективного интеллекта па основе моделей адаптивного поведения муравьиной колонии для решения отними рационных «дач», Граш РФФИ № 12381 (№ 10 - 07 - 00055) «Разработка теории и принципов поиска решений в экспертных системах на основе меюдов и моделей адаптивного поведения биологических систем», Грант РФФИ № (№ 11 - 07 - 00064) «Разработка теории и принципов создания итерированных меюдов интеллектуального анализа данных для реализации па высокопроизводительных вычислительных системах», Грант РФФИ № 12388 (№ 11 - 01 - 00975) «Разработка теории и принципов управления iочное 1ыо решения комбинаторно-логических задач па основе методов искусственною интеллекта и принятия решений».

Материалы диссертации 1акже использованы в учебном процессе па кафедре САПР Южного федерального университета в цикле лекций и практических занятий по курсам «Автоматизация конегрукюрского и icxiiojioi ического проектирования», «Методы ошимизации» и «Эволюционное моделирование и генетические алгоритмы».

Апробация работы. Основные результаты диссер1ациошюй работы обсуждались и были одобрены на научных семинарах (с 2009 по 2012 ir., Т1И ЮФУ), Молодежной научно-технической конференции «Интеллектуальные системы - 2009» («ИС-2009») в рамках Кошресса по интеллектуальным системам и информационным технологиям «AIS-I Г09» (Дивпоморское, 2009 г.), Молодежной научно-технической конференции «Ишеллектуалытые системы - 2010» («ИС-2010») в рамках Кошресса по интеллектуальным системам и информационным технологиям «AIS-I Г'10» (Дивпоморское, 2010 г.), Молодежной научно-технической конференции «Интеллектуальные системы - 2011» («ИС-2011») в рамках Кошресса по интеллектуальным системам и информационным технолотиям «AIS-I Г11» (Дивпоморское, 2011 г.), Молодежной научно-технической конференции «Интеллектуальные системы - 2012» («ИС-2012») в рамках Кошресса по интеллектуальным системам и информационным технологиям «AIS-1P12» (Дивпоморское, 2012 г.).

Публикации. Результаты диссертации отражены в 13 печатных работах, в числе которых 2 - в изданиях, рекомендованных ВАК

Cipyiciypa и обьем диссертационной работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа содержит 147 страницы, а также 58 рисунков, 6 таблиц, список литературы из 107 наименований, 7 страницы приложений, в числе которых акты об использовании результатов диссертационной работы и листинг протраммпого комплекса.

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

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

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

сисi см.

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

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

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

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

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

В приложении даны копии актов об использовании рс?улыаюв рабои»!, а гакже копии свидетельств о регистрации протрамм для ЭВМ

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

1.1 Анализ проблемы размещения компонентов СБИС

1.1.1 Развитие полузаказных матричных СБИС

С рос ЮМ 3aipai на прост ирование интегральных схем и развижем полупроводниковой технологии, выгодным для использования с1ап0ви1ся полузаказпое проектирование. Основная идея полузаказного проектирования являс i с я предварительное изготовление реконфигурируемой архитектуры с дальнейшей конкретизацией её функционального назначения [1] Гакис фирмы, как Actel, Altera, AT&T, Xilinx являются мировыми лидерами в изготовлении схем [1-5].

Полузаказпые СБИС обладают разнообразием копструкжвно-icxHOJioi ичсских решений. Полузаказные СБИС делятся па три типа [2]

• программируемые логические матрицы (ПЛМ / PLD);

• íipoi раммируемая матричная логика (ПМЛ / PAL);

• npoi раммируемые вентильные массивы (FPGA).

1.1.2 Иерархический подход к проектированию ЭВА

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

• большое количество переменных не позволяет использовать ЭВМ с конечной памятыо;

• большое количество малоэффективных шагов поиска за счет неравноценною влияния на обобщений критерий качества переменных па разных уровнях [2-10].

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

\ \

В проектпо-конструкторских задачах применяют 2~ или 3~-уровпевос рассмотрение устройства Для двухуровневого представления элемент (Ы 1)-ю уровня рассматривают как некоторое устройство с соответствующим делением па компоненты к-го уровня. При трехуровневом представлении )лсмеп1 (к+2)-го уровня рассматривается как кристалл, состоящий из блоков (к+1)-ю уровня, который в свою очередь состоят из базовых злемептов к-ю уровня |7-13 ]

Формальная структурная модель представляется в виде совокупности блоков разного уровня В данной модели каждый блок содержит блоки нижних уровней [3]. Такая иерархическая структура позволяет снизить сложноеп> задач проектирования, за счет разбиения на несколько подзадач Каждая подзадача значительно проще и меньше размерностью Исходя из вышесказанною, отметим, чю иерархическое деление позволяс! ор1 апизова1 ь храпение данных, в результате которою не нарушаем ограничение па допустимый обьём оперативной памяти [4]

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

Технологический маршрут обязан обеспечить высокое качество проектирования в приемлемые сроки [2].

Процесс проектирования можно разделить па:

• физическое проектирование;

• электрическое проектирование.

Физическое проектирование решает проблемы проектирования тополо! ии, а именно:

• размещение полупроводниковых приборов;

• трассировки межсоединений.

Электрическое проектирование использует функциональное проектирование ЭВА, логическое проектирование, проектирование схем и частично полупроводниковых приборов.

В настоящее время проектирование СБИС включает следующие шаги |2-Ю]-

• сис1емная спецификация;

• функциональное проектирование;

• лот ичсское проектирование;

• схемное проектирование;

• конструкторское проектирование;

• технологическое проектирование;

• конструирование и тестирование.

При проектировании СБИС па этапе копсгрукгорско-техпологичсско1 о проек1 ировапия, важными этапами являются - разбиение, размещение и фассировка (рисунок 1).

'Трассировка

/»V

Технологическое проектирование

\

Конструирование и тестирование

Рисунок 1 - Обобщенный цикл проектирования СБИС

1.2 Пост роение математической модели задачи размещения

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

ючного решеиия затруднено, поэюму для ее решения использую I формальные математические модели и алгоритмы [2-10].

Сформулируем тривиальную задачу размещения. Дано-

• множество элементов (модулей) с расположенными па них выводами;

• коммутационное поле (КП), па котором должны размещайся элементы;

• электрическая принципиальная схема, связывающая выводы )лемеп юв

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

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

Математическая модель - это совокупность математических обьскюв (чисел, переменных, векторов, множеств и т.п.) и отношений между ними, коюрая адекватно отображает некоторые свойства проектируемою техническою обьекта [27]

К математическим моделям предъявляются следующие требования

• представление начального обьекта в простой форме,

• возможность перехода о г одной математической модели к друюй, 01 представления обьекга к математической модели и обратно;

• небольшой обьём занимаемой памяти для храпения информации о модели,

• анализ математического аппарата для использования различных магматических моделей;

• простота использования и дальнейшего функционирования

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

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

содержа!елыю описывает объекты и используется для создания алтршмов конструирования, легко обрабатываемых па ЭВМ Исходя из вышесказанною, рассмотрим задачу размещения компонентов СЪИС па основе 1 иперграфовой математической модели [15, 27, 28, 29]

Считают, что гиперграф 2 = задан, если задано множество

вершин /V = А/х и Д/2 и множество ребер М = [т1тг тк] , |Л/| = I, \М\ = к Для каждого гиперребра устанавливается подмножеспзо вершин, 1С, УУ Е {1,2, .,/<:} Ту Е Л/1<5 где ]\Г/ соответствует множеспзу блоков коммутационной схемы, а N2 - подмножссизу входов и выходов коммутационной схемы.

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

Гиперграф рассмотренный на рисунке 3 имеет следующий математический вид: е! = {х]? х2}, е2={ х2, х3}, е3= { хь х4, х5}, е,(= { хь х2, х,|}, е5~ { Хз, х4, х5}.

Рисунок 2 - Коммутационная схема блоков ЭВА

Рисунок 3 - Гиперграфовая модель схемы

Сложность алгоритмов решения задачи размещения гинертрафовои математической модели обьяснястся структурой гиперграфа («плавающими» ребрами). Одними из главных достоинств гиперграфовой модели являеюя Iочное определение главных конструктивных параметров усфойспы, а также переход от коммутационной схемы к математической модели не вьпывас! затруднений [15,27].

Учитывая тот факт, что в коммутационной схеме содержится большое число рашешлёпных цепей, то наиболее адекватной формой представления будет матрица цепей, которая обозначается С=\си\т/, где Г - наибольшее число контактов блоков, т - число элементов схемы |27] В лом случае, сфокам матрицы С соответствуют номера блоков, а столбцам номера кон ¡актов. Гогда, номер ребра гиперграфа (цепи) подхо/цпцего к /-му кош акту /-ю элемента ставится па пересечении 1-й строки и ]-\ о сюлбца Одним из недостатков матрица цепей является содержание избьпочпои информации Но, тем не менее, данная информация удобна для оперирования с помощью ЭВМ

Проанализировав приведенные рассуждения, вытекает вывод, о необходимоеIи применения гиперграфовой математической модели для решения задачи размещения схем при проектировании СБИС I аким образом, для решения задачи размещения схем при проектировании СБИС будем использовать гиперграфовую математическую мо/1ель [15|

1.3 Пос1ановка задачи размещени*! компоиснюв СБИС

Эффек1 ивность решения проблемы проектирования в целом зависж 01 выбора целевой функции - критерия качества. Подходов для определения кршерия качества в задачах САПР применяется много [16,28].

Выделим 1руппы критериев размещения учитывающих последующее размещение Выделим классификацию критериев размещения по харак 1сру онIимитируемых показателей

• мсфические показатели, такие как: юполо1 ическис, надежностью, плотост упаковки;

• по процессу оптимизации - последовательная оптимизация, оптимизация единого функционала и оптимизация ведущего пока за юля 116|

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

• Iсиловую совместимость;

• электромагнитную совместимость.

Автором, предлагается использовать метрический критерий суммарная длина соединений в качестве одного из критерия размещения

а = ЕпР$п|п = 1-к со

1де (2-критерий размещения,

У7^, —длина /7-й цепи, вычисляемая по теореме Пифаюра,

к - общее количество цепей схемы.

F - минимизироваться.

Выбранный критерий широко распространен в алюри[ма\ размещениях, так как:

• сокращение длины соединений улучшает электрические характеристики устройства,

• просюта трассировки;

• простая реализация критерия [16].

Несмотря на достоинства данного критерия, следус] учитывав, что применение суммарной длины соединений целесообразно до пекоюрою предела, ык как при необходимости уплотнения монтажа, что применимо для ироекIирования БИС и СБИС, необходимо применять дополниюльные критерии ¡7-15,16, 28,37]

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

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

• определить взаимное расположение блоков на кристалле,

• наметить предполагаемое расположение внешних выводов блоков

Данная с 1руктура позволяет приблизительно оцепить задержку в

передаче данных в начале разработки. Таким образом, решить вопрос сокращения числа итераций и соответственно времени проектирования [861

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

Следует учесть, что необходимо найти распределение злемептов на плоскоеIи, коюрос является наилучшим. Важно шать, что наилучшею решения найти не возможно. Применим модель цепи па основе дерева ППейпера для оценки временной задержки [86-87].

Произведем размещение элементов на рабочем поле в стандартные ячеики Применим Мапхэттепскую метрику для определения рассюяпии между элементами

Построение модели заключается в следующей работе алгоритма [86|

1 дано размещение трех элементов, соединенных цспыо 1? у;лы сетки рабочею поля (рисунок 4);

2 строим модель цепи на основе звездного графа,

3 задаем координаты нептра как среднее арифметическое коорципа! всех элементов цепи;

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

5. через эту ючку проводим «прямую», для построения дерева Штейнера;

6. каждый элемент цепи связывается с «прямой Штейнера»;

7. применяем модель цепи па основе дерева Штейнера в Мапхл 1 ейской метрике (рисунок 5);

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

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

10. Завершаем алгоритм.

Координаты центроида:

хс = avQÍsum(xl)) ус = ауд^ипЧу,))

сГ N X цент / ! юмд ЩХрУг)

у1 / С<хс Ус) ч ----- -О

у ч ч о Щ* тУч)

Рисунок 4 - Модель цепи «звездный граф»

и»р / и^х,- уе)

1с, 1 -- / О

С и,<х,Л1 с 3 тУп)

Рисунок 5 - Модель цепи в Манхэттенской метрике

23

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

Ввиду вышесказанного, применим аддитивный кршерии Целевая функция рассчитывается по формуле 2:

F(P) = а * пг * Д + ß * nz * /2 (2)

1де Ь(Р) —» min,

Гь Г2 - критерии суммарная длина связей и временная задержка,

а + ß= 1; 0<a,ß<l;

а и ß рассчитываются в ходе экспериментальных исследований,

П|, п2 - нормировочные показатели,

5 = —

nz

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

В данной работе а и 8 подбираются на основе мсюдов юории приняi ия решений Подбор коэффициентов производится с учетом представления лица принимающе1 о решения (ЛПР). К сожалению, па сегодняшний день не существует обьективпых методик подбора данных козффицисшов г)ю связано пепосредствеппо с тем, что уровень компетенции у каждого ЛПР разный Автором рассчитывались показатели а и 5, па основе различных пожеланий качественных характеристик и отображал свои представления па основе качества решений. Качественные характеристики это вербальные характеристики, а не формальные Качественные xapaKicpnci ики ло сравни тельные характеристики, не выражающиеся в цифрах

1.4 Классификация и анализ мсюдов размещения

1.4.1 Классификация традиционных методов размещения

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

Применяют различные признаки в качестве классификации алгоришов размещения элементов [15, 27]:

• По принципу решения задачи размещения.

• По структуре построения алгоритма.

• По постановке задачи

• По принципу структурной общности.

Разделяю^ алгоритмы размещения конструктивных и типовых блоков Па рисунке 6 приведена классификация алгоритмов размещения

Алюритмы размещения, основанные па математических меюдах, можно условно поделить па:

• алюритмы, использующие методы целочислсппою липсиною npoi раммировапия,

® алгоритмы, основанные на методе ветвей и границ

5 5

к-f ü S

Лл ropin m . ос i roun m г ы i i hü метоле роя части

AjHOpH J,S3 КОЛОНИИ

музтаиьен (АС'О)_

Лл го р i it,м "кол опт |Г _пчел (ЛВС)

Алгоритм косяк рмб

\j 111 р 11 г м о v¿i и пит

Си

К

СХ

О

Г

03

s

ЕГ сЗ

s

-е

s о о cd tî b¿

MD CN

ЧО

О

>->

о s

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Кулиев, Эльмар Валерьевич

4.4 Выводы

• Разработан программный комплекс для решения задачи размещения, с помощью которого проведены экспериментальные исследования разработанных алгоритмов на тестовых примерах. Определена оценка временной сложности: для гибридного алгоритма она имеет вид: 0(14 ) где N - число элементов СБИС.

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

2. Разработана модель поведения биологической системы роевого интеллекта для решения задачи размещения элементов СБИС.

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

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

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

6. Разработана двухуровневая архитектура генетического (эволюционного) алгоритма размещения элементов СБИС.

7. Представлены процедуры кодирования-декодирования решений и формирования окрестности поиска методом роевого интеллекта.

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

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

10. Разработан программный комплекс для решения задачи размещения, с помощью которого проведены экспериментальные исследования алгоритмов на тестовых примерах. Определена оценка временной сложности: для гибридного алгоритма она имеет вид: О(ТЯ ) •1 где N - число элементов СБИС.

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

Список литературы диссертационного исследования кандидат технических наук Кулиев, Эльмар Валерьевич, 2013 год

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

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

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

3. Норенков И.П., Кузьмик П.К. Информационная поддержка наукоемких изделий. CALS-технологии. М.: Изд-во МГТУ им. Н.Э. Баумана, 2002.

4. Сороколетов П.В. Коммутационные модели блоков ЭВА. Перспективные информационные технологии интеллектуальные системы, №2(18), 2004, с.46-53.

5. Chen L. Chang Y., "Solve the vehicle routing problem with time windows via a genetic algorithm," Discrete and continuous dynamical systems supplement, C. 240-249, 2007.

6. Waleron M, Waleron K, Podhajska AJ and E. Lojkowska 2002. Genotyping of bacteria belonging to the former Erwinia genus by PCR-RFLP analysis of a recA gene fragment Microbiology , 148, 583—595

7. Michael Wooldridge, An Introduction to MultiAgent Systems, John Wiley & Sons Ltd, 2002, paperback, 366 pages, ISBN 0-471-49691-Х.

8. Carl Hewitt and Jeff Inman. DAI Betwixt and Between: From «Intelligent Agents» to Open Systems Science IEEE Transactions on Systems, Man, and Cybernetics. Nov ./Dec. 1991.

9. The Journal of Autonomous Agents and Multiagent Systems, Publisher: Springer Science+Business Media B.V., formerly Kluwer Academic Publishers B.V.

10. Gerhard Weiss, ed. by, Multiagent Systems, A Modern Approach to Distributed Artificial Intelligence, MIT Press, 1999, ISBN 0-262-23203-0.

11. Sumpter D.J.T., Broomhead D.S. Formalising the Link between Worker and Society in Honey Bee Colonies // Lecture Notes In Computer Science: Proceedings of the First International Workshop on Multi-Agent Systems and Agent -Based Simulation. - MABS '98 LNAI, 1998. - P. 95-110.

12. Di Caro G., Dorigo M. Two ant colony algorithms for best routing in datagram networks // Proceedings of the Tenth IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS'98) / Eds: Y. Pan, S.G. Akl, K. Li. - Anheim: IASTED/ACTA Press, 1998. - P. 541-546.

13. Leguizamron G., Michalewicz Z. A new version of Ant System for subset problems // Proceedings of the 1999 Congress on Evolutionary Computation (CEC'99). - New Jersey: IEEE Press, 1999. - P. 1459-1464.

14. Berg, H. C., Motile Behior of Bacteria, Physics Today, Vol. 53, pp. 24-29, 2000.

15. Курейчик B.M., Лебедев Б.К., Лебедев О.Б. Поисковая адаптация. Теория и практика. М.: Физматлит, 2003, с 142-157.

16. Segall, J. Е., Block, S. М., And Berg, H. С., Temporal Comparisons in Bacterial Chemotaxis, Proceedings of the National Academy of Sciences, Vol.

17. Курейчик B.B., Курейчик B.M. Перспективные технологии для решения оптимизационных задач. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.1. М.: Физматлит, 2003, с 59-67.

18. Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, 1992.

19. Курейчик B.M. Генетические алгоритмы: Состояние. Проблемы. Перспективы. Теория и системы управления РАН. Москва. N 1, 2000, с.144-160.

20. Caldwell W.K. Mic - Cut Partitioning With Functional Replication for Technology - Mapped Circuits Using Minimum Area Over hed. -//-V.21, №4, april 2002, pp. 491 -496.

32. Емельянов, В. В. Теория и практика эволюционного моделирования. М.: Физматлит, 2003.

33. Sherwani, N. A. Algorithms for VLSI Physical Design Automation. - Boston: Kluwer Academic Publishers, 1995. 538 p.

34. Karypis G., Kumar V. A coarse-grain parallel multilevel k-way partitioning algorithm. In Proceedings of the eighth SIAM conference on Parallel Processing for Scientific Computing, 2003.

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

36. Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы, учеб. пособие для. Ростов - на - Дону: Ростиздат, 2004.

37. Хедрик Ф. Генетика популяций. М.: Техносфера, 2003.

38. Тарасов В.Б. Интеллектуальные системы в проектировании. Новости ИИ, №4. - 1993. - с.24 - 67.

39. Тарасов В.Б. От многоагентных систем к интеллектуальным организациям: философия, психология, информатика. М.: Эдиториал УРСС, 2002. -352с

40. Karaboga, D. An idea based on honey bee swarm for numerical optimization // Technical Report TR06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005.

41. Субботин C.A., Олейник Ан.А., Олейник Ал.А. Интеллектуальные мультиагентные методы (Swarm Intelligence), часть III // Фрагмент рабочих материалов монографии. - с. 35 - 52.

42. Goldberg D. Е. Genetic algorithms in search, optimization and machine learning. - Addison-Wesley Publishing Company Inc., 1989. - 442p.

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

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

45. Secanina, L. Evolutionary design of digital circuits: where are current limits? // Proceedings of the first NASA/ESA conference on adaptive hardware and systems. - 2006.

46. Конушин А. Эволюционные нейросетевые модели с незаданным заранее числом связей. - www.ict.edu.ru/fl/002414/numlevol.pdf

47. Vose M.D. Modeling simple genetic algorithms // In Whitley L.D. (ed): Foundations of Genetic Algorithms 2. Morgan Kaufmann, 2003.

48. Stoica A. Evolvable hardware for autonomous systems // CEC-2004. -Tutorial .Portland, Oregon.

49. Miller J. F, Banzhaf W., Daida J., Eiben A. E., Garzon M., Honavar V., Jakiela M., Smith R. E. An empirical study of the efficiency of learning boolean functions using a Cartesian Genetic Programming Approach // Proceedings of the 1st Genetic and Evolutionary Computation Conference. - San Francisco, CA: Morgan Kaufmann. - 1999. - Vol.2. - P.927-936.

50. Miller, J. F. Job D., Vassilev V. K. Principles in the Evolutionary Design of Digital Circuits. Genetic Programming and Evolvable Machines. Part I. -Netherlands: Kluwer Academic Publishers, 2000. - 1. - pp.7-35.

51. Holland J. H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. - The University of Michigan Press, 1975.

52. Курейчик В.М. , Зинченко JI. А. Эволюционное моделирование с динамическим изменением параметров // Труды VII национальной конференции по искусственному интеллекту. М.: Физматлит, 2000. -с. 516-523.

53. Сороколетов П.В. Курейчик В.В. Концептуальная модель представления решений в генетических алгоритмах. Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР», №. 9, с. 7-12, 2008.

54. Гладков J1. А., Зинченко JI. А., Курейчик В. В., Курейчик В. М., Лебедев Б. К., Нужнов Е. В., Сорокин С. Н. Методы генетического поиска. Научное издание. Таганрог: Изд-во ТРТУ, 2002. - 122 с.

55. Курейчик В. В Эволюционные, синергетические и гомеостатические методы принятия решений. Монография. Таганрог: Изд-во ТРТУ, 2001.

56. Potts J.C., Giddens Т., Yadav S. The Development and Evaluation of a improved Genetic Algorithm Based on Migration and Artificial Selection, IEEE Transactions on systems, man, and cybernetics. - January 1994. - Vol.24, No.l.-pp. 73-86.

57. Кулиев Э. В. Разбиение на основе муравьиной колонии.- 3стр. -, Государственное образовательное учреждение высшего профессионального образования «Ульяновский государственный технический университет», стр. 324-326

58. Кулиев Э. В., Лебедев Б.К. Определение функции окрестности в задачах размещения на основе роевого интеллекта. Автоматизация управления и интеллектуальные системы и среды. Третья международная конференция Автоматизация управления и интеллектуальные системы и среды (АУИСС -2012) стр. 45-48

59. Кулиев Э.В., Лежебоков A.A. О гибридном алгоритме размещения компонентов СБИС, 7стр, Известия ЮФУ №11, ноябрь 2012г. стр. 188-192

60. Кулиев Э.В., Лебедев Б.К. Нахождение максимального значения функции с помощью пчелиного алгоритма,, Зстр, IX Всероссийская научная конференция молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление». Таганрог: Изд-во ТТИ ЮФУ, 2011.-Т.1. - С. 236-238

61. Кулиев Э.В. Задача размещения элементов ЭВА с использованием генетического алгоритма и алгоритма пчелиной колонии. // Труды конгресса по интеллектуальным системам и информационным технологиям «IS-IT'12». Научное издание в 4-х томах, т. 3. - М.: Физматлит, 2012. — с. 99-104.

62. Кулиев Э.В., Генетический алгоритм решения задачи размещения элементов СБИС. IX Всероссийская научная конференция молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление». Таганрог: Изд-во ТТИ ЮФУ, 2012.-Т.2. - С. 55-59

63. Неупокоева Н.В., Курейчик В.М. Квантовые и генетические алгоритмы размещения компонентов ЭВА // Монография - Таганрог: Изд-во ТТИ ЮФУ, 2010.

64. Кулиев Э.В., Лежебоков A.A. Архитектура гибридного поиска для размещения компонентов СБИС // Научная сессия НИЯУ МИФИ-2013. Аннотации докладов. В 3 томах. Т.2. Проблемы фундаментальной науки. Стратегические информационные технологии. М.: НИЯУ МИФИ, 2013. с. 320.

65. Кулиев Э.В., Лежебоков A.A. Эффективный способ кодирования решения для задачи размещения компонентов СБИС. Электронный журнал. Информатика, вычислительная техника и инженерное образование. Св. № ФС77-39729 от 29.04.2010г. - Таганрог: ТТИ ЮФУ, 2012, №8(10), - С. 1-6

66. Кулиев Э.В., Заруба Д.В., Работа гибридного поиска размещения компонентов СБИС // Труды молодых ученых Южного федерального университета и Южного научного центра РАН «Высокопроизводительные вычислительные системы». Выпуск 2. Изд-во Ростов-на-Дону - Таганрог 2012. с 43-46

67. Кулиев Э.В., Лежебоков A.A. Исследование характеристик гибридного алгоритма размещения Известия ЮФУ №3, март 2013г. стр. 255- 261

68. Herrera F., Lozano M. Adaptive Genetic Algorithms, based on Fuzzy Techniques. - Granada, Spain, 1996. - pp. 775-780.

69. Davis L.D. Handbook of Genetic Algorithms // Van Nostrand Reinold. -New York, 1991.

70. Goldberg D. E., Kalyanmoy D. A. Comparative analysis of selection schemes used in genetic algorithms // In Rawlings G.(Ed.). Foundations of Genetic Algorithms. - Indiana University. - Mogan Kaufmann, San Mateo, CA, 1991.

71. Курейчик B.B. Мищенко M. H. Бионический метод определения путей оптимальной длины в графовых моделях // III-й Международный научно-практический семинар "интегрированные модели и мягкие вычисления в искусственном интеллекте. М: Изд-во Физматлит, 2005. - с. 261 - 266.

72. Генетические алгоритмы. URL: http://www.tspu.tula.ru/ivt/old_site/umr/eal g/w3c.html.

73. Норенков И. П., Косачевский О. Т. Генетические алгоритмы комбинирования эвристик в задачах дискретной оптимизации // Электронное научно-техническое издание "Наука и образование", 2005. URL: http://technomag.edu.ru/doc/56533.html.

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

75. Адлер Ю.П. Планирование эксперимента при поиске оптимальных условий. М.: Наука, 1971. 283 с.

76. Андерсон Т. Введение в многомерный статистический анализ/ Пер. с англ. Кичатова Ю.Ф. М.: Физматгиз, 1963. 500 е.: ил.

77. Даймонд С. Статистика в науке / Пер. с англ. А.Л. Дружининой М.: Статистика, 1970. 155 с.

78. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. 476 с.

79. Батищев Д.И., Коган Д.И. Вычислительная сложность экстремальных задач переборного типа. Нижний Новгород, Нижегородский госуниверситет, 1994.

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

81. Лежебоков A.A. Генетический алгоритм решения задачи размещения элементов СБИС с учетом временных задержек. // Сборник научных трудов международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте», т.1. - , М.: Физматлит, 2007. - с. 429-436.

82. Лежебоков A.A. Решение задачи размещения элементов СБИС с учетом временных задержек. // Труды Международных научно-технических конференций «Интеллектуальные системы» (AIS'06) и «Интеллектуальные САПР» (CAD-2006). Научное издание в 3-х томах. М.: Изд-во Физико-математической литературы, 2006, Т.1. с. 557-563.

83. Лежебоков A.A. Решение задачи размещения элементов СБИС с учетом временных задержек. // Известия ТРТУ. Тематический выпуск "Интеллектуальные САПР". Таганрог: Изд-во ТРТУ, 2006. №8(63). -с. 146-151.

84. Лежебоков A.A., Гладков Л.А. Результаты компьютерного моделирования решения задачи размещения элементов СБИС с учетом временных задержек. III Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем-2008» (МЭС-2008), 2008. - Сборник научных трудов/ под общ. ред. А.Л. Стемпковского. - М.: ИППМ РАН, 2008. С. 130-136.

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

86. Митропольский A.K. Техника статистических исследований. M., "Наука", 1971. 576 е.: ил

87. Останин А.Н. Применение математических методов и ЭВМ. Планирование и обработка результатов эксперимента // Учеб. Пособие. Минск: Высшая школа., 1989. 218 е.: ил.

88. Львовский E.H. Статистические методы построения эмпирических формул // Учеб. пособие для втузов. М.: Высшая школа, 1988. 239 с.

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

90. Болынов Л.Н., Смирнов Н.В. Таблицы математической статистики. М.: Наука, 1965. 464 с.

91. Гурский Е.И. Теория вероятностей с элементами математической статистики. М.: Высшая школа, 1971. 328 с.

92. Гренандер У. Случайные процессы и статистические выводы / Пер. с англ. и доп. Яглоба A.M. M.: Изд-во иностранной лит., 1961. 167 с.

93. Даймонд С. Статистика в науке / Пер. с англ. А.Л. Дружининой М.: Статистика, 1970. 155 с.

94. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. 476 с.

95. Батищев Д.И., Коган Д.И. Вычислительная сложность экстремальных задач переборного типа. Нижний Новгород, Нижегородский госуниверситет, 1994.

96. Курейчик В.В., Запорожец Д.Ю. Современные проблемы при размещении элементов СБИС. // Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР», № 7 (120), 2011. -Таганрог: Изд-во ТТИ ЮФУ, 2011. - с. 68-73.

97. Лебедев Б.К., Лебедев В.Б. Размещение на основе метода пчелиной колонии. // Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР» , № 12 (113), 2010. - Таганрог: Изд-во ТТИ ЮФУ, 2011.-е. 12-19.

98. Гладков JI.А. Интегрированный алгоритм решения задач размещения и трассировки на основе нечетких генетических методов. // Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР», № 7 (120), 2011. - Таганрог: Изд-во ТТИ ЮФУ, 2011. - с. 22-30.

99. Гладков JI.A., Шрамкова A.C. Использование генетического алгоритма для решения задачи размещения схем ЭВА с учетом временных задержек // Труды конгресса по интеллектуальным системам и информационным технологиям «IS- IT'11». Научное издание в 4-х томах, т.З.-М.: Физматлит, 2011.-е. 199-205.

100. Гладков JI.A. Гибридный генетический алгоритм решения задачи размещения элементов СБИС с учетом трассируемости соединений. // Вестник ростовского государственного университета путей сообщения. Научно-технический журнал, №3, 2011. - Ростов н/Д: Изд-во РГУПС, 2011.-е. 58-66.

101. Лаврик П.В., Глушань В.М. Оптимальное размещение элементов схемы на площади заданной конфигурации. Экспериментально-практический аспект // Труды конгресса по интеллектуальным системам и информационным технологиям «IS— IT'12». Научное издание в 4-х томах. — М.: Физматлит, 2012. - Т. 1. - С. 129-136

102. Кузнецов А.Д., Гладков Л.А. Формирование конфигурации схем ЭВА на основе решения задачи Штейнера // Труды конгресса по интеллектуальным системам и информационным технологиям «IS— IT'12». Научное издание в 4-х томах. - М.: Физматлит, 2012. - Т.З. - С. 51-56

103. Адрунов А.П., Лебедев О.Б. Размещение элементов СБИС при помощи процедур генетического поиска // Труды конгресса по интеллектуальным системам и информационным технологиям «IS- IT'12». Научное издание в 4-х томах. - М.: Физматлит, 2012. - Т.З. - С. 104-117

104. Адрунов А.П., Лебедев Б.К. Размещение компонентов СБИС методами роевого интеллекта // Пятьдесят девятая студенческая научная конференция. - Таганрог: Изд-во ТТИ ЮФУ, 2012

105. Лебедев Б.К., Лебедев О.Б. Оптимизация методами роевого интеллекта задач, интерпретируемых древовидными структурами // Тринадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-2012.Труды конференции. - Белгород: Изд-во БГТУ, 2012. -Т.2.-С. 219-227

106. Б.К. Лебедев, В.Б. Лебедев. Глобальная трассировка на основе роевого интеллекта // Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». - Таганрог: Изд-во ТТИ ЮФУ, 2010, №7 (108), С. 32-39

107. Б.К. Лебедев, В.Б. Лебедев Покрытие на основе роевого интеллекта // Труды конгресса по интеллектуальным системам и информационным технологиям «AIS- IT'10». Научное издание в 4-х томах. - М.: Физматлит, 2010. - Т.1. - С. 71-79