Содержание к диссертации
Введение
1 . Проблемы, методы, состояние и практика решения задачи планирования кристалла СБИС 16
1.1 .Введение в проблему 16
1.2. Анализ существующих методов и подходов к задаче планирования 20
1.2.1. Планирование, основанное на целочисленном программировании...20
1.2.2 Прямоугольная дуализация 23
1.2.3. Методы планирования, основанные на иерархическом дереве 24
1.2.4. Планирование, основанное на ограничениях 26
1.3. Методы оптимизации при решении задач проектирования СБИС 28
1.4. Выводы 44
2. Разработка алгоритмов и моделей поисковой адаптации для решения задачи планирования кристалла СБИС 46
2.1. Проблемная формулировка, термины и определения 46
2.2. Формирование пространства решений 47
2.3. Формирование плана методом свертки 48
2.4. Организация поисковой процедуры на основе коллективной адаптации при планировании кристалла СБИС с изменяющейся ориентацией блоков . 54
2.5. Организация поисковой процедуры на основе коллективной адаптации при планировании кристалла СБИС с изменяющимися размерами блоков...62
2.6. Выводы 69
3. Планирование СБИС на основе многоуровневой эволюции 70
3.1. Основные задачи раздела 70
3.2. Разработка принципов кодирования и декодирования хромосом при планировании на основе "гильотинного разреза" 70
3.3. Разработка представления и принципов кодирования дерева при планировании методом "не гильотинного разреза" 76
3.4. Разработка представления и принципов кодирования п-арного дерева разрезов 83
3.5. Стохастическое планирование СБИС 87
3.6. Генетические операторы при планировании 92
3.7. Организация процедуры генетического поиска при планировании 94
3.8. Выводы 103
4. Экспериментальные исследования разработанных алгоритмов 106
4.1. Цель экспериментальных исследований 106
4.2. Исследование механизмов генетического поиска 107
4.3. Исследование механизмов коллективной альтернативной адаптации.. 113
4.4. Исследование эффективности и сравнение результатов, получаемых представленными алгоритмами планирования кристалла СБИС 121
4.5. Выводы 126
Заключение 128
Литература
- Анализ существующих методов и подходов к задаче планирования
- Организация поисковой процедуры на основе коллективной адаптации при планировании кристалла СБИС с изменяющейся ориентацией блоков
- Разработка принципов кодирования и декодирования хромосом при планировании на основе "гильотинного разреза"
- Исследование механизмов генетического поиска
Введение к работе
Последние достижения в области интегральной схемотехники и технологии изготовления СБИС привели к увеличению сложности разрабатываемых изделий. В ближайшем будущем, новые технологии позволят проектировать схемы с геометрическими размерами транзисторов меньше 0.1 микрона при количестве транзисторов, превышающем 100 миллионов. Следствием этого становится существенное увеличение размерности решаемых задач на всех этапах проектирования. Такие схемы могут быть спроектированы только на основе иерархического подхода.
Совершенствование технологии производства и резкое повышение функциональной сложности СБИС часто опережает возможности проектирования, что вызывает необходимость в пересмотре разработанных ранее и существующих на сегодняшний день алгоритмов и методов конструкторского проектирования и стимулирует разработку новых эффективных методов и средств их проектирования.
В связи с этим особо актуальна разработка новых эффективных методов решения задач конструкторского проектирования^].
Очевидно, что решить проблему роста сложности можно только путем разбиения сложного объекта на части, которые затем обрабатываются проектными процедурами, т.е. представлением сложного объекта в виде иерархически описанного множества объектов меньшей размерности. Нормальным является разбиение схемы группированием элементов в блоки. В результате разбиения формируется множество блоков (модулей) и межсоединений между блоками. В очень больших схемах используется иерархическая структура разбиения.
При проектировании больших систем, часто топологическая схема требуется уже на ранних стадиях проектирования, хотя еще не были спроектированы все модули, т.е. не вся информация о всех модулях имеется в наличии, или, что еще хуже, часть этой информации неточна. Планирование это
5 ранняя фаза проектирования СБИС. Оно дает информацию о приблизительных значениях площади, задержки, мощности и других рабочих характеристиках..
Планирование с учетом неопределенности - это проблема получения хорошей топологии, когда информация о размерах модулей не является полной.
Таким образом, одной из важнейших задач синтеза и формирования топологии СБИС является задача планирования кристалла СБИС.
Основными проблемами задачи планирования кристалла СБИС - это проблема поиска подхода к представлению решения (плана) и проблема построения оптимизационной процедуры поиска решения.
В настоящее время наибольшее распространение получил подход, при котором план строится на основе различного рода деревьев. Однако существующие способы записи и кодирования деревьев предполагают для их модификации использование нелинейных процедур.
Особенностью проектирования СБИС является очень большая область поиска решения. По этой причине существует проблема, связанная с огромным числом возможных проектных решений, которые необходимо исследовать, чтобы выбрать решение, которое бы отвечало входным требованиям.
Задача планирования кристалла СБИС относится к классу NP. Поэтому очень большой класс разработанных к настоящему времени алгоритмов планирования кристалла СБИС основан на различных эвристиках, обеспечивающих получение решений в полиномиальное время. Основным недостатком этих алгоритмов (последовательных и итерационных) является невысокое качество результатов из-за попадания в "локальные ямы", малая пригодность для задач большой размерности, плохая приспособленность для реализации на современных технических средствах, отсутствие альтернатив. Одним из возможных методов решений этой проблемы является использование методов случайного направленного поиска, основанного на моделирование естественных процессов. К таким относятся бурно развивающиеся в последнее время методы поисковой адаптации на основе механизмов генетического поиска и эволюционной адаптации. Слово адаптация, широко используемое в современной научно-технической литературе, заимствовано из биологии, где оно означает приспособление живых организмов к изменяющимся окружающим условиям. Адаптация многолика и разнообразна. Известны такие проявления адаптации, как эволюция, привыкание, обучение и самообучение, организация и самоорганизация и т.д. [2,3,4].
Наблюдения в области адаптации живых организмов привели к идее "наделить" указанным свойством технические системы [4].. Это достигается введением в конструкцию технической системы возможности приспособления к новым ситуациям, заранее не предвиденным с тем, чтобы в процессе функционирования эта система изменялась и улучшала свои характеристики.
Значительный вклад в разработку технических устройств и моделей имитирующих процессы подобной адаптации, внесли - М.Л. Цетлин, Л.А. Растригин, А.А. Красовский, Д.А. Поспелов, Г.С.Поспелов, В.Ф. Венда, А.А. Самарский, ЯЗ. Цыпкин, П.В. Куропаткин, В.Г. Срагович, Б.И. Кузьмин, В.П.Сигорский, D.E.Goldberg, J.H.Holland, Д.И.Батищев, И.Л.Букатова, В.М.Курейчик, и многие другие ученые
В настоящее время в технических системах существует два подхода к организации адаптивных процессов [5].
При первом подходе адаптивные процессы поддерживают объект в состоянии, определяемом целью и, в этом смысле, адаптация является управлением [6,7].
При втором подходе адаптивные процессы связанны с максимизацией эффективности функционирования некоторого объекта. Здесь адаптация рассматривается как оптимизация.
При втором подходе решение задачи адаптации сводится к определению такого управляющего воздействия, при котором достигается максимальная эффективность работы объекта и, одновременно, выполняются все жесткие требования, предъявляемые к этому объекту [8,9]. Такая задача является задачей оптимизации (максимизации эффективности) в обстановке ограничений.
7 Процесс разработки проекта на САПР может быть представлен как адаптивный поисковый процесс, целью которого является достижение объектом проектирования оптимального состояния, при котором его оценки эффективности достигают наилучших значений [10].
Объект адаптации рассматривается как обучающаяся система, помещенная в среду, характеризующуюся вероятностной реакцией.
Значительным шагом в развитии технических устройств, для имитации адаптации был предложенный М.Л. Цетлиным подход, основанный на использовании вероятностных обучающихся автоматов [11].
Работа адаптивной системы моделируется как функционирование некоторого вероятностного автомата, действующего в случайной среде. Адаптивная система представляется в виде двух компонентов - среды и управляющего устройства.
Под средой понимается объект управления (объект оптимизации), а управляющее устройство работает в соответствии с алгоритмом случайного поиска.
Основываясь на этой идее, М.Л. Цетлин поместил в среду, характеризующуюся случайной реакцией, вероятностный автомат адаптации (АА) для реализации функции управляющего устройства. Адаптация автомата производится путем самообучения в процессе его функционирования.
На каждом такте работы адаптивной системы в соответствии со значениями выхода автомата адаптации формируется управляющее воздействие, приводящее к изменению состояния среды и показателя качества. Идеи М.Л. Цетлина легли в основу теории построения алгоритмов альтернативной поисковой адаптации.
Идеи использования методов естественной генетики появились в результате работ Холланда [12]. Генетический алгоритм (ГА) есть адаптивный поисковый метод, который основан на селекции лучших индивидуальностей в популяции, подобно эволюционной теории Дарвина. Отличительной особенностью генетических алгоритмов является следующее:
8 -генетические алгоритмы работают на основе популяции, т.е. на множестве индивидуальностей; - оперирование производится не с решениями, а с их кодами. Каждому решению соответствует одна или несколько хромосом, которые представляют собой закодированный генетический материал. Хромосомы состоят из генов. Каждый ген имеет свой локус или позицию в хромосоме. Гены могут иметь различные значения: число, строка, сектор, массив и т.д. Решение получается на основе декодирования хромосом [12, 13].
Преимуществом этих методов является параллельная обработка альтернативных решений, что является мощным средством выхода из локальных оптимумов. Алгоритмы поисковой адаптации являются алгоритмами случайного поиска, однако, заложенная в них стратегия эволюционного развития самообучения и саморазвития приводит к синтезу решений близких к оптимальным. Однако эти подходы в задачах конструкторского проектирования СБИС еще не получили достаточного развития и обобщения.
Разработка эволюционных алгоритмов связана с решением проблемы представления - преобразования исходной формулировки задачи в компоненты некоторой адаптивной системы. Обычно существует несколько способов такого представления задачи. Искусство выбора хорошего представления очень существенно для применения методов адаптации к решению оптимизационных задач.
В связи с этим становится актуальным вопрос поиска и разработки эффективных представлений, методов и алгоритмов для решения задачи планирования кристалла СБИС.
Целью диссертационной работы является разработка на основе эволюционной адаптации новых оптимизационных процедур для решения задачи планирования кристалла СБИС;
Для достижения поставленной цели решались следующие задачи.
9 1.Проведение сравнительного анализа методов оптимизации и выработка общего подхода и структуры к организации оптимизационных процедур на основе методов эволюционной адаптации;
2.Разработка новых моделей и подходов к решению задачи планирования кристалла СБИС;
3.Разработка представления исходной формулировки задачи планирования кристалла СБИС в виде адаптивного процесса на основе самообучения, моделируемого вероятностными автоматами адаптации (АА), что предполагает: формирование моделей среды и объекта адаптации, локальных целей объектов адаптации и глобальной цели коллектива; разработка структуры обучающегося АА и механизмов переходов в АА; разработка общей структуры процесса адаптивного поиска;
4.Разработка представления исходной формулировки задачи планирования кристалла СБИС на основе генетической эволюции, что предполагает: формирование структур и принципов кодирования хромосом с учетом специфики задачи планирования кристалла СБИС, оптимизирующих процесс генетического поиска; разработку, модификацию и адаптацию к решаемой задаче генетических операторов; разработку и модификацию механизмов генетического поиска.
5.Разработка и исследование алгоритма планирования кристалла СБИС на базе общего подхода к построению адаптивных процедур, опирающегося на сочетание принципов адаптации на основе самообучения и генетического поиска; б.Разработка программных средств на основе проведенных исследований для решения задачи планирования кристалла СБИС.
Методика исследований базируются на комплексном использовании результатов теории множеств, теории графов, теории алгоритмов, теории автоматов, исследования операций, математического моделирования,
10дискретного программирования, оптимизации, эволюционного моделирования, методов конструирования ЭВА, РЭА и СБИС. Практическая проверка предлагаемых моделей и методов осуществлялась путем их программной реализации, апробацией на реальных задачах и тестированием на стандартных тестах (бенчмарках).
Научная новизна работы заключается в теоретическом обобщении и решении проблемы, имеющей важное значение для решения задачи планирования кристалла СБИС. К наиболее существенным научным результатам работы относятся следующие:
1. Разработаны методы и способы представления задачи планирования кристалла СБИС в виде адаптивных поисковых процедур, основанных на сочетании принципов эволюционной и альтернативной адаптации - самообучения и генетического поиска
Разработаны новые механизмы решения задачи планирования кристалла СБИС на основе альтернативной коллективной адаптации с использованием вероятностных средств для преодоления барьера локального оптимума
Разработаны и исследованы с учетом специфики задачи планирования кристалла СБИС, с ориентацией на большие размерности новые принципы кодирования решений в виде структурированных и многохромосомных представлений, отличающихся гомологичностью, простотой, линейной оценкой трудоемкости.
Разработаны и экспериментально исследованы новые адаптивные поисковые алгоритмы для решения задачи детерминированного и стохастического планирования кристалла СБИС на основе самообучения и генетического поиска и предложены технологии как их совместного, так и автономного использования.
Достоверность результатов диссертационной работы. Достоверность результатов, полученных в работе, подтверждаются работой вычислительных экспериментов на ЭВМ, публикациями, апробацией работы на ряде международных, всероссийских и всесоюзных конференций, результатами практического использования предложенных в диссертации моделей, методов и алгоритмов, подтвержденных актами о внедрении и использовании.
Основные положения, выносимые на защиту.
Архитектура алгоритма планирования кристалла СБИС методами эволюционной адаптации на основе самообучения и генетического поиска.
Модели, методы и алгоритмы альтернативной коллективной адаптации для решения задачи планирования кристалла СБИС. Новые технологии и средства повышения эффективности процесса альтернативной адаптации для усиления способности выхода из "локальных ям".
Модели, методы и алгоритмы решения задачи детерминированного и стохастического планирования кристалла СБИС на основе генетической адаптации. Новые технологии и механизмы генетического поиска на базе адаптируемого виртуального набора популяций с альтернативными структурами хромосом и генетических операторов.
Принципы кодирования решений и структуры хромосом, учитывающие специфику решаемых задач с ориентацией на задачи большей размерности, отличающиеся гомологичностью, линейными оценками пространственной и временной сложности и имеющих широкую сферу применения.
Практическая ценность работы состоит в том, что основные теоретические положения доведены до конкретных методик и алгоритмов. Разработанные методы эволюционной адаптации на основе самообучения и генетического поиска, являются мощным средством выхода из "локальных ям", приводящим к синтезу решений, близких к оптимальным. Алгоритм планирования кристалла СБИС методами эволюционной адаптации реализован в виде программы на языке Borland C++ для Windows. Созданный комплекс программ позволяет при решении задачи планирования кристалла СБИС осуществлять выбор метода решения: только методами генетического поиска;
12 методами коллективной, альтернативной адаптации, моделируемой вероятностными обучающимися автоматами адаптации; либо их совместное использование. Предложенные методы позволяют достигнуть улучшенных показателей объектов проектирования. Кроме того, предложенные алгоритмы и программы носят достаточно универсальный характер и могут быть использованы для решения задач в области генетического программирования, в частности задачи символического регресса, заключающейся в построении математического выражения, задаваемого примерами.
Реализация результатов работы. Основные теоретические и практические результаты, полученные в диссертационной работе, использованы в ряде научно-исследовательских работ, проводимых в Таганрогском государственном радиотехническом университете руководителем или исполнителем которых являлся автор.
В работах, выполняемых по грантам РФФИ: "Генетические алгоритмы в интеллектуальных САПР" (шифр 99-01-00050); "Символьные информационные технологии проектирования на основе эволюционной адаптации" (шифр 00-01-00125); "Эволюционное проектирование с адаптацией" (шифр 01-01-00044).
По гранту Минобразования РФ на проведение фундаментальных исследований в области технических наук - "Исследование и разработка методов трассировки СБИС на основе эволюционной адаптации".
По гранту РФФИ Конкурс молодых ученых и специалистов "Разработка эволюционных алгоритмов и программ для решения основных задач автоматизированного проектирования" (шифр 99-01-00050, Руководитель Лебедев В.Б.);
В г/б НИР № 12353, выполняемой по ЕЗН Минобразования РФ -"Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений ".
В х/д работе №16005 «Поисковые исследования по созданию нейросистем, основанных на генетических и эволюционных технологиях и
13 ориентированных на решение оптимизационных задач военного назначения в реальном масштабе времени».
В х/д работе № 710/98-16002-7 «Участие в разработке технических предложений по созданию РИС и алгоритмов ее функционирования» (шифр «Модуль 8»)
Применение предложенных в диссертационной работе алгоритмов и разработанных программ позволило уменьшить время проектирования элементов вычислительных систем.
Научные результаты и разработанное программное обеспечение диссертационной работы внедрены в учебный процесс по курсам "Прикладные интеллектуальные системы", "Проблемы разработки и перспективы интеллектуальных САПР", "Методы оптимизации", а также в цикле лабораторных работ по курсу "Автоматизация конструкторского проектирования СБИС". Акты внедрения и использования научных результатов прилагаются.
Апробация работы и публикации. Основные положения и результаты докладывались и обсуждались на: Всероссийской НТК с международным участием "Интеллектуальные САПР" (Геленджик, 1999-2001гг); Международном конгрессе "Искусственный интеллект в XXI веке" (Дивноморское, 2001 г.); Международных НТК "Искусственные интеллектуальные системы (IEEE AIS'02) " и " Интеллектуальные САПР (CAD-2002) " (Геленджик, 2002 г.); Всероссийской студенческой НК "5 Королевские чтения" (Самара, 1999 г.); 4-й и 5-й Всероссийской НК студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления" (Таганрог, 1998, 2000 г.г.); НТК профессорско-преподавательского состава ТРТУ (2000-2003 г.г.) и других конференциях.
По теме диссертации опубликовано 13 печатных работ.
Структура и объем диссертационной работы. Диссертация состоит из введения, 4 глав, заключения, списка использованной литературы и
14 приложения. Объем диссертации 138 страниц, включая список литературы из 118 наименований. В приложении вынесены акты об использовании и внедрении результатов диссертационной работы.
Во введении показана актуальность, сформулированы основные задачи исследований, указаны полученные в работе научные результаты, их практическая значимость, апробация. Приводится структура и характеристика разделов работы.
В первой главе дается постановка задачи исследования. Проанализированы основные подходы и методы решения задачи планирования кристалла СБИС. Показана эффективность методов эволюционной адаптации. Предложен общий подход к поисковой адаптации, рассмотрены основные механизмы генетического поиска и альтернативной коллективной адаптации для решения оптимизационных задач.
Вторая глава посвящена разработке адаптивных поисковых процедур для решения задачи планирования кристалла СБИС. Рассмотрены методика представления решения и формирования пространства решений. Разработаны алгоритмы и методики на основе механизмов коллективной альтернативной адаптации для двух постановок: с фиксированными размерами, но изменяющейся ориентацией модулей; с гибкими размерами модулей. С учётом специфики задачи планирования кристалла СБИС в рамках каждой постановки определены объекты коллективной адаптации, разработаны и модернизированы механизмы альтернативной поисковой адаптации, что позволило разработать представление поиска решения задачи планирования в виде адаптивного поискового процесса на основе самообучения. Предложены различные методики выработки откликов среды и реализации альтернатив, что даёт возможность осуществлять настройку алгоритма в зависимости от требований и целей. Приведены оценки сложности разработанных алгоритмов.
В третьей главе предложены алгоритмы эволюционной адаптации для решения задачи планирования кристалла СБИС. Дается постановка задачи при детерминированном и стохастическом задании размеров модулей,
15 обосновывается выбор критериев. Рассмотрены принципы кодирования хромосом при планировании на основе "гильотинного разреза" и "негильотинного разреза" В работе используется два типа "гильотинных" разрезов - бинарный и и-арный.. Для представления бинарного дерева разрезов используется польская запись, а для представления л-арного дерева разрезов запись, разработанная автором.
Предложенные способы кодирования хромосом, исключают появление нелегальных решений и имеют линейную оценку трудоемкости. Описаны модифицированные генетические операторы. Рассмотрена параллельно-последовательная структура генетического поиска для многохромосомного представления решения
В четвертой главе приведены оценки эффективности рассмотренных алгоритмов и результаты экспериментальных исследований.
Описываются средства повышения эффективности адаптивных поисковых процедур и рекомендации по выработке значений управляющий параметров.
В заключении приводятся основные результаты, полученные в диссертационной работе.
В приложении приводятся акты об использовании результатов диссертационной работы.
Анализ существующих методов и подходов к задаче планирования
Проблема планирования моделируется как набор линейных уравнений, использующих целочисленные переменные {1,0} [20,21]. Рассматриваются два типа ограничений: ограничения перекрытий и ограничения маршрутизации. Ограничения перекрытий предотвращают перекрытия двух любых блоков, а ограничения маршрутизации оценивают площадь маршрутизации между двумя блоками. Ограничения по перекрытию для фиксированных блоков: дано два фиксированных блока Bri и Brj которые не должны перекрываться.
Имеется четыре возможных способа расположения блоков так, чтобы они не перекрывались [22,23]. Пусть {х,.,у,.,w,.,/г,. } и {л;., .,и .,/г. } будут кортежами длины четыре, связанными с блоками Bri и Brj соответственно, где {х„у) даёт расположение блока, wt - ширина блока, ht - высота блока. Блок BrJ может быть расположен правее, левее, сверху или снизу блока Bri. Эти условия трансформируются в следующие уравнения: xt+wt Xj (Bri правее BrJ) Xi-Wj Xj (Brjлевее Bri) Уі+кі Уу (Вгівьіше Brj) yi-hJ y] (BrJ иижеВгі) (1.1)
Чтобы удовлетворить одному из этих уравнений две целочисленные переменные ху и ytj используются для каждой пары блоков. Две ограничивающие функции W и Н определены так, что У І - У j х,-ху W и Н. Величина W может быть эквивалентна WMAX, которая является максимально позволенной шириной чипа или W = Zf=i9+r w, Аналогично Н = НМАХ, максимально допустимая высота чипа или Н = Y,?=iq+rht Множество уравнений (1.1) может быть переписано с введением целочисленных переменных, чтобы создать условие «или»: xl+wluxJ+W(xff+ylf) X Wj Xj+W -X..+Уу) y h yj+W + Xy-y,,) y hjbyj+Wfr-Xy-yt,) (1.2) Так как целочисленные переменные xtJ и х(. могут принимать значения
О или 1, только одно из выше перечисленных уравнений будет активно, а другие уравнения будут истиной исходя из значений xt. и х,.. Например, когда Ху= Ху=\, первое уравнение в (1.2) становится активным, а все остальные - истинны. xt 0 Уі 0 xt+wt W (1.3) у yt + ht где у - минимизируемая высота. Если для оптимизации решения допускается вращение блоков таким, для каждого блока используется переменная - zt (z,=0 когда блок находится в исходной ориентации, и z(. = 1, когда блок повёрнут на 90). Ограничения для фиксированных блоков с учетом вращения могут быть представлены как: х, + z,h, +(1- zt )wt Xj + W(x.. + уtJ) x, -Zjhj- -z j xj+W -xij +7,) У і + , w, +(1- z, )ht у j + W{\ + x, - ytJ) У І - ZJJ - (1 - ZJ h У j + H2 - ху - У,) (1 -4) где M = MAX(W,H). Ограничения (1.3) переписаны как: , 0 Уі 0 xt+{ -zt)wt+ztht W (1.5) y yt +(l-z.)w,. +zihi
Задача планирования для фиксированных блоков без рассмотрения транзитных областей может быть решена поиском минимума у по ограничениям (1.4) и (1.5) [24,25,26]. Ограничения по перекрытию для гибких блоков:
Гибкие блоки могут принимать прямоугольную форму в пределе ограниченного диапазона характеристических отношений, то есть его высота и ширина может меняться, оставляя площадь фиксированной[27,28]. Не линейное отношение площади линеаризуется вокруг точки максимально разрешенной ширины, применяя два первых члена ряда Тейлора дающие: /2,. = hj0 + Aw,.Я,, где где Awt - непрерывная переменная блока Bfr Ограничение на перекрытия для гибкого блока Bfl и фиксированного блока В могут быть записаны как: xi + WIMAX - &wi xj (вп правее Brj), или xt - Wj Xj (В . левее Bri), или yi + hi0 + Aw, Л, yj (Bri выше Brj), или Уі-hj yj (BrJ нижеБп.)
Для удовлетворения условия «или» между уравнениями для каждой пары блоков используются две целочисленные переменные Ху и у0-, как это было сделано для фиксированных блоков [29,30].
То же множество уравнений может быть расширено, чтобы получить ограничения на перекрытия между двумя гибкими блоками. Используя ту же технику, могут быть разработаны ограничения на длину межсоединений и ограничения на область маршрутизации. Это множество уравнений — входные данные для любого стандартного программного обеспечения (ПО) линейного программирования, такого как LINDO. Расположение блоков и их размеры - переменные, значения которых рассчитываются ПО исходя из ограничений и целевой функции.
Организация поисковой процедуры на основе коллективной адаптации при планировании кристалла СБИС с изменяющейся ориентацией блоков
Будем называть преобразование исходной формулировки задачи в компоненты некоторой адаптивной системы проблемой представления. Обычно существует несколько способов такого представления задачи. Искусство выбора хорошего представления очень существенно для применения методов адаптации к решению оптимизационных задач [108].
Основными компонентами адаптивной системы являются: внешняя среда, объект адаптации и общая структура процесса адаптации.
Любая система, живая или техническая, представляется совокупностью элементов для каждого, из которых может быть поставлена оптимизационная задача. В этом случае необходим переход к моделированию целесообразного поведения коллектива автоматов. Объект можно разбить на подобъекты, которые могут существовать в альтернативных состояниях. Альтернативная коллективная адаптация подобъектов приводит к эволюционной адаптации всего объекта в целом. Этот подход можно расширить, т.е. использовать многоуровневую иерархическую структуру объекта.
Представление исходной формулировки задачи в виде адаптивной системы, основанной на идеях коллективного поведения, предполагает решение следующих задач [108]: a) формирование моделей среды и объектов адаптации; b) формирование локальных целей объектов адаптации и глобальной цели коллектива; c) разработка альтернативных состояний объекта адаптации, структуры обучающегося автомата адаптации и механизмов переходов АА; d) разработка методики выработки управляющих сигналов поощрения или наказания в процессе работы адаптивного алгоритма; e) разработка общей структуры процесса адаптивного поиска. В качестве объекта адаптации может выступать сам автомат адаптации, т.е. его структура и механизмы переходов.
В работе используется два подхода к уменьшению общей площади SR прямоугольника R: SR = VIQ-WQ.
При первом подходе размеры модулей фиксированы [109]. Можно изменять ориентацию модулей. Для заданного дерева разрезов отыскиваются ориентации модулей, обеспечивающие при свертке минимальные значения показателя F = SR.
При втором подходе размеры модулей могут изменяться в соответствии с ограничениями (2.1),(2.2). Для заданного дерева разрезов отыскиваются размеры модулей, соответствующих ограничениям (2.1),(2.2) и обеспечивающих при свертке минимальное значение показателя F = SR.
Рассмотрим сначала первый подход Представим исходную формулировку задачи в виде адаптивной системы, работающей на основе моделирования коллективного поведения автоматов адаптации.
Ориентацию модуля т,- при его размещении в области будем задавать параметром ot. о,є{1,2}, т.е. для тэт,- возможны два способа (две ориентации) размещения в области щ . Обозначим через (Н\,wlд размеры тг при о, = 1, а через (h2i,w2i) размеры т, при о, = 2. При этом h1\ = w2t, h2{ = w11 (рис.2.6), h1, h2t, 1 -. 2 W i W ,-. Пусть первой ориентации соответствует такое расположение модулей ти hl h2 что —у- 1, а при второй ориентации - 1 (рис.2.6).
Множество модулей M={mi\i=l,2,..., п} с фиксированными размерами, дерево разрезов D={dj\J=l,2,...,2n-lJ и ориентации модулей 0={ОІ\І=1,2,...,П} однозначно определяют план, который строится с помощью процедуры свертки.
Пространство решений составляют решения, отличающиеся друг от друга значениями элементов множества О, задающими ориентацию модулей.
Процесс поиска в пространстве решений оптимального решения представим в виде адаптивной системы работающей в условиях неопределенности.
На каждом шаге работы адаптивной системы под действием адаптирующего воздействия осуществляется переход от одной вершины пространства к другой, т.е. перевыбор альтернативных значений элементов множества О.
В качестве объектов адаптации будем рассматривать модули т,. Каждый объект может быть только в одном из двух альтернативных состояний {A itA ,). Состояние объекта адаптации соответствует выбранной альтернативе (ориентации).
Пусть для множества модулей М с фиксированными размерами задан некоторый первоначальный план, т.е. задано дерево разрезов, ориентация модулей, в соответствии с выбранными альтернативами, произведена свертка областей и сформированы выражения для определения значений параметров h0 и w0 прямоугольника R.
Для каждого т,- средой будет множество взаимодействующих друг с другом и с ті модулей Mt = М\ ті. Состояние среды определяется выбранными для всех модулей ориентациями. Оценка состояний объекта адаптации зависит как от состояния среды, так и от состояния объекта адаптации в среде.
Глобальная цель коллектива объектов адаптации, т.е. множества модулей М, - достичь такого состояния, при котором значение критерия F имеет минимальное значение.
Разработка принципов кодирования и декодирования хромосом при планировании на основе "гильотинного разреза"
Плану кристалла на основе "гильотинного разреза" соответствует дерево разрезов, листьями которого являются вершины, соответствующие блокам, а внутренние вершины дерева соответствуют разрезам [99]. Процесс синтеза плана включает два этапа. На первом этапе синтезируется дерево разрезов. Второй этап заключается в метризации плана, т.е. в определении размеров областей, удовлетворяющих дереву разрезов и ограничениям (2.1),(2.2).
Задать дерево разрезов это, во-первых, задать структуру этого дерева, т.е. последовательность бинарных разрезов, во-вторых, для внутренних вершин дерева, соответствующих разрезам, указать тип разреза Н - горизонтальный или V - вертикальный, в-третьих пометить висячие вершины дерева (листья) номерами блоков [35]. Обозначим через Е = {et і = \,2,..,п } множество висячих вершин дерева разрезов, которые располагаются в горизонтальном ряду слева направо. Задать разметку блоков можно с помощью вектора Q = qt \ і - 1,2,...,и , где qt - номер блока.
Основу генетического алгоритма составляют принципы кодирования и декодирования хромосом, генетические операторы и структура генетического поиска. В работе решение кодируется набором R из четырех хромосом: R={H1,Н2,НЗ,Н4}. Хромосома HI несёт информацию о разметке множества вершин Е. Хромосома Н2 содержит информацию о структуре дерева. Хромосома НЗ содержит информацию о типах разрезов (Н или V). Хромосома Н4 содержит информацию о значениях соотношений —l-.
Пусть п - число областей плана (число вершин множества Е). Хромосома HI имеет вид: HI = glt g2 gn-i Каждый ген gi может принимать значение в интервале от 1 до ( п+\- і ). Например: для п = 8; 1 gi 8; 1 g2 7; 1 g3 6;...; 1 g7 2.
Декодирование хромосомы HI производится следующим образом. Пусть для п = 8 имеется хромосома HI = 3,5,3,4,4,2,2 , и пусть имеется опорный вектор В1 = 1,2,3,4,5,6,7,8 , число элементов которого равно п, а значения элементов изменяются от 1 до п. Рассматриваем по порядку гены хромосомы и в соответствии с их значениями выбираем элементы в опорном векторе и записываем их в порядке выборки в вектор Q.
Значение gi -3. Выбираем в В элемент Ъ j (j= gj =3, b13 =3) и записываем его на первое место формируемого вектора Q, т.е. q} = b13=3 .
Удаляем элемент Ь 3изВ и получаем вектор В = 1,2,4,5,6,7,8 , содержащий 7 элементов. Следующим выбирается g2, g2 =5. Отыскиваем элемент Ь 5 вектора В . Ь 5=6. Следовательно, q2 = 6. Удаляем из В элемент Ъ 5 , получаем вектор В3 = 1,2,4,5,7,8 . Далее:
g3 = 3, Ь33 = 4,q3 = 4,B4 = 1,2,5,7,8 \g4=A, b\ = l,q4 = l,B5 = 1,2,5,8 ; g5 =4,b54 = 8,q5 = S,B6 = l,2,5 ; g6 =2, b62 = 2, q6 = 2, B7 = 1,5 ; g7 = 5, b72 = 5, q7 = 5, B8 = 1 ; и наконец, q8 = 68; = 1.
В итоге получаем вектор Q = 3,6,4,7,8,2,5,1 , задающий разметку множества вершин Е.
Рассмотрим структуру хромосомы Н2. Введём алфавите = {О, }. Структуру дерева разрезов можно задать, используя на базе алфавита А польское выражение для бинарного дерева, где О соответствует листьям дерева разрезов (областям), а - соответствует внутренним вершинам дерева (разрезам) [113,114]. Польские выражения для деревьев, представленных на рис.3.1,а и 3.1,Ь, имеют следующий вид:
00 00»0« 00«00 »0« .
Процесс восстановления дерева по польскому выражению достаточно прост. Последовательно слева направо просматривается польское выражение, и отыскиваются буквы типа , соответствующие разрезам. Каждый такой разрез объединяет два ближайших подграфа, расположенных в польской записи слева от знака и образованных на предыдущих шагах. На рис.3.1,а и 3.1,b показаны контуром образованные подграфы при просмотре польского выражения.
Отметим основные свойства польского выражения, выполнение которых необходимо, чтобы выражению соответствовало дерево разрезов. Обозначим через пх — число элементов польского выражения типа О, а через п. - число элементов типа . Для дерева разрезов всегда выполняется равенство пх = п.+ 1.
Если в польском выражении провести справа от знака сечение, то слева от сечения число знаков О больше числа знаков , по крайней мере, на единицу. пхк -число знаков О в записи с 1 по к элемент; п k -число знаков в записи с 1 по к элемент; п - n k : 1.
Первый знак в польском выражении (при просмотре слева направо) может появиться только после двух знаков О . Пронумеруем позиции между знаками О, как показано на рис.3.2. Максимальное число знаков , которое может появиться в позиции, равно номеру позиции. Напомним, что общее число п. = пх- 1.
Если польское выражение соответствует вышеперечисленным свойствам, то ему соответствует дерево разрезов.
Хромосома Н2 имеет вид: Н2 = g/, g2,..., gn В результате декодирования хромосомы строится польское выражение. Число генов в хромосоме равно п., т.е. числу знаков . Значение гена gt колеблется в пределах от / до п., т.е. / Z(g() п.. Значение гена указывает номер позиции в польском выражении в которую необходимо поместить знак . Например: пусть для п. = 4 имеется хромосома Н2 = 4,2,2,4 . Польское выражение, соответствующее хромосоме, имеет вид: оо о- с о 4»
Дерево, соответствующее данному польскому выражению, представлено на рис.3.3,а.
С помощью хромосомы НЗ задаются типы разрезов (Н или V). Число генов НЗ равно п.. Значением гена является 0 или 1,0- соответствует Н и 1 - соответствует V. Разметка внутренних вершин (определение типа разрезов ) осуществляется последовательно в порядке расположения знаков в польском выражении.
Например: НЗ = 1,0,0,1 . Модифицированное с учётом НЗ польское выражение примет вид: OOOHVOOVH. Пусть HI = 1,1,1,1,1 . Соответствующий HI вектор Q = 1,2,3,4,5 .
Тогда для HI = 1,1,1,1 , Н2 = 4,2,2,4 ,НЗ = 1,0,0,1 дерево разрезов имеет вид, представленный на рис.З.З,Ь. А план разрезов имеет вид, представленный на рис.3.4,а.
Размеры областей и описывающего прямоугольника плана определяются путем последовательной свертки областей по дереву разрезов, исходя из размеров модулей, помещаемых в эти области. Размеры модулей задаются хромосо-MOUH4={g41,g42,-.-,g4ri}, где w-число модулей.
Исследование механизмов генетического поиска
Для проведения исследований были синтезированы тестовые примеры - Ех.1 на 30 блоков, Ех.2 - 40, Ех.З - 60, Ех.4 - 90, Ех.5 - 110.
Исследование генетического алгоритма направлено на то, чтобы обеспечить возможность получения ответов на вопросы прикладного характера, например: a) какое значение вероятностей мутации и кроссинговера Рм и Рк обеспечивает наилучшее решение; b) какое число поколений (размер генерации) Т достаточно для получения качественного решения; c) какое количество членов популяции обеспечивает наилучшие условия для организации генетического поиска.
Для нахождения наилучшего сочетания таких параметров как вероятности мутации и кроссинговера Рм и Рк , размер популяции М и число генераций Т, а также для выбора последовательности и типа генетических операторов экспериментальные исследования проводились следующим образом. Для каждой структуры сначала фиксировался параметр Рк и изменялись параметры Рм, М. М принимал значения - 20, 40, 50, 100. Рм принимал значения - 1.0, 0.8, 0.6, 0.4, 0.2. Затем фиксировался параметр Рм Рк принимал значения - 0.1, 0.2, 0.3, 0.4, 0.5. Проводилась серия из 10 экспериментов для каждого фиксированного набора параметров. В каждом эксперименте фиксировалось число итераций, после которого не наблюдалось улучшения решения и оценка решения. В таблице 4.1 и таблице 4.2 приведены экспериментальные результаты для первого примера. В таблице 4.1 для фиксированного значения Рк = 0.4. В таблице 4.2 для фиксированного значения Рм = 0.2. В таблице 4.3 и таблице 4.4 приведены экспериментальные исследования для второго примера.
При проведении испытаний для каждого эксперимента фиксировался номер генерации, после которой не наблюдалось улучшения оценки. В каждой серии из 10 испытаний определялись минимальный и максимальный номера генерации, которые отражены в таблице в колонках "Min" и "Мах". Кроме этого рассчитывалось среднее значение числа генераций (колонка "Среднее") после которого не наблюдалось улучшения оценки решения. Для каждой серии испытаний определялось лучшее решение, которое фактически являлось оптимальным. Затем фиксировалось число испытаний в серии, при которых было получено оптимальное решение (колонка " Оптим "), число испытаний, при которых решение отличалось от оптимального менее, чем на 5% (колонка " 5%") и число испытаний, при которых решение отличалось от оптимального более, чем на 5% (колонка " 5%"). В результате анализа результатов было установлено, что наилучшее сочетание Рм и Рк - Рм = 0.2; Рк = 0.4.
Эксперименты показали, что увеличение популяции М больше 150 нецелесообразно, т.к. это не приведет к заметному изменению качества. На рис. 4.1 для второго примера показана усредненная зависимость качества решения от числа генераций при значениях параметров Рм = 0.2 , Рк =0.4, М = 50. Из графика видно, что на 150 генерации достигается решение близкое к оптимальному.
Для исследования влияния размера и типа задачи на качество решения проводились исследования, показанные на рис. 4.2. Исследования проводились при значениях параметров Рм= 0.2 , Рк =0.4, М = 50.
Здесь горизонтальные уровни соответствуют номеру примера. По горизонтали для каждого эксперимента отложено число генераций. На уровнях кружочек соответствует одному испытанию и размещен он в том месте, которое соответствует числу генераций, при котором было получено лучшее решение. Как видно из диаграммы, с ростом сложности примера, растет диапазон числа генераций, при котором находится лучшее решение, а в общем растет число генераций, необходимое для получения качественного решения.
Результаты исследований генетического алгоритма планирования кристалла СБИС показывают, что для поиска оптимальных решений, близких к оптимальным, необходимо не более 150 поколений.
