Стронгин Р.Г (ред.) Высокопроизводительные параллельные вычисления на кластерных системах

Подождите немного. Документ загружается.

О ПРАКТИЧЕСКОМ ПРИМЕНЕНИИ

ПАРАЛЛЕЛЬНОЙ СИСТЕМЫ ОПТИМИЗАЦИИ

ABSOLUTE EXPERT

К.А. Баркалов

Нижегородский государственный университет

Введение

Работа выполнена в рамках совместного проекта «Быстрые

вычисления в глобальной оптимизации: последовательные и

параллельные среды» между ННГУ и Технологическим университетом

г. Делфта, Нидерланды (TUDelft). Задачами проекта являлись

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

использование для решения вычислительно

-трудоемких задач на

высокопроизводительных кластерных системах. Инженерным

приложением являлась задача поиска оптимального профиля колеса

для рельсовых видов транспорта: метро, трамвай и т.п.

Содержательная постановка задачи

Рассматривается задача оптимизации профиля рельсового колеса

([1], [2]). Вследствие конической формы колеса центр колесной пары

совершает синусоидальные движения (см. рис. 1). Кинематические

свойства контакта колеса с рельсом

, такие как радиус вращения, угол

контакта и угол наклона колесной пары, варьируются при поперечном

– относительно рельса – смещении колесной пары. Зависимость между

этим изменениями и поперечной позицией колесной пары

определяется профилем колеса и рельса.

Рис. 1

Важной характеристикой контакта колеса и рельса является радиус

вращения колеса в контактной точке. Фактически радиус может быть

разным для правого и левого колес, так как колесная пара смещается

по рельсу (радиусы r

и r

соответственно на рис. 2).

Рис. 2

Когда колесная пара находится в центральной позиции, радиусы

вращения левого и правого колес совпадают, т.е.

= r

= r . Отличие

между радиусами вращения левого и правого колес может быть

определено как функция бокового смещения y колесной пары по

отношению к ее центральной позиции

r(x)=r

(x)

−

(x).

Математическая модель

Профиль колеса описывается с помощью B-сплайна, для

построения которого выбирается множество точек на кромке,

основании кромки и поверхности качения колеса (рис. 3). Положение

этих точек может варьироваться с целью изменения профиля. Для

уменьшения трудоемкости задачи оптимизации положение точек на

верху кромки и конической части профиля фиксируется, так как эти

части колесного профиля не участвуют в контакте с рельсом.

Рис. 3

В качестве компонент вектора y параметров задачи оптимизации

выбраны ординаты

подвижных точек сплайна, т.е.

y=[z

,…,z

при этом абсциссы данных точек фиксированы.

В рассматриваемой задаче число подвижных точек –

следовательно, и число переменных – составляет N=11, границы

изменения параметров [–1, 1]; минимизируется разность радиусов

вращения

r(x), а ограничения вводятся из соображений устойчивости

(например, одно из ограничений наложено на максимальный угол

наклона колесной пары).

Таким образом, возникает задача оптимизации с числом

параметров N

11, числом ограничений m

6; целевая функция и

функции ограничений – многоэкстремальные. Для иллюстрации на

рис. 4 приведено одномерное сечение целевой функции.

Рис. 4

Указанная задача является вычислительно-трудоемкой: проверка

ограничений задачи и вычисление значения целевой функции в одной

точке занимает 20 сек. (Pentium IV, 3 ГГц). Для функции с такой

вычислительной трудоемкостью определение значения градиента в

точке занимает 7 минут, что делает весьма затратным применение

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

В Технологическом университете г. Делфта для решения

задачи

применялась система оптимизации MARS (см. [3]). В данной системе

решение исходной задачи оптимизации сводится к решению

последовательности задач квадратичного программирования. Тем

самым гарантируется сходимость, вообще говоря, лишь к локально-

оптимальному решению исходной многоэкстремальной задачи. С

помощью системы MARS было получено локально-оптимальное

решение, которому соответствует значение

=3.89 целевой функции.

Параллельная система оптимизации Absolut Expert

С целью получения глобально-оптимального решения задачи была

использована параллельная система оптимизации Absolut Expert,

разработанная на кафедре МО ЭВМ факультета ВМК ННГУ. В основе

алгоритмов, реализованных в системе, лежит индексный метод

глобальной оптимизации, разработанный под руководством Стронгина

Р.Г. (см. [4] – [8]).

Рассмотрим общую постановку задачи оптимизации

ϕ∗

∗

)

min

{ϕ

(y)

∈

D, g

(y)

≤

0, 1

≤

}

∈

: a

≤

, 1

≤

}

(1)

целевая функция

(y) и левые части ограничений g

(y),1

≤

предполагаются липшицевыми с соответствующими константами

≤

Используя кривые типа развертки Пеано y(x), однозначно

отображающие отрезок [0,1] на N-мерный гиперкуб D

∈

−

≤

−

1, 1

≤

}

{

y(x)

≤

}

исходную задачу можно редуцировать к следующей одномерной

задаче:

(y(x

∗

))=min

{ϕ

(y(x))

∈

[0,1], g

(y(x))

≤

0, 1

≤

}

Редукция многомерных задач к одномерным с помощью разверток

имеет такие важные свойства, как непрерывность и сохранение

равномерной ограниченности разностей функций при ограниченности

вариации аргумента. Однако при этом происходит потеря части

информации о близости точек в многомерном пространстве, ибо точка

∈

[0,1] имеет лишь левых и правых соседей, а соответствующая ей

точка y(x)

∈

имеет соседей по 2

направлениям. Как результат, при

использовании отображений типа кривой Пеано близким в N-мерном

пространстве образам y', y'' могут соответствовать достаточно далекие

прообразы x', x'' на отрезке [0,1].

В работе [5] предложен возможный способ преодоления этого

недостатка, идея которого заключается в одновременном

использовании множественных отображений

(x)=

{

(x),…, y

(x)

}

вместо применения единственной кривой Пеано y(x), что сводит одну

многомерную задачу к нескольким связанным одномерным задачам.

Каждая кривая Пеано y

(x) из Y

(x) может быть получена в

результате некоторого сдвига вдоль главной диагонали

гиперинтервала D. Таким образом сконструированное множество

кривых Пеано позволяет получить для любых близких образов y', y'',

отличающихся только по одной координате, близкие прообразы x', x''

для некоторого отображения y

(x).

Использование множества отображений приводит к

формированию соответствующего множества одномерных

многоэкстремальных задач

min

{ϕ

(x))

∈

[0,1], g

(yl(x))

≤

0, 1

≤

}

, 1

≤

(2)

Каждая задача из данного набора может решаться независимо, при

этом любое вычисленное значение z

(y'),

ν=ν

(y'), y'

(x') функции

(y) в i-й задаче может интерпретироваться как вычисление значения

(y'),

ν=ν

(y'), y'

(x'') для любой другой s-й задачи без повторных

трудоемких вычислений функции g

(y).

Подобное информационное единство дает возможность решать

исходную задачу (1) путем параллельного решения индексным

методом L одномерных задач вида (2) на наборе отрезков [0,1]. Каждая

одномерная задача (или группа задач при недостаточном количестве

процессоров) решается на отдельном процессоре. Результаты

испытания в точке x

, полученные конкретным процессором для

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

всех остальных задачах (в соответствующих точках x

,…,x

Подробное описание решающих правил параллельного алгоритма

глобальной оптимизации см. в работе [8].

Результаты экспериментов

Задача решалась на вычислительном кластере из 4 компьютеров

(Pentium IV, 3 ГГц, сеть 100 Мбит, под управлением WindowsXP,

использовался MPI в реализации MPICH 1.2.5) с помощью

параллельного индексного метода с множественной разверткой. Число

разверток соответствовало числу процессоров L=4.

С помощью системы Absolute Expert было получено решение

*=3.94, которое было локально уточнено до значения

*=3.86. Всего

для получения решения потребовалось 26 часов машинного времени,

при этом функционалы задачи были оценены в 4297 точках. Расчеты,

проведенные специалистами TUDelft для колеса оптимизированного

профиля, показали, что его ресурс возрос до 120000 км пробега (более

чем в пять раз по сравнению с колесом оригинального профиля), а

максимально допустимая скорость – с 40 до 60 м/сек

Результаты работы используются в Технологическом университете

г. Делфта (Нидерланды).

Работа выполнена при финансовой поддержке РФФИ (номер

проекта 07-01-00467) и Нидерландской организации по научным

исследованиям (the Netherlands Organisation for Scientific Research),

номер проекта 047.016.014.

Литература

1. Shevtsov I.Y., Markine V.L., Esveld C. Optimal design of wheel

profile for railway vehicles // Proceedings 6th International

Conference on Contact Mechanics and Wear of Rail/Wheel

Systems, Gothenburg, Sweden, June 10 – 13, 2003. Pp. 231 – 236.

2. Shevtsov I.Y., Markine V.L., Esveld C. An inverse shape design

method for railway wheel profiles. Structural and Multidisciplinary

Optimization. Volume 33, № 3, Springer Berlin/Heidelberg, 2007.

Pp.243 – 253.

3. Toropov V.V., Keulen F., Markine, V.L., Alvarez L.F. Multipoint

Approximations Based on Response Surface Fitting: a Summary of

Recent Developments // In V.V. Toropov (Ed.) Proceedings of the

1st ASMO UK/ISSMO Conference on Engineering Design

Optimization, Ilkley, West Yorkshire, UK, 1999. Pp. 371 – 381.

4. Стронгин Р.Г. Поиск глобального оптимума. М.: Знание, 1990.

5. Стронгин Р.Г. Параллельная многоэкстремальная

оптимизация с использованием множества разверток// Ж.

вычисл. матем. и матем. физ. 1991. Т.31. №8. С. 1173 – 1185.

6. Стронгин Р.Г., Баркалов К.А. О сходимости индексного

алгоритма

в задачах условной оптимизации с ε-

резервированными решениями// Математические вопросы

кибернетики. М.: Наука, 1999. С. 273 – 288.

7. Баркалов К.А. Ускорение сходимости в задачах условной

глобальной оптимизации. Нижний Новгород: Изд-во

Нижегородского гос. ун-та, 2005.

8. Strongin R.G., Sergeyev Ya.D. Global optimization with non-

convex constraints. Sequential and parallel algorithms. Kluwer

Academic Publishers, Dordrecht, 2000.

ВЕБ-СЕРВИС ПОСТРОЕНИЯ НАГЛЯДНЫХ СХЕМ

ПРОЦЕССОВ В ПРОГРАММАХ НА ЯЗЫКЕ OCCAM

В.Н. Белов, А.С. Сарайкин

Пензенский государственный университет

Введение

Параллельные вычисления уже долгое время являются одной из

приоритетных областей научных и практических исследований для

вычислительной техники. Постоянно создаются новые и

совершенствуются существующие аппаратные и программные

средства для более эффективного решения задач. Одним из таких

программных средств является язык Occam.

Язык программирования Occam — это процедурный язык

параллельного программирования высокого уровня, разработанный

группой учёных из Оксфорда в рамках работ по созданию

транспьютеров.

В основе языка лежит так называемая CSP-концепция (концепция

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

Ч.Хоаром. В сущности, CSP — это

формализм для описания

соответствующей вычислительной модели, достаточно

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

теоремы, и достаточно мощный и однозначный, чтобы являться

языком программирования.

Базовые концепции языка, в частности такое свойство, как

концепция выполнения параллельных процессов, которые не

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

помощью каналов

связи, потенциально позволяют получать продукт

высокой целостности, так как при этом поддерживается определенная

форма ограничения распространения ошибок.

Развитие языка Occam идет в сторону добавления новых типов

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

программирование. При этом философия языка не пересматривается,

что свидетельствует об ее изначальной удачности. Реализации Occam

существуют для разных, в том

числе нетранспьютерных архитектур.

Таким образом, он может использоваться и для создания программ для

обычных ПК. Спектр его применения чрезвычайно широк: от

скринсейверов и программ построения фракталов до серверов

многопользовательских компьютерных игр, хотя, разумеется, наиболее

оправдано использование языка Occam для создания параллельных

программ. Известны также библиотеки, реализующие примитивы

базовой для Occam концепции CSP, что позволяет

программировать в

стиле Occam на других языках.

Постановка задачи

Несмотря на понятность концепции языка и синтаксис, изначально

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

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

возникновения и выполнения, что в той или иной степени характерно

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

мыслить в терминах параллельных процессов и писать параллельные

программы намного сложнее, чем классические. Это приводит к тому,

что при изучении языка параллельного программирования появляются

сложности в понимании работы алгоритмов параллельных

вычислений, что тормозит процесс обучения. Даже после освоения

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

проблемы при отладке программ, что

зачастую вызвано недостаточной

наглядностью исходных кодов. Несмотря на обязательное

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

ошибку, приводящую к неправильной последовательности

выполнения процессов.

Представляется необходимым создание программного средства,

которое позволит наглядно показывать структуру Occam-программы в

характерных для языка терминах.

Краткое описание проекта

Для решения поставленной задачи был создан веб

-сервис, который

позволит по исходным кодам Occam-программы получить

представление о протекающих во время ее исполнения процессах.

Пользователю достаточно зайти на веб-страницу и отправить на

обработку текст программы. В результате он получит графическую

схему, иллюстрирующую работу приложения в терминах процессов,

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

детализации веток приложения,

каждый раз получая новую схему,

наглядно отображающую все необходимые данные, в том числе и

исходный текст, формирующий процессы Occam-программы.

Веб-сервис реализован как CGI-программа на языке Perl. В рамках

одного CGI-сценария производится синтаксический разбор

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

схемы программы и формирование ответа. Благодаря большим

возможностям языка Perl использование других программных

средств

на серверной стороне не требуется, что также уменьшает затраты

системы на обработку запроса. Имеются и другие особенности языка

Perl, в силу которых он был выбран в качестве основного при

реализации проекта:

 Perl имеет богатые возможности для работы с текстом,

реализованные при помощи регулярных выражений, что

представляется критичным в рамках

данного проекта;

 сценарии Perl выполняются на сервере, что позволяет

пользователю не беспокоиться о наличии на локальном

компьютере специфических программных средств;

 Perl - кроссплатформенный язык программирования,

программы, написанные на Perl, работают на UNIX, Windows,

Macintosh, VMS и других платформах;

 имеется возможность писать программы как с использованием

процедур, так и с помощью объектов.

Однако Perl не предоставляет возможности для

создания

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

наглядности схемы программы. Для решения этой проблемы в HTML-

страницы вставляются команды JavaScript, обеспечивающие

необходимое взаимодействие с пользователем. На JavaScript

реализованы всплывающие подсказки, ставящие в соответствие

элементам схемы программы фрагменты ее исходных кодов. Выбор в

пользу данной технологии сделан в силу того, что она

изначально

ориентирована на подобные задачи и поддерживается большинством

современных браузеров.

Данный веб-сервис может быть размещен на большинстве

существующих Интернет-серверов и должен принести ощутимую

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

языка Occam.

РАСПАРАЛЛЕЛИВАНИЕ АЛГОРИТМА ВЕЙВЛЕТ-

ПРЕОБРАЗОВАНИЯ ПРИ ВЫЯВЛЕНИИ ПОВЕРХНОСТНЫХ

ДЕФЕКТОВ ЛИСТОВОГО МЕТАЛЛА ПРИ ОБРАБОТКЕ

НА ПРОКАТНОМ СТАНЕ

Д.П. Бугаев

Оренбургский государственный университет

При обработке цифровые изображения необходимо обозревать или

обрабатывать при различных увеличениях и разрешениях, для этих

целей используется дискретное вейвлет-преобразование (DWT).

Помимо того, что вейвлет-преобразование является весьма

эффективным и интуитивно понятным инструментом для

представления и хранения кратномасштабных изображений, оно