авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

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

Итерационные методы и алгоритмы решения задачи сильной отделимости

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

ЕРШОВА Арина Владимировна ИТЕРАЦИОННЫЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ СИЛЬНОЙ ОТДЕЛИМОСТИ 05.13.17 – теоретические основы информатики

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Челябинск – 2012

Работа выполнена на кафедре дифференциальных уравнений и динамических систем ФГБОУ ВПО «Южно-Уральский государственный университет» (национальный исследовательский университет) СОКОЛИНСКАЯ Ирина Михайловна

Научный консультант:

кандидат физ.-мат. наук, доцент доцент кафедры дифференциальных уравнений и дина мических систем, ФГБОУ ВПО «Южно-Уральский госу дарственный университет» (национальный исследова тельский университет) УХОБОТОВ Виктор Иванович

Официальные оппоненты:

доктор физ.-мат. наук, профессор зав.кафедрой теории управления и оптимизации, ФГБОУ ВПО «Челябинский государственный университет» ОЛЕНЕВ Николай Николаевич кандидат физ.-мат. наук, доцент старший научный сотрудник отдела «Математическое моделирование экономических систем», ФГБУН Вычис лительный центр им. А.А. Дородницына Российской ака демии наук (ВЦ РАН) Федеральное государственное бюджетное учреждение

Ведущая организация:

науки Институт математики и механики Уральского от деления Российской академии наук (ИММ УрО РАН) (г. Екатеринбург)

Защита состоится 15 июня 2012 г. в 12:00 часов на заседании диссертационного совета Д 212.298.18 при ФГБОУ ВПО «Южно-Уральский государственный университет» (национальный исследовательский университет) по адресу: 454080, г. Челябинск, пр. Ленина, 76, ауд. 1001.

С диссертацией можно ознакомиться в библиотеке Южно-Уральского государственного университета.

Автореферат разослан “_” 2012 г.

Ученый секретарь диссертационного совета М.Л. Цымблер

Общая характеристика работы

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

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

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

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

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

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

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

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

На базе данного подхода разработать масштабируемый метод решения задачи 2.

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

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

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

Спроектировать и реализовать программный комплекс для решения задачи силь 4.



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

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

Научная новизна работы заключается в следующем:

Предложен новый итерационный метод решения задачи сильной отделимости 1.

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

На основе предложенного метода разработан новый параллельный алгоритм, для 2.

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

Впервые выполнена реализация разработанного алгоритма решения задачи силь 3.

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

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

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

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

на Международной конференции «Алгоритмический анализ неустойчивых задач» (1–6 сентября 2008 г., г. Екатеринбург);

на Международной научной конференции «Параллельные вычислительные техно логии (ПаВТ’2010)» (29 марта – 2 апреля 2010 г., г. Уфа);

на XVIII Международной конференции «Математика. Экономика. Образование» (25 мая – 1 июня 2010 г., г. Новороссийск);

на Международной научной конференции «Научный сервис в сети Интернет: су перкомпьютерные центры и задачи» (20–25 сентября 2010 г., г. Новороссийск);

на XIV Всероссийской конференции "Математическое программирование и при ложения" (28 февраля – 4 марта 2011 г., г. Екатеринбург);

на Международной научной конференции «Научный сервис в сети Интернет: эк зафлопсное будущее» (19–24 сентября 2011 г., г. Новороссийск);

на Международной научной конференции «Параллельные вычислительные техно логии (ПаВТ’2012)» (26–30 марта 2012 г., г. Новосибирск).

Публикации. По теме диссертации опубликовано 10 печатных работ, причем ра боты [1 – 4] опубликованы в журналах, включенные ВАК в перечень журналов, в которых должны быть опубликованы основные результаты диссертаций на соискание ученой сте пени доктора и кандидата наук. Получено 3 свидетельства Роспатента об официальной регистрации программ для ЭВМ. В совместных работах научному руководителю И.М. Соколинской принадлежит постановка задачи, А.В. Ершовой принадлежат все по лученные результаты.





Структура и объем работы. Диссертация состоит из введения, четырех глав, за ключения и библиографии. Объем диссертации составляет 97 страниц, объем библиогра фии – 92 наименования.

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

приводится обзор работ по тематике ис следования и кратко излагается содержание диссертации.

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

Определение 1. Пусть n n. Отображение называется M-фейеровским, если y y, y M ;

x y x y, y M, x M.

xk xk M n Последовательность называется M-фейеровской, если, xk 1 y xk y, k, y M.

Тип 1 (однозначное фейеровское отображение). Пусть в задана конечная сис n тема линейных неравенств Ax b : l j x a j, x b j 0, j 1, (1), m, где a j 0 для любого j. Определим l x max l j x, 0, j 1,, m.

j Тогда фейеровское отображение первого типа имеет вид:

l x m x x j j j 2 a j (2) aj j для любой системы положительных коэффициентов j 0, j 1,, m, таких, что m 1 и коэффициентов релаксации 0 j 2.

j j Тип 2 (многозначное фейеровское отображение) Сконструируем фейеровское отображение второго типа следующим образом:

max l x j j x x a jx, (3) a jx где jx – любой из индексов, на котором достигается max l x, 0 2 – коэффициент j j релаксации.

В завершение главы 1 дается аналитический обзор известных методов решения за дачи сильной отделимости.

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

Пусть даны два выпуклых непересекающихся многогранника M n и N n, заданные системами линейных неравенств:

M x Ax b ;

N x Bx d ;

(4) M N.

Задача сильной отделимости – это задача нахождения слоя наибольшей толщины (-слоя), разделяющего M и N. Сильная отделимость, по существу, эквивалентна задаче отыскания расстояния между M и N в смысле метрики M, N min x y xM, yN. (5) Если x M и y N являются arg-точками задачи (5), то есть (M, N ) x y, то слоем наибольшей толщины, разделяющим множества M и N, является P : {x | x P P2 }, где P и P2 – полупространства, задаваемые линейными 1 неравенствами x x, x y 0 и y y, x y 0.

Таким образом, в краткой форме задачу сильной отделимости можно записать так:

{x, y} Arg min x y x M, y N. (6) Задача сильной отделимости может быть решена с помощью известного метода последовательного проектирования, на основе которого можно построить итерационный алгоритм на базе операции проектирования. Однако, если M и N – произвольные много гранники, то этот алгоритм не может быть признан эффективным, так как не известен универсальный конструктивный метод построения проекции точки на многогранник. Си туацию можно исправить, если вместо операции проектирования использовать фейеров ские отображения.

Пусть задано однозначное отображение FM. Под степенью s ( x) отображения ( x) будем понимать его последовательное применение s раз, то есть.

Под фейеровским процессом, порождаемым однозначным фейеровским отображе нием при произвольном начальном приближении x0 n, будем понимать последова тельность { s ( x0 )}0. Известно, что, в случае, когда однозначное M-фейеровское отобра s жение является непрерывным, фейеровский процесс сходится к точке, принадлежащей множеству M:

{ s ( x0 )}0 x M.

s Для сходящегося фейеровского процесса при произвольном начальном приближе нии x0 введем следующее обозначение lim s ( x0 ) x.

s Это означает, что для любого вещественного 0 существует целое неотрицательное число S такое, что для всех s S имеем xs x.

Определение 2. Пусть задано однозначное непрерывное отображение FM. Под -проектированием (псевдопроектированием) точки x n на множество M будем по нимать отображение M : n M, задаваемое соотношением M ( x) lim s ( x).

s Точку M ( x) будем называть псевдопроекцией точки x на множество M.

Пусть в контексте задачи сильной отделимости (6) заданы два однозначных непрерывных фейеровских отображения: FM, FN. Используя операции – и -проектирования, можно построить следующий алгоритм F, решающий задачу сильной отделимости с использованием фейеровских отображений. Пусть задано произвольное начальное приближение w0 n. Зафиксируем положительное вещественное число.

Алгоритм F состоит из следующих шагов:

Шаг 0. k : 0.

Шаг 1. xk 1 : M wk.

Шаг 2. yk 1 : N wk.

xk 1 yk Шаг 3. wk 1 :.

Шаг 4. k : k 1.

Шаг 5. Если min xk 1 xk, yk 1 yk, перейти на шаг 1.

Шаг 6. Стоп.

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

Пусть задана система линейных неравенств в пространстве n :

Ax b. (7) Пусть y A, b – информационный вектор, задающий все параметры системы (7), nm m y. Обозначим через M y многогранник решений системы (7), определяемой ин формационным вектором y. Имеем M y. Справедлива следующая лемма.

n nm m Лемма 1. Пусть y – информационный вектор, задающий устойчиво совме стную систему неравенств Ax b.

Тогда существует некоторая окрестность V точки y, такая, что любая точка y V также определяет устойчиво совместную систему неравенств Ax b, где y A, b.

Определение 3. Пусть задано отображение : nmm n n двух аргументов. Обозначим через y отображение из nm m y и x в, которое получается n n n из, путем фиксации аргумента y. Отображение является устойчиво фейеровским, если y FM y и существует окрестность V nm m nm m относительно точки y точки y такая, что для любого y V имеем y FM y.

Теорема 1. Пусть отображение : nm m nm m двух аргументов y и n n x является непрерывным по x и у. Пусть система Ax b, определяемая информа n ционным вектором y, является устойчиво совместной и y FM y. Тогда отображение является устойчиво фейеровским относительно точки y nmm. Доказательство теоре мы 1 опирается на лемму 1.

Алгоритм F оказывается эффективным для задач небольшой размерности. Однако для больших задач ( n 500 ) время работы данного алгоритма может составлять сотни часов. В связи с этим в диссертационной работе был разработан новый масштабируемый алгоритм S построения псевдопроекции точки на многогранник с использованием фейеровских отображений, который допускает эффективное распараллеливание на большом количестве процессоров в системах с распределенной памятью. В основе масштабируемого алгоритма построения псевдопроекции на многогранник лежит метод разбиения пространства на подпространства. Для каждого подпространства организуется независимый фейеровский процесс. Через каждые s шагов результаты, полученные на подпространствах, соединяются в один вектор, который и является очередным приближением. Если расстояние между соседними приближениями меньше заданного положительного числа, то полученный вектор принимается в качестве псевдопроекции.

В противном случае вычисления продолжаются.

x через Для произвольного линейного подпространства обозначим n ортогональную проекцию x на линейное подпространство. Везде далее линейное n подпространство будем называть просто подпространством. Через (, x) : min p x p будем обозначать расстояние от точки x до подпространства. Пусть линейное получается из сдвигом на некоторый вектор z : z. Через x многообразие x обозначим ортогональную проекцию на линейное многообразие n :

x x z.

Алгоритм Пусть задано однозначное непрерывное S. M-фейеровское отображение { }, M – выпукло и замкнуто. Зададим разбиение пространства n n при i j.

в прямую сумму ортогональных подпространств: n n, i j 1 r (i 1, Для каждого подпространства, r ) построим линейное многообразие i i следующим образом. Пусть x Arg min ( i, x). Положим z ( x ). Здесь i i i i i xM i обозначает ортогональное дополнение к подпространству. Построим линейное i многообразие путем сдвига подпространства на вектор z i :

i i zi. (8) i i, r} определим отображение i { Для каждого i {1, n }:

i x.

i x (9) i i Зафиксируем некоторое натуральное число s и положительное вещественное число.

Положим x0 0 n.

2 x M z 2 x x xk+ k k xk z 2 xk xk xk 1 z 2 xk 1 xk- x z1 1 x x x k 1 k k z x1 1 x11 zx1 1 z 0 zk k k Рис. 1. Работа алгоритма S: x1 ( xk ), x1 1 1s ( x1 );

xk2 ( xk ), xk21 2s ( xk2 ).

k k k 1 Алгоритм S состоит из следующих шагов:

Шаг 0. k : 0.

xk z i.

r Шаг 1. xk 1 : is i i Шаг 2. k : k 1.

Шаг 3. Если xk 1 xk & d M ( xk 1 ), перейти на шаг 1.

Шаг 4. Стоп.

На шаге 3 алгоритма вычисляется функция невязки d M, которая определяет степень бли зости точки xk 1 к многограннику M.

m d M ( x) max a j, x b j, j Работа алгоритма S для размерности n 2 и s 2 схематично изображена на Рис. 1. Натуральное число s является важным параметром алгоритма S, влияющем на его масштабируемость. Увеличение s ведет к росту ресурса параллелизма, заложенного в алгоритме S. Однако, при выборе слишком большого значения для параметра s после довательность точек xk, порождаемых алгоритмом S на шаге 1, может не попасть на многогранник. В этом случае выход из итерационного процесса произойдет из-за невы полнения условия xk 1 xk, входящего в критерий завершения. Если это произошло, необходимо уменьшить значение s и повторить вычислительный процесс.

Для того чтобы алгоритм S был корректным, необходимо и достаточно, чтобы последовательность точек {xk}, порождаемых алгоритмом S на шаге 1, сходилась. Сле дующая теорема показывает, что каждое отображение i { i i }, строящееся в алго ритме S, является фейеровским относительно множества i M.

Теорема 2. Пусть задано замкнутое множество M n и однозначное M-фейеровское отображение { n n }. Пусть – некоторое собственное линейное, подпространство в пространстве – ортогональное дополнение к подпростран n. Пусть x Arg min (, x). Представим x в виде суммы ортогональных векторов ству xM и : x ( x ) ( x ). Обозначим z ( x ). Построим ли из подпространств на вектор z : z. Опре нейное многообразие путем сдвига подпространства делим отображение { } следующим образом:

x x. (10) Положим M M. (11) Тогда отображение является M -фейеровским.

Справедлива следующая лемма.

Лемма 2. Пусть {xk} – последовательность точек, порождаемых алгоритмом S на шаге 1:

xk 1 : is xk z i ;

k 0,1, r i В условиях алгоритма S определим M i M (i 1,, r ). Положим i x0 i ( x0 ), xk 1 i ( xk ).

i i i Тогда is xk xsi ( k 1), k.

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

Теорема 3. Пусть {xk} – последовательность точек, порождаемых алгоритмом S на шаге 1:

xk 1 : is xk z i ;

k 0,1, r.

i Тогда {xk }0 x n.

k Доказательство теоремы 3 опирается на теорему 2 и лемму 2.

Третья глава, «Параллельные алгоритмы решения задачи слиьной отделимо сти», посвящена вопросам параллелизации алгоритма F решения задачи сильной отдели мости. Приводится описание параллельного алгоритма Simple вычисления псевдопроек ции, основанного на распараллеливании независимых итераций цикла. Для алгоритма Simple строится информационный граф, показывающий, что не существует эффективной реализации этого алгоритма на многопроцессорных системах с распределенной памятью.

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

Сконструируем M-фейеровское отображение следующим образом. Представим систему линейных неравенств, задающих многогранник M, в следующем виде:

Ax b : a j, x b j 0, j 1,, m, где a j 0 для любого j. Тогда отображение вида a max a j, x b j, m x x j j (12) j aj j будет однозначным непрерывным M-фейеровским отображением для любой системы по m ложительных коэффициентов j 0, j 1,, m, таких, что 1 и коэффициентов j j релаксации 0 j 2. Применим к (12) технику разбиения на подпространства. Пусть n – размерность пространства задачи (6). Пусть задано r : r n. Для простоты мы будем считать, что r всегда кратно n : n r l. Пусть задан ортонормированный базис про странства n :

{e1,, en }. (13) Определим i Lin({e1 ( i 1) l,, el (i 1)l }) i j, i 1, для,r. Очевидно, что при и. Пусть n i j 1 r x i Arg min ( i, x). Положим z ( x ) (i 1, i i, r).

i xM i, r определим отображения i { Для i 1, } следующим образом. Пусть n l x, xn ) – координаты вектора x в ортонормированном базисе (13). Тогда n, ( x1, i ( x) ( x1(i 1)l,, xl (i 1)l ). (14) Обозначим i : – ограничение i на подпространство. Произволь n l i i будет иметь в базисе (13) координаты x (0, ный x,0). Со,0, x1(i 1)l,, xl (i 1)l,0, i поставляя это с (14), видим, что отображение i является взаимно-однозначным и для не го существует обратное отображение i 1. В контексте формул (8) и (12) определим i { } следующим образом:

n i m max i (a j ), i ( x) a j, z i b j, i ( x ) i i ( x ) j j i ( a j ).

(15) j aj Выполнение условий алгоритма S обеспечивается следующей теоремой.

Теорема 4. Отображения i (i 1,, r ), определяемые формулой (15), удовлетво ряют тождеству (9).

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

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

Программный комплекс включает в себя следующие программы:

Программа Random генерации случайных многогранников;

Программа Sequence, реализующая последовательный алгоритм;

Программа, реализующая параллельный алгоритм Simple;

Программа, реализующая параллельный алгоритм Block.

Исходные тексты программ свободно доступны в Интернет по адресу http://life.susu.ru/discr/.

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

Программа Sequence, реализует последовательную версию алгоритма F. При этом для построения псевдопроекции точки на многогранник могут использоваться фейеров ские отображения двух типов. 1-й тип вычисляется по формуле (2), 2-й тип – по форму ле (3). Номер типа отображения является параметром программы, задаваемым при ее за пуске.

Программа Simple реализует простой параллельный алгоритм. В качестве техноло гии параллельного программирования была использована библиотека MPI. Параллельный алгоритм Simple использует хорошо известную технику распараллеливания независимых итераций цикла, вычисляющего сумму в формуле (2). Максимальная степень параллелиз ма в этом случае равна m. Подобный алгоритм может показывать хорошее ускорение на многопроцессорных системах с общей памятью. Однако в многопроцессорных системах с распределенной памятью пересылка данных может привести к большим накладным рас ходам.

Программа Block реализует параллельный алгоритм. Параллельная структура про граммы организована по иерархическому принципу. Во главе иерархии стоит процесс «мастер», координирующий работу остальных процессов по выполнению алгоритма F.

Процессу «мастер» подчиняются два независимых процесса-«бригадира». Первый про цесс-«бригадир» вычисляет функцию Pi_Phi_M. Второй процесс-«бригадир» вычисляет функцию Pi_Psi_N. Каждому процессу-«бригадиру» подчинено по r независимых про цессов-«рабочих». «Бригадир» делит полученный от «мастера» вектор на подвекторы и передает их «рабочим». Каждый «рабочий» выполняет s фейеровских итераций в своем подпространстве и передает полученный подвектор «бригадиру», который объединяет подвекторы, пришедшие от различных «рабочих», в единый вектор. «Бригадир» проверя ет критерий завершения итерационного процесса. Если он не выполнен, то «бригадир» снова делит вектор на подвекторы и передает их «рабочим». Если критерий завершения имеет место, то полученный вектор принимается в качестве приближения псевдопроек ции на многогранник и передается «мастеру». «Мастер», получив обе псевдопроекции от «бригадиров», считает очередную среднюю точку и проверяет для нее критерий заверше ния. Если он не выполнен, то мастер передает среднюю точку каждому из «бригадиров» для продолжения вычислений.

Все указанные процессы оформляются как процессы MPI, которые могут запус каться на любом количестве процессоров (процессорных ядер), не превосходящем (2r 3). В предельном случае, когда каждое подпространство имеет размерность 1, име ем r n. Т.е. максимальная масштабируемость алгоритма равняется (2n 3) процессо ров, где n – размерность задачи.

Важным параметром реализации является количество независимых итераций s, выполняемых процессом-«рабочим». Увеличивая s, можно повышать вычислительную нагрузку на те процессоры, на которых выполняются процессы-«рабочие». Это позволяет оптимизировать затраты на пересылку сообщений между «рабочими» и «бригадирами».

На вычислительном кластере «СКИФ-Урал» были проведены вычислительные эксперименты на случайных задачах Random и модельных масштабируемых задачах Model-n (Рис. 2). Для модельных задач можно легко аналитически вычислить точное зна чение толщины максимального разделяющего слоя. Они хорошо подходят для проверки корректности алгоритма, исследования его масштабируемости, и дают хорошую возмож ность для подбора оптимальных значений параметров алгоритма.

Многогранник M Многогранник N x1 2 x2 0 x1 2 x2 x1 2 xn 0 x1 2 xn x1 2 x2 20000 x1 2 x2 x1 2 xn 20000 x1 2 xn x1 0 x1 x2 0 x2 Итерации алгоритма F для задачи Model-3.

xn 0 xn Рис. 2. Модельная задача Model-n.

С помощью программы Sequence была исследована последовательная реализация алгоритма F для фейеровских отображений двух типов на модельных задачах Model-n (Рис. 3 и Рис. 4) и случайных задачах Random (Рис. 5, Рис. 6). Первый тип вычислялся по формуле (2), второй – по формуле (3). Эксперименты показали, что тип используемого фейеровского отображения может существенно влиять на скорость работы алгоритма.

Далее был исследован последовательный алгоритм Simple. На основе проведенных экспериментов (Рис. 7) можно сделать вывод, что алгоритм Simple может эффективно ра ботать только на небольшом (до 16) количестве процессорных ядер.

Рис. 3. Зависимость количества итераций от Рис. 4. Зависимость времени решения задачи размерности n для Model-n. Model-n от размерности n.

Рис. 6. Зависимость времени решения задач Рис. 5. Зависимость количества итераций от Random от размерности n.

размерности n для Random.

Рис. 8. Ускорение для задачи Model-n.

Рис. 7. Ускорение алгоритма Simple для задачи Model-n.

Также в вычислительных экспериментах был исследован параллельный алгоритм Block, разработанный в рамках настоящего диссертационного исследования. Были иссле дованы различные параметры алгоритма Block и даны рекомендации по выбору их значе ний. Проведено исследование ускорение параллельного алгоритма Block (Рис. 8). Ускоре ние вычислялось по формуле t p / t64, где t64 – время, затраченное на решение задачи Model-n на 64 процессорных ядрах, t p – время, затраченное на решение этой же задачи на p процессорных ядрах. Эксперименты проводились для трех размерностей: n 1024, n 1536 и n 2048, при фиксированном s 10000 и r p. Для каждой размерности варьировалось количество процессорных ядер, используемых для решения задачи. Во всех трех случаях наблюдалось ускорение, близкое к линейному, вплоть до 512 процес сорных ядер. Далее рост ускорения замедлялся. Однако при больших размерностях «заго ризонталивание» кривой ускорения происходило позже.

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

Основные результаты диссертационной работы На защиту выносятся следующие новые научные результаты.

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

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

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

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

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

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

Публикации по теме диссертации Статьи, опубликованные в журналах из списка ВАК Ершова А.В. Алгоритм разделения двух выпуклых непересекающихся многогранни 1.

ков с использованием фейеровских отображений // Системы управления и информа ционные технологии. 2009. № 1(35). С. 53-56.

Ершова А.В., Соколинская И.М. Параллельный алгоритм решения задачи сильной от 2.

делимости на основе фейеровских отображений // Вычислительные методы и про граммирование. 2011. Т. 12, № 2. С. 178-189.

Ершова А.В., Соколинская И.М. О сходимости масштабируемого алгоритма построе 3.

ния псевдопроекции на выпуклое замкнутое множество // Вестник ЮУрГУ. Серия “Математическое моделирование и программирование”. 2011. № 37(254), вып.10.

C. 12-21.

Ершова А.В., Соколинская И.М. Исследование устойчивости параллельного алгоритма 4.

решения задачи сильной отделимости на базе фейеровских отображений // Вестник ЮУрГУ. Серия “Математическое моделирование и программирование”. 2012. № (277), вып.12. C. 5-12.

Другие публикации Ершова А.В. Задача разделения двух выпуклых многогранников с использованием 5.

фейеровских отображений // Алгоритмический анализ неустойчивых задач: Тезисы докладов Международной конференции (1–6 сентября 2008 г., г. Екатеринбург). Ека теринбург: Изд-во Урал. ун-та, 2008. С. 274-275.

Ершова А.В. Метод решения задачи сильной отделимости для многопроцессорных 6.

систем с массовым параллелизмом // Параллельные вычислительные технологии (ПаВТ’2010): Труды международной научной конференции (29 марта – 2 апреля г., г. Уфа). Челябинск: Издательский центр ЮУрГУ, 2010. С. 660-661.

Ершова А.В. Алгоритм решения задачи сильной отделимости на базе фейеровских 7.

отображений // Тезисы докладов XVIII Международной конференции «Математика.

Экономика. Образование» (25 мая – 1 июня 2010 г., г. Новороссийск). Ростов-на Дону: Изд-во СКНЦ ВШ ЮФУ, 2010. С. 131-132.

Ершова А.В., Соколинская И.М. Параллельный алгоритм разделения двух выпуклых 8.

непересекающихся многогранников с использованием фейеровских отображений // Научный сервис в сети Интернет: суперкомпьютерные центры и задачи: Труды меж дународной научной конференции (20–25 сентября 2010 г., г. Новороссийск). М.:

Изд-во МГУ, 2010. С. 242-248.

Ершова А.В. Параллельный метод решения задачи сильной отделимости на базе фей 9.

еровских отображений // Информационный бюллетень Ассоциации математического программирования. №12. Научное издание. (28 февраля – 4 марта 2011 г., г. Екате ринбург) Екатеринбург: УрО РАН, 2011. С. 85-86.

10. Ершова А.В., Соколинская И.М. Масштабируемый параллельный алгоритм построе ния псевдопроекций в задачах сильной отделимости // Научный сервис в сети Интер нет: экзафлопсное будущее: Труды международной научной конференции (19– сентября 2011 г., г. Новороссийск). М.: Изд-во МГУ, 2011. С. 132-138.

Свидетельства о регистрации программ 11. Ершова А.В. Свидетельство Роспатента об официальной регистрации программы для ЭВМ "Последовательный алгоритм решения задачи разделения двух выпуклых непе ресекающихся многогранников на базе фейеровских отображений" № 2010616104 от 16.09.2010.

12. Ершова А.В. Свидетельство Роспатента об официальной регистрации программы для ЭВМ "Генерация двух выпуклых непересекающихся многогранников" № от 16.09.2010.

13. Ершова А.В. Свидетельство Роспатента об официальной регистрации программы для ЭВМ "Параллельный алгоритм решения задачи разделения двух выпуклых непересе кающихся многогранников на базе фейеровских отображений" № 2011610980 от 26.01.2011.

Работа выполнялась при поддержке Российского фонда фундаментальных исследований (проекты 09-01-00546а и 12-01-00452а).

Подписано в печать 28 апреля 2012 г.

Формат 60х84 1/16. Бумага офсетная.

Печать офсетная. Усл. печ. л. 1,0. Уч.-изд. л. 1,2.

Тираж 100 экз.

Типография «Фотохудожник» 454091, г. Челябинск, ул. Свободы, 155/

 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.