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

Размещено на http://www.allbest.ru/

ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ ЗАДАЧ СИНТЕЗА АРХИТЕКТУР ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ И ПЛАНИРОВАНИЯ ВЫЧИСЛЕНИЙ

Кольдичева Т.А.

Annotation

The article is devoted to the implementation of genetic algorithms within the tasks of syntheses of the computing system architectures and planning of the parallel calculations. There are running time requirements of the applied program and number of processors in computing system for this class of the tasks. The main problems of syntheses of the computing system architectures and planning of parallel calculations, and their solution are described in detail.

Основная часть

Задачи, решаемые при синтезе архитектур вычислительных систем (ВС) и планировании параллельных вычислений в общей постановке являются NP полными. В связи с этим для практического их решения используются эвристические методы. К одним из таких методов относятся генетические алгоритмы. Идея генетических алгоритмов заимствована у живой природы и состоит в организации эволюционного процесса, конечной целью которого является получение оптимального решения в сложной комбинаторной задаче. Разработчик генетических алгоритмов выступает в данном случае как "создатель", который должен правильно установить законы эволюции, чтобы достичь желаемой цели как можно быстрее. Впервые эти нестандартные идеи были применены к решению оптимизационных задач в середине 70-х годов. Примерно через десять лет появились первые теоретические обоснования этого подхода. На сегодняшний день генетические алгоритмы доказали свою конкурентоспособность при решении многих NP-трудных задач. Их применение очень часто оправдано, когда детерминированные методы или более простые стохастические методы не позволяют получать приемлемые по качеству и сложности нахождения решения.

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

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

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

1) не зависит от времени,

2) целевая функция для каждого варианта решения задачи может быть вычислена независимо от других вариантов решения задачи,

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

4) не является регулярной и имеет большое число локальных минимумов и максимумов,

5) имеет точки разрыва по осям “порядка” и “привязки”, они обусловлены недопустимыми вариантами решения задачи, например, нарушение частичного порядка на множестве процессов прикладной программы,

6) имеет не один, а некоторое множество оптимумов.

Сложность получения дополнительных данных о свойствах 4-6 имеет один порядок со сложностью получения оптимальных решений. То есть задачи синтеза структур ВС и планирования вычислений должны решаться при отсутствии каких-либо априорных данных о свойствах 4-6 пространства решений.

Детерминированные методы или более простые стохастические методы очень часто не позволяют найти оптимальное решение или достаточно близкое к нему для задач большого размера с подобными пространствами решений. Для решения таких задач, как показывает практика, успешно могут быть использованы генетические методы [1]. Вычислительная сложность генетических методов при увеличении размера и размерности задачи растет медленнее, чем для большинства детерминированных методов. Однако генетические методы представляют собой скорее некоторую методику, чем единый алгоритм. Для успешного решения (по сложности и качеству) конкретного класса задач они требуют “содержательного” наполнения. При их использовании для синтеза архитектур и планирования параллельных вычислений возникает ряд нетривиальных проблем, решение которых, определяет эффективность применения генетических алгоритмов. К основным проблемам можно отнести:

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

§ настройку основных операций генетического алгоритма;

§ возможность обнаружения и исключения/коррекции недопустимых вариантов решения;

§ настройку критерия выживаемости и критерия останова;

§ уменьшение сложности операции мутации из-за большой длины битовой строки;

§ выбор начальной популяции;

§ выбор объема популяции.

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

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

Кроссовер (скрещивание) - заключается в передаче участков генов от родителей к потомкам. Кроссовер может быть одноточечный или многоточечный.

Мутации - выполняются с определенной вероятностью: происходит замена аллеля (значения гена) случайным значением, выбираемым с равной вероятностью в области определения гена.

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

На рисунке показана укрупненная схема генетического алгоритма; схема алгоритма, разработанного для решения данной задачи, аналогична.

Рисунок 1 Укрупненная схема генетического алгоритма

алгоритм вычислительный система холланд

Рассмотрим использование для синтеза структуры ВС реального времени алгоритм, базирующийся на алгоритме, предложенном Холландом [2], основные принципы которого рассмотрены выше.

Определим следующую постановку задачи.

Пусть заданы:

§ прикладная программа в виде наиболее сложной истории ее поведения [3] - частично-упорядоченное множество рабочих интервалов/процессов, составляющих историю;

§ директивный срок ее выполнения;

требуется определить:

§ число процессоров в ВС,

§ привязку процессов, составляющих программу, к процессорам ВС в форме упорядоченных списков процессов;

§ интенсивность межпроцессорного взаимодействия в форме матрицы интенсивности обменов между процессорами или временной диаграммы обменов;

при этом должны выполняться условия:

§ время выполнения алгоритма не должно превышать директивный срок;

§ число процессоров в ВС должно быть минимально необходимым для выполнения предыдущего условия.

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

Алгоритм синтеза ( )

[

задание начальной популяции;

вычисление критерия выживаемости,

пока не достигнут критерий останова;

[

селекция;

скрещивание;

мутация;

вычисление критерия выживаемости;

]

]

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

<битовая строка> (U<битовое поле процесса>)

<битовое поле процесса> (<номер процессора> U <приоритет процесса>)

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

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

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

Селекция. В алгоритме синтеза используются комбинации схемы пропорциональной селекции и схемы рулетки [5]. Для вычисления целого числа потомков используется схема пропорциональной селекции, а для распределения остатка - схема рулетки.

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

Мутация. В связи с большим объёмом битовой строки была модифицирована операция мутации. Вместо вызова генератора случайных чисел для каждого бита вычисляется случайным образом расстояние между инвертируемыми битами.

Статистическое исследование алгоритма проводилось на графах прикладных программ, представляющих собой: 1) набор процессов с произвольными информационными связями (сгенерированными случайным образом) - нет никаких ограничений на число входных/выходных дуг; 2) набор независимых процессов; 3) набор цепочек процессов - каждая вершина имеет не более одной входной и выходной дуги; 4) входящее дерево - каждая вершина имеет не более одной выходной дуги, число входных дуг не ограничено; 5) выходящее дерево - каждая вершина имеет не более одной входной дуги, число выходных дуг не ограничено; 6) граф адаптивных методов цифровой обработки сигналов.

Число вершин в графах изменялось от 15 до 300. Разброс времен выполнения процессов относительно среднего времени изменялся в пределах: 1)050%; 2)50100%; 3)100200%.

В качестве начальной популяции во всех тестах задавались два варианта распределения процессов по процессорам:

- все процессы выполняются на одном процессоре,

- каждый процесс выполняется на своем процессоре.

Число битовых строк в начальной популяции с этими вариантами распределения составляло по 50%.

Статистические испытания показали, что параметры разработанного алгоритма синтеза структур ВС могут быть настроены универсальным образом на характеристики графа прикладной программы. При этом достигаются приемлемые сложность нахождения и качество решения. Оптимальное решение или достаточно близкое к нему находится за 50500 итераций алгоритма. Наибольшее влияние на сложность получения и качество решения оказывают вероятность мутации и весовые коэффициенты (C₁ и C₂) в критерии выживаемости. Оптимальные параметры алгоритма находятся в пределах:

§ размер популяции 25

§ вероятность мутации 0.00750.0095

§ вероятность скрещивания 0.30.5

§ весовые коэффициенты (С₁) 0.30.5

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

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

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

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

Минимально возможное время выполнения прикладной программы определяется критическим путем в графе программы. При ограниченной арности вершин критический путь может быть найден за полиномиальное число шагов.

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

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

§ ограничением при кодировке длины первого поля (<номер процессора>) в соответствии с заданным числом процессоров;

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

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

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

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

Литература

1. Обозрение прикладной математики. Серия “Методы оптимизации”. Эволюционные вычисления и генетические алгоритмы., Т.3, выпуск 5. - 1996.

2. Holland J.N. Adaptation in Natural and Artificial Systems. Ann Arbor, Michigan: Univ. Michigan Press, 1975.

3. Смелянский Р.Л. Модель функционирования распределённых вычислительных систем// Вестник МГУ, сер.15, Вычислительная математика и кибернетика. - 1990., №3.

4. Васильев В.И. Интеллектуальные системы управления с использованием генетических алгоритмов» / В.И. Васильев, Б.Г. Ильясов // Приложение к журналу «Информационные технологии» №12, 2000, Изд-во «Машиностроение», «Информационные технологии».

5. Основы генетического программирования http://trubchaninoff.narod.ru/ job.htm

Размещено на Allbest.ru