Содержание к диссертации
Введение
1 Анализ и исследование математических моделей и методов решения задачи размещения при проектировании эва на основе сбис 12
1.1 Развитие полузаказных матричных сбис 12
1.2 Иерархический подход 13
1.3 Этапы проектирования эв а 14
1.4 Анализ математических моделей схем для задачи размещения 17
1.5 Классификация критериев задачи размещения 25
1.6 Анализ методов решения задачи размещения
1.6.1 Классификация традиционных методов размещения 30
1.6.2 Метод имитации отжига 38
1.6.3 Метод имитации эволюции 41
1.6.4 Анализ достоинств и недостатков методов размещения 42
1.7 Выводы и рекомендации 45
2 Теоретические исследования факторов, влияющих на качество алгоритма размещения блоков эва 46
2.1 Анализ современного уровня проектирования интегральных схем 46
2.2 Процедура сжатия обрабатываемой информации 50
2.3 Выбор способа распределения блоков по макробластям 52
2.4 Основные понятия и термины генетических алгоритмов 56
2.5 Символьная модель задачи оптимизации 57
2.6 Функция степени приспособленности 59
2.7 Цель эволюции популяции в процессе естественного отбора 60
2.8 Оценка генетического разнообразия популяции 61
2.9 Способы создания стартовой популяции
2.10 Классификация способов образования новых особей 65
2.11 Системы скрещивания особей 69
2.12 Классификация стратегий отбора 74
2.13 Общие требования к алгоритму размещения 80
2.14 Процедура размещения макрообластей 81
2.15 Процедура размещения элементов макрообластей 82
2.16 Анализ этапа макроэволюции 85
2.17 Выбор структуры локальной сети 87
2.18 Выбор операционной системы 89
2.19 Структура поиска решения задачи размещения 91
2.20 Выводы и рекомендации 93
3 Разработка генетического алгоритма параллельного размещения 94
3.1 Анализ этапов размещения 94
3.2 Разработка механизма обмена данными в локальной вычислительной сети
3.2.1 Механизм, реализующий искусственный отбор 97
3.2.2 Механизм, реализующий естественный отбор 98
3.2.3 Обмен данными на этапе макроэволюции 99
3.3 Разработка генетического алгоритма распределения блоков эва по макрообластям 102
3.3.1 Входные данные 102
3.3.2 Начальное назначение элементов макрообластей 102
3.3.3 Выбор кандидатов для очередного этапа скрещивания 104
3.3.4 Оператор кроссинговера 106
3.3.5 Оператор мутации 107
3.3.6 Вычисление значения целевой функции 108
3.3.7 Критерий завершения процесса. 109
3.3.8 Выходные данные п0
3.4 Разработка генетического алгоритма размещения макрообластей п0
3.4.1 Входные данные 110
3.4.2 Начальное размещение макрообластей 111
3.4.3 Выбор кандидатов для очередного этапа скрещивания 112
3.4.4 Операторы кроссинговера и мутации 112
3.4.5 Вычисление значения целевой функции 112
3.4.6 Критерий завершения процесса 113
3.4.7 Выходные данные 114
3.5 Разработка генетического алгоритма окончатель ного размещения (этап макроэволюции) 114
3.5.1 Входные данные 114
3.5.2 Создание популяции для этапа макроэволюции 115
3.5.3 Операторы кроссинговера и мутации 117
3.5.4 Вычисление 3начения целевой функции 117
3.5.5 Выбор кандидатов для очередного этапа скрещивания 117
3.5.6 Обмен решениями с процессами близнецами 118
3.5.7 Критерий завершения процесса 118
3.5.8 Выходные данные
3.6 оценка результатов проектирования 119
3.7 Выводы и рекомендации 120
4 Экспериментальные исследования разработан ного алгоритма 121
4.1 Цель экспериментального исследования 121
4.2 Определение зависимости качества решения от размера популяции 122
4.3 Определение параметров для этапа размещения 136
4.4 Определение параметров миграции 137
4.5 Определение временной сложности алгоритма 140
4.6 Выводы и рекомендации 144
Заключение 146
Литература
- Анализ математических моделей схем для задачи размещения
- Выбор способа распределения блоков по макробластям
- Механизм, реализующий искусственный отбор
- Определение параметров для этапа размещения
Анализ математических моделей схем для задачи размещения
В данной главе рассматриваются основные алгоритмы решения задачи размещения элементов. Такие задачи относятся к классу NP-полных задач. Современный уровень математического аппарата не способен преодолеть проблемы NP-полных задач, а именно, невозможно построить точный полиномиальный алгоритм NP-полной задачи. В настоящее время оптимальное решение NP-полных задач можно найти только путём полного перебора возможных решений и затратить при этом экспоненциальное время. Поэтому рассматриваются только методы нахождения приближённых решений [17,26,48,113].
Всю совокупность алгоритмов размещения можно классифицировать исходя из различных признаков. Исходя из принципа решения задачи размещения, можно выделить две основные группы методов: непрерывно-дискретные и дискретные.
При использовании непрерывно-дискретных методов оптимизация задачи размещения решается в два этапа: на первом определяют координаты местоположения центров элементов, при которых целевая функция имеет экстремальное значение; на втором полученные координаты «округляются» до фиксированных целочисленных значений координатной сетки, нанесённой на поверхность коммутационного поля (КП). К этим методам относятся следующие алгоритмы: основанные на построении динамических моделей; градиентные методы; методы последовательного сдвига. В методах последовательного сдвига оптимальное положение элемента определяют не перебором приращения целевой функции, а аналитически. Например, выполняется последовательный сдвиг каждого из элементов в положении, где сила, действующая на него со стороны других элементом минимальна. Эти методы относятся к классу итерационных алгоритмов. Временная сложность алгоритма составляет Офп )-0(рп ).
В дискретных методах оптимизации модель КП представляют в виде множества фиксированных координат позиций. Задача размещения сводится к сравнению различных вариантов закрепления элементов в узлах координатной сетки, и выбору того из них, который обеспечивает экстремальное значение целевой функции.
Методы решения задачи размещения можно разделить на следующие три основные группы: конструктивные, итерационные и реализующие математические или физические аналоги.
В первой группе алгоритмов, называемых конструктивными, различают методы с первоначальным размещением и без него. Конструктивные методы с первоначальным размещением заключаются в следующем. Первоначально задаётся или выбирается по определённым правилам подмножество размещённых элементов (так называемое ядро). Далее анализируется подмножество неразмещённых элементов. Из этого подмножества выбирается один элемент, соответствующий наилучшему размещению по заданному критерию. Например, для алгоритма последовательного размещения по связанности выбор очередного элемента основывается на определении меры связанности каждого элемента из оставшихся элементов с уже размещёнными и поиска элемента с максимальным значением связанности. Выбор позиции для элемента проводится согласно используемым критериям оптимальности размещения. Затем процесс повторяется итерационно до полного размещения всех элементов. После размещения элементов на посадочных местах они более не перемещаются. В конструктивных методах без первоначального размещения ядро выбирается на основе различных эвристических приёмов.
Конструктивные методы очень просты, требуют небольших затрат машинного времени, находят широкое практическое применение. При большом числе элементов ВС А имеет вид 0(рп)-0(Рп2). Алгоритмы такого типа просты в реализации, обладают низкой вычислительной сложностью, но отличаются сравнительно невысоким качеством получаемого решения. Тем не менее, они часто применяются при проектировании, предваряя более эффективные алгоритмы. к конструктивным алгоритмам относятся алгоритмы:
Метод последовательного размещения по связности на каждом шаге выбирает один из неразмещённых элементов и помещает в одну из свободных позиций. Последующий выбор элементов основан на анализе связности оставшихся элементов с размещёнными. Структура дальнейшей стратегии основана на заданных правилах выбора очередного элемента. Временная сложность алгоритма равна Офп).
Метод связывания пар начинает поиск с выбора пары элементов, имеющих, например, наибольшую сумму общих связей. Далее происходит последовательное подсоединение элементов с выполнением первоначально введённого правила до полного размещения всех элементов. Временная сложность алгоритма равна 0(Рп).
Метод расширения ядра для каждого неразмещенного элемента определяет среднее суммарное число ожидаемых связей с размещёнными элементами на основе анализа покрывающих деревьев. Для размещения выбирается элемент с наибольшим значением и располагается во взвешенном центре тяжести групп уже размещённых элементов. Далее процесс продолжается итеративно. Временная сложность алгоритма равна 0((3п).
В матричных методах выбор элемента и позиции для него на г-м шаге выполняется по специальной матрице размещения B=bjj, каждый элемент которой соответствует «цене назначения» элемента х, в позицию pj при условии, что (г-1) элементов уже размещено. Структура алгоритма основана на различных способах определения «цен назначения» и методиках выбора. Временная сложность алгоритма равна 0((3п)-0((3п2).
Выбор способа распределения блоков по макробластям
Методы первой группы обеспечивают точное решение, но из-за их сложности и больших затрат машинного времени они не нашли широкого практического применения. Методы второй, третьей и четвёртой группы являются приближёнными и приводят к получению решения с заданной точностью,
Последовательные методы, например, последовательного размешения по связности, получают тем или иным методом один вариант компоновки и прекращают свою работу. Достоинство этих алгоритмов заключается в простоте реализации и высокой скорости получения результата. Недостаток этих алгоритмов в том, что полученный вариант компоновки будет далёк от оптимального.
К итерационным методам относятся такие методы, как метод парных перестановок, метод групповых перестановок, метод имитации эволюции, метод ветвей и границ. Все эти методы характеризует то, что они последовательно улучшают уже существующее решение и требуют для своей работы наличие целевой функции.
На практике обычно применяются смешанные методы, получающие начальное значение последовательным методом, а затем итерационно его улучшающие. Наиболее сильное развитие в современных исследованиях получили генетические алгоритмы, которые гарантированно позволяют получить решение с требуемым значением целевой функции. Поскольку, как было указано выше, временная сложность генетических алгоритмов ниже, чем у остальных (что важно для задач компоновки с количеством элементов, достигающим 10 ), то на этапе компоновки элементов в кластера будет использоваться метод имитации эволюции.
Алгоритмы имитации эволюции, или генетические алгоритмы являются мощным способом решения оптимизационных задач. Базовая схема генетического алгоритма состоит в следующем. Каждое решение оптимизационной задачи кодируется строкой (или несколькими строками), называемой хромосомой. В дальнейшем, такое решение рассматривается как индивид, живущий и развивающийся в популяции - сообществе себе подобных. Каждому индивиду популяции присваивается значение фитнесс в соответствии со значением критерия оптимизации решаемой задачи (целевой функции) [32, 99, 67, 116].
Случайным образом или целенаправленно создаётся начальная популяция или стартовое множество решений, которое в дальнейшем развивается по законам эволюционной теории Дарвина. Новые индивиды в популяции формируются либо путём скрещивания двух особей (оператор кроссинговера), либо мутагенным изменением хромосомы одной особи (оператор мутации). Для повышения фитнесса вновь получаемых особей вводят различные схемы отбора более качественных особей для скрещивания (схемы селекции). После репродукции новых членов популяции производится уменьшение популяции до её прежних размеров с помощью механизма естественного отбора или выживания сильнейшего. Производится отсев менее качественных особей. Далее вся процедура повторяется на новом витке эволюции. Процесс заканчивается когда достигнута заданная точность т.е. за последние несколько итераций сумма изменений качества лучших особей меньше заданной точности Процесс может также остановиться после заданного количества шагов эволюции
Принципиальных отличием ГА является то, что поиск осуществляется не из единственной точки, а из множества решений, и анализируются одновременно различные области пространства решений. ГА более приспособлены к нахождению областей с лучшими значениями критерия качества за счёт объединения субоптимальных решений из различных подобластей.
При создании символьной модели задачи требуется каждое решение представить в виде хромосомы - строки символов. Необходимо отметить, что выбор символьной модели оптимизационной задачи во многом определяет эффективность применения генетического алгоритма и качество получаемого решения. Для каждого класса комбинаторных задач должна строиться своя символьная модель, отражающая специфику и особенности решаемой задачи. На быстродействие генетических алгоритмов сильное влияние оказывает длина хромосомы, кодирующей решение.
Генетические алгоритмы быстро получают качественное решение, но обладают тем недостатком, что требуют для работы большого объёма памяти, поскольку работают не с одним решением, а с популяцией. При бинарном кодировании для задачи с размером хромосомы п потребуется объём памяти для входной информации равный nv, где v - размер популяции. В том случае, если в генетическом алгоритме используется идея макроэволюции, то требуемый объём памяти увеличивается и равен Kp-n-v, где Кр - количество одновременно развивающихся популяций. В этом случае сокращение длины кодирующей хромосомы было бы особенно актуально. Среди шести принципов создания эффективной символьной модели решений фигурирует принцип минимальной избыточности: каждый элемент области поиска должен быть представлен минимальным (идеально - одной) количеством генов, чтобы сократить размер области поиска ГА [11, 99].
Механизм, реализующий искусственный отбор
В начале работы алгоритма счётчик итераций устанавливается в какое-то, заранее большее, чем требуемое, число. Далее каждый цикл происходит уменьшение значения счётчика на единицу. Выход из процедуры компоновки осуществляется или по достижению условия, что минимум и максимум целевой функции отличается не более чем на пять процентов, или же по достижению счётчиком итераций значения нуля.
Выходными данными этапа компоновки являются набор заполненных кластеров и сокращённая квадратная матрица связности, индивидуальные для каждого узла вычислительной сети.
Ко времени начала работы непосредственно процедуры размещения кластеризованных элементов на каждом узле сети уже произошла процедура компоновки. Причём поскольку размер кластера на каждом узле сети варьируется, то и размер стринга будет разным на каждом узле сети. Как следствие - время работы подпрограммы размещения кластеров будет различным. Кроме этого, в работе программ на разных узлах нет никаких различий.
Размещение кластеров является вторым глобальным этапом генетического параллельного алгоритма размещения элементов СБИС. Предшествующий ему этап компоновки подготавливает обширную структуру хромосомы к текущему этапу, сворачивая её и компонуя кластера оптимальным образом. Входными данными для этапа начального размещения является набор кластеров, сформированных по принципу максимальной концентрации связей внутри кластера, и матриц связности кластеров.
При выборе стратегии начального размещения необходимо руководствоваться принципом создания популяции с большим генофондом и высоким значением целевой функции, усреднённой по всей популяции. С этой целью для получения начальной популяции следует, действуя по стратегии комбинирования стратегий фокусировки и дробовика, применить алгоритм последовательного размещения по связности. Причём необходимо ввести в алгоритм некоторые случайные параметры для обеспечения необходимого разнообразия генофонда. Для этой цели необходимо и достаточно для выбора очередного размещаемого кластера использовать процедуру рулетки, где в качестве критерия ширины зоны использовать степень связности размещаемого элемента с уже размещёнными.
В качестве целевой функции используется критерий уменьшения суммы полупериметров описывающих прямоугольников всех цепей схемы. Этот критерий является наиболее универсальным, поскольку косвенно включает в себя остальные метрические критерии. Вместе с тем, вычисление этого критерия является вычислительно наименее сложной операцией по сравнению с другими вариантами целевой функции, что является важным для сетевых задач, которые могут препятствовать выполнению друг друга. Упрощение же вычисления значения фитнесса позволяет уменьшить время выполнения отдельной процедуры и разгрузить вычислительную сеть. Таким образом, формула вычисления значения целевой функции будет выглядеть:
В формуле (3.7) предлагается вместо полупериметров использовать значение полных периметров, что позволяет уйти от использования значений целевой функции с плавающей запятой. Использование только целочисленной арифметики позволяет значительно сократить объём и сроки вычислений, что также позволяет разгрузить центральные процессоры узлов вычислительной сети.
В отличие от процесса компоновки, когда только два критерия завершения процесса подходят для применения в процедуре, в процессе размещения необходимо учесть также критерий системного времени, прошедшего с момента начала работы программы. Критерий прошедшего времени необходим для того, что бы все процессы сети имели возможность участвовать в этапе макроэволюции.
В начале работы алгоритма счётчик итераций устанавливается в какое-то, заранее большее, чем требуемое, число. Максимальное время, отведённое на этап компоновки, заранее выбирается достаточно большим и может быть изменено для отдельных узлов сети на этапе отладки программного комплекса. Далее каждый цикл происходит уменьшение значения счётчика на единицу. Выход из процедуры компоновки осуществляется или по достижению условия, что минимум и максимум целевой функции отличается не более чем на пять процентов, или по достижению счётчиком итераций значения нуля, или же по истечению временного интервала
Определение параметров для этапа размещения
Для проверки статистической гипотезы необходимо произвести аппроксимацию полученной функцией других наборов данных [27]. На рисунках 4.2, 4.3, 4.4 и 4.5 представлены графики для наборов данных при 200, 300, 400 и 500 размещаемых элементов, аппроксимированные функцией 4.2. Полученные графики указывают на отсутствие опровержений выбранной гипотезы. Таким образом, будем считать, что на рассмотренном интервале значений размера популяции целевая функция является случайной величиной, математическое ожидание которой является функцией от размера популяции и имеет вид: Р=т-(\-Ших), (4.2) где X - размер популяции; ш - значение целевой функции при некоторой идеальной компоновке
В результате проведённых экспериментов была получена зависимость между ожидаемым значением целевой функции и размером популяции. Исследуем полученную зависимость. С некоторой вероятностью значение целевой функции будет асимптотически приближаться к идеальному значению по мере увеличения концентрации нужных генов в популяции и отмирании "вредных" генов. Возрастание значения целевой функции ожидается по зависимости (1//« х) и будет значительным в начале координатной оси. По мере увеличения размера популяции значение целевой функции будет возрастать, но скорость роста функции будет падать.
Оценим размер популяции, необходимый для получения решения заданного качества. Определим размер популяции, необходимый для преодоления целевой функцией 50 %-го порога от т : Р 0,5FHa. Для этой цели необходимо решить неравенство вида:
Поскольку ось абсцисс измеряется в п (количество размещаемых элементов), то для преодоления целевой функцией 50%-го порога размер популяции должен превышать е\ = 7,29 п. Поскольку скорость роста целевой функции значительна, пока размер популяции не достигает 10п, и падает после этого, то предлагается выбирать размер популяции равный 10п, где п -количество размещаемых элементов. Таким образом обеспечивается возможность быстрого достижения целевой функцией значения, близкого к оптимальному.
Среднее значение целевой функции на этапе компоновки является функцией от размера популяции. Полученная функция на исследованном участке выражает обратную зависимость от натурального логарифма. Появление глобальной константы е можно объяснить тем, сто предложенный алгоритм является моделированием естественного природного процесса, большинство же естественных процессов развивается экспоненциально. Следовательно, можно сделать предположение, что и на этапе размещения кластеров значение целевой функции будет показывать ту же зависимость, поскольку здесь также используется генетический алгоритм; разница заключается в методе вычисления целевой функции и способе расшифровки хромосомы.
Экспериментальные данные, приведённые в табл. 4.6 и 4.7 показывают на отсутствие опровержения высказанной гипотезе. Графики полученных зависимостей приведены нарис. 4.6, 4.7. Миграционный процесс является параллельным основному эволюционному процессу популяции и предназначен для обмена вариантами размещения между различными узлами локальной вычислительной сети на этапе макроэволюции. Особи-эмигранты выбираются случайным образом на основе механизма моделирования стола рулетки после определения особей-родителей на текущем щаге эволюции. Таким образом, реализуется механизм миграции, когда особь с высокими потенциальными возможностями, но низкой степенью приспособленности к конкретной среде обитания пытается реализоваться в других популяциях данного вида.
Разработанный алгоритм состоит из пяти глобальных этапов (см. Рис.2.6). Первый этап (блок 2) заключается в формировании кластеров, путём анализа геометрических размеров коммутационного поля и определения геометрических размеров и пространственной ориентации кластера. Данный этап имеет временную сложность порядка 0(п).
Второй этап (блок 3) заключается в заполнении кластеров элементами и выполняется генетической процедурой компоновки. Известно, что временная сложность данного метода оценивается 0(п3) [61].
Bo время экспериментальных исследований для задачи размещения элементов необходимо установить зависимость времени решения задачи от количества размещаемых элементов, т.е. необходимо определить зависимость типа у= f(x).
В целях получения экспериментальных данных о работе комплекса программ в целом было произведено размещения на регулярных полях размером 6x10=60, 9x10=90, 12x10=120, 15x10=150 и 12x15=180 посадочных мест. Размещение производилось в локальной вычислительной сети из трёх вычислительных машин с процессорами Intel Pentium III с тактовой частотой 667 МГц. Размеры кластера варьировались как 2x2, 2x3 и 3x2. Этап компоновки производился из расчёта размера популяции 600, 900, 1200, 1500 и 1800 особей соответственно. Окончательное размещение элементов производилось из расчёта размера миграции 4 6 8 10и12 особей
