Содержание к диссертации
Введение
Глава 1. Постановка и многокритериальная математическая модель задачи распределения заданий в мультипроцессорной системе 19
1.1. Постановка задачи 19
1.2. Анализ критериев оптимизации распределения выполнения заданий в мультипроцессорной системе 20
1.2. Математическая модель задачи 26
1.3. Обзор методов решения задачи многокритериальной оптимизации .28
Выводы 31
Глава 2. Методы решения задачи на основе дискретной и соответствующей нейросетевой математических моделей 32
2.1. Метод решения на основе детерминированной асинхронной дискретной сети Хопфилда 33
2.2. Метод имитации отжига 41
2.3. Метод имитации отжига на основе стохастической асинхронной дискретной сети Хопфилда 46
2.4. Комбинированный метод 48
2.5. Оценка трудоемкости алгоритмов 50
2.6. Экспериментальное исследование алгоритмов 54
2.6.1. Исследование параметров метода имитации отжига 54
2.6.2. Сравнение алгоритмов решения задачи 65
Выводы 71
Глава 3. Методы решения задачи на основе непрерывной и соответствующей нейросетевой математических моделей 73
3.1. Непрерывная математическая модель 73
3.2. Методы решения задач непрерывной оптимизации 73
3.2.1. Метод Флетчера-Ривса 76
3.2.2. Нейросетевой метод 85
3.3. Экспериментальное исследование разработанных алгоритмов 96
3.3.1. Исследование параметров алгоритма Флетчера-Ривса 96
3.3.2. Исследование параметров непрерывной сети Хопфилда 112
3.3.3. Сравнение разработанных алгоритмов решения задачи 115
Выводы 118
Глава 4. Описание программного комплекса «оптимизация распределения заданий в мультипроцессорной системе» 120
4.1. Структура программного комплекса 120
4.3. Руководство пользователя 123
Выводы 131
Заключение 132
Список литературы 133
Приложение! 142
- Анализ критериев оптимизации распределения выполнения заданий в мультипроцессорной системе
- Метод имитации отжига на основе стохастической асинхронной дискретной сети Хопфилда
- Методы решения задач непрерывной оптимизации
- Экспериментальное исследование разработанных алгоритмов
Введение к работе
Актуальность проблемы. В корпоративных автоматизированных системах организационного управления различных государственных структур, характеризующихся большим количеством пользователей, необходимо решать множество задач обработки информации. Очевидно, что от скорости обработки информации во многом зависит оперативность принятия управленческих и финансовых решений. Однако быстродействия одного компьютера недостаточно для массового обслуживания задач пользователей.
Современные тенденции увеличения производительности компьютеров связаны с распараллеливанием вычислительных процессов: появились многоядерные процессоры и высокопроизводительные кластерные системы -модульные мультипроцессорные системы, созданные на базе стандартных вычислительных узлов, соединенных высокоскоростной коммуникационной средой [43, 70]. Эффективность работы кластерной системы зависит от правильного распределения выполнения заданий по вычислительным узлам. Поэтому актуальными в настоящее время являются задачи эффективного использования мультипроцессорных систем в автоматизированных системах организационного управления и распределения в них заданий.
Постановка задачи распределения и упорядочения заданий в мультипроцессорной системе является хорошо известной в теории расписаний и рассматривается в работах Конвея Р.В., Максвелла В.Л., Миллера Л.В., Танаева B.C., Шкурбы В.В., Левина В.И. и других [26, 46, 52, 74, 78]. Многие задачи распределения являются NP-полными, что не позволяет эффективно решать их точными методами, поэтому необходимо разрабатывать алгоритмы на основе приближенных методов [51]. Появление искусственных нейронных сетей как математического инструментария распараллеливания вычислений делают актуальной задачу разработки
5 нейросетевых математических моделей, методов и алгоритмов оптимального распределения заданий в мультипроцессорной системе.
Цель и задачи исследования. Целью диссертационной работы является разработка нейросетевых математических моделей, методов и алгоритмов решения задачи оптимального распределения заданий в мультипроцессорной системе.
Для достижения поставленной цели необходимо решить следующие научные задачи:
Исследовать вычислительную сложность задачи распределения заданий в мультипроцессорной системе с разными критериями оптимизации;
Разработать нейросетевые дискретную и непрерывную математические модели распределения заданий в мультипроцессорной системе;
Разработать нейросетевые алгоритмы решения задачи распределения, исследовать параметры алгоритмов и выработать рекомендации по их определению;
Разработать программный комплекс, реализующий разработанные алгоритмы решения задачи распределения заданий в мультипроцессорной системе;
Провести численные эксперименты для сравнительного анализа классических и разработанных алгоритмов с помощью разработанного программного комплекса.
Методы исследования. Для решения поставленных задач в работе использовались методы оптимизации, исследования операций, теории принятия решений, численных методов, теории обыкновенных дифференциальных уравнений, теории нейронных сетей, теории алгоритмов, математического анализа.
Научная новизна. В диссертационной работе получены следующие новые научные результаты:
Сформулирована и доказана теорема, обосновывающая Л/Р-полноту задачи распределения заданий в мультипроцессорной системе с равномерной загрузкой компьютеров;
Построена двухкритериальная модель булевой оптимизации распределения заданий в мультипроцессорной системе, и на ее основе разработаны однокритериальные дискретная, непрерывная и нейросетевые модели;
Предложен метод решения дискретной задачи распределения заданий, сочетающий метод имитации отжига, детерминированную и стохастическую асинхронные дискретные сети Хопфилда;
Разработаны алгоритм определения начальной температуры для методов имитации отжига, выражения для вычисления временного шага и оценки временной константы нейронов алгоритма непрерывной нейронной сети Хопфилда.
Достоверность результатов работы. Основные положения диссертационной работы получены на основании достоверных знаний прикладной математики и использования строгого математического аппарата. Полученные теоретические результаты подтверждены вычислительными экспериментами, актами использования в деятельности государственных организаций и внедрения в учебный процесс.
Практическая ценность работы заключается в создании программного комплекса, реализующего разработанные алгоритмы и позволяющего решать задачу распределения заданий в мультипроцессорной системе.
Апробация работы. Основные результаты работы докладывались и обсуждались на следующих международных, всероссийских конференциях и семинарах: XII Международная молодежная научная конференция «Туполевские чтения» (Казань, 2004), XVI Международная научно-техническая конференция: «Математические методы и информационные технологии в экономике, социологии и образовании» (Пенза, 2005), VIII Международная научно-практическая конференция «Фундаментальные и
7 прикладные проблемы приборостроения, информатики и экономики» (Москва, 2005), IV Общероссийская конференция с международным участием «Новейшие технологические решения и оборудование» (Москва, 2006), Всероссийская научная конференция студентов и аспирантов (Вологда, 2007), XV Международная молодежная научная конференция «Туполевские чтения» (Казань, 2007), заочная электронная конференция «Фундаментальные и прикладные проблемы математики» (Рос. акад. естествознан., декабрь 2008).
Публикации. По теме диссертации опубликовано 10 научных работ, включая 2 статьи и 8 тезисов докладов.
Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка, одного приложения. Работа содержит 142 страницы машинописного текста, 36 рисунков и 24 таблицы. Список литературы включает 87 наименований.
Содержание работы.
Во введении содержится обоснование актуальности проблемы, основные научные положения и результаты.
Первая глава посвящена постановке задачи, анализу критериев оптимизации распределения заданий в мультипроцессорной системе, построению математической модели задачи многокритериальной оптимизации и обзору методов ее решения.
Рассматривается мультипроцессорная система, состоящая из і компыотеров различной производительности. Время xiz выполнения Z-TO
задания на /-м компьютере (i = l,;z = l,n) известно. Необходимо оптимальным образом распределить п заданий по компьютерам [26, 52, 78].
Оптимизацию распределения заданий можно осуществлять на основе различных критериев: минимизации «длины» расписания, среднего времени завершения выполнения заданий, разности между загруженностью компыотеров, суммарного времени работы компьютеров.
8 В работе был проведен анализ этих критериев с точки зрения вычислительной сложности рассматриваемой задачи. В литературе доказана NP -полнота задачи с критерием минимизации «длины» расписания и показано, что задача с критерием минимизации среднего времени завершения выполнения заданий сводится к задаче нахождения потока минимальной стоимости, для которой существует эффективный алгоритм
решения, сложность которого равна 0\N3J, где ./V -размерность задачи [78].
Для критерия минимизации разности между загруженностью компьютеров в диссертации сформулирована и доказана следующая теорема.
Теорема 1. Задача распределения заданий по компьютерам в соответствии с критерием минимизации разности между загруженностью компьютеров является NP -полной.
Задача с критерием минимизации суммарного времени работы компьютеров легко разрешима за полиномиальное время, поскольку оптимальному решению этой задачи будет соответствовать расписание, в котором каждое задание назначается на компьютер, который выполняет его максимально быстро. Составление расписаний только на основе этого критерия может привести к тому, что все задания будут назначаться на самый быстродействующий компьютер. А это приведет к простою остальных компьютеров.
Указанные недостатки двух последних критериев частично компенсируются за счет их совместного использования, поэтому при составлении расписаний целесообразно использовать оба критерия одновременно. Таким образом, мы получаем NP -полную задачу многокритериальной оптимизации.
Первый критерий и совокупность последних двух критериев ' обеспечивают достижение одних и тех же целей: максимальное использование всех имеющихся вычислительных ресурсов и минимизация времени решения задач мультипроцессорной системой. Однако задача распределения с критерием минимизации «длины» расписания ограничивает
9 методы решения методами дискретной оптимизации и методами нулевого порядка, требующими вычисления лишь значений целевой функции. Поэтому в данной работе в исследовательских целях использованы последние два критерия.
В диссертации построена математическая модель составления расписаний на основе критериев минимизации разности между загруженностью компьютеров и минимизации суммарного времени работы компьютеров.
Поскольку задача распределения заданий в мультипроцессорной системе относится к классу задач нелинейной булевой многокритериальной оптимизации, имеет место противоречивость критериев, связанная с невозможностью найти оптимальное решение задачи сразу по двум целевым функциям. Поэтому для таких задач необходимо искать компромиссное эффективное решение, учитывающее «важность» каждой целевой функции [30, 67, 76].
К основным методам решения задач многокритериальной оптимизации относятся метод аддитивной свертки целевых функций, метод уступок, метод минимизации отклонения от «идеальной точки». Недостатком метода аддитивной свертки является необходимость априорного задания весовых коэффициентов. Недостатками метода уступок являются необходимость априорного задания значений уступок и решения задач по каждой частной целевой функции, что может привести к существенному увеличению времени решения исходной задачи. Недостатком метода минимального отклонения от «идеальной точки» является необходимость решения задачи сначала по каждому критерию отдельно, а затем решения задачи с новой целевой функцией.
Таким образом, каждый из приведенных методов имеет свои недостатки, однако по скорости решения предпочтительно использовать метод аддитивной свертки, т.к. он требует однократного решения задачи при выбранных значениях весовых коэффициентов. Поэтому для решения
10 исходной задачи распределения заданий в мультипроцессорной системе применяется метод аддитивной свертки, в соответствии с которым исходная задача представляется как задача однокритериальной оптимизации.
Во второй главе исследован алгоритм метода имитации отжига для решения рассматриваемой задачи. Экспериментально исследованы параметры, влияющие на сходимость методов имитации отжига, предложен алгоритм вычисления начальной температуры, предложены и исследованы способы определения нового состояния из окрестности текущего состояния. Сформулирована нейросетевая дискретная модель задачи распределения заданий в мультипроцессорной системе и разработаны алгоритмы ее решения. Проведена оценка трудоемкости и сравнительный анализ разработанных алгоритмов.
Поскольку рассматриваемая задача является NP -полной, для ее решения используются приближенные методы дискретной оптимизации. Для решения задачи распределения заданий в мультипроцессорной системе приближенными дискретными методами был осуществлен переход от условной задачи к безусловной задаче оптимизации. Среди множества приближенных дискретных методов безусловной оптимизации для решения исходной задачи были выбраны следующие известные методы: метод имитации отжига [8], нейросетевой метод на основе детерминированной асинхронной дискретной сети Хопфилда (АДСХ) [60, 80], метод имитации отжига на основе стохастической асинхронной дискретной нейронной сети Хопфилда (САДСХ) [80]. Помимо известных методов предлагается и исследуется комбинированный метод, сочетающий детерминированную и стохастическую асинхронные дискретные сети Хопфилда и метод имитации отжига.
Алгоритм метода имитации отжига представляет собой алгоритмический аналог физического процесса управляемого охлаждения металлов. Суть алгоритма заключается в следующем. Процесс охлаждения начинается с некоторого начального состояния при начальной температуре
Гтах. В процессе работы алгоритма температура Т понижается с коэффициентом охлаждения скє(0,і). При каждой температуре предпринимается m попыток изменения состояния системы, которые могут привести к увеличению или уменьшению целевой функции. Если новое состояние системы обеспечивает уменьшение значения целевой функции, то такой переход системы принимается, в противном случае определяется вероятность этого перехода по формуле р = е~ , где AF - положительное приращение целевой функции. Процесс останавливается, когда не происходит уменьшения целевой функции при 5 последовательных температурах.
Для улучшения сходимости алгоритма метода имитации отжига были исследованы следующие его параметры: начальная температура Гтах, способ выбора нового состояния из окрестности текущего состояния, коэффициент охлаждения а, число итераций при постоянной температуре m.
Для вычисления начальной температуры в диссертации предложен алгоритм, обеспечивающий принятие около 50% переходов, увеличивающих значение целевой функции. В работе также были предложены способы выбора нового состояния.
Проведенные численные эксперименты показали, что, чем ближе значение коэффициента а к единице и чем выше число итераций т, тем меньше пофешность получаемых решений, но тем больше времени требуется для нахождения решения.
Для решения исходной задачи методом, основанным на детерминированной асинхронной дискретной сети Хопфилда, построена нейросетевая модель. Вводятся следующие обозначения: xiz є (ОД)
\i = l,;z = \,n) - состояния нейронов, где индекс / - кодирует номер компьютера, a z - номер задания, X(t)=(xt(t))M.n - вектор состояний нейронов в момент времени /. Время / дискретная величина. В начальный момент времени сеть характеризуется некоторым вектором Х{0) = (xiz {0))м.п
12 начальных состояний. Элементы х1= вектора нейронов X соответствуют
плану распределения заданий.
Традиционно энергия дискретной сети Хопфилда представляется в виде функции Ляпунова. Каждый нейрон преобразует входной сигнал в выходной сигнал с помощью нелинейной функции активации. В качестве функции активации f{h) используется пороговая функция. Сеть функционирует в асинхронном режиме. Для решения задачи с помощью дискретной сети Хопфилда необходимо преобразовать целевую функцию к виду функции Ляпунова. Известно, что динамика функционирования сети Хопфилда обеспечивает схождение сети к локальному экстремуму. Для нахождения глобального или близкого к глобальному решению необходимо запускать сеть из различных начальных состояний и выбирать из полученных решений наилучшее.
В диссертации для решения исходной задачи рассматривается алгоритм метода имитации отжига на основе стохастической асинхронной дискретной сети Хопфилда. В отличие от детерминированной сети Хопфилда, где состояния нейрона однозначно определяются детерминированной процедурой, реализующей асинхронную динамику, нейронные стохастические сети принимают состояния 0 или 1 в соответствии с процедурой, включающей элемент случайности.
В работе был предложен комбинированный метод, который реализует алгоритм имитации отжига на основе стохастической асинхронной дискретной сети Хопфилда (САДСХ), но, в дополнение к нему, из промежуточных состояний запускается детерминированная асинхронная дискретная сеть Хопфилда (АДСХ), которая обеспечивает быстрое нахождение локальных оптимумов. Затем из полученных решений выбирается наилучшее.
Для каждого разработанного алгоритма была проведена оценка трудоемкости, которая показала, что все рассмотренные алгоритмы имеют
13 полиномиальную сложность, но минимальную сложность имеет алгоритм поиска решения на основе сети Хопфилда (АДСХ).
Сравнительный анализ алгоритмов на v основе численных экспериментов проводился на множестве модельных примеров с числом компьютеров от 4 до 6 и количеством заданий от 6 до 150. Эксперимент показал, что комбинированный метод находит наилучшие решения с точки зрения оптимального значения целевой функции.
В третьей главе построены непрерывная и соответствующая нейросетевая модели задачи распределения заданий в мультипроцессорной системе и разработаны алгоритмы ее решения; сформулирована и доказана теорема о достаточном условии локального минимума функции энергии сети; выработаны рекомендации по подбору параметров нейросетевого алгоритма; проведен сравнительный анализ разработанных алгоритмов.
По аналогии с построенной во второй главе дискретной моделью формулируется непрерывная модель задачи распределения заданий в мультипроцессорной системе, при этом переменные плана распределения рассматриваются как непрерывные величины. Для решения задачи на основе непрерывной модели был осуществлен переход от задачи условной оптимизации к задаче безусловной оптимизации.
Среди множества численных методов поиска приближенного экстремума были выбраны два метода:
Метод Флетчера-Ривса, поскольку в нем заложено вычисление оптимального шага, который обеспечивает наискорейший спуск целевой функции вдоль выбранного направления, тем самым, позволяя сократить количество необходимых итераций;
Метод, основанный на применении непрерывной нейронной сети Хопфилда, обеспечивающей высокую скорость поиска решения и возможность распараллеливания вычислений, что особенно актуально в связи с появлением высоко производительных кластерных систем и многоядерных процессоров.
Поскольку целевая функция непрерывной задачи многоэкстремальная, необходимо запустить алгоритм Флетчера-Ривса из различных начальных точек и среди полученных решений выбрать план распределения, соответствующий наименьшему значению целевой функции.
В диссертации исследовался метод решения на основе непрерывной синхронной сети Хопфилда. В отличие от дискретной сети Хопфилда, рассмотренной во второй главе, время t > О и состояния нейронов сети являются непрерывными величинами, xiz(t) є (0,l) \і = Г,І;z = 1,п).
Нейродинамическая модель непрерывной сети Хопфилда описывается системой дифференциальных уравнений:
Clt j=\q = \ &iz
где uiz{t) - напряжение на нейроне (потенциал нейрона) (i,z) в момент времени /, (0j::jq - вес связи между нейронами (i,z) и (j,q), Siz — пороговое значение (потенциал активизации) (/,z)-ro нейрона, 9iz^R — временная константа нейрона; f(niz(t)) - функция активации нейрона, преобразующая напряжение на нейроне в выходной сигнал нейрона, т.е.
**(') = /(«&('))
В работе в качестве функции активации используется логистическая функция.
Подход к решению оптимизационной задачи с помощью непрерывной сети Хопфилда аналогичен подходу, применяемому для дискретной модели: исходная задача формулируется как безусловная задача оптимизации, полученная целевая функция безусловной задачи сопоставляется с функцией энергии сети Хопфилда, далее находится минимум функции энергии, а соответствующие этому минимуму состояния нейронов округляются до целочисленных значений 0 или 1. В случае если эта точка удовлетворяет ограничениям исходной задачи, то она принимается за ее решение.
Непрерывная сеть Хопфилда, функционирующая в соответствии с синхронной динамикой обеспечивает нахождение минимума функции энергии, что подтверждается многими известными теоремами [60].
В работе сформулирована и доказана теорема, гарантирующая, что устойчивые точки непрерывной сети Хопфилда из є -окрестности углов единичного гиперкуба, являются точками минимума функции энергии.
Теорема 2. Существует такой є>0, что если точка С = (ciz)lxi.n
является решением системы дифференциальных уравнений
^=itcD,jqf(uiM^-U^, (l = U;z = u), ГДЄ Ciz=f(lli2), И
М j=\q=\ Viz
выполняется условие k/z|< или |c/V—1|<, то С является точкой
локального минимума функции энергии.
Непрерывная сеть Хопфилда реализует метод Эйлера решения задачи Коши для систем дифференциальных уравнений.
В работе приведен алгоритм решения задачи распределения заданий в мультипроцессорной системе на основе синхронной непрерывной сети Хопфилда. Поскольку функция энергии сети многоэкстремальная, необходимо запускать сеть Хопфилда из различных начальных состояний и среди полученных планов распределения выбирать план, соответствующий наименьшему значению целевой функции.
На скорость сходимости сети и качество получаемых решений
оказывают влияние следующие параметры: начальная точка X —ус^пхе-п' величина шага А/, критерий останова є, временная константа нейрона Qiz.
Начальные точки X = \х?2)ыс-п предлагается выбирать из окрестности центра единичного гиперкуба в соответствии с формулой: xl = 0.5 + Ax(2R-\),{z = U?; / = 1,1), Ах є (0;0.5], где случайное число R є (0,l) генерируется датчиком псевдослучайных чисел в соответствии с равномерным законом распределения.
Величина шага At должна быть достаточно малой для того, чтобы обеспечить убывание функции энергии в процессе функционирования сети на основе процедуры
в.
В работе предлагается способ вычисления шага At на каждой итерации по следующей формуле:
0.4
А^ =
a- max
z=\,...,n
в,
it^Jg/M))^ Ut{t)
j=\q=\
max| Auiz (tj
12 < є, в котором левая часть выражает относительное
тахіи
В качестве критерия останова принимается выполнение следующего неравенства
изменение напряжений на нейронах, поэтому величина є должна быть малым положительным числом, близким к нулю.
Временная константа нейрона 0iz обеспечивает смещение минимумов энергии сети Хопфилда во внутреннюю область единичного гиперкуба и обеспечивает конечность напряжений niz{t) на нейронах. Данное смещение тем больше, чем меньше коэффициент 6І=. Приводится оценка временной константы:
0.4
t п j=\q=l
в,,>
а-е- тах^
> i.t,a>ia+&L
U=,?=I
где^л=10'
г. = J ^/zy^ если ^. <0
в противном случае
и со
izjq
\coizjq,Qcimcdizjq>0 0, в противном случае
Заметим, что данная оценка является несколько заниженной, однако она определяет порядок величины вг, а также устанавливает взаимосвязь параметров Qiz и є между собой. Показано, что неправильный выбор
17 данного параметра может привести к бесконечному числу итераций алгоритма функционирования сети, поэтому выбор конкретного значения 6t
при решении задач требует уточнения.
В экспериментальной части на основе исследования параметров разработанных алгоритмов получены следующие результаты.
Численные эксперименты показали, что наилучшие результаты для типовых примеров были получены, когда начальная точка не отклонялась от центра единичного гиперкуба более чем на 40%.
Исследование классических критериев останова и параметров sx и
є2 алгоритма Флетчера-Ривса позволило выявить их недостатки, связанные с
трудностью подбора параметров ех и є2. В работе обоснована
целесообразность применения для рассматриваемой задачи
модифицированного критерия при s2 ^ 0.01.
3. Наилучшие результаты использования непрерывной сети Хопфилда
maxJAz/,,^)
с критерием останова —-—:—^т~ < s были получены при значениях
max|M/z (ц
параметра є< 0.001. Кроме того, было отмечено, что при одном и том же значении є количество итераций функционирования синхронной сети Хопфилда практически не зависит от размерности задачи.
Экспериментальные исследования позволили сделать следующие выводы:
Для решения булевых задач с помощью непрерывных моделей нет необходимости в получении точных значений точек минимума, т.к. результат округляется, поэтому можно прервать построение последовательности точек в тот момент, когда все последующие точки округляются до одного и того же целочисленного решения.
Алгоритм решения задачи на основе непрерывной синхронной сети Хопфилда является наиболее эффективным с точки зрения качества получаемых решений.
В четвертой главе приводится описание разработанного программного комплекса, его структура, информационная технология интерактивного взаимодействия пользователя и программы, а также руководство пользователя.
Созданный программный комплекс предназначен для решения задачи распределения заданий в мультипроцессорной системе алгоритмами, рассмотренными в предыдущих главах диссертации. Кроме того, он предоставляет возможность настройки параметров алгоритмов решения, что позволяет проводить исследование разработанных алгоритмов.
Для разработки программного комплекса использовалась среда Delph 6, язык разработки - Object Pascal. В работе приведены требования к программному и аппаратному обеспечению.
Входными данными программы являются число заданий, число компьютеров, длительности выполнения заданий. Выходными данными является план распределения заданий.
В работе рассматривается технология интерактивного взаимодействия пользователя с программой, которая включает три основных этапа:
ввод исходных данных задачи;
настройка параметров задачи и алгоритмов решения;
решение задачи с помощью выбранного алгоритма.
Анализ критериев оптимизации распределения выполнения заданий в мультипроцессорной системе
Покажем, что рассматриваемая задача относится к классу задач теории расписаний. Задача теории расписаний считается заданной, если определены [59,78]: 1. Подлежащие выполнению работы и операции; 2. Количество и типы машин, выполняющих операции; 3. Порядок прохождения машин; 4. Критерии оценки расписаний. В терминах решаемой задачи в качестве работ выступают задания, для которых известны длительности выполнения на компьютерах. По характеру поступления заданий в мультипроцессорную систему задача распределения заданий является статической, т.к. расписание составляется для известного числа заданий. Под машинами понимаются однотипные компьютеры различной производительности, способные решить любое задание. Поскольку задание полностью выполняется на 1 машине, то порядок прохождения машин формируется следующим образом: задание выполняется полностью только на одном из компьютеров мультипроцессорной системы.
Оптимизацию распределения заданий можно осуществлять на основе различных критериев [26, 61, 78]. Критерий 1. «Длина» расписания, т.е. время, необходимое для выполнения всех заданий, должно быть минимальным: Критерий 2. Среднее время завершения выполнения заданий должно быть минимальным: где y/z — время, прошедшее с момента начала обработки первого задания до момента окончания обработки z-ro задания, т.е. это время нахождения задания z в системе. Критерий 3. Разность между загруженностью компьютеров должна быть минимальной: Критерий 4. Суммарное время работы компьютеров должно быть минимальным: Таким образом, задача распределения заданий является задачей теории расписаний. Оценим рассматриваемую задачу с разными критериями оптимальности с точки зрения сложности решения. Для этого рассмотрим понятие класса NP -полных задач, введенное независимо Куком и Левиным. К этому классу относятся задачи, для которых не найдено полиномиальных алгоритмов, однако не доказано, что таких алгоритмов не существует [48]. Описание многих NP -полных задач и других задач теории сложности содержится в [25, 56, 83]. Исторически теория NP -полных задач строится только для задач распознавания свойств, т.е. задач в качестве решения которых должен быть получен ответ «да» или «нет» [22]. Для каждой оптимизационной задачи можно определить тесно связанную с ней задачу распознавания. Например, для критерия (1.1) соответствующая задача распознавания может быть сформулирована следующим образом: «Существует ли расписание, длина которого не превосходит заранее заданного крайнего срока D?» В [78] доказано, что если задача распознавания NP -полная, следовательно связанная с ней оптимизационная задача является NP -полной.
Класс NP -полных задач является подклассом более широкого класса NP задач (рис. 1.2), который включает в себя также и класс Р задач. Класс Р объединяет задачи, решение которых может быть найдено с помощью известных полиномиальных алгоритмов. Класс NP можно определить с помощью понятия «недетерминированный алгоритм». Такой алгоритм состоит из двух различных стадий - стадии угадывания и стадии проверки. По заданной задаче распознавания на первой стадии происходит «угадывание» некоторого решения, затем на второй стадии за полиномиальное время осуществляется проверка решения, результатом которой является ответ «да» или «нет».
Метод имитации отжига на основе стохастической асинхронной дискретной сети Хопфилда
Рассмотрим алгоритм имитации отжига, реализуемый стохастической асинхронной дискретной нейронной сетью Хопфилда. В отличие от детерминированной нейронной сети, рассмотренной в параграфе 2.1, где состояния нейронов однозначно определяются детерминированной процедурой, реализующей динамику (2.5), нейроны стохастической сети принимают состояния 0 или 1 в соответствии с процедурой, включающей элемент случайности. Для каждого нейрона (i,z) i = \,;z = \,n в сети Хопфилда определяется вероятность нахождения этого нейрона в состоянии 1 по следующей формуле: рь = — ВУГТГ {i = W;z = T,n), (2.13) 1 + е Р" где взвешенная сумма входов hiz нейрона (i,z) определяется по формуле: j=\q=\ Затем, путем генерации случайного числа Riz є (ОД) и сравнения его с вероятностью piz, определяется реальное состояние нейрона \i,z). Приведем алгоритм имитации отжига на основе стохастической асинхронной дискретной сети Хопфилда. Алгоритм 2.5 состоит из следующих этапов: Входные параметры алгоритма: начальное состояние X =\Ха)м.п матрица весов W = [coh in) , вычисленная по формуле (2.9); вектор порогов V = («9/z )м.п, вычисленная по формуле (2.10). коэффициент охлаждения а є (0,і), число итераций т. 1. Задать начальное состояние сети X = X . 2. Определить начальную температуру Т, используя алгоритм 2.4 и задать значение целевой функции Fmin = оо. 3.
Задать признаки улучшения значения целевой функции dy = d2 = d3 = /4 = 5 = 1 4. Задать номер нейрона: / = 1, z = 1. 5. Если с/, + d2 + d3 + d4 + d5 0, то: 5.1. Задать признак / = 0. 5.2. Установить счетчик итераций к = 1. 5.3. Вычислить вероятность piz нахождения нейрона (i,z) в состоянии 1 по формуле (2.13). 5.4. В соответствии с равномерным законом распределения случайных величин сгенерировать число R из диапазона (ОД). 5.5. Если R piz, то принять xiz = 1, иначе xiz =0. 5.6. Если состояние X = (xiz)we_n является допустимым планом распределения заданий и Fm-m F(x), где F(x) вычисляется по формуле (2.2), то присвоить Fmin=F(x), Xmin =Х и установить признак уменьшения целевой функции d = 1. 5.7. Если z п, то установить z = z +1 и перейти на пункт 5.9. 5.8. Если z = n, то: 5.8.1. Если / , то установить / = / + 1, z = 1 и перейти на пункт 5.9. 5.8.2. Если / = , то установить / = 1, z = 1 и перейти на пункт 5.9. 5.9. Если к т,то к = к + \ и перейти на пункт 5.3. 5.10. Переустановить признаки уменьшения целевой функции dx=d2, d2=d3, d3=d4, d4 =d5, d5 =d . 5.11. Вычислить новую температуру T - аТ и перейти на пункт 5. 6. Если Fmin оо, то Xm-m =\Х;2)Ш. - полученное решение, иначе — решения не найдено. 7. Выход. Комбинированный метод реализует алгоритм 2.5 имитации отжига на основе стохастической асинхронной дискретной сети Хопфилда, но, в дополнение к нему, из промежуточных состояний запускается детерминированная асинхронная дискретная сеть Хопфилда (АДСХ), которая обеспечивает быстрое нахождение локального минимума целевой функции в соответствии с алгоритмом 2.1. Из найденных АДСХ решений выбирается наилучшее. Работу комбинированного алгоритма иллюстрирует рис. 2.2.
Приведем алгоритм комбинированного метода. Алгоритм 2.6 состоит из следующих этапов: Входные параметры алгоритма: начальное состояние X -\xiz\xi.n , матрица весов W = [coiz jq) , вычисленная по формуле (2.9); вектор порогов V = ($iz)1х/.я, вычисленная по формуле (2.10); коэффициент охлаждения а є (0,l); число итераций т. 1. Задать начальное состояние сети X = X . 2. Определить начальную температуру Т, используя алгоритм 2.4 и задать значение целевой функции Fmin = оо. 3. Задать признаки улучшения значения целевой функции i] = d2 = d3 = d4 = d5 = 1. 4. Задать номер нейрона: / = 1, z = 1. 5. Если dx + d2 + d3 + d4 + d5 0, то: 5.1. Задать признак d = 0. 5.2. Установить счетчик итераций к = 1. 5.3. Вычислить вероятность piz нахождения нейрона (i,z) в состоянии 1 по формуле (2.13). 5.4. В соответствии с равномерным законом распределения случайных величин сгенерировать число R из диапазона (0,l). 5.5. Если R piz, то принять xiz = 1, иначе xiz = 0. 5.6. Запустить АДСХ из начального состояния X = (xiz)M.n. При использовании алгоритма 2.1 найти план X = {x iz\xe.n 5.7. Если состояние Х = (х ь)ш является допустимым планом распределения заданий и Fmin F(X ), где F(X ) вычисляется по формуле (2.2), то присвоить Fmin=F(X ), Xmm=X и установить признак уменьшения целевой функции d 1. 5.8. Если z п, то установить z = z + l и перейти на пункт 5.10. 5.9. Если z = и, то: 5.9.1.
Если і , то установить / = / + 1, z = \ и перейти на пункт 5.10. 5.9.2. Если / = , то установить / = 1, z = \ и перейти на пункт 5.10. 5.10. Если к т,то к = к + \ и перейти на пункт 5.3. 5.11. Переустановить признаки уменьшения целевой функции dl=d2, СІ2 — &2 &2 = и, л , и. л =- Clc , flc — СІ . 5.12. Вычислить новую температуру Т = «Г и перейти на пункт 5. 6. Если Fmin оо, то Xm-m =(xiz)M.n - полученное решение, иначе - решения не найдено. 7. Выход. Под трудоемкостью алгоритма понимается количество некоторых условных операций, необходимых для завершения работы алгоритма, решающего задачу [22, 56]. Функцией трудоемкости называется отношение, связывающие входные данные алгоритма с количеством элементарных операций. Оценка функции трудоемкости, называемая сложностью алгоритма, позволяет определить, как быстро растет трудоёмкость алгоритма с увеличением объема данных. Верхней оценкой функции сложности алгоритма является оценка О.
Методы решения задач непрерывной оптимизации
Непрерывная модель задачи распределения заданий в мультипроцессорной системе формулируется по аналогии с дискретной моделью (1.10), (1.8)-(1.9), описанной в главе 1, при этом переменные xiz \i = \,;z = \,nj плана распределения X рассматриваются как непрерывные величины. Необходимо определить план, обеспечивающий минимум целевой функции: при следующих ограничениях: Ограничение (3.2) требует, чтобы каждое задание выполнялось только на одном компьютере. Ограничение (3.3) требует, чтобы на /-м компьютере задание z либо выполнялось целиком, либо вовсе не выполнялось. Таким образом, непрерывная математическая модель распределения заданий в мультипроцессорной системе представляется выражениями (3.1) (3.3). Задача (3.1)-(3.3) является непрерывной с ограничениями типа равенств и относится к классу задач нелинейного программирования. Численные методы решения таких задач подразделяются на методы поиска условного и безусловного экстремума. Методы поиска условного экстремума работают по принципу генерирования последовательности допустимых точек с монотонно убывающими значениями целевой функции [24]. Поиск оптимального решения начинается с некоторого начального приближения из допустимой области, при этом предполагается, что эта область является непрерывной. В нашем случае допустимая область представляет собой множество точек, располагаемых в углах единичного гиперкуба в Евклидовом ( х п) -мерном пространстве.
Подобные методы для решения задачи в непрерывной постановке аналогичны дискретным методам. В. соответствии со вторым подходом задача оптимизации с ограничениями преобразуется к задаче без ограничений путем добавления к целевой функции неотрицательных штрафных функций, обращающихся в ноль при выполнении соответствующих ограничений задачи ([72]), а затем полученная задача решается методами безусловной оптимизации. Перейдем от задачи условной оптимизации (3.1)-(3.3) к задаче безусловной оптимизации. После преобразований функций ограничений непрерывная математическая модель безусловной оптимизации распределения заданий в мультипроцессорной системе запишется следующим образом: Некоторое решение X = (xt)[xl непрерывной модели (3.4) должно интерпретироваться как план распределения заданий в мультипроцессорной системе.
Поэтому переменные xiz [і l,t,z = 1,/7) должны принимать значения 0 или 1. Однако точка минимума может быть смещена ближе к центру единичного гиперкуба, поэтому будем использовать следующее правило округления нецелочисленного решения: fc=i 1, если xiz 0.5 0, если х;, 0.5 Численные методы решения задач безусловной оптимизации делятся на три группы [54, 72, 73]: 1. Методы нулевого порядка, использующие только информацию о значении целевой функции (метод конфигураций, метод деформируемого многогранника, метод Розенброка, метод сопряженных направлений, адаптивный метод случайного поиска и др.). 2. Методы первого порядка, использующие информацию о первых производных целевой функции (методы градиентного спуска с постоянным шагом, наискорейшего градиентного спуска, покоординатного спуска, Гаусса-Зейделя (наискорейшего покоординатного спуска), Флетчера-Ривса, Дэвидона-Флетчера-Пауэлла, методы на основе нейронных сетей и др.). 3. Методы второго порядка, требующие для своей реализации знания вторых производных целевой функции (методы Ньютона, Ньютона-Рафсона, Маркварда и др.). Среди всех методов методы первого порядка характеризуются высокой скоростью сходимости к экстремуму функции. Поиск экстремума начинается из некоторой начальной точки. Движение осуществляется с некоторым шагом в направлении убывания целевой функции, определяемом на основании вычисления производной функции. Среди методов первого порядка выделяется метод Флетчера-Ривса, поскольку в нем заложено вычисление оптимального шага, который обеспечивает максимальное убывание целевой функции вдоль выбранного направления, тем самым позволяя сократить количество необходимых итераций.
Экспериментальное исследование разработанных алгоритмов
В корпоративных автоматизированных системах организационного управления различных государственных структур, характеризующихся большим количеством пользователей, необходимо решать множество задач обработки информации. Очевидно, что от скорости обработки информации во многом зависит оперативность принятия управленческих и финансовых решений. Однако быстродействия одного компьютера недостаточно для массового обслуживания задач пользователей.
Современные тенденции увеличения производительности компьютеров связаны с распараллеливанием вычислительных процессов: появились многоядерные процессоры и высокопроизводительные кластерные системы -модульные мультипроцессорные системы, созданные на базе стандартных вычислительных узлов, соединенных высокоскоростной коммуникационной средой [43, 70]. Эффективность работы кластерной системы зависит от правильного распределения выполнения заданий по вычислительным узлам. Поэтому актуальными в настоящее время являются задачи эффективного использования мультипроцессорных систем в автоматизированных системах организационного управления и распределения в них заданий.
Постановка задачи распределения и упорядочения заданий в мультипроцессорной системе является хорошо известной в теории расписаний и рассматривается в работах Конвея Р.В., Максвелла В.Л., Миллера Л.В., Танаева B.C., Шкурбы В.В., Левина В.И. и других [26, 46, 52, 74, 78]. Многие задачи распределения являются NP-полными, что не позволяет эффективно решать их точными методами, поэтому необходимо разрабатывать алгоритмы на основе приближенных методов [51]. Появление искусственных нейронных сетей как математического инструментария распараллеливания вычислений делают актуальной задачу разработки нейросетевых математических моделей, методов и алгоритмов оптимального распределения заданий в мультипроцессорной системе. Цель и задачи исследования. Целью диссертационной работы является разработка нейросетевых математических моделей, методов и алгоритмов решения задачи оптимального распределения заданий в мультипроцессорной системе. Для достижения поставленной цели необходимо решить следующие научные задачи: 1. Исследовать вычислительную сложность задачи распределения заданий в мультипроцессорной системе с разными критериями оптимизации; 2. Разработать нейросетевые дискретную и непрерывную математические модели распределения заданий в мультипроцессорной системе; 3. Разработать нейросетевые алгоритмы решения задачи распределения, исследовать параметры алгоритмов и выработать рекомендации по их определению; 4. Разработать программный комплекс, реализующий разработанные алгоритмы решения задачи распределения заданий в мультипроцессорной системе; 5. Провести численные эксперименты для сравнительного анализа классических и разработанных алгоритмов с помощью разработанного программного комплекса. Методы исследования. Для решения поставленных задач в работе использовались методы оптимизации, исследования операций, теории принятия решений, численных методов, теории обыкновенных дифференциальных уравнений, теории нейронных сетей, теории алгоритмов, математического анализа.
Научная новизна. В диссертационной работе получены следующие новые научные результаты:1. Сформулирована и доказана теорема, обосновывающая Л/Р-полноту задачи распределения заданий в мультипроцессорной системе с равномерной загрузкой компьютеров; 2. Построена двухкритериальная модель булевой оптимизации распределения заданий в мультипроцессорной системе, и на ее основе разработаны однокритериальные дискретная, непрерывная и нейросетевые модели; 3. Предложен метод решения дискретной задачи распределения заданий, сочетающий метод имитации отжига, детерминированную и стохастическую асинхронные дискретные сети Хопфилда; 4. Разработаны алгоритм определения начальной температуры для методов имитации отжига, выражения для вычисления временного шага и оценки временной константы нейронов алгоритма непрерывной нейронной сети Хопфилда.
Достоверность результатов работы. Основные положения диссертационной работы получены на основании достоверных знаний прикладной математики и использования строгого математического аппарата. Полученные теоретические результаты подтверждены вычислительными экспериментами, актами использования в деятельности государственных организаций и внедрения в учебный процесс.
Практическая ценность работы заключается в создании программного комплекса, реализующего разработанные алгоритмы и позволяющего решать задачу распределения заданий в мультипроцессорной системе.
