Высокопроизводительные Параллельные Вычисления на Кластерных Системах Абсолют Эксперт программный комплекс параллельного решения задач многомерной многокритериальной оптимизации ННГУ им. Н.И. Лобачевского Сысоев А.В., Гергель В.П. 2002

Абсолют Эксперт ННГУ им. Н.И. Лобачевского Сысоев А.В.,Гергель В.П. 2 Класс задач Объект исследования характеризуется: набором параметров вектор-функцией характеристик Область параметров: вектор y из D = {y R N : a i y i b i, 1 i N} кортеж u принимает значения в виде набора дискретных параметров из некоторого множества Характеристики: В отношении части характеристик ставится условие уменьшения их значений до некоторых заданных допусков Часть характеристик рассматривается как векторный критерий эффективности Конкретная характеристика может принадлежать обеим частям одновременно

Абсолют Эксперт ННГУ им. Н.И. Лобачевского Сысоев А.В.,Гергель В.П. 3 Класс задач

Абсолют Эксперт ННГУ им. Н.И. Лобачевского Сысоев А.В.,Гергель В.П. 4 Подход Предположение: упорядоченность частных критериев эффективности, составляющих векторный критерий, по важности Схема: минимизируется первый по важности частный критерий назначается величина допустимого увеличения его значения ищется минимальное значение второго критерия (с учетом допуска, наложенного на первый)

Абсолют Эксперт ННГУ им. Н.И. Лобачевского Сысоев А.В.,Гергель В.П. 5 Схема решения Минимизация критерия многомерный критерий эффективности редуцируется к семейству скалярных одномерных однокритериальных задач понижение размерности осуществляется с помощью разверток (кривые Пеано) для сохранения информации о близости точек в многомерном пространстве используется множественная развертка дальнейший выбор оптимального варианта строится с использованием эффективных алгоритмов глобального поиска из класса характеристически-представимых

Абсолют Эксперт ННГУ им. Н.И. Лобачевского Сысоев А.В.,Гергель В.П. 6 Множественная развертка приводит к появлению семейства из L+1 одномерной задачи оптимизации каждая из задач определена на [0, 1] испытание (вычисление функционалов) в любой из задач – испытание для каждой задачи семейства

Абсолют Эксперт ННГУ им. Н.И. Лобачевского Сысоев А.В.,Гергель В.П. 7 Параллельная схема вычислений Предпосылки существенно различные времена испытаний разнотипность процессоров Подход Необходима асинхронная схема проведения расчетов

Абсолют Эксперт ННГУ им. Н.И. Лобачевского Сысоев А.В.,Гергель В.П. 8 Параллельная схема вычислений Схема итерации поиска поиск очередной точки испытания перед началом выполнить прием информации от других процессоров выполнение испытания - инициировать рассылку информации о точке испытания с признаком - блокирования - выполнить итерацию - инициировать повторную рассылку с информацией о результатах вычислений обновление поисковой информации

Абсолют Эксперт ННГУ им. Н.И. Лобачевского Сысоев А.В.,Гергель В.П. 9 Абсолют Эксперт Оптимизация Очередь характеристик Страничная память Поисковая информация Обработка состояний Архив Функциональная структура комплекса Абсолют Эксперт

Абсолют Эксперт ННГУ им. Н.И. Лобачевского Сысоев А.В.,Гергель В.П. 10 Подсистема Оптимизация Процесс оптимизации выполнение итераций поиска Задание ограничения, критерии Задача Задача область поиска Задача Задача фикс. параметры Задача Задача дискретный набор Объект оптимизации размерность, максимальная область поиска, функционалы

Абсолют Эксперт ННГУ им. Н.И. Лобачевского Сысоев А.В.,Гергель В.П. 11 Текущие результаты В настоящий момент: реализована вся необходимая функциональность подсистем –развертки, в том числе множественные –индексный метод –процесс оптимизации –параллельная схема вычислений создан макетный вариант комплекса

Абсолют Эксперт ННГУ им. Н.И. Лобачевского Сысоев А.В.,Гергель В.П. 12 Текущие результаты 2 процессора Точность К-во итераций Собств. итераций Время~0.60 c~14 c~90 c 1 процессор Точность К-во итераций Время~4.50 c~80 c-

Абсолют Эксперт ННГУ им. Н.И. Лобачевского Сысоев А.В.,Гергель В.П. 13 Литература 1. Strongin R.G., Sergeev Ya.D. (2000). Global optimization with non-convex constraints: Sequential and parallel algorithms. Kluwer Academic Publisher, Dordrecht. 2. Gergel V.P. A software system for multiextremal optimization // European Journal of Operation Research, v. 65, N 3, pp , 1993

Абсолют Эксперт ННГУ им. Н.И. Лобачевского Сысоев А.В.,Гергель В.П. 14 Подсистема Оптимизация Понятия: Процесс оптимизации – оперирует набором заданий, основанных на едином Объекте Объект оптимизации – критерии, размерность, максимальная область поиска, параметры Задание – объединение совместных (в смысле МСП) задач, метода и его параметров Задача – формируется на основе Объекта. Позволяет: –изменить (уменьшить) область поиска –зафиксировать часть конструктивных параметров ! На уровне Задания –определяются функционалы-ограничения и допуска для них –критерии эффективности и их порядок по важности