close

Вход

Забыли?

вход по аккаунту

?

Алгоритмический подход к уменьшению времени работы точного метода в однородных системах.

код для вставкиСкачать
Технические науки. Часть I
УДК 681.3.681.5
В.Г. КОБАК, Д.В. ТИТОВ
АЛГОРИТМИЧЕСКИЙ ПОДХОД К УМЕНЬШЕНИЮ ВРЕМЕНИ
РАБОТЫ ТОЧНОГО МЕТОДА В ОДНОРОДНЫХ СИСТЕМАХ
Данная работа дает оценку точному алгоритму Романовского при использовании в
качестве начального значения верхней границы одной из модификаций генетического алгоритма. Данный подход приводит к резкому сокращению времени получения точного решения, особенно для двухпроцессорных вычислительных систем.
Ключевые слова: теория расписаний, задача планирования, алгоритм Романовского, генетический алгоритм, списочные алгоритмы, вычислительный эксперимент, вектор загрузки.
Введение. Во многих отраслях промышленности и производства очень часто применяются многопроцессорные (многоядерные) вычислительные системы для решения различного рода задач. Для эффективного решения
этих задач, которые необходимо распределить по параллельно работающим процессорам, используют различные методы построения расписаний.
Для построения оптимального расписания необходимо использовать точные алгоритмы, основанные на методе ветвей и границ, из-за этого при
большом количестве задач и процессоров время нахождения оптимального
расписания сильно увеличивается. Если допускается решение, близкое к
оптимальному, то для этих целей можно использовать приближенные алгоритмы построения расписаний, которые работают намного быстрее точных
для большого числа независимых заданий.
Постановка задачи. Следует составить расписание для n однородных
параллельных процессоров, на которые необходимо распределить m независимых заданий [1], образующих параллельную программу. Математическая постановка данной задачи приведена в [2], где также было отмечено,
что при n ≥ 2 данная задача относится к классу NP-полных.
Алгоритм Романовского. Принцип действия алгоритма Романовского заключается в следующем. Упорядочивается по убыванию список заданий,
затем вычисляется нижняя граница (оценка снизу) est =
m
∑t
j
/ n и верх-
j=1
няя граница (оценка сверху) rec =
m
∑t
j
. Выбираем какое-либо число
j=1
z ∈ (est , rec) и рассматриваем z-задачу, т.е. находим такое распределение заданий по процессорам, при котором минимальное общее время выполнения задач T ≤ z . Если удается найти решение этой задачи, то z берется в качестве нового значения верхней границы, после чего процесс повторяется. Если z-задача решения не имеет, то z берется в качестве нового
значения нижней границы, и также процесс повторяется. Для выделения
последующих z-задач рекомендовано в [3] брать полусумму верхней и нижней границ, т.е. z = (est + rec) / 2 . Процесс повторяется, пока не будет
найдено оптимальное решение, которое достигается при выполнении условия rec = est + 1 . Для решения z-задачи используется метод ветвей и границ с односторонним обходом дерева вариантов. Предполагается, что загрузка каждого процессора не превышает максимально допустимой загрузки z, т.е. Ti ≤ z , где i = 1, n . Таким образом, суммарная загрузка процес24
Технические науки. Часть I
соров Tsum =
m
∑
j=1
t j будет меньше максимально допустимой загрузки про-
цессоров Tmax = z × n на величину sl = Tmax − Tsum . Задачи назначаются
на процессоры последовательно из списка заданий, стремясь, каждый раз
назначить на процессор задачу с самым большим временем выполнения,
при этом вычисляется разность si между максимально допустимой загрузкой процессоров и загрузкой i-го процессора, т.е. si = z − Ti , причем si
каждый раз вычитается из sl, и результат должен в течение всего вычислительного процесса оставаться неотрицательным. Если результат станет отрицательным, то происходит отмена последнего из назначений.
Списочные алгоритмы. Одним из самых распространенных списочных
алгоритмов является метод критического пути Critical Path Method (CPM).
Принцип действия CPM заключается в том, что очередное задание из
списка заданий, упорядоченных по убыванию, назначается на процессор с
самой минимальной суммарной загрузкой.
К списочным алгоритмам также относится алгоритм Пашкеева (алгоритм по направлению). Принцип действия которого заключается в том,
что сравнивается суммарная загрузка крайних процессоров (первого и последнего), если загрузка первого процессора меньше последнего, то очередные задания по порядку назначаются с первого по последний процессор, если загрузка первого процессора больше последнего, то очередные
задания назначаются с последнего по первый процессор.
Генетические алгоритмы. К одним из самых популярных эвристических
методов относятся генетические алгоритмы (ГА), которые являются одной
из парадигм эволюционных вычислений, построены на принципах, сходных
с принципами естественного отбора и генетики. Общий принцип работы ГА
состоит в следующем: на первом шаге формируется начальное поколение,
состоящее из заданного числа особей; на втором шаге происходит отбор
особей и применение операторов кроссовера и мутации ГА с заданной вероятностью, формирование нового поколения; на шаге три происходит
проверка условия останова, которая обычно заключается в неизменности
лучшего решения в течение заданного числа поколений, если проверка
прошла успешно, то лучшая особь выбирается как найденное решение,
иначе происходит переход на второй шаг.
В базовой схеме работы ГА в ходе формирования нового поколения
особи потомков могут замещать родительские особи. Такой подход достаточно естественен, но не особенно эффективен, так как существует вероятность замещения лучшей родительской особи худшей особью потомка.
Для решения данной проблемы был разработан принцип элитизма. Суть
этого принципа заключается в том, что в новое поколение включаются
лучшие родительские особи (элитные особи), что позволяет не потерять
хорошее промежуточное решение. Число элитных особей может быть от
одной и более.
Использование разных подходов к формированию границ алгоритма Романовского. В стандартном алгоритме Романовского для выделения последующих z-задач рекомендовано брать полусумму верхней и
нижней границ [3]. Как было отмечено выше, если z-задача имеет решение, то z берется в качестве нового значения верхней границы, иначе –
нижней границы. В статье [4] были предложены методы выделения последующих z-задач: последовательный спуск и ускоренный спуск с шагом два.
25
Вестник ДГТУ, 2009. Спец. выпуск
При последовательном спуске новое значение z равняется значению верхней границы минус единица, а при ускоренном спуске с шагом два – значению верхней границы минус два.
Использование списочных алгоритмов при формировании верхней
границы алгоритма Романовского. Для повышения эффективности алгоритма Романовского при формировании начального значения верхней
границы можно использовать списочные алгоритмы [2, 4]. В статье [2]
были рассмотрены разные модификации алгоритма Романовского, в которых для формирования начального значения верхней границы использовались результаты, которые возвращались алгоритмами CPM и Пашкеева.
Для выделения последующих z-задач использовались полусумма верхней и
нижней границ, последовательный спуск и ускоренный спуск с шагом два.
В ходе вычислительного эксперимента, описанного в [2], было отмечено,
что для распределения задач на два, три и четыре процессора самой эффективной является модификация алгоритма Романовского, использующая
для взятия начального значения верхней границы алгоритм CPM, а для
формирования верхней и нижней границ - последовательный спуск. Данную модификацию будем обозначать как МАР[CPM].
Использование генетического алгоритма при формировании
верхней границы алгоритма Романовского. В качестве начального
значения верхней границы алгоритма Романовского можно использовать
результат, возвращенный генетическим алгоритмом.
В статье [5] была предложена модификация ГА, которая являлась
самой лучшей из рассмотренных в статье других модификаций ГА. Данная
модификация заключалась в том, что при формировании нового поколения использовался турнирный отбор, в котором участвовала очередная
особь (родительская) и результирующая (потомок), полученная в ходе выполнения операторов кроссовера и мутации. Данный способ формирования нового поколения будем называть турнир с родителем. Модификацию
алгоритма Романовского, использующую описанный генетический алгоритм, будем обозначать как МАР[ГА(т.р.)].
Были реализованы генетические алгоритмы с использованием элитизма и турнира с родителем. В первом случае была задана одна элитная
особь. Алгоритм Романовского, использующий данный генетический алгоритм, будем обозначать как МАР[ГА(1эл.о., т.р.)]. Во втором случае в качестве элитной особи в начальном поколении выбиралась особь, полученная
из преобразованного решения, возвращаемого метод CPM. Алгоритм Романовского, использующий данный генетический алгоритм, будем обозначать как МАР[ГА(1эл.о.+ CPM, т.р.)].
Первый вычислительный эксперимент. Для сравнительного исследования модификаций алгоритма Романовского с помощью генетических алгоритмов был проведен ряд вычислительных экспериментов для
2-4-процессорных систем обработки информации.
Для проведения эксперимента были случайным образом сгенерированы 100 векторов загрузки, содержащие задачи в диапазоне 25…30, каждый из векторов решался МАР[ГА(т.р.)], МАР[ГА(1эл.о., т.р.)] и
МАР[ГА(1эл.о.+ CPM, т.р.)]. Для выделения последующих z-задач использовались полусумма верхней и нижней границ, последовательный спуск и
ускоренный спуск с шагом два. Число задач m было фиксировано и равнялось 17. Для всех используемых генетических алгоритмов были выбраны
следующие фиксированные параметры: число особей составляло 50, условием останова являлось появление в процессе решения более 500 поколе26
Технические науки. Часть I
ний с лучшей одинаковой особью, вероятность кроссовера составляла
90%, а вероятность мутации - 10%.
Полученные результаты усреднялись по времени решения задач,
т.е. Tcp =
100
∑
ti / 100 , где t i - время нахождения решения для i-го вектора
i= 1
загрузки.
Результаты
первого
вычислительного
эксперимента.
Проанализировав
результаты
вычислительного
эксперимента,
представленного на диаграммах (рис.1, 2), можно сделать следующие
основные заключения. Наиболее перспективным для использования
является модификация алгоритма Романовского, использующая для
начального формирования верхней границы генетический алгоритм без
элитной особи, использующий турнир с родителем (МАР[ГА(т.р.)]), а для
выделения последующих z-задач – последовательный спуск. Также можно
отметить, что модификации алгоритма Романовского, использующие для
выделения последующих z-задач последовательный спуск, работают намного быстрее, чем модификации с ускоренным спуском, которые, в свою
очередь, работают быстрее модификаций с полусуммой границ.
Рис.1. Усредненное время решения алгоритмов для двух-трех процессоров
Рис.2. Усредненное время решения алгоритмов для четырех процессоров
27
Вестник ДГТУ, 2009. Спец. выпуск
Второй вычислительный эксперимент. Для определения, какой из
предложенных модификаций алгоритма Романовского: МАР[CPM] или
МАР[ГА(т.р.)] - является лучшим, был проведен ряд вычислительных экспериментов для 2-4-процессорных систем обработки информации. Для проведения эксперимента были случайным образом сгенерированы 100 векторов загрузки, содержащие задачи в диапазоне 25…30. Для 2-процес-сорных
систем число задач составляло 41 и 43, для 3-процессорных – 41, а для 4процессорных – 19. Для генетического алгоритма были выбраны те же самые фиксированные параметры, что и в первом эксперименте. Полученные
результаты усреднялись по времени решения задач.
Результаты второго вычислительного эксперимента. Основные результаты вычислительного эксперимента отображены на рис.3.
а)
б)
Рис.3. Усредненное время решения алгоритмов
для двух (а), трех (б) и четырех (в) про-цессоров
в)
Проанализировав результаты вычислительного эксперимента,
представленного на диаграммах (см. рис.3), можно сделать вывод, что
применение модификации алгоритма Романовского, использующей для
начального формирования верхней границы генетический алгоритм без
элитной особи, использующий турнир с родителем (МАР[ГА(т.р.)]), в целом
быстрее выполняется, чем модификация Романовского с использованием
метода CPM (МАР[CPM]), особенно это заметно для двухпроцессорных вычислительных систем, где разница составляет несколько сотен раз, а для
трех и четырех процессоров данные модификации приблизительно выполняются одинаковое количество времени.
28
Технические науки. Часть I
Выводы. Модификация алгоритма Романовского, использующая генетический алгоритм с турнирным отбором для формирования нового поколения
без элитной особи и использующая для выделения последующих z-задач
последовательный спуск, работает более эффективно, чем рассмотренные
другие модификации алгоритма Романовского, особенно для двухпроцессорных вычислительных систем, следовательно, её можно рекомендовать
для использования составления точного расписания для 2-4-процессорных
вычислительных систем.
Библиографический список
1. Коффман Э.Г. Теория расписания и вычислительные машины.
/ Э.Г.Коффман. - М.: Наука, 1987.
2. Кобак В.Г. Исследование работы алгоритма Романовского с использованием списочных алгоритмов при формировании верхней границы
/ В.Г.Кобак, Д.В.Титов // Системный анализ, управление и обработка информации: 1-й межвуз. сб. науч. ст. / ДГТУ; ТТИ ЮФУ. - Ростов н/Д, 2007.
3. Романовский И.В. Алгоритмы решения экстремальных задач.
/ И.В.Романовский. - М.: Наука, 1977.
4. Кобак В.Г.. Анализ работы алгоритма Романовского с использованием разных подходов к формированию верхней и нижней границ
/ В.Г.Кобак, Д.В.Титов // Сб. тр. МНК ММТТ-20. Т.2. Ярославль: ЯГТУ, 2007.
5. Кобак В.Г. Анализ подходов к улучшению результатов работы
генетического алгоритма при решении однородной минимаксной задачи
/ В.Г.Кобак, Д.В.Титов // Проблемы информатики в образовании, управлении, экономике и технике // Сб. ст. VIII Всерос. науч.-техн. конф. - Пенза,
2008.
Материал поступил в редакцию 23.05.09.
V.G.KOBAK, D.V.TITOV
THE GENETIC APPROACH TO REDUCTION
OF THE OPERATING TIME OF EXACT ALGORITHM
ROMANOVSKIY IN HOMOGENEOUS SYSTEMS
This paper gives the estimation of exact algorithm Romanovskiy at use
as initial value of the top border of one updatings genetic algorithm. The given
approach leads to sharp reduction of time of reception of the exact decision, especially for dual-processor computing systems.
КОБАК Валерий Григорьевич (р.1961), докторант ДГТУ, кандидат технических наук. Окончил Новочеркасский политехнический институт (1983).
Научные интересы: методы решения экстремальных задач в однородных
вычислительных системах.
Автор более 70 научных работ.
ТИТОВ Дмитрий Вячеславович (р.1981), аспирант ДГТУ. Окончил магистратуру в ДГТУ (2005).
Научные интересы: методы решения минимаксной задачи в однородных
вычислительных системах точными и приближенными алгоритмами.
Автор более 8 научных работ.
29
Вестник ДГТУ, 2009. Спец. выпуск
titov_dima@mail.ru
30
Документ
Категория
Без категории
Просмотров
8
Размер файла
171 Кб
Теги
времени, алгоритмического, однородные, уменьшении, метод, точного, система, подход, работа
1/--страниц
Пожаловаться на содержимое документа