Диссертация (Разработка моделей и алгоритмов составления оптимальных расписаний выполнения программных модулей в вычислительной сети на основе эволюционного подхода), страница 9

Эффективность коммуникаций представляетмножество весов каналов связи C = {cαβ : ∈ A; ∈ B }, где множество Aидентификаторы узлов-передатчиков, множество B идентификаторы узловприёмников, A ⊂ J, B ⊂ J и A ∩ B , а cαβ вес канала связи между узлом сидентификатором и узлом с идентификатором , если ≡ , то вес каналасвязи равен 0, это значит, что задачи выполняются на одном узле и для передачиданных каналы связи не используются.

Большое количество нулевых связейприближает эффективность параллельного выполнения к последовательному.Сравнение выполнения комплекса ИЗЗ на одной последовательной машине и вРСОД приводится в [39].Каждому элементу множества Q соответствует некоторый элементмножества С, т.е. ∀ ∈ , ∃с ∈ С ( q)=c.

Заменив элементы множества Q насоответствующие элементы множества С можно рассчитать общий вескоммуникационной среды для конкретного расписания.58Всевышеописанныемножества,отображающиекритерии,представляются в виде соответствующих, одноимённых матриц, которыерассчитываются до запуска алгоритма.Задача фитнес-функции заключается в следующем. На основе данныхполученных с помощью матричного анализа, рассчитать для каждой хромосомыобщее время завершения всех ИЗЗ комплекса, которое включает времявыполнения и время задержки передачи, и на основании этих расчетов датьоценку каждой особи.̅̅̅̅̅Представим популяцию особей как множество ́={Sγ: γ=1,η , γ ∈ Γ}, где Sγособь с номером γ, а η размер популяции, Γ⊂ Z и ́ ⊂ ŜUP , тогда оценка для особиSγ тогда есть функция (Sγ) .Оценка представляет числовое значение, находящееся в диапазоне (0,1],где значение 1 достигается в случае оптимального расписания, эти значенияиспользует оператор отбора.Оператор отбора в ГА предназначен для выбора хорошего векторахромосомы и отклонения плохого.

Его работа основана на значенияхприспособленности фитнес-функции, если форма хромосомы хорошая, то онаимеет больше шансов быть выбранной. Существуют различные методы отборатакие, как турнирная селекция, ранговая селекция и др. [51]. В данной работеиспользуется основной для генетических алгоритмов метод вращения рулетки(roulette wheel selection).

В этом виде селекции гипотетический круг рулеткипредставляет диапазон чисел (0,λ], где λ=∑=1 (Sγ) сумма оценок всех особей.Каждой из особей популяции ставится в соответствие сектор этого круга, т.едиапазон чисел, размер которого пропорционален вероятности выбора особи,которая рассчитывается по формуле 2.1.1 и выражается в процентах.( ) =( )∑=1 ( ),(2.1.1)59где f (Sγ) – значение функции пригодности хромосомы Sγ , p (Sγ) –вероятность отбора хромосомы Sγ.Пусть Ω = {ω: ω ∈ (0,λ]} множество всех значений круга рулетки, а ΔṤмножество секторов для популяции ́, тогдаΔṤ = {δγ (0, p(Sγ)), δγ+1(p(Sγ), p(Sγ+1)), … δη (p(Sη-1), p(Sη))},где δγ (0, p(Sγ)) сектор представляющий особь с номером γ, с диапазономот 0 до p(Sγ)).На следующем шаге из диапазона чисел, представляющих круг, случайнымобразом выбирается число, далее производится выбор особи, сектору (диапазону)которой принадлежит это число.

Процесс повторяется заданное количество раз, ипо окончанию селекции создается популяция, называемая родительским пулом счисленностью, которая задаётся параметром алгоритма. В результате работыоператора отбора, в этот пул могут попадать не только хорошие, но и плохиеособи. Таким образом, эволюционная модель отображает стохастичностьпроцессов в природе, которые не протекают гладко, и иногда в результатекатаклизмов особи менее жизнеспособные оказываются в большинстве, а болееприспособленные погибают.После того как отбор закончен начинает работу оператор скрещивания.Этот оператор в ГА реализует один из принципов эволюции. Новая хромосомаобразуется при помощи комбинации частей двух случайно выбранныхродительских хромосом, таким образом, предок наследует генетическийматериал, образуя новый вид расписания.

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

В работе [48]применяется специальный генетический оператор скрещивания для сохранения60целостности расписания при скрещивании, гены должны исключаться из обеихродительских хромосом, чтобы не допустить попадания в дочернюю хромосомуещё раз. В результате алгоритм гарантирует, что никакой ген при скрещивании непопадёт в дочернюю хромосому дважды. Представленный алгоритм используетоператор с одной точкой скрещивания.Далее следует оператор мутации, он случайным образом меняет местамиидентификаторы узлов в хромосоме.

Мутация используется, чтобы уйти отранней конвергенции. Хромосома может подвергаться мутации несколько раз(параметр алгоритма). В статье [39] используется нестандартный оператормутации, который применяет частичную мутацию гена, в этом случае в случайновыбраннойхромосоме,водномслучайновыбранномгенеизменяетсяидентификатор узла, после анализа матрицы времени выполнения из всехдоступных узлов для задачи выбирается узел, на котором время выполнениязадачи, представляющей ген минимально из всех доступных узлов для этойзадачи. В работе [48] после завершения работы оператора мутации необходимовносить изменения в составляющие времени генов, т.к. после обмена гены могутбыть поставлены в соответствие процессорам с отличными от прежниххарактеристиками.

Т.к. в данной работе хромосома имеет упрощённый вид ипредставляет вектор из номеров узлов, алгоритм использует стандартныйоператор мутации.Критерием останова алгоритма может служить неулучшение целевойфункции для лучшей из строк на протяжении заданного числа шагов [47].Представленный алгоритм останавливается после заданного количества итераций.Параметры алгоритма: входными данными является размер начальнойпопуляции, размер родительской популяции, матрицы длительностей выполненияT, матрица эффективности коммуникаций C, матрица взаимосвязей задач Q,количество скрещиваний, количество мутаций каждой хромосомы, количествопоколений (итераций).Схема алгоритма:61Шаг 1.

Счётчик поколений X = 0. Создание начальной популяции путемпроизвольного выбора последовательностей узлов.Шаг 2. Оценка фитнес-функции для каждой особи, с помощью анализаматриц T, C и Q. На основании следующих данных:а) время выполнения задачи,б) пропускная способность канала связи.Шаг 3. Оператор отбора. Расчёт суммы оценок всех особей и вероятностейвыбора для каждой особи по формуле 2.2.1.

Генерация случайного числа издиапазона (0, λ], выбор соответствующей особи.Шаг 4. Сохранение лучшей особи.Шаг 5. Выполнениеоператораскрещивания.Генерация точкискрещивания, обмен частей хромосом в случайно выбранной паре особей.Шаг 6. Оператор мутации. Обмен местами двух случайно выбранных геновв случайно выбранных хромосомах.Шаг 7. Формирование новой популяции.Шаг 8. Счетчик поколений X = X+1.Шаг 9. Если X = maxX выход с лучшим решением и остановка, еслиX<max X переход на 3 шаг.2.2.Разработкаэволюционныхмоделейпоискаоптимальныхрасписаний выполнения программных модулей в вычислительной сети2.2.1.

Разработка общей модели поиска оптимальных расписанийвыполнения программных модулей в вычислительной сетиРазработка ПО для РСОД основана на декомпозиционном подходе. Насегодняшний день в данной области существует множество исследуемыхпроблем.Однойизтакихпроблемявляетсяпортируемостьпараллельнойпрограммы, т.е.

перенос её с одной РСОД на другую, что в свою очередь требует62разработки систем, производящих распараллеливание исходной программы, сучетом конкретных архитектурных особенностей аппаратного обеспечения.В работе [51] представлена разработка системы «Парус», которая наоснове анализа последовательной программы и РСОД, в которой онавыполняется,производитраспараллеливаниеисходнойпрограммысиспользованием вставок директив из библиотеки MPI.

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

В этомслучае, мелко-распараллеленная исходная программа поступает на вход системыи планировщик, исходя из состояния системы на данный момент времени,распределяет части программы по ВУ.Т.к. количество узлов и программных модулей может быть значительным,данная задача приобретает NP-сложность. Исследованиями в данной областизанимается теория расписаний.В последние годы отмечается повышенный интерес к данной научнойобласти,т.к. создание корректных, полныхматематическихмоделей иэффективных алгоритмов составления расписаний является актуальной задачей.