Quliyev genetika

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

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

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

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 Анализ модели пчелиного роя

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 Многоагентный подход к описанию разработанных моделей

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рекомендованный список диссертаций по специальности «Системы автоматизации проектирования (по отраслям)», 05.13.12 шифр ВАК

Разработка и исследование биоинспирированных алгоритмов разбиения схем при проектировании СБИС 2012 год, кандидат технических наук Полупанова, Елена Евгеньевна

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

Биоинспирированные методы и средства автоматизированного размещения фрагментов СБИС 2019 год, кандидат наук Курейчик Владимир Владимирович

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

Исследование и разработка гибридных генетических алгоритмов трассировки коммутационных блоков 2011 год, кандидат технических наук Кныш, Данил Сергеевич

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

Одной из сложнейших и наиболее важных задач при создании средств микроэлектронной техники является синтез юпологий СБИС. Синтез – создание проектного решения в виде его конструктивных особенностей, функциональной или структурной. О тличи тельной особенностью современного этапа является высокая сложное 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 ибридного алюритма размещения компонентов СБИС, сочетающая в себе в качес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 – Обобщенный цикл проектирования СБИС

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

Гиперграф рассмотренный на рисунке 3 имеет следующий математический вид: е! = , е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|

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

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

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

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

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

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

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

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

• простая реализация критерия [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 цент / ! юмд ЩХрУг)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

AjHOpH J,S3 КОЛОНИИ

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

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

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

Quliyev genetika

Заведующий кафедрой:
доктор с/х. наук, профессор Кулиев Рауф Алекпер оглы –
известный ученый в области генетики и слекции, является одним из создателей сорта хлопчатника Агдаш-3

Кафедра генетики и дарвинизма была организована в 1937-ом году. В этом же году по инициативе первого заведующего кафедрой Мирали Ахундова при кафедре был создан музей эволюционного учения, который функционирует и по сей день. С 1988-го года кафедрой руководит доктор сельско-хозяйственных наук,профессор Р.А.Кулиев.
На кафедре функционируют 2 учебные лаборатории: 1) Дрозофильная лаборатория, 2) Лаборатория Цитологии, гистологии и эмбриологии.

1. проф.Бабаев М.Ш.
2. проф.Ахундова Э.М.
3. проф.Алиева К.А.
4. доц.Ахундзаде А.И.
5. доц.Комачкова З.К.
6. доц.Гусейнова Н.Т.
7. доц.Самедов А.А.
8. доц.Меджидов М.М.
9. ст.препод.Микаилова К.Н.
10. к.б.н.и.о.доц.Акперова Г.Х.

Исследование мутагенного и антимутагенного эффекта физико-химических факторов на живые организмы

• Генетика
• Эволюционное учение
• Цитология
• Гистология
• Эмбриология
• Экологическая генетика
• Методика преподавания биологии

Публикации за последние 3 года

1. Р.А.Кулиев Генетика (учебник). Баку.2007. 408 с.
2. М.Ш.Бабаев. Общая биология (учебник). Баку.2007. 253 с.
3. М.Ш.Бабаев Практикум по генетике (учебное пособие). Баку. 2006. 140 с.
4. Э.М.Ахундова Экологическая генетика. Баку.2005. 264 с.
5. М.Ш.Бабаев Задачи по генетике .Баку. 2006. 192 с.

Гулиев, Джамиль Багатур оглы

Успешно закончил Московский государственный университет имени М. В. Ломоносова. Защитил докторскую диссертацию по специальности «Отечественная история».

Преподавательская и научная деятельность

С 1952 по 1972 года преподавал в Бакинском государственном университете. Получил учёное звание профессора.

Основные научные работы:

• «Борьба КП за осуществление национальной политики в Азербайджане» (1918—1920 года);
• «Образование Закфедерации»;
• «Империализм дөврүнүн биринҹи халг ингилабы» (азерб.) ;
• «К истории образования Второй Республики Азербайджана»;
• «Азербайджанская Республика» (1918—1920 года), 6-ой том «Истории Азербайджана».

Всего опубликовал 103 научные работы.

Был главным редактором всех 10 томов Азербайджанской Советской Энциклопедии, заместителем председателя редакционного совета 7-томника «История Азербайджана».

В 1972 Джамиль Гулиев был выбран членом-корреспондентом АН АзССР по дисциплине «Отечественная история». В 1980 году по той же дисциплине его выбирают действительным членом АН АзССР. Был избран членом Президиума Национальной академии наук Азербайджана.

Достижения

См. также

• Азербайджанская республика
• Национальная Академия Наук Азербайджана

Ссылки

• Официальный сайт АНА
• Академия Наук Азербайджана (eng)

• Персоналии по алфавиту
• Учёные по алфавиту
• Родившиеся 16 декабря
• Родившиеся в 1927 году
• Родившиеся в Шуше
• Умершие 27 декабря
• Умершие в 2010 году
• Умершие в Баку
• Историки по алфавиту
• Академики НАН Азербайджана
• Историки СССР
• Историки Азербайджана

Wikimedia Foundation . 2010 .