Стронгин Р.Г. Высокопроизводительные паралленльные вычисления на кластерных системах. 2003
.pdfD = {y R N : y j [a j ,b j ], 1 ≤ j ≤ N}, |
(2) |
в которой целевая функция f (y) является многоэкстремальной и удовлетворяющей условию Липшица. В задаче (1)–(2) требуется найти ее глобально-оптимальное решение.
Многоэкстремальные задачи оптимизации обладают высокой степенью вычислительной сложности, одним из основных факторов которой является размерность (количество варьируемых параметров). Для преодоления высокой трудоемкости многомерных многоэкстремальных задач используются различные подходы их редуцирования к более простым одномерным задачам [1,2]. Один из таких подходов основан на применении многошаговой схемы редукции размерности [1,2,4], согласно которой решение исходной задачи сводится к решению семейства рекурсивно связанных одномерных подзадач. Кратко опишем основную алгоритмическую идею многошаговой схемы редукции.
Введем для 1 ≤ i ≤ N–1 вектора ui = (y1,…, yi), vi = (yi+1,…, yN) и примем, что v0 = un = y. Затем, положив по определению f N(y) ≡ f(y),
построим семейство функций
f i (ui ) = min{ f i+1(ui , yi+1) : yi+1 Πi+1} , 1 ≤ i ≤ N −1 ,
определенных на соответствующих проекциях
Di ={y Ri : y j [a j , b j ], 1 ≤ j ≤ i} .
Тогда имеет место основное соотношение
min f ( y) = min min . . . |
min f ( y) , |
(3) |
|
y D |
y1 Π1 y2 Π2 |
yN ΠN |
|
где Πi =[ai , bi ] R1.
Как следует из (3), для решения задачи (1)–(2) достаточно решить одномерную задачу
f 1( y1) → min , y1 Π1 R1
При этом каждое вычисление функции f 1(y1) в некоторой фиксированной точке y1 П1 представляет собой согласно (3) решение одномерной задачи
f 2 ( y1, y2 ) → min , y2 Π2 R1
251
Эта задача является одномерной задачей минимизации по y2, т.к. y1 фиксировано.
В свою очередь, каждое вычисление значения функции f 2(y1, y2) при фиксированных y1, y2 требует решения одномерной задачи
f3 (u2 , y3 ) → min , y3 Π3 R1
ит.д. вплоть до решения задачи
f N (uN −1, yN ) = f (uN −1, yN ) → min , yN ΠN R1
при фиксированном uN–1.
Окончательно решение задачи (1)–(2) сводится к решению семейства "вложенных" одномерных подзадач
f i (ui−1, yi ) → min , yi Πi R1 , |
(4) |
где фиксированный вектор ui–1 D i–1.
Внастоящей работе рассматривается алгоритмическая схема [5], обеспечивающая параллельную реализацию многошаговой схемы
редукции размерности и позволяющая при решении многомерной задачи (1)–(2) использовать до 2N параллельно работающих процессоров.
Вкачестве тестового класса для проведения вычислительных экспериментов был выбран класс недифференцируемых многоэкстремальных функций нескольких переменных, предложенный
вработе [6]. Для функций данного класса, генерируемых случайно, известны координаты и значения глобального и всех локальных минимумов, причем возможно управление сложностью генерируемых функций посредством задания числа локальных минимумов и области притяжения глобального минимума.
Для решения одномерных подзадач оптимизации (4) использовались алгоритмы, относящиеся к классу параллельных характеристических методов [3], в которых параллелизм обеспечивается параллельным проведением испытаний (вычислений значений целевой функции). Для сравнения были выбраны две схемы распараллеливания. В синхронной схеме новая итерация (параллельное проведение испытаний несколькими процессорами) выполнялась после завершения всех параллельных процессов предшествующей ей итерации. В асинхронной реализации
252
освободившийся процессор получал координату нового испытания, не ожидая завершения работы других процессоров.
В эксперименте были рассмотрены двух-, трех- и четырехмерные задачи оптимизации (100 функций для каждой размерности). Результаты эксперимента подтвердили теоретические оценки высокой эффективности распараллеливания вычислений по многошаговой схеме, полученные в работе [4] и продемонстрировали существенное ускорение вычислений в асинхронной схеме в сравнении с синхронным параллелизмом.
Литература
1.Стронгин Р.Г. Численные методы в многоэкстремальных задачах. Информационно-статистический подход. М.: Наука, 1978.
2.Strongin R.G., Sergeyev Ya.D. Global optimization with nonconvex constraints: Sequential and parallel algorithms, Kluwer Academic Publishers, Dordrecht, Netherlands. 2000.
3.Strongin R.G., Sergeyev Ya.D., Grishagin V.A. Parallel
Characteristical Algorithms for Solving Problems of Global Optimization // Journal of Global Optimization,10, 1997. P. 185– 206.
4.Sergeyev Ya.D., Grishagin V.A. Parallel asynchronous global search and the nested optimization scheme, Journal of Computational Analysis & Applications, 3(2), 2001. P. 123–145.
5.Гришагин В.А., Филатов А.А. Параллельные рекурсивные алгоритмы многоэкстремальной оптимизации // Материалы второго Международного научно-практического семинара / Под ред. проф. Р.Г. Стронгина. Нижний Новгород: Изд-во Нижегородского госуниверситета, 2002. С. 88–90.
6.Gaviano M., Kvasov D.E., Lera D., Sergeyev Ya.D. Software for
Generation of Classes of Test Functions with Known Local and Global Minima for Global Optimization // (Принято к опубликованию в ACM Transactions on Mathematical Software).
253
СОДЕРЖАНИЕ |
|
Оргкомитет семинара................................................................................. |
4 |
Афанасьев К.Е., Демидов А.В. Портал поддержки параллельных |
|
вычислений...................................................................................... |
5 |
Банникова М.Н., Сивков Д.А. Использование OpenMP |
|
при расчете влияния денежной политики Центрального |
|
банка на производство .................................................................. |
12 |
Борец Т.В. Ассоциативная версия алгоритма поиска в глубину.......... |
17 |
Борисов Е.С. Декомпозиция последовательных программ при |
|
параллельных вычислениях.......................................................... |
25 |
Вшивков В.А., Неупокоев Е.В. Моделирование динамики |
|
гравитирующих систем на многопроцессорных системах....... |
29 |
Городничев М.А. APT − система параллельного |
|
программирования на основе языка с динамическими |
|
массивами. Подсистема поддержки времени исполнения......... |
37 |
Гергель В.П., Гришагин А.В. Реализация метода окрестностей в |
|
задачах распознавания образов с использованием XML |
|
Web Services и кластерных систем............................................... |
44 |
Гришагин В.А., Ленц Я.Г. Инструментальная система |
|
распределенной глобальной оптимизации.................................. |
47 |
Деменев А.Г. Лабораторный практикум спецкурса |
|
“Программирование для параллельных вычислительных |
|
систем” ........................................................................................... |
53 |
Заручевская (Лозинская) Г.В., Севостьянова О.В., |
|
Юфрякова О.А., Кожин И.Н. Мелкозернистый локально- |
|
параллельный алгоритм для четырехточечной неявной |
|
разностной схемы уравнения теплопроводности....................... |
59 |
Иванченко М.В., Канаков О.И., Мишагин К.Г., |
|
Шалфеев В.Д.Использование средств MPI в программной |
|
системе для моделирования динамики больших ансамблей |
|
нелинейных осцилляторов............................................................ |
64 |
Кузенков О.А., Ирхина А.Л., Жулин М. Параллельный алгоритм |
|
оптимизации на основе метода случайного поиска .................. |
68 |
Истомин Т.Е. ParaCon: cистема параллельного програм- |
|
мирования на типовых алгоритмических структурах................ |
70 |
254
Коробко А.Ю. О системе выявления параллелизма.............................. |
76 |
Кринов П.С., Якобовский М.В., Муравьёв С.В. Визуализация |
|
данных большого объёма в распределённых |
|
многопроцессорных системах...................................................... |
81 |
Кудерметов Р.К., Пиза Н.Д. Применение параллельных систем |
|
для моделирования в реальном времени..................................... |
89 |
Кузьминский М.Б., Михайлов М.Н. Cоздание кластерных |
|
ресурсов для химических исследований. Тестирование |
|
аппаратной платформы нового поколения для узлов ............... |
93 |
Кучин Н.В. Управление вычислительными ресурсами |
|
Высокопроизводительного Вычислительного Кластера |
|
МВС-1000/М Сибирского Суперкомпьютерного Центра.......... |
99 |
Лабутин Д.Ю. Система удаленного доступа к вычислительному |
|
кластеру........................................................................................ |
108 |
Лопатин И.В. Краткий обзор методов мониторинга состояния |
|
кластеров...................................................................................... |
110 |
Лучицкий Г. Моделирование и прогноз атмосферных процессов |
|
для региона................................................................................... |
116 |
Орлов В.С. Программная система исследования задач |
|
аппроксимации смешанного типа.............................................. |
122 |
Пиза Н.Д., Кудерметов Р.К. Применение кластерных |
|
систем для моделирования движения космического |
|
аппарата........................................................................................ |
127 |
Попов С.Б., Скуратов С.А. Пространственное и потоковое |
|
распараллеливание в технологиях обработки изображений |
|
скользящим окном....................................................................... |
135 |
Прилуцкий М.Х., Афраймович Л.Г. Параллельные структуры |
|
потоковых и итерационных алгоритмов распределения |
|
ресурса в иерархических системах........................................... |
140 |
Прилуцкий М.Х., Петри С.Ю. Распределение вычислительных |
|
ресурсов неоднородной кластерной системы........................... |
145 |
Селихов А.В. CMDE: динамическое программное окружение |
|
для отказоустойчивого выполнения MPI–программ на |
|
кластерах и сетях......................................................................... |
153 |
Снытников А.В. Моделирование динамики протопланетного |
|
диска на многопроцессорных вычислительных системах...... |
161 |
Сомов Н.В., Чупрунов Е.В. Распределённые вычисления |
|
псевдосимметрии кристаллов..................................................... |
167 |
|
255 |
Стронгин Р.Г., Гергель В.П. Параллельные вычисления |
|
в задачах выбора глобально-оптимальных решений для |
|
многопроцессорных кластерных систем................................... |
169 |
Суков С.А. Использование тетраэдрических сеток |
|
для моделирования обтекания тел на многопроцессорных |
|
системах ....................................................................................... |
191 |
Сысоев А.В. Программная система параллельных вычислений |
|
в задачах выбора глобально-оптимальных решений................ |
194 |
Тимошевская Н.Е. Разработка параллельных алгоритмов обхода |
|
дерева............................................................................................ |
198 |
Тырчак Ю.М. Об эффективном распараллеливании численных |
|
методов задач распространения примеси в атмосфере............ |
206 |
Уразов А.Р. APT – система параллельного программирования |
|
на основе языка с динамическими массивами. Концепция |
|
и язык............................................................................................ |
213 |
Фурсов В.А., Дроздов М.А. Декомпозиция по данным в задачах |
|
итерационной обработки изображений на |
|
многопроцессорных системах.................................................... |
221 |
Хохлов Н.Н., Кудерметов Р.К. Параллельная вычислительная |
|
система с распределением вычислительной нагрузки |
|
между узлами компьютерной сети............................................. |
227 |
Абросимова О.Н., Белов С.А., Сысоев А.В. Балансировка |
|
вычислительной нагрузки для параллельных алгоритмов |
|
на вероятностных сетях .............................................................. |
230 |
Виноградов Р.В., Гергель В.П., Сенин А.В. Масштабируемость |
|
параллельных алгоритмов на вероятностных сетях |
|
(на примере алгоритма Gibbs Sampling) .................................... |
234 |
Гергель А.В., Чернышова А.Н. Алгоритмы передачи сообщений |
|
в байесовых сетях и принципы их распараллеливания............ |
240 |
Гришагин В.А., Квасов Д.Е., Сергеев Я.Д. Cравнительная оценка |
|
эффективности синхронных и асинхронных рекурсивных |
|
алгоритмов глобальной оптимизации........................................ |
243 |
256