автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Модели и алгоритмы управления параллельным решением вычислительно трудоемких задач глобальной оптимизации

На правах рукописи

Сидоров Сергей Владимирович

МОДЕЛИ И АЛГОРИТМЫ УПРАВЛЕНИЯ ПАРАЛЛЕЛЬНЫМ РЕШЕНИЕМ ВЫЧИСЛИТЕЛЬНО ТРУДОЕМКИХ ЗАДАЧ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ

Специальность 05.13.01 - Системный анализ, управление и обработка информации (в науке и промышленности)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

16 МДІї ¿013

Нижний Новгород - 2013

005059096

005059096

Работа выполнена на кафедре математического обеспечения ЭВМ факультета вычислительной математики и кибернетики Нижегородского государственного университета им. Н.И. Лобачевского (национальный исследовательский университет)

Научный руководитель: доктор технических наук, профессор,

Гергель Виктор Павлович

Официальные оппоненты: Федосенко Юрий Семенович

доктор технических наук, профессор, Волжская государственная академия водного транспорта, кафедра «Информатика, системы управления и телекоммуникации», заведующий

Гай Василий Евгеньевич, кандидат технических наук. Нижегородский государственный технический университет им. Р.Е.Алексеева, кафедра «Вычислительные системы и технологии», доцент

Ведущая организация: Институт проблем передачи информации

РАН, г. Москва

Защита диссертации состоится « 23 » мая 2013 года в 13 часов в ауд. 1258 на заседании диссертационного совета Д 212.165.05 при Нижегородском государственном техническом университете им. P.E. Алексеева по адресу: 603950, г. Нижний Новгород, ул. Минина, 24.

С диссертацией можно ознакомиться в библиотеке Нижегородского государственного технического университета им. P.E. Алексеева

Автореферат разослан апреля 2013 года.

Ученый секретарь диссертационного совета

A.C. Суркова

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы диссертационной работы.

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

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

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

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

Как результат, можно говорить о том, что решение таких задач при реалистических временных затратах может осуществляться только при использовании высокого вычислительного потенциала современных суперкомпьютерных систем.

Ввиду сложности архитектуры современных многопроцессорных систем, классические последовательные математические алгоритмы и численные методы не

з

могут эффективно использовать их вычислительный потенциал, так как основаны на строго последовательном порядке вычислений. Таким образом, возникает проблема разработки эффективных алгоритмов не только для реализации собственно параллельных вычислений, но и управления ими.

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

Отметим работы Батищева Д.И., Васильева Ф.П., Гергеля В.П.,

Гришагина В.А., Евтушенко Ю.Г., Жилинскаса А.Г., Карманова В.Г., Коротченко А.Г , Неймарка Ю.И., Пиявского С.А., Сергеева Я.Д., Стронгина Р.Г., Сухарева А.Г. и др. Среди зарубежных ученых можно выделить Brent R., Pardalos Р, Pinter J., Tuy H., Hansen E., Horst, R. и др.

Данная работа выполняется в рамках информационно-статистической теории глобального поиска. Алгоритмы, развиваемые в рамках указанного подхода, основаны на предположении липшицевости всех функционалов задачи. В рамках информационно-статистической теории была разработана индексная схема учета ограничений (индексный метод). При этом допускается, что некоторые функционалы задачи определены не во всей области поиска (частичная вычислимость).

В обсуждаемом подходе есть еще одно важное принципиальное отличие: решение многомерных задач сводится к решению эквивалентных им одномерных задач (редукция размерности). Соответствующая редукция может быть основана на использовании разверток единичного отрезка вещественной оси на гиперкуб. Роль таких разверток играют непрерывные однозначные отображения типа кривой Пеано, называемые также кривыми, заполняющими пространство, и их обобщения, названные "множественными развертками". Эффективное использование аппарата таких отображений послужило основой для разработки перспективных параллельных численных методов глобальной оптимизации.

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

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

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

Методы исследования. Работа базируется на информационно-статистической теории глобального поиска, аппарате теории оптимизации, методах анализа алгоритмов, методах вычислительной математики, методах параллельных вычислений.

Научная новизна. При выполнении работы получены следующие основные новые результаты, выносимые на защиту:

- Сформулирована модель процесса параллельного глобального поиска и общая схема сведения сложных проблем оптимального выбора к серии информационно-связанных задач глобального поиска, решение которых может осуществляться параллельно;

- Предложен двухуровневый алгоритм управления параллельными вычислениями для глобальной оптимизации, позволяющий на уровне отдельных вычислительных узлов с общей разделяемой памятью исключить передачу данных, а на уровне всей вычислительной системы обеспечивающий асинхронное выполнение параллельных вычислений и балансировку вычислительной нагрузки;

- Предложена новая схема порождения множественных отображений для многомерных многоэкстремальных задач глобальной оптимизации на основе вращаемых разверток типа кривой Пеано, позволяющая задействовать при организации параллельных вычислений высокий вычислительный потенциал (сотни и тысячи процессоров) современных суперкомпьютерных систем;

- Разработаны модифицированные информационно-статистические алгоритмы глобального поиска, использующие новую схему порождения множественных отображений.

Практическая ценность работы составляет:

- Методика организации и управления параллельными вычислениями для разработанной схемы редукции размерности на основе вращаемых разверток может быть использована для решения других многомерных научно-технических задач из разных областей приложений.

- Разработанная программная система С1оЬа1ЕхреП+ может использоваться для параллельного решения сложных вычислительно-трудоемких задач многомерной многоэкстремапыюй оптимизации. Система применена на практике и внедрена в учебный процесс.

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

обеспечения, научной экспертизой на научных конференциях и при публикации в научной печати.

Внедрение результатов работы. Результаты работы нашли свое применение при выполнении проектов, выполняемых на факультете вычислительной математики и кибернетики ННГУ им. Н.И. Лобачевского при поддержке Российского фонда фундаментальных исследований (грант № 11-07-97017-р_поволжье_а), Совета по грантам Президента Российской Федерации (гранты № МК-1536.2009.9, HLII-64729.2010.9, НШ-1960.2012.9), ФЦП «Научные и научно-педагогические кадры инновационной России» (госконтракт №02.740.11.5018), ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007 - 2013 годы» (госконтракт № 11.519.11.4015). Результаты работы используются также в учебном процессе факультета вычислительной математики и кибернетики ННГУ им. Н.И. Лобачевского при чтении курсов «Модели и методы многоэкстремальной оптимизации», «Системы поддержки принятия решений».

Апробация работы. Результаты работы докладывались на международных конференциях «Высокопроизводительные вычисления на кластерных системах» (Нижний Новгород 2005, Санкт Петербург 2006, Нижний Новгород 2007, Казань 2008, Владимир 2009, Пермь 2010, Нижний Новгород 2011), «Параллельные вычислительные технологии» (Уфа 2010), Всероссийской конференции «Научный сервис в сети Интернет» (Новороссийск, 2008, 2010, 2012), научно-технических конференциях «Технологии Майкрософт в теории и практике программирования» (Нижний Новгород, 2006-2008), Всероссийской научно-технической конференции «Аэрокосмическая техника, высокие технологии и инновации», (Пермь, 2008, 2009), на научных конференциях и семинарах ННГУ им. Н.И. Лобачевского.

Публикации. Основное содержание диссертации изложено в работах [1]-[26] из них пять представлено в Перечне рецензируемых научных журналов1 [1]-[5].

Личный вклад соискателя. Постановка задач и методика исследования принадлежат руководителю. Соискателю принадлежит разработка модели процесса параллельного глобального поиска и новой схемы сведения сложных проблем оптимального выбора к серии информационно-связанных задач глобального поиска, двухуровневый алгоритм управления параллельными вычислениями, новой схемы множественной развертки, выполнение вычислительных экспериментов, обработка и интерпретация результатов.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы из 184 наименований. Основной печатный текст занимает 101 страницы.

1 Позиции 358,570,673 Перечня российских рецензируемых научных журнало» (http^/vak.ed.gov.ni/coiimwn/im^pk>aded/fi^^2013/eDumeriitioa/|w-25^5-2012^.docX

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении отражена актуальность задач глобальной условной оптимизации, определяются цели и задачи исследования, показана научная новизна и практическая ценность диссертационной работы.

В первой главе (Вычислительно трудоемкие задачи глобального поиска и современные методы их решения) приводятся примеры прикладных задач оптимизации (§ 1.1), рассматривается модель объекта глобально-оптимального выбора (§ 1.2) и методы поиска глобально оптимальных решений (§ 1.3), а также предлагается общая схема сведения сложных проблем оптимального выбора к серии информационно-связанных задач глобального поиска, решение которых может осуществляться параллельно (§ 1.4).

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

В § 1.2 представлена математическая модель объекта глобально-оптимального выбора, описывающая широкий класс постановок многокритериальных многомерных задач условной оптимизации с невыпуклыми ограничениями.

Пусть объект исследования характеризуется набором параметров

У = (Ук —«У«) (1)

и вектор-функцией характеристик

w(y) = (wt (у),..., w„ (у)) (2)

определенных таким образом, что уменьшение значений характеристик соответствует лучшему выбору. При этом предполагается, что координаты вектора у могут непрерывно изменяться в заданных пределах гиперинтервала D, а каждая характеристика wf(y), 1 < i <п, является липшицевой функцией с соответствующей константой Липшица, которая может быть не задана.

В отношении части координатных функций Wj из (2), номера которых определяются множеством С, ставится условие уменьшения их значений до некоторых заданных допусков qit т.е. на возможные значения набора у из (1) накладываются функциональные ограничения

Wf(y) < qui 6 G,G с (1, ...,п).

Часть координатных функций (2), номера которых определяются множеством F рассматривается как векторный критерий эффективности

/(у) = (А (у)...../к(у)). О)

где

fj(y) = Wj-(y), У е F, F с {1.....П). (4)

Принимается, что каждая функция giiy) = Wj(y) — qi, 1 < i < т определена и вычислима лишь в соответствующем множестве Qit где

Ol = D.Qi+i = {у е Qi'.gify) < 0},1 < i < т. (5)

7

Будем рассматривать задачу рационального выбора Ф(у), включающую в себя построение 5 оптимальных точек (каждая из которых оптимальна либо по Парето, либо по Слейтеру). Для этого необходимо задать 5 векторов Xе, 0 < с < 5

Xе еЛ, А1 = {Дс},0 < с < б (6)

которые порождают 5 однокритериапьных задач минимизации вида:

„п 1(Г)С= ш1п (шахЯ/ЛСу))) я (7)

((ГПс = М(у'У),1<1<к)

Указанный оптимальный выбор (парето-оптимальная, либо слейтер-оптимальная точка) для заданного набора Xе, 0 <с<б соответствует вектору (у')с, который является решением задачи (у).

Таким образом, Ф(у) может быть записана как набор задач глобальной оптимизации (7).

Ф(У) = (8)

Решением задачи рационального выбора (8), является множество точек У.

Г = {(У')1,(У*)2.....(У')1}- (9)

Набор задач (8), решение которых дает набор из оптимальных вариантов (9),

может решаться параллельно, так как задачи независимы. Более того, поисковая информация, получаемая в ходе вычислений при решении всех задач, может быть использована для повышения эффективности решения каждой задачи семейства (8) -см. далее § 1.4.

В § 1.3 представлен обзор методов поиска глобально оптимальных решений, особое внимание уделено современным параллельным алгоритмам.

В § 1.4 сформулирована модель процесса параллельного глобального поиска и общая схема сведения сложных проблем оптимального выбора к серии информационно-связанных задач глобального поиска, решение которых может осуществляться параллельно.

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

Для заданной точки испытания у обозначим через ш пару из вектора у и значений характеристик в этой точке н^ (у ),..., (у ).

со(у) = (у,и'(у)) (10)

Таким образом, в процессе решения конкретной каждой задачи 1 < с < 5 происходит накопление множества

Яс№) = {<^(&):0<1<&},1<с<5. (И)

При одновременном решении нескольких задач оптимизации накопленные данные при решении каждой из задач можно использовать при решении других задач. В § 1.4 предложен способ взаимного использования и пополнения поисковой информации между отдельными задачами и /у, ( Ф ) при параллельном решении задачи рационального выбора Ф(у)- см. рис. 1.

Задачи

Поисковая информация

Взаимное пополнение, взаимное использование

0 а

п,

л

а 0

а

• • •

• • •

а

а

Рис 1. Информационная связанность задач оптимизации при решении задачи рационального выбора

Далее на основе схемы редукции размерности в § 1.4 построен набор множественных отображений каждой многомерной задачи 1 ^ с < 5, из (7) к Ъ одномерным

П = (уЧ*). ....У1 (Ж)}, 1 < с < 5 . (12)

Данные отображения порождают (для каждой многомерной задачи 1 < с < в) Ь вспомогательных информационно-связанных одномерных задач 1 < с < 5, О < к < I.

^с-*)) = 6 [т^Х1)<0,1 <; < ш\

(13)

0<к<Ь, 1<С<Б,

где <Рс(у) = тах А.-Л (у), 1 < с < х.

В процессе решения каждой задачи <р* происходит накопление множества

%к(<Рс) = ((У. и'(ук(х'))): 0<1<г}, 1<с<5 (14)

где г - число выполненных итераций поисковым методом.

Так как для каждой из задач 1 ^ с < 5, при решении задачи рационального выбора Ф(у) порождается семейство эквивалентных ей задач <р}, ...,<рс, то в работе построена 2-х уровневая модель информационной связанности процесса параллельного глобального поиска - см. рис. 2.

Задачи (уровень 1).

Подзадачи (уровень 2)

Поисковая информация

Взаимное пополнение, взаимное использование на уровне подзадач

И

® И д д

••И

л

[уГ

д

с

о-

Д

• •

0

м ы

д д

''V . * |

Д д

И 1

Рис 2. 2-х уровневая модель информационная связанности задач при решении задачи рационального выбора.

На первом уровне располагаются задачи Рс, 1 < с < э, а на втором уровне вспомогательные одномерные подзадачи ср£, ..., <Рс> 1 < с < б. Из рис. 2 видно, что, как и в процессе параллельного решения подзадач <р..., происходит обмен поисковой информацией, так и при параллельном решении задач Рс,. 1 < с < б. Таким образом, вся накопленная информация используется максимально возможным способом, что существенно повышает эффективность решения задачи рационального выбора с использованием параллельных вычислений.

Во второй главе (Методика организации параллельных вычислений на основе множественных схем редукции размерности) рассматривается способы сведения многомерной задачи оптимизации к семейству одномерных задач (§§2.1-2.2) и предлагается новая схема построения множественных отображений . на основе вращения исходной развертки (§ 2.3).

В § 2.1 описываются способы сведение многомерной задачи оптимизации к семейству одномерных задач. Один из важных активно используемых подходов -редукция размерности.

В работе используется подход к редукции, основанный на использовании отображений, называемых кривыми (развертками) Пеано, которые сопоставляют любой липшицевой в гиперкубе Р = {и е Д": -2"1 <vi< 2'1,1 < I < АО многомерной функции <р(у) одномерную функцию <рСУ(х)), удовлетворяющую на отрезке [0, 1] равномерному условию Гельдера с показателем 1//У:

ю

КуОО)-*(уОО)| * *1Щх'-х\У»,х\х 6 [ОД]. (15)

При численном построении развертки задается точность М, которая определяет максимальную погрешность оценки каждой координаты функции <р(у), равную 2~(м+1) Алгоритмы построения точек кривой сопоставляют равномерной с шагом 2"мм сетке на отрезке [0, 1] равномерную с шагом 2"м сетку в гиперкубе Р.

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

В § 2.2 рассматривается разработанный в рамках информационно-статистической теории способ построения серии отображений, называемый сдвиговая развертка. Такая развертка позволяет естественным образом организовать параллельную схему поиска глобального оптимума, используя для расчетов с каждой из Ь разверток отдельный процессор. Однако параллелизм в этом случае ограничен условием, которое накладывает приближенное построение каждой отдельной развертки, -+1 <= М. Это ограничение существенно сужает возможность применения параллельных вычислений. Для преодоления вышеописанного недостатка

§ 2.3 предложена новая схема построения семейства множественных разверток, называемая вращаемая развертка и рассматриваются вопросы построения вращаемой развертки, дается оценка меры близости точек и оценка применимости для организации параллельных вычислений.

Примем, что развертка у°(х) типа кривой Пеано отображает отрезок [0,1] на гиперкуб £).

0 = {у°(*):*е[0,1]}. (16)

Тогда вращаемые развертки у1(_х), могут быть построены путем умножений каждой точки исходной развертки у°(х~) на матрицу К, поворота в многомерном пространстве на углы кратные я/2.

у'Сх) =у°(х) *Я„1<1<1 (17)

Так, например, матрицы поворота на углы ±я/2 и л в 2х мерном пространстве имеют вид:

Яг — ^ ^ поворот на угол я/2,

Л2 = ( д) поворот на угол-л/2,

й3 = ( * ^ поворот на угол я.

При этом матрица поворота на Я,- в Л'-мерном пространстве строится путем замены двух единиц на диагонали, соответствующей 2-м координатам по одному из правил в (18)-(20).

Максимальное число различных поворотов развертки, отображающей /У-мерный гиперкуб на одномерный отрезок, составляет 2("~1) • N. так как из каждой точки многомерного гиперкуба (а их 2") можно начать построение развертки, причем конечная точка может быть выбрана по любому из направлений N. при этом считаем за одну те развертки, у которых начало и конец отрезка меняются местами.

Утверждение. При использовании вращаемых разверток найдется отображение у'(х), которое точкам многомерного пространства у', у", которым при исходном отображении соответствовали наиболее удаленные прообразы на отрезке [0,1]. будет сопоставлять более близкие прообразы х', х" - см. рис. 3.

п

--*

Рис.3. Уменьшение расстояния при вращаемой развертке между близкими точками в пространстве

При использовании вращаемых разверток максимальное число построенных информационно-связанных задач зависит только от размерности пространства поиска, так это напрямую связано с числом всевозможных поворотов. Таким образом, при решении 5-мерной задачи можно использовать до 80-ти вычислительных узлов, 7 - 222, а 10-мерной - 5120, и т.д. .

Другим преимуществом является то, что при использовании вращаемых разверток не требуется введение дополнительного ограничения на попадание в область D, что требовалось при использовании сдвиговых разверток.

Заметим, что в случае, когда число свободных вычислительных узлов к меньше максимального возможного количества разверток, т.е.

к<1, (21) то при решении исходной задачи можно выбрать различные комбинации из всевозможных вращений разверток размера к из (21).

#00 = {у^х).....?£(*)} (22)

Yfc) = {у*«.....у£ (*)}

В работе предлагаются различные стратегии к построению комбинаций вращаемых разверток.

В третьей главе (Алгоритмы управления и программные средства параллельной глобальной оптимизации) предлагается новый двухуровневый алгоритм управления параллельными вычислениями для индексного метода глобального поиска (§ 3.2), учитывающий особенности иерархической архитектуры современных кластерных систем (набор многоядерных процессоров, соединенных локальной сетью), и рассматривается способ повышения точности вычислений в задачах высокой размерности при использовании разверток типа кривой Пеано (§ 3.3). В главе также представлено описание архитектуры программного комплекса параллельных вычислений в задачах глобально-оптимального выбора GlobalExpert+ (§ 3.4), в

12

котором реализованы разработанные в рамках диссертационной работы методы глобальной оптимизации.

В § 3.1 дается описание индексного алгоритма глобальной оптимизации. В § 3.2 представлено описание разработанного двухуровневого алгоритма управления параллельными вычислениями на основе индексного алгоритма глобальной оптимизации.

Схема алгоритма на межпроцессорном уровне

Использование множественных отображений позволяет решать отдельную задачу 1 < с < 5 из набора (7) путем параллельного решения Ь одномерных задач <рк,1 < с < 5, 0 < к < Ь из (13) на наборе отрезков [0,1]- Каждая одномерная задача <рк решается на отдельном процессоре с использованием развертки у*, 1 < 5 < I. Результаты испытания в точке хк, полученные конкретным процессором для решаемой им задачи, интерпретируются как результаты испытаний во всех остальных задачах (в соответствующих точках хк1, — ,хк1) и рассылаются другим процессорам

При таком подходе испытание в точке х"е[0,1], осуществляемое в 5-й задаче, состоит в последовательности действий:

1. определить образ ук = при соответствии у*(х);

2. проинформировать остальные процессоры о начале проведения испытания в точке ук (блокирование точки укУ,

3. провести испытание в точке у к\

4. определить прообразы хы е[0Д], 1<1<1,точки у\ и интерпретировать

испытание, проведенное в точке ук ей, как проведение испытаний в Ь точках

„к1 Гк1 Л , ••• , Л г

с одинаковыми результатами;

5. проинформировать остальные процессоры о результатах испытания в точке ук, разослав им результаты испытания - см рис. 4 (для случая N=2, ¿=2, М=2).

Процессор 1

Процессор 2

Процессор 3

Процессор 4

□ С

Обмен данными

Рис 4. Схема алгоритма на межпроцессорном уровне

Каждый процессор выполняет поиск глобального оптимума независимо на выделенной ему развертке. Этот процесс представляет собой последовательность итераций, состоящих из испытаний в различных точках области, а так же приема и отсылки посчитанной поисковой информации другим узлам.

Данная схема организована асинхронно. Предположение длительности вычисления функционалов в прикладных задачах позволяет разбить пересылки данных на каждой итерации на два шага:

• первый - пересылка найденной координаты точки испытания с признаком блокирования, что дает процессам возможность не выбирать одни и те же точки и

гарантирует от использования интервалов, на одном из концов которых не вычислено значение функции;

• второй - пересылка точки после вычисления в ней значений функционалов задачи.

Схема алгоритма иа уровне отдельного процессора

При решении задачи <р£ на отдельном процессоре на каждой итерации поиска происходит выбор нескольких наилучших интервалов и параллельного проведения испытаний (вычисления критериев задачи) на отдельных вычислительных ядрах - см рис. 5 (для случая использования 4-х вычислительных ядер).

Будем считать, что вычислительный процессор имеет р ядер, тогда итерация алгоритма на отдельном вычислительном процессоре состоит в следующем:

1. выбрать р наилучших интервалов;

2. выбрать р точек для проведения испытаний;

3. проинформировать остальные процессоры о блокировке р точек;

4. выполнить параллельно испытание в этих точках на р ядрах;

5. присоединить р новых точек к поисковой информации V;

6. проинформировать остальные процессоры о результатах испытания в точке.

Выбор нескольких наилучших интервалов на итерации

Х„ = 0 Х2 Х3 X*-s **-4 хк-3 хк-2 хк-1 хк ~ 1

Выбор нескольких точек I \

испытаний «»••"• ».....<•—•• »-----—•

*1 Хг Х3 xl х3 __. Щ **-3 xt Xfc-2

Параллельноевьшолнение -4._A- _ _

испытаний xj xj *з х*

• • • •

Ядро 1 Ядро 2 ЯдроЗ Ядро 4

Рис 5. Схема алгоритма на уровне отдельного процессора

В § 3.3 описывается способ оптимизации вычислений при поиске глобального оптимума за счет эффективного использования чисел расширенной точности.

Алгоритм построения кривой Пеано в случае, когда размерность пространства равна N при точности развертки М, соответствующей разбиению пространства на 2м частей по каждой координате, осуществляет деление отрезка [0, 1] на 2NM частей и устанавливает соответствие каждой их этих частей гиперкубу в внутри D.

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

N • М < 52, (23)

где N- размерность области D, а М - точность построения развертки.

Для снятия требования (23) и преодоления, тем самым, ограничения на размерность решаемых задач в диссертационном исследовании предлагается использовать числа расширенной точности, поддерживаемые программным образом,

14

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

В результате выделения необходимого количества операций в расширенной точности временные затраты на их использование удалось сократить с 500 до 5 раз по сравнению с обычной точностью.

В § 3.4 представлено описание архитектуры программного комплекса С1оЬа1ЕхрегН- для решения вычислительно-трудоемких задач глобально-оптимального выбора (1)-(9), в котором реализованы разработанные в рамках диссертационной работы алгоритмы многоэкстремальной оптимизации.

Базовым алгоритмом, используемым в комплексе, является двухуровневый алгоритм управления параллельными вычислениями на основе индексного метода с вращаемыми развертками, который запускается исполнение на многопроцессорной многоядерной вычислительной системе.

Разработанный программный комплекс параллельных вычислений для решения задач глобально-оптимального выбора имеет три режима запуска:

• запуск поиска из графического приложения с возможностью визуализации процесса поиска;

• запуск поиска из системы управления кластером через консольное приложение;

• запуск расчетного модуля комплекса в качестве оптимизационного компонента в прикладных пакетах моделирования, решающих задачи, в которых поиск оптимального выбора является лишь одним из этапов.

Архитектура комплекса включает два уровня: системный и прикладной (рис. б).

Рис. б. Архитектура программного комплекса 01оЬа1ЕхрегН-

В четвертой главе (Анализ эффективности алгоритмов управления параллельным глобальным поиском и решение задач глобальной оптимизации) производится анализ эффективности предложенных алгоритмов (§§ 4.2-4.4) , а также их применение для решения тестовых и прикладных задач (§ 4.5). В § 4.1 описывается методика сравнения поисковых алгоритмов с использованием операционных характеристик. Операционная характеристика метода представляет собой набор пар:

1<к,р(к)>],

где к есть количество итераций поиска, а р(к) есть доля успешно решенных задач тестового класса за указанное количество итераций. Подобные показатели могут быть рассчитаны по результатам экспериментов и показаны графически в виде графика кусочно-ломаной линии. Сравнение различных стратегий выбора последовательностей вращаемых разверток представлено в § 4.2.

В § 4.3 дается оценка эффективности индексного метода с вращаемой разверткой. Для сравнения эффективности индексного метода с другими алгоритмами был выбран известный алгоритм глобальной оптимизации DIRECT и его модификация LBDIRECT (locally-based DIRECT).

В § 4.4 представлена оценка масштабируемости параллельного двухуровневого индексного алгоритма. Оценка эффективности использования расширенной точности дается в § 4.5. Вычислительные эксперименты проводились на наборе задач из 100 функций, полученных с помощью генератора GKSL._

Операционные характеристики

Количество итераций метода

О о о

о о см

о о ■ч-

о о со

о о СО

о о о см

о о о

Обычная точность

-Расширенная точность

ООО ООО ООО

С0 со о

-- СП

Рис 7. Операционные характеристики индексного метода при использовании расширенной и обычной точности

Из рис. 7 видно, что при одинаковом числе выполненных итераций доля успешно решенных задач индексным методом с использованием чисел расширенной точности существенно больше по сравнению с методом, использующим обычную точность.

В § 4.6 описывается применение предложенных алгоритмов для решения прикладных задач. В диссертационном исследовании проводилось решение задачи идентификации многосекторной модели региональной экономики на данных Нижегородской области, разработанной в Вычислительном центре им. А.А.Дородница РАН (ВЦ РАН). В общем виде задача идентификации математической модели состоит в поиске ее неизвестных параметров из оптимальных соотношений, отражающих степень близости расчётных и реальных (статистических) данных. Возникающая здесь задача оптимизации является вычислительно трудоемкой и многоэкстремальной.

В заключении сформулированы основные результаты диссертационной работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Сформулирована модель процесса параллельного глобального поиска, и общая схема сведения сложных проблем оптимального выбора к серии информационно-связанных задач глобального поиска, решение которых может осуществляться параллельно;

2. Предложен двухуровневый алгоритм управления параллельными вычислениями для глобальной оптимизации, позволяющий на уровне отдельных вычислительных узлов с общей разделяемой памятью исключить передачу данных, а на уровне всей вычислительной системы обеспечивающий асинхронное выполнение параллельных вычислений и балансировку вычислительной нагрузки;

3. Предложена новая схема порождения множественных отображений для многомерных многоэкстремальных задач глобальной оптимизации на основе вращаемых разверток типа кривой Пеано, позволяющая задействовать при организации параллельных вычислений высокий вычислительный потенциал (сотни и тысячи процессоров) современных суперкомпьютерных систем;

4. Разработаны модифицированные информационно-статистические алгоритмы глобального поиска, использующие новую схему порождения множественных отображений;

5. Разработана программная система ОІоЬаІЕхрегн- для параллельного решения вычислительно-трудоемких задач многомерной многоэкстремальной оптимизации.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

Публикации в рецензируемых журналах

1. Сидоров, C.B. Параллельные методы решения задач глобальной оптимизации [Текст] / К.А. Баркалов, В.В. Рябов, C.B. Сидоров // Вестник Нижегородского университета им. Н.И. Лобачевского. — Н.Новгород : Издательство Нижегородского госуниверситета, 2009. №6(1). С. 171-177.

2. Сидоров, C.B. О некоторых способах балансировки локального и глобального поиска в параллельных алгоритмах глобальной оптимизации [Текст] / К.А. Баркалов, В.В. Рябов, C.B. Сидоров // Ж. Вычислительные методы и программирование. Т.П. 2010. С. 382-387.

3. Сидоров, C.B. Параллельные методы глобальной оптимизации в идентификации динамической балансовой нормативной модели региональной экономики [Текст] / В.П. Гергель, В.А. Горбачев, H.H. Оленев, В.В. Рябов, C.B. Сидоров II Вестник Южно-Уральского государственного университета. — Челябинск : Издательство Южно-Уральского государственного университета, №25 (242), 2011. С.4-15. (Сер. "Математическое моделирование и программирование", вып.9.)

4. Сидоров, C.B. Параллельные алгоритмы глобальной оптимизации с использованием разверток растущего уровня детализации. [Текст] / C.B. Сидоров, В.В. Рябов // Вестник Нижегородского университета им. Н.И. Лобачевского. — Н.Новгород : Издательство Нижегородского госуниверситета, 2011. N3(2). С. 127-133.

5. Сидоров, C.B. Параллельный двухуровневый индексный алгоритм глобальной оптимизации [Текст] / C.B. Сидоров // Вестник Нижегородского университета им. Н.И. Лобачевского. — Н.Новгород : Издательство Нижегородского госуниверситета, 2012. №5(2), С. 206-211.

Статьи в журналах и трудах научных конференций

6. Сидоров, C.B. Интерактивное управление параллельными вычислениями при решении задач многомерной многоэкстремальной оптимизации [Текст] / В.В. Рябов, C.B. Сидоров, A.B. Сысоев // Материалы международной конференции «Высокопроизводительные параллельные вычисления на кластерных системах»: — Н.Новгород : Издательство Нижегородского госуниверситета,, 2007, стр. 294-298.

7. Сидоров, C.B. Использование чисел расширенной точности в параллельных алгоритмах глобально-оптимального поиска [Текст] / C.B. Сидоров, A.B. Сысоев // Материалы международной конференции «Высокопроизводительные вычисления на кластерных системах»:изд-во Нижегородского гос. ун-та, 2005, стр. 233.

8. Сидоров, C.B. О распараллеливании индексного метода глобально-оптимального поиска [Текст] / C.B. Сидоров, A.B. Сысоев, В.П. Гергель // Материалы конференции «Технологии Microsoft в теории и практике программирования». — Н.Новгород : Издательство Нижегородского госуниверситета,, 2006 с. 273.

9. Сидоров, C.B. Распараллеливание индексного метода поиска глобально-оптимальных решений с использованием технологий MPI и ОрепМР [Текст] / C.B. Сидоров, A.B. Сысоев II Материалы сессии молодых ученых, Семенов, 2006, стр. 21.

10. Сидоров, C.B. Реализация схемы остановки и возобновления счета в параллельном индексном методе поиска глобально-оптимальных решений [Текст] / C.B. Сидоров, A.B. Сысоев // Материалы международной конференции «Высокопроизводительные вычисления на кластерных системах», Санкт Петербург, 2006, стр. 159-163.

П.Сидоров, C.B. Реализация поддержки страничной памяти в алгоритмах поиска глобально-оптимальных решений [Текст] I Е.В. Субботина, C.B. Сидоров, В.П. Гергель // Материалы конференции «Технологии Microsoft в теории и практике программирования». — Н.Новгород Издательство Нижегородского госуниверситета, 2007, с. 279.

12.Сидоров, C.B. Общая схема реализации остановки и возобновления счета индексного метода поиска глобально-оптимальных решений [Текст] / C.B. Сидоров, A.B. Сысоев // Материалы конференции «Технологии Microsoft в теории и практике программирования». — Н.Новгород : Издательство Нижегородского госуниверситета, 2007, с. 259.

13.Сидоров, C.B. Эффективные параллельные алгоритмы и программные средства поиска глобально-оптимальных решений в многомерных многоэкстремальных задачах [Текст] / C.B. Сидоров, A.B. Сысоев, В.В. Рябов // Материалы международной конференции «Высокопроизводительные параллельные вычисления на кластерных системах». — Н.Новгород : Издательство Нижегородского госуниверситета, 2007, стр. 302-305.

14. Сидоров, C.B. Об опыте решения задач многоэкстремальной оптимизации на высокопроизводительных кластерных системах [Текст] / К.А. Баркалов, В.В. Рябов, C.B. Сидоров, A.B. Сысоев // Материалы XI всероссийской научно-технической конференции «Аэрокосмическая техника, высокие технологии и инновации», Пермь 2008: Изд. ПГТУ, 2008, стр. 36-39.

15. Сидоров, C.B. Решение задач многомерной многоэкстремальной оптимизации с использованием высокопроизводительных кластерных систем [Текст] / C.B. Сидоров, В.В. Рябов // Материалы всероссийской конференции «Научный сервис в сети Интернет: технологии параллельного программирования»,Новороссийск, 2008: М. Изд-во МГУ 2008, стр. 342-344.

16. Сидоров, C.B. Исследование методов глобальной оптимизации на некоторых классах многоэкстремальных задач [Текст] / К.А. Баркалов, C.B. Сидоров, В.В. Рябов // Материалы международной конференции «Высокопроизводительные параллельные вычисления на кластерных системах», Казань, 2008.

17.Сидоров, C.B. Об опыте решения задач многоэкстремальной оптимизации на высокопроизводительных кластерных системах [Текст] / К.А. Баркалов, В.В. Рябов, C.B. Сидоров, A.B. Сысоев // Материалы конференции «Технологии Microsoft в теории и практике программирования». — Н.Новгород : Издательство Нижегородского госуниверситета, 2008, стр. 21-25.

18. Сидоров, C.B. Параллельные методы решения задач многомерной глобальной оптимизации [Текст] / В.П. Гергель, К.А. Баркалов, C.B. Сидоров // Материалы конференции «Технологии Microsoft в теории и практике программирования». — Н.Новгород : Издательство Нижегородского госуниверситета, 2009.

19.Сидоров, C.B. Параллельные вычисления для задач глобальной оптимизации [Текст] / В.П. Гергель, К.А. Баркалов, C.B. Сидоров // Материалы XII всероссийской научно-технической конференции «Аэрокосмическая техника, высокие технологии и инновации». Пермь 2009, Изд. 111 "ГУ, 2009, стр. 240-243.

20. Сидоров, C.B. Использование кривых Пеано в параллельной глобальной оптимизации [Текст] / К.А. Баркалов, В.В. Рябов, C.B. Сидоров // Материалы Девятой международной конференции-семинара "Высокопроизводительные параллельные вычисления на кластерных системах". Владимир, 2009: Изд. ВТУ 2009, Стр. 44 - 47.

21. Сидоров, C.B. Масштабируемые параллельные алгоритмы глобальной оптимизации со смешанной локально-глобальной стратегией [Текст] / К.А. Баркалов, В.В. Рябов, C.B. Сидоров // Материалы международной конференции «Параллельные вычислительные технологии» Уфа, 2010:. Челябинск: Издательский центр ЮУрГУ 2010. С. 402-409.

22. Сидоров, C.B. О некоторых способах балансировки локального и глобального поиска в параллельных алгоритмах глобальной оптимизации [Текст] / К.А. Баркалов, В.В. Рябов, C.B. Сидоров // Материалы международной конференции «Научный сервис в сети Интернет: суперкомпьютерные центры и задачи». Новороссийск, 2010. - Изд-во МГУ 2010, С. 188-192.

23.Сидоров, C.B. Оценки эффективности параллельного индексного метода глобальной оптимизации [Текст] / К.А. Баркалов, В.В. Рябов, C.B. Сидоров // Материалы Десятой международной конференции-семинара "Высокопроизводительные параллельные вычисления на кластерных системах", Пермь 2010: Изд. ПГТУ, 2010. С. 62-70.

24.Сидоров, C.B. Parallel scalable algorithms with mixed local-global strategy for global optimization problems [Текст] / Barkalov K., Ryabov V., Sidorov S., // MTPP'10 Proceedings of the Second Russia-Taiwan conference on Methods and

tools of parallel programming multiComputers, Springer-Verlag Berlin, Heidelberg ©2010, p. 232-240

25. Сидоров, C.B. Современные параллельные алгоритмы глобальной оптимизации [Текст] / C.B. Сидоров // Материалы Одиннадцатой международной конференции-семинара "Высокопроизводительные параллельные вычисления на кластерных системах", — Н.Новгород : Издательство Нижегородского госуниверситета, 2011. С. 287-291.

26. Сидоров, C.B. Глобальная оптимизация в идентификации многосекторной модели экономики Нижегородской области [Текст] / В.П. Гергель, H.H. Оленев, К.А. Баркалов, В.В. Рябов, C.B. Сидоров // Материалы международной конференции «Научный сервис в сети Интернет: поиск новых решений», Новороссийск, 2012. - М.: Изд-во МГУ, 2012. С.79-81.

Подписано в печать 16.04.2013. Формат 60x84'/16. Бумага офсетная. Печать офсетная. Уч.-изд. л. 1,0. Тираж 120 экз. Заказ 302.

Нижегородский государственный технический университет им. P.E. Алексеева.

Типография НГТУ. Адрес университета и полиграфического предприятия: 603950, г. Нижний Новгород, ул. К. Минина, 24.