Модификации алгоритма Крона

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

Модификация заключается в случайном начальном распределении множества заданий, затем уточнении полученного распределения по алгоритму Крона, и дополнительном уточнении. Дополнительное уточнение будет осуществляться посредством обмена парами заданий между приборами с максимальным T^max и минимальным T^min значениями из набора {T_i} при выполнении условия q^max - q^min < D, где p^max = p_i^max + p_j^max, p^min = p_k^min + p_l^min, D = T^max - T^min, i, k = 1,2,..,m-1, j, l = 2,3,..,m (m – количество заданий). После каждой операции обмена значения {T_i} пересчитываются, выбираются новые два прибора с T^max и T^min и процесс проверки указанного выше условия повторяется. Если сравнение с T^max проведено для каждого T^min и условие ни разу не выполнилось, то алгоритм завершает свою работу.

Для большего понимания принципов работы модифицированного алгоритма Крона приведём его графическую интерпретацию.

Пусть на вход модифицированного алгоритма Крона поступает множество из 12 заданий распределённое случайным образом на 3 прибора. Далее вычисляется суммарная загрузка каждого прибора, в результате чего получаем множество T = {T₁, T₂, T₃,}. Из полученного множества {T} выбираем T^max и T^min. На следующем этапе начинаем итерационный процесс в ходе которого необходимо суммировать пары заданий из T^max и T^min и проверять условие p^max - p^min < D. Графическая интерпретация итерационного процесса приведена на рисунке 1.

(a11+a12) – (a21+a22) < D (a11+a12) – (a21+a23) < D

(a11+a12) – (a22+a23) < D (a11+a13) – (a21+a22) < D

(a11+a13) – (a21+a23) < D

Рисунок 1 – Итерационный процесс выбора двух пар заданий для обмена

Пусть условие (a11+a13) – (a21+a23) < D выполняется, тогда задания a11 и a13 из первого прибора необходимо «перебросить» во второй прибор, а задания а21 и а23 со второго прибора «перебросить» на первый прибор. В результате получим распределение, приведённое на рисунке 2.

Рисунок 2 – Распределение, полученное в результате обмена заданиями

После этого, значения множества {T} пересчитываются и для приборов с T^max и T^min итерационный процесс повторяется. И, так до тех пор, пока условие q^max - q^min < D ни разу не выполнится.

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

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

Таблица 1 – Усредненные значения критериев

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

Варианты заданий

Задание определяется согласно № - номера студента в списке, по приведенным ниже таблицам (Таблица 1, Таблица 2, Таблица 3). Алг. - название алгоритма, который необходимо запрограммировать. Параметр n-определяет число устройств. m – количество работ, выбирается одно значение из указанного отрезка в таблице 3, T – множество весов работ, случайным образом берется m работ в пределах указанных в таблице 3.

Например, если студент в списке под номером №5, то Алг. = “Критический путь”, n = 4, m выбирается произвольно в отрезке [20,25] m = 21, T формируется из n работ, вес которых выбирается случайным образом в отрезке [20,35].

Таблица 1

Таблица 2

Таблица 3

Литература

1. Коффман Э.Г. “Теория расписания и вычислительные машины” – M.: “Наука”, 1987

1. Романовский И.В. “Алгоритмы решения экстремальных задач” – М.: “Наука”, 1977

1. Пашкеев С.Д., Минязов Р.И., Могилевский В.Д. “Машинные методы оптимизации в технике связи” – М.: “Связь”, 1976.

Редактор __________________

_________________________________________________________

ЛР № 04779 от 18.05.01. В набор В печать

Объем 0,5 усл.п.л., уч.-изд.л. Офсет. Формат 60x84/16.

Бумага тип №3. Заказ № Тираж 140. _________________________________________________________

Издательский центр ДГТУ

Адрес университета и полиграфического предприятия:

344010, г. Ростов-на-Дону, пл. гагарина, 1.

Дата добавления: 2014-12-09; просмотров: 303; Нарушение авторских прав

Мы поможем в написании ваших работ!