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

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

131

называемое характеристикой интервала.

Этап 6 (упорядочение характеристик). Характеристики

,),(

IiiR ∈

упорядочиваются по убыванию:

)()()()(

121

ττ

tRtRtRtR ≥≥≥≥

−

. (29)

Этап 8 (формирование координат испытаний). В

последовательности (29) выбираются

≤

= )1(npp

наибольших

характеристик с номерами

,1, pit

≤

и в интервалах,

соответствующих этим характеристикам, формируются точки

испытаний

pkk

новой

)1( +n

-й итерации согласно

выражениям

xxx

)(

−

−+=

(30)

для

ps ≤≤1

Этап 9 (завершение параллельной итерации). Если

≤

−

≤≤

)(min

(31)

где

- заданная точность поиска, то поиск прекращается и в

качестве решения принимается величина

)(min

≤≤

, а также ее

координата.

Если же (31) не выполняется, осуществляется параллельная

итерация метода, т.е. вычисление в точках

,1, psx

≤≤

значений

функции

)(

- каждое испытание на своем процессоре. После

этого номер итерации

увеличивается на единицу, количество

испытаний

)1(

становится равным

pnk

)(

и происходит переход

Этапу 2.

Описание алгоритма завершено.

Вследствие (26), (27), (30) координата

нового испытания

неизбежно попадает внутрь интервала

),(

1−

и порождает два

новых разрешенных интервала, что означает невозможность

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

. Как следствие,

использование алгоритма в структуре рекурсивной схемы (19)

обеспечивает проведение испытаний только в допустимой области (2).

132

Заметим, что описанный алгоритм реализует синхронную схему

организации вычислений индексного метода, когда процессор,

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

процессоров, участвующих в параллельной итерации метода. Однако

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

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

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

в которых не

завершено вычисление значения функции.

Из результатов работы [4] следует, что теоретические свойства

сходимости метода (как в синхронном, так и в асинхронном варианте)

совпадают со свойствами его последовательного прототипа [1, 2]. В

частности, если целевая функция

)(x

удовлетворяет в области

условию Липшица с константой

0>L

, то при

Lm 2>

метод будет

сходиться ко всем точкам глобального минимума функции

)(x

только к таким точкам. Кроме того, для алгоритма справедливы

оценки избыточности, полученные в [4].

Как отмечено в [5 - 7], многошаговая схема в сочетании с

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

параллелизма. А именно, если на всех итерациях метода, решающего

одномерные задачи, связанные с координатой

, используется

процессоров, тогда для решения задачи (1)-(3) можно использовать

вплоть до

∏

(32)

параллельно работающих процессоров. При этом в рамках

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

существовать до

pP /

одномерных подзадач (19), решаемых

одновременно.

Работа выполнена при поддержке РФФИ (грант № 07-01-00467).

Литература

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

convex constraints: Sequential and parallel algorithms, Kluwer

Academic Publishers, Dordrecht, Netherlands. 2000.

133

Стронгин Р.Г. Численные методы в многоэкстремальных

задачах. Информационно- статистический подход. М.: Наука,

1978.

Strongin R.G., Markin D.L. Minimization of multiextremal

functions with nonconvex constraints. Cybernetics 22, 1986. P.

486-493.

Strongin R.G., Sergeyev Ya.D., Grishagin V.A. Parallel

Characteristical Algorithms for Solving Problems of Global

Optimization // Journal of Global Optimization,10, 1997. P. 185–

206.

Sergeyev Ya.D., Grishagin V.A. Parallel asynchronous global

search and the nested optimization scheme, Journal of

Computational Analysis & Applications, 3(2), 2001. P. 123–145.

Гришагин В.А., Сергеев Я.Д. Эффективность

распараллеливания характеристических алгоритмов

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

размерности. // Высокопроизводительные параллельные

вычисления на кластерных системах. Материалы четвертого

Международного научно-практического семинара и

Всероссийской молодежной школы / Под ред. В.А.Сойфера.

Самара: Изд-во Самарского научного центра РАН, 2004. С. 70-

74.

Гришагин В.А., Сергеев Я.Д. Параллельный метод решения

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

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

вычисления на кластерных системах: Материалы пятого

Международного научно-практического семинара / Под ред.

Р.Г. Стронгина. Нижний Новгород: Изд-во Нижегородского

госуниверситета, 2005. С. 74-83.

134

РАЗРАБОТКА СИСТЕМЫ УПРАВЛЕНИЯ

ИНТЕГРИРОВАННОЙ СРЕДОЙ

ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ВЫЧИСЛЕНИЙ ННГУ

В.В. Домрачев, А. В. Сенин

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

Введение

Всё больше и больше появляется задач, требующих привлечения

больших вычислительных ресурсов. Это связано с тем, что произошли

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

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

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

моделирования и численного эксперимента. Численное

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

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

явления, которые

являются либо слишком сложными для

исследования аналитическими методами, либо слишком

дорогостоящими или опасными для экспериментального изучения.

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

процесс научного и технологического поиска. Стало возможным

моделировать в реальном времени процессы интенсивных физико-

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

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

и т.д.

Для этого понадобилось создание дорогостоящих

сверхпроизводительных вычислительных систем (суперкомпьютеров).

Для решения сложных вычислительных задач всё больше

используются кластерные системы. Вычислительный кластер – это

совокупность компьютеров, соединённых сетью и работающих как

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

показателей, а цена их остаётся сравнительно низкой. Таким образом,

кластер может быть

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

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

кластерных технологий за последние годы хорошо видно из анализа

списка Тор500: c 2000 по 2006 г. доля кластеров в списке изменилась с

2.2% до 72.2%. Этот бурный рост обусловлен тем, что кластерные

системы стоят существенно меньше многопроцессорных

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

меньшую

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

135

Для управления компьютерами в составе кластера необходимо

специальное программное обеспечение – система управления

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

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

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

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

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

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

как единого

вычислительного ресурса.

В середине 2007 года ННГУ приобрел мощный вычислительный

кластер, состоящий из 64 двухпроцессорных серверов Intel Xeon 5150

2,66 ГГц с 4 Гб оперативной памяти каждый. В качестве сетевого

интерфейса используется Gigabit Ethernet. Кроме того, в ННГУ

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

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

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

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

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

администрирования необходимо интегрировать вычислительный

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

единой системой. Однако это осложнено тем, что в части лабораторий

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

(Microsoft Compute Cluster Server 2003, PBS). Кроме того, часть

лабораторий работают под управлением операционной системы

Windows, а часть – Linux. Указанные факторы

делают чрезвычайно

сложным или даже невозможным внедрение одной из существующих

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

ННГУ, что обусловливает необходимость создания собственной

системы.

В рамках учебно-исследовательской лаборатории

«Информационные технологии» существует проект «Метакластер»,

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

важнейшими отличительными особенностями которой являются

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

кластерами,

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

предоставление удалённого доступа и интеграция с другими

системами управления.

136

Описание проекта «Метакластер»

Основными требованиями, выдвигаемыми к создаваемой системе

управления кластером, являются следующие:

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

кластерами на базе различных операционных систем

(Windows, Linux) и систем управления кластерами (Windows

CCS, PBS);

 предоставление удобного способа доступа через сеть

Интернет или Интранет;

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

задачами: запуск, получение статуса, остановка выполнения,

получение результатов вычислений.

Система имеет уникальную архитектуру, она состоит из трёх

компонентов (см. рис. 1).

Пользовательский компьютер

Менеджеры задач (Windows)

Менеджер задач

(Windows)

Менеджер задач

(Linux)

Диспетчер доступа

Интегратор кластеров

Рис. 1. Общая архитектура системы «Метакластер 2.0»

Диспетчер доступа

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

пользователя с системой. С его помощью можно запускать задачи с

удалённого компьютера через сеть Интернет (в частности, веб-

интерфейс). Компонент проводит регистрацию пользователей в

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

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

задач, возвращать результаты работы пользователю.

137

Интегратор кластеров

Интегратор является связующим звеном, которое объединяет

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

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

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

ресурсов любой сложности. В состав интегратора входит

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

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

имеющейся

информации о загруженности кластеров, предыдущем

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

запросу предоставляет необходимую информацию (ход выполнения

заданий, информация о загруженности кластера, результаты

вычислений).

Менеджер задач

Компонент, фактически являющейся локальной системой

управления кластером, на котором он установлен. Менеджер задач

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

вычислительных узлов, сбор и сохранение результатов работы

вычислительных задач (стандартный поток вывода и сгенерированные

файлы). В том случае, если на кластере уже установлена система

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

выступать

промежуточным звеном, транслирующим команды

интегратора в команды установленной системы. Каждый менеджер

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

он будет работать (операционная система, установленное программное

обеспечение, возможно, аппаратные характеристики). Благодаря

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

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

операционными системами и различными аппаратными

характеристиками.

Текущее состояние разработки

В настоящее время в системе реализована следующая

функциональность:

 обеспечение доступа к системе через web-интерфейс;

 поддержка базового набора операций: загрузка задачи на

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

остановка задачи, просмотр состояния задачи;

138

 поддержка произвольного числа кластеров на базе ОС

Windows и возможность интеграции с Microsoft Compute

Cluster Server 2003.

Разрабатываемая система управления в настоящее время

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

ННГУ, мини-кластер (оба под управлением Microsoft CCS 2003) и

8-узловый кластер под управлением Менеджера задач «Метакластера».

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

систему управления «Метакластер», используются широким

кругом

исследовательских проектов как из ННГУ, так и из других

университетов. В числе проектов можно упомянуть проект по

моделированию работы сердца кафедры ТУДМ факультета ВМК

ННГУ, проекты «ПараЛаб» и «Абсолют», выполняемые на кафедре

МО ЭВМ, проект «Финансовая математика» лаборатории

«Информационные технологии».

Планы дальнейшего развития

Можно выделить следующие основные направления дальнейшей

работы:

Расширение функциональности системы для операционной

системы Windows, разработка версий для Linux, FreeBSD.

Интеграция с другими системами управления кластерами (в

ближайших планах – PBS).

Разработка программ-клиентов с командным и графическим

интерфейсами.

Расширение сохраняемой статистики использования

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

Большое внимание планируется уделить вопросам

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

кластера и обеспечению безопасной и отказоустойчивой работы

кластеров, в том числе:

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

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

Вопросы шифрования при обмене информацией по сети.

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

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

139

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

самовосстановление системы в случае аварийного завершения

работы.

Литература

1. Baker M. et al. Cluster Computing White Paper. Final Release,

Version 2.0.

By Thomas Sterling. Beowulf Cluster Computing with Windows.

The MIT Press, Cambridge, Massachusetts, 2002 y.

Microsoft Windows Compute Cluster Server 2003 Beta 2

Reviewers Guide

(http://www.microsoft.com/windowsserver2003/ccs/reviewersguid

e.mspx).

Боголепов Д., Алехин А. Архитектура системы мониторинга

GPM. (http://www.software.unn.ac.ru/grid/).

Гергель В.П. Теория и практика параллельных вычислений.

(http://www.software.unn.ac.ru/ccam/kurs1.htm).

Гергель В.П., Стронгин Р.Г. Высокопроизводительный

вычислительный кластер Нижегородского университета – //

Материалы конференции Relam. Н. Новгород, 2002 г.

ОПТИМАЛЬНАЯ ДЕКОМПОЗИЦИЯ ВЫЧИСЛИТЕЛЬНЫХ

ЗАДАЧ В КОРПОРАТИВНЫХ ГРИД-СИСТЕМАХ НА ОСНОВЕ

INTEL GRID PROGRAMMING ENVIRONMENT

А.В. Дунаев, А.В. Ларченко, А.В. Бухановский

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

информационных технологий, механики и оптики

Современный этап развития технологий Грид характеризуется

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

Классические (и независимые) определения, сформулированные I.

Foster и С. Kesselman [1] и M. Livny [2], по мере внедрения Грид

расширяются и модифицируются. В обзорной работе [3] отмечается,

что основной чертой Грид, отделяющей его от других систем

распределенных

вычислений (например, P2P, utility computing и пр.),

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

осуществляется объединение вычислительных и информационных

ресурсов. Как следствие, в настоящее время наиболее часто Грид

140

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

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

главу угла ставится виртуализация вычислительных ресурсов, а не

пользовательских приложений. Это связано как с технологическими

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

коммерческого использования [4].

В рамках определения [3] допустимой является интерпретация

Грид как

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

традиционными (например, кластерными, гибридными, P2P)

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

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

параллельных вычислений связана с объединением и синхронизацией

большого количества вычислительных узлов (в общем случае -

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

для решения одной задачи. Очевидно, что

параллельные вычисления в

Грид по производительности не могут сравняться с традиционными

кластерными системами в силу высокой коммуникационной

составляющей. Однако использование концепции Грид способно

предоставить пользователю сравнительно дешевую и неограниченно

расширяемую параллельную архитектуру. Как следствие,

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

связанные с моделированием сложных систем [5], состоящих из

огромного количества

взаимодействующих объектов с дальними

связями, размещаемых в оперативной памяти.

В докладе рассматриваются особенности организации

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

Intel Grid Programming Environment (GPE). Для реализации

параллельных вычислений общего вида на основе среды Intel GPE

авторами разработана программная система PEG (Parallel Execution on

GPE). Ее назначением является автоматизация и упрощение процесса

переноса параллельных приложений кластерного уровня под Грид.

PEG

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

интерфейсов (API). Он позволяет «обернуть» готовую программу и

выполнять ее параллельно, если распараллеливание ведется

функционально или по данным. Однако, несмотря на кажущуюся

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

Грид по сравнению, например, с кластерными системами, даже на

корпоративном уровне требует учета ряда специфических факторов, в

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